Scalable key agile cryptography

• US 5,796,836 A
• Filed: 08/29/1995
• Issued: 08/18/1998
• Est. Priority Date: 04/17/1995
• Status: Expired due to Term

• Current Assignee: McAfee, LLC
• Original Assignee: Secure Computing Corporation (McAfee, LLC)
• Inventors: Markham, Thomas R.
• Primary Examiner(s): Tarcza, Thomas H.
• Assistant Examiner(s): Laufer, Pinchus M.
• Application Number:
  US08/521,056
• Time in Patent Office: 1,085 Days
• Field of Search: 380/37, 380/42, 380/43, 380/46, 380/50, 380/28, 364/717
• US Class Current: 380/28
• CPC Class Codes: H04L 2012/5673 Coding or scrambling
• CPC Class Codes: H04L 2012/5687 Security aspects
• CPC Class Codes: H04L 2209/125 Parallelization or pipelining, e.g. for accelerating processing of cryptographic operations
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 9/0637 Modes of operation, e.g. cipher block chaining [CBC], electronic codebook [ECB] or Galois/counter mode [GCM]
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections
• CPC Class Codes: Y04S 40/20 Information technology specific aspects, e.g. CAD, simulation, modelling, system security

Abstract

A system and method for encrypting blocks of plain text. Output FIFO memories are provided for decoupling pseudorandom vector generation from plain text encryption. The output FIFOs produce the effect of multiplexing several cryptographic devices together and can be combined with feedback FIFO memories in order to provide key agility and parallel secret key encryption. Throughput is also enhanced by constructing wide codebooks so that a block of data can be enciphered as a whole.

Claims

1. A method of encrypting a plurality M of plain text blocks, the method comprising the steps of:

providing a plurality N of memory locations, where M>

N and N>

1;

storing precomputed pseudorandom vectors in each of the plurality of memory locations; and

encrypting the ith plain text block, wherein M>

i>

N and wherein the step of encrypting the ith plain text block comprises the steps;

a) performing a first function CT(i)=f(PT(i),PV(i-N)), where CT(i) is the ith cipher text block, PT(i) is the plain text block for iteration i, PV(i-N) is the pseudorandom vector calculated during iteration i-N and the first function, f( ), is a first encryption algorithm;

b) calculating a new pseudorandom vector, wherein the step of calculating a new pseudorandom vector comprises the step of performing a second function PV(i)=g(PV(i-N))!g( ) on PV(i-N) to calculate PV(i), where PV(i) is the pseudorandom vector calculated during iteration i, PV(i-N) is the pseudorandom vector calculated during iteration i-N and the second function, g( ), is a second encryption algorithm; and

c) storing the new pseudorandom vector in one of the N memory locations.

2. The method according to claim 1 wherein the function f( ) is modulo-two addition.

3. The method according to claim 2 wherein the function g( ) is secret key encryption of the pseudorandom vector PV(i-N).

4. The method according to claim 2 wherein the function g( ) is secret key encryption of the cipher text block CT(i).

5. The method according to claim 1 wherein the function g() is secret key encryption of the modulo-two addition of pseudorandom vector PV(i-N) and plain text block PT(i).

6. A method of encrypting a plain text block to form a cipher text block, the method comprising the steps of:

providing an encryption circuit having an output FIFO of depth N, where N>

1;

storing N precomputed pseudorandom vectors in the output FIFO;

performing a function CT=f(PT,PV), where CT is the cipher text block, PT is the plain text block encrypted, PV is the pseudorandom vector which was least recently stored in the output FIFO and f( ) is the encryption function;

computing a new pseudorandom vector, wherein the step of computing a new pseudorandom vector comprises the step of performing a function g( ) on PV; and

storing the new pseudorandom vector in the output FIFO.

7. The method according to claim 6 wherein the function f( ) is modulo-two addition.

8. The method according to claim 7 wherein the function g( ) is secret key encryption of the pseudorandom vector PV.

9. The method according to claim 7 wherein the function g( ) is secret key encryption of the cipher text block CT.

