Subject: Re: [Ietf-krb-wg] Assignments for Camellia-CCM enctypes

From: Ken Raeburn <[email-masked]>
Date: Tue, 5 Oct 2010 02:39:40 -0400

On Sep 16, 2010, at 16:17, Sam Hartman wrote:
> Ken, can I get you to separate issues you see as blocking as the IANA
> expert from issues you're making as individual comments.
> 
> For example it seems kind of odd for the IANA expert to block on whether
> a new simplified profile is defined or on whether they just define a new
> enctype without a profile.  Obviously, if a documented attempted
> incorrectly to use a profile, that would be something where blocking
> comments would be reasonable.

Of course; sorry about that.  Looking over the Designated Expert Review criteria written up in RFC 5226, the main blocking issues fall under the categories of documentation clarity and ability to ensure interoperability, and consistency with the basic architecture.

Documentation clarity and interoperability issues:

* The text and tables in section 5 say two different things.  The tables alone might barely be enough for a spec, but the contradictory text is a problem.

* The undefined "Flags" stuff.

* "B0" in decryption.

* Lack of test vectors.

Architectural consistency:

* The assumption that we can put such limits on plaintext or ciphertext message sizes is, I believe, new.  We do have a limit in the current Kerberos protocol transports, but we also have means to provide future extensions in the transport specs that could work around that, the limits are higher than what the Camellia-CCM spec permits, and not all uses of Kerberos cryptosystems are for messages that need to fit over that protocol anyways.  Nothing in the Kerberos specifications allows for a cryptosystem to refuse to encrypt or checksum a message that's too big.

Ken
_______________________________________________
ietf-krb-wg mailing list
[email-masked]
https://lists.anl.gov/mailman/listinfo/ietf-krb-wg

---

From: Tom Yu <[email-masked]>
Date: Tue, 05 Oct 2010 09:33:48 -0400

Ken Raeburn <[email-masked]> writes:

> * The assumption that we can put such limits on plaintext or
> ciphertext message sizes is, I believe, new.  We do have a limit in
> the current Kerberos protocol transports, but we also have means to
> provide future extensions in the transport specs that could work
> around that, the limits are higher than what the Camellia-CCM spec
> permits, and not all uses of Kerberos cryptosystems are for messages
> that need to fit over that protocol anyways.  Nothing in the
> Kerberos specifications allows for a cryptosystem to refuse to
> encrypt or checksum a message that's too big.

I agree that this is formally a new architectural requirement, but
it's one that is perhaps overdue.

There is an implicit upper bound on the quantity of plaintext that our
cryptographic primitives can safely process: SHA-1 has an explicitly
stated maximum of 2**64 bits of input because it appends a length
encoding to its input, as I recall; 64-bit block ciphers in CBC mode
should not be used to encrypt more than about 2**32 blocks to avoid
ciphertext block collisions; etc.

Practically speaking, there is very limited utility in using
authenticated encryption (or MACs) for protecting transient messages
whose lengths are substantial multiples of the delay-bandwidth product
of your link.  Are the limits imposed by CCM mode approaching that
number for reasonably likely network paths between Kerberos-using
endpoints?  Protecting data at rest is not really what Kerberos is
intended for...
_______________________________________________
ietf-krb-wg mailing list
[email-masked]
https://lists.anl.gov/mailman/listinfo/ietf-krb-wg

---

From: Ken Raeburn <[email-masked]>
Date: Tue, 5 Oct 2010 22:20:37 -0400

> it's one that is perhaps overdue.

I won't argue with that; in fact I think I've even suggested it before.  Maybe this is the time to get into it?

> encoding to its input, as I recall;

Good point.  Still, one could argue that 2 exabytes is not a limitation for Kerberos crypto messages in practice, while 16 megabytes may well be within the range of not-entirely-unreasonable applications.

> 64-bit block ciphers in CBC mode

True, but we don't actually specify that you can't do it.

> endpoints?  Protecting data at rest is not really what Kerberos is

I'm not sure -- nor am I sure it's really going to be a determining factor in protocol design, compared with issues like logical message boundaries (messages might unexpectedly be very large), endpoint buffer memory use (which would probably also encourage smaller sizes regardless of BDP), etc.

