Subject: [Ietf-krb-wg] Enctype design

From: [email-masked]
Date: Wed, 9 Dec 2009 16:55:40 -0500 (EST)

MIT is planning an implementation of an enctype using Camellia, which
looks and acts very much like AES.  Our current expectation is that we
will publish an informational RFC about this enctype after the fact.
I'm here to solicit working group opinions on aspects of the new
enctype, lest we inflict anything too awful on the world.

The big question is the cipher mode.  The options are:

1. CTS mode, paralleling AES.  Several people have voiced opposition
to adding another CTS mode enctype, citing the lack of hardware
support for this cipher mode.

2. CBC mode with padding, paralleling DES3.  Sam has raised strong
objections to adding a new padded enctype; see:
http://mailman.mit.edu/pipermail/krbdev/2009-December/008373.html

3. CCM mode (see RFCs 3610 and 5116).  We have code for a prototype
aes-ccm enctype already, so this would be easy for us to implement.
Relative to GCM, CCM has the weaknesses that it does not allow
parallel processing of message blocks (due to the CBC MAC) and that it
disturbs the block alignment of additional data.

4. GCM.  Relative to CCM, GCM has the weakness that nonce reuse
compromises the integrity protection of all messages encrypted using
that key, and not merely the privacy of the two messages encrypted
with that nonce.  Nonces in both cipher modes would typically be 96
bits long, and it is likely that we would randomly generate nonces
without absolutely guaranteeing non-reuse.

If we go with CTS or CBC, we would need to use a hash.  This is a
little awkward because NIST is working on standardizing a SHA-3 hash
but won't be done until 2012.  The best current candidate is probably
SHA-256, but the AEAD modes are attractive in that they allow us to
skip the SHA-2 family, which is viewed by some as transitional.

A possible issue with AEAD modes is that neither CCM nor GCM support
the interleaving of additional and encrypted data; that is, if you
have a message which looks like A1 | M1 | A2 | M2, CCM or GCM will
authenticate A1 | A2 | M1 | M2.  We do not expect this to be a serious
issue as we expect most users of iov-style encryption to be using
fixed packet formats, which precludes an attacker from tricking an
endpoint into reordering blocks.

Currently we are internally favoring CCM.

Another question is whether we want to do anything differently with
key derivation.  When deriving 256-bit keys for the current AES
enctypes, we encrypt an n-folded constant once to produce the first
128 bits, and then encrypt those 128 bits again to produce the rest.
An alternative might be n-folding the constant to 256 bits and
encrypting that with ECB (or CBC, though I don't see the point), which
would allow such keys to be derived inside a PKCS11 token with the
CKM_AES_ECB_ENCRYPT_DATA mechanism.

It's not yet clear to me that there is any great value in this.  As
Sam pointed out, if you have a non-extractable long-term key inside a
PKCS11 token, and an attacker gets root on your machine, the attacker
can cause the token to spit out the bits of all useful derivations of
the key by asking it to encrypt specific nfolded constants.  But I
thought I would raise the issue, especially because I've heard Sam
express a certain amount of discomfort with our current "encrypt, then
encrypt the result" method of producing random bits.
_______________________________________________
ietf-krb-wg mailing list
[email-masked]
https://lists.anl.gov/mailman/listinfo/ietf-krb-wg

---

From: Tom Yu <[email-masked]>
Date: Wed, 09 Dec 2009 20:56:02 -0500

> support for this cipher mode.

The main performance penalty of CTS is from decrypting ciphertext that
is not a multiple of the block size in length.  In this case, if using
a hardware-accelerated CBC implementation, CTS decryption would incur
an additional CBC setup penalty to handle the final two blocks.  For
short CTS messages, this can halve the performance compared to
ordinary CBC decryption.

> disturbs the block alignment of additional data.

The word alignment of the additional authenticated data can be
restored by prepending padding bytes to the additional data as an
additional formatting step, ensuring that the application-submitted
additional data end up fall on a cipher block or machine word
boundary.  Of course, this increases the length extension caused by
the AEAD mode.

> Currently we are internally favoring CCM.

Some benchmarks indicate that CCM performs more poorly than CBC,
reflecting the fact that CCM conceptually requires two block cipher
invocations per cipher block of plaintext or ciphertext, while CBC
requires only one.  However, CCM can achieve some performance increase
by using parallelism, unlike CBC + HMAC, where both the encryption
function and the authentication function are inherently serial.

> encrypt the result" method of producing random bits.

If the attacker does not compromise the cryptographic module, and the
key derivation function involves more than encrypting some chosen
plaintext using the non-extractable key, the attacker may not be able
to get all the useful derivations of that key.
_______________________________________________
ietf-krb-wg mailing list
[email-masked]
https://lists.anl.gov/mailman/listinfo/ietf-krb-wg

---

From: Sam Hartman <[email-masked]>
Date: Wed, 16 Dec 2009 12:13:44 -0500

My personal preference at the WG level would be for us to focus
standardization efforts on GCM rather than CCM:

1) better performance than CCM
2) Avoids the word alignment issue.

However, I seem to be much less worried about the nonce reuse issue than
other people do.  I'm wondering if I'm missing something.

That said, I certainly don't object to an informational RFC on a CCM
mode being published.  I think CCM and GCM are both reasonable ways
forward.
_______________________________________________
ietf-krb-wg mailing list
[email-masked]
https://lists.anl.gov/mailman/listinfo/ietf-krb-wg

---

From: Greg Hudson <[email-masked]>
Date: Wed, 16 Dec 2009 13:27:44 -0500

> other people do.  I'm wondering if I'm missing something.

I have some more thoughts on this.  NIST SP 800-38D states:
        
        The probability that the authenticated encryption function ever
        will be invoked with the same IV and the same key on two (or
        more) distinct sets of input data shall be no greater than
        2^-32.

(That document uses IV and nonce interchangeably, as far as I can tell;
see section 5.2.1.1.)  The precise math on the birthday paradox is a
little bit above my pay grade, but I believe for a randomly generated
96-bit nonce, the probability of a collision will approach 2^-32 around
when the number of nonces reaches 2^32, as there are ~2^63 pairings at
that point.  Indeed, the NIST document goes on to state that for a
randomly-generated nonce of any size:
        
        The total number of invocations of the authenticated encryption
        function shall not exceed 2^32, including all IV lengths and all
        instances of the authenticated encryption function with the
        given key.

As Tom noted to me recently, RFC 3961 does not place any limits on the
number or size of encryptions performed with a given key.  In practice,
a keytab or password which isn't changed for a long time, or which is
used heavily, could wind up being used for an unlimited number of
encryptions.  It might also be possible to induce a party to generate a
large number of encryptions with a particular key, such as performing a
large number of TGS-REQs for the same principal.

Of course, there may be problems of similar magnitude for other enctypes
(real and hypothetical).  A CCM-based enctype would expect to see a
nonce collision with the same probability, although the consequences are
less severe.  After 2^32 encryptions with an AES enctype, you'd expect
to see a collision in the hash output with about 2^-32 probability; such
a collision could allow an attacker to substitute one ciphertext for
another, which is still less severe but is a compromise.