Subject: Re: [kitten] considering abandoning CTS mode (Re: I-D Action: draft-ietf-kitten-aes-cts-hmac-sha2-01.txt)

From: Sam Hartman <[email-masked]>
Date: Thu, 01 Aug 2013 08:38:18 -0400

Hi.
I've read all the discussions on this thread, and with my chair hat on,
a few points seem to have been made and not really considered.

1) we have not evaluated CTR mode. We looked at CCM and GCM, but have
not looked at CTR with an HMAC.
Just pointing out that we have not thoroughly considered the options.

2) You don't need to implement the short plaintext special case if you
implement Kerberos and GSS-API.  You need  to implement it only if you
expose a general RFC 3961 API and choose to support short plaintexts in
that that API.

3) Speaking as someone involved at the time, making sure that no more
than 8 bytes of expansion were included in the AES enctypes was a
critical consideration to gaining consensus and to developing RFC 4121.

The chairs will need to discuss how to approach consensus on this document.

---

From: Greg Hudson <[email-masked]>
Date: Thu, 01 Aug 2013 10:17:06 -0400

> Just pointing out that we have not thoroughly considered the options.

If I understand how CTR+HMAC would work, the same problems exist for
CTR+HMAC as for CCM: the 128-bit block size of AES is not big enough for
a random nonce and a block counter, given the requirements for maximum
message size and the requirements for confidence of nonce uniqueness.

> expose a general RFC 3961 API and choose to support short plaintexts in

I don't think that's an interesting fact for my MIT krb5, and I would
speculate that it's not interesting fact for any Kerberos
implementation.  This is a 3961 enctype, and if we implement it, we
would want to implement it generally.  We have internal uses of 3961
which involve short plaintexts, and we know of other 3961 consumers such
as OpenAFS.

> critical consideration to gaining consensus and to developing RFC 4121.

[Sam clarified online that he meant no more than 8 bytes of variable
expansion; fixed expansion beyond 8 bytes is okay.  I think he may have
meant 3962 rather than 4121.]

I would welcome additional information on this.  I am not at all
comfortable with the position that, essentially, the burden of proof is
on anyone who doesn't want to meet this technical requirement, the
rationale for which has never been concretely described on the mailing
list.  When we searched the archives for discussion of the rationale for
CTS in RFC 3962, all we found is suggestions from Ken that it would save
some space (which was also presumably the reason for truncating the HMAC
to 96 bits).

Also, I would like a clarification on Sam's earlier statement (July 17)
that:

> We're at a point in the process where the presumption is that we will
> not make a given change unless consensus is demonstrated to make the
> change.

Was there a WG last call on this draft?  (I wasn't able to find one in
the archives, but I think Sam mentioned a "second last call" at some
point during the meeting.)  When did it reach this point in the process
if not?

---

From: Kelley Burgin <[email-masked]>
Date: Fri, 2 Aug 2013 08:32:11 -0400

Sam,

I understand you've set the bar high for moving to CBC+padding from CTS mode. I believe we can provide the necessary justifications and assurance to move to CBC+padding, but I'm still unclear what the actual hurdles are. 

Would you provide your concerns? In particular, I'd like to hear the reason for limiting variable expansion to 8 bytes (your point 3 below). Seems like the reasons I can imagine are no longer relevant.

Kelley

---

From: Love Hörnquist Åstrand <[email-masked]>
Date: Fri, 2 Aug 2013 14:41:09 +0200

Kelly,

Legacy DCE-RPC appellations that didn’t query unlaying DCE crypto layer to see what the padding layer is and just sent in 8 as a padding/extra block, since that worked with both DES and RC4.

You better ask the msft folks if this still is an issue.

Love

2 aug 2013 kl. 14:32 skrev Kelley Burgin <[email-masked]>:

> _______________________________________________
> Kitten mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/kitten

---

From: Benjamin Kaduk <[email-masked]>
Date: Tue, 6 Aug 2013 17:13:39 -0400 (EDT)

On Fri, 2 Aug 2013, Love Hörnquist Åstrand wrote:

> Kelly,
>
> Legacy DCE-RPC appellations that didn’t query unlaying DCE crypto layer 
> to see what the padding layer is and just sent in 8 as a padding/extra 
> block, since that worked with both DES and RC4.
>