Within the main Kerberos protocol itself, it's only likely to come up if you include very large application messages, or do something really obnoxious with some of the variable-sized fields like authorization data (or even principal names), neither of which we prohibit.  I can't speak to the other uses of Kerberos crypto (e.g., GSSAPI CFX, rxgk) offhand.

Ken

---

From: Sam Hartman <[email-masked]>
Date: Wed, 06 Oct 2010 11:31:31 -0400

Thinking more about this, I'd argue that adding a significant length
limitation to the Kerberos crypto framework would be an update to RFC
3961 and thus would require a standards action.

I don't consider 2**64 to be a significant limitation.  I do consider
2**35 as a spec-enforced limit to be significant, although I certainly
would not object to an implementation choosing to upper-bound use of CBC
at 2**32 blocks.

I definitely do consider 2**24 to be a significant message size limit.
So, if we're going to make that limitation I think we need an update to
3961.
_______________________________________________
ietf-krb-wg mailing list
[email-masked]
https://lists.anl.gov/mailman/listinfo/ietf-krb-wg

---

From: Greg Hudson <[email-masked]>
Date: Wed, 06 Oct 2010 12:19:31 -0400

At the expense of message size, we can eliminate the 2^24 length
limitation and also improve on the 2^48 security margin for nonce
collisions.

For example, we could give each CCM message a 32-bit prefix, where one
bit signifies "more messages follow" and the other 31 bits are randomly
generated and are used (together with the protocol key usage value) in
key derivation.  To prevent message reordering, we'd use the additional
data input to the CCM message somehow--say, by prefixing a 64-bit
sub-message number to the user-provided additional data.  So a
camellia-ccm message would look like:

  {1|deriv-constant|CCM-message}{1|deriv-constant|CCM-message}...{0|
deriv-constant|CCM-message}

With this change, enctype messages could be up to 2^88 bits long, and an
attacker would expect to see a nonce collision after gathering 2^63.5
messages; such a collision leaks the xor of the plaintexts of the
colliding messages.  That's comparable to expecting to see a CBC
ciphertext block collision after 2^64 blocks with aes-cts; such a
collision leaks the xor of the plaintexts of the preceding blocks in
each message.

Does this seem like a reasonable direction?  It would mean camellia-ccm
would expand plaintexts by 32 bytes, as opposed to 28 bytes for aes-cts.
It would also mean that each CTR encryption operation in a sequence of
messages would typically use a different key, even if the key usage and
protocol key are the same; this could impact performance in some
settings.

It also occurs to me that we need to think up something cleverer for
cipher state chaining than just preserving the block number.  I don't
have any specific ideas for that at the moment.

---

From: Martin Rex <[email-masked]>
Date: Wed, 6 Oct 2010 18:20:57 +0200 (MEST)

> So, if we're going to make that limitation I think we need an update to

There appears to be a length limitation of 2**16 for the delegated
credential (=TGT) in the Kerberos 5 gssapi mechanism:

   http://tools.ietf.org/html/rfc1964#page-4
   http://tools.ietf.org/html/rfc4121#page-6

due to the use of the 2-octet length field within the checksum
of the KRB_AP_REQ authenticator.

-Martin

---

From: Sam Hartman <[email-masked]>
Date: Wed, 06 Oct 2010 12:36:53 -0400

>>>>> "Martin" == Martin Rex <[email-masked]> writes:

    Martin> There appears to be a length limitation of 2**16 for the
    Martin> delegated credential (=TGT) in the Kerberos 5 gssapi
    Martin> mechanism:

    Martin>    http://tools.ietf.org/html/rfc1964#page-4
    Martin> http://tools.ietf.org/html/rfc4121#page-6

Thanks for pointing this out.
There are certainly limits on this and on certain other messages.

---

From: Sam Hartman <[email-masked]>
Date: Wed, 06 Oct 2010 13:15:34 -0400

Your direction sounds good to me.

---

From: Greg Hudson <[email-masked]>
Date: Wed, 06 Oct 2010 13:20:33 -0400

> limitation and also improve on the 2^48 security margin for nonce

