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

From: Tom Yu <[email-masked]>
Date: Tue, 09 Jul 2013 19:46:25 -0400

I've looked at the diff against the previous version of this document.
Most of the changes look reasonable to me, but the special case
handling of short plaintexts seems too complicated from an
implementation perspective.  I'd prefer to go back to the more widely
accepted practice of CBC mode with explicit IV and PKCS#7-ish padding.

It seems that one of the goals of this effort is to use, as much as
possible, the off-the shelf capabilities of cryptographic modules that
are validated to FIPS 140-2 or other relevant standards.  As far as I
know, few (if any) validated cryptographic modules support CTS mode
directly.

At this point, I think it is useful to try moving away from CTS: the
benefits of CTS do not outweigh the implementation complexity,
particularly when dealing with the short plaintext case.  Implementing
CTS mode has already proven to be a challenge even for the existing
AES-CTS enctypes, and I'm reluctant to magnify that difficulty with
the new enctypes in this document.  Returning to a scheme based on
conventionally padded CBC would further the goal of using the existing
capabilities of validated cryptographic modules, and poses fewer
implementation risks.

Statements from Microsoft imply that the main problems caused by
variable-length ciphertext expansion would be limited to SSPI
applications that do not use the APIs correctly.  SSPI functions exist
such that an application can use to obtain the required lengths for
use with the in-place encryption functions.

I realize we've spent a significant amount of effort trying to make
CTS work in the short-plaintext case.  I'd like to thank to Nico,
Kelley, and others who participated in trying to make CTS mode work in
this specification.  Looking at this document as an implementer, I
think using CTS mode, especially with the short-plaintext special
case, presents too much risk, and I'd like us to consider going back
to a more normal CBC mode.

---

From: Luke Howard <[email-masked]>
Date: Wed, 10 Jul 2013 09:52:59 +1000

The objection to CTR mode is because there is no maximum message size and the counter may wrap, or something else?

-- Luke

---

From: Tom Yu <[email-masked]>
Date: Tue, 09 Jul 2013 20:01:39 -0400

> The objection to CTR mode is because there is no maximum message size and the counter may wrap, or something else?

I'm not sure whether plain CTR mode (with HMAC?) was proposed.  GCM
and CCM each have multiple problems, especially when used with
long-term keys.  Repetition of a GCM IV can lead to forgeries, and I
think there were length encoding issues in both GCM and CCM.  I'd have
to check the archives for details, but I think we discussed them
extensively.

---

From: Tom Yu <[email-masked]>
Date: Wed, 10 Jul 2013 17:04:15 -0400

Nico Williams <[email-masked]> writes:

> If we're going to use GCM/CCM then I would strongly prefer if we had a
> key derivation method that uses a 256-bit IV to derive keys from
> long-term keys (so that we can have enough bits for a nonce, a high-res
> timestamp, a KDC or other ID, and a use counter).  I don't think that's
> a lot to ask for, but it will do more violence to existing
> implementations than a non-confounded CTS mode would, so I would prefer
> a non-confounded CTS mode, but it's a mild preference.

I still think we should avoid GCM or CCM mode.

---

From: Nico Williams <[email-masked]>
Date: Wed, 10 Jul 2013 16:30:46 -0500

> capabilities of validated cryptographic modules, and poses fewer

I'm not at all worried about implementation risks.  We can test every
possible plaintext length between the shortest (zero-bytes) and a
small multiple of the block size (in bytes), both with test vectors
and random data (making sure it round-trips).