Tom's message from 10 July 
(http://www.ietf.org/mail-archive/web/kitten/current/msg04114.html) 
indicates that "The most recent information I have from Microsoft (from a 
few months ago in private mail) is that it would only be a problem for 
legacy applications that aren't using the SSPI correctly.

To me, that appears to address your concerns.

-Ben

---

From: Love Hörnquist Åstrand <[email-masked]>
Date: Tue, 6 Aug 2013 23:45:01 +0200

6 aug 2013 kl. 23:13 skrev Benjamin Kaduk <[email-masked]>:

> Tom's message from 10 July (http://www.ietf.org/mail-archive/web/kitten/current/msg04114.html) indicates that "The most recent information I have from Microsoft (from a few months ago in private mail) is that it would only be a problem for legacy applications that aren't using the SSPI correctly.
> 

That doesn’t address the the concern. msft needs to pipe up and say if this is would be a issue for them and if they would not implement this draft.

Love

---

From: Nico Williams <[email-masked]>
Date: Tue, 6 Aug 2013 16:45:58 -0500

On Tue, Aug 6, 2013 at 4:13 PM, Benjamin Kaduk <[email-masked]> wrote:
>> Legacy DCE-RPC appellations that didn’t query unlaying DCE crypto layer to
>> see what the padding layer is and just sent in 8 as a padding/extra block,
>> since that worked with both DES and RC4.
>>

Well, it's "hearsay", but we can't just wait forever.  Speaking for
myself, not for Love, my concern would be addressed by the chairs
seeing to it that Microsoft is notified.  Then we can start WGLC
immediately and Microsoft will have the usual WGLC and IETF LC to
comment.

Nico
--

---

From: Kelley Burgin <[email-masked]>
Date: Wed, 7 Aug 2013 08:36:57 -0400

Based on the history of the draft, it seems like we can assume Microsoft will not pipe up. Given this assumption, I like Nico's plan to put the burden on Microsoft to come forward if they have complaints instead of putting the (destined to fail) burden on us to get them to reply.

Kelley

---

From: Josh Howlett <[email-masked]>
Date: Wed, 7 Aug 2013 13:22:29 +0000

Anyone object to this?

Josh.

--
IETF Kitten co-chair

On 07/08/2013 13:36, "Kelley Burgin" <[email-masked]> wrote:

>Based on the history of the draft, it seems like we can assume Microsoft
>will not pipe up. Given this assumption, I like Nico's plan to put the
>burden on Microsoft to come forward if they have complaints instead of
>putting the (destined to fail) burden on us to get them to reply.
>
>Kelley
>
>>>> Legacy DCE-RPC appellations that didn¹t query unlaying DCE crypto
>>>>layer to

Janet(UK) is a trading name of Jisc Collections and Janet Limited, a 
not-for-profit company which is registered in England under No. 2881024 
and whose Registered Office is at Lumen House, Library Avenue,
Harwell Oxford, Didcot, Oxfordshire. OX11 0SG. VAT No. 614944238

---

From: Tom Yu <[email-masked]>
Date: Wed, 07 Aug 2013 12:39:23 -0400

> Josh.

I don't object, but I can try to ask some of our Microsoft contacts
specifically about the DCE-RPC issue.  It's possible that they
interpreted some of my previous queries solely in an SSPI context.

Also, do I recall correctly that Luke was going to do some research on
this?  I've been trying to get some answers by reading DCE C706, but
it's not easy.

---

From: Nico Williams <[email-masked]>
Date: Wed, 7 Aug 2013 12:20:31 -0500

> Anyone object to this?

Well, following IETF process can't be objectionable :)  Two weeks for
WGLC and four for IETF LC should be plenty of time.  The addition of
personally reaching out to whoever
might-not-be-but-should-be-paying-attention is not required but is
certainly the right thing to do here.  But that's it, if we get no
comments in that period (and, really, right up till final publication,
so much more than just 6 weeks), then that's it.

Nico
--

---

From: Benjamin Kaduk <[email-masked]>
Date: Wed, 7 Aug 2013 17:21:17 -0400 (EDT)

On Fri, 28 Jun 2013, [email-masked] wrote:

