Ian, What you are referring to is a weak form of the birthday paradox: how large the sample set needs to be (k) to get a collision with 50% chance. What I wrote is the strong form, which tells you the probability of a collision for any number of queries, when k^2/n is small. From the strong form, you get back the week form (approximately) with simple arithmetic.
I wrote, "if a collision is catastrophic"... If you have 50% chance that the crypto breaks on your hard disk, it is not a secure system. How much chance do you want to take? A disk manufacturer produces about 100 million disk drives a year. Most of them will be encrypting data in the very near future, and many of them would face some kind of automated attacks (viruses). If only one breaks, it could bring a multi-million dollar lawsuit, and large loss of trust, and marketing disadvantage. Accepting 10% risk of this to happen gives the requirement of 10^-9 chance of a collision. Of course, with other means we can ensure that such collisions won't have catastrophic consequences. This is a different topic. The P1619 specification only limits the key scopes. If you have a larger disk or disk array, you should partition it into different key scopes. There is no practical limit on the disk capacity. Judging from your question, it has to be clarified more in the standard. Laszlo > -------- Original Message -------- > Subject: RE: P1619 D4 draft > From: dtufs <[EMAIL PROTECTED]> > Date: Fri, February 24, 2006 3:01 pm > To: [email protected] > > --- [EMAIL PROTECTED] wrote: > > > The birthday paradox says, that choosing k entries > > (with repetitions) from n different ones gives a > > collision with the approximate probability > > 3 k^2 / (2n). > > Actually, the birthday paradox says that it is likely > that you will find a collision after 2**(n/2) querries > to n-bit oracle. Hence, the attacker's advantage is > q**2/2**n, which must be < 1. This is the upper bound. > For LRW, this bound is three times lower. Therefore, > we take (q**2)/3, which gives us (2**64**2)/3 = > ~2**62.2**2 > > The _upper_ bound for LRW is therefore ~2**62.2 > querries (blocks). > > > The _lower_ bound cannot be determined. Therefore, > ~2**39 appears to be based on hand waving. If you > disagree, then where did 10^-9 come from? How do you > explain this value? What is it based on? Why not > 10^-10? How is it substantiated? > > > If AES-LRW was specified to be usable only for not > more "than a few dozen terabytes of data" then it > would soon be useless. > > Regards, > Ian Malik > > __________________________________________________ > Do You Yahoo!? > Tired of spam? Yahoo! Mail has the best spam protection around > http://mail.yahoo.com
