[Cryptography] RFC: block cipher randomization

[Natanael]

Den 28 juni 2016 13:24 skrev "Jerry Leichter" <leichter at lrw.com>:
>
> > Because there are known characteristics of many plaintexts (e.g., XML
streams, Zip packages, even compressed streams), I have always fancied
shuffling the ciphertext or the plaintext, as most appropriate, and having
the means of determining the permutation obtained by key expansion or
something equally devious....
> If you're going to go this route, there's little reason to believe that
you can beat the classic DESX construction - W1 XOR DES(W2 XOR P) - where P
is the plaintext and W1 and W2 are "whitening" keys.  This construction was
analyzed by Rogoway years ago - quick intro at
http://web.cs.ucdavis.edu/~rogaway/papers/cryptobytes.pdf - and is
surprisingly strong.  (Granted, its strength is analyzed against brute
force attacks - an issue for DES but not for modern ciphers.)  Still, it
will hide any fixed pieces of plaintext quite nicely.  (And, yes, you need
to apply the XOR both before and after encryption or the construction adds
little.)

You can make W1 = W2, see Minimalism in cryptography: the Even-Mansour
scheme revisited

https://eprint.iacr.org/2011/541.pdf

The abstract: In this paper we consider the following fundamental problem:
What is the simplest possible construction of a block cipher which is
provably secure in some formal sense? This problem motivated Even and
Mansour to develop their scheme in 1991, but its exact security remained
open for more than 20 years in the sense that the lower bound proof
considered known plaintexts, whereas the best published attack (which was
based on dierential cryptanalysis) required chosen plaintexts. In this
paper we solve this long standing open problem by describing the new Slidex
attack which matches the T = (2n=D) lower bound on the time T for any
number of known plaintexts D. Once we obtain this tight bound, we can show
that the original two-key Even-Mansour scheme is not minimal in the sense
that it can be simplied into a single key scheme with half as many key bits
which provides exactly the same security, and which can be argued to be the
simplest conceivable provably secure block cipher. We then show that there
can be no comparable lower bound on the memory requirements of such
attacks, by developing a new memoryless attack which can be applied with
the same time complexity but only in the special case of D = 2n=2. In the
last part of the paper we analyze the security of several other variants of
the Even-Mansour scheme, showing that some of them provide the same level
of security while in others the lower bound proof fails for very delicate
reasons.

---

Basically, an unkeyed permutation + two applications of XOR or other
functions of similar effect (like modular additions which they also analyze
the effect of).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160629/b6a2c7a4/attachment.html>