Subject: [kitten] History of AES block size issues

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

For those copied on this message, the kitten working group is
considering a proposal to produce an AES enctype that provides message
expansion of up to 16 octets.

That's kind of a departure from how we've been approaching this, so I
decided to go over the history and implications a bit.
The chairs are requiring the proponents of the proposal to try and
investigate why we wanted to avoid message expansion in the past and do
their best to compile our rationale and an explanation of why the change
is desirable.
Yes, this all would have been easier if we'd done a better job of
documenting the rationale.

This is from my memory,  and I may be getting things wrong; however I
think I know the people who were involved enough that you should be able
to reach out to folks and try and figure out what was happening.

During the development of what became RFC 3962, I believe that John
Brezak and possibly Paul  Leach approached Ken Raeburn with a proposal
to avoid non-constant message expansion.
I don't believe a strong explanation was offered at that point why; it
seemed very important to John.

It seemed like an improvement, so the WG went along.

Originally, Ken raeburn proposed draft-ietf-krb-wg-gss-crypto as a
mechanism for  GSS-API in Kerberos.

Larry Zhu was very unhappy  with this approach and proposed an
alternative.
I can't find that  alternative.  It was a lot closer to RFC 1964 than
RFc 4121.
MIT was very unhappy with that alternative because you had to specify
GSS crypto  algorithms separate from RFC 3961 algorithms.

The big compromise that allowed us all to get to RFC 4121 was the RRC.
It is my belief that two things went into that.
First, a desire that the MAC and other information needed to be at the
header of the token not at the end as in RFC 3961.

I seem to recall a desire to do something with padding, but am not able
to substantiate that now.

I'd also like to discuss API implications.

Most of the implementations (MIT, Heimdal and Microsoft) have a
scatter-gather API for GSS operations.
In Microsoft, it's the SSP.
In the other implementations it is the iov interface to GSS-API.

All the existing implementations will negotiate  a subsession key of a
modern enctype in their default configuration.  That is the default
configurations of all the GSS implementations will end up negotiating
something that does not pad GSS tokens.
So, in the default configuration, an application using the
scatter-gather APIs will never test its support for padding buffers.
If a non-default configuration is used and one of the DES enctypes is
used for GSS-API messages, padding may be used.

both the Microsoft and other APIs support padding; a correctly written
application  can work with padding under all the existing APIs.

We believe there are some protocols that use AEAD where the length of a
token is protected by AEAD.  These protocols need to be able to make
sure that padding does not adjust the length.

Also, note that while MIT and Heimdal have a scatter-gather API, it is
not their default API.  The API described in RFC 2744 is more common on
these implementations for applications to use.

---

From: Michiko Short <[email-masked]>
Date: Wed, 14 Aug 2013 22:56:55 +0000

What is the scenario requiring message expansion up to 16 octets?

-----Original Message-----
From: Sam Hartman [mailto:[email-masked]] 
Sent: Wednesday, August 14, 2013 10:17 AM
To: [email-masked]
Cc: Michiko Short; Larry Zhu; [email-masked]
Subject: History of AES block size issues

For those copied on this message, the kitten working group is considering a proposal to produce an AES enctype that provides message expansion of up to 16 octets.

That's kind of a departure from how we've been approaching this, so I decided to go over the history and implications a bit.
The chairs are requiring the proponents of the proposal to try and investigate why we wanted to avoid message expansion in the past and do their best to compile our rationale and an explanation of why the change is desirable.
Yes, this all would have been easier if we'd done a better job of documenting the rationale.

This is from my memory,  and I may be getting things wrong; however I think I know the people who were involved enough that you should be able to reach out to folks and try and figure out what was happening.

During the development of what became RFC 3962, I believe that John Brezak and possibly Paul  Leach approached Ken Raeburn with a proposal to avoid non-constant message expansion.
I don't believe a strong explanation was offered at that point why; it seemed very important to John.

Originally, Ken raeburn proposed draft-ietf-krb-wg-gss-crypto as a mechanism for  GSS-API in Kerberos.

Larry Zhu was very unhappy  with this approach and proposed an alternative.
I can't find that  alternative.  It was a lot closer to RFC 1964 than RFc 4121.
MIT was very unhappy with that alternative because you had to specify GSS crypto  algorithms separate from RFC 3961 algorithms.

The big compromise that allowed us all to get to RFC 4121 was the RRC.
It is my belief that two things went into that.
First, a desire that the MAC and other information needed to be at the header of the token not at the end as in RFC 3961.

I seem to recall a desire to do something with padding, but am not able to substantiate that now.

