Cryptography – Key management – Having particular key generator
Reexamination Certificate
1997-11-18
2002-07-23
Hayes, Gail (Department: 2131)
Cryptography
Key management
Having particular key generator
Reexamination Certificate
active
06424713
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to cryptographic systems, and, more particularly, to a method and apparatus for generating cryptographic keys with a concealed work factor. The system provides a high apparent work factor to maintain a high level of security against attackers. At the same time, with knowledge of a secret distribution key, a governmental agency is presented with a lower work factor.
BACKGROUND OF THE INVENTION
A cryptographic system uses cryptographic keys to secure data. Clear text is transformed into cipher text by the use of at least one cryptographic key which is known at the transmitter and delivered to the receiver for use in decryption of the cipher text. The size (e.g., length) of the cryptographic key is one measure of the level of security provided by the cryptographic system. For example, for the commonly used Data Encryption Standard (DES), the key length is 56 bits. Thus, since each bit can assume one of two possible values (e.g., 0 or 1), up to 2
56
attempts would be required to discover a given cryptographic key using a trial and error approach.
Discovery of the key generation sequence is another form of attack on the system. Generally, cryptographic keys are typically changed often to thwart trial and error attacks. The rate of key generation is a measure of cryptographic agility. Changing the key often makes it more difficult to discover the key because the key is not used for very long. For example, it may be acceptable to provide only one key for a two hour video program where a security breach is not critical. Alternatively, when a significant level of security is required, several (e.g., ten) new keys may be generated each second. In any case, the attacker could have access to some sequence of the cryptographic keys during the normal operation of a cryptographic system. For example, the attacker may gain access to the sequence of keys by becoming a legitimate subscriber of an information service. Over time, the attacker could observe and collect a large number of valid cryptographic keys. The attacker could then use these keys to extrapolate or guess the method of key generation.
Since the number of possible keys increases with bit length, the longer the bit length of a cryptographic key, the more difficult the task of discovering the key sequence. Thus, cryptographic keys with longer bit lengths are more desirable since they generally provide a more secure system, with all other factors being equal.
However, cryptographic security systems are subject to strict controls by governmental authorities. Laws vary from country to country, but almost all industrial nations control the strength of security-related products that cross their borders. Some nations such as the United States control export only, while others, such as France, control both export and import. Companies that manufacture products that use cryptography must design their products to conform to various governmental regulations to import or export their products to foreign markets. Moreover, oftentimes, manufacturers must produce different versions of their products for different countries. This introduces additional development expenses and complexity.
Typically, cryptographic strength is controlled by limiting the number of bits in the keys, and consequently, the number of possible unique keys. For example, the DES algorithm could be exported for satellite television conditional access applications if the 56-bit key is reduced to 40 bits by fixing 16 bits to a constant (e.g., zero). Similarly, in the DVB Common Scrambling Algorithm, a 64 bit key could be reduced to a 48 bit key by fixing 16 bits. However, while reducing the cryptographic key bit length satisfies governmental authorities, it also weakens the cryptographic strength of conventional systems. Accordingly, it would be desirable to provide a cryptographic system that can be easily weakened to satisfy government requirements, but which is not weakened for the purpose of defending against hostile attackers. The system should thus provide a level of security to attackers that is greater than the level presented to a governmental agency. Furthermore, the system should include a common encryption engine which can be adapted to different key bit-length requirements by a simple re-programming at the time of manufacture. The present invention provides the above and other advantages.
SUMMARY OF THE INVENTION
In the present invention, the number of possible cryptographic key combinations can be reduced in a manner that is not known to an attacker. The key has a large bit-length that provides a high security level and maintains a burdensome analysis task for a prospective attacker. But, with knowledge of a secret distribution key, the number of possible key combinations (e.g., the key space size) can be reduced to provide a lower security level that satisfies governmental requirements. In particular, a larger key length of, for example, B=56 bits is used. With knowledge of the secret distribution key, the S=2
56
available key combinations can be reduced to a subset (e.g., W=2
40
) of key combinations. To conceal the fact that a subset of the larger set of keys is used, the selected subset is distributed throughout the larger set of keys using a random process or some other process that is unknown to an attacker. Up to 2
40
56-bit keys can be produced in this manner for cryptographically processing a clear text message.
The governmental agency can be informed of the 2
40
keys out of the total possible 2
56
keys which are used. On the other hand, the attacker has no knowledge that only a subset of keys is used. Even if the attacker knew that only a subset of 2
56
keys was used, he still cannot identify the subset. However, the governmental agency can determine which key is in use at a given time through, for example, a comprehensive list of the 2
40
56-bit keys, or through a secret key or other algorithm which allows production of such a list. Note that the governmental agency is faced with the same amount of work, or “work factor”, (e.g., performing W=2
40
trials) regardless of the bit length of the keys on their list since the work factor is determined by the number of possible different keys. An attacker, however, cannot create this list, and must therefore check all possible 56-bit key combinations. In the above example, the attacker would need to check all 2
56
56-bit keys, which is much more effort than that facing the governmental agency. The work factor can therefore be viewed as the average number of trials that must be performed to determine the keys of the cryptographic system. The work factor will be lower, for instance, for a person who knows that the keys are generated in a particular (e.g., non-random) order, with a particular starting point, and in a particular sequence.
The attacker is thus faced with a level of difficulty (work factor) identical to that provided by a 56-bit key, while the government agency is faced with a level of difficulty provided by a 40-bit key. Accordingly, the conflicting goals of designing a system that meets governmental regulations while maintaining cryptographic strength are achieved.
In another aspect of the present invention, a key sequence generator for generating a subset of cryptographic keys out of a larger set is disclosed. In particular, a key generator for generating 2
B-F
cryptographic keys out of a possible 2
B
cryptographic keys uses a secret double or triple DES key in a hashing algorithm to randomly distribute a key space corresponding to 2
B-F
-bit keys over a larger key space which corresponds to 2
B
-bit keys. In this manner, the 2
B-F
different keys can be generated as required by the governmental agency, thereby avoiding the need to store the keys in a large memory.
REFERENCES:
patent: 4908861 (1990-03-01), Brachtl et al.
patent: 5323464 (1994-06-01), Elander et al.
patent: 5416841 (1995-05-01), Merrick
patent: 5483598 (1996-01-01), Kaufman et al.
patent: 0604008 (1994-06-01), None
patent: 2274229 (1994-0
General Instrument Corporation
Hayes Gail
Lipsitz Barry R.
Sayadian Hrayr A.
LandOfFree
Cryptographic system with concealed work factor does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cryptographic system with concealed work factor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cryptographic system with concealed work factor will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2847710