10. The method according to claim 6 wherein the function g( ) is secret key encryption of the modulo-two addition of pseudorandom vector PV and plain text block PT.

11. The method according to claim 6 wherein the step of providing an encryption circuit having an output FIFO comprises the steps of:

determining a latency of encryption of the encryption circuit;

determining a desired throughput; and

calculating N as a function of the latency of encryption and the desired throughput.

12. The method according to claim 11 wherein the latency of encryption is N clock cycles and the desired throughput is one plain text block per clock cycle.

13. An encryption device, comprising:

a codebook module having an input, wherein the codebook module applies a secret key algorithm to data received at the input in order to produce pseudorandom vectors;

an output FIFO module connected to the codebook module, wherein the output FIFO module comprises a first output FIFO memory having a depth N, where N>

1, wherein the first output FIFO memory stores pseudorandom vectors received from the codebook module and transmits the pseudorandom vectors received on a first in, first out basis; and

an encryption module connected to the output FIFO module, wherein the encryption module includes encryption means for encrypting plain text as a function of the pseudorandom vectors stored in the output FIFO module in order to form cipher text, wherein the encryption module further includes transmission means for transmitting data to the codebook module to be used in generating pseudorandom vectors.

14. The device according to claim 13, wherein the transmission means transmits back to the codebook module the pseudorandom vectors received from the codebook module.

15. The device according to claim 13, wherein the transmission means transmits the cipher text back to the codebook module.

16. The device according to claim 13, wherein the encryption module further comprises a feedback FIFO module connected to the codebook module, wherein the feedback FIFO module comprises a first feedback FIFO memory.

17. The device according to claim 16, wherein the encryption module further comprises a second feedback FIFO memory and a first multiplexer connected to said first and second feedback FIFO memories, wherein the output FIFO module further comprises a second output FIFO memory and a second multiplexer connected to said first and second output FIFO memories, wherein each of said FIFO memories has a depth N and wherein the first and second multiplexers operate under the control of a keystream indicator to selectively transmit data from the first and second feedback and output FIFOs.

18. The device according to claim 17, wherein the codebook module comprises a first codebook, wherein the first codebook applies a secret key cryptographic algorithm.

19. The device according to claim 13, wherein the codebook module comprises a first codebook, wherein the first codebook applies a secret key cryptographic algorithm.

20. An encryption device, comprising:

a codebook module, wherein the codebook module comprises a codebook input and a first codebook, the first codebook comprising;

a plurality of encryption algorithm devices, wherein each encryption algorithm device applies a secret key cryptographic algorithm;

a codebook input module connected to the codebook input and to the plurality of encryption algorithm devices, wherein the codebook input module distributes data received at the codebook input to the plurality of encryption algorithm devices according to a dispersion algorithm;

a combiner module connected to the plurality of encryption algorithm devices, wherein the output combiner combines data received from the plurality of encryption algorithm devices to form pseudorandom vectors, wherein the combiner module includes means for forming at least one bit of the keystream as a function of data received from two or more of the plurality of encryption algorithm devices;

an output memory module connected to the codebook module, wherein the output memory module comprises a first output FIFO memory of depth N, where N is an integer number greater than one, wherein the first output FIFO memory stores pseudorandom vectors received from the codebook module and transmits the pseudorandom vectors received on a first in, first out basis; and

encryption means, connected to the output memory module, for combining the pseudorandom vectors stored in the output FIFO module with plain text to form cipher text, wherein the encryption means includes transmission means for generating data to be fed back into the codebook module.

21. The encryption device according to claim 20 wherein the dispersion algorithm is selected such that a change of a single bit in the data received at the codebook input module will cause each bit of the pseudorandom vector calculated from that data to change with a probability of approximately 0.5.

22. The device according to claim 20, wherein the transmission means transmits back to the codebook module the pseudorandom vectors received from the codebook module.

23. The device according to claim 20, wherein the transmission means transmits the cipher text back to the codebook module.

24. The device according to claim 20, wherein the encryption module further comprises a feedback FIFO module connected to the encryption module, wherein the feedback FIFO module comprises a first feedback FIFO memory having a depth greater than one.

