Re: Encyption of two 256-blocks


"Maaartin" <grajcar1@xxxxxxxxx> wrote in message news:95119a6f-34cb-4201-871f-75c8a19c9764@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
The mixing is very fast, as compared to the encryption, so I think it
should be done.

Perfectly acceptable answer.

> Do you thing some more expensive mixing could be better?

Not really. I chose the mix type I did because it is trivially proven that
the information from all bits is scattered across all blocks, forming an
AONT for the specific size, provided the cipher is secure.

Yes, but it's not as perfect as it could be.
Using only two rounds the cipherstream can be told from random in
about 2**32 steps:
The value of the last 128 bits influences only the last block of the
1st round cipher.
There're only 32 bits of it's output transferred to the first block of
the 2nd round cipher.
So varying the last 128 plaintext bits leads to only 2*32 possible
outcomes for the first 128 bits of the ciphertext.

That's why I said 2 rounds should be enough, but 4 rounds is provable. The avalanche/diffusion is not complete until the end of the encryption in round 4. From there the encruption used in each step provides the key mixing.

Using ECB would lead to the same problem for all blocks, not only for
the single pair as with CBC.

ECB has another disadvantage in this, the lack of forward mixing means that the system requires 5 rounds instead of 4 to reach provability.


That's probably no problem at all but it's unnecessary. We can do
better at about no cost.
I'll use "@" for concatenation in the following (as "|" is used in C
already).
Let's split the output of the 1st cipher in blocks of same size (128
bits):
a @ b @ c @ d := CBC_encrypt(X0 @ X1)
Now compute
s = a ^ b ^ c ^ d
and let f be any bijective function. Now feed the 2nd cipher by
A @ B @ C @ D := F(a, b, c, d) := (a ^ f(s)) @ (b ^ f(s)) @ (c ^ f(s))
@ (d ^ f(s))
Now the input blocks A depends on all bits of b, c, and d.
Actually, any input block of the 2nd cipher depends on at least 3*128
bits of a @ b @ c @d,
so the distinguisher from above doesn't work any more.

Note, that the function F is bijective and selfinverse, whatever f you
choose.

If I'm reading the expression correctly it can be rewritten as
s = a ^ b ^ c ^ d
a' = a ^ f(s)
b' = b ^ f(s)
c' = c ^ f(s)
d' = d ^ f(s)
I assume this is one round, designed to be repeated. Unfortunately, this is insecure.

a^b = a'^b' = a ^ f(s) ^ b^f(s), f(s)^f(s) ==0x000...000
b^c = b'^c'
c^d = c'^d'
d^a = d'^a'

Other combinations are possible. Since a'^b' can be openly computed the right hand side of all the equations is given, from there, 4 algebraic equations with 4 variables makes the equations easily solved giving the inputs to that round. Any number of rounds can then be unwound as will. If a CBC_encrypt is inserted between them (one alternative reading of the statements) then at 4 rounds it is provable as a AONT, any earlier and the saturation limits the amount of entropy that can be stirred together. The only other assumption required is that f be bijective, otherwise the entropy loss increases the number of rounds necessary.

Using the identity function for f would work.
With the left shift
f(x) := x<<1
the bijectivity of f doesn't hold anymore, but it works better than
before,

It will also be less secure. Because f() will be mapping 128 bits to 127 bits, f() cannot preserve all possible input combinations leading to a slight degeneration in the security.

as any input block of the first cipher depends on at least 3*127+128
bits of a @ b @ c @d,
Using bitwise rotation would work even better.
The ideal solution is
f(x) := 2*x (computed in GF(128))
which is bijective and makes all input blocks depend on all bits of a
@ b @ c @ d.

If it is bijective any mixing function that mixes the previous output blocks equally among the next input blocks has the same 4 round proof, so any will work.


The idea is very simple but I wasn't able to describe it any shorter.

It has flaws, the blocks are not fully mixed, at least not to the degree
that you seem to desire. Block[0] is fully diffused into Block[1], but only
half the data from Block[0] gets to Block[2], and 1/4 gets to Block[3]. It
would be secure, but doesn't have the warm fuzzies.

Could you elaborate on it? "half the data", how it comes to it?

