Cryptographic technique that provides fast encryption and decryption and assures integrity of a ciphertext message through use of a message authentication code formed through cipher block chaining of the plaintext message

• US 6,226,742 B1
• Filed: 04/20/1998
• Issued: 05/01/2001
• Est. Priority Date: 04/20/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jakubowski, Mariusz H., Venkatesan, Ramarathnam
• Primary Examiner(s): HAYES, GAIL O
• Assistant Examiner(s): Tucker, Christopher M.
• Application Number:
  US09/062,836
• Time in Patent Office: 1,107 Days
• Field of Search: 713/170, 713/181, 380/28, 380/37, 380/259
• US Class Current: 713/170
• CPC Class Codes: H04L 9/0625 with splitting of the data block into left and right halves, e.g. Feistel based algorithms, DES, FEAL, IDEA or KASUMI
• 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: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC

Abstract

A cryptographic technique that not only provides fast and extremely secure encryption and decryption but also assures integrity of a ciphertext message. This technique involves, during message encryption: generating, in response to an incoming plaintext message, an intermediate stream—such as by chaining the message, wherein a predefined portion of the intermediate stream defines a message authentication code (MAC); inserting an encrypted version of the MAC into a predefined portion of a ciphertext message; and generating, in response to the intermediate stream and the encrypted MAC, a remainder of the ciphertext message such that the remainder exhibits a predefined variation, e.g., a pseudo-random sequence, also contained within the encrypted MAC. Decryption proceeds in essentially a reverse fashion. By extending the sequence across the remainder of the ciphertext, any subsequent change to the ciphertext would likely destroy the continuity of the sequence otherwise residing throughout the remainder of the ciphertext. During decryption, any violation to the integrity of the ciphertext can be readily detected by decrypting the MAC contained in the ciphertext and comparing it, for any discrepancies, against a MAC generated from recovered plaintext.

Claims

1. A method of encrypting a plaintext message, P having n+1 blocks (P_i, where n>

i>

0 and n is an integer), into a ciphertext message such that, in response to contents of the ciphertext message itself, a subsequent violation to integrity of the ciphertext message can be detected, the method comprising the steps of;

(a) generating, in response to the plaintext message, an intermediate stream Y, having n+1 blocks (Y_i) with a predefined portion of the intermediate stream defining a message authentication code (MAC) through the steps of;

(a1) transforming the plaintext message, through a first predefined cipher block chaining (CBC) operation and using a key formed in response to predefined non-zero integer values a, b, c and d, into the intermediate stream; and

(a2) forming the MAC as a predefined portion of the intermediate stream;

(a3) wherein the CBC is implemented according to the following so as to yield Y_i;

(i) for i=0, as a first function, F, of P₀ as input;

(ii) for even i within n, as the function, F, of Y<sub>i−

1</sub> and P_i as input; and

(iii) for odd i within n, as a second function, G, of Y<sub>i−

1</sub> and P_i as input;

where;

P₀ and P_i represent blocks zero and i within the plaintext message (P), respectively, and the functions F and G comprise terms of the form ax+b and cx+d, respectively, with x representing the input to either of the functions;

(b) inserting an encrypted version of the MAC into a predefined portion of the ciphertext message; and

(c) generating, in response to the intermediate stream and the encrypted MAC, a remainder of the ciphertext message such that the remainder exhibits a predefined variation contained within the encrypted MAC.

2. The method of claim 1 further comprising the steps of:

encrypting the predefined portion of the intermediate stream, through a predetermined pseudo-random permutation, into the encrypted MAC;

inserting the encrypted MAC into the predefined portion of the ciphertext message; and

constructing the remainder of the ciphertext message through a second predefined cipher block chaining operation and in response to both the remainder of the intermediate stream and the encrypted MAC such that a pseudo-random sequence in the encrypted MAC, the sequence being said predefined variation, extends throughout the remainder of the ciphertext message.

3. The method in claim 2 wherein the second predefined cipher block chaining operation comprises either a backward CBC or a predefined stream cipher procedure.

4. The method in claim 3 wherein the predefined portion of the intermediate stream and the encrypted MAC are both at least 32 bits in length.

5. The method in claim 3 wherein the backward CBC is calculated according to the following equations:

for i=n−

1;

6. The method in claim 2 wherein encrypting step comprises the step of generating the encrypted MAC through use of DES (data encryption standard).

7. The method in claim 6 wherein the predefined portion of the intermediate stream and the encrypted MAC are both at least 32 bits in length.

8. The method in claim 2 wherein the first cipher block chaining operation is a forward CBC.

9. The method in claim 8 wherein the predefined portion of the intermediate stream and the encrypted MAC are both at least 32 bits in length.

10. The method in claim 8 wherein the constructing step further comprises the steps, provided through the stream cipher procedure of:

generating a cipher stream through a predefined stream cipher function in response to both the intermediate stream and, as a seed to the stream cipher function, the encrypted MAC; and

combining, through a predetermined function, each different block of the cipher stream with a corresponding different block of the intermediate stream so as to yield a corresponding different one of the blocks of the remainder of the ciphertext message.

11. The method in claim 10 wherein the predetermined function is an exclusive-OR operation.

12. The method in claim 10 wherein the predefined stream cipher procedure is an RC4 stream cipher.

13. The method in claim 10 wherein the predefined portion of the intermediate stream and the encrypted MAC are both at least 32 bits in length.

14. The method in claim 8 wherein the forward CBC is calculated according to the following equations:

for i=0;

15. A computer readable medium having computer executable instructions stored therein for performing the steps of claim 14.

16. The method in claim 8 wherein the forward CBC is calculated according to the following equations, where K is a second intermediate stream having n+1 blocks, K_i:

for i=0;

17. A computer readable medium having computer executable instructions stored therein for performing the steps of claim 1.

18. A method of decrypting a ciphertext message into a recovered plaintext message ({circumflex over (P)}), having n+1 blocks ({circumflex over (P)}_i, where n≧

i≧

0 and n is an integer), and detecting whether integrity of the ciphertext message has been violated, the method comprising the steps of;

(a) decrypting the ciphertext message into a recovered plaintext message comprising the steps of;

(a1) removing, in response to an encrypted message authentication code contained in a predefined portion of the ciphertext message, a predefined variation from a remainder of the ciphertext message so as to yield an intermediate stream, the variation also being contained within the encrypted MAC; and

(a2) determining the recovered plaintext message, as a predefined function of the intermediate stream and a decrypted version of the encrypted MAC; and

(b) determining whether the integrity of the ciphertext message has been violated comprising the steps of;

(b1) generating, in response to the recovered plaintext message, a recovered MAC therefrom through the steps of;

(b1a) transforming the recovered plaintext message, through a first predefined cipher block chaining (CBC) operation and using a key formed in response to predefined non-zero integer values a, b, c and d, into an intermediate stream Ŷ

having n+1 blocks (Ŷ

_i with n≧

i≧

0); and

(b1b) forming the MAC as a predefined portion of the intermediate stream;

(b1c) wherein the CBC is implemented according to the following so as to yield Ŷ

_i;

(i) for i=0, as a first function, F, of {circumflex over (P)}₀ as input;

(ii) for even i within n, as the function, F, of Ŷ

<sub>i−

1</sub> and {circumflex over (P)}_i as input; and

(iii) for odd i within n, as a second function, G, of Ŷ

<sub>i−

1</sub> and {circumflex over (P)}_i as input;

where;

{circumflex over (P)}₀ and {circumflex over (P)}_i represent block zero

and i within the recovered plaintext message ({circumflex over (P)}), respectively, and the functions F and G comprise terms of the form ax+b and cx+d, respectively, with x representing the input to either of the functions; and

(b2) comparing the values of the recovered MAC and the decrypted MAC so as to determine any discrepancy therebetween, whereby said discrepancy indicates that the ciphertext message has been altered prior to its decryption.

19. The method of claim 18 wherein the intermediate stream has a predefined portion and a remainder and the decrypting step further comprises the steps of:

decrypting the predefined portion of the ciphertext message, through a predetermined inverse pseudo-random permutation, so as to yield the decrypted MAC;

inserting the decrypted MAC into the predefined portion of the intermediate stream; and

transforming the intermediate stream, through a second predefined cipher block chaining operation, so as to yield the recovered plaintext message; and