25. The device according to claim 24, wherein the codebook module further includes a second feedback FIFO memory and a first multiplexer connected to said first and second feedback FIFO memories, wherein the output FIFO module further comprises a second output FIFO memory and a second multiplexer connected to said first and second output FIFO memories, wherein each of the FIFO memories has a depth greater than one and wherein the first and second multiplexers operate under the control of a keystream indicator to selectively transmit data from the first and second feedback and output FIFO memories.

26. The encryption device according to claim 20 wherein the codebook module further comprises a second codebook connected in parallel to the first codebook to increase throughput through the codebook module.

27. A method of encrypting a packet having a header and an M byte payload, the method comprising the steps of:

providing an encryption circuit including a memory connected to a codebook module, wherein the codebook module includes a plurality of encryption algorithm devices;

storing a first M byte pseudorandom vector in the memory;

encrypting the M byte payload with the first M byte wide pseudorandom vector read from the memory;

generating an M byte keystream; and

generating a second M byte wide pseudorandom vector, wherein the step of generating the second M byte wide pseudorandom vector comprises the steps of;

a) distributing the M byte keystream across the plurality of encryption algorithm devices according to a dispersion algorithm;

b) encrypting the distributed keystream with a secret key encryption algorithm;

c) recombining the encrypted distributed keystream as a function of the dispersion algorithm to form the second M byte wide pseudorandom vector, wherein the step of recombining includes the step of forming at least one bit of the keystream as a function of data received from two or more of the plurality of encryption algorithm devices; and

d) storing the second M byte wide pseudorandom vector in the memory.

28. The method according to claim 27, wherein the step of storing the first M byte wide pseudorandom vector comprises the steps of:

providing an M byte initialization vector;

distributing the M byte initialization vector across the plurality of encryption algorithm devices according to the dispersion algorithm;

encrypting the distributed M byte initialization vector with a secret key encryption algorithm; and

recombining the encrypted distributed keystream as a function of the dispersion algorithm to form the first M byte wide pseudorandom vector, wherein the step of recombining includes the step of forming at least one bit of the keystream as a function of data received from two or more of the plurality of encryption algorithm devices.

29. A method of encrypting a plurality of packets, including a first and a second packet, wherein each of the plurality of packets include a header and an M byte payload, the method comprising the steps of:

providing an encryption circuit including a memory connected to a codebook module, wherein the codebook module includes a plurality of encryption algorithm devices;

providing a plurality of M byte pseudorandom vectors, including a first and a second M byte pseudorandom vector;

storing the plurality of M byte pseudorandom vectors in the memory;

retrieving in successive order the plurality of M byte pseudorandom vectors;

encrypting in the same successive order the M byte payloads of the plurality of packets;

generating a plurality of M byte keystream; and

generating a plurality of new M byte wide pseudorandom vectors, wherein the step of generating the plurality of new M byte wide pseudorandom vector comprises the steps of;

a) distributing the plurality of M byte keystream across the plurality of encryption algorithm devices according to a dispersion algorithm;

b) encrypting the distributed M byte keystream with a secret key encryption algorithm;

c) recombining the encrypted distributed M byte keystream as a function of the dispersion algorithm to form the plurality of new M byte wide pseudorandom vectors, wherein the step of recombining includes the step of forming at least one bit of the pseudorandom vectors as a function of data received from two or more of the plurality of encryption algorithm devices; and

d) storing the new M byte wide pseudorandom vectors in the memory.

30. The method according to claim 29, wherein the step of providing a memory includes the step of providing a first and a second output FIFO memory, wherein each output FIFO memory has a depth greater than one and wherein the step of storing the new M byte wide pseudorandom vectors in the memory includes the step of determining whether the new M byte wide pseudorandom vectors should be placed in said first or said second output FIFO memory.

31. An encryption device, comprising:

a ciphertext memory module for storing ciphertext;

a codebook module, connected to the ciphertext memory module, wherein the codebook module comprises a first codebook, the first codebook comprising;

