Method and apparatus for advanced byte-oriented symmetric key block cipher with variable length key and block

• US 6,192,129 B1
• Filed: 02/04/1998
• Issued: 02/20/2001
• Est. Priority Date: 02/04/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Zunic, Nevenko, Safford, David Robert, Halevi, Shai, Jutla, Charanjit S., Coppersmith, Don, Matyas, Stephen M. Jr., Gennaro, Rosario, Peyravian, Mohammed
• Primary Examiner(s): BARRON JR, GILBERTO
• Application Number:
  US09/018,630
• Time in Patent Office: 1,112 Days
• Field of Search: 380/29, 380/37, 380/259, 380/264, 380/265
• US Class Current: 380/259
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• 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

Abstract

A method and apparatus for an advanced byte-oriented symmetric key cipher for encryption and decryption, using a block cipher algorithm. Different block sizes and key sizes are supported, and a different sub-key is used in each round. Encryption is computed using a variable number of rounds of mixing, permutation, and key-dependent substitution. Decryption uses a variable number of rounds of key-dependent inverse substitution, inverse permutation, and inverse mixing. The variable length sub-keys are data-independent, and can be precomputed.

Claims

1. In a computing environment, computer-readable code for providing a byte-oriented symmetric key block cipher which supports a variable length symmetric input key, a variable length block, and a variable number of rounds, said computer-readable code embodied on a computer-readable medium and comprising:

computer-readable program code means for determining a number of rounds of cipher processing to use as said variable number of rounds, a key length of said variable length symmetric input key, and a block length of said variable length block;

computer-readable program code means for generating a plurality of sub-keys using said symmetric input key as an input value, wherein each of said generated sub-keys is equal in length to said block length and where a distinct one of said sub-keys is generated for each of said number of rounds;

computer-readable program code means for obtaining an input data block to be encrypted, wherein said input data block comprises a plurality of input data bytes, said plurality being equal in number to said block length; and

computer-readable program code means for iteratively performing a set of round functions a number of times equal to said number of rounds in order to encrypt said input data block, wherein said set of round functions comprises a mixing function, a permuting function, and a key-dependent substitution function, and wherein said computer-readable program code means for iteratively performing further comprises;

computer-readable program code means for performing said mixing function by mixing each of said input data bytes using a first XOR operation and a second XOR operation, wherein said first and second XOR operations are different, followed by a first substitution-box (S-box) lookup operation, thereby creating a plurality of mixed bytes;

computer-readable program code means for performing said permuting function by swapping each of said mixed bytes, thereby creating a plurality of permuted bytes;

computer-readable program code means for performing said key-dependent substitution function by substituting a byte value for each of said permuted bytes, wherein said byte value is determined by performing a third XOR operation followed by a second S-box lookup operation, thereby creating a plurality of substituted bytes; and

computer-readable program code means for treating said plurality of substituted bytes as said plurality of input data bytes for a subsequent iteration of said computer-readable program code means for iteratively performing, provided said number of times has not been reached.

2. The computer-readable code according to claim 1, wherein said computer-readable program code means for performing said mixing function further comprises:

computer-readable program code means for dividing said plurality of input data bytes into a left input half and a right input half;

computer-readable program code means for performing a first mixing operation on said left input half and a second mixing operation on said right input half, wherein said second mixing operation uses a different selection of operands for said first and second XOR operations than does said first mixing operation;

computer-readable program code means for using each byte of a result of said second XOR operation of said first mixing operation as a lookup index for said first S-box lookup operation to retrieve bytes of a new left half; and

computer-readable pro=am code means for using each byte of an output of said second XOR operation of said second mixing operation as said lookup index for said first S-box lookup operation to retrieve bytes of a new right half.

3. The computer-readable code according to claim 2, wherein:

said computer-readable program code means for performing said first mixing operation further comprises;

computer-readable program code means for using an identically-numbered byte from said left input half and said right input half as operands of said first XOR operation; and

computer-readable program code means for using a result of said first XOR operation and a byte from said right input half that has been effectively rotated right one byte as operands of said second XOR operation; and

said computer-readable program code means for performing said second mixing operation further comprises;

computer-readable program code means for using a selected byte from said right input half and a previously-mixed byte from said new left half that has been effectively rotated right one byte as operands of said first XOR operation; and

computer-readable program code means for using an output of said first XOR operation and a different previously-mixed byte from said new left half that has been effectively rotated left two bytes as operands of said second XOR operation.

4. The computer-readable code according to claim 1, wherein said computer-readable program code means for performing said mixing function and said computer-readable program code means for performing said key-dependent substitution function perform said first S-box lookup operation and said second S-box lookup operational, respectively, by accessing a selected one of two distinct S-boxes using a one-byte index, each of said S-boxes having 256 distinct entries, each of said entries being a one-byte value.

5. The computer-readable code according to claim 1, wherein one or more of said computer-readable program code means is embodied in a hardware chip.

