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). If a collision is catastrophic, even a chance of 0.1% (of loosing your banking password) is unacceptable. A rule of thumb is less than 1ppm collision chance for normal applications, 10^-9 for higher security applications is necessary.
10^-9 > 1.5 k^2/n, with n = 2^128 gives the bound for k < 2^64 sqrt(10^-9/1.5) = ~ 2^39. Laszlo > -------- Original Message -------- > Subject: Re: P1619 D4 draft > From: dtufs <[EMAIL PROTECTED]> > Date: Thu, February 23, 2006 6:45 pm > To: [email protected] > > > Enclosed is the latest draft of P1619 (D4). > > Hello, > > First of all, I'd like to point out that I'm just a > bystander, not a member of the P1619 group. I've read > the latest P1619 draft (disk) and would like to > comment on it. > > > Regarding Appendinx C.3 p.26: > > It says: > "When using AES as the underlying block cipher, we > have n=128 and the expression 3q**2/2**n would be > small > enough as long as q is not much more than 2**40." > > I believe the last figure is incorrect. The last > sentence should read: "as long as q is not much more > than 2**63." > > Here is the substantiation: q**2/2**n is the birthday > paradox limit for a PRP. The LRW mode limit is > 3q**2/2**n, that is: 3(q**2)/2**n. Obviously, the LRW > bound is only 3 times smaller than the birthday bound. > Hence, for LRW bound, the max. q should be > ((2**64)**2)/3 = ~2**63.2 > > > Therefore, I would suggest removing the sentence that > directly follows: > > "This means that practically speaking there should be > no problem using the same key to encrypt a terabyte of > data (which gives q=2**36 blocks), but one probably > should not be using the same key for a petabyte of > data (2**46 blocks)." > > > And also in Appendinx C.5 Miscellaneous I would > suggest removing this paragraph: > > "As discussed above, typically one should not use a > single cryptographic key for more than a few dozen > terabytes of data. We note that this limitation is not > unique to this standard. It comes directly from the > fact that AES has block size of 128 bits. This > limitation is not mitigated by using AES with a > 256-bit > key." > > > The reason for the removal would be the fact that > 2**63 blocks is more than one hundred thousand > exabytes, which does not seem realistic to be reached > before LRW-AES is superseded by something even more > advanced. > > Regards, > Ian Malik > > __________________________________________________ > Do You Yahoo!? > Tired of spam? Yahoo! Mail has the best spam protection around > http://mail.yahoo.com
