Re: 1619: LRW collision probabilities
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