I think the only risk we should be concerned about here is the risk
that we might design-in a cryptographic weakness.  I definitely don't
want to be even partly to blame for that :) so it's a risk that
bothers me.  I think we can analyze the non-confounded CTS we came up
with, and we could/should/must ask for review by strong cryptographers
before we go forward with it (or otherwise we must show that the new
thing must have the same properties as the old confounded CTS, which I
think we informally did, but we'd have to redo that analysis).

Another risk I care about is the risk that we lose some hardware
optimizations as a result of using CTS.  Though with the trend towards
on-die hardware cipher implementations that problem becomes much less
relevant.

> use with the in-place encryption functions.

This was a big deal to them once.  It might still be.  It'd be nice to
hear from someone at Microsoft as to whether this is still an issue.

> to a more normal CBC mode.

I'll be fine with ditching the no-padding requirement if the
implementors we've known to care for no-padding modes are ok with it
now and no new ones show up to tell us otherwise.

Nico
--

---

From: Tom Yu <[email-masked]>
Date: Wed, 10 Jul 2013 18:24:23 -0400

> and random data (making sure it round-trips).

I think it's still unavoidably more code, which carries its own risks.

> think we informally did, but we'd have to redo that analysis).

The new CTS constructions are different from what we use for the
current aes-cts-hmac enctypes, and the short-plaintext special cases
are even more different.  If we can make a cryptographic best practice
(CBC with padding, encrypt-then-MAC, explicit random IV, etc.) work
for us, I think that would be better from a cryptographic risk
standpoint.  I'd rather use a construction that's been analyzed
extensively in the literature than use something we invented and maybe
had some cryptographers (even if they're good ones) glance at briefly.

> on-die hardware cipher implementations that problem becomes much less

It could still be a problem for validated hardware security modules,
which I think would be a likely way for Suite B cryptography to be
implemented in practice.

> hear from someone at Microsoft as to whether this is still an issue.

No, I think some non-Microsoft WG participants once believed it to be
a big deal for Microsoft, but we never had any confirmation from
anyone at Microsoft that it was a problem (at least none that I could
find).  The most recent information that 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.

> now and no new ones show up to tell us otherwise.

Thanks.

---

From: Nico Williams <[email-masked]>
Date: Wed, 10 Jul 2013 17:33:37 -0500

> I think it's still unavoidably more code, which carries its own risks.

It's code with very low rates of change.

> had some cryptographers (even if they're good ones) glance at briefly.

So you'd object to even the CTS mode we have in use today?

> which I think would be a likely way for Suite B cryptography to be

Sure, but if they can be used in such a way as to use Suite B modes
then the problem devolves to a performance problem.  (The currently
in-use CTS mode has this property.)

> legacy applications that aren't using the SSPI correctly.

Oh!  Well then, in that case to heck with CTS.  Hurry!  :)

Nico
--

---

From: Tom Yu <[email-masked]>
Date: Wed, 10 Jul 2013 18:47:30 -0400

> So you'd object to even the CTS mode we have in use today?

For new enctypes, I would like us to move toward cryptographic best
practice.  It seems that the Suite B proponents would prefer that as
well.

> in-use CTS mode has this property.)

Yes, you can use a normal CBC implementation to build CTS mode, at the
cost of doubling the setup overhead on decryption (and possibly
encryption), as people who have had to implement CTS on top of HSM
type interfaces have told me.

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Wed, 10 Jul 2013 19:09:20 -0400

> legacy applications that aren't using the SSPI correctly.

What about non-legacy applications implementing standards-track
GSS-API-using protocols according to a specification that isn't written
with the SSPI in mind?  It's all well and good to say "call the API to
see what length you should use", but if the protocol says to send a
1025-byte message, then I have to send a 1025-byte message, even if the
SSPI would rather I somehow only send a 1016-byte message.

-- Jeff

---

From: Nico Williams <[email-masked]>
Date: Wed, 10 Jul 2013 18:33:34 -0500

> legacy applications that aren't using the SSPI correctly.

Could we get some details?  Doesn't have to be on-list, since wouldn't
be on-topic.  I'm thinking of a) MSDN links to the relevant SSPI docs
(that is, for the relevant functions), b) examples of correct and
typical incorrect code using them.  I just want to make sure before we
leave one implementor unhappy.

Nico
--

---

From: Greg Hudson <[email-masked]>
Date: Wed, 10 Jul 2013 19:42:18 -0400

