Electrical computers and digital processing systems: support – Multiple computer communication using cryptography – Security kernel or utility
Reexamination Certificate
2003-03-14
2004-05-25
Peeso, Thomas R. (Department: 2132)
Electrical computers and digital processing systems: support
Multiple computer communication using cryptography
Security kernel or utility
C713S165000, C713S166000, C713S168000
Reexamination Certificate
active
06742115
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to the encryption of wireless communication signals, and relates in particular to the communication between systems having different encryption requirements. It has become commonplace to transmit messages, in the form of digital data, via wireless communication systems and/or the Internet.
Two general types of cryptography are secret key cryptography and public key cryptography. In the case of secret key cryptography, a message, often referred to as “plaintext”, to be transmitted from a sender to an intended recipient is encrypted using a secret key and the intended recipient decrypts the encrypted message, frequently referred to as a “ciphertext” or a “cryptogram”, using the same secret key. Only the secret key may be used to encrypt and decrypt the message and attempts made to decrypt the message with other keys will fail. A widely used secret key system is the Data Encryption Standard (DES) which employs a 56 bit key and 8 non-key parity bits. DES was published as a U.S. Federal Information Processing Standard in 1977.
The present invention is directed essentially to secret key cryptography.
The degree of security provided by a given encryption system depends on the strength, or work factor, of the system, which is commonly measured in terms of the number of bits in the key.
A work factor is a number, expressed in bits, which is the logarithm to base 2 of the maximum number of basic decryption operations which must be performed, using different trial keys, to determine with certainty which trial key corresponds to the actual key that was used for encryption. For example, the DES Algorithm has a work factor of 56 bits because it provides a key with 2
56
possible values. As is known in the art, any trial key may be the correct key. Therefore, the correct key will usually be found after fewer than 2
56
trials. On average, the correct key will be found after half of the possible trial key values have been tested. However, it is common practice to base the work factor on the maximum number of possible key values and this provides a valid basis for comparison of different work factors.
Thus, for example, in a secret key encryption system, a key which is three bytes long, i.e., consists of 24 bits, can be broken relatively easily by trying all 2
24
possible keys until comprehensible plaintext is obtained. This technique is one form of what is sometimes referred to as a “brute force attack” or “exhaustive cryptoanalysis”. The larger the number of bits in a key, the greater will be its strength. It is presently believed that, for example, a 128 bit key for a secret encryption algorithm will be completely unbreakable, at least by the brute force method.
The work factor of an encryption key may or may not be less than the physical size of the key. However, the work factor cannot be greater than the physical size of the key. This is because the work factor is dependent only on the amount of secret information in the keys. If the physical size of an encryption key is increased by adding information that is not secret, its work factor is not increased.
Another type of attack relies on advance knowledge, or assumed advance knowledge, of the plaintext of a portion of a message. For example, it may be known that e-mail messages always include certain passages, such as section headings. One seeking to intercept and decrypt such messages could precompute the encrypted form of the known passages, with each possible key and stores both the result for each key and the key itself in a table. Then, if a message is intercepted, the encrypted portion of known context is found in the table, which yields the correct key. This technique is known as a precomputation attack.
Precomputation attack allows intercepted messages to be decrypted relatively quickly and inexpensively, even when the encryption key has a high work factor, but can be foiled by use of a “salt,” which will be described in detail below.
On the other hand, the time and expense required to decrypt an intercepted message by the brute force approach depends essentially on the work factor of the encryption key. However, in certain situations, it is necessary to utilize keys having reduced work factors. For example, U.S. law permits the export of cryptographic algorithms or products having a limited key length. For example, certain algorithms may currently be exported if limited to a 40 bit key length. In addition, the laws in certain foreign countries place an upper limit on key length.
BRIEF SUMMARY OF THE INVENTION
It is an object of the present invention to facilitate communication between users, or stations, that operate with keys having different work factors.
A more specific object of the invention is to establish, between two stations, a work factor that can be used by two stations having respectively different work factor capabilities to allow communication between those stations.
The above and other objects are achieved, according to the present invention, by a method for permitting encrypted communications between two stations which are operable with encryption algorithms that accept encryption keys having work factors with respectively different values, comprising:
in a first determining step, determining the lower one of the different work factor values;
providing an initial encryption key having a first work factor value;
comparing the first work factor value with the lower one of the work factors determined in said determining step;
when, in the comparing step, the first work factor value is found to be greater than the lower one of the work factor values determined in said determining step, performing the following steps:
performing a hash function on the initial encryption key to produce a first output, and deriving from the first output a first intermediate key having a work factor value not greater than the lower one of the different work factor values determined in the determining step;
performing a hash function on the first intermediate key to produce a second output, and deriving from the second output a final encryption key having a work factor value not greater than the lower one of the different work factor values determined in said determining step; and
using the final encryption key to encrypt communications between the two stations; and
when, in the comparing step, the first work factor value is found to not be greater than the lower one of the work factor values determined in the determining step, using the initial encryption key to encrypt communications between the two stations.
Objects according to the invention are further achieved, according to the invention, by a method for permitting encrypted communications between two stations, each of which stations is operable with an encryption algorithm that can accept an encryption key having a given work factor value, comprising:
providing an initial encryption key having a first work factor value which is smaller than the given work factor value of the encryption key that can be accepted by each station;
performing a hash function on a first word that includes the initial encryption key to produce an intermediate key, and deriving from the intermediate key a modified intermediate key having a work factor value which has a greater resistance to precomputation attack than the first work factor value and which is not greater than the given work factor value of the encryption key that can be accepted by each station;
performing a hash function on a second word that includes the modified intermediate key to produce a second output, and deriving from the second output a final encryption key having a work factor value equal to the work factor value of the first intermediate key; and
using the final encryption key to encrypt communications between the two stations.
REFERENCES:
patent: 6240513 (2001-05-01), Friedman et al.
patent: 6253193 (2001-06-01), Ginter et al.
patent: 6304658 (2001-10-01), Kocher et al.
Choi Jae-Hee
Minhas Sandip S.
Peeso Thomas R.
Qualcomm Inc.
Wadsworth Philip R.
LandOfFree
Method for negotiating weakened keys in encryption systems does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for negotiating weakened keys in encryption systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for negotiating weakened keys in encryption systems will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3243781