Subject: aes128gcm: why verify padding?

From: "Manger, James" <[email-masked]>
Date: Sun, 15 Jan 2017 23:51:05 +0000

draft-ietf-httpbis-encryption-encoding<https://github.com/httpwg/http-extensions/blob/master/draft-ietf-httpbis-encryption-encoding.md> allows any amount of padding to be added alongside the content being encrypted. The spec says the receiver (decryptor) MUST confirm that every padding byte is 0x00. Why?

I'm not sure how it helps to check the padding. It doesn't make the encryption deterministic as there is a salt involved, and the length of padding can also vary. It isn't useful for integrity as that is provided by the GCM tag.

Checking the padding could be harmful. Padding (to a block size) has caused lots of security vulnerabilities when the padding is checked before doing a proper integrity check. AEAD algorithms (such as GCM) theoretically solve this, but only when receivers process a whole AEAD decryption in one go, not via a (very common) streaming API.

The aes128gcm Content-Encoding adds "app-layer" padding, but by putting it first with a fixed format it is almost tempting receivers to check it before processing the rest of the ciphertext, and hence introduce vulnerabilities.

3 possible improvements:

1.       Allow padding bytes to have any value. The receiver just skips them.

2.       Calculate the padding length by reducing a 2-byte unsigned integer modulo the maximum possible padding length (plaintext length - 2). That means every 2-byte value will give a valid padding length.

3.       Put the 2-byte padding length field at the end. So the receiver has to have a whole AEAD plaintext block before knowing where the content starts.

A plaintext block would be: plaintext = padding || content || padlen
Len(plaintext) is the record size - 16.
Len(padlen) is 2 bytes.
Len(padding) = padlen % (Len(plaintext) - 2)
Padding bytes have any value.
Content is the remainder of the plaintext block.

The nice feature of this is that every plaintext block is valid. The last 2 bytes can be anything; mod (Len(plaintext) - 2) always gives a valid padding length; padding can be anything; and all that is left is the content to pass to the next layer. With this arrangement there is very little risk that plaintext structure is dangerously checked before performing the AEAD integrity check.

This form is no harder that the current structure to process, but it does encourage proper use of AEAD APIs.

--
James Manger

---

From: Martin Thomson <[email-masked]>
Date: Mon, 16 Jan 2017 13:32:43 +1300

I don't think that this warrants a change at this stage.

The reason for enforcing the checking was so that we could ensure that
when people sent padding there was only one way to send it.  You are
asking to allow variation, which I think needs stronger justification
than you've provided.

A secondary, though weak, reason for validating is to squash
heartbleed-like uninitialized memory reads.

Regarding AEAD APIs, yes, I'm aware that some libraries have bad APIs
for AEADs (thanks openssl).  I don't think that's justification for a
change, at least not in the format.  The API, certainly.

On 16 January 2017 at 12:51, Manger, James
<[email-masked]> wrote:
> draft-ietf-httpbis-encryption-encoding allows any amount of padding to be
> added alongside the content being encrypted. The spec says the receiver
> (decryptor) MUST confirm that every padding byte is 0x00. Why?
>
>
>
> I’m not sure how it helps to check the padding. It doesn’t make the
> encryption deterministic as there is a salt involved, and the length of
> padding can also vary. It isn’t useful for integrity as that is provided by
> the GCM tag.
>
>
>
> Checking the padding could be harmful. Padding (to a block size) has caused
> lots of security vulnerabilities when the padding is checked before doing a
> proper integrity check. AEAD algorithms (such as GCM) theoretically solve
> this, but only when receivers process a whole AEAD decryption in one go, not
> via a (very common) streaming API.
>
>
>
> The aes128gcm Content-Encoding adds “app-layer” padding, but by putting it
> first with a fixed format it is almost tempting receivers to check it before
> processing the rest of the ciphertext, and hence introduce vulnerabilities.
>
>
>
> 3 possible improvements:
>
>
>
> 2.       Calculate the padding length by reducing a 2-byte unsigned integer
> modulo the maximum possible padding length (plaintext length – 2). That
> means every 2-byte value will give a valid padding length.
>
>
>
> 3.       Put the 2-byte padding length field at the end. So the receiver has
> to have a whole AEAD plaintext block before knowing where the content
> starts.
>
>
>
> The nice feature of this is that every plaintext block is valid. The last 2
> bytes can be anything; mod (Len(plaintext) - 2) always gives a valid padding
> length; padding can be anything; and all that is left is the content to pass
> to the next layer. With this arrangement there is very little risk that
> plaintext structure is dangerously checked before performing the AEAD
> integrity check.
>
>
>

