|Publication number||US5351301 A|
|Application number||US 06/129,047|
|Publication date||Sep 27, 1994|
|Filing date||Mar 3, 1980|
|Priority date||Mar 3, 1980|
|Publication number||06129047, 129047, US 5351301 A, US 5351301A, US-A-5351301, US5351301 A, US5351301A|
|Inventors||Ronald M. Benincasa|
|Original Assignee||The United States Of America As Represented By The Director Of National Security Agency|
|Export Citation||BiBTeX, EndNote, RefMan|
|Patent Citations (11), Referenced by (3), Classifications (14)|
|External Links: USPTO, USPTO Assignment, Espacenet|
1. Field of the Invention
This invention relates to the field of digital communications, and more specifically to authentication of binary coded communications.
2. Description of the Prior Art
Vast quantities of information are routinely transmitted from one place to another by means which allow a message to be intercepted by unauthorized persons. In many cases serious harm could result if such persons were able to transmit their own improper messages in place of an authorized one, or to transmit previously intercepted proper messages at an improper time. Examples of communication systems where harm could occur from such unauthorized transmissions include funds transfer and accounting messages between financial institutions and command and control information for satellites. There is a need for means which allow the receiver of a message to be assured that the message has been correctly received and that it was transmitted from an authorized source.
A method well known in the prior art for insuring that a message has been received without errors is by use of cyclic error correcting codes generated by feedback registers. A substantial amount of literature is available on such codes; for example, see W. Wesley Peterson, Error-Correcting Codes, MIT, 1961. A particular type of cyclic code generator described therein is known as a Galois register. FIG. 1 illustrates such an apparatus with an 8-stage binary shift register S divided by a first mod-2 adder 10 between the third and fourth stages S3 and S4 respectively, and a mod-2 adder 11 between the fifth and sixth stages. A third mod-2 adder 12 sums the contents of S8 and an external input I1, with the sum provided as an input to S1. Following an initial preset step where the stages are loaded with some sequence of binary digits, the contents of each stage of the register at a given time t is a known function of the register contents at time t-1, one clock pulse earlier and the external input I1 t. Specifically with reference to FIG. 1, the contents of stage 6 at time t is equal to the contents of stage 8 at time t-1 plus the contents of stage 5 at t-1, or
S6 t =S8 t-l ⊕S5 t-1
where ⊕ indicates mod-2 addition.
S8 t =S7 t-1
S7 t =S6 t-1
S5 t =S4 t-1
S4 t =S8 t-1 ⊕S3 t-1
S3 t =S2 t-1
S2 t =S1 t-1
S1 t =S8 t-1 ⊕Il t.
FIG. 2 illustrates a similar apparatus with an 8-stage register T broken by a first mod-2 adder 20 between stages T2 and T3, a second mod-2 adder 21 between stages T6 and T7, and a third mod-2 adder 22 providing the sum of T8 and to T1. This register steps according to the rules
T8 t =T7 t-1
T7 t =T8 t-1 ⊕T6 t-1
T6 t =T5 t-1
T5 t =T4 t-1
T4 t =T3 t-1
T3 t =T8 t-1 ⊕T2 t-1
T2 t =T1 t-1
T1 t =T8 t-1 ⊕I2 t.
The manner in which Galois registers are used for error detecting is well known, and will not be discussed here. Details are available in the above-identified reference by Peterson.
It is desirable to communicate information freely both with assurance that a message received is in fact an authorized message from an authorized source, and that the message has been received without error.
Accordingly it is an object of this invention to provide an apparatus for authenticating transmitted messages.
It is a further object to provide a communication means which insures that a message has been received without error.
It is also an object to provide message authentication by testing agreement between a transmitted and a separately generated authentication word.
A further object is to generate the authentication word in a manner which is not readily discoverable by one having access only to the message and the authentication word.
It is a still further object to provide an authentication means in which a choice of stepping rules is controlled by a pseudorandom key stream.
An apparatus having the above advantages and others would include a plurality of delay stages connected to form a shift register; a first mod-2 adder inserted between two consecutive stages of the register, the output of the preceeding stage forming one input of the adder and the output of the adder forming the input to the succeeding stage; first and second terminals for providing information to the apparatus; a second mod-2 adder having an input from the first terminal, an input from the last stage of the register, and an output connected to the first stage of the register; means controlled by data provided on the second terminal for selectively switching either the information in the last delay stage or a zero to the second input of the first adder; and an output terminal connected to a selected one of the register stages.
My invention may be best understood by reading the specification with reference to the attached drawings, which:
FIG. 1 is a logic block diagram of a simple Galois register typical of the type known in the prior art;
FIG. 2 is a logic diagram of a second example of a Galois register;
FIG. 3 is a logic diagram of a modified Galois register incorporating certain elements of my invention;
FIG. 4 is a block diagram of a transmitter attachment incorporating the elements of my invention, and
FIG. 5 is a block diagram of a receiver attachment incorporating the elements of my invention.
An authenticator circuit 30 is illustrated in FIG. 3. A Galois register W includes a plurality of delay stages W1, W2, W8. Selected stages of register W are connected directly to the preceeding stage such that a clock pulse will shift the contents of a stage directly into the next; specifically, the contents of W1 will shift into W2, W4 into W5, and W7 into W8. Other stages are separated by a mod-2 adder, or "Exclusive OR", with adder 31 connecting W2 to W3, adder 32 connecting W3 to W4, adder 35 connecting W5 to W6 and adder 36 connecting W6 to W7. An adder 37 connects a terminal 53 to W1. The output of W8 is connected to each of the adders through binary AND gates; AND gate 40 connects W8 to adder 31, AND gate 42 connects W8 to adder 32, AND gate 43 connects W8 to adder 35, and AND gate 46 connects W8 to adder 36. W8 is also connected directly to an input of adder 37. An input key terminal 47 is connected through an inverter 51 to AND gate 40 and through an inverter 52 to AND gate 46. In addition, key terminal 47 is connected directly to AND gates 42 and 43. An authenticator output terminal 50 is connected to the output of one of the register stages, which in this embodiment is selected to be W3.
Assume that the key terminal 47 is held to a constant binary "0". Because one of the inputs to AND gates 42 and 43 is held to "0", the output of AND gates 42 and 43 will be "0" regardless of the contents of W8. The resulting effect is that W3 will shift directly into W4, and W5 will shift directly into W6 as if adders 32 and 35 were not present. The same "0" applied to terminal 47 will appear at AND gates 40 and 46 as a constant "1" because of inverters 51 and 52. The outputs of AND gates 40 and 46 will then take the value of W8, W3 will be the sum of W8 and W2, and W7 will be the sum of W8 and W6. It is apparent that when the input on key terminal 47 is "0", register W steps according to the rules set forth above with respect to FIG. 2.
Assume now that the input to key terminal 47 is held to a constant "1". Inverters 51 and 52 cause one input of AND gates 40 and 46 to appear as a continuous "0", which necessarily means that the output of AND gates 40 and 46 are also a continuous "0" regardless of the content of W8. W2 then shifts directly into W3 and W6 shifts directly into W7 as if adders 31 and 36 were not present. Because a constant "1" is presented to AND gates 42 and 43, their outputs assume the value of the second input, W8. W6 is then the sum of W8 and W5, and W4 is the sum of W8 and W3. It is apparent that when the input to key terminal 47 is "1", register W steps according to the rules set forth above with respect to FIG. 1.
The key terminal 47 may be connected to a pseudorandom pattern source to cause authenticator 30 to "randomly" switch back and forth between the mode of FIG. 1 and that of FIG. 2. For the purpose of this description, the term "pseudorandom pattern" is defined to mean a reproducable binary data stream which is generated according to a known rule, but which appears to be random to one who is unaware of the method of generation. The source for the pseudorandom pattern may be, for example, a maximum length linear sequence generator of the Galois register type. The pattern which emerges at terminal 50 is thus dependent on the initial fill of register W, the number of clock pulses which have occurred since the initial fill, the data pattern provided at input terminal 53 and the pseudorandom pattern provided at key terminal 47. A practical use to which the authenticator of FIG. 3 may be put is described below with reference to FIGS. 4 and 5.
FIG. 4 illustrates an apparatus capable of providing message authentication for a transmitted message. A communications path 63 includes a message input terminal 60 connected through contact 62 of a two-position switch 65 to an output terminal 66. Input 69 of an authenticator circuit 70 is also connected to the communications path 63. A pseudorandum pattern generator 71 connects to authenticator 70 through terminal 72. Authenticator output 75 is connected to contact 61 of switch 65. Authenticator 70 may be of the type shown in FIG. 3 with input 69 corresponding to input 53, input 72 corresponding to input 47, and output 75 corresponding to output 50.
Operation of authenticator 70 is in three phases: initialization, message transmission, and authenticator transmission. During initialization, register W is loaded with a predetermined initial fill pattern. No specific means for this is shown because means of initializing shift register stages are well known. A message transmission phase follows with the message to be transmitted provided at terminal 60 while switch 65 is turned to contact 62. The message, which is a binary data sequence, is provided directly to terminal 66 which is connected to a conventional transmitter apparatus such as a radio or microwave transmitter. The transmitted message is simultaneously provided to authenticator 70 through terminal 69. A key generator or similar pseudorandom pattern source 71 is simultaneously started, feeding input terminal 72. Throughout the message transmission phase, authenticator 70 is stepping sequentially and the W register stages are changing. The data on output terminal 75 is not utilized because of the open circuit at contact 61. Following the transmission of the final bit of message, switch 65 is turned to contact 61 and authenticator 70 and key generator 71 are stepped some additional number of times. This authentication phase provides output data from terminal 75 to terminal 66 for transmission to the receiver. Upon completion of the authentication phase, the transmission ends.
FIG. 5 illustrates the receiver portion of an apparatus capable of authenticating a message transmitted by the apparatus described in connection with the circuit of FIG. 4 above. A communications path 83 includes a data input terminal 80 connected to an output terminal 81. Input terminal 82 of an authenticator 85 and one input of a 2 input mod-2 adder 86 are also connected to the communications path 83. A key generator or similar pseudorandom pattern generator 87 connects to terminal 90 of authenticator 85. Output terminal 91 connects to the second input of adder 86. Common communication requires that pattern generator 87 be identical to generator 71 of FIG. 4, and that authenticator 85 be identical to authenticator 70. The output of adder 86 is connected through an inverter 95 to the "count" input of a binary counter 92 and directly to the reset input of counter 92.
Prior to reception of data from the apparatus of FIG. 4, pattern generator 87 must be operating synchronously with generator 71, and the register stages of authenticator 85 must be preset the same as the stages of authenticator 70. The message bit stream on terminal 66 of FIG. 4 reaches terminal 80 and is passed directly to output 81 which is preferably connected to some type of storage device where the message may be retained until authenticity has been established. Because the sequences at authenticator inputs 82 and 72 are identical to those at inputs 69 and 90 (FIG. 4) the sequence at output 91 will be identical to that at output 75. A "1" will appear on the output of adder 86 when data bits at terminals 80 and 91 are dissimilar, causing a "1" at the reset input of counter 92 which resets the counter to zero. When the data bits at terminals 80 and 91 are the same, the output of adder 86 will be a "0", which causes a "1" to appear at the count (CNT) input of counter 92 because of inverter 95. The value of the counter 92 at any time will thus be equal to the number of consecutive agreements of the bits at terminals 80 and 91. During that time which corresponds to the message transmission phase described above, there is no direct correlation between these two streams so the output of adder 86 is essentially random and the value in the counter 92 remains quite low. Following the message transmission phase, the authenticator transmission received at terminal 80 will be identical to that generated by authenticator 85 and there will be exact correlation of the two inputs to adder 86. Counter 92 will thus increment continuously, without resetting, to a number greater than or equal to the number of bits in the authenticator transmission sequence. The message is determined to be authentic by noting the value in counter 92 following the final phase. This value must be at least as great as the number of bits in the authenticator transmission sequence. If not, either an error was generated during the course of transmission or an improper authenticator sequence was present. Either event cautions the use of the received message to obtain further authentication prior to utilizing the message.
I have thus described an authenticator circuit in a system in which the circuit may be utilized to insure that a message has been received without error and from an authorized source. Numerous modifications are possible, including varying the length and shifting rules of the feedback register and utilizing more than one interconnected register within the authenticator circuit. In addition, further security might be obtained by separately encoding the message either prior to or after utilization of the authenticator. I do not intend that my invention be limited to the precise embodiment illustrated above, but rather to that which is claimed hereinbelow.
|Cited Patent||Filing date||Publication date||Applicant||Title|
|US3662337 *||Oct 1, 1970||May 9, 1972||Nasa||Mod 2 sequential function generator for multibit binary sequence|
|US3700806 *||Sep 18, 1967||Oct 24, 1972||Csf||Key generators for cryptographic devices|
|US3749832 *||Apr 13, 1964||Jul 31, 1973||Co Intern Pour L Inf||Binary coded signal and ciphering and deciphering method and systems embodying same|
|US3751648 *||Dec 1, 1971||Aug 7, 1973||Communications Satellite Corp||Generalized shift register pulse sequence generator|
|US3885139 *||Jul 27, 1973||May 20, 1975||California Inst Of Techn||Wideband digital pseudo-gaussian noise generator|
|US3895349 *||Apr 29, 1974||Jul 15, 1975||Marconi Co Ltd||Pseudo-random binary sequence error counters|
|US3911216 *||Dec 17, 1973||Oct 7, 1975||Honeywell Inf Systems||Nonlinear code generator and decoder for transmitting data securely|
|US3988538 *||Feb 26, 1975||Oct 26, 1976||International Standard Electric Corporation||Digital data scrambler and descrambler|
|US4009374 *||May 17, 1976||Feb 22, 1977||Rockwell International Corporation||Pseudo-random bidirectional counter|
|US4023026 *||Dec 15, 1975||May 10, 1977||International Telephone And Telegraph Corporation||Pseudo-random coder with improved near range rejection|
|US4165444 *||Nov 29, 1977||Aug 21, 1979||National Research Development Corporation||Apparatus for electronic encypherment of digital data|
|Citing Patent||Filing date||Publication date||Applicant||Title|
|US6167516 *||Apr 10, 1997||Dec 26, 2000||Inria Institut National De Recherche En Informatique Et En Automatique Cogenit||Data file authentication device|
|US8036380||Dec 14, 2006||Oct 11, 2011||Telefonaktiebolaget L M Ericsson (Publ)||Efficient data integrity protection|
|US20080144819 *||Dec 14, 2006||Jun 19, 2008||Telefonaktiebolaget L M Ericsson (Publ)||Efficient Data Integrity Protection|
|U.S. Classification||713/168, 708/250, 331/78, 713/170|
|International Classification||G06F7/58, H04L9/22|
|Cooperative Classification||H04L9/0662, G06F2207/581, G06F2207/583, G06F7/584, H04L9/32, H04L2209/12|
|European Classification||H04L9/22, G06F7/58P1|