Cryptography – Communication system using cryptography – Pseudo-random sequence scrambling
Reexamination Certificate
1998-09-18
2002-02-26
Peeso, Thomas R. (Department: 2132)
Cryptography
Communication system using cryptography
Pseudo-random sequence scrambling
C380S044000, C380S046000
Reexamination Certificate
active
06351539
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to block ciphers. More particularly, this invention relates to improving the security of block ciphers using cipher concatenation in combination with a random number generator.
2. Description of the Related Art
Various block ciphers are known and are used to encrypt (and decrypt) data. Block ciphers are described in detail in Bruce Schneier, “Applied Cryptography” Second Edition, 1996, which is incorporated herein by reference. Block ciphers operate on blocks of plaintext and ciphertext, usually of 64 bits but sometimes longer. Block ciphers have the property that, using the same key, the same plaintext block will always encrypt to the same ciphertext block. Typical block ciphers currently use 128-bit keys although shorter and longer keys can be used.
It is generally the case that the greater the key length for a particular cipher, the stronger the cipher. In some ways this is simply related to the number of keys which need to be tried in order to decipher a message. A key length of k means that at most 2
k
possible keys exist and must be tried in order to decipher a message using an exhaustive key search. In fact, for an n-bit block cipher with a k-bit key, given a small number e.g., ┌(k+4)
┐ of plaintext-ciphertext pairs encrypted under the key K, K can be recovered by exhaustive key search in an expected time on the order of 2
k−1
operations.
Cipher concatenation or combined (e.g., chained) block ciphers are also known, however such combinations do not necessarily add to security since they may not effectively increase the key length. For example, double encryption with two separate 128-bit keys does not provide effective 256-bit key security against known attacks.
One of the reasons that cascaded or multiple chained block ciphers may not be any stronger than a single block cipher is that chains are vulnerable to various attacks which do not require brute force attempts using all keys. A naïve exhaustive attack on all key pairs in double DES uses on the order of 2
112
operations, whereas a non-naïve, so-called meet-in-the-middle attack on the same combination requires only on the order of 2
56
operations. Various other combinations are known, including, e.g., triple encryption with two keys, and other variants on triple encryption.
One other known way to combine multiple blocks is to use two algorithms (and two independent keys). Using this approach, first generate a random-bit string, R, the same size as the message M. Then encrypt R with the first algorithm (and the first key) and then encrypt M⊕R (the exclusive-or combination of M and R) with the second algorithm (and the second key). The ciphertext is the combined result of the two encryptions and is at least as strong as the stronger of the two encryption algorithms.
Assuming that the random string is indeed random, this approach encrypts M with a one-time pad and then encrypts both the pad and the encrypted message with each of the two algorithms, respectively. Since both algorithms are required to reconstruct M, a cryptanalyst must break both. This method can be extended to multiple algorithms.
Combining multiple ciphers can have a problem in that the combination is potentially weakened if one of the component ciphers is compromised. Further, the combination may be only as strong as only one of the elements in the combination.
It is desirable to produce block ciphers with arbitrarily long key length so as to increase their security. It is also desirable to produce such block ciphers from existing, already accepted block ciphers as components. By using existing block ciphers as components, there is already a built up trust in the components.
SUMMARY OF THE INVENTION
This invention solves these and other problems by providing a combination block cipher with an effective key length greater than that of its components.
This invention increases the security provided by any single block cipher by providing encryption of an input stream by at least two different block ciphers. To add to the security, a one-time pad in the form of a random data stream, is combined with an encrypted form of the input stream before it is encrypted by the second block cipher.
In one aspect, this invention is an encryption device which has a random number generator and three block cipher mechanisms. The first block cipher mechanism takes a plaintext input and produces a first enciphered output based on the plaintext and on a first key. An exclusive-or mechanism takes as input the first enciphered output from the first block cipher and the output of the random number generator and produces a combined output. The second block cipher mechanism takes as input the output of the exclusive-or mechanism and produces a second enciphered output based on the output of the exclusive-or mechanism and on a second key. The third block cipher mechanism takes as input the output of the random number generator and produces a third enciphered output based on the output of the random number generator and on a third key. The first and second block cipher mechanisms differ from each other, with one preferably being the IDEA block cipher, and the other preferably being the Blowfish block cipher.
Preferably the first and third block cipher mechanisms are Blowfish block ciphers and the second block cipher is the IDEA block cipher. The plaintext input is preferably a sequence of 64-bit values and the output of the random number generator is a sequence of 64-bit random values. Preferably the random number generator is a true random number generator.
In another aspect, this invention is the decryption device corresponding to the encryption device.
This invention's combination of block ciphers with random numbers has a number of advantages, including:
Cryptanalysis based on known characteristics of the plaintext is impossible.
The effective key length is the sum of key lengths used in BC
1
and BC
2
(256-bits in the preferred scheme).
Failure (such as discovery of a backdoor) of any of the two block cipher kinds used still leaves the 128-bit security of the other intact.
The same plaintext block never encrypts to the identical ciphertext block, and yet every ciphertext block is independent from any other ciphertext block.
REFERENCES:
patent: 4933969 (1990-06-01), Marshall et al.
patent: 4995082 (1991-02-01), Schnorr
patent: 5214703 (1993-05-01), Massey et al.
patent: 5384848 (1995-01-01), Kikuchi
patent: 5606616 (1997-02-01), Sprunk et al.
patent: 5623549 (1997-04-01), Ritter
patent: 5671284 (1997-09-01), Buer
patent: 5673319 (1997-09-01), Bellare et al.
patent: 5703952 (1997-12-01), Taylor
Menezes, Alfred f. et al., “Applied Cryptography”, CRC Press LLC, Jan. 1997.*
“Randomness Recommendations for Security,” Network Working Group, Request for Comments: 1750, Dec., 1994.
Bruce Schneier, Applied Cryptography, 2n Ed., John wiley & Sons, Inc. 1996, pp. 319-325, 336-339, 357-368.
Integrated Device Technology Inc.
Jack Todd
Peeso Thomas R.
Pillsbury & Winthrop LLP
LandOfFree
Cipher mixer with random number generator does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cipher mixer with random number generator, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cipher mixer with random number generator will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2981538