Subject: [kitten] Input on Paul's concerns about aes-cbc

From: Sam Hartman <[email-masked]>
Date: Fri, 04 Oct 2013 09:48:21 -0400

Folks, I'd really appreciate input from those who responded to the AES
CBC consensus call.

1) Do you need any additional information to evaluate Paul's message?

2) Has Paul's message caused you to revise your opinions in any way?

Comments from those who did not respond to the consensus call are also
welcome.

---

From: Greg Hudson <[email-masked]>
Date: Fri, 04 Oct 2013 10:17:37 -0400

> 1) Do you need any additional information to evaluate Paul's message?

I don't think so.  We are still curious about the details of legacy 
application risk (i.e. what kinds of things might a legacy SSPI 
application do wrong such that it works now but fails with a padded 
enctype), but the conclusion is pretty clear.

> 2) Has Paul's message caused you to revise your opinions in any way?

Yes; I think a CBC-padded enctype is more problematic for Microsoft than 
we had concluded based on previous input.  However, I am still 
uncomfortable with the amount of novel cipher mode design in 
http://tools.ietf.org/html/draft-ietf-kitten-aes-cts-hmac-sha2-01 to 
handle short inputs.

I am interested in the outcome of the discussion about using a 
confounder instead of an explicit IV.  Although confounders are less 
efficient than explicit IVs and less consistent with current 
cryptographic practice, using them does have several advantages 
(simplifying the CTS short-input problem down to the case of zero-length 
inputs; reducing the impact of PRNG compromise under specific threat 
mdels; allowing more implementation sharing with RFC 3962).

I have also spent some more time thinking about CTR mode as you 
suggested earlier (where we pick a random 128-bit nonce and use some 
function f(nonce, blocknum) to produce the counter for each block), and 
whether a nonce or block counter collision is any worse than a CBC 
cipher-block collision.  I noted that a CTR nonce collision would leak 
the XOR of the entire plaintexts of two multi-block messages, while a 
CBC cipher-block collision or only leaks the XOR of the plaintexts of 
the two colliding blocks, and a CBC IV/confounder collision only leaks 
information about how many blocks of two messages are identical.

---

From: Nico Williams <[email-masked]>
Date: Fri, 4 Oct 2013 16:09:46 -0500

On Fri, Oct 4, 2013 at 9:17 AM, Greg Hudson <[email-masked]> wrote:
> application risk (i.e. what kinds of things might a legacy SSPI application
> do wrong such that it works now but fails with a padded enctype), but the
> conclusion is pretty clear.

I can't tell if Paul is acting out of [quite reasonable] conservatism,
or if he's really identified actual failure modes of existing
applications (or likely ones), nor has he indicated whether there's
any way to work around such failures (by, e.g., downgrading to CTS
enctypes), nor whether any such workarounds are acceptable.

I'm not going to insist on -say- proprietary evidence.  Indeed, I like
the random IV CTS mode we cooked up.  I just think we need to
understand the *actual* constraints, in so far as they can be
published, so that we can a) not have this conversation again later,
b) understand how those constraints might apply to future proposals,
c) document how developers should write code so as not to impose these
constraints on us.

> I have also spent some more time thinking about CTR mode as you suggested
> earlier (where we pick a random 128-bit nonce and use some function f(nonce,
> blocknum) to produce the counter for each block), and whether a nonce or
> block counter collision is any worse than a CBC cipher-block collision.  I
> noted that a CTR nonce collision would leak the XOR of the entire plaintexts
> of two multi-block messages, while a CBC cipher-block collision or only
> leaks the XOR of the plaintexts of the two colliding blocks, and a CBC
> IV/confounder collision only leaks information about how many blocks of two
> messages are identical.

I'm now convinced that what we need in order to make certain cipher
modes usable in Kerberos is a change to RFC3961 so that the API knows
whether a given key is a sub-session key or not.  I don't feel
comfortable with CTR modes applied to long-term keys (or even Ticket
session keys) without taking steps that would effectively kill
performance for the GSS mechanism's per-msg tokens.  I don't think we
should have *this* discussion in the context of CTS vs. CBC: we should
first decide that we don't want either CTS nor CBC.

Nico
--

---

From: "Paul Miller (NT)" <[email-masked]>
Date: Tue, 8 Oct 2013 00:22:08 +0000

I don't have any information about specific application failures with padded ciphers.  If there were problems with a block cipher, it would not be possible to do a fallback just for impacted callers as the cipher of the subsession key is chosen during the context establishment which is before the first call to EncryptMessage (GSS_Wrap analogue).  By the time we knew that the caller was not providing for padding, it would be too late to select differently.

With the existing calling pattern used for DES in Windows, callers that did not pass in the SECBUFFER_PADDING into the EncryptMessage call would just fail when the buffer was not aligned.  Additionally, if the buffer was a multiple of the block size then it would not get the PKCS#7 padding and then would fail on the other end that expected the pad block.  I suspect this would break a whole lot of callers.