6. The computer-readable code according to claim 1, wherein said computer-readable program code means for performing said permuting function further comprises:

computer-readable program code means for dividing said plurality of mixed bytes into a left mixed half and a right mixed half; and

computer-readable program code means for swapping said left mixed half with said right mixed half.

7. The computer-readable code according to claim 1, wherein said computer-readable program code means for performing said key-dependent substitution function further comprises:

computer-readable program code means for using a sub-key byte from a selected one of said generated sub-keys which is uniquely associated with said round as an operand of said third XOR operation, along with said each permuted byte; and

computer-readable program code means for performing said second S-box lookup operation using each byte of a result of said third XOR operation as an index.

8. The computer-readable code according to claim 1, wherein particular values of one or more of said number of rounds, said key length, and said block length are determined in advance in order to optimize said computer-readable code, and wherein said computer-readable program code means for determining therefore operates as if said one or more particular values are fixed.

9. The computer-readable code according to claim 1, further comprising:

computer-readable program code means for decrypting said encrypted data block, resulting in restoration of said plurality of input data bytes, by performing a set of inverse round functions said number of times equal to said number of rounds, wherein said set of inverse round functions comprises an inverse key-dependent substitution function which is inverse to said key-dependent substitution function, an inverse permuting function which is inverse to said permuting function, and an inverse mixing function which is inverse to said mixing function.

10. A system for providing a byte-oriented symmetric key block cipher which supports a variable length symmetric input key, a variable length block, and a variable number of rounds, comprising:

means for determining a number of rounds of cipher processing to use as said variable number of rounds, a key length of said variable length symmetric input key, and a block length of said variable length block;

means for generating a plurality of sub-keys using said symmetric input key as an input value, wherein each of said generated sub-keys is equal in length to said block length and where a distinct one of said sub-keys is generated for each of said number of rounds;

means for obtaining an input data block to be encrypted, wherein said input data block comprises a plurality of input data bytes, said plurality being equal in number to said block length; and

means for iteratively performing a set of round functions a number of times equal to said number of rounds in order to encrypt said input data block, wherein said set of round functions comprises a mixing function, a permuting function, and a key-dependent substitution function, and wherein said means for iteratively performing further comprises;

means for performing said mixing function by mixing each of said input data bytes using a first XOR operation and a second XOR operation, wherein said first and second XOR operations are different, followed by a first substitution-box (S-box) lookup operation, thereby creating a plurality of mixed bytes;

means for performing said permuting function by swapping each of said mixed bytes, thereby creating a plurality of permuted bytes;

means for performing said key-dependent substitution function by substituting a byte value for each of said permuted bytes, wherein said byte value is determined by performing a third XOR operation followed by a second S-box lookup operation, thereby creating a plurality of substituted bytes; and

means for treating said plurality of substituted bytes as said plurality of input data bytes for a subsequent iteration of said means for iteratively performing, provided said number of times has not been reached.

11. The system according to claim 10, wherein said means for performing said mixing function further comprises:

means for dividing said plurality of input data bytes into a left input half and a right input half;

means for performing a first mixing operation on said left input half and a second mix operation said if right half, wherein said second mixing operation uses a different selection of operands for said first and said second XOR operations than does said first mixing operation;

means for using each byte of a result of said second XOR operation of said first mixing operation as a lookup index for said first S-box lookup operation to retrieve bytes of a new left half; and

means for using each byte of an output of said second XOR operation of said second mixing operation as said lookup index for said first S-box lookup operation to retrieve bytes of a new right half.

12. The system according to claim 11, wherein:

said means for performing said first mixing operation further comprises;

means for using an identically-numbered byte from said left input half and said right input half as operands of said first XOR operation; and

means for using a result of said first XOR operation and a byte from said right input half that has been effectively rotated right one byte as operands of said second XOR operation; and

said means for performing said second mixing operation further comprises;

means for using a selected byte from said right input half and a previously-mixed byte from said new left half that has been effectively rotated right one byte as operands of said first XOR operation; and

means for using an output of said first XOR operation and a different previously-mixed byte from said new left half that has been effectively rotated left two bytes as operands of said second XOR operation.

13. The system according to claim 10, wherein said means for performing said mixing function and said means for performing said key-dependent substitution function perform said first S-box lookup operation and said second S-box lookup operation, respectively, by accessing a selected one of two distinct S-boxes using a one-byte index, each of said S-boxes having 256 distinct entries, each of said entries being a one-byte value.

14. The system according to claim 10, wherein one or more of said means is embodied in a hardware chip.

15. The system according to claim 10, wherein said means for performing said permuting function further comprises:

means for dividing said plurality of mixed bytes into a left mixed half and a right mixed half; and

means for swapping said left mixed half with said right mixed half.

16. The system according to claim 10, wherein said means for performing said key-dependent substitution function further comprises:

means for using a sub-key byte from a selected one of said generated sub-keys which is uniquely associated with said round as an operand of said third XOR operation, along with said each permuted byte; and

