Subject: Re: A New Triple-DES Key Wrap Algorithm

From: Russ Housley <[email-masked]>
Date: Tue, 09 Feb 1999 11:31:55 -0500

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
>[email-masked]
>1-801-861-7387

---

From: Carl Ellison <[email-masked]>
Date: Tue, 09 Feb 1999 23:26:52 -0800

-----BEGIN PGP SIGNED MESSAGE-----

>[RH] Two different IVs is easy.  The zero IVs were suggested by Carl Ellison. 

That's because one constant IV is as good as another, IMHO, and zero is a 
lot easier to get right in a standard.

+------------------------------------------------------------------+
|Carl M. Ellison         [email-masked]     http://www.pobox.com/~cme |
|    PGP: 08FF BA05 599B 49D2  23C6 6FFD 36BA D342                 |
+--Officer, officer, arrest that man. He's whistling a dirty song.-+