>
> A New Internet-Draft is available from the on-line Internet-Drafts directories.
> This draft is a work item of the Common Authentication Technology Next Generation Working Group of the IETF.
>
> 	Title           : AES Encryption with HMAC-SHA2 for Kerberos 5
> 	Author(s)       : Kelley W. Burgin
>                          Michael A. Peck
> 	Filename        : draft-ietf-kitten-aes-cts-hmac-sha2-01.txt
> 	Pages           : 15
> 	Date            : 2013-06-28
>
> Abstract:
>   This document specifies two encryption types and two corresponding
>   checksum types for Kerberos 5.  The new types use AES in CTS mode
>   (CBC mode with ciphertext stealing) for confidentiality and HMAC with
>   a SHA-2 hash for integrity.
>
>
> The IETF datatracker status page for this draft is:
> https://datatracker.ietf.org/doc/draft-ietf-kitten-aes-cts-hmac-sha2
>
> There's also a htmlized version available at:
> http://tools.ietf.org/html/draft-ietf-kitten-aes-cts-hmac-sha2-01

I've reached this document in my process of going through all the 
documents mentioned in the kitten slides from Berlin, but don't think it's 
worth the time to do the review until the cts vs. cbc question is 
resolved.  Sam, I think this is blocking on your historical recollections; 
do you have an estimate for when you'll be able to send them to the list?

Thanks,

Ben

---

From: Luke Howard <[email-masked]>
Date: Thu, 8 Aug 2013 09:15:29 +1000

> this?  I've been trying to get some answers by reading DCE C706, but

Yeah, and you won't find it there because GSS wasn't in the original DCE RPC spec (only raw Kerberos). Instead I think you want [MS-RPCE] 2.2.2.11 which says the auth trailer must be 4 byte aligned, and that it's OK to zero fill the trailer if you over-allocated.

I'm a bit skeptical about the 4 byte alignment in practice. In the last implementation I worked on, I made the following note:

/*
 * [MS-RPCE] states that the stub data is padded to the underlying
 * blocksize (or four bytes, if that is greater). In practice they
 * use the underlying keysize when the blocksize is one. For now,
 * a constant 16 bytes works for all known ciphers and mechanisms
 * (at the expense of 8 bytes extra padding for DES), but we should
 * eventually fix it to use gss_context_query_attributes().
 */

-- Luke

---

From: Luke Howard <[email-masked]>
Date: Thu, 8 Aug 2013 09:38:59 +1000

> Yeah, and you won't find it there because GSS wasn't in the original DCE RPC spec (only raw Kerberos). Instead I think you want [MS-RPCE] 2.2.2.11 which says the auth trailer must be 4 byte aligned…

To be clear: the DCE RPC auth padding is at the application layer so it's orthogonal to any Kerberos padding. (NB: for pre-RFC 4121 enctypes such as RC4/DES, PKCS#7 padding is disabled; presumably a putative MS implementation wouldn't do this for RFC 4121 enctypes that require padding.)

The salient point from [MS-RPCE] is that the trailer can be variable length (because it's OK to zero fill if you over-allocated). So you can have a variable length filler (RFC 4121 s.4.2.4) containing the PKCS#7-ish padding.

I think we're good to go!

-- Luke

---

From: Luke Howard <[email-masked]>
Date: Thu, 8 Aug 2013 14:10:17 +1000

> To be clear: the DCE RPC auth padding is at the application layer so it's orthogonal to any Kerberos padding. (NB: for pre-RFC 4121 enctypes such as RC4/DES, PKCS#7 padding is disabled; presumably…

Well, almost orthogonal. Maybe at right angles or something. :-)

It's not orthogonal in the sense that: if the DCE RPC auth padding pads the PDU to the underlying block size, then you can guarantee that the auth trailer will be a constant size. But, as I mentioned in my earlier message, because [MS-RPCE] permits variable length trailers by allowing the trailer length to be over-allocated, constant size is not a requirement.

According to the spec, you could align to a 4 byte boundary and do any additional padding  in the RFC 4121 filler (which after rotation ends up in a single token, placed in the auth trailer). Whether Microsoft's implementation uses 4 bytes, I'm unsure although it should be possible to instrument our SSP to determine this.

Now, there are bugs in Microsoft's RFC 4121 implementation when DCE is in effect: even though no padding is required for CTS, their implementation rejects non-zero EC, and miscalculates the RRC. Not being privy to their implementation, I cannot say whether this would carry over to any future enctypes.

-- Luke

PS. http://code.metager.de/source/xref/dcerpc/dcerpc/ncklib/gssauthcn.c if anyone wants to see an implementation.

---

From: Luke Howard <[email-masked]>
Date: Thu, 8 Aug 2013 15:08:57 +1000

> Well, almost orthogonal. Maybe at right angles or something. :-)