On 07/10/2013 05:30 PM, Nico Williams wrote:
> I'm not at all worried about implementation risks.

I disagree.

The RFC 3962 enctypes have an exception case when the plaintext is the
empty string.  Both MIT's and Heimdal's implementation do the wrong
thing with the output cipher state in this case.  A more comprehensive
suite of test vectors would have helped, but there's no guarantee that
someone designing such a suite would have thought to combine cipher
state with a zero-length input, or would have interpreted the spec
correctly if they did.

Nobody appears to care, because encrypting the empty string is rare and
using cipher state is also rare, but the lesson remains that even in
rarely-changing code, there are implementation risks to having a
complicated specification.

Details: RFC 3962 adds a confounder to the input, so there is always at
least one block to encrypt.  If the input plaintext length is 0, then
there is exactly one block to encrypt.  RFC 3962 section 4 specifies
that "If exactly one block is to be encrypted, that block is simply
encrypted with AES (also known as ECB mode)."  Section 6 specifies the
encryption/decryption functions as "AES in CBC-CTS mode (cipher block
size 16 octets), with next-to-last block (last block if only one) as
CBC-style ivec."  One could possibly interpret section 4 as saying that
the input state should be ignored, although that would be bogus.  In any
event, it's clear from section 6 that the output state should be the
last (and only) block of ciphertext.  What actually happens, in both MIT
and Heimdal, is that the cipher state is neither used nor modified.

---

From: Nico Williams <[email-masked]>
Date: Wed, 10 Jul 2013 19:09:21 -0500

> complicated specification.

