So far, I have not seen any substantiation of the 10**-9 figure. I ask again: Why not 10**-10? Why not 10**-11? To me it's apparently a figure that someone just made up. In contrast, the birthday bound used for evaluation of security of RNGs and hash functions, 2**(n/2), is substantiated. And _that_ is what's actually used in cryptography in such contexts. 10**-9 is not. Therefore I'm asking for a substantiation.
--- [EMAIL PROTECTED] wrote: > Ian, > > >> Could you describe the "weak form" in detail > please? > > It is what you used. Choose randomly k elements > (repetition allowed) > from n different ones. What value of k gives a 50% > chance of a > collision, that is, having at least two equal chosen > elements? The > strong form, what is much more useful, tells the > probability of the > collision for any (n,k) pair: > P(n,k) = 1-n!/(n-k)!/n^k. > For example, P(100,12) = 1-100!/88!/100^12 = ~0.497. > It means, there is > a 50% chance of a repetition when choosing 12 > elements from 100. The > original birthday paradox is formulated by > P(365,23) = 1-365!/(365-23)!/365^23 = ~0.507, > that is, there is a 50% chance that among 23 > randomly chosen people at > least two have the same birthday (excluding leap > days). Here, the days > of the year represent the different elements and the > birthday of the > chosen people represent the choosing. This is > elementary probability > theory, in the high school level. > > The equation for P(n,k) can be simplified using > Stirling's approximation > and the Taylor expansion of the log and exp > functions. They are accurate > enough if the discarded high order terms are small. > > >> [From the strong form, you get back the week form > (approximately) with simple arithmetic.]How? > > If you want to know, how many samples to take, such > that a collision > occurs with a 50% chance, solve the equation > 0.5 = 3 k^2 / (2n) > You get n = 3k^2 or k = sqrt(n/3). This is middle > school math. > > But don't forget, this is approximate, the > simplified collision > probability formula is valid, if k and n/k^2 are > large (at least 10 to > get an error around 10%). For the 50% case this > approximation gives k = > 6, when choosing from 100 elements, that is, a > factor of 2 error, > because n/k^2 is not large enough. Still, you get > the right order of > magnitude. > > >> So you are saying that a 10% chance makes a > secure system? > > I recommend that you read my emails before you > reply. I said that a > failure probability less than 10^-9 makes a secure > system. It means, > having built a hundred million of this system, there > is only 10% chance > than one has a block collision. Any single one fails > with a probability > of less than 10^-9. In a 5 out of 90 lottery, the > chance of winning the > grand price is 20 times higher. And the chance that > the disk drive fails > completely is thousand times higher. > > >> [How much chance do you want to take?] Zero. > > You are out of luck. I can guess your password with > greater probability. > > >> ...where did this 10% come from? What is it based > on? > > You can argue that a disk manufacturer should take > only 1% chance of a > lawsuit, whatever. The actual numbers used in the > industry depend on > more factors: the chance that a customer discovers > the problem, he > actually suffers significant loss, the chance that > he sues the > manufacturer, the cost of a litigation vs. the cost > of improving the > security of 100 million disk drives. For our > discussions, it does not > really matter. A factor of 100 change in this > collision probability > means a factor of 10 change of the recommended > number of blocks > encrypted with the same key. It is adding or > subtracting barely more > than 3 in the exponent of 2. > > >> how I would explain this limit to my customers > > You don't have to explain the 10%, but the chance of > collision being 20 > times less than winning in the lottery. Or, compare > it to the chance of > being killed in a car accident or of being hit by > lightning. But you are > probably better off not to mention it at all. Do you > want to explain > that English texts have about 1.6 bit entropy per > letter, and so a > password has to be at least 40 letters long? Random > guessing and > collisions are general security issues, every block > cipher and hash > function has similar problems. If you have > difficulties understanding > the unavoidability of collisions or the non-zero > probability of > successful password guessing, you should not sell > security equipment. > > Nevertheless, you have a valid point: in the > proposed standard a > recommendation or requirement of this kind should be > explained better, > just to avoid questions like yours. > > Laszlo > > -------- Original Message -------- > > Subject: RE: P1619 D4 draft > > From: dtufs <[EMAIL PROTECTED]> > > Date: Sat, February 25, 2006 8:25 am > > To: STDS-P1619@listserv.ieee.org > > > > --- [EMAIL PROTECTED] wrote: > > > > > What you are referring to is a weak form of the > > > birthday paradox > > > > I've never heard that birthday paradox had two > > "forms". Could you describe the "weak form" in > detail > > please? > > > > > > > From the strong form, you get back the week > > > form (approximately)with simple arithmetic. > > > > How? > > > > > > > > > If you have 50% chance that the crypto breaks on > > > > your hard disk, it is not a secure system. > > > > So you are saying that a 10% chance makes a secure > > system? Is the difference between 50% and 10% > > considerable? A secure system is where the chance > is > > negligible, i.e., close to zero. Can you see why > it is > > infeasible to specify the _lower_ bound? (Lower > bound > > is two blocks.) > > > > > > > How much chance do you want to take? > > > > Zero. > > > > > > > Accepting 10% risk > > > > Again, where did this 10% come from? What is it > based > > on? The birthday bound, 2**(n/2), is commonly used > > when assessing security of hash functions or RNGs. > > This bound is perfectly substantiated. Collisions > in > > PRPs and PRFs are statistically not to be expected > > sooner than after 2**(n/2) querries. For LRW this > > bound is three times lower. Which gives us > ~2**63.2 > > querries for 128-bit blocks. This is the _upper_ > > bound, yes. So going close to it is not > recommended. > > But this is substantiated. 10% is not based on > > anything. You can get a collision after just two > > querries. The _lower_ bound for PRPs is q=2. > > > > If you want to use 10% bound, then back it up by > > something. I don't know how I would explain this > limit > > to my customers. It appears to be just made up (a > nice > > round figure). Can anyone see the problem? > > > > Regards, > > Ian Malik > > > > > > __________________________________________________ > > Do You Yahoo!? > > Tired of spam? Yahoo! Mail has the best spam > protection around > > http://mail.yahoo.com > __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com
