Re: 1619: LRW collision probabilities
Shai,
> My calculations do not assumes that [blocks are written with equal
probability]
If you didn't assume that the block locations are chosen uniformly random,
your calculations would have covered the case, where most write operations
address a single block. In this case the probability of a useful collision
is very low, though.
> just replace the *shall* with a *should* in the part that talks about not
using the same key for too much data?
This was my proposal, with adding the security tradeoff expressions to the
Appendix. It was rejected with the argument that the standard must not
require an implementer to do elaborate calculations, and errors will be
made.
Laszlo
Shai Halevi
Sent by:
stds-p1619@ieee.o To
rg SISWG <stds-p1619@IEEE.ORG>
No Phone Info cc
Available
Subject
Re: 1619: LRW collision
08/14/2006 12:47 probabilities
PM
Laszlo wrote:
> Shai assumes that each block is written with equal probability, which is
> not the case in real life storage.
My calculations do not assumes that. What is assumed (implicitly) is that
the blocks are re-written with *different* values every times. Clearly,
writing the same value at the same location has no effect.
The calculations that I wrote are formally only an upper bound (obtained
by the union bound), but in pretty much all cases this upper bound is an
excellent estimate for the real number.
You can get better bounds using the inclusion-exclusion principle (i.e.,
subtract the probability that two pairs collide, then add the probability
that three collide, etc.) but then you would get into complicated
calculations and you need to start worrying about the exact distribution
of your plaintext. And since all this extra complexity just deals with
2nd-order effects (and 3rd, and 4th,...) it is quite safe to ignore it.
> This brings us back to the discussions: should mandatory restrictions be
> imposed based on the worst case situations, or leave it to the
implementer
> to decide. The WG seem to have agreed, that the worst case scenario
should
> dictate a mandatory restriction on the number of encryption operations,
> with only Seagate being against it.
I wasn't present in much of the discussion last time, so I don't know if
there was any agreement about that point. Would it satisfy everyone if we
just replace the *shall* with a *should* in the part that talks about not
using the same key for too much data?
-- Shai