I apologize; I didn't think this through far enough.  Here is a better
proposal for eliminating the 2^24 length limitation (without doing
anything for the 2^48 security margin for nonce collisions; that's now
orthogonal).

RFC 3961 messages have externally defined lengths, as do CCM messages.
The longest possible CCM message with the parameters we have chosen is
2^24 + 28 bytes; we'll call that CCM_MAX.

Therefore, if you receive a camellia-ccm message longer than CCM_MAX
bytes, expect it to be the concatenation of multiple CCM messages, each
of length CCM_MAX except for the last one.  To prevent reordering and
truncation attacks, the authenticated data input to each CCM message
gets a prefix containing the message number and the total number of
messages, conveyed as 64-bit binary values (so together they form one
128-byte block in the CBC-MAC).

---

From: Sam Hartman <[email-masked]>
Date: Wed, 06 Oct 2010 16:04:47 -0400

Your second proposal looks good as well.
_______________________________________________
ietf-krb-wg mailing list
[email-masked]
https://lists.anl.gov/mailman/listinfo/ietf-krb-wg

---

From: Tom Yu <[email-masked]>
Date: Thu, 07 Oct 2010 17:41:19 -0400

> deriv-constant|CCM-message}

I think you would also want to chain the MAC tag from the previous
fragment in the additional data input, to prevent cut-and-paste
attacks from cases such as when an attacker sees multiple fragmented
messages encrypted under the same key.  Maybe chaining a fragment of
the MAC tag is sufficient, though.
_______________________________________________
ietf-krb-wg mailing list
[email-masked]
https://lists.anl.gov/mailman/listinfo/ietf-krb-wg

---

From: Greg Hudson <[email-masked]>
Date: Fri, 08 Oct 2010 11:22:47 -0400

> the MAC tag is sufficient, though.

We can also use that for the RFC 3961 cipher state, instead of the block
counter.  Here's my current thinking:

  * Enctype messages are a concatenation of CCM messages, all but the
last of which is 2^24 + 28 bytes long.

  * Each CCM message receives additional data input consisting of the
previous CCM message's auth tag--or the RFC 3961 cipher state for the
initial CCM message--followed by any user-provided additional data.  If
there are more CCM messages within the enctype message, the bits of the
auth tag are inverted.

  * The RFC 3961 cipher state is the auth tag of the last CCM message
(initially all zeros).

Reordering and cut+paste are foiled by auth tag chaining, while
truncation within an enctype message is foiled by the inversion of the
auth tag inputs for intermediate CCM messages.  The cost of all of this
is one block cipher operation per CCM message during the CBC-MAC.

User-provided additional data is out of scope for RFC 3961, of course.

---

From: Ken Raeburn <[email-masked]>
Date: Tue, 12 Oct 2010 14:43:08 -0400

> counter.  Here's my current thinking:

<designated-expert-mode>

That does appear to fix the length limitation, although if you're using the formatting function from SP300-80C Appendix A (it's not clear, but hinted at by the similar choices of some names), I believe it only supports lengths of *less than* 2^n.

That would just leave the documentation clarity and interoperability issues.

