<div dir="auto"><div><br><div class="gmail_extra"><div class="gmail_quote">Den 19 mar 2017 23:50 skrev "Kristian Gjøsteen" <<a href="mailto:kristian.gjosteen@ntnu.no" target="_blank">kristian.gjosteen@ntnu.no</a>>:<blockquote class="m_-4897320041099260789m_3811966909836941499quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
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.</blockquote></div></div></div><div dir="auto"><br></div><div dir="auto"><font face="sans-serif">As for a quick demonstration of that you can have secure </font><span style="font-family:sans-serif">"streaming behavior" without needing to start off with a full pass on the plaintext / ciphertext before final encryption / decryption</span><span style="font-family:sans-serif">:</span></div><div dir="auto"><font face="sans-serif"><br></font></div><div dir="auto"><font face="sans-serif">Option A: Use CBC mode (or another non-stream cipher mode), but instead of computing an HMAC authentication tag</font><font face="sans-serif"> 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)</font><span style="font-family:sans-serif">. </span></div><div dir="auto"><span style="font-family:sans-serif"><br></span></div><div dir="auto"><font face="sans-serif">This requires both linear encryption and then linear validation of every block from start to end as you decrypt, </font><span style="font-family:sans-serif">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.)</span></div><div dir="auto"><font face="sans-serif"><br></font></div><div dir="auto"><font face="sans-serif">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 </font><font face="sans-serif">encryption, and sign each Merkle root hash version</font><span style="font-family:sans-serif">, then you validate each of the ciphertext blocks against the signed Merkle root on decryption. </span></div><div dir="auto"><span style="font-family:sans-serif"><br></span></div><div dir="auto"><font face="sans-serif">For reference, Tahoe-LAFS already uses Merkle tree hashes to enable "seekable decryption" on static files and simpler sync: <a href="https://tahoe-lafs.readthedocs.io/en/latest/specifications/file-encoding.html" target="_blank">https://tahoe-lafs.<wbr>readthedocs.io/en/latest/<wbr>specifications/file-encoding.<wbr>html</a></font></div><div dir="auto"><font face="sans-serif"><br></font></div><div dir="auto"><font face="sans-serif">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. </font></div><div dir="auto"><font face="sans-serif"><br></font></div><div dir="auto"><font face="sans-serif">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</font><span style="font-family:sans-serif"> requires some linearity in computing the Merkle tree (although with the right underlying ciphermode you can still encrypt in parallel). </span></div><div dir="auto"><font face="sans-serif"><br></font></div><div dir="auto"><font face="sans-serif">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.</font></div><div dir="auto"><font face="sans-serif"><br></font></div><div dir="auto"><span style="font-family:sans-serif">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</span><span style="font-family:sans-serif"> 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. </span></div><div dir="auto"><span style="font-family:sans-serif"><br></span></div><div dir="auto">---</div><div dir="auto"><br></div><div dir="auto"><div dir="auto" style="font-family:sans-serif">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;</div></div><div dir="auto"><br></div><div dir="auto">1: Tweakable block ciphers. </div><div dir="auto">For example, see AEZ, with Rogaway as one of the authors: <a href="http://web.cs.ucdavis.edu/~rogaway/aez/" target="_blank">http://web.cs.ucdavis.edu/~<wbr>rogaway/aez/</a></div><div dir="auto"><br></div><div dir="auto">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). </div><div dir="auto">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). </div><div dir="auto"><span style="font-family:sans-serif">(Note: AEZ also has a variable block width, which makes it a convenient replacement for XTS mode as well.)</span></div><div dir="auto"><span style="font-family:sans-serif"><br></span></div><div dir="auto">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. </div><div dir="auto"><br></div><div dir="auto">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). </div><div dir="auto"><br></div><div dir="auto">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). </div><div dir="auto"><br></div><div dir="auto">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). </div><div dir="auto"><br></div><div dir="auto">(Note that the tweak input also allows it to double as an AEAD, since the tweak by design is validated together with the plaintext.) </div><div dir="auto"><br></div><div dir="auto">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. </div><div dir="auto"><br></div><div dir="auto">2: A hybrid mode with a stream cipher keyed block cipher. </div><div dir="auto">See Enchilada for reference: <a href="https://aezoo.compute.dtu.dk/doku.php?id=enchilada" target="_blank">https://aezoo.<wbr>compute.dtu.dk/doku.php?id=<wbr>enchilada</a></div><div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto">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. </div><div dir="auto"><br></div><div dir="auto">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. </div><div dir="auto"><br></div><div dir="auto">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.)</div><div dir="auto"><br></div><div dir="auto">---</div><div dir="auto"><br></div><div dir="auto">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. </div><div dir="auto"><br></div><div dir="auto">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. </div></div>