a plurality of encryption algorithm devices;

an input module connected to the ciphertext memory module and to the plurality of encryption algorithm devices, wherein the input module distributes the ciphertext received from the ciphertext memory module according to a dispersion algorithm;

output means, connected to the plurality of encryption algorithm devices, for forming keystream by combining data received from the plurality of encryption algorithm devices according to the dispersion algorithm, wherein the output means includes means for forming at least one bit of the keystream as a function of data received from two or more of the plurality of encryption algorithm devices;

a keystream memory module, connected to the output means, for storing keystream generated from the ciphertext; and

encryption means, connected to the keystream memory module, for combining the keystream with plaintext to form ciphertext and for feeding the ciphertext back into the ciphertext memory module.

32. The encryption device according to claim 31 wherein the dispersion algorithm is such that a change of a single bit in the ciphertext received at the input module will cause each bit of the keystream calculated from the ciphertext to change with a probability of approximately 0.5.

33. The encryption device according to claim 31 wherein the ciphertext memory module comprises a first ciphertext FIFO memory used to store first ciphertext, wherein the first ciphertext FIFO memory has a depth sufficient to store at least two packets of ciphertext;

and

wherein the keystream memory module comprises a first keystream FIFO memory, connected to the output means, for storing first keystream generated from the first ciphertext, wherein the first keystream FIFO memory has a depth sufficient to store at least two packets of keystream.

34. The encryption device according to claim 33 wherein the ciphertext memory module further comprises:

a second ciphertext FIFO memory used to store second ciphertext, wherein the second ciphertext FIFO memory has a depth sufficient to store at least two packets of ciphertext; and

a multiplexer, connected to the first and second ciphertext FIFO memories and to the input module, for selectively applying ciphertext from the first and second ciphertext FIFO memories to the input means to achieve a desired keystream.

35. The encryption device according to claim 34 wherein the keystream memory module further comprises:

a second keystream FIFO memory used to store second keystream, wherein the second keystream FIFO memory has a depth sufficient to store at least two packets of keystream; and

a multiplexer, connected to the first and second keystream FIFO memories and to the encryption means, for selectively encrypting plaintext with keystream read from the first and second keystream FIFO memories.

36. A method of encrypting packets having a header and an N byte payload, the method comprising the steps of:

providing a ciphertext memory module for storing ciphertext;

providing a codebook module, connected to the ciphertext memory module, wherein the codebook module comprises a first codebook, the first codebook comprising;

a plurality of encryption algorithm devices;

an input module connected to the ciphertext memory module and to the plurality of encryption algorithm devices, wherein the input module distributes the ciphertext received from the ciphertext memory module according to a dispersion algorithm;

output means, connected to the plurality of encryption algorithm devices, for forming keystream by combining data received from the plurality of encryption algorithm devices according to the dispersion algorithm, wherein the output means includes means for forming at least one bit of the keystream as a function of data received from two or more of the plurality of encryption algorithm devices;

providing a keystream memory module, connected to the output means, for storing keystream generated from the ciphertext;

generating a first N byte wide keystream word;

encrypting the N byte payload with the first N byte wide keystream word;

storing the encrypted N byte payload in the ciphertext memory module; and

generating a second N byte wide keystream word, wherein the step of generating the second N byte wide keystream word comprises the steps of;

distributing the encrypted N byte payload across the plurality of encryption algorithm devices according to a dispersion algorithm;

generating keystream data in the plurality of encryption algorithm devices as a function of the distributed payload; and

recombining the keystream data as a function of the dispersion algorithm to form the second N byte wide keystream; and

storing the second N byte wide keystream in the keystream memory module.

37. The method according to claim 36, wherein the step of generating the first N byte wide keystream comprises the steps of:

providing an initialization vector;

distributing N bytes of the initialization vector across the plurality of encryption algorithm devices according to the dispersion algorithm;

generating initial data in the plurality of encryption algorithm devices as a function of the distributed ciphertext; and

recombining the initial data as a function of the dispersion algorithm to form the first N byte wide keystream.

