Cryptography – Key management
Reexamination Certificate
1999-06-03
2001-08-21
Swann, Tod (Department: 2132)
Cryptography
Key management
C380S002000, C380S042000, C713S340000
Reexamination Certificate
active
06278783
ABSTRACT:
FIELD OF THE INVENTION
The method and apparatus of the invention relate generally to securing cryptographic systems against external attacks and, more specifically, to preventing attacks that involve the external monitoring of cryptographic operations.
BACKGROUND OF THE INVENTION
Cryptographic operations are used for a variety of processes such as data encryption and authentication. In a typical symmetric cryptographic process, a secret key is known to two or more participants, who use it to secure their communications. In systems using asymmetric (or public key) cryptography, one party typically performs operations using a secret key (e.g., the so-called private key), while the other performs complementary operations using only non-secret parameters (e.g., the so-called public key). In both symmetric and asymmetric cryptosystems, secret parameters must be kept confidential, since an attacker who compromises a key can decrypt communications, forge signatures, perform unauthorized transactions, impersonate users, or cause other problems.
Methods for managing keys securely using physically secure, well-shielded rooms are known in the background art and are widely used today. However, previously-known methods for protecting keys in low-cost cryptographic devices are often inadequate for many applications, such as those requiring a high degree of tamper resistance. Attacks such as reverse-engineering of ROM using microscopes, timing attack cryptanalysis (see, for example, P. Kocher, “Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems,”
Advances in Cryptology—CRYPTO '
96, Springer-Verlag, pages 104-113), and error analysis (see, for example, E. Biham and A. Shamir, “Differential Fault Analysis of Secret Key Cryptosystems,”
Advances in Cryptology—CRYPTO '
97, Springer-Verlag, 1997, pages 513-525) have been described for analyzing cryptosystems.
Ciphers and algorithms believed to be cryptographically secure are known in the background art. For example, protocols using triple DES (a cipher constructed using three applications of the Data Encryption Standard using different keys) can resist all feasible cryptanalytic attacks, provided that attackers only have access to the standard inputs to and outputs from the protocol. However, even a product using an extremely strong cipher such as triple DES can be insecure if the keys are not managed securely.
This document assumes a detailed understanding of the Data Encryption Standard (DES), which is defined in Federal Information Processing Standards Publication 46 and need not be described in detail here. Information on DES and other cryptographic algorithms can also be found in
Applied Cryptography
by Bruce Schneier (Wiley and Sons, Inc., 1996), in the
Handbook of Applied Cryptography
by Menezes et al. (CRC Press, Inc., 1997), or in other standard references as will be appreciated by those skilled in the art.
SUMMARY OF THE INVENTION
This invention describes processes in which secrets (e.g., keys and/or messages) are divided into separate portions, which are then separately mutated, while maintaining mathematical relationships between or among the portions that are used for performing secure cryptographic operations. In the update (“mutation”) operation, key management devices introduce randomness or other unpredictability into their internal state. By changing the secret portions, information collected by attackers about them can be made obsolete. If information is invalidated faster than it can be collected by attackers, a system can be made secure.
The invention provides for improved implementations of the Data Encryption Standard (DES), as well as other cryptographic operations, that resist external monitoring attacks. Unlike traditional DES implementations, which perform a set of processing operations that depend only on the input key and the message, the invention involves additional random (or otherwise unpredictable) state information in the cryptographic processing. The random state information is mixed with the keys, plaintext messages, and intermediate quantities used during processing. Information leaked to attackers during cryptographic processing is correlated to the random information, and any correlation to secret information is partially or completely hidden. As a result, it is difficult or impossible for attackers to determine secret parameters through analysis of leaked information.
A detailed description of how the invention may be applied to the Data Encryption Standard is provided. State parameters that are normally encoded as ordinary binary values are blinded and their order masked using randomized permutation tables. While a traditional DES implementation would encode the input message M as a 64-bit value, an exemplary embodiment of the invention blinds M to produce a two-part value (M
1
, M
2
) such that M
1
XOR M
2
corresponds to the “normal” message. Additionally, the parameters M
1
and M
2
are encoded in random order, where permutations M
1
P and M
2
P are stored in memory to keep track of the current order of the bits in M
1
and M
2
. Keys may be similarly stored in blinded, order-randomized form. M
1
P and M
2
P contain bit ordering information and do not represent message content. The message blinding technique of the invention ensures that neither M
1
by itself nor M
2
by itself is correlated to the message in any way. Consequently, the implementation can remain secure even if the complete value of any parameter is leaked to an attacker.
The standard DES algorithm involves three primary types of operations: permutations, S lookups, and bitwise XORs. In the exemplary embodiment, permutations of the message (M
1
, M
2
, M
1
P, M
2
P) are performed by manipulating M
1
P and M
2
P. Only the permutation arrays are manipulated; the parameter data bits in M
1
and M
2
do not need to be accessed or modified. Permutations (such as IP, PC
1
, E, P, and FP, which are defined as part of the standard DES algorithm definition) can thus be made safe against leakage. For XOR operations, halves of the input parameters are processed separately. For example, using the message notation above, the operation of computing the XOR of two values A and B encoded as (A
1
, A
2
, A
1
P, A
2
P) and (B
1
, B
2
, B
1
P, B
2
P) is computed by first finding the XOR of (A
1
, A
1
P) and (B
1
, B
1
P), then finding the XOR of (A
2
, A
2
P) and (B
2
, B
2
P). Note that because of the blinding, A
1
and B
1
by themselves are not correlated to the complete value of A or B. Order randomization is used to prevent attackers from obtaining information about A and B from correlations within and between observations of the two XOR operations. Finally, for the S table lookup operations, the S tables themselves are stored in the device's memory in blinded form, such that the S table inputs and outputs are blinded with random values. To perform an S operation, the inputs (e.g., A
1
, A
2
, A
1
P, A
2
P), the S table input blinding factor, and the S input table permutation are combined and used to index the S table itself. (The S tables are blinded and randomly permuted, and are re-shuffled periodically.) The S results are obtained in halves, which are separately processed through the P permutation and XORed onto the destination. Sixteen rounds are performed, ultimately yielding the final ciphertext. The ciphertext is produced in permuted, blinded form, which may be easily converted to the standard DES ciphertext.
Although the invention has been described in the context of permuting both keys and messages, each into two sub-parts, those skilled in the art will appreciate that either or both (as well as other secret quantities) could be permuted, into a plurality of parts greater than two. In addition, although the invention has been described with respect to DES, the invention can be applied to and adapted to other cryptographic symmetric algorithms, including without limitation Blowfish, SEAL, IDEA, SHA, RC
5
, TEA, and other cryptographic algorithms involving operations suitable for applicatio
Jaffe Joshua M.
Jun Benjamin C.
Kocher Paul C.
Arps Skadden
Cryptography Research, Inc.
Darrow Justin T.
Lane Thomas R.
Swann Tod
LandOfFree
Des and other cryptographic, processes with leak... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Des and other cryptographic, processes with leak..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Des and other cryptographic, processes with leak... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2466754