It is the saturation. After encryption Block[0] has an apparent entropy of 1 bit per bit. Combining this with Block[1] the saturation limit for entropy is 1 bit per bit so some entropy must be lost. After the encryption of Block[1] because the encrypted block is apparently 1 bit of entropy per bit and the transform is unknown the Block[0] entropy must be part, but since Block[1] can have any value, the entropy values can be assumed to be equal (at least after the first round) so the EncryptedBlock[1] has half of its entropy from Block[0] and half from Block[1], so when EncryptedBlock[1] is combined with Block[2] only half the apparent entropy comes from Block[0] (through some extreme weirdness the math also says that all the entropy of Block[1] is brought along for some very complicated reasons). As a result only half of Block[0] impacts Block[2], and it can actually be argued that the amount is far less. It is also worth noting that it can get very bizarre.


The way I proposed is provably an All-Or-Nothing-Transform as
long as the cipher includes a complete Avalanche Effect.

Could you point me to the proof?

I'm not aware of a published one, and it is too long to publish a useful form here. A brief sketch would be that because AES is a perfect diffuser across 128-bits (otherwise the encryption is weak). It is easier to do the math in reverse, the first round of mixing leave 75% of the entropy outside the block, the CBC leaves at most 87.5% of the entropy from other blocks, so a single round leaves 65.6% of the entropy outside at the end of the first full round. The same holds for the second full round leaving 43% outside. The third full round brings 28.2%, the fourth 18.5%, since the AES operation is a perfect diffuser for 1/4 of the bits anything under 25% results in perfect diffusion. So four rounds is provable with CBC.

Even when you don't know who to trust, you can always trust math,
the paper itself is short, the proof actually rather approachable for cryptographic proofs.

By accident, I read the paper about EME* instead... the proof has over
23 pages.

For cryptography that is approachable. It is not uncommon to see proof sketches that are 20 pages.

The paper about EME is shorter, I haven't read it yet, however, I
believe I can trust it.
But EME is patented, isn't it?

Honestly, I don't know.


In order to be secure the PRF needs to be secure, since the PRP of a good
block cipher as the most analyzed it would seem most reasonable to use them.
The big question though is, how many rounds is actually enough? Since the
behaviors of the central PRF haven't been completely masked (by the change
in birthday effects) 4 rounds is not necessarily enough for security, and an
in depth analysis of the final structure would be necessary.

Is the problem using a secure PRP in the Luby-Rackoff construction,
which was designed for a PRF?

There is no problem using a secure PRP in place of a secure PRF in Ruby-Lackoff. A PRP is by definition a PRF.

Oddly, my recommendation is beginning to change. The proof of security of EME* or any of the other disk encryption modes is certainly at the same level of capability as my AONT proposal, but since the designs have more research into them they are generally more efficient. Just to make it very clear, my proposal requires four layers of encryption, EME requires 2, so it is twice the speed. This advantage cannot be denied. So even though my proposal is of equal security, I think given the choice to implement it myself, I would probably use one of the disk encryption modes.
Joe

.

Relevant Pages

  • Re: CryptGetRandom API
    ... Sergei writes: ... The other way round. ... Entropy can be related to information. ... If you have an entirely predictable stream, ...
    (sci.crypt)
  • Re: Toaster to Generate Random Numbers
    ... >> a hash function contains most of the entropy in the input. ... >> The expected lost of entropy can be estimated analytically, ... some round off error:- {) ...
    (comp.security.misc)
  • Re: Toaster to Generate Random Numbers
    ... >> a hash function contains most of the entropy in the input. ... >> The expected lost of entropy can be estimated analytically, ... some round off error:- {) ...
    (sci.crypt)
  • Re: "crypto groupie" beginning to mature
    ... > I'm beginning to wonder how commercial products create and use encryption ... By this I mean that every bit of key space available to the cipher ... a properly design cryptosystem will maximize the usage of available ... private entropy to seed a cryptographic PRNG that makes session keys. ...
    (sci.crypt)
  • Re: Encyption of two 256-blocks
    ... Moreover, there's no key, so it can't be a cipher. ... Any number of rounds can then be unwound as will. ... the saturation limits the amount of entropy that can be stirred together. ... After encryption Blockhas an apparent entropy of 1 ...
    (sci.crypt)