the determining step further comprises the step of ascertaining, through a third predefined cipher block chaining operation and in response to the recovered plaintext message, the recovered MAC the therefrom.

20. The method in claim 19 wherein the first predefined cipher block chaining operation comprises either a backward CBC or a predefined stream cipher procedure.

21. The method in claim 20 wherein the predefined portion of the intermediate stream and the encrypted MAC are both at least 32 bits in length.

22. The method in claim 21 wherein the generating step further comprises the steps, provided through the stream cipher procedure of:

generating a cipher stream through a predefined stream cipher function in response to both the ciphertext message and, as a seed to the stream cipher function, the encrypted MAC; and

combining, through a predetermined function, each different block of the cipher stream with a corresponding different block of the ciphertext message so as to yield a corresponding different one of the blocks of the remainder of the intermediate stream.

23. The method in claim 22 wherein the predetermined function is an exclusive-OR operation.

24. The method in claim 22 wherein the predefined stream cipher function is an RC4 stream cipher.

25. The method in claim 22 wherein the predefined portion of the intermediate stream and the encrypted MAC are both at least 32 bits in length.

26. The method in claim 20 wherein the backward CBC is calculated according to the following equations:

for i=n−

1;

${\hat{Y}}_{n-1}=\frac{F^{-1}<br><br>\left[C_{n-1}\right]}{e^{\mathrm{\alpha <br><br>}}}$

for even i within 0≧

i>

n−

1;

${\hat{Y}}_i=\frac{F^{-1}<br><br>\left[\left(C_i\right)-\left(C_{i+1}\right)\right]}{e^{\mathrm{\alpha <br><br>}}}$

for odd i within 0≧

i>

n−

1;

27. The method in claim 19 wherein the second predefined cipher block chaining operation is a backward CBC.

28. The method in claim 27 wherein the backward CBC is calculated according to the following equations:

for i=0;

${\hat{P}}_0=\frac{F^{-1}<br><br>\left[\left({\hat{Y}}_0\right)\right]}{e^{\mathrm{\alpha <br><br>}}}$

for even i within n;

${\hat{P}}_i=\frac{F^{-1}<br><br>\left[\left({\hat{Y}}_i\right)-\left({\hat{Y}}_{i-1}\right)\right]}{e^{\mathrm{\alpha <br><br>}}}$

for odd i within n;

29. The method in claim 28 wherein the predefined portion of the intermediate stream and the encrypted MAC are both at least 32 bits in length.

30. The method in claim 19 wherein decrypting step comprises the step of generating the decrypted MAC through use of an inverse DES (data encryption standard).

31. The method in claim 30 wherein the predefined portion of the intermediate stream and the encrypted MAC are both at least 32 bits in length.

32. The method in claim 19 wherein the third predefined cipher block chaining operation comprises a forward CBC.

33. The method in claim 32 wherein the predefined portion of the intermediate stream and the encrypted MAC are both at least 32 bits in length.

34. The method in claim 32 wherein the forward CBC is calculated according to the following equations:

for i=0;

35. Apparatus for encrypting a plaintext message, P having n+1 blocks (P_i, where n>

i>

0 and n is an integer), into a ciphertext message such that, in response to contents of the ciphertext message itself, a subsequent violation to integrity of the ciphertext message can be detected, the apparatus comprising;

(a) a processor; and

(b) a memory having said computer program stored therein, said program having computer executable instructions;

(c) wherein, in response to the stored instructions, the processor;

(c1) generates, in response to the plaintext message, an intermediate stream Y, having n+1 blocks (Y_i) with a predefined portion of the intermediate stream defining a message authentication code (MAC) by

(c1a) transforming the plaintext message, through a first predefined cipher block chaining (CBC) operation and using a key formed in response to predefined non-zero integer values a, b, c and d, into the intermediate stream; and

(c1b) forming the MAC as a predefined portion of the intermediate stream;

(c1c) wherein the CBC is implemented according to the following so as to yield Y_i;

(i) for i=0, as a first function, F, of P₀ as input;

(ii) for even i within n, as the function, F, of Y<sub>i−

1</sub> and P_i as input; and

(iii) for odd i within n, as a second function, G, of Y<sub>i−

1</sub> and P_i as input;

where;