Interesting.  Only Kerberos applications that use the Kerberos
cryptosystem directly and *chain( encryptions are affected.  Not GSS
apps, for example, nor apps that use any Kerberos PDUs.

In any case, I stand by what I said.  I find the cryptographic
vulnerability risk of much higher concern.  There's no point to
properly implementing a broken algorithm.

> and Heimdal, is that the cipher state is neither used nor modified.

This is good to know.

This doesn't really change my opinion, but that will be moot anyways
once we have the details showing that we don't have to worry about not
padding for SSPI apps.

Nico
--

---

From: Luke Howard <[email-masked]>
Date: Thu, 11 Jul 2013 10:17:04 +1000

Good point Jeff.

An SSPI application can call QueryContextAttributes(SECPKG_ATTR_SIZES), but unlike gss_wrap_iov_length(), that data to be wrapped is not passed as an argument. So it can only return the maximum security trailer size (trailer being the RFC4121 wrap token/rotated checksum).

If an in-place wrap truncates the trailer length, the application protocol may not be able to update it (consider something like DCE RPC where the message length is also authenticated). (It's sort of irrelevant whether the padding is done inside the trailer -- via EC -- or by the application.)

I would need to do some research; from memory DCE RPC always pads PDUs to 16 bytes, so for common block sizes the trailer is effectively constant length (there is no requirement for EC). I will investigate.

Of course, there are other SSPI applications than DCE RPC, but I'm not sure if they have the limitation of not allowing the trailer size to be shorter after wrap.

-- Luke

---

From: Derek Atkins <[email-masked]>
Date: Thu, 11 Jul 2013 09:01:51 -0400

> type interfaces have told me.

Having recently implemented Krb5 CTS mode myself, it is just one extra
block and a little bit-fudging on decryption.  It's really not a lot of
code.  I think the encryption and decryption routines added about 20-40
LoC (I'd have to actually look again to count if you want an exact
number).

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

-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: Kelley Burgin <[email-masked]>
Date: Fri, 12 Jul 2013 09:27:03 -0400

Looks like the choices now are:

1. Come up with a security proof that the current short plaintext algorithm is secure (so Nico isn't worried about baked-in crypto weaknesses), and continue with CTS
2. Go back to CBC with padding (my original proposal a couple of years ago)
3. Wait to see what SSPI (and other?) applications are negatively affected by plaintext padding, then choose 1. or 2.

I still like 2, or 3 then 2 :)

Kelley

On Jul 10, 2013, at 8:17 PM, Luke Howard <[email-masked]> wrote:

> _______________________________________________
> Kitten mailing list
> [email-masked]

---

From: Benjamin Kaduk <[email-masked]>
Date: Fri, 12 Jul 2013 15:18:31 -0400 (EDT)

>From the research I did through the krb-wg mail archives, I do not see 
reason to support (3).  Going with (2) seems fine.

-Ben

---

From: Greg Hudson <[email-masked]>
Date: Tue, 16 Jul 2013 10:38:54 -0400

> 3. Wait to see what SSPI (and other?) applications are negatively affected by plaintext padding, then choose 1. or 2.

At the moment I favor #2.

I know I was the one who relayed the SSPI-based objections to padded CBC
in the past, so this may seem inconsistent.  At the time my reasoning
was that we were already used to the pain of having CTS and we aren't
going to get away from it any time soon, so even a vaguely-understood
objection based on SSPI usage ought to be sufficient.  I did not
consider that the use of explicit IVs instead of confounders would
necessitate a complicated and novel construction to make CTS work for
short plaintexts.

Now that we have gone through that exercise, I think we would need a
much clearer objection from the SSPI front to justify the use of CTS
with the proposed enctype.

> SSPI would rather I somehow only send a 1016-byte message.

I don't understand this question.  All RFC 3961 enctypes carry some
plaintext expansion, which in turn affects the length of a CFX wrap
token.  The existing (RFC 3962) AES enctypes have a fixed 28-byte
expansion, for instance.  Kelley's current draft imposes a 32-byte or
40-byte expansion for aes128 or aes256.  We are considering adding a
variable 1-16 bytes to that expansion depending on input length.

So, what does this hypothetical specification have in mind?  Is it
making assumptions about the amount of expansion from gss_wrap based on
existing GSS mechanisms and enctypes?

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Tue, 16 Jul 2013 11:30:50 -0400

> existing GSS mechanisms and enctypes?

Huh?  No; GSS doesn't promise a particular amount of expansion.  My
understanding is that Microsoft says the only SSPI applications that are
negatively affected are those that don't call Microsoft's API to decide
how much data they should put in a wrap token.  But GSS tokens aren't a
stream; they're discrete, so the amount of data I put in a token has to
be based on what the protocol says I put in the token, not what some
particular implementation's non-standard API says about how much data I
ought to put into a token.

-- Jeff

---

From: Benjamin Kaduk <[email-masked]>
Date: Tue, 16 Jul 2013 11:33:32 -0400 (EDT)

> ought to put into a token.

In this case, isn't it that particular implementation's non-standard API 
which is generating the actual GSS token?  If the implementation is 
broken, the implementation is broken, but I don't see how the 
application's behavior comes into play just based on the above.

-Ben

---

From: Nico Williams <[email-masked]>
Date: Tue, 16 Jul 2013 11:54:56 -0500

If the issue is apps using an unsupported interface from SSPI then I
think we have our answer: it was important, once, to support them so
they could get off 1DES and RC4, but I think it's much less important
to get them off HMAC-SHA-1.  So I think we can just go with a CBC mode
cipher with random IV (and state chaining for RFC3961 apps).

Nico
--

---

From: Kelley Burgin <[email-masked]>
Date: Tue, 16 Jul 2013 12:57:12 -0400

I've gone through the effort of re-writing the draft using CBC mode with padding (being hopeful of its return - I'll be on vacation for most of the next two weeks). I see however that it's past the submission deadline, so if anyone's interested in seeing the draft before the tool reopens, I'd be happy to send it to you (assuming this doesn't break any IETF rules).

Kelley

---

From: Luke Howard <[email-masked]>
Date: Wed, 17 Jul 2013 10:13:21 +1000

> ought to put into a token.

I think we need more input from Microsoft to know exactly what the issue is, if anything. At this point in time I actually have no idea. :-)

