System for secure and private communication in a triple-connected network

• US 5,161,186 A
• Filed: 09/06/1991
• Issued: 11/03/1992
• Est. Priority Date: 09/06/1991
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dwork, Cynthia, Dolev, Danny
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US07/756,276
• Time in Patent Office: 424 Days
• Field of Search: 380/2, 370/16, 375/38, 340/825.01, 371/8.2, 371/67.1, 371/68.1, 371/68.2
• US Class Current: 380/2
• CPC Class Codes: H04L 1/22 using redundant apparatus to increase reliability
• CPC Class Codes: H04L 9/004 for fault attacks

Abstract

An apparatus and method for secure and private communications in a triple-connected processor network. Communication of a message over at least three data paths is achieved by transmitting the message in coded form over the data paths, determining whether the message is correctly received, and if the message is not correctly received, identifying a non-faulty data path, testing remaining data paths to identify a faulty data path, and transmitting the message in coded form over remaining non-faulty data paths.

Claims

1. A method for the private and secure communication of a message over at least three data paths, comprising the steps of:

transmitting a message in coded form over three of said data paths;

determining whether the message is correctly received;

if the message is not correctly received, testing the data paths to identify a faulty data path;

transmitting the message in coded form over the remaining non-faulty data paths; and

said method steps being performed in three phases wherein a single bit message is transmitted in a fault-free environment using not more than six communication bits and in a faulty environment of a single faulty wire, using not more than thirty-two communication bits.

2. The method of claim 1 wherein the message is initially transmitted as two codewords over said data paths, and wherein the message is determined to be correctly received if said codewords are not altered during transmission.

3. The method of claim 2 wherein each of said codewords has elements corresponding to said data paths and a faulty path is identified by first identifying a non-faulty data path by testing said codewords to determine elements thereof that were not altered during the transmission of said codewords.

4. The method of claim 3 wherein said codewords are selected from codes corresponding to said data paths, said codes being formulated such that the alteration of one of said transmitted codewords due to a fault in a corresponding data path will not be detected while an alteration of one of said codewords due to a fault in a noncorresponding data path will be detected, and wherein a non-faulty data path is identified by determining whether either of said codewords are altered during transmission so as not to remain as part of a corresponding code.

5. The method of claim 4 wherein following identification of a non-faulty data path, remaining data paths are tested by transmitting a random codeword from a code corresponding to the non-faulty data path.

6. The method of claim 5 wherein following identification of a non-faulty data path, the message is transmitted in a first coded form if no remaining faulty data paths are found and a second coded form if a remaining faulty data path is found.

7. The method of claim 6 wherein the message is transmitted in said first coded form by transmitting the result of an Exclusive-OR comparison of a value corresponding to said random codeword and the message, and deriving the message as the result of an Exclusive-0R comparison of said transmitted result and said random codeword value.

8. The method of claim 6 wherein the message is transmitted in said second coded form by selecting a pair of random values such that the result of an Exclusive-0R comparison of said values is the message, transmitting said values over the remaining non-faulty data paths and deriving the message as the result of an Exclusive-OR comparison of said random values.

9. The method of claim 6 wherein the message is transmitted in said first and second coded forms using the results of logical operations.

10. In a digital processing network, a method for the private and secure communication of a message between first and second non-faulty, non-adjacent network nodes connected by at least three vertex-disjoint data paths, comprising:

transmitting over three data paths a first three digit codeword corresponding to a message to be communicated, said first codeword utilizing a first one of said data paths as a first flipper wire;

transmitting over said three data paths a second three digit codeword corresponding to the message, said second codeword utilizing a second one of said data paths as a second flipper wire;

receiving said first and second codewords and interpreting one of said codewords as the message if said first and second received codewords are equal, and if not equal, testing said first and second received codewords to identify a non-faulty data path;

if a non-faulty data path is identified, transmitting over said data path a random three digit codeword utilizing said identified non-faulty path as a flipper wire;

receiving said random codeword and testing said received random codeword to identify a faulty data path other than said nonfaulty data path;

if no faulty data path is identified, transmitting a first result of an Exclusive-OR comparison of a value corresponding to said random codeword and the message, and if a faulty data path is idendified, transmitting two random digits over the remaining non-faulty data paths, said random digits being selected such that the result of an Exclusive-OR comparison therebetween is equal to the message;

if no faulty data path is identified, receiving said first Exclusive-OR comparison result and determining the message as a second result of an Exclusive-OR comparison of said first result and said random codeword value, and if a faulty data path is identified, receiving said two random digits and determining the message as the result of an Exclusive-OR comparison of said random digits.

11. The method of claim 10 wherein the digits of said codewords correspond to said data paths and said non-faulty path is identified by comparing said codewords to determine common digits thereof that were not altered during the transmission of said codewords.

