<p dir="ltr">Den 31 aug. 2016 08:39 skrev "Kristian Gjøsteen" <<a href="mailto:kristian.gjosteen@math.ntnu.no">kristian.gjosteen@math.ntnu.no</a>>:<br>
><br>
> 30. aug. 2016 kl. 18.22 skrev Phillip Hallam-Baker <<a href="mailto:phill@hallambaker.com">phill@hallambaker.com</a>>:<br>
> > What I don't understand is why the various symmetric cipher modes we have keep the key fixed and modify the data.<br>
> ><br>
> > So for CBC we take<br>
> ><br>
> > C0 =  E (B0 XOR IV, k)<br>
> > C1 =  E (B1 XOR C0, k)<br>
> > ...<br>
> ><br>
> > Why not use:<br>
> ><br>
> > C0 =  E (B0, k)<br>
> > C1 =  E (B1, k + 1)<br>
> > ...<br>
> ><br>
> > This has the advantage that it can be applied to the use cases that motivated ECB and CBC. It doesn't require an initialization vector either.<br>
><br>
> You have now created a stateful cryptosystem. You have to remember the key between encryptions. This is inconvenient in many situations.<br>
><br>
> You have also made a system that needs a block cipher secure against related key attacks. As we know, a secure block cipher does not have to be secure against related key attacks, so you have to redo a lot of analysis.<br>
><br>
> Also, there’s this thing about the key schedule. Yes, modern computers can do key schedules real quick, but I still have other stuff for them to do, so not having to do key schedules is a good thing.<br>
><br>
> If you don’t care about cost, you can du stuff like<br>
><br>
>         Ci = E(Bi, H(k, IV, i))<br>
><br>
> which would be secure if you use any decent hash function. Now you have a choice whether to include an IV or keep a state.</p>
<p dir="ltr">My own preference is one that already has been mentioned a few times previously: a fast symmetric cipher keyed by a fast (seekable) stream cipher.</p>
<p dir="ltr">(wall of text below) </p>
<p dir="ltr">The series of blocks takes consecutive stream cipher keystream bit-ranges as their keys. This could be considered making the stream cipher your key schedule. </p>
<p dir="ltr">For the symmetric cipher I'd want a XEX construction, given that you can get strong security with just a small and very fast unkeyed permutation using a single XOR key per block - see this paper for reference (also see the non-XOR variants, like modular addition);</p>
<p dir="ltr">Minimalism in cryptography: The Even-Mansour scheme revisited <br>
<a href="https://eprint.iacr.org/2011/541.pdf">https://eprint.iacr.org/2011/541.pdf</a></p>
<p dir="ltr">The permutation used could for example be any block cipher using a fixed known key, or any other function with a random 1:1 mapping between inputs/outputs. Sidechannel resistance is the only major requirement. </p>
<p dir="ltr">The double XOR protects the permutation from cryptanalysis, the XEX construction protects the stream cipher from cryptanalysis, and the stream cipher provides unique unpredictable keys to the XEX construction. </p>
<p dir="ltr">Regarding block size: This is essentially the same as blockwise XOR instead of bitwise, mathematically speaking (assuming a good permutation). With very small blocks and partially known plaintexts, the keystream would be partially exposed since one could bruteforce the individual block keys (assuming block sizes below ~80 bits, perhaps 16/32 bit if somebody would want that in an IoT implementation). </p>
<p dir="ltr">These keys then directly represent the keystream, and a weak stream cipher (for example RC4) would then be easier to break to recover the main key and thus all plaintext. Assuming the use of a very lightweight stream cipher, it might be necessary with blocks large enough to protect the stream cipher from cryptanalysis. Typically 128 bits should suffice. Note that besides sidechannel resistance, we really only need unpredictability (difficulty to guess the key stream) from the stream cipher more than any other property, thanks to the XEX construction. </p>
<p dir="ltr">Given a stream cipher strong enough to resist key recovery / key stream prediction, small block sizes still should prevent known plaintext attacks, including distinguishability, given that all block keys are independent (with computational security). </p>
<p dir="ltr">The block size chosen could be whatever performs best on your intended hardware, given that you take account for the points above. </p>
<p dir="ltr">The security characteristics of this method should be similar to the block cipher mode XTS, I believe. XTS uses two layers of symmetric encryption: it first encrypts the disk blocks using counters (producing a static ciphertext), then it encrypts the plaintext using both per-disk-block counters, the disk block ciphertext and the plaintext as inputs. </p>
<p dir="ltr">XTS is resistant to plaintext leakage in the case of key reuse, as all you can see is when you have identical plaintext + key pairs in the very same place (unlike CTR which breaks under key reuse). It is also resistant to controlled bitflipping unlike CTR, and prevents plaintext injection unlike CBC. </p>
<p dir="ltr">The problems with XTS is the relatively low maximum ciphertext limit due to its particular construction and usage of a 128 bit cipher block size (can't encrypt more than some few terabytes max - less than many harddrives can store) together with limited performance. </p>
<p dir="ltr">Somebody else described it by saying XTS has the ECB penguin security flaw in the time dimension: when something's edited in place you can see the position of the changes, and which ciphertext blocks that are identical / different. This method would behave the same.</p>
<p dir="ltr">Given that both the stream cipher and the XEX construction individually can be lighter than AES, we could be able to get similar security to something like AES-CTR with potentially higher performance, and it would definitely beat XTS in performance. </p>
<p dir="ltr">A stream cipher with large enough internal state could answer generate a large enough keystream securely to encrypt much larger amounts of data, including very large harddrives. </p>
<p dir="ltr">From my reading of the Chacha20 paper, it can easily encrypt enough data for a whole datacenter with a single key and remain secure. Chacha20 is also generally faster than AES except when the CPU has AES acceleration circuits. It also has a security level comparable to AES. </p>
<p dir="ltr">With a construction like this (where the XEX construction hides the key stream even given partial known plaintexts, assuming large blocks = few collisions) we could even use a stream cipher which is lighter and faster than Chacha20 and still remain secure. </p>
<p dir="ltr">A XEX construction is also very easy to parallellize, since the middle function always is the same and XOR is trivial. A seekable stream cipher will likewise be easy to parallellize (although initialization might not always be quick). If both components also are chosen to be efficient in hardware you could get very high throughputs with a little parallellization. </p>
<p dir="ltr">By comparison the common cipher mode AES-CBC can't be parallellized, hurting performance in many circumstances, but is still weaker than this method. Many other secure cipher modes are also hard to parallellize. </p>
<p dir="ltr">It would be preferable to also pair it with key/IV reuse tolerant authentication tags similar to the GCM-SIV construction, just for additional robustness. </p>