RE: 1619: LRW collision probabilities
Matt has a good point.
Shai's calculations are approximate, and only valid if the number of
encrypted blocks are much smaller than the birthday bound. (If a=b, a=c =>
b=c, therefore the events are never independent.)
As I explained in the last teleconference, even this rough estimate is only
valid with the extra assumption: the plaintext is "independent" on the
location it is written to. In particular, no arithmetic sequences
(including identical plaintexts), or members of small sets are allowed.
This was the point (Matt raised and I fully agreed with), why known
plaintext attacks are not feasible in many secure storage applications.
Still, if restrictions are based on worst case estimates, these additional
requirements don't matter.
"Matt Ball"
Sent by:
stds-p1619@LISTSE To
RV.IEEE.ORG "Shai Halevi", "SISWG"
No Phone Info <stds-p1619@IEEE.ORG>
Available cc
Subject
08/14/2006 12:26 RE: 1619: LRW collision
PM probabilities
Hi Shai,
I'm still not quite satisfied with the equation for computing the
collision-
probability.
> --------------------------------------------------------------------
> Compare a setting where you have a 16GB storage (=2^34 bytes) that you
> overwrite 1024 times to the setting where you have a 16TB storage (so
> in both cases you perform 2^40 block-encryptions). Consider first the
> case of small storage. Denote by P_{I,j} the j'th plaintext block that
> was written in location I. A collision event occurs if there exist two
> pairs (I,j) and (I',j') with I<>I' such that
>
> K2 = (P_{I,j} xor P_{I',j'}) / (I xor I')
>
> The number of such pairs is 2^40*(2^30-1)*1024/2, because every pair
> (I,j) can potentially collide with all other pairs *except* the ones that
> have the same I component. Hence, a good estimate for the probability of
> collisions (when K2 is chosen at random) is
>
> (2^40*(2^30-1)*1024)/(2*2^128) ~= 2^{-49}*(1-2^{-30})
>
Just because each pair *can* collide with any other pair does not make
the probability statistically independent (which is necessary for an
accurate birthday-bounds computation). Given that (I xor I') frequently
equals the same value (example: 0 xor 1 = 2 xor 3), I'm not convinced
that it's possible to use conventional statistical methods. Since (I xor
I')
does not introduce very much variation, it is then necessary for the
plaintext (P_{I,j} xor P_{I',j'}) to provide entropy and statistical
independence, which is hard to require.
Let's take an example where each 16-byte block of plaintext randomly
has one of two values (zero and one, for example). In this case, the
plaintext effectively provides 1 bit of entropy per block. Let's also
assume that the user has encrypted 2^64 such blocks using a random K2.
Also assume that the values for I are in the range (0..2^64-1) and that
the upper 64 bits are always zero.
In this example, we have a collision when the following is true:
K2 = 1 / (I xor I')
(use Shai's equation above and substitute "P_{I,j} xor P_{I',j')" = 1,
which is the XOR of the two possible plaintext values.)
Since there are 2^64 different values for (I xor I'), then there are only
2^64 different ways to hit a collision instead of the usual "2^64 choose
2".
In this example, either K2 is such that there are zero collisions, or
there are roughly 2^64/2 collisions. In this example, there are about 2^64
"weak keys" which cause a massive plaintext leak. The other 2^128 - 2^64
keys
have no chance of leaking plaintext. If we average this out, we still
arrive
at 2^64 as an 'approximate' birthday-bound, but the distribution is such
that
certain K2 and plaintext distributions have a collision bound close to
2^128,
and others have a collision bound closer to something like 2^32.
The bottom line is this: The security of LRW strongly depends on the
relation
between K2 and the plaintext. With a random K2, there is a reasonably good
chance
that K2 is strong, but its strength depends strongly on the nature of the
plaintext.
I would still like to see some better research on the subject. I think
that
Landon might be performing such research.
-Matt