38. The method according to claim 36, wherein the keystream memory module includes a keystream FIFO, wherein the keystream FIFO has a depth sufficient to store at least two N byte keystream words, and wherein the step of storing the second N byte wide keystream includes the step of:

storing the second N byte wide keystream in said keystream FIFO.

39. The method according to claim 38, wherein the step of providing a keystream memory module includes the steps of:

determining a latency of keystream generation, wherein the latency of keystream generation is a function of the time needed to calculate new keystream; and

sizing the keystream FIFO to hide the latency of keystream generation.

40. The method according to claim 36, wherein the step of storing the encrypted N byte payload includes the steps of:

providing a ciphertext FIFO sufficient to store a plurality of N byte payloads; and

storing the encrypted N byte payload in said ciphertext FIFO.

41. A method of encrypting a plurality of packets, wherein each packet includes a header and an N byte payload, the method comprising the steps of:

a) providing a keystream memory;

b) providing a plurality of encryption algorithm devices;

c) providing a first keystream, wherein the first keystream includes a plurality of N byte keystream words, including a first and a second N byte keystream word;

d) storing the plurality of N byte keystream words in the keystream memory;

e) encrypting the payload of one of the plurality of packets with the first N byte keystream word;

f) generating an N byte keystream word from the encrypted payload, wherein the step of generating comprises the steps of;

distributing the encrypted payload across the plurality of encryption algorithm devices according to a dispersion algorithm;

generating keystream data in the plurality of encryption algorithm devices as a function of the distributed encrypted payload; and

recombining the keystream data as a function of the dispersion algorithm to form the N byte wide keystream word, wherein the step of recombining includes the step of forming at least one bit of the N byte wide keystream word as a function of data received from two or more of the plurality of encryption algorithm devices;

g) storing the recombined N byte keystream word into the keystream memory; and

h) repeating steps e-g for each packet of the plurality of packets.

42. The method according to claim 41, wherein the step of providing a keystream memory includes the step of providing a first and a second keystream FIFO memory, wherein each of said first and second keystream FIFO memories has a depth sufficient to store at least two N byte keystream words, and wherein the step of storing the recombined N byte keystream word includes the step of determining whether the recombined N byte keystream word should be placed in said first or said second keystream FIFO memory.

43. The method according to claim 41, wherein the step of encrypting includes the step of storing the encrypted payload in ciphertext memory.

44. An encryption system, comprising:

a ciphertext memory module for storing a plurality of ciphertext, wherein the ciphertext memory module comprises a first ciphertext FIFO memory used to store first ciphertext from the plurality of ciphertext, wherein the first ciphertext FIFO memory has a depth sufficient to store at least two words of first ciphertext;

an encryption algorithm device, connected to the ciphertext memory module, wherein the encryption algorithm device includes a keystream generator for generating first keystream from the first ciphertext;

a keystream memory module, wherein the keystream memory module comprises a first keystream FIFO memory connected to the encryption algorithm device for storing the first keystream, wherein the first keystream FIFO memory has a depth sufficient to store at least two words of first keystream; and

encryption means, connected to the keystream memory module, for combining the keystream with plaintext to form ciphertext and for feeding the ciphertext back into the ciphertext memory module.

45. The encryption system according to claim 44 wherein the ciphertext memory module further comprises:

a second ciphertext FIFO memory used to store second ciphertext, wherein the second ciphertext FIFO memory has a depth sufficient to store at least two words of second ciphertext; and

a multiplexer, connected to the first and second ciphertext FIFO memories and to the input module, for selectively applying ciphertext from the first and second ciphertext FIFO memories to the input means to achieve a desired keystream.

46. The encryption system according to claim 45 wherein the keystream memory module further comprises:

a second keystream FIFO memory used to store second keystream, wherein the second keystream FIFO memory has a depth sufficient to store at least two words of second keystream; and

a multiplexer, connected to the first and second keystream FIFO memories and to the encryption means, for selectively encrypting plaintext with keystream read from the first and second keystream FIFO memories.