means for performing said second S-box lookup operation using each byte of a result of said third XOR operation as an index.

17. The system according to claim 10, wherein particular values of one or more of said number of rounds, said key length, and said block length are determined in advance in order to optimize said system, and wherein said means for determining therefore operates as if said one or more particular values are fixed.

18. The system according to claim 10, further comprising:

means for decrypting said encrypted data block, resulting in restoration of said plurality of input data bytes, by performing a set of inverse round functions said number of times equal to said number of rounds, wherein said set of inverse round functions comprises an inverse key-dependent substitution function which is inverse to said key-dependent substitution function, an inverse permuting function which is inverse to said permuting function, and an inverse mixing function which is inverse to said mixing function.

19. A method of providing a byte-oriented symmetric key block cipher which supports a variable length symmetric input key, a variable length block, and a variable number of rounds, comprising the steps of:

determining a number of rounds of cipher processing to use as said variable number of rounds, a key length of said variable length symmetric input key, and a block length of said variable length block;

generating a plurality of sub-keys using said symmetric input key as an input value, wherein each of said generated sub-keys is equal in length to said block length and where a distinct one of said sub-keys is generated for each of said number of rounds;

obtaining an input data block to be encrypted, wherein said input data block comprises a plurality of input data bytes, said plurality being equal in number to said block length; and

iteratively performing a set of round functions a number of times equal to said number of rounds in order to encrypt said input data block, wherein said set of round functions comprises a mixing function, a permuting function, and a key-dependent substitution function, and wherein said iteratively performing step further comprises the steps of;

performing said mixing function by mixing each of said input data bytes using a first XOR operation and a second XOR operation, wherein said first and second XOR operations are different, followed by a first substitution-box (S-box) lookup operation, thereby creating a plurality of mixed bytes;

performing said permuting function by swapping each of said mixed bytes, thereby creating a plurality of permuted bytes;

performing said key-dependent substitution function by substituting a byte value for each of said permuted bytes, wherein said byte value is determined by performing a third XOR operation followed by a second S-box lookup operation, thereby creating a plurality of substituted bytes; and

treating said plurality of substituted bytes as said plurality of input data bytes for a subsequent iteration of said iteratively performing step, provided said number of times has not been reached.

20. The method according to claim 19, wherein said step of performing said mixing function further comprises the steps of:

dividing said plurality of input data bytes into a left input half and a right input half;

performing a first mixing operation on said left input half and a second mixing operation on said right half, wherein said second mixing operation uses a different selection of operands for said first and second XOR operations than does said first mixing operation;

using each byte of a result of said second XOR operation of said first mixing operation as a lookup index for said first S-box lookup operation to retrieve bytes of a new left half; and

using each byte of an output of said second XOR operation of said second mixing operation as said lookup index for said first S-box lookup operation to retrieve bytes of a new right half.

21. The method according to claim 20, wherein:

said step of performing said first mixing operation further comprises the steps of;

using an identically-numbered byte from said left input half and said right input half as operands of said first XOR operation; and

using a result of said first XOR operation and a byte from said right input half that has been effectively rotated right one byte as operands of said second XOR operation; and

said step of performing said second mixing operation further comprises the steps of;

using a selected byte from said right input half and a previously-mixed byte from said new left half that has been effectively rotated right one byte as operands of said first XOR operation; and

using an output of said first XOR operation and a different previously-mixed byte from said new left half that has been effectively rotated left two bytes as operands of said second XOR operation.

22. The method according to claim 19, wherein said step of performing said mixing function and said step of performing said key-dependent substitution function perform said first S-box lookup operation and said second S-box lookup operation, respectively, by accessing a selected one of two distinct S-boxes using a one-byte index, each of said S-boxes having 256 distinct entries, each of said entries being a one-byte value.

23. The method according to claim 19, wherein one or more of said steps is embodied in a hardware chip.

24. The method according to claim 19, wherein said step of performing said permuting function further comprises the steps of

dividing said plurality of mixed bytes into a left mixed half and a right mixed half;

and

swapping said left mixed half with said right mixed half.

25. The method according to claim 19, wherein said step of performing said key-dependent substitution function further comprises the steps of:

using a sub-key byte from a selected one of said generated sub-keys which is uniquely associated with said round as an-operand of said third XOR operation, along with said each permuted byte; and

performing said second S-box lookup operation using each byte of a result of said third XOR operation as an index.

26. The method according to claims 19, wherein particular values of one or more of said number of rounds, said key length, and said block length are determined in advance in order to optimize said method, and wherein said step of determining therefore operates as if said one or more particular values are fixed.

27. The method according to claim 19, further comprising the step of:

decrypting said encrypted data block, resulting in restoration of said plurality of input data bytes, by performing a set of inverse round functions said number of times equal to said number of rounds, wherein said set of inverse round functions comprises an inverse key-dependent substitution function which is inverse to said key-dependent substitution function, an inverse permuting function which is inverse to said permuting function, and an inverse mixing function which to said mixing function.