12. The method of claim 11 wherein said codewords are selected from codes corresponding to said data paths, said codes being formulated such that the alteration of a digit of said transmitted codewords due to a fault in a flipper wire data path will not be detected while an alteration of a digit of said codewords due to a fault in a non-flipper wire data path will be detected, and wherein a non-faulty data path is identified by determining whether either of said codewords are altered during transmission so as not to remain as part of a corresponding code.

13. The method of claim 12 wherein each said code has four possible codewords defining two possible values.

14. The method of claim 13 wherein said values are the inverse of each other.

15. A system operable in conjunction with a digital processing aparatus to provide secure and private communication between non-faulty, non-adjacent nodes connected by at least three vertex-disjoint data paths, said system comprising:

a data storage medium operable in conjunction with a data storage system of said digital processing apparatus;

said data storage medium having resident thereon security procedure means executable on said digital processing apparatus for;

transmitting over three data paths a first three digit codeword corresponding to a message to be communicated, said first codeword utilizing a first one of said data paths as a first flipper wire;

transmitting over said three data paths a second three digit codeword corresponding to the message, said second codeword utilizing a second one of said data paths as a second flipper wire;

receiving said first and second codewords and interpreting one of said codewords as the message if said first and second received codewords are equal, and if not equal, testing said first and second received codewords to identify a non-faulty data path;

if a non-faulty data path is identified, transmitting over said three data paths a random three digit codeword utilizing said identified non-faulty path as a flipper wire;

receiving said random codeword and testing said received random codeword to identify a faulty data path other than said nonfaulty data path;

if no faulty data path is identified, transmitting a first result of an Exclusive-OR comparison of a value corresponding to said random codeword and the message, and if a faulty data path is idendified, transmitting two random digits over the remaining non-faulty data paths, said random digits being selected such that the result of an Exclusive-OR comparison therebetween is equal to the message;

if no faulty data path is identified, receiving said first Exclusive-OR comparison result and determining the message as a second result of an Exclusive-OR comparison of said first result and said random codeword value, and if a faulty data path is identified, receiving said two random digits and determining the message as the result of an Exclusive-OR comparison of said random digits.

16. The system of claim 15 wherein the digits of said codewords correspond to said data paths and said non-faulty path is identified by comparing said codewords to determine common digits thereof that were not altered during the transmission of said codewords.

17. The system of claim 16 wherein said codewords are selected from codes corresponding to said data paths, said codes being formulated such that the alteration of a digit of said transmitted codewords due to a fault in a flipper wire data path will not be detected while an alteration of a digit of said codewords due to a fault in a non-flipper wire data path will be detected, and wherein a non-faulty data path is identified by determining whether either of said codewords are altered during transmission so as not to remain as part of a corresponding code.

18. The system of claim 17 wherein each said code has four possible codewords defining two possible values.

19. The system of claim 18 wherein said values are the converse of each other.

20. A digital data processing apparatus for providing secure and private communication between first and second non-fault, non-adjacent nodes coupled by at least three vertex-disjoint data paths, the digital data processing apparatus comprising:

a data storage medium operating in conjunction with a data storage system of the digital data processing apparatus;

security means for effecting the secure and private communication of a message w, said security means including;

a) means for sending first and second codewords from the first node across the data paths to the second node, the first and second codewords each corresponding to the message w in respective first and second codes;

b) means for receiving the first and second codewords from the data paths and for determining values of the first and second codewords and validity of the first and second codewords within the first and second codes, respectively;

c) means for determining from the values and validity of the first and second codewords whether the first and second codewords were sent over the data paths without error, and for determining, if an error occurred in transmission of the first and second codewords, a data path which is without error;

d) means for determining the message w from said first or second codewords upon determination that said first and second codewords were sent over the data paths without error;

e) means for transmitting a message identifying the data path determined to be without error upon determination that an error occurred in transmission of the first and second codewords;

f) means for sending a third codeword from the first node across the data paths to the second node following transmission of the message, the third codeword corresponding to a random value p in a respective third code;

g) means for receiving the third codeword from the data paths and determining validity of the third codeword within the third code;

h) means for determining from the validity of the third codeword whether the codeword was sent over the data paths without error;

i) means for determining the value p of the third codeword upon determination that the third codeword was sent over the data paths without error;

j) means for transmitting a third codeword vector corresponding to the received third codeword upon determination that the third codeword was sent over the data paths in error;

k) means for encoding the message w using the value p to generate a first encoding and transmitting the first encoding upon determination that the third codeword was sent over the data paths without error;

l) means for comparing the third codeword with the third codeword vector to determine a faulty data path and transmitting a second random encoding of the message w over the remaining data paths which are good; and

m) means for receiving either of the first and second encodings and for decoding the message w therefrom.