---

From: "Manger, James" <[email-masked]>
Date: Mon, 16 Jan 2017 01:06:23 +0000

> I don't think that this warrants a change at this stage.

Drafts have been around for at least a year, though there have been incompatible changes as recently as last week. This isn't a trivial change, but it isn’t a hard one for implementers either.

> I don't think that's justification for a change, at least not in the format.  The API, certainly.

Theoretically, changing APIs is better. But many APIs have been set for a long time. Actually this scheme encourages the retention of streaming APIs — as long as they operate in record-sized chunks, instead of block-sized chunks. I think it would be good is the padding forced APIs to use record-sized chunks, instead of insecure block-sized ones.

My gut feeling is that a software engineer would only have to be a bit sloppy to implement the current padding scheme insecurely (on many underlying AEAD APIs), but would have to be malicious to be insecure with small changes to the padding structure.

> A secondary, though weak, reason for validating is to squash heartbleed-like uninitialized memory reads.

Improvement 2 is actually much better for this. The "internal" length (padding length) is calculated mod (external length - 2) so it can never be too large. 

--
James Manger

-----Original Message-----
From: Martin Thomson [mailto:[email-masked]] 
Sent: Monday, 16 January 2017 11:33 AM
To: Manger, James <[email-masked]>
Cc: [email-masked]
Subject: Re: aes128gcm: why verify padding?

The reason for enforcing the checking was so that we could ensure that when people sent padding there was only one way to send it.  You are asking to allow variation, which I think needs stronger justification than you've provided.

A secondary, though weak, reason for validating is to squash heartbleed-like uninitialized memory reads.

Regarding AEAD APIs, yes, I'm aware that some libraries have bad APIs for AEADs (thanks openssl).  I don't think that's justification for a change, at least not in the format.  The API, certainly.

On 16 January 2017 at 12:51, Manger, James <[email-masked]> wrote:
> draft-ietf-httpbis-encryption-encoding allows any amount of padding to 
> be added alongside the content being encrypted. The spec says the 
> receiver
> encryption deterministic as there is a salt involved, and the length 
> of padding can also vary. It isn’t useful for integrity as that is 
> provided by the GCM tag.
>
>
>
> Checking the padding could be harmful. Padding (to a block size) has 
> caused lots of security vulnerabilities when the padding is checked 
> before doing a proper integrity check. AEAD algorithms (such as GCM) 
> theoretically solve this, but only when receivers process a whole AEAD 
> decryption in one go, not via a (very common) streaming API.
>
>
>
> The aes128gcm Content-Encoding adds “app-layer” padding, but by 
> putting it first with a fixed format it is almost tempting receivers 
> to check it before processing the rest of the ciphertext, and hence introduce vulnerabilities.
>
>
>
> 3 possible improvements:
>
>
>
> modulo the maximum possible padding length (plaintext length – 2). 
> That means every 2-byte value will give a valid padding length.
>
>
>
> The nice feature of this is that every plaintext block is valid. The 
> last 2 bytes can be anything; mod (Len(plaintext) - 2) always gives a 
> valid padding length; padding can be anything; and all that is left is 
> the content to pass to the next layer. With this arrangement there is 
> very little risk that plaintext structure is dangerously checked 
> before performing the AEAD integrity check.
>
>
>

---

From: Martin Thomson <[email-masked]>
Date: Mon, 16 Jan 2017 20:09:26 +1300

> Improvement 2 is actually much better for this. The "internal" length (padding length) is calculated mod (external length - 2) so it can never be too large.

A better scheme would be to pad with an arbitrary number of zeroes,
then a terminal non-zero value.  That could be at the end, like in
TLS.  It also allows for lower overhead and arbitrary amounts of
padding.

But I'd like to hear whether other people think that this is worth fixing.

---

From: "Manger, James" <[email-masked]>
Date: Mon, 23 Jan 2017 04:28:55 +0000

After implementing aes128gcm I have another reason to adjust the padding scheme.
Putting the content first, before the padding (whatever format), will save moving the content after decryption in some (typical?) implementations. A Decrypt API will typically expect the content to be at the start of a given buffer. For instance, my implementation decrypts to a given buffer, but due to the current padding scheme (<padlen><padding><content>) then needs to copy the data to the start of the buffer (shifting it 2 bytes backwards in typical no-padding situations). If, instead, the content came first then the data wouldn't need to be moved.