Um. 45 degrees. Obviously it's a long time since I've used a protractor.

-- Luke

---

From: Sam Hartman <[email-masked]>
Date: Mon, 12 Aug 2013 10:18:58 -0400

Hi.
I have this Wednesday scheduled for IETF tasks including this writeup.

---

From: Sam Hartman <[email-masked]>
Date: Wed, 14 Aug 2013 13:40:47 -0400

>>>>> "Greg" == Greg Hudson <[email-masked]> writes:

    Greg> On 08/01/2013 08:38 AM, Sam Hartman wrote:
    >> 1) we have not evaluated CTR mode. We looked at CCM and GCM, but
    >> have not looked at CTR with an HMAC.  Just pointing out that we
    >> have not thoroughly considered the options.

    Greg> If I understand how CTR+HMAC would work, the same problems
    Greg> exist for CTR+HMAC as for CCM: the 128-bit block size of AES
    Greg> is not big enough for a random nonce and a block counter,
    Greg> given the requirements for maximum message size and the
    Greg> requirements for confidence of nonce uniqueness.

However, CTR unlike CCM doesn't specify the breakdown.
You could for example pick a random counter for each message.
So, the question is whether 128-bits is big enough to get you the
uniqueness probability you desire.

    >> 2) You don't need to implement the short plaintext special case
    >> if you implement Kerberos and GSS-API.  You need to implement it
    >> only if you expose a general RFC 3961 API and choose to support
    >> short plaintexts in that that API.

    Greg> I don't think that's an interesting fact for my MIT krb5, and
    Greg> I would speculate that it's not interesting fact for any
    Greg> Kerberos implementation.  This is a 3961 enctype, and if we
    Greg> implement it, we would want to implement it generally.  We
    Greg> have internal uses of 3961 which involve short plaintexts, and
    Greg> we know of other 3961 consumers such as OpenAFS.

Neither Microsoft nor Java provide access to RFC 3961.
They are both widely deployed implementations of Kerberos.
I agree that MIT provides access to a RFC 3961 API.

To be clear I'm not making any specific proposal; I don't have an
opinion on whether I favor CTR as an example.
As a chair though, I have an obligation to make sure we reach an
informed consensus so I'm trying to get everything out on the table.

---

From: Greg Hudson <[email-masked]>
Date: Wed, 14 Aug 2013 15:21:19 -0400

> You could for example pick a random counter for each message.

I'm not sure how "a random counter for each message" could mean anything
different from the "random nonce" I referred to above.  This may mean
that I was unclear, so I will expand on what I meant.

Each block of message plaintext needs to be assigned a 128-bit counter
value, somehow, and we want (at a minimum) a probabilistic guarantee
that the same counter value will not be used for the same key.  In
Kerberos, the same long-term key is used for many messages in an
uncoordinated fashion, so the best we can do is pick a random counter
value and transmit it along with the message in the header.  If we could
use the full 128-bit space for this choice, then we would expect a
birthday attack to succeed after an attacker observes around 2^64
messages.  This is not so bad; in CBC mode we also start leaking
information about plaintexts once a cipher block collision occurs.

However, RFC 3961 messages can be more than one block long; in fact, RFC
3961 says that messages can have "arbitrary size."  So, we have to
decide what counter value to use with blocks after the first one.  Some
obvious options are:

1. Reserve some of the counter bits for a block counter, e.g. 96 bits
for the random component and 32 bits for the counter.  This decreases
the expected number of messages before a birthday attack would succeed
to something on the order of 2^48 messages, and also places a limit on
the length of each message.

2. Apply a predictable function, such as 128-bit increment, to the
current block's counter to produce the next one.  Do not restrict the
choice of the initial counter; instead, try to reason about the
probability that the Nth block of one message has a counter collision
with the Mth block of another message.

3. Pick a new random counter value for each block, and transmit it along
with the ciphertext.  This yields a 100% ciphertext expansion (or a bit
more than that if the final plaintext block is short).

