BLOCK CIPHER MODES OF NON- MALLEABLE OPERATION

Title:

BLOCK CIPHER MODES OF NON- MALLEABLE OPERATION

Document Type and Number:

WIPO Patent Application WO/2013/024379

Kind Code:

Abstract:

A method and system for producing at least one ciphertext block from at least one plaintext block using a block cipher is described, the block cipher including an encryption function Enc, the method and system including receiving n plaintext blocks, wherein n is an integer greater than 0, for each plaintext block of the n plaintext blocks inputting two inputs into a keyed invertible transformation function, e, the two inputs including a masking value, denoted Mi,where 0 < i <= n, and one of a plaintext block, denoted Pi, Pi being an i-th plaintext block of the n plaintext blocks, and a function of the plaintext block Pi, where 0 < i <= n, wherein one of the two inputs Mi and Pi includes a key for round key generation by the function e and the second of the two inputs Mi and Pi includes a data item operated on during rounds of function e, outputting a result of the function e, the output being at least partially encrypted in a case where the masking value includes an output of the encryption function Enc, the output of the function e includes a ciphertext block, thereby producing n ciphertext blocks, in a case where the masking value includes one of one of Pi-,and an initialization vector when i =1, and one of a function of Pi-1, and an initialization vector when i=1, the output of the function e includes an input into the encryption function Enc, and the output of the function Enc includes a ciphertext block, thereby producing n ciphertext blocks, and in a case where the masking value includes one of an output of the function e(M i-1 , P i-1 ), and an initialization vector when i =1, the input into the function Enc includes a result of xor-ing the masking value Mi with Pi, and the output of the function Enc includes a ciphertext block, thereby producing n ciphertext blocks. Related methods and systems are also described.

More Like This:

JP2004506379	Methods and systems for embedding information bits in the source signal with steganography
WO/2023/107350	SYSTEM AND METHOD FOR CREATING AND MAINTAINING IMMUTABILITY, AGREEMENT AND AVAILABILITY OF DATA
JP5453367	A block cipher system with substitutions to hide the core cryptographic functions of each cryptographic round

Inventors:

MANTIN ITSIK (IL)

Application Number:

PCT/IB2012/053750

Publication Date:

February 21, 2013

Filing Date:

July 24, 2012

Export Citation:

Click for automatic bibliography generation Help

Assignee:

NDS LTD (GB)
MANTIN ITSIK (IL)

International Classes:

H04L9/06

Domestic Patent References:

WO2008021145A1	2008-02-21
WO2007118829A1	2007-10-25
WO2006117775A2	2006-11-09

Foreign References:

EP1077554A1	2001-02-21
US20070058806A1	2007-03-15
US6351539B1	2002-02-26
US7940930B2	2011-05-10

Other References:

"Chapter 7: Block Ciphers ED - Menezes A J; Van Oorschot P C; Vanstone S A", 1 October 1996, HANDBOOK OF APPLIED CRYPTOGRAPHY; [CRC PRESS SERIES ON DISCRETE MATHEMATICES AND ITS APPLICATIONS], CRC PRESS, BOCA RATON, FL, US, PAGE(S) 223 - 282, ISBN: 978-0-8493-8523-0, XP001525007
A. MENEZES, P. VAN OORSCHOT AND S. VANSTONE.,: "Handbook of Applied Cryptography", 1996, CRC PRESS, pages: 228 - 233,272,

Attorney, Agent or Firm:

KATZ, Samuel M. et al. (One London Road, Staines Middlesex TW18 4EX, GB)

Download PDF:

View/Download PDF PDF Help

Claims:

What is claimed is:

CLAIMS

1. A method for producing at least one ciphertext block from at least one plaintext block using a block cipher, the block cipher comprising an encryption function El C, the method comprising:

receiving n plaintext blocks, wherein n is an integer greater than 0; for each plaintext block of the n plaintext blocks:

inputting two inputs into a keyed invertible transformation function, e, the two inputs comprising: a masking value, denoted Mj, where 0 < i <= n; and one of: a plaintext block, denoted P^, Pj being an i-th plaintext block of the n plaintext blocks; and a function of the plaintext block P^, where 0 < i <= n,

wherein one of the two inputs M and Pj comprises a key for round key generation by the function e and the second of the two inputs Mj and Pi comprises a data item operated on during rounds of function e

outputting a result of the function e, the output being at least partially encrypted:

in a case where the masking value comprises an output of the encryption function Enc, the output of the function e comprises a ciphertext block, thereby producing n ciphertext blocks;

in a case where the masking value comprises one of: one of: Pi_i; and an initialization vector when i

=1 ;

and

one of: a function of P .i; and an initialization vector when i =1, the output of the function e comprises an input into the encryption function EllC, and the output of the function Enc comprises a ciphertext block, thereby producing n ciphertext blocks; and

in a case where the masking value comprises one of: an output of the function e(Mi_j , Pi.]),' and an initialization vector when i =1, the input into the function EllC comprises a result of xor-ing the masking value

M with Pj, and the output of the function Enc comprises a ciphertext block, thereby producing n ciphertext blocks. 2. A method for producing at least one ciphertext block from at least one plaintext block using a block cipher, the block cipher comprising an encryption function EllC, the method comprising:

receiving n plaintext blocks, wherein n is an integer greater than 0; for each plaintext block of the n plaintext blocks:

computing an output of a function e, the output being e(Mi,

P) and

