[Cryptography] Crypto best practices

[Natanael]

Den 19 mar 2017 23:50 skrev "Kristian Gjøsteen" <kristian.gjosteen at ntnu.no>:


What practical people appear to worry about is that you need to process the
entire message before you can begin producing ciphertext. This seems to be
a requirement for misuse-resistant modes, and it is probably possible to
prove a theorem to that effect. With AEAD modes such as GCM, you can begin
producing ciphertext the moment you get the first bytes of the message,
which is convenient in some settings, I am told.


As for a quick demonstration of that you can have secure "streaming
behavior" without needing to start off with a full pass on the plaintext /
ciphertext before final encryption / decryption:

Option A: Use CBC mode (or another non-stream cipher mode), but instead of
computing an HMAC authentication tag on the full ciphertext first when the
encryption is done, you compute HMAC tags on one or a few blocks at a time
and append the tag to those blocks. Then for each set of blocks after the
first set you also use the previous HMAC tag as an input (chaining the HMAC
tags).

This requires both linear encryption and then linear validation of every
block from start to end as you decrypt, but proves at every stage that the
full message is intact from the start to the block you're currently
processing. (It can still be decrypted in parallel.)

Option B: As above use CBC, and for ciphertext authentication you
iteratively build a Merkle tree hash of the ciphertext blocks as you go
during the encryption, and sign each Merkle root hash version, then you
validate each of the ciphertext blocks against the signed Merkle root on
decryption.

For reference, Tahoe-LAFS already uses Merkle tree hashes to enable
"seekable decryption" on static files and simpler sync: https://tahoe-lafs.
readthedocs.io/en/latest/specifications/file-encoding.html

This could be used for example to stream video over a network, where you
first would continously transmit the signed partial Merkle tree roots, each
substituting the prior one, until done streaming (this would however be
fairly inefficient compared to the other options). Then you can just reuse
that last signed Merkle root for the full video file if retransmitting it.

It can be decrypted and validated in parallel, allowing you to jump to any
part of the file at will to decode, but for encryption it requires some
linearity in computing the Merkle tree (although with the right underlying
ciphermode you can still encrypt in parallel).

Technically this does mean that you're chaining together many small
plaintexts if going by your description, so I guess you're technically
correct. Also all full-message authentication mechanisms seems to require a
linear processing component during encryption.

With authenticated CBC mode you only reveal how many initial plaintext
blocks that are identical in the case of key+IV reuse. With both of these
authentication methods there's no malleability or block substitution - you
know that the entire full message is intact, no cut-and-paste of individual
blocks across different messages with the same key. No encryption key
leakage or authentication key leakage.

---

As for single-pass methods that *probably* would simultaneously be much
simpler, faster, have less overhead and yet be robust and secure (although
neither with full-message authentication), here's the two approaches that I
prefer;

1: Tweakable block ciphers.
For example, see AEZ, with Rogaway as one of the authors:
http://web.cs.ucdavis.edu/~rogaway/aez/

A tweakable cipher like AEZ encrypts the plaintext in a single pass, and
has three inputs: the key, the data and the tweak value (variable size).
What this means is that every trio of plaintext block + key + tweak will
produce "independent" encrypted blocks, since the tweak behaves as an
extension of the symmetric key (and the tweak can be public knowledge,
IIRC).
(Note: AEZ also has a variable block width, which makes it a convenient
replacement for XTS mode as well.)

This tweak allows you to define your cipher modes by for example feeding
AEZ a tweak input composed of an IV + a counter (mimicking CTR). This also
gives you much higher security than CTR mode, since reuse doesn't leak
anything other than information on which blocks in the same locations that
have identical plaintexts across the repeated encryptions (same as XTS
mode). It also isn't malleable like CBC mode. Every block is still only
processed once.

For AEZ, their own recommended way of implementing authentication (and
preserving the single-pass encryption) is to use the variable block width
to make the block size larger than the plaintext, and setting the remaining
bits to a fixed authentication string. For example, you could have a 256
bit block with 192/64 bits of plaintext / authentication string. Or any
other size of your choice (within the limits supported by AEZ).

On decryption, you look for the presence of this authentication string
(which may be all zeroes) in the plaintext before continuing. Any
modification of the ciphertext (or tweak) will unpredictability randomize
the decrypted data in the affected blocks, with the authentication string
length determining the probability of the string unintentionally matching
(assuming a string of 64 zeroes, a random match has a probability of 1 /
2^64).

This makes it non-malleable and gives you a security level at least
matching AES-GCM-SIV using *one* primitive and with none of the fragility
(GCM-SIV still only tolerates a limited number of nonce repetitions before
breaking too).

(Note that the tweak input also allows it to double as an AEAD, since the
tweak by design is validated together with the plaintext.)

Adding an authentication tag like Poly1305 as an option allows you to
separate authentication from decryption (with a latency penalty), which
could be a useful feature in for example edge routers in datacenters
(allows you to reject invalid incoming ciphertext blocks in hardware that
doesn't know the more sensitive decryption key). It would also allow you to
authenticate any AD (additional data) without decryption, which could
assist session management.

2: A hybrid mode with a stream cipher keyed block cipher.
See Enchilada for reference: https://aezoo.compute.dtu.dk/doku.php?id=
enchilada

As mentioned previously this can be done with XEX mode (XOR-encrypt-XOR)
with a static block key (see "Minimalism in cryptography") . Authentication
could still be implemented using either one of the same methods as above,
tags or fixed authentication strings in the plaintext blocks. Every block
is keyed individually from the stream cipher, the stream cipher is fed the
IV.
Note that to make this an AEAD, you either have to use an authentication
tag over the ciphertext or something similar to a tweakable cipher for the
encryption primitive.

The main advantage of this over AEZ is the reduced implementation
complexity; a simple stream cipher and simple XEX block (small, static and
parallelizable) vs a tweakable variable-width block cipher (needs to be
duplicated in full to parallelized). A tweakable cipher is presumably also
more sensitive to sidechannel attacks. However AEZ has fewer moving parts,
which is a plus. The tweak also enables in-protocol domain separation
between packets by using different tags for different data channels, with
minimal overhead.

The hybrid method should also have reduced latency - the stream cipher core
can feed a large number of parallel XEX instances with keystream inputs
every cycle, and you feed each XEX instance with a piece of plaintext /
ciphertext. (If using authentication tags, you just add that in the XEX
block data pipeline, same for both types of ciphers.)

---

Both options should share the advantage that they aren't limited by a
relatively low maximum number of plaintext blocks that you can encrypt
per-key before it becomes insecure (GCM) or that it just halts (XTS, if I
remember correctly), assuming that the stream cipher used in the hybrid
method has a large enough internal state. You should be able to encrypt
arbitrarily large amounts of data without worrying.

Since neither of these methods have full-message authentication, then for
key+IV reuse their biggest problem is that blocks in the same position can
be swapped arbitrarily between the two encryptions. This would allow file
headers to be substituted, and other similar attacks. Preventing that does
require processing the full plaintext in one pass, but the authentication
modes explained in the top solves that without breaking streaming.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20170320/5efa4a88/attachment.html>