Re: Why is RMAC resistant to birthday attacks?
On Tue, Oct 22, 2002 at 11:09:41AM -0700, bear wrote: Now Bob sends Alice 2^32 messages (and Alice's key-management software totally doesn't notice that the key has been worn to a nub and prompt her to revoke it). Reviewing his files, Bob finds that he has a January 21 document and a September 30 document which have the same MAC. What does Bob do now? How does this get Bob the ability to create something Alice didn't sign, but which has a valid MAC from Alice's key? Call the Jan 21 document x, and the Sept 30 document y. Now Bob knows MAC_Alice(x | z) = MAC_Alice(y | z) for all z, because the internal states of the MAC after processing x and y are the same and therefore will remain equal given identical suffixes. So he can get a MAC on x | z and it's also a valid MAC for y | z, which Alice didn't sign. This applies for CBC-MAC, DMAC, HMAC, and any another MAC that is not randomized or maintains state (for example a counter) from message to message. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Why is RMAC resistant to birthday attacks?
On Tue, Oct 22, 2002 at 12:31:47PM -0700, Ed Gerck wrote: My earlier comment to bear applies here as well -- this attack can be avoided if only a subset of the MAC tag is used I can't seem to find your earlier comment. It probably hasn't gone through the mailing list yet. I don't see how the attack is avoided if only a substring of the MAC tag is used. (I assume you mean substring above instead of subset.) The attacker just needs to find messages x and y such that the truncated MAC tags of x|0, x|1, ..., x|n, matches those of y|0, y|1, ..., y|n, and this will tell him that there is an internal collision between x and y. n only has to be large enough so that the total length of the truncated MAC tags is greater than the size of the internal state of the MAC. OR if the message to be hashed has a fixed length defined by the issuer. Only one of these conditions are needed. No I don't think that works either. The attacker can try to find messages x and y such that MAC(x|0^n) = MAC(y|0^n) (where 0^n denotes enough zeros to pad the messages up to the fixed length). Then there is a good chance that the internal collision occured before the 0's and so MAC(x|z) = MAC(y|z) for all z of length n. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Lucky's 1024-bit post [was: RE: objectivity and factoring analysis]
Sorry, there's a mistake in my post, which makes the relationship finding phase look easier than it actually is. BTW, why did it take 5 days for that post to go through? On Wed, Apr 24, 2002 at 12:30:26PM -0700, Wei Dai wrote: Using a factor base size of 10^9, in the relationship finding phase you would have to check the smoothness of 2^89 numbers, each around 46 bits long. Obviously there are not 2^89 integers that are 46 bits long. Each of the numbers that need to be checked for smoothness is actually around 195 bits long. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Lucky's 1024-bit post
On Wed, May 01, 2002 at 01:37:09AM +0200, Anonymous wrote: This is probably not the right way to approach the problem. Bernstein's relation-finding proposal to directly use ECM on each value, while asymptotically superior to conventional sieving, is unlikely to be cost-effective for 1024 bit keys. Better to extrapolate from the recent sieving results. Yes, good point. For about $200 you can buy a 1000 MIPS CPU, and the memory needed for sieving is probably another couple of hundred dollars. So call it $500 to get a computer that can sieve 1000 MIPS years in a year. You need a lot more than a couple of hundred dollars for the memory, because you'll need 125 GB per machine. See Robert Silverman's post at http://groups.google.com/groups?hl=enselm=8626nu%24e5g%241%40nnrp1.deja.comprev=/groups%3Fq%3D1024%2Bsieve%2Bmemory%26start%3D20%26hl%3Den%26scoring%3Dd%26selm%3D8626nu%2524e5g%25241%2540nnrp1.deja.com%26rnum%3D21 According to pricewatch.com, 128MB costs $14, so each of your sieving machines would cost about $14000 instead of $500. If we are willing to take one year to generate the relations then ($500 / 1000) x 8 x 10^10 is $40 billion dollars, used to buy approximately 80 million cpu+memory combinations. ($14000 / 1000) x 8 x 10^10 is $1.1 trillion. So my earlier estimate for a $10 trillion 4-month machine was only off by a factor of 3, which is a nice coincidence. :) (Too bad about the memory, otherwise you can get your sieving machine almost for free by writing a worm to take over half of the Internet, which currently has about 190 million hosts.) - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Lucky's 1024-bit post [was: RE: objectivity and factoring analysis]
I have one other question about the panel analysis. Why did it focus only on the linear algebra part of the NFS algorithm? I would like to know, given the same assumption on the factor base size (10^9), how much would it cost to build a machine that can perform the relationship finding phase of the algorithm in the same estimated time frame (i.e. months)? Using a factor base size of 10^9, in the relationship finding phase you would have to check the smoothness of 2^89 numbers, each around 46 bits long. (See Frog3's analysis posted at http://www.mail-archive.com/cryptography%40wasabisystems.com/msg01833.html. Those numbers look correct to me.) If you assume a chip that can check one number per microsecond, you would need 10^13 chips to be able to complete the relationship finding phase in 4 months. Even at one dollar per chip this would cost ten trillion dollars (approximately the U.S. GDP). So it would seem that it's still not possible for even a major government to factor 1024-bit keys within an operationally relevant time frame unless it was willing to devote most of its national income to the effort. BTW, if we assume one watt per chip, the machine would consume 87 trillion kWh of eletricity per year. The U.S. electricity production was only 3.678 trillion kWh in 1999. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