In looking at the draft to see if the associated-data part (not needed functionality for basic Kerberos crypto, but if present it can't be allowed to cause clarity or interop problems) has a similar issue, I note that the encoding for adata_len is not given, though presumably it and Flags could be covered with (explicit, please) references to the CCM specs if you're using their formatting function.  It also appears that "adata" is not actually included in the CBC-MAC invocation in the encryption function as given.

Also:

In the key derivation function, is K0 key-sized or block-sized?  I assume the latter, but it's not stated.

</designated-expert-mode>

As far as the security of the mode goes, I think it's probably fine, though getting review from professional cryptographers more familiar with CCM wouldn't be a bad idea.

If RFC3610 is substantially similar to SP800-38C in its description of CCM mode as used here, it might be a better reference, or at least could be listed as an additional reference for the specification.  Sending someone off to download specs from NIST is okay, but if, like me, they keep a local mirror of the entire RFC archive anyways, it's a bit of a waste.

I do wonder if the 28-byte addition per 2^24 bytes is going to go over well with some implementors, as in the next 2^24 (or less) bytes, each 16-byte block encryption result (for counter mode) gets XORed with a message chunk that is not 16-byte aligned in memory.  (Actually, in each CCM message, the XOR-generated portion starts at offset 12 bytes, after the nonce, so that'll be 12 mod 16 for the first, 8 mod 16 for the second, etc.  RFC 4309 -- AES-CCM for IPsec -- does take this into account when constraining certain parameters, and in the selection of parameter values that must be supported.  Microsoft pushed hard for in-place encryption/decryption for CFX for performance reasons; have they weighed in on this?)

Ken

---

From: Luke Howard <[email-masked]>
Date: Wed, 13 Oct 2010 10:36:04 +1100

> That would just leave the documentation clarity and interoperability issues.

The formatting functions are per the NIST document you cite.

> In the key derivation function, is K0 key-sized or block-sized?  I assume the latter, but it's not stated.

Block

-- Luke

---

From: Greg Hudson <[email-masked]>
Date: Mon, 18 Oct 2010 10:40:11 -0400

On Tue, 2010-10-12 at 14:43 -0400, Ken Raeburn wrote:
> I do wonder if the 28-byte addition per 2^24 bytes is going to go over
> well with some implementors [...]

This is a serious concern, and I thought of it independently.  We want
the enctype to work with IOV encryption, which means there has to be one
header and one trailer of fixed sizes.  So, concatenating CCM messages
won't work.

How about this, then: modify CCM to relax the length restriction by
computing a next nonce if the block counter runs out.  There are a
variety of options for the next-nonce function--it could depend on the
key, the plaintext, and/or the additional data--but I'm not sure if any
of them are better than "the previous nonce plus one" (treating the
nonce as an unsigned 96-bit value) given that we're only changing the
nonce every 2^24 blocks.

---

From: Ken Raeburn <[email-masked]>
Date: Sun, 24 Oct 2010 18:55:00 -0400

> nonce as an unsigned 96-bit value) given that we're only changing the

Seems reasonable to me, so long as integrity protection is maintained.  Got a specific proposal?

How is the authentication tag to be handled?

Ken

---

From: Greg Hudson <[email-masked]>
Date: Mon, 25 Oct 2010 00:17:50 -0400

> Seems reasonable to me, so long as integrity protection is maintained.

I'd like to start with the plan of just incrementing the nonce
(considered as a big-endian 96-bit unsigned value) each time you run out
of counter blocks.  Given that we're using random nonces, I don't think
this should have a significant impact on the probability of a nonce
collision if you consider the total number of blocks encoded.

> How is the authentication tag to be handled?

There is a snag here which I hadn't thought of, and I can think of two
ways to handle it.  The authentication tag is the CBC-MAC of:

  B0 | associated_len | associated_data | plaintext

where associated_len is encoded in 2, 6, or 10 bytes, and can have
values up to 2^64.

There's no intrinsic length limitation to a CBC-MAC, but the definition
of B0 is problematic; it's {flag_byte | nonce | plaintext_len} where
plaintext_len is supposed to fit into 3 bytes.  So in order to relax the
length restriction, we have to fix this as well.

The simplest fix is to encode plaintext_len mod 2^24.  This fix has the
desirable property of incurring no change for normal-length messages.  I
believe the length ambiguity would be pretty harmless--I don't see how
an attacker could truncate multiples of 2^24 bytes off of a message
without changing the CBC-MAC--but that might bear further study.

A more conservative fix is to encode the "real" (possibly >2^24)
plaintext length and treat it as part of the associated data, so:

  B0 | associated_len | {plaintext_len | associated_data} | plaintext

where associated_len would be the length of the braced expression (so
the length of associated_data plus 2, 6, or 10 bytes for the
plaintext_len).

Taking a step back here: the best alternative I see to CCM is CTS with
CMAC for integrity.  CTS has been rightly criticized as being
complicated and not fitting well into cryptography APIs, but the same
could perhaps be said for CCM.  So I'm still internally weighing the
complexity of CCM versus CTS+CMAC, and each of these tweaks we're having
to make to CCM obviously affects that side of the weight.

---

From: Sam Hartman <[email-masked]>
Date: Mon, 25 Oct 2010 13:16:51 -0400

I'd support taking a proposal like this to CFRG for review.

--Sam