So I would support a padding scheme similar to TLS 1.3: <content><non-zero byte><zeros…>.

--
James Manger

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 23 Jan 2017 09:36:23 +0200

On Mon, Jan 23, 2017 at 04:28:55AM +0000, Manger, James wrote:
> After implementing aes128gcm I have another reason to adjust the
> padding scheme. Putting the content first, before the padding
> (whatever format), will save moving the content after decryption
> in some (typical?) implementations. A Decrypt API will typically
> expect the content to be at the start of a given buffer. For
> instance, my implementation decrypts to a given buffer, but due
> to the current padding scheme (<padlen><padding><content>) then
> needs to copy the data to the start of the buffer (shifting it 2
> bytes backwards in typical no-padding situations). If, instead,
> the content came first then the data wouldn't need to be moved.
> 
> 

Furthermore, if the nonzero byte was 0x01 for non-final blocks and
0x81 for final block (or any two different nonzero values), then
that would also solve the truncation flaw from last message, no?

And while we are at breaking things, it would be good time to make
rs count ciphertext, not plaintext, right?

-Ilari

---

From: "Manger, James" <[email-masked]>
Date: Mon, 23 Jan 2017 12:47:37 +0000

A padding byte to distinguish intermediate and final records could indeed work.

It doesn't consume any extra bytes in this scheme as it piggy-backs on an end-of-padding byte. But in a different multiple-AEAD-record scheme that didn't offer padding (a nice, but not strictly necessary feature) it wouldn't be so ideal. I've seen ideas to put the first-vs-intermediate-vs-last indicator in the nonce, in the KDF, in the AAD, in the record length, and now in the plaintext. I'm not sure how to pick.

What do you do if last non-zero byte isn't 0x01 or 0x02?

That's already in the editor's draft (https://github.com/httpwg/http-extensions/blob/master/draft-ietf-httpbis-encryption-encoding.md).

--
James Manger

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] 
Sent: Monday, 23 January 2017 6:36 PM
To: Manger, James <[email-masked]>
Cc: Martin Thomson <[email-masked]>; [email-masked]
Subject: Re: aes128gcm: why verify padding?

-Ilari

---

From: Martin Thomson <[email-masked]>
Date: Tue, 24 Jan 2017 08:37:51 +0900

> A padding byte to distinguish intermediate and final records could indeed work.

I like it.  You can pad an arbitrary amount and you only pay one octet
per record overhead if you don't like padding, and the trailing record
requirement goes away.

> It doesn't consume any extra bytes in this scheme as it piggy-backs on an end-of-padding byte. But in a different multiple-AEAD-record scheme that didn't offer padding (a nice, but not strictly nec…

I believe that it doesn't matter.

> What do you do if last non-zero byte isn't 0x01 or 0x02?

Explode and discard the data - it's corrupted.  If we don't require
that, then an attacker gains a decryption oracle.  (Same reason for
requiring that the padding be fixed in size.)

---

From: "Manger, James" <[email-masked]>
Date: Tue, 24 Jan 2017 00:10:55 +0000

If we go with this approach, we should also distinguish the 1st record. For instance, for the end-of-padding byte:
* Set bit 8
* Set bit 1 if this is the first record
* Set bit 2 if this is the last record
So
0x81 indicates the 1st of multiple records;
0x83 indicates a message with only a single record (first is also last);
0x82 indicates the last of multiple records;
0x80 indicates an intermediate record;
0x00 is padding, keeping looking back for the end-of-padding byte
Any other value indicates an error.

--
James Manger

---

From: Martin Thomson <[email-masked]>
Date: Thu, 26 Jan 2017 08:42:01 +0900

> If we go with this approach, we should also distinguish the 1st record. For instance, for the end-of-padding byte:

I think that might be going too far.  Truncating the first record
requires that you are able to find an input to HKDF that provides the
same key, and a nonce that has just the lower bit flipped (you can
truncate more with higher probability).  That requires several
preimage attacks on SHA-256 in series.  Mostly though, marking the
start also increases complexity.  I think that it's enough to say 0x01
= keep going, 0x02 = all done.

---

From: "Manger, James" <[email-masked]>
Date: Fri, 27 Jan 2017 01:50:15 +0000

I agree that Start-or-middle vs End is enough in this case due to the KDF.
I was hoping for an anti-truncation mechanism that didn't depend in a not-completely-obvious-to-me manner on a seemingly quite separate aspect: the KDF.
For instance, even with no KDF (for key or nonce) having a byte distinguishing start/middle/end would be sufficient to authenticate you have received an authentic prefix or suffix or complete message.

--
James Manger

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 27 Jan 2017 09:20:41 +0200

On Fri, Jan 27, 2017 at 01:50:15AM +0000, Manger, James wrote:

> I was hoping for an anti-truncation mechanism that didn't depend in a
> not-completely-obvious-to-me manner on a seemingly quite separate aspect:
> the KDF. For instance, even with no KDF (for key or nonce) having a byte
> distinguishing start/middle/end would be sufficient to authenticate you
> have received an authentic prefix or suffix or complete message.

Actually, if you don't use KDF to obtain the nonce base together with
the key, attacker can corrupt messages unless you actually verify that
the start block is in its proper place.

This is because if attacker can choose noncebase, attacker can reorder
the blocks so all decrypt properly.

Using KDF prevents this because attacker can't produce suitably
related noncebase pairs for the same key

-Ilari

---

From: "Manger, James" <[email-masked]>
Date: Mon, 30 Jan 2017 02:30:03 +0000

> the start block is in its proper place.

Is this because the scheme uses Nonce XOR Index (not Nonce + Index)?
Given 2 valid AEADs, you can get the XOR of their indices but that isn't enough to tell how far apart they are in a sequence. It isn't even sufficient to tell that one comes right before the other. Hence, you really need to get the AEAD marked "start" first (or get the salt from which the "start" record's nonce is derived).

--
James Manger

---

From: Martin Thomson <[email-masked]>
Date: Mon, 30 Jan 2017 14:19:49 +1100

> Is this because the scheme uses Nonce XOR Index (not Nonce + Index)?

Not exactly.  The theoretical attack (if I understood Ilari correctly)
is if you had an explicit nonce on each record.  For instance, the
nonce is the first 12 octets of the ciphertext.  At that point, an
attacker would be more capable of performing interchanging any two
records.

That's different to your concern regarding dropping of some number of
records and producing a valid sequence of records.

Even assuming that you find an input that produces the same key while
allowing you to control the nonce, you would be stuck with the
interesting problem of finding a pattern of records that fit the XOR
pattern. If there were only two records, dropping the first is
trivial.  If there were three records and you wanted to keep two of
them, you have to switch the second and third to fit the pattern,
which would run afoul of the padding delimiter check.

Given that you would know the key at this point, I'd suggest that
constructing a new message would be easier.

> Given 2 valid AEADs, you can get the XOR of their indices but that isn't enough to tell how far apart they are in a sequence. It isn't even sufficient to tell that one comes right before the other.…

Are you saying that you can feed random data into your oracle until it
accepts two records?  And that you used the same key to generate that
random data?  Assuming those preconditions, I agree that you can get
the XOR of the indices of these records.  But you must have known
those indices because the oracle we're designing only accepts records
at those indices.

Even if you could do what you suggest (with a different oracle
perhaps), I think that you are right in suggesting that that isn't
much use.  You have just won every lottery on the planet in the same
week, and still that information doesn't seem very useful.

---

From: "Manger, James" <[email-masked]>
Date: Mon, 30 Jan 2017 05:23:03 +0000

My though experiment was to have a very simply situation: a key and a counter to use as the nonce. To send a message in, say, 3 AEAD parts use nonces  1, 2, 3; to send the next message in, say, 2 parts use nonces 4 & 5; and the next message in 1 part uses nonce 6. As long as records that start a message are flagged (1, 4, & 6 here) and records that end a message are flagged (3, 5, & 6 here) I think this simple scheme can work: a receiver can tell when a bunch of records are an authentic sequence (prefix, suffix, or in the middle); though not when separate sequences are part of the same message without joining them (no start/end flags in between).

Using XOR, instead of +, can still work; but a receiver can only really authenticate from the start.

Using the KDF seems to mean: you know records are part of the same message (same salt); you know a record's position (even if using XOR, not +); you know where the start is so you don't need to distinguish start & middle.

A start/middle/end indicator is necessary for the simplest schemes.
A not-end/end indicator is sufficient for the aes128gcm scheme, thanks to the KDF.
My judgement is that start/middle/end is more generic, with very little extra complexity (but if I'm in the rough so be it).

--
James Manger