Option 1 is essentially what CCM and GCM do.  Option 2 could be
considered novel (although you could also characterize it as just CTR
with the counter XOR'd with the nonce), and I do not immediately know
what probabilistic guarantees it would have.  Option 3 seems strictly
more likely to be incompatible with SSPI consumers than padded CBC is.

As an aside, Luke has suggested in the past that we specify a CCM or GCM
enctype and restrict its use to short-lived subkeys in sequential
protocols (basically, as a result of RFC 4537 negotiation).  However,
this would not satisfy the motivating the current enctype proposal; we
would still need something appropriate for use with long-term keys.
Also, I'm not sure if I have good ways in MIT krb5 implementation to
ensure that such an enctype is only used in a secure fashion.

---

From: Simo Sorce <[email-masked]>
Date: Wed, 14 Aug 2013 15:35:17 -0400

> with the Mth block of another message.

If you simply increment and you have 1 collision, then you have a stream
of collisions for all the remaining blocks of both messages after the
collision, as they all have the counter increment the same way.

Or did I misunderstand something in the way you propose to increment the
random counter ?

I am not sure whether it helps to avoid multiple collisions, but if it
does then perhaps what you could do is use a PRNG that is seeded by the
random counter and guarantee that different seeds produce completely
different sequences, ie even if at some point there is a counter
collision, the next pseudo-random counter would be different anyway as
long as the initial seed was different. this may be obtained perhaps by
combining the initial seed with the result of the defined pseudo random
function for each block.

Simo.

-- 
Simo Sorce * Red Hat, Inc * New York

---

From: Nico Williams <[email-masked]>
Date: Wed, 14 Aug 2013 14:36:47 -0500

> information about plaintexts once a cipher block collision occurs.

We've discussed GCM and such modes before.  My opinion is that if
we're to use such a mode we should:

a) use a 256-bit IV, (or even 192?) using at least 128 of those bits
to derive an encryption key,
b) using some of the remaining 128 bits as a nonce to be held constant
for all uses of the derived key,
c) and using the remaining bits as a block counter

That would give us enough bits with which to ensure no duplicate
key+IV usage using: a) a high-resolution timestamp, b) a boot counter
or timestamp, c) a random nonce.

> ensure that such an enctype is only used in a secure fashion.

Agreed, that'd be a nice solution but it has those problems.

Nico
--

---

From: Sam Hartman <[email-masked]>
Date: Wed, 14 Aug 2013 15:40:25 -0400

>>>>> "Greg" == Greg Hudson <[email-masked]> writes:
    Greg> 2. Apply a predictable function, such as 128-bit increment, to
    Greg> the current block's counter to produce the next one.  Do not
    Greg> restrict the choice of the initial counter; instead, try to
    Greg> reason about the probability that the Nth block of one message
    Greg> has a counter collision with the Mth block of another message.

This is what I was talking about.

It's something we haven't thought about before.
I don't know if it would be acceptable, nor am I personally either
advocating it nor asking that we evaluate it.

---

From: Sam Hartman <[email-masked]>
Date: Wed, 14 Aug 2013 15:44:54 -0400

Derek, after the  Berlin meeting, you asked me some questions about CBC
timing attacks and the new aes-cbc-hmac-sha2 proposal.
I didn't know the answers.
Any chance you could write that up here so we can discuss?

---

From: Derek Atkins <[email-masked]>
Date: Fri, 16 Aug 2013 09:46:11 -0400

Hi,

> Any chance you could write that up here so we can discuss?

The issue was a question of whether it would be subject to the same
timing attacks as Lucky13 used against SSL/TLS.  The issue there was
that an attacker could distinguish timing differences because padding
changes could cause changes in the amount of padding data checked and
also the number of MAC rounds performed.

For example, in TLS you can pad from 0 to 255 bytes.  If you assume the
ciphertext is a constant length an attacker could use this to time the
difference in processing time of different pad lengths, which can lead
to disclosure of data and possibly keys.

The main questions are whether changes in pad length could affect the
number of rounds in the MAC process, and whether you have a
constant-time padding checker, regardless of the actual number of pad
bytes.  I.e., Lucky13 was successful because the MAC (and possibly
padding checks) were not constant-time based on the ciphertext length.

-derek

-- 
       Derek Atkins, SB '93 MIT EE, SM '95 MIT Media Laboratory
       Member, MIT Student Information Processing Board  (SIPB)
       URL: http://web.mit.edu/warlord/    PP-ASEL-IA     N1NWH
       [email-masked]                        PGP key available

---

From: Greg Hudson <[email-masked]>
Date: Fri, 16 Aug 2013 10:35:45 -0400

On 08/16/2013 09:46 AM, Derek Atkins wrote:
> timing attacks as Lucky13 used against SSL/TLS.

I believe it would not, since it uses encrypt-then-mac.