To reduce the application compatibility problem, I'd have to use the Rotate Right Count in the header to move padding into the header.  Up front, Kerberos on Windows would tell callers that they needed to allocate for the header one block more than they actually need.  Then, on output we would shorten the length to whatever portion was actually used.  This would fix the callers that do not handle padding for the first encryption, but making the header variable length causes a different set of problems.  Today, the header is always the same length so the caller can allocate that buffer and then reuse it throughout multiple encryption calls.  Making it variable length would require the caller to take the additional step of resetting the length field to the allocated size between calls, which not all applications may be doing today.

There are several reasons that I think this is a significant risk.  First of all, the documentation that Microsoft has for the EncryptMessage function for Kerberos has very little bearing on how the function should actually be used.  In fact, most of the document is incorrectly copied and pasted from SSL's documentation.  It'd be highly optimistic to expect developers to have used the API correctly while the documentation was incorrect.  This makes the risk that some application is broken quite high.

The second factor is that we only have the ability to control supported encryption types at the machine level.  This means that if there is one application in an enterprise, all impacted machines will have the new cipher supported.  This means that if a LOB app is  impacted, the enterprise is likely to disable the new cipher on all machines via policy.

If the problem is likely to occur and the impact of the problem is the disablement of the new ciphers for the entire realm, the objective of introducing the new cipher is compromised.  It is much safer to move forward with a cipher that is more likely broadly to be used.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Nico Williams
Sent: Friday, October 4, 2013 2:10 PM
To: Greg Hudson
Cc: [email-masked]; Sam Hartman
Subject: Re: [kitten] Input on Paul's concerns about aes-cbc

> enctype), but the conclusion is pretty clear.

I can't tell if Paul is acting out of [quite reasonable] conservatism, or if he's really identified actual failure modes of existing applications (or likely ones), nor has he indicated whether there's any way to work around such failures (by, e.g., downgrading to CTS enctypes), nor whether any such workarounds are acceptable.

I'm not going to insist on -say- proprietary evidence.  Indeed, I like the random IV CTS mode we cooked up.  I just think we need to understand the *actual* constraints, in so far as they can be published, so that we can a) not have this conversation again later,
b) understand how those constraints might apply to future proposals,
c) document how developers should write code so as not to impose these constraints on us.

> function f(nonce,
> blocknum) to produce the counter for each block), and whether a nonce 
> or block counter collision is any worse than a CBC cipher-block 
> collision.  I noted that a CTR nonce collision would leak the XOR of 
> the entire plaintexts of two multi-block messages, while a CBC 
> cipher-block collision or only leaks the XOR of the plaintexts of the 
> two colliding blocks, and a CBC IV/confounder collision only leaks 

I'm now convinced that what we need in order to make certain cipher modes usable in Kerberos is a change to RFC3961 so that the API knows whether a given key is a sub-session key or not.  I don't feel comfortable with CTR modes applied to long-term keys (or even Ticket session keys) without taking steps that would effectively kill performance for the GSS mechanism's per-msg tokens.  I don't think we should have *this* discussion in the context of CTS vs. CBC: we should first decide that we don't want either CTS nor CBC.

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

---

From: Nico Williams <[email-masked]>
Date: Mon, 7 Oct 2013 22:55:33 -0500

On Mon, Oct 7, 2013 at 7:22 PM, Paul Miller (NT) <[email-masked]> wrote:
> [...]

Thanks, that was exactly what I was looking for.  That's convincing.
We need the new enctype to require no padding.

I'm not a fan of coutner modes for Kerberos, but if someone has a
specific proposal I would review it; the same goes for just about any
cipher modes other than CTS.  Assuming nobody proposes such a thing
that leaves us with confounded CTS or random IV CTS (including
short-plaintext cases because of non-GSS RFC3961 applications).

Nico
--

---

From: Luke Howard <[email-masked]>
Date: Tue, 8 Oct 2013 15:18:28 +1100

> To reduce the application compatibility problem, I'd have to use the Rotate Right Count in the header to move padding into the header.  Up front, Kerberos on Windows would tell callers that they needed to allocate for

MIT scatter/gather APIs do this. There are not the same compatibility issues as there are (to my knowledge) few consumers. The only consumer I'm aware of, DCE RPC, can deal with extra bytes in the header, because its PDUs contain explicit lengths.

It's unfortunate about the documentation...

-- Luke

---

From: [email-masked] (Martin Rex)
Date: Wed, 9 Oct 2013 04:23:05 +0200 (CEST)

Paul Miller (NT) wrote:
>
>  ... it would not be possible to do a fallback just for impacted
> callers as the cipher of the subsession key is chosen during the
> context establishment which is before the first call to
> EncryptMessage (GSS_Wrap analogue).  By the time we knew that the
> caller was not providing for padding, it would be too late to
> select differently.

That fallback isn't possible has been intuitively obvious, at least to me.

