authenticating every packet

[D. J. Bernstein]

There's a false alarm going around about some new Google crypto code.
This motivates a review of some principles of boring cryptography:

Protocol designers:
1. Split all data into packets sent through the network.
2. Put a small global limit on the packet length (e.g., 1024 bytes).
3. Encrypt and authenticate each packet (with, e.g., crypto_box).

Crypto library designers:
1. Encrypt and authenticate a packet all at once.
2. Don't support "update" interfaces (such as HMAC_Update).
3. Test every small packet size (up to, e.g., 16384 bytes).

The fundamental reason for encrypting and authenticating each packet is
to get rid of forged data as quickly as possible. For comparison, here's
what happens if many packets are concatenated into a large file before
authenticators are verified:

* A single forged packet will destroy an entire file. This is massive
denial-of-service amplification.

* The protocol implementor won't want to buffer arbitrary amounts of
data. To avoid this he'll pass along _unverified_ data to the next
application layer, followed eventually by some sort of failure
notification. This ends up drastically increasing the amount of
code that has to deal with forged data.

If a crypto library supports only one-packet-at-a-time verification and
decryption, without any update options, then the protocol implementor
won't be able to pass unverified data along to the next layer, and there
will be a serious incentive for the protocol designer to authenticate
every packet.

Authenticating and encrypting _very_ small packets, say 53 bytes, means
considerable overhead. But state-of-the-art cryptographic primitives
don't have serious performance problems with, e.g., 1024-byte packets.
(Ethernet links can physically transmit 1500-byte packets; IPv6 requires
at least 1280; I can't remember the last time I saw an IP link imposing
a lower limit. I think forged packets can still fool current operating
systems into setting smaller limits, but presumably that will be fixed
eventually.)

Apparently Google is deploying ChaCha20 as a TLS option. The Chromium
ChaCha20 implementation doesn't correctly encrypt input messages larger
than 256 GB---it simply repeats the first 256 GB of keystream, whereas
the ChaCha20 definition actually allows messages up to 1099511627776 GB.
Fortunately, TLS splits the plaintext into "packets" of at most 16384
bytes, and this TLS option separately handles each "packet", generating
at most 16384 bytes of keystream for each nonce, so the bug is never
actually triggered.

There's a gap between the SUPERCOP/NaCl tests, which go only up to 4096
bytes, and the TLS range of plaintext sizes, up through 16384 bytes.
Maybe SUPERCOP should extend its tests up through 16384 bytes, just in
case some software has a bug between 4096 bytes and 16384 bytes.

For comparison, imagine a non-boring protocol design in which the sender
decides how many packets to send before sending an authenticator of all
of them and switching to the next nonce. It's easy to imagine gigabytes
of data being sent under the same nonce ("it's just a big file download;
no need to authenticate until the end"), and then the protocol can't
even be _implemented_ using a simple non-updating API on a 32-bit
machine. So the protocol implementor will demand a non-boring updating
API, and then there's no huge obstacle to a bug being triggered after
256 GB---which would also be quite painful to comprehensively test.

Apparently OpenSSL is refusing to take Google's ChaCha20 TLS patches
until the patches are modified to support an updating API. Further
discussion of this lunacy is obviously _much_ too interesting for the
boring-crypto mailing list. :-)

The NaCl development team has been discussing a related issue for some
time, namely what the "AES" primitive should actually take as input.
Right now it's a quite traditional counter mode, generating keystream
AES(n), AES(n+1), AES(n+2), etc., but this means that the requirements
on n are more than just "use a new n for each message"---it would be a
problem to start the next message with n+1, for example. We've
considered a 32-bit counter and a 96-bit nonce, which would fit nicely
with GCM, but this raises the question of what to do (on a 64-bit
machine) if some non-boring protocol asks for encryption of a plaintext
larger than 64 gigabytes. What we're leaning towards is a 64-bit counter
and a 64-bit nonce.

---Dan

[Adam Langley]

On Fri, Nov 22, 2013 at 3:57 PM, D. J. Bernstein <d...@cr.yp.to> wrote:
> Apparently Google is deploying ChaCha20 as a TLS option. The Chromium
> ChaCha20 implementation doesn't correctly encrypt input messages larger
> than 256 GB---it simply repeats the first 256 GB of keystream, whereas
> the ChaCha20 definition actually allows messages up to 1099511627776 GB.

Note that the code in question is, essentially,
supercop-20130419/crypto_stream/chacha20/krovetz/stream.c, which has
the same size limitation.

> Apparently OpenSSL is refusing to take Google's ChaCha20 TLS patches
> until the patches are modified to support an updating API. Further
> discussion of this lunacy is obviously _much_ too interesting for the
> boring-crypto mailing list. :-)

As part of the ChaCha20 patches, I implemented an AEAD API in OpenSSL
because the existing one was kept in an odd place, disguised as
something else, and took all manner pokes and shakes to make it work.

In the interests of never exposing unauthenticated plaintext to the
user of the API, it's purely a one-shot affair; like secretbox and
secretbox_open. AES-GCM is also supported by this API and I understand
that there's an exciting new cryptographic standard called CMS[1] that
a) uses AES-GCM and b) requires streaming decryption of large
messages.

[1] http://tools.ietf.org/html/rfc5652

Thus upstream thought it unwise to commit to a new API that didn't
support that use.

With a heavy heart I've now written a streaming, AEAD API that goes
alongside the one-shot version. But it's stalled in code review for
the moment.

> The NaCl development team has been discussing a related issue for some
> time, namely what the "AES" primitive should actually take as input.
> Right now it's a quite traditional counter mode, generating keystream
> AES(n), AES(n+1), AES(n+2), etc., but this means that the requirements
> on n are more than just "use a new n for each message"---it would be a
> problem to start the next message with n+1, for example. We've
> considered a 32-bit counter and a 96-bit nonce, which would fit nicely
> with GCM, but this raises the question of what to do (on a 64-bit
> machine) if some non-boring protocol asks for encryption of a plaintext
> larger than 64 gigabytes. What we're leaning towards is a 64-bit counter
> and a 64-bit nonce.

Any user of the API that requests a > 64GB operation is likely to
force some participant in the protocol to perform a streaming
(en/de)cryption. So it might be more boring to force all users to
produce < 64GB chunks.

However, a 96-bit nonce isn't comfortably long enough to pick at
random so there doesn't seem to be any benefit for 96 bits of nonce
over 64.


Cheers

AGL

--
Adam Langley a...@imperialviolet.org http://www.imperialviolet.org