computing Έΐίθ(β(Μ_ί, PJ) according to a key of the block cipher,

thereby producing n ciphertext blocks,

wherein:

function e comprises a keyed invertible transformation function;

0 < i <= n;

Pi denotes an i-th plaintext block of the n plaintext blocks; and

Mi denotes a masking value, the masking value being _z.j for i>l, and an initialization vector for i=l.

3. The method according to claim 2 wherein function e comprises a plurality of rounds of a second block cipher encryption or decryption function.

4. The method according to claim 3 wherein function e comprises 3 rounds of the second block cipher encryption function.

5. The method according to any of claims 3 or 4 wherein a round key generation algorithm of function e comprises one of:

the round key generation algorithm of the second block cipher encryption function; and

an non-standard derivation algorithm.

6. The method according to claim 5 wherein the non-standard derivation algorithm comprises xor-ing a key with round constants.

7. The method according to any of claims 3 - 6 wherein the round function of function e comprises one of:

the round key generation algorithm of the second block cipher encryption function; and

a tweaked block cipher round function.

8. The method according to claim 7 wherein the tweaked block cipher round function comprises any of:

pseudo-random tables;

pseudo-random s-boxes; and

pseudo-random p-boxes.

9. A method for producing at least one plaintext block from at least one ciphertext block using a block cipher, the block cipher comprising and decryption function Dec, the method comprising:

receiving n ciphertext blocks, wherein n is an integer greater than 0; for each ciphertext block of the n ciphertext blocks:

computing an output of the function Dec, the output being

Dec( Cj), according to a key of the block cipher; and computing e^'1 (M_bDec( Cj) ) ;

thereby producing n plaintext blocks,

wherein:

function e ^ comprises a keyed invertible transformation function;

0 < i <= n;

Ci denotes an i-th ciphertext block of the n ciphertext blocks; and

Mi denotes a masking value, the masking value being _;-1 for i>l, and an initialization vector for Mj, and Pj denoting an i-th plaintext block of the n plaintext blocks.

10. The method according to claim 9 wherein function e ¹ comprises a plurality of rounds of a second block cipher encryption function.

11. The method according to claim 10 and wherein function comprises 3 rounds of a second block cipher encryption function.

12. The method according to any of claims 10 or 11 wherein a round key generation algorithm of function e ¹ comprises one of:

the round key generation algorithm of the second block cipher encryption function; and

an non-standard derivation algorithm.

13. The method according to claim 12 wherein the non-standard derivation algorithm comprises xor-ing a key with round constants.

14. The method according to any of claims 10 - 13 wherein the round function of function e ¹ comprises one of:

the round key generation algorithm of the second block cipher encryption function; and

a tweaked block cipher round function.

15. The method according to claim 14 wherein the tweaked block ciphi round function comprises any of:

pseudo-random tables;

pseudo-random s-boxes; and

pseudo-random p-boxes.

16. The method of any of claims 10 - 15 wherein the function e comprises the inverse of function e of claim 2.

17. A method for producing at least one ciphertext block from at least one plaintext block using a block cipher, the block cipher comprising and encryption function EllC, the method comprising:

receiving n plaintext blocks, wherein n is an integer greater than 0; for each plaintext block of the n plaintext blocks:

computing an output of a function e, the output being e(M(,

computing Enc( ; φ Pj) according to a key of the block cipher,

thereby producing n ciphertext blocks,

wherein:

function e comprises a keyed invertible transformation function;

0 < i <= n; Pi denotes an i-th plaintext block of the n plaintext blocks; and

Mi denotes a masking value, the masking value being e(Mi_ j, Pi-i) for i > 1, and an initialization vector for i=l.

18. The method according to claim 17 wherein function e comprises a plurality of rounds of a second block cipher encryption function.

19. The method according to claim 18 wherein function e comprises 3 rounds of the second block cipher encryption function.

20. The method according to any of claims 18 or 19 wherein a round key generation algorithm of function e comprises one of:

the round key generation algorithm of the second block cipher encryption function; and

an non-standard derivation algorithm.

21. The method according to claim 20 wherein the non-standard derivation algorithm comprises xor-ing a key with round constants.

22. The method according to any of claims 18 - 21 wherein the round function of function e comprises one of:

the round key generation algorithm of the second block cipher encryption function; and

a tweaked block cipher round function.

23. The method according to claim 22 wherein the tweaked block cipher round function comprises any of:

pseudo-random tables;

pseudo-random s-boxes; and pseudo-random p-boxes.

24. A method for producing at least one plaintext block from at least one ciphertext block using a block cipher, the block cipher comprising and decryption function Dec, the method comprising:

receiving n ciphertext blocks, wherein n is an integer greater than 0; for each ciphertext block of the n ciphertext blocks:

computing (Mi © Dec(Ci)) according to a key of the block cipher,

thereby producing n plaintext blocks,

wherein:

function e comprises a keyed invertible transformation function;

0 < i <= n;

C; denotes an i-th ciphertext block of the n ciphertext blocks; and

Mi denotes a masking value, the masking value being e(Mi_ j, Pi-j) for i > 1, and an initialization vector for i=l, denoting an i-th plaintext block of the n plaintext blocks.

25. The method according to claim 24 wherein function e comprises a plurality of rounds of a second block cipher encryption function.

26. The method according to claim 25 wherein function e comprises 3 rounds of the second block cipher encryption function.

27. The method according to any of claims 25 or 26 wherein a round key generation algorithm of function e comprises one of:

the round key generation algorithm of the second block cipher encryption function; and -standard derivation algorithm.

28. The method according to claim 27 wherein the non-standard derivation algorithm comprises xor-ing a key with round constants.

29. The method according to any of claims 25 - 28 wherein the round function of function e comprises one of:

the round key generation algorithm of the second block cipher encryption function; and

a tweaked block cipher round function.

30. The method according to claim 29 wherein the tweaked block cipher round function comprises any of:

pseudo-random tables;

pseudo-random s-boxes; and

pseudo-random p-boxes.

31. A method for producing at least one ciphertext block from at least one plaintext block using a block cipher, the block cipher comprising and encryption function EllC, the method comprising:

receiving n plaintext blocks, wherein n is an integer greater than 0; for each plaintext block of the n plaintext blocks:

computing an output of a function e, the output being e(Mi,

Pi); and

computing Έΐίθ β(Μ_ί, PJ) according to a key of the block cipher,

thereby producing n ciphertext blocks,

wherein:

function e comprises a keyed invertible transformation function;

0 < i <= n; Pi denotes an i-th plaintext block of the n plaintext blocks; and

Mi denotes a masking value, the masking value being:

xTend(CS(Pi_j)) for i>l, and an initialization vector for i=l, where CS denotes a shrinking function, and xTend denotes a function which extends an output of the CS function into a value of an original block length.

32. The method according to claim 31 wherein the shrinking function comprises a checksum function.

33. The method according to claim 31 wherein the shrinking function outputs an output of 1 - 3 bytes long. 34. The method according to any of claims 31 - 33 wherein the xTend function extends the output of the CS function with a fixed vector.

35. The method according to any of claims 31 - 33 wherein the xTend function extends the output of the CS function by repeating the output of the CS function in order to extend the output to a fixed length.

36. The method according to any of claims 31 - 33 wherein the xTend function comprises a lookup table, and the output of the CS function comprises an index of the lookup table.

37. The method according to any of claims 31 - 36 wherein function e comprises a plurality of rounds of a second block cipher encryption function.

38. The method according to claim 37 wherein function e comprises 3 rounds of the second block cipher encryption function.

39. The method according to any of claims 37 or 38 wherein a round key generation algorithm of function e comprises one of:

the round key generation algorithm of the second block cipher encryption function; and

an non-standard derivation algorithm.

40. The method according to claim 39 wherein the non-standard derivation algorithm comprises xor-ing a key with round constants. 41. The method according to any of claims 37 - 40 wherein the round function of function e comprises one of:

the round key generation algorithm of the second block cipher encryption function; and

a tweaked block cipher round function.

42. The method according to claim 41 wherein the tweaked block cipher round function comprises any of:

pseudo-random tables;

pseudo-random s-boxes; and

pseudo-random p-boxes.

43. A method for producing at least one plaintext block from at least one ciphertext block using a block cipher, the block cipher comprising and decryption function Dec, the method comprising:

receiving n ciphertext blocks, wherein n is an integer greater than 0; for each ciphertext block of the n ciphertext blocks:

computing an output of the function Dec, the output being Dec( Ci), according to a key of the block cipher;

computing e^'1 (M Dec( Ci));

thereby producing n plaintext blocks,

wherein: function e comprises a keyed invertible transformation function;

0 < i <= n;

C; denotes an i-th ciphertext block of the n ciphertext blocks; and

Mi denotes a masking value, the masking value being xTend( CS(Pi.j)) for i>l, and an initialization vector for i=l, where CS denotes a shrinking function, and xTend denotes a function which extends an output of the CS function into a value of an original block length.

44. The method according to claim 43 wherein the shrinking function comprises a checksum function.

45. The method according to claim 43 wherein the shrinking function outputs an output of 1 - 3 bytes long.

46. The method according to any of claims 43 - 45 wherein the xTend function extends the output of the CS function with a fixed vector. 47. The method according to any of claims 43 - 45 wherein the xTend function extends the output of the CS function by repeating the output of the CS function in order to extend the output to a fixed length.

48. The method according to any of claims 43 - 45 wherein the xTend function comprises a lookup table, and the output of the CS function comprises an index of the lookup table.

49. The method according to claim 43 wherein function e comprises a plurality of rounds of a second block cipher encryption function.

50. The method according to claim 49 wherein function e comprises 3 rounds of the second block cipher encryption function.

51. The method according to any of claims 49 or 50 wherein a round key generation algorithm of function e ¹ comprises one of:

the round key generation algorithm of the second block cipher encryption function; and

an non-standard derivation algorithm. 52. The method according to claim 51 wherein the non-standard derivation algorithm comprises xor-ing a key with round constants.

53. The method according to any of claims 49 - 52 wherein the round function of function e ¹ comprises one of:

the round key generation algorithm of the second block cipher encryption function; and

a tweaked block cipher round function.

54. The method according to claim 53 wherein the tweaked block cipher round function comprises any of:

pseudo-random tables;

pseudo-random s-boxes; and

pseudo-random p-boxes. 55. The method of any of claims 43 - 54 and wherein the function e ¹ comprises the inverse of function e of claim 31

56. A method for producing at least one ciphertext block from at least one plaintext block using a block cipher, the block cipher comprising and encryption function Enc, the method comprising:

receiving n plaintext blocks, wherein n is an integer greater than 0; for each plaintext block of the n plaintext blocks:

computing Mi — Εΐ1θ(7 according to a key of the block cipher; and

computing e(M_b P ,

thereby producing n ciphertext blocks,

wherein:

function e comprises a keyed invertible transformation function;

0 < i <= n;

Pi denotes an i-th plaintext block of the n plaintext blocks;

IV i denotes an initialization vector; and

Mi denotes a masking value.

57. The method according to claim 56 wherein function e comprises a plurality of rounds of a second block cipher encryption function.

58. The method according to claim 57 wherein function e comprises 3 rounds of the second block cipher encryption function. 59. The method according to any of claims 57 or 58 wherein a round key generation algorithm of function e comprises one of:

the round key generation algorithm of the second block cipher encryption function; and

an non-standard derivation algorithm.

60. The method according to claim 59 wherein the non-standard derivation algorithm comprises xor-ing a key with round constants.

61. The method according to any of claims 57 - 60 wherein the round function of function e comprises one of:

the round key generation algorithm of the second block cipher encryption function; and

a tweaked block cipher round function.

62. The method according to claim 61 wherein the tweaked block cipher round function comprises any of:

pseudo-random tables;

pseudo-random s-boxes; and

pseudo-random p-boxes.

63. The method according to any of claims 56 - 62 wherein IV i = IV + i - 1.

64. A method for producing at least one plaintext block from at least one ciphertext block using a block cipher, the block cipher comprising and encryption function EllC, the method comprising:

receiving n ciphertext blocks, wherein n is an integer greater than 0; for each ciphertext block of the n ciphertext blocks:

computing Mj— Enc^K_jj according to a key of the block cipher;

computing e (Μ_» Cj) thereby producing n plaintext wherein:

function e ¹ comprises a plurality of rounds of a keyed invertible transformation function;

0 < i <= n;

Ci denotes an i-th ciphertext block of the n ciphertext IV i denotes an initialization vector; and

Mi denotes a masking value.

65. The method according to claim 64 wherein function e ¹ comprises a plurality of rounds of a second block cipher encryption function.

66. The method according to claim 65 wherein function e ^ comprises 3 rounds of the second block cipher encryption function. 67. The method according to any of claims 65 or 66 wherein a round key generation algorithm of function e ¹ comprises one of:

the round key generation algorithm of the second block cipher encryption function; and

an non-standard derivation algorithm.

68. The method according to claim 67 wherein the non-standard derivation algorithm comprises xor-ing a key with round constants.

69. The method according to any of claims 65 - 68 wherein the round function of function e ^ comprises one of:

the round key generation algorithm of the second block cipher encryption function; and

a tweaked block cipher round function. 70. The method according to claim 69 wherein the tweaked block cipher round function comprises any of:

pseudo-random tables;

pseudo-random s-boxes; and

pseudo-random p-boxes.

71. The method according to any of claims 64 - 70 wherein IV{ = IV + i - 1.

72. The method of any of claims 64 - 71 and wherein the function e comprises the inverse of function e of claim 56.

73. Apparatus for producing at least one ciphertext block from at least one plaintext block using a block cipher, the block cipher comprising an encryption function Enc, the apparatus comprising:

a receiving unit for receiving n plaintext blocks, wherein n is an integer greater than 0;

an initialization unit operative to set an initialization vector equal to an initial value;

a computation unit operative, for each plaintext block of the n plaintext blocks:

to compute an output of a function e, the output being β(Μ{,

Pi); and

to compute Elic(e(¾ _/, PJ) according to a key of the block cipher,

thereby producing n ciphertext blocks,

wherein:

function e comprises a keyed invertible transformation function;

0 < i <= n;

Pi denotes an i-th plaintext block of the n plaintext blocks; and

Mi denotes a masking value, the masking value being _;-1 for i>l, and the initialization vector for i=l.

74. An apparatus for producing at least one plaintext block from at least one ciphertext block using a block cipher, the block cipher comprising and decryption function Dec, the apparatus comprising:

a receiving unit for receiving n plaintext blocks, wherein n is an integer greater than 0;

an initialization unit operative to set an initialization vector equal to an initial value;

a computation unit operative, for each plaintext block of the n plaintext blocks:

to compute an output of the function Dec, the output being

Dec( Ci), according to a key of the block cipher; and to compute e^'1 '

thereby producing n plaintext blocks,

wherein:

function e ¹ comprises a keyed invertible transformation function;

0 < i <= n;

Ci denotes an i-th ciphertext block of the n ciphertext blocks; and

Mi denotes a masking value, the masking value being _;-1 for i>l, and the initialization vector for Mj, and denoting an i-th plaintext block of the n plaintext blocks.

75. Apparatus for producing at least one ciphertext block from at least one plaintext block using a block cipher, the block cipher comprising and encryption function EllC, the apparatus comprising:

a receiving unit for receiving n plaintext blocks, wherein n is an integer greater than 0;

an initialization unit operative to set an initialization vector equal to an initial value; a computation unit operative, for each plaintext block of the n plaintext blocks:

to compute an output of a function e, the output being e(M_iy

Pi); and

to compute Enc(A/_/ φ Pj) according to a key of the block cipher,

thereby producing n ciphertext blocks,

wherein:

function e comprises a keyed invertible transformation function;

0 < i <= n;

Pi denotes an i-th plaintext block of the n plaintext blocks; and

Mi denotes a masking value, the masking value being e(Mi_ /, P{-i) for i > 1, and the initialization vector for i=l.

76. An apparatus for producing at least one plaintext block from at least one ciphertext block using a block cipher, the block cipher comprising and decryption function Dec, the apparatus comprising:

a receiving unit for receiving n ciphertext blocks, wherein n is an integer greater than 0;

an initialization unit operative to set an initialization vector equal to an initial value;

a computation unit operative, for each ciphertext block of the n ciphertext blocks:

to compute (Mj φ Dec(Cj)) according to a key of the block cipher,

thereby producing n plaintext blocks,

wherein: function e comprises a keyed invertible transformation function;

0 < i <= n;

C; denotes an i-th ciphertext block of the n ciphertext blocks; and

Mi denotes a masking value, the masking value being e(Mi_i, Pi-i) for i > 1, and the initialization vector for i=l, P[ denoting an i-th plaintext block of the n plaintext blocks. 77. An apparatus for producing at least one ciphertext block from at least one plaintext block using a block cipher, the block cipher comprising and encryption function EllC, the apparatus comprising:

a receiving unit for receiving n plaintext blocks, wherein n is an integer greater than 0;

an initialization unit operative to set an initialization vector equal to an initial value;

a computation unit operative, for each plaintext block of the n plaintext blocks:

to compute an output of a function e, the output being e(M_f,

to compute Elic(e(¾f_;-, PJ) according to a key of the block cipher,

thereby producing n ciphertext blocks,

wherein:

function e comprises a keyed invertible transformation function;

0 < i <= n;

Pi denotes an i-th plaintext block of the n plaintext blocks; and Mi denotes a masking value, the masking value being:

xTend(CS(Pi-])) for i>l, and the initialization vector for i=l, where CS denotes a shrinking function, and xTend denotes a function which extends an output of the CS function into a value of an original block length.

78. An apparatus for producing at least one plaintext block from at least one ciphertext block using a block cipher, the block cipher comprising and decryption function Dec, the apparatus comprising:

a receiving unit for receiving n ciphertext blocks, wherein n is an integer greater than 0;

an initialization unit operative to set an initialization vector equal to an initial value;

a computation unit operative, for each ciphertext block of the n ciphertext blocks:

to compute an output of the function Dec, the output being

Dec( Ci), according to a key of the block cipher; to compute e ¹ (M_t, Dec(Ci));

thereby producing n plaintext blocks,

wherein:

function e ¹ comprises a keyed invertible transformation function;

0 < i <= n;

Ci denotes an i-th ciphertext block of the n ciphertext blocks; and

Mi denotes a masking value, the masking value being xTend( CS(Pi.j)) for i>l, and the initialization vector for i=l, where CS denotes a shrinking function, and xTend denotes a function which extends an output of the CS function into a value of an original block length.

79. An apparatus for producing at least one ciphertext block from at least one plaintext block using a block cipher, the block cipher comprising and encryption function El C, the apparatus comprising:

a receiving unit for receiving n plaintext blocks, wherein n is an integer greater than 0;

an initialization unit operative to set an initialization vector equal to an initial value;

a computation unit operative, for each plaintext block of the n plaintext blocks:

to compute = El c(/K^) according to a key of the block cipher; and

to compute e(Mi, Pj),

thereby producing n ciphertext blocks,

wherein:

function e comprises a keyed invertible transformation function;

0 < i <= n;

Pi denotes an i-th plaintext block of the n plaintext blocks; IV i denotes an initialization vector; and

Mi denotes a masking value.

80. An apparatus for producing at least one plaintext block from at least one ciphertext block using a block cipher, the block cipher comprising and encryption function EllC, the apparatus comprising:

a receiving unit for receiving n plaintext blocks, wherein n is an integer greater than 0;

an initialization unit operative to set an initialization vector equal to an initial value; a computation unit operative, for each ciphertext block of the n ciphertext blocks:

to compute = Enc(/K^) according to a key of the block cipher;

to compute e ¹ (M^, C_j) thereby producing n plaintext blocks,

wherein:

function e ¹ comprises a plurality of rounds of a keyed invertible transformation function;

0 < i <= n;

Ci denotes an i-th ciphertext block of the n ciphertext blocks;

IV i denotes the initialization vector; and

Mi denotes a masking value.

Respectfully submitted,

Description:

BLOCK CIPHER MODES OF NON- MALLEABLE OPERATION

FIELD OF THE INVENTION

Embodiments of the present invention described herein relate to cryptography, and more specifically, to block cipher cryptography.

BACKGROUND OF THE INVENTION

Reference is now made to Fig. 1, which is a simplified block diagram illustration of a generalized block cipher (prior art). Block ciphers are well known in the art. Block ciphers typically encrypt plaintext in fixed sized n-bit blocks (often 16 or 64 bits, depicted as 16 bits). Block ciphers typically take an n- bit block of plain text and an n-bit key, and combine the block of plain text and the key using an encryption function, in order to output an n-bit block of cipher text.

For messages exceeding n bits, the simplest approach is to partition the message into n-bit blocks and encrypt each block separately. This mode of operation is usually referred to as "electronic-cookbook" (ECB) mode. There are other known modes of operation which attempt to solve various drawbacks of ECB. Well known modes of operation include CBC (Cipher Block Chaining), CFB (Cipher Feedback), and OFB (Output Feedback).

Various modes of operation are described in the Handbook of

Applied Cryptography, by A. Menezes, P. van Oorschot and S. Vanstone., CRC Press, 1996. The Handbook of Applied Cryptography is also available on-line at www.cacr.math.uwterloo.ca/hac. See pages 228 - 233, 272, 367 - 368, and 645 - 654, which describe various well known and standard applications of modes of operation of block ciphers.

Malleability in cryptography is discussed at en.wikipedia.org/wiki/Malleability_%28cryptography%29.

Naor et-al analyze different ways to achieve non-malleability in cryptographic primitives in a paper "Non-Malleable Cryptography" available at www.wisdom.weizmann.ac.il/~naor/PAPERS/nmc.ps.

Malleability in cryptography (see, for instance, en.wikipedia.org/wiki/Malleability_(cryptography)) is a property in which it is possible for an attacker to transform a cipher text into another cipher text in a manner that the new ciphertext will be decrypted by the legitimate decryptor into a plaintext that is related to the original plaintext in a way that is beneficial to the attacker. Naor et-al analyze different ways to achieve non-malleability in cryptographic primitives in "Non-Malleable Cryptography" (www.wisdom.weizmann.ac.il/~naor/PAPERS/nmc.ps). However, they do not discuss solutions to the practical problem of non-malleable mode of operation for block ciphers. Those that are skilled in the art will appreciate that malleability attacks may be applicable in applications where the decryption process is subject to white-box cryptanalysis and graybox cryptanalysis, e.g., DRM applications.

Accordingly, it is desirable to use a block cipher mode of operation that has the following properties:

Provides immunity against controlled manipulation of plaintext data;

Allows parallel decryption of blocks in the client;

Has minimal performance overhead when compared to CBC; and

Leaves obscurity hooks, i.e., has "holes" in which different proprietary functions can be added.

The only block cipher mode of operation with which the inventors are familiar, which is immune against controlled manipulation of plaintext data are authenticated encryption schemes such as OCB, CCM, CWC, EAX, GCM, PCFB and XCBC. However, these usually prevent parallel decryption of the blocks and random access to the encrypted data which is a critical feature in many applications.

The description of the embodiments of the present invention herein provides a hypothetical example of several modes of operation that are based on using a mini-encryption function, which will typically be denoted herein as e. These include ePBC, xePBC, CS-PBC, and eCTR.

Published PCT application 2006/117775 of NDS Ltd. and corresponding granted US patent 7,940,930 of Shen-Orr et al. describes a system for scrambling / descrambling packets of a stream of content, each packet having a must stay clear (MSC) section, the system including an input handler including a receiving module to receive the stream, a characteristic analyzer to analyze the stream in order to determine a data independent characteristic of each packet, and a scrambling / descrambling device operationally associated with the input handler, the scrambling / descrambling device including a receiving module to receive the data independent characteristic for each packet from the input handler, and an Initial Value module to determine an Initial Value for each packet as a function of the data independent characteristic of one of the packets being processed, wherein the scrambling / descrambling device is adapted to scramble and/or descramble the packets based on the Initial Value and a Control Word.

SUMMARY OF THE INVENTION

The present invention, in certain embodiments thereof, seeks to provide an improved method of using block cipher encryption which is not susceptible to malleability attacks.

There is thus provided in accordance with another embodiment of the present invention method for producing at least one ciphertext block from at least one plaintext block using a block cipher, the block cipher comprising an encryption function Enc, the method including receiving n plaintext blocks, wherein n is an integer greater than 0, for each plaintext block of the n plaintext blocks inputting two inputs into a keyed invertible transformation function, e, the two inputs including a masking value, denoted Mi, where 0 < i <= n, and one of a plaintext block, denoted Pi, Pi being an i-th plaintext block of the n plaintext blocks, and a function of the plaintext block Pi, where 0 < i <= n, wherein one of the two inputs i and Pi includes a key for round key generation by the function e and the second of the two inputs Mj and Pi includes a data item operated on during rounds of function e, outputting a result of the function e, the output being at least partially encrypted in a case where the masking value includes an output of the encryption function Enc, the output of the function e includes a ciphertext block, thereby producing n ciphertext blocks, in a case where the masking value includes one of one of Pi_i, and an initialization vector when i =1, and one of a function of Pi_i, and an initialization vector when i =1, the output of the function e includes an input into the encryption function EllC, and the output of the function Enc includes a ciphertext block, thereby producing n ciphertext blocks, and in a case where the masking value includes one of an output of the function e(Mi_j , Pi-i), and an initialization vector when i =1, the input into the function Enc includes a result of xor-ing the masking value Mj with Pi, and the output of the function EllC includes a ciphertext block, thereby producing n ciphertext blocks. There is further provided in accordance with another embodiment of the present invention a method for producing at least one ciphertext block from at least one plaintext block using a block cipher, the block cipher comprising an encryption function EllC, the method including receiving n plaintext blocks, wherein n is an integer greater than 0, for each plaintext block of the n plaintext blocks computing an output of a function e, the output being e(M[, P), and computing Έΐίθ(β(Μ _ί, Pj ) according to a key of the block cipher, thereby producing n ciphertext blocks, wherein function e includes a keyed invertible transformation function, 0 l, and an initialization vector for i=l.

Further in accordance with an embodiment of the present invention function e includes a plurality of rounds of a second block cipher encryption or decryption function.

Still further in accordance with an embodiment of the present invention function e includes 3 rounds of the second block cipher encryption function.

Additionally in accordance with an embodiment of the present invention a round key generation algorithm of function e includes one of the round key generation algorithm of the second block cipher encryption function, and an non-standard derivation algorithm.

Moreover in accordance with an embodiment of the present invention the non-standard derivation algorithm includes xor-ing a key with round constants.

Further in accordance with an embodiment of the present invention the round function of function e includes one of the round key generation algorithm of the second block cipher encryption function, and a tweaked block cipher round function. Still further in accordance with an embodiment of the present invention the tweaked block cipher round function includes any of pseudo-random tables, pseudo-random s-boxes, and pseudo-random p-boxes.

There is also provided in accordance with still another embodiment of the present invention a method for producing at least one plaintext block from at least one ciphertext block using a block cipher, the block cipher including and decryption function Dec, the method including receiving n ciphertext blocks, wherein n is an integer greater than 0, for each ciphertext block of the n ciphertext blocks computing an output of the function Dec, the output being Dec(Cj), according to a key of the block cipher, and computing e ¹ (Mi,Dec( Cj)), thereby producing n plaintext blocks, wherein function e ^ includes a keyed invertible transformation function, 0 l, and an initialization vector for M , and _; denoting an i-th plaintext block of the n plaintext blocks.

Further in accordance with an embodiment of the present invention function e ¹ includes a plurality of rounds of a second block cipher encryption function.

Still further in accordance with an embodiment of the present invention function e ¹ includes 3 rounds of a second block cipher encryption function.

Additionally in accordance with an embodiment of the present invention a round key generation algorithm of function e ¹ includes one of the round key generation algorithm of the second block cipher encryption function, and an non-standard derivation algorithm.

Moreover in accordance with an embodiment of the present invention the non-standard derivation algorithm includes xor-ing a key with round constants. Further in accordance with an embodiment of the present invention the round function of function e ¹ includes one of the round key generation algorithm of the second block cipher encryption function, and a tweaked block cipher round function.

Still further in accordance with an embodiment of the present invention the tweaked block cipher round function includes any of pseudo-random tables, pseudo-random s-boxes, and pseudo-random p-boxes.

Additionally in accordance with an embodiment of the present invention the function e ¹ includes the inverse of function e.

There is also provided in accordance with still another embodiment of the present invention a method for producing at least one ciphertext block from at least one plaintext block using a block cipher, the block cipher including and encryption function Enc, the method including receiving n plaintext blocks, wherein n is an integer greater than 0, for each plaintext block of the n plaintext blocks computing an output of a function e, the output being e(Mi, Pj), and computing Enc( ; © Mj) according to a key of the block cipher, thereby producing n ciphertext blocks, wherein function e includes a keyed invertible transformation function, 0 1, and an initialization vector for i=l.

Further in accordance with an embodiment of the present invention function e includes a plurality of rounds of a second block cipher encryption function.

Still further in accordance with an embodiment of the present invention function e includes 3 rounds of the second block cipher encryption function.

Additionally in accordance with an embodiment of the present invention wherein a round key generation algorithm of function e includes one of the round key generation algorithm of the second block cipher encryption function, and an non-standard derivation algorithm.

Moreover in accordance with an embodiment of the present invention the non-standard derivation algorithm includes xor-ing a key with round constants.

Still further in accordance with an embodiment of the present invention the tweaked block cipher round function includes any of pseudo-random tables, pseudo-random s-boxes, and pseudo-random p-boxes.

There is also provided in accordance with another embodiment of the present invention a method for producing at least one plaintext block from at least one ciphertext block using a block cipher, the block cipher including and decryption function Dec, the method including receiving n ciphertext blocks, wherein n is an integer greater than 0, for each ciphertext block of the n ciphertext blocks computing (M( φ Dec(Ci)) according to a key of the block cipher, thereby producing n plaintext blocks, wherein function e includes a keyed invertible transformation function, 0 1, and an initialization vector for i=l, _z- denoting an i-th plaintext block of the n plaintext blocks.

Further in accordance with an embodiment of the present invention function e includes a plurality of rounds of a second block cipher encryption function.

Still further in accordance with an embodiment of the present invention function e includes 3 rounds of the second block cipher encryption function. Additionally in accordance with an embodiment of the present invention a round key generation algorithm of function e includes one of the round key generation algorithm of the second block cipher encryption function, and an non-standard derivation algorithm.

Moreover in accordance with an embodiment of the present invention the non-standard derivation algorithm includes xor-ing a key with round constants.

Still further in accordance with an embodiment of the present invention the tweaked block cipher round function includes any of pseudo-random tables, pseudo-random s-boxes, and pseudo-random p-boxes.

There is also provided in accordance with still another embodiment of the present invention a method for producing at least one ciphertext block from at least one plaintext block using a block cipher, the block cipher including and encryption function Enc, the method including receiving n plaintext blocks, wherein n is an integer greater than 0, for each plaintext block of the n plaintext blocks computing an output of a function β, the output being e(M _it Pj), and computing Έΐίθ(β(Μ _ί, PJ) according to a key of the block cipher, thereby producing n ciphertext blocks, wherein function e includes a keyed invertible transformation function, 0 l, and an initialization vector for i=l, where CS denotes a shrinking function, and xTend denotes a function which extends an output of the CS function into a value of an original block length.

Further in accordance with an embodiment of the present invention the shrinking function includes a checksum function. Still further in accordance with an embodiment of the present invention the shrinking function outputs an output of 1 - 3 bytes long.

Additionally in accordance with an embodiment of the present invention the xTend function extends the output of the CS function with a fixed vector.

Moreover in accordance with an embodiment of the present invention the xTend function extends the output of the CS function by repeating the output of the CS function in order to extend the output to a fixed length.

Further in accordance with an embodiment of the present invention the xTend function includes a lookup table, and the output of the CS function includes an index of the lookup table.

Still further in accordance with an embodiment of the present invention function e includes a plurality of rounds of a second block cipher encryption function.

Additionally in accordance with an embodiment of the present invention function e includes 3 rounds of the second block cipher encryption function.

Moreover in accordance with an embodiment of the present invention a round key generation algorithm of function e includes one of the round key generation algorithm of the second block cipher encryption function, and an non-standard derivation algorithm.

Further in accordance with an embodiment of the present invention the non-standard derivation algorithm includes xor-ing a key with round constants.

Still further in accordance with an embodiment of the present invention the round function of function e includes one of the round key generation algorithm of the second block cipher encryption function, and a tweaked block cipher round function.

Additionally in accordance with an embodiment of the present invention the tweaked block cipher round function includes any of pseudo-random tables, pseudo-random s-boxes, and pseudo-random p-boxes. There is also provided in accordance with still another embodiment of the present invention a method for producing at least one plaintext block from at least one ciphertext block using a block cipher, the block cipher including and decryption function Dec, the method including receiving n ciphertext blocks, wherein n is an integer greater than 0, for each ciphertext block of the n ciphertext blocks computing an output of the function Dec, the output being Dec(Cj), according to a key of the block cipher, computing e ¹ (Mi, Dec(Ci)), thereby producing n plaintext blocks, wherein function e ¹ includes a keyed invertible transformation function, 0 l, and an initialization vector for i=l, where CS denotes a shrinking function, and xTend denotes a function which extends an output of the CS function into a value of an original block length.

Further in accordance with an embodiment of the present invention the shrinking function includes a checksum function.

Still further in accordance with an embodiment of the present invention the shrinking function outputs an output of 1 - 3 bytes long.

Additionally in accordance with an embodiment of the present invention the xTend function extends the output of the CS function with a fixed vector.

Further in accordance with an embodiment of the present invention the xTend function includes a lookup table, and the output of the CS function includes an index of the lookup table.

Still further in accordance with an embodiment of the present invention function e ¹ includes a plurality of rounds of a second block cipher encryption function. Additionally in accordance with an embodiment of the present invention function e ¹ includes 3 rounds of the second block cipher encryption function.

Moreover in accordance with an embodiment of the present invention a round key generation algorithm of function e ¹ includes one of the round key generation algorithm of the second block cipher encryption function, and a non-standard derivation algorithm.

Further in accordance with an embodiment of the present invention non-standard derivation algorithm includes xor-ing a key with round constants.

Still further in accordance with an embodiment of the present invention the round function of function e ¹ includes one of the round key generation algorithm of the second block cipher encryption function, and a tweaked block cipher round function.

Additionally in accordance with an embodiment of the present invention the tweaked block cipher round function includes any of pseudo-random tables, pseudo-random s-boxes, and pseudo-random p-boxes.

Moreover in accordance with an embodiment of the present invention the function e ¹ includes the inverse of function e.

Mi denotes a masking value. Further in accordance with an embodiment of the present invention function e includes a plurality of rounds of a second block cipher encryption function.

Still further in accordance with an embodiment of the present invention function e includes 3 rounds of the second block cipher encryption function.

Moreover in accordance with an embodiment of the present invention the non-standard derivation algorithm includes xor-ing a key with round constants.

Still further in accordance with an embodiment of the present invention the tweaked block cipher round function includes any of pseudo-random tables, pseudo-random s-boxes, and pseudo-random p-boxes.

Additionally in accordance with an embodiment of the present invention IV i = IV + i - 1.

There is also provided in accordance with still another embodiment of the present invention a method for producing at least one plaintext block from at least one ciphertext block using a block cipher, the block cipher including and encryption function EllC, the method including receiving n ciphertext blocks, wherein n is an integer greater than 0, for each ciphertext block of the n ciphertext blocks computing Mi = Enc(/K^ according to a key of the block cipher, computing e ¹ (M^ C[) thereby producing n plaintext blocks, wherein function e ¹ includes a plurality of rounds of a keyed invertible transformation function, 0 < i <= n, C denotes an i-th ciphertext block of the n ciphertext blocks, IV i denotes an initialization vector, and A _;- denotes a masking value.

Further in accordance with an embodiment of the present invention function e ¹ includes a plurality of rounds of a second block cipher encryption function.

Still further in accordance with an embodiment of the present invention function e ¹ includes 3 rounds of the second block cipher encryption function.

Moreover in accordance with an embodiment of the present invention the non-standard derivation algorithm includes xor-ing a key with round constants.

Further in accordance with an embodiment of the present invention the round function of function e ¹ includes one of the round key generation algorithm of the second block cipher encryption function, and a tweaked block cipher round function.

Still further in accordance with an embodiment of the present invention the tweaked block cipher round function includes any of pseudo-random tables, pseudo-random s-boxes, and pseudo-random p-boxes.

Additionally in accordance with an embodiment of the present invention IV i = IV+ i - 1.

Moreover in accordance with an embodiment of the present invention the function e ¹ includes the inverse of function.

There is also provided in accordance with still another embodiment of the present invention an apparatus for producing at least one ciphertext block from at least one plaintext block using a block cipher, the block cipher including an encryption function Enc, the apparatus including a receiving unit for receiving n plaintext blocks, wherein n is an integer greater than 0, an initialization unit operative to set an initialization vector equal to an initial value, a computation unit operative, for each plaintext block of the n plaintext blocks to compute an output of a function e, the output being e(Mj, Pi), and to compute ΈΐΙθ β(Μ _ί, PJ) according to a key of the block cipher, thereby producing n ciphertext blocks, wherein function e includes a keyed invertible transformation function, 0 < i <= n,

Pi denotes an i-th plaintext block of the n plaintext blocks, and Mi denotes a masking value, the masking value being P^ for i>l, and the initialization vector for i=l.

There is also provided in accordance with still another embodiment of the present invention an apparatus for producing at least one plaintext block from at least one ciphertext block using a block cipher, the block cipher including and decryption function Dec, the apparatus including a receiving unit for receiving n plaintext blocks, wherein n is an integer greater than 0, an initialization unit operative to set an initialization vector equal to an initial value, a computation unit operative, for each plaintext block of the n plaintext blocks to compute an output of the function Dec, the output being Dec( Ci), according to a key of the block cipher, and to compute e ¹ (Mi,Dec(Ci)), thereby producing n plaintext blocks, wherein function e ¹ includes a keyed invertible transformation function, 0 l, and the initialization vector for M], and Pi denoting an i-th plaintext block of the n plaintext blocks.

There is also provided in accordance with still another embodiment of the present invention an apparatus for producing at least one ciphertext block from at least one plaintext block using a block cipher, the block cipher including and encryption function Enc, the apparatus including a receiving unit for receiving n plaintext blocks, wherein n is an integer greater than 0, an initialization unit operative to set an initialization vector equal to an initial value, a computation unit operative, for each plaintext block of the n plaintext blocks to compute an output of a function e, the output being e(Mj, P), and to compute Enc(P _z φ

Mj) according to a key of the block cipher, thereby producing n ciphertext blocks, wherein function e includes a keyed invertible transformation function, 0 1, and the initialization vector for i= 1.

There is also provided in accordance with still another embodiment of the present invention an apparatus for producing at least one plaintext block from at least one ciphertext block using a block cipher, the block cipher including and decryption function Dec, the apparatus including a receiving unit for receiving n ciphertext blocks, wherein n is an integer greater than 0, an initialization unit operative to set an initialization vector equal to an initial value, a computation unit operative, for each ciphertext block of the n ciphertext blocks to compute (Mi φ Dec(Ci)) according to a key of the block cipher, thereby producing n plaintext blocks, wherein function e includes a keyed invertible transformation function, 0 < i <= n, C _z- denotes an i-th ciphertext block of the n ciphertext blocks, and denotes a masking value, the masking value being e(Pi.

I, Mi.]) for i > 1, and the initialization vector for i=l, _; denoting an i-th plaintext block of the n plaintext blocks.

There is also provided in accordance with still another embodiment of the present invention an apparatus for producing at least one ciphertext block from at least one plaintext block using a block cipher, the block cipher including and encryption function EllC, the apparatus including a receiving unit for receiving n plaintext blocks, wherein n is an integer greater than 0, an initialization unit operative to set an initialization vector equal to an initial value, a computation unit operative, for each plaintext block of the n plaintext blocks to compute an output of a function e, the output being e(Mi, P), and to compute Enc(e(¾f _;, P _jf) according to a key of the block cipher, thereby producing n ciphertext blocks, wherein function e includes a keyed invertible transformation function, 0 < i <= n,

Pi denotes an i-th plaintext block of the n plaintext blocks, and M^ denotes a masking value, the masking value being xTend(CS(Pi. )) for i>l, and the initialization vector for i=l, where CS denotes a shrinking function, and xTend denotes a function which extends an output of the CS function into a value of an original block length.

There is also provided in accordance with still another embodiment of the present invention an apparatus for producing at least one plaintext block from at least one ciphertext block using a block cipher, the block cipher including and decryption function Dec, the apparatus including a receiving unit for receiving n ciphertext blocks, wherein n is an integer greater than 0, an initialization unit operative to set an initialization vector equal to an initial value, a computation unit operative, for each ciphertext block of the n ciphertext blocks to compute an output of the function Dec, the output being Dec(Ci), according to a key of the block cipher, to compute e ¹ (M^, Dec(Cj)), thereby producing n plaintext blocks, wherein function e ¹ includes a keyed invertible transformation function, 0 l, and the initialization vector for i=l, where CS denotes a shrinking function, and xTend denotes a function which extends an output of the CS function into a value of an original block length.

There is also provided in accordance with still another embodiment of the present invention an apparatus for producing at least one ciphertext block from at least one plaintext block using a block cipher, the block cipher including and encryption function Enc, the apparatus including a receiving unit for receiving n plaintext blocks, wherein n is an integer greater than 0, an initialization unit operative to set an initialization vector equal to an initial value, a computation unit operative, for each plaintext block of the n plaintext blocks to compute M^ = Enc(/K _j according to a key of the block cipher, and to compute e(M _it Pj), thereby producing n ciphertext blocks, wherein function e includes a keyed invertible transformation function, 0 < i <= n, Pi denotes an i-th plaintext block of the n plaintext blocks, IVi denotes an initialization vector, and Mi denotes a masking value.

There is also provided in accordance with still another embodiment of the present invention an apparatus for producing at least one plaintext block from at least one ciphertext block using a block cipher, the block cipher including and encryption function Enc, the apparatus including a receiving unit for receiving n plaintext blocks, wherein n is an integer greater than 0, an initialization unit operative to set an initialization vector equal to an initial value, a computation unit operative, for each ciphertext block of the n ciphertext blocks to compute Mi = Enc(/K^) according to a key of the block cipher, to compute e ¹ (Mi, Cj) thereby producing n plaintext blocks, wherein function e ¹ includes a plurality of rounds of a keyed invertible transformation function, 0 < i <= n, _; denotes an i-th ciphertext block of the n ciphertext blocks, IV denotes the initialization vector, and Mi denotes a masking value.

BRIEF DESCRIPTION OF THE DRAWINGS

Embodiments of the present invention will be understood and appreciated more fully from the following detailed description, taken in conjunction with the drawings in which:

Fig. 1 is a simplified block diagram illustration of a generalized block cipher (prior art);

Fig. 2 is a simplified block diagram illustration of a block cipher usage implementing an ePBC mode of operation, constructed and operative in accordance with an embodiment of the present invention;

Fig. 3 is a simplified block diagram illustration of a block cipher usage implementing an xePBC mode of operation, constructed and operative in accordance with an embodiment of the present invention;

Fig. 4 is a simplified block diagram illustration of a block cipher usage implementing an CS-ePBC mode of operation, constructed and operative in accordance with an embodiment of the present invention;

Fig. 5 is a simplified block diagram illustration of a block cipher usage implementing an eCTR mode of operation, constructed and operative in accordance with an embodiment of the present invention;

Fig. 6 is a simplified block diagram illustration of an implementation of function e of Figs. 2 - 5; and

Figs. 7 - 14 are simplified flowchart diagrams of preferred methods of operation of the systems described in Figs. 2 - 5.

DETAILED DESCRIPTION OF AN EMBODIMENT

Reference is now made to Figs. 2 - 5, which are simplified block diagram illustrations of various modes of operation for block ciphers, the block diagram illustrations being drawn in a form that will be understood by persons of skill in the art. Specifically, Fig. 2 is a block diagram illustration of a block cipher usage implementing an ePBC mode of operation, constructed and operative in accordance with an embodiment of the present invention. Fig. 3 is a simplified block diagram illustration of a block cipher usage implementing an xePBC mode of operation, constructed and operative in accordance with an embodiment of the present invention. Fig. 4 is a simplified block diagram illustration of a block cipher usage implementing an CS-ePBC mode of operation, constructed and operative in accordance with an embodiment of the present invention. Fig. 5 is a simplified block diagram illustration of a block cipher usage implementing an eCTR mode of operation, constructed and operative in accordance with an embodiment of the present invention.

As was noted above, each of the block ciphers described herein are implementing a mode of operation that is based on using a mini-encryption function, denoted e. As a non-limiting example, in Fig. 2, the block e receives plain text inputs and either a plain text input from a previous activation of the block cipher, or, in the first activation of the block cipher, an initialization vector.

Turning to the implementation of the mode of operation described herein with reference to Fig. 2, the ePBC mode of operation is similar to the well known Plaintext-Block-Chaining (PBC) mode of operation. However, the exclusive-or (XOR) operation used in PBC is replaced with the function e. The implementation of the function e is discussed below with reference to Fig. 6.

With regard to Figs. 2 - 5, those skilled in the art will appreciate that the discussion herein is symmetrical, with respect to encryption and decryption. Hence, although the present discussion focuses primarily on the use of the function e in the context of encryption, this is solely for the sake of ease of discussion, and in no way is meant to be limiting. Rather, the lack of discussion of decryption is due to the symmetric nature of encryption / decryption in block ciphers. Turning to the implementation of the mode of operation described herein with reference to Fig. 3, the xePBC mode of operation is similar to the well known Plaintext-Block-Chaining (PBC) mode of operation. During encryption, the initialization vector (IV) and the plaintext blocks are used by the function e to generate a sequence of masking blocks M _l5 M ₂, M ₃, ...to be masked (XOR-ed) with the plaintext prior to encryption.

The masking block M; for plaintext block P; is a function of the IV and all precious plaintext blocks, P _x, ..., P^.

Despite the dependency on previous blocks, the desired property of parallelized decryption is fulfilled because the main decryption operation, that is to say, the block decryption, can run in parallel for all blocks independently and only resolution of the masking values (i.e., the computationally lighter operation) should run sequentially.

Turning to the implementation of the mode of operation described herein with reference to Fig. 4, the CS-ePBC mode of operation comprises, in addition to the ePBC mode described above, a CS (checksum) module. The CS module shrinks the previous plaintext value (i.e. the chaining value) into a small size, for example and without limiting the generality of the foregoing, by performing a checksum operation on the previous plaintext value (for example a byte checksum or a CRC). (It is understood that the phrase, "a small size" refers to a size which is smaller than the size of the plaintext block.) Typically, the plaintext value is shrunk to a size that ranges between 1 - 3 bytes.

The xTend module extends the result of the CS module (the checksum) into a value of the original block length, for example and without limiting the generality of the foregoing, by circular usage of the checksum bytes to the required length, or by padding with a fixed vector. The xTend module might work in a fashion as is known in the art. For example and without limiting the generality of the foregoing, the xTend module may pad the output of the CS module with a fixed vector, such as adding 13 bytes of all zeros to a 3 byte shrunken plaintext.

Alternatively, the xTend module may repeat the output of the CS module to extend the value to the full length. For example and without limiting the generality of the foregoing, if the output of the CS module is 2 bytes in length, the xTend module may repeat those two bytes an additional seven times, in order to achieve a 16 byte block.

Alternatively, the xTend module may use the output of the CS module as an index for a lookup table (i.e. an S-box). So, an output of the CS module may comprise a 1 - 3 byte output, as was noted above. The result of the lookup is a 16 byte output which is input into the function e.

The rationale for using the CS and xTend modules is to facilitate random access in the decryption environment through trial and error of the shrunken chaining value. The number of potential chaining values (outputted from the xTend module) is thus 2 ^L (L being the checksum length) and for small enough L (e.g., 16 bits) the masking value can be found through trial and error of only 2 ^L trials (65536 in the example). The decryptor tries to calculate the plaintext message using each of the 2 ^L possible values of CS(P _i_ ₁) until the decryptor recognizes that the resultant P _; is the correct Pj.

Turning to the implementation of the mode of operation described herein with reference to Fig. 5, the eCTR mode of operation is similar to the well known Counter (CTR) mode of operation. In the eCTR mode of operation, the XOR function is replaced with the e function.

Reference is now made to Fig. 6, which is a simplified block diagram illustration of an implementation of function e of Figs. 2 - 5. As was noted above, the function e is a mini-encryption function that breaks trivial patterns in the processed data but does not necessarily have cryptographic strength. The function e uses two inputs: a first input comprising a data item and a second input comprising a key.

The function e produces an output.

The function e is a keyed invertible transformation which means that for a fixed key k there is an inverse function e ^"1 for which the following holds for every x: e ^_1(k, e(k,x)) = e(k, e ^_1(k,x)) = x .

The function e need not be a cryptographically secure function, but rather a 'light' scrambling function that breaks trivial patterns in the sequence of the masking values. The function e can have various implementations. For example and without limiting the generality of the foregoing, a small number of rounds, say 3, of a block cipher, such as AES, DES, Serpent, Skipjack, with a simple round keys generation.

The round key generation algorithm can be either the 'regular' block cipher round key generation algorithm (that is to say the key expansion or key scheduling of the implemented block cipher), or a different trivial derivation algorithm, such as XOR-ing the key with round constants.

For example and without limiting the generality of the foregoing, one implementation of the round key generation algorithm for e that uses 3 rounds of a block cipher using 16-byte round keys might be:

RoundKeyGeneration(k) :

Kl - K Θ 0x93FDDA10D3F8E4F0C5919ECBCA2BB073 K2 - K Θ 0x0E34C707BE75338BF13558EDD2B40293 K3 r K Θ 0x9F758C53D926BEF21FC90A83AC73E42B

Return Kl, K2, K3.

The round function can be implemented as the round function of any known block cipher, as was noted above. The round function can be either the

"regular" block cipher round function, or a tweaked block cipher round function.

For example, letting:

TO, Tl, T2, T3 be fast AES tables (each including 256 4-byte values)

and letting:

P0, PI, P2, P15 be [0,5,10,15,4,9,14,3,8,13,2,7,12,1,6,11] (the AES ShiftRows permutation),

the AES round function looks as follows:

AesRound (S, RK):

For i in 0..4:

Return S

For example, letting:

TO, Tl, T2, T3 be some pseudo random tables (each including 256 4-byte values) and letting:

PO, PI, P2, P15 be some pseudo random permutation of

0..15

a tweaked AES round function will be:

AesTweakedRound (S, RK):

For i in 0..4:

Return S

Referring once again to Fig. 2:

Referring once again to Fig. 3:

For the encryption side, in each activation of the block cipher encryption function, the plaintext block is xor-ed with the masking value before being input into the block cipher encryption function. The masking value is also processed by the function e in order to produce the masking value for the next activation of the block cipher. The plaintext block is used as the key for the function e (or an initialization vector IV in the case of the first block) for the next activation of the block cipher.

For decryption side, in each activation of the block cipher decryption function, the ciphertext is decrypted in the block cipher and then is processed by being xor-ed with the masking value. The result of the xor-ing is the plaintext. The masking value is processed by the function e in order to produce the masking value for the next activation of the block cipher. The plaintext block (or an initialization vector IV in the case of the first block) is used as the key for the function e for the next activation of the block cipher.

Referring once again to Fig. 4:

For the encryption side, in every activation of the block cipher encryption function, the plaintext block is processed through the function e before being input into the block cipher encryption function. The function e uses the masking value as the key, the masking value being the result of inputting the plaintext from the previous activation of the block cipher into a checksum module, and then an xTend module which extends the result of the CS module (the checksum) into a value of the original block length. In the case of the first activation of the block cipher, an initialization vector IV is used as the masking value.

For the decryption side, in every activation of the block cipher decryption function, the ciphertext block is decrypted in the block cipher and then is processed through the function e ^"1 (the inverse of e). The function e uses the masking value as the key, the masking value being the result of inputting the plaintext resulting from decrypting the ciphertext from the previous activation of the block cipher decryption function into a checksum module. The result of the checksum module is then input into the xTend module which extends the result of the CS module (the checksum) into a value of the original block length. In the case of the first activation of the block cipher, an initialization vector IV is used as the masking value. Those skilled in the art will appreciate that for the embodiments of e discussed above, e ¹, the inverse of e, is trivially derived.

Referring once again to Fig. 5:

For the encryption side, in every activation of the block cipher encryption function, the plaintext block is processed through the function e. The function e uses the masking value as the key, the masking value being the output of the block cipher encryption function. Instead of encrypting the plaintext block, the block cipher encryption function encrypts an initialization vector IV. In each activation of the block cipher, the initialization vector IV is incremented. For the decryption side, in every block decryption operation, the block cipher encryption function encrypts an initialization vector IV. In each activation of the block cipher, the initialization vector IV is incremented. The ciphertext is processed through the function e ^"1 (the inverse of e), with the function e using the masking value as the key, the masking value being the output of the block function encryption function. Those skilled in the art will appreciate that for the embodiments of e discussed above, e ^"1, the inverse of e, is trivially derived.

Those skilled in the art will appreciate that the function e can be implemented in other manners than those described here. For example and without limiting the generality of the foregoing, (not depicted):

For the encryption side, in every activation of the block cipher encryption function, the plaintext block is processed through the function e before being input into the block cipher encryption function. The function e uses the masking value as the key, the masking value being the output of the function e from the previous activation of the block cipher. In the case of the first block, the function e can operate on the initialization vector IV as though it were both the plaintext block and the masking value. The plaintext is xor-ed with the masking value prior to being input into the block cipher encryption function.

For the decryption side, in every activation of the block cipher decryption function, the ciphertext block is decrypted in the block cipher and then is xor-ed with the masking value. The result of the xor-ing is output as the plaintext. The plaintext block is processed through the function e, using the masking value as the key, where the input masking value comprises the output of the function e from the previous activation of the block cipher. In the case of the first block, the function e can operate on the initialization vector IV as though it were both the plaintext block and the masking value.

Those skilled in the art will appreciate that other modes of operation which utilize the function e may be implemented as well.

Reference is now made to Figs. 7 - 14, which are simplified flowchart diagrams of preferred methods of operation of the systems described in Figs. 2 - 5. The systems and methods of Figs. 7 - 14 are believed to be self explanatory in light of the above discussion. It is appreciated that software components of the present invention may, if desired, be implemented in ROM (read only memory) form. The software components may, generally, be implemented in hardware, if desired, using conventional techniques. It is further appreciated that the software components may be instantiated, for example: as a computer program product; on a tangible medium; or as a signal interpretable by an appropriate computer.

It is appreciated that various features of the invention which are, for clarity, described in the contexts of separate embodiments may also be provided in combination in a single embodiment. Conversely, various features of the invention which are, for brevity, described in the context of a single embodiment may also be provided separately or in any suitable subcombination.

It will be appreciated by persons skilled in the art that the present invention is not limited by what has been particularly shown and described hereinabove. Rather the scope of the invention is defined by the appended claims and equivalents thereof:

Previous Patent: DISPOSABLE PROTECTIVE FOOTWEAR COVER

Next Patent: METHOD TO ESTIMATE INTERFRACTIONAL AND INTRAFRACTIONAL ORGAN MOTION FOR ADAPTIVE EXTERNAL BEAM RADIO...