> 
> With the existing calling pattern used for DES in Windows, callers that
> did not pass in the SECBUFFER_PADDING into the EncryptMessage call would
> just fail when the buffer was not aligned.

Hmmm.

While I did write my code that calls SSPI's EncryptMessage() in 1999
(during W2K beta), and don't exactly remeber which documentation
I used,  The "MDSN Library October 2001 Platform SDK" contains
a description titled "SSPI/Kerberos Interoperability with GSS-API
with this code sample:

  // Need 3 descriptors - 2 for the SSP and one to hold the application data 
  in_buf_desc.cBuffers = 3;
  in_buf_desc.pBuffers = wrap_bufs;
  in_buf_desc.ulVersion = SECBUFFER_VERSION;
  wrap_bufs[0].cbBuffer = sizes.cbSecurityTrailer;
  wrap_bufs[0].BufferType = SECBUFFER_TOKEN;
  wrap_bufs[0].pvBuffer = malloc(sizes.cbSecurityTrailer);
  // This buffer holds the application data
  wrap_bufs[1].BufferType = SECBUFFER_DATA;
  wrap_bufs[1].cbBuffer = in_buf.cbBuffer;
  wrap_bufs[1].pvBuffer = malloc(wrap_bufs[1].cbBuffer);
  memcpy(wrap_bufs[1].pvBuffer, in_buf.pvBuffer, in_buf.cbBuffer);
  wrap_bufs[2].BufferType = SECBUFFER_PADDING;
  wrap_bufs[2].cbBuffer = sizes.cbBlockSize;
  wrap_bufs[2].pvBuffer = malloc(wrap_bufs[2].cbBuffer);
  maj_stat = EncryptMessage(&context,
          SignOnly ? KERB_WRAP_NO_ENCRYPT : 0,
          &in_buf_desc, 0);

// Send message to server

>
> There are several reasons that I think this is a significant risk.
> First of all, the documentation that Microsoft has for the
> EncryptMessage function for Kerberos has very little bearing on how
> the function should actually be used.  In fact, most of the document
> is incorrectly copied and pasted from SSL's documentation.

Would the above code really fail to work?

-Martin

---

From: Luke Howard <[email-masked]>
Date: Wed, 9 Oct 2013 13:34:26 +1100

> a description titled "SSPI/Kerberos Interoperability with GSS-API

Because this sample was geared towards GSS-API interoperability (which was DES only at the time, hence required PKCS#7 padding), it's no surprise that it correctly uses SECBUFFER_PADDING.

That sample code works fine with both truncated token and padding buffers. Paul's point, I guess, is that not all applications follow this.
 
-- Luke

---

From: Luke Howard <[email-masked]>
Date: Wed, 9 Oct 2013 13:38:51 +1100

> With the existing calling pattern used for DES in Windows, callers that did not pass in the SECBUFFER_PADDING into the EncryptMessage call would just fail when the buffer was not aligned.  Addition…

Are you saying that even for RC4 (where there is one byte of PKCS#7 padding per RFC 4757 7.3), padding would be omitted entirely if the buffer was a multiple of the block size? Isn't this a bug? I noticed this was the case when building an interoperable DCE RPC implementation, but I assumed it was special-cased for GSS_C_DCE_STYLE. [1]

-- Luke

[1] https://github.com/krb5/krb5/blob/master/src/lib/gssapi/krb5/k5sealiov.c#L89

---

From: Tom Yu <[email-masked]>
Date: Wed, 09 Oct 2013 09:12:12 -0400

> Because this sample was geared towards GSS-API interoperability (which was DES only at the time, hence required PKCS#7 padding), it's no surprise that it correctly uses SECBUFFER_PADDING.

The DES enctypes used in Kerberos are not PKCS#7 padding.  When the
plaintext is an exact multiple of the block size, there is no padding
for DES.  PKCS#7 type padding requires a full block of padding in that
case, because it is self-describing.

This could be an important distinction, but I haven't fully analyzed
how this affects the usability of the AES-SHA2 proposal with SSPI
EncryptMessage.

---

From: Luke Howard <[email-masked]>
Date: Thu, 10 Oct 2013 00:21:05 +1100

> case, because it is self-describing.

Ah, my (long-term) bad.

What about RFC 4757?

Greg: in the MIT implementation, make_seal_token_v1_iov()/kg_fixup_padding_iov() may be  wrong then for DES, I believe I assumed PKCS#7 when implementing it.

-- Luke

---

From: Tom Yu <[email-masked]>
Date: Wed, 09 Oct 2013 09:46:00 -0400

> Greg: in the MIT implementation, make_seal_token_v1_iov()/kg_fixup_padding_iov() may be  wrong then for DES, I believe I assumed PKCS#7 when implementing it.

Greg has reminded me that RFC 1964 uses PKCS#7 padding for single-DES;
I was mistakenly recalling that the DES CBC padding used in the RFC
1510 protocol (which is not PKCS#7) was the same used with DES for
GSS-Wrap.  Sorry for any confusion.