Most of the implementations (MIT, Heimdal and Microsoft) have a scatter-gather API for GSS operations.
In Microsoft, it's the SSP.
In the other implementations it is the iov interface to GSS-API.

All the existing implementations will negotiate  a subsession key of a modern enctype in their default configuration.  That is the default configurations of all the GSS implementations will end up negotiating something that does not pad GSS tokens.
So, in the default configuration, an application using the scatter-gather APIs will never test its support for padding buffers.
If a non-default configuration is used and one of the DES enctypes is used for GSS-API messages, padding may be used.

both the Microsoft and other APIs support padding; a correctly written application  can work with padding under all the existing APIs.

We believe there are some protocols that use AEAD where the length of a token is protected by AEAD.  These protocols need to be able to make sure that padding does not adjust the length.

Also, note that while MIT and Heimdal have a scatter-gather API, it is not their default API.  The API described in RFC 2744 is more common on these implementations for applications to use.

---

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

>>>>> "Michiko" == Michiko Short <[email-masked]> writes:

    Michiko> What is the scenario requiring message expansion up to 16
    Michiko> octets?  -----Original Message----- From: Sam Hartman

With DES your message is padded to 8 octets.So if I  sent you a 2 byte
message it actually gets padded out to be 8 octets.

If I send you a 9-octet message it's actually 16.
If I send you a 16-octet message it's still 16 octets.

Added onto that is the size of the checksum and confounder, but those
are constant.

With aes-cts and rc4, there's a checksum and confounder but the
ciphertext is as long as the plaintext.

With this aes-cbc- proposal, there's a checksum and initial IV (constant
size).  However the message is padded to 16-octet boundaries.  If I send
1 byte of plaintext then it's going to be 16 octets.  If I send a
16-octet plaintext message I think it comes out to 32 octets because of
padding.

Greg, am I right that if your application aligns to a block size then
you'll actually end up expanding more so you can indicate no padding is
needed?
If so will DCE RPC be OK with that?

---

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

> If I send you a 16-octet message it's still 16 octets.

Is it not 24 octets?

> If so will DCE RPC be OK with that?

I believe it's fine for the reasons I mentioned in my last mail:

Note "trailer" here means DCE RPC auth trailer, containing the RFC 4121 "header" (which has the EC and checksum rotated into a single token)

* DCE RPC always pads at the application layer, if this it to at least 16 bytes then we will have a constant length trailer (we need to investigate this)

* Even if DCE RPC doesn't pad at the application layer to 16 bytes, [MS-RPCE] allows the trailer to be over-allocated, so as long as it's big enough for the largest value of EC, variable length trailers are OK

-- Luke

---

From: Sam Hartman <[email-masked]>
Date: Wed, 14 Aug 2013 20:02:43 -0400

>>>>> "Luke" == Luke Howard <[email-masked]> writes:

    >> If I send you a 9-octet message it's actually 16.  If I send you
    >> a 16-octet message it's still 16 octets.

    Luke> Is it not 24 octets?

Ah, that depends if you are talking RFC 3961 or RFC 1964.
Under 3961 I think 16; under 1964 I think 24.

    >> Greg, am I right that if your application aligns to a block size
    >> then you'll actually end up expanding more so you can indicate no
    >> padding is needed?  If so will DCE RPC be OK with that?

    Luke> I believe it's fine for the reasons I mentioned in my last
    Luke> mail:

    Luke> Note "trailer" here means DCE RPC auth trailer, containing the
    Luke> RFC 4121 "header" (which has the EC and checksum rotated into
    Luke> a single token)

    Luke> * DCE RPC always pads at the application layer, if this it to
    Luke> at least 16 bytes then we will have a constant length trailer
    Luke> (we need to investigate this)

Yeah, although in the obvious implementation we'll have 16 octets of pad
buffer.

so you might have to modify DCE RPC to deal with that if it doesn't
already, but I guess that's not a problem if you control both your DCE
RPC and your GSS.

---

From: Tom Yu <[email-masked]>
Date: Wed, 14 Aug 2013 22:48:37 -0400

> already, but I guess that's not a problem if you control both your DCE

My interpretation of C706 and MS-RPCE is that it won't be a problem at
a MS-RPC protocol level (except for possibly transmitting
overallocated padding).  Applications that roll their own MS-RPC
implementation rather than using a library might be in trouble,
though.  Applications that can query for the padding and block size,
and pad at the application layer to 16 bytes, can probably get away
with assuming a constant size trailer without overallocating.

I don't have detailed citations for the above at this time, but I
could probably write them up if people feel that it's necessary.