Cryptography – Particular algorithmic function encoding
Reexamination Certificate
1998-06-11
2001-11-06
Hayes, Gail (Department: 2131)
Cryptography
Particular algorithmic function encoding
Reexamination Certificate
active
06314186
ABSTRACT:
Korean Application 1997-26558, filed Jun. 23, 1997 upon which a claim for priority is based, is herein incorporated by reference.
FIELD OF THE INVENTION
The invention relates to a data encryption method, and to the fast block cipher algorithm that is secure against differential cryptanalysis, linear cryptanalysis, and higher-order differential cryptanalysis. More specifically, it can be embodied easily and executed rapidly in comparison with the conventional block cipher algorithms.
DESCRIPTION OF THE RELATED ART
Conventional cipher algorithms are designed intuitively or through the practical experience of a designer. Therefore, many on-going field-tests may be needed to ensure the security of the cipher algorithm.
A common block cipher algorithm is based on DES, which is adopted as the United States Data Processing Standard 46 (FIPS PUB46) by the United States Standardization Office. DES is a block cipher algorithm which encrypts data in 64-bit blocks.
A 64-bit block of plain text serves as an input to one end of the algorithm and a 64-bit block of cipher text is output from the other end. DES is, therefore, a symmetric algorithm.
The same algorithm and key are used for both encryption and decryption, except for minor differences in the key schedule. The key length is 56-bits. However, the key is usually expressed as a 64-bit number, where 8-bits are used for parity checking and are therefore, ignored during encryption/decryption. Also the parity bits are the least significant bits of the key bytes. The key can be any 56-bit number and can be changed at any time. Several numbers are considered weak keys, but these weak keys are easily avoided, since all security rests within the key.
At its simplest level, an algorithm is nothing more than a combination of the two basic techniques of encryption, that is, confusion and diffusion. The fundamental building block of DES is a single combination of these techniques, i.e., a substitution followed by a permutation in the text, based on the key, commonly referred to as a round.
DES has 16 rounds. It applies the same combination of techniques on plain text block 16 times. The DES algorithm uses only standard arithmetic and logical operations on a maximum of 64-bits, thus it was easily implemented in late 1970s hardware technology. The repetitive nature of the algorithm made it ideal for use on a special purpose chip. Initial software implementations were clumsy; however, current implementations have improved.
DES operates on a 64-bit block of plain text. After an initial permutation, the block is broken into a right half and a left half, each 32-bits long. Then, there are 16 rounds of identical operations, called function F, in which the data is combined with the key. After the sixteenth round, the right and left halves are joined, and a final permutation, the inverse of the initial permutation, completes the algorithm.
In each round, the key bits are shifted, and then 48-bits are selected from the 56-bits of the key. The right half of the data is expanded to 48-bits via an expansion permutation, combined with 48-bits of a shifted and permuted key via an XOR, sent through 8 S-boxes producing new 32-bits, and permuted again. These four operations make up the round function F. The output of function F is then combined with the left half via another XOR. The results of these operations become the new right half; and the old right half becomes the new left half. The operations are repeated 16 times, thereby making 16 rounds of DES.
Based on differential cryptanalysis, linear cryptanalysis and higher-order differential cryptanalysis, DES is attackable by using 2
47
chosen cipher texts via differential cryptanalysis and by using 2
43
known cipher texts via linear cryptanalysis.
Many cipher algorithms have been proposed for handling the above cryptanalysis, and one comes to think that the encryption algorithm that is resistant against the above attacks (differential and linear) will be a secure one. For additional security, a method has been developed to construct an encryption algorithm by the theoretical and logical proofs of the algorithm's resistance against differential and linear cryptanalysis. However such an approach is very difficult.
The first attempt to solve these problems was the MISTY algorithm of Japan. In the MISTY algorithm, S-boxes consisting of 7-bits or 9-bits have simple algebraic form. A disadvantage of the MISTY algorithm is that an implementation of it requires a complicated recursive structure.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a rapid block cipher algorithm to address the problem which ensures its security against the differential cryptanalysis and linear cryptanalysis attacks, and moreover against the higher-order differential cryptanalysis.
The present invention, herein referred to as SNAKE, has a round function differing from the conventional block cipher algorithms. The round function of SNAKE has a very simple structure which has a basic logical operation (exclusive OR-operator), and an 8-bit rotating operation (except for the S-boxes which are required to have high non-linearity for their security), in order to simplify the embodiment. SNAKE, however, does not have the same recursive structure as the MISTY algorithm, but is instead structured for the output data block of one S-box to be fed back to the left next S-box, and it is shifted in the left by 8-bits. This structure brings strict avalanche diffusion to the flowing data, so as to make the round function's linearity and differential uniformity low. In the verification of its resistance against differential and linear cryptanalysis, the inventors' concept of ‘Difference string’ and ‘Fundamental Differential Matrix’ has been developed wherefrom theoretical inducement has been established.
The key scheduling process of SNAKE will now be described. Initially, the process is fed a random 128-bit seed key and the seed key is broken into four 32-bit sub-blocks. The sub-blocks go through the process illustrated in
FIG. 2
with a 32-bit constant irrational number GN having a characteristic sequence of random bits via the three operations: exclusive-OR operation; 256-modulus addition; and 5-bit left rotation. This processes prevents the recovery of the previous round's key, even if the next round's keys are found.
REFERENCES:
patent: 5003597 (1991-03-01), Merkle
patent: 5623548 (1997-04-01), Akiyama et al.
patent: 5838794 (1998-11-01), Mittenthal
patent: WO 98/00949 (1998-01-01), None
Schneier, Applied Cryptography, pp. 272, 320-323, 1996.*
Mittenthal, Statistical Efficient Inter-Round Mixing in Block Substitution Devices, Teledyne, 1996.*
Lee, et al., “The Block Cipher: Snake with Provable Resistance Against DC and LC Attacks,”Proc. of JW-ISC, 1997, Session 1, pp. 3-17.
Knudsen, “Truncated and Higher Order Differentials,”Advances in Cryptology, Fast Software Encryption, 1995.
Matsui, “Linear Cryptanalysis Method for DES Cipher,”Advances In Cryptology, Endocrypt, 1993, pp. 391-397.
Nyberg, “S-Boxes and Round Functions with Controllable Linearity and Differential Uniformity,”Advances In Cryptology, Fast Software Encryption, 1994, pp. 111-129.
Internet thread concerning Teledyne, cypherpunks@toad.com, Jul. 1996.
Cha Young-tae
Lee Chang-hyi
Burns Doane Swecker & Mathis L.L.P.
Hayes Gail
Samsung Electronics Co,. Ltd.
Seal James
LandOfFree
Block cipher algorithm having a robust security against... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Block cipher algorithm having a robust security against..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Block cipher algorithm having a robust security against... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2575992