One thing I will point out, though: SSPI doesn't have an equivalent to gss_wrap_size_limit(); instead one calls QueryContextAttributes(SECPKG_ATTR_SIZES) and provides a token buffer of cbMaxToken bytes and and a padding buffer of cbBlockSize. My understanding is that, for RFC 4121 encryption types, the padding buffer is not used and instead any padding is rotated into the token. But maybe Yizeng can correct me (it's hard to tell for AES CTS, because there's no padding anyway).

Anyway, the token/padding buffers may be smaller after calling EncryptMessage.

-- Luke

---

From: Benjamin Kaduk <[email-masked]>
Date: Tue, 16 Jul 2013 20:17:43 -0400 (EDT)

On Tue, 16 Jul 2013, Kelley Burgin wrote:

> I've gone through the effort of re-writing the draft using CBC mode with 
> padding (being hopeful of its return - I'll be on vacation for most of 
> the next two weeks). I see however that it's past the submission 
> deadline, so if anyone's interested in seeing the draft before the tool 
> reopens, I'd be happy to send it to you (assuming this doesn't break any 
> IETF rules).

I think it should be fine to post a rendered copy somewhere on the 
internet and send a link to the list.  I, for one, would be interested in 
seeing it.

Thanks,

Ben

---

From: Tom Yu <[email-masked]>
Date: Tue, 16 Jul 2013 22:55:11 -0400

Kelley Burgin <[email-masked]> writes:

> I've gone through the effort of re-writing the draft using CBC mode
> with padding (being hopeful of its return - I'll be on vacation for
> most of the next two weeks). I see however that it's past the
> submission deadline, so if anyone's interested in seeing the draft
> before the tool reopens, I'd be happy to send it to you (assuming
> this doesn't break any IETF rules).

The I-D submission cutoff functionally allows the WG Chairs to set
reasonable expectations for what participants have read before the
in-person WG session.  (This is a topic that undergoes some
significant recurring debate in the IETF at large.)  I believe under
exceptional conditions, a WG Chair can work with an AD to allow
posting within the blackout window.  I also believe that may not be
required here, because most of the active participants with an
interest in this document already have a good idea of what the CBC
mode proposal will look like.

---

From: Sam Hartman <[email-masked]>
Date: Wed, 17 Jul 2013 07:29:40 -0400

>>>>> "Kelley" == Kelley Burgin <[email-masked]> writes:

    Kelley> I've gone through the effort of re-writing the draft using
    Kelley> CBC mode with padding (being hopeful of its return - I'll be
    Kelley> on vacation for most of the next two weeks). I see however
    Kelley> that it's past the submission deadline, so if anyone's
    Kelley> interested in seeing the draft before the tool reopens, I'd
    Kelley> be happy to send it to you (assuming this doesn't break any
    Kelley> IETF rules).  Kelley

Hi.
It would be great to make the text available to people, but not in the
form of a WG draft.

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.

I think most of us can guess what CBC would look like but having text
available would still be great.
Distributing to people is fine, putting on a web page is fine.

The question before the WG is whether to adopt Tom's proposal to change
cipher modes as implemented in text by Kelley.
Just because editors of the draft are making the proposal does not give
it special standing.

We'll need to make a consensus call on this after discussion in the
meeting and confirm on the list.

An alternative would be to post this as an individual draft
draft-author-kitten-kerberos-aes256-alternate-cbc or some such.
I've asked Stephen if he would grat an exception if you want to go that
route.

---

From: Stephen Farrell <[email-masked]>
Date: Wed, 17 Jul 2013 14:54:11 +0100

> I've asked Stephen if he would grat an exception if you want to go that

If the chairs figure that it'll help make for a better wg meeting
then I will.

Cheers,
S.

---

From: Kelley Burgin <[email-masked]>
Date: Fri, 19 Jul 2013 11:24:36 -0400

I've put the draft at http://www.cs.jhu.edu/~kburgin1/draft-burgin-kitten-aes-cbc-padding-hmac-sha2-00.txt

Kelley