P₀ and P_i represent blocks zero and i within the plaintext message (P), respectively, and the functions F and G comprise terms of the form ax+b and cx+d, respectively, with x representing the input to either of the functions;

(c2) inserts an encrypted version of the MAC into a predefined portion of the ciphertext message; and

(c3) generates, in response to the intermediate stream and the encrypted MAC, a remainder of the ciphertext message such that the remainder exhibits a predefined variation contained within the encrypted MAC.

36. The apparatus of claim 35 wherein the processor, in response to the stored instructions:

encrypts the predefined portion of the intermediate stream, through a predetermined pseudo-random permutation, into the encrypted MAC;

inserts the encrypted MAC into the predefined portion of the ciphertext message; and

constructs the remainder of the ciphertext message through a second predefined cipher block chaining operation and in response to both the remainder of the intermediate stream and the encrypted MAC such that a pseudo-random sequence in the encrypted MAC, the sequence being said predefined variation, extends throughout the remainder of the ciphertext message.

37. The apparatus in claim 36 wherein the first predefined cipher block chaining operation is a forward CBC.

38. The apparatus in claim 37 wherein the predefined portion of the intermediate stream and the encrypted MAC are both at least 32 bits in length.

39. The apparatus in claim 37 wherein the processor, in response to the stored instructions and through the stream cipher procedure:

generates a cipher stream through a predefined stream cipher function in response to both the intermediate stream and, as a seed to the stream cipher function, the encrypted MAC; and

combines, through a predetermined function, each different block of the cipher stream with a corresponding different block of the intermediate stream so as to yield a corresponding different one of the blocks of the remainder of the ciphertext message.

40. The apparatus in claim 39 wherein the predetermined function is an exclusive-OR operation.

41. The apparatus in claim 39 wherein the predefined stream cipher procedure is an RC4 stream cipher.

42. The apparatus in claim 39 wherein the predefined portion of the intermediate stream and the encrypted MAC are both at least 32 bits in length.

43. The apparatus in claim 37 wherein the forward CBC is calculated according to the following equations:

for i=0;

44. The apparatus in claim 37 wherein the forward CBC is calculated according to the following equations, where K is a second intermediate stream having n+1 blocks, K_i:

for i=0;

45. The apparatus in claim 36 wherein the second predefined cipher block chaining operation is a backward CBC or a predefined stream cipher procedure.

46. The apparatus in claim 45 wherein the predefined portion of the intermediate stream and the encrypted MAC are both at least 32 bits in length.

47. The apparatus in claim 45 wherein the backward CBC is calculated according to the following equations:

for i=n−

1;

48. The apparatus in claim 36 wherein the processor, in response to the stored instructions, generates the encrypted MAC through use of DES (data encryption standard).

49. The apparatus in claim 48 wherein the predefined portion of the intermediate stream and the encrypted MAC are both at least 32 bits in length.

50. Apparatus for decrypting a ciphertext message into a recovered plaintext message ({circumflex over (P)}), having n+1 blocks ({circumflex over (P)}_i, where n≧

i≧

0 and n is an integer), and detecting whether integrity of the ciphertext message has been violated, the apparatus comprising;

(a) a processor; and

(b) a memory having said computer program stored therein, said program having computer executable instructions;

(c) wherein, in response to the stored instructions, the processor;

(c1) removes, in response to an encrypted message authentication code contained in a predefined portion of the ciphertext message, a predefined variation from a remainder of the ciphertext message so as to yield an intermediate stream, the variation also being contained within the encrypted MAC; and

(c2) determines the recovered plaintext message, as a predefined function of the intermediate stream and a decrypted version of the encrypted MAC;

(c3) generates, in response to the recovered plaintext message, a recovered MAC therefrom through;

(c3a) transforming the recovered plaintext message, through a first predefined cipher block chaining (CBC) operation and using a key formed in response to predefined non-zero integer values a, b, c and d, into an intermediate stream Ŷ

having n+1 blocks (Ŷ

_i with n≧

i≧

0); and

(c3c) forming the MAC as a predefined portion of the intermediate stream;

wherein the CBC is implemented according to the following so as to yield Y_i;

(i) for i=0, as a first function, F, of {circumflex over (P)}₀ as input;

(ii) for even i within n, as the function, F, of Ŷ

