Bob Jueneman wrote:
Russ, nice job of synthesizing various inputs into a standard format.
[RH] Thanks.
However, I continue to think we have two problems that have to
be addressed. One is cryptographic, and one is architectural.
The cryptographic problem is one of not wanting to leak any
information in the case of many, many wrappings of the same CEK,
or in the case of a single KEK being used to wrap many, many CEKs;
where an observation of two matching ciphertexts might reveal information
about the plaintext if the cipher text includes any form of stereotyped of
constant information, e.g., parity bits or padding.
[RH] Bob, this a a good summary of the high-level objectives.
The architectural problem is to try to avoid the forthcoming problem of
needing N-squared algorithm IDs in order to handle the various combinations
of key encryption keys and content encryption keys of different types that
are likely to be developed over the coming years.
[RH] Algorithm identifiers are cheap. The security is much more important
than conserving identifiers. However, I understand the desire for a
general solution.
Although S/MIME may only be interested in some small number of algorithm
types today, there are lots of places where wrapped keys may be required
in addition to S/MIME, and as a security architect I don't want to have
to keep reinventing (and recoding) key wrapping techniques.
For this reason, I will offer my comments inline on the algorithms that
you have
proposed, and then propose a new Generalized Key Wrapping Algorithm
that attempts to take the best features of each of the three approaches you
have described, and apply them in a more generalized way.
In addition, I've tried to explicitly state the security criteria, as I
agree with
Don Johnson. Reasonable men can still differ, but if they don't have a
common
understanding and agreement as to the requirements, differences are almost
guaranteed.
= = = = = = = = = =
WRAP ALGORITHM #1: DOUBLE ENCRYPTION
A.1 Key Checksum
The CMS Checksum Algorithm is used to provide an content-encryption key
integrity check value. The algorithm is:
1. Compute a 20 octet SHA-1 message digest on the
content-encryption key.
2. Use the most significant (first) eight octets of the
message digest value as the checksum value.
[RRJ] I'm really not convinced of the necessity for a key checksum, although
I certainly have not followed all of the previous discussion. If someone
were
trying to attack the key distribution mechanism, then the key checksum
could act as an oracle. I would _much_ prefer to checksum the entire result,
i.e., the final encrypted key, than to checksum the CEK itself. Is there
some
strong justification for this that I've missed, such as the French stop-code
requirement?
[RH] My reason is quite straightforward. Once the key is unwrapped, it
will be used to decrypt the content. In many cases, the content will be
rather large. If an attacker alters the wrapped key, the resulting
upwrapped key will not be the correct CEK. If there is not an integrity
check on the CEK, then the entire content must be processed. The resulting
content will be junk, and a fair amount of processing was doen to get that
junk. I simply want to detect the modification as early in the processing
as possible.
A.2 Triple-DES Key Wrap
1. Set odd parity for each of the DES key octets comprising
the content-encryption key.
2. Compute a 8 octet key checksum value on the content-encryption
key as described above.
3. Concatenate the key checksum value and the content-encryption key.
The result is four 8 octet blocks: B1, B2, B3, and B4.
4. Encrypt in CBC mode the four blocks using the key-encryption key.
Use an IV of all zeros.
5. Reverse the order of the four ciphertext blocks. The resulting
order is B4, B3, B2, and B1.
[RRJ] Rather than merely interchange the order of the four blocks, I believe
that the entire string should be reversed, byte for byte. (I'd really like
to do it bit by bit, but the code would be a little awkward.) Preserving the
original block boundaries might possibly allow some clever attacks. I also
don't see the need for the final reversal.
[RH] I only see one reversal. Also, Reordering the blocks, bytes or bits
all preserve the block boundaries. The same ciphertext bits (in different
orders) will comprise the inputs to the second encryption in each case.
6. Encrypt the four blocks a second time. Encrypt in CBC mode
using the key-encryption key. Use an IV of all zeros.
[RRJ] I would prefer to use something other than 0 for the IV.
Ideally, the IV should be variable for each KEK, in order to make
a chosen plaintext attack that much more difficult. If a varying IV is
too difficult from a protocol standpoint, then at least avoid any kind of
repeating structure -- use pi, or the square root of 2, or something
random. And use two different IVs for the different steps.
Tom Berson is absolutely right -- avoid structure and
symmetry at all cost!
[RH] Two different IVs is easy. The zero IVs were suggested by Carl Ellison.
[RRJ] But my primary objection to this approach is the expense incurred
by the
second encryption pass. Even though a triple-DES operation may be quite
fast compared to say an RSA encryption, cycles are cycles, and
deliberately causing additional key management overhead that could be
avoided is unacceptable.
[RH] This double encryption operation has the property that every output
bit depends on every input bit. This is highly desirable.
WRAP ALGORITHM #2: MASK AND ENCRYPT
B.1 Key Checksum
The CMS Checksum Algorithm is used to provide an content-encryption key
integrity check value. The algorithm is:
1. Compute a 20 octet SHA-1 message digest on the
content-encryption key.
2. Use the most significant (first) eight octets of the
message digest value as the checksum value.
B.2 Triple-DES Key Wrap
1. Set odd parity for each of the DES key octets comprising
the content-encryption key.
2. Compute a 8 octet key checksum value on the content-encryption
key as described above.
3. Generate an 8 octet random number: RAND.
4. Let H1 = SHA-1 ( RAND ).
5. Let H2 = SHA-1 ( H1 ).
6. Let MASK equal the most significant (first) 32 octets of H1 || H2.
[RRJ] H2 is in some sense "more random" than H1, since it includes
the mixing effect of the previous SHA-1. If RAND were less than perfectly
random, i.e., subject to some kind of bias, H1 might remove most, but perhaps
not all of the bias, but if SHA-1 is any good at all, H2 should be much
less likely to leak information. For that reason, and since CBC introduces
error propagation in the forward direction, MASK should equal the most
significant (first) 32 octets of H2 || H1.
[RH] Fine.
7. Let KEYICV equal the content-encryption key concatenated with
the key checksum value.
[RRJ] For the reason given above, forward error propagation, the KEYICV should
be formed by taking the key checksum concatenated with (followed by)
the CEK. But I would greatly prefer not to have a key checksum at all,
in which case MASK would only be 24 octets long, assuming a "naked"
triple-DES CEK.
[RH] Okay. Let KEYICV equal the key checksum value concatenated with the
content-encryption key.
8. Let PLAIN = RAND || ( KEYICV XOR MASK ).
[RRJ] The disadvantage of this approach, as compared to approach 3
(OAEP), is that the RAND is not whitened. Therefore, if there is any weakness
in RAND, it may be possible to derive some information from any block that
has a matching ciphertext.
[RH] In your posting on 4 Feb 1999, I did not see any whitening of RAND.
This alternative builds on your proposal....
9. Encrypt PLAIN in CBC mode using the key-encryption key.
Use an IV of all zeros.
WRAP ALGORITHM #3: OAEP AND ENCRYPT
C.1 Key Checksum
No explicit checksum algorism is needed. The OAEP processing provides
the necessary integrity.
C.2 Triple-DES Key Wrap
1. Set odd parity for each of the DES key octets comprising
the content-encryption key, called CEK.
2. Let CEKPAD = 0x18 || CEK || 0x0000000000000000000000.
3. Generate a 160-bit random value, called RAND.
4. Let H1 = SHA-1 ( RAND || 0x01 ).
5. Let H2 = SHA-1 ( RAND || 0x02 ).
6. Let MASK1 equal the most significant (first) 36 octets of H1 || H2.
[RRJ] I would prefer that a stronger function than this be used.
As it stands, the input to the two SHA-1 routines differ by only
two bits. Use the approach of scheme 2 as modified above, i.e.,
Let H1 = SHA-1 ( RAND ), H2 = SHA-1 ( H1 ) ,
MASK1 equal the most significant (first) 36 octets of H2 || H1.
[RH] I took this approach from SET. I have not problem with your suggestion.
7. Let MKEY = CEKPAD XOR MASK1.
8. Let MASK2 = SHA-1 ( MKEY ).
9. Let MRAND = MASK2 XOR RAND.
10. Let MDATA = MRAND || MKEY.
11. Encrypt MDATA with the key-encryption key and CBC mode. Use an IV
with each octet equal to 0xA5. The ciphertext is 56 octets long.
[RRJ] Again, there is absolutely no reason to deliberately introduce
structure and symmetry in the IV. If possible, use a real IV that varies
for each KEK, in order to make a chosen plaintext attack that much
more difficult. At a minimum, use a pseudo-random constant with no
apparent structure.
[RH] A random IV is fine. I was trying to avoid an extra block. We could
accept the extra block or generate a random value and use it as a constant.
[RRJ] If these problems were fixed, I believe that Approach 3 would be my
favorite of those above, because it seems to be the most secure
without introducing an unnecessary second encryption step.
[RH] You seem to agree with Burt Kaliski that OAEP is the correct foundation.
However, I believe we can do better yet. Here is my recommended approach,
one that tries to take advantage of all of the tweaks included above.
======================
GENERALIZED KEY WRAPPING ALGORITHM (Version 1)
Criteria:
1. Explicitly define the type of Content Encryption Key and
algorithm to be used in a manner that is independent of the KEK
algorithm type, for example by a ASN.1 structure and designated
algorithm ID, to avoid the N-squared proliferation of algorithm IDs
for various combinations of KEK and CEK types.
2. The Key Wrapping algorithm must be secure against
a number of recently discovered attacks or threats; in particular it
should be possible to securely encrypt a huge (>2^32) number of
CEKs in a single KEK, and vice versa to encrypt a single CEK in a
huge number of KEKs, without any significant possibility of information
leakage that might be caused by a birthday attack, i.e., two pieces of
matching cipher text revealing something about the plaintext.
3. In particular, the key wrapping format should not contain
any stereotyped or common information in the plaintext, whether in
the form of key parity bits, encryption padding bits, or other constant
information. Instead, some form of encryption or whitening should be
used to hide or mask such common information. The whitening must
be unique for each wrapped key.
4. The key wrapping technique should be secure according
to these criteria, regardless of whether the algorithm is a symmetric
or an asymmetric one. In particular, the key wrapping should be as
good as OAEP when used with an asymmetric key. (Since I don't
consider myself to be very strong in this area, I'll leave it up to the
crypto-mathematicians to tell me whether I have achieved this goal.)
TO ENCRYPT:
1. Generate a random Content Encryption Key of an appropriate
key length. Fix up parity bits and/or any other constraints imposed by
the CEK algorithm.
2. Wrap the key plus any other required parameters in a descriptive
ASN.1 structure which includes the CEK algorithm ID, with the resulting
string called CEKWRAP. The ASN.1 structure and the various algorithm
IDs are TBD.
3. Add encryption padding bits (zeroes), if and as required by the
algorithm by computing CEKPAD = CEKWRAP || paddingBits
4. Let LCEK = the length of CEKWRAP in bytes, a 16 bit unsigned integer
5. Compute the maximum length of CEKWRAP plus padding:
LCEKPAD = LCEK + maximumAlgorithmPadding
6. Compute the length of CEKPAD in SHA-1 blocks:
LCEKSHA= floor(LCEKPAD/20) + 1
7. Generate a 160-bit random nonce, RAND
8. Generate a sequence of LCEKSHA SHA-1 blocks:
R(0) = RAND,
R(1)=SHA-1(R(0)), ..., R(LCEKSHA)=SHA-1(R(LCEKSHA-1))
9. Generate MASK1 = R(1) || R(2) ||...||R(LCEKSHA)
10. Generate the whitened CEK plus padding by computing
CEKWH = MASK1 XOR (CEKPAD)
11. Whiten the RAND: MRAND = SHA-1(CEKWH) XOR RAND
12. Whiten the length: MLCEK = LCEK XOR MRAND, using the most
significant 16 bits of MRAND
13. Generate the string to be encrypted, including the length of the
whitened key: MDATA = MRAND || MLCEK || CEKPAD
14. Encrypt MDATA using the chosen Key Encryption Key KEK
and the key encryption algorithm. If the algorithm requires an IV, use the
first n bits (as specified by the algorithm) of SHA-1 of the UTF-8 encoding
of
"Generalized Key Wrapping Algorithm, version 1", repeated as necessary
if n>160 bits (as it might be for AES).
TO DECRYPT:
1. Decrypt MDATA using the KEK and appropriate algorithm
2. Extract MRAND (20 bytes)
3. Extract MLCEK (2 bytes)
4. Compute LCEK = MRAND XOR MLCEK (most significant 16 bits)
5. Extract CEKPAD
6. Extract CEKWH from CEKPAD by taking the first LCEK bytes
7. Compute RAND = MRAND XOR SHA-1(CEKWH)
8. Regenerate MASK1 as before, based on the extracted RAND.
9. Extract CEKWRAP by taking the first LCEK from CEKWH XOR MASK1
10. Unwrap the CEKWRAP ASN.1 structure if and as required,
extracting the CEK and algorithm type, plus any other required parameters.
Regards,
Bob
Robert R. Jueneman
Security Architect
Network Security Development
Novell, Inc.
122 East 1700 South
Provo, UT 84606
bjueneman(_at_)novell(_dot_)com
1-801-861-7387