[Cryptography] Key meshing (Re: [Crypto-practicum] Retire all 64-bit block ciphers.)

[Natanael]

Den 31 aug. 2016 08:39 skrev "Kristian Gjøsteen" <
kristian.gjosteen at math.ntnu.no>:
>
> 30. aug. 2016 kl. 18.22 skrev Phillip Hallam-Baker <phill at hallambaker.com
>:
> > What I don't understand is why the various symmetric cipher modes we
have keep the key fixed and modify the data.
> >
> > So for CBC we take
> >
> > C0 =  E (B0 XOR IV, k)
> > C1 =  E (B1 XOR C0, k)
> > ...
> >
> > Why not use:
> >
> > C0 =  E (B0, k)
> > C1 =  E (B1, k + 1)
> > ...
> >
> > 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.
>
> You have now created a stateful cryptosystem. You have to remember the
key between encryptions. This is inconvenient in many situations.
>
> 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.
>
> 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.
>
> If you don’t care about cost, you can du stuff like
>
>         Ci = E(Bi, H(k, IV, i))
>
> 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.

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.

(wall of text below)

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.

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);

Minimalism in cryptography: The Even-Mansour scheme revisited
https://eprint.iacr.org/2011/541.pdf

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.

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.

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).

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.

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).

The block size chosen could be whatever performs best on your intended
hardware, given that you take account for the points above.

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.

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.

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.

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.

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.

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.

>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.

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.

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.

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.

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160831/3ce173c2/attachment.html>