<sub>i−

1</sub> and {circumflex over (P)}_i as input; and

(iii) for odd i within n, as a second function, G, of Ŷ

<sub>i−

1</sub> and {circumflex over (P)}_i as input;

where;

{circumflex over (P)}₀ and {circumflex over (P)}_i represent block zero and i within the recovered plaintext message ({circumflex over (P)}), respectively, and the functions F and G comprise terms of the form ax+b and cx+d, respectively, with x representing the input to either of the functions; and

(c4) compares the values of the recovered MAC and the decrypted MAC so as to determine any discrepancy therebetween, whereby said discrepancy indicates that the ciphertext message has been altered prior to its decryption.

51. The apparatus of claim 50 wherein the intermediate stream has a predefined portion and a remainder, and the processor, in response to the stored instructions:

decrypts the predefined portion of the ciphertext message, through a predetermined inverse pseudo-random permutation, so as to yield the decrypted MAC;

inserts the decrypted MAC into the predefined portion of the intermediate stream;

transforms the intermediate stream, through a second predefined cipher block chaining operation, so as to yield the recovered plaintext message; and

ascertains, through a third predefined cipher block chaining operation and in response to the recovered plaintext message, the recovered MAC therefrom.

52. The apparatus in claim 51 wherein the first predefined cipher block chaining operation comprises either a backward CBC or a predefined stream cipher procedure.

53. The apparatus in claim 52 wherein the predefined portion of the intermediate stream and the encrypted MAC are both at least 32 bits in length.

54. The apparatus in claim 52 wherein the backward CBC is calculated according to the following equations:

for i=n−

1;

${\hat{Y}}_{n-1}=\frac{F^{-1}<br><br>\left[C_{n-1}\right]}{e^{\mathrm{\alpha <br><br>}}}$

for even i within 0≧

i>

n−

1;

${\hat{Y}}_i=\frac{F^{-1}<br><br>\left[\left(C_i\right)-\left(C_{i+1}\right)\right]}{e^{\mathrm{\alpha <br><br>}}}$

for odd i within 0≧

i>

n−

1;

55. The apparatus in claim 51 wherein the second predefined cipher block chaining operation is a backward CBC.

56. The apparatus in claim 55 wherein the predefined portion of the intermediate stream and the encrypted MAC are both at least 32 bits in length.

57. The apparatus in claim 51 wherein the backward CBC is calculated according to the following equations:

For i=0;

${\hat{P}}_0=\frac{F^{-1}<br><br>\left[\left({\hat{Y}}_0\right)\right]}{e^{\mathrm{\alpha <br><br>}}}$

For even i within n;

${\hat{P}}_i=\frac{F^{-1}<br><br>\left[\left({\hat{Y}}_i\right)-\left({\hat{Y}}_{i-1}\right)\right]}{e^{\mathrm{\alpha <br><br>}}}$

For odd i within n;

58. The apparatus in claim 52 wherein the processor, in response to the stored instructions:

generates a cipher stream through a predefined stream cipher function in response to both the ciphertext message and, as a seed to the stream cipher function, the encrypted MAC; and

combines, through a predetermined function, each different block of the cipher stream with a corresponding different block of the ciphertext message so as to yield a corresponding different one of the blocks of the remainder of the intermediate stream.

59. The apparatus in claim 58 wherein the predetermined function is an exclusive-OR operation.

60. The apparatus in claim 58 wherein the predefined stream cipher procedure is an RC4 stream cipher.

61. The apparatus in claim 58 wherein the predefined portion of the intermediate stream and the encrypted MAC are both at least 32 bits in length.

62. The apparatus in claim 58 wherein the processor, in response to the stored instructions, generates the decrypted MAC through use of an inverse DES (data encryption standard).

63. The apparatus in claim 62 wherein the predefined portion of the intermediate stream and the encrypted MAC are both at least 32 bits in length.

64. The apparatus in claim 51 wherein the third predefined cipher block chaining operation comprises a forward CBC.

65. The apparatus in claim 64 wherein the predefined portion of the intermediate stream and the encrypted MAC are both at least 32 bits in length.

66. The apparatus in claim 64 wherein the forward CBC is calculated according to the following equations:

for i=0;