Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

Re: [P1619-2] another P1619.2 question: the EME2 mix function

On Mon, Mar 22, 2010 at 4:17 PM, Laszlo Hars <laszlo.hars@xxxxxxxxxxx> wrote:
> There might be a problem with EME2. Its mixing layer does not seem to be
> very secure:
> If the XOR of all the ciphertext blocks PPPi of top layer of encryptors
> happens to be the same at two sets of input plaintext blocks, the mix value
> M1 remains also the same, and so each XORed value M1*a^i in the mix layer
> also remains the same. This happens at 50% chance among 2^64 encryption
> operations. Thus, if we keep the P2...Pk plaintext blocks constant for some
> k≤m<129, and vary the others, after 2^64 random tries we find two sets of
> input at 50% chance such that the corresponding ciphertext blocks C2...Ck
> are identical. It distinguishes EME2 from a random permutation. (When
> varying the address of the target sector T* would change pseudo randomly. It
> is just XORed to the PPPs, which does not affect the random search.)
> A modern disk drive contains 2TB/512 ~= 2^32 sectors, which are filled up
> pretty soon. There are close to 10^9 ~= 2^30 encrypting disk drives
> manufactured a year, and so some user somewhere will find this strange
> situation with equal C2...Ck blocks with non-negligible probability.

This last part isn't correct. With 2^32 trials (sectors) the chance of
a 128-bit collision in a single disk is only about 1 in 2^65 by
standard birthday arguments (n^2 / 2H where n=2^32 trials and
H=2^128). Therefore close to 2^64 disks would have to be used which
would take over 10 billion years at present rates.

Hal Finney