Re: On hash breaks, was Re: First quantum crypto bank transfer
>From: Jerrold Leichter <[EMAIL PROTECTED]> >Sent: Aug 24, 2004 7:18 AM >To: Joseph Ashwood <[EMAIL PROTECTED]> >Cc: [EMAIL PROTECTED] >Subject: Re: On hash breaks, was Re: First quantum crypto bank transfer [[Note: I've tried to sort out who wrote what, but something odd was going on in the quoting of the messages, so I may have it all wrong]] ... >| Actually for years the cryptography community has been saying >|"retire MD5," ...because it's been seen as giving too short a hash, >|and because of a minor weakness - widely described as >|"certificational" - in the compression function that no one ever >|showed lead to an attack. (While the details of the current attack >|aren't yet completely clear, the fact that it worked on so many >|functions strongly indicates that the particular weakness in the MD5 >|compression function has nothing to do with it.) >The advice may have been prudent, but it doesn't rise to the level of >a theory for distinguishing good from bad hash functions. How about this: When someone finds any collision at all in your hash compression function, even a pseudocollision or a free-start collision, it's time to change hash functions. This is true, even when the alternatives are slower, and the existing attacks don't yet turn into a full attack. Also, when your collision resistance is known to be vulnerable to brute-force collision attacks, you really need to stop using it. Even when the alternatives are slower, and you think you can maybe get away with using MD5 here if the stars all line up properly. Now, for fielded hardware and (to some extent) software, you can try to phase out the use of the broken primitive, if the attack isn't yet leading to a practical fast collision-finding algorithm. If MD5 had started being phased out when the pseudocollision attack was found, or even when the Dobbertin attack was found, it seems like we'd be in better shape now. ... >| So basically I encourage my clients to maintain good business >| practices which means that they don't need to have belief in the >| long term security of AES, or SHA-1, or RSA, or . This is >| just good business, and it is a process that evolved to deal with >| similar circumstances. >Real good business practice has to make judgements about possible >risks and trade them off against potential costs. I quite agree that >your advice is sound. But that doesn't change the facts: Our >theoretical bases for security are much weaker than we sometimes let >on. We can still be surprised. True. But was anyone surprised at another attack on MD5, which had already had two high-profile attacks on its compression function? Was anyone surprised at an attack on HAVAL? >Suppose a year ago I offered the following bet: At the next Crypto, >all but one of the widely-discussed hash functions will be shown to be >fundamentally flawed. What odds would you have given me? You would have lost the bet. Where's the fundamental flaw in SHA1, SHA256, SHA512, or RIPE-MD160? Where's the fundamental flaw in Whirlpool? There may *be* such flaws in any or all of these hashes, but they haven't been shown yet. (Phil Hawkes' results on SHA256 look interesting; it will be interesting to see if they lead anywhere, but it sure doesn't look trivial to control those corrective patterns with choices of message block differences.) >What odds would you have given me on the following bet: At the next >Crypto, an attack against AES that is substantially better than brute >force will be published? If the odds were significantly different, >how would you have justified the difference? Remember that we had the algebraic attacks, which claimed the ability to break the whole AES, though the attacks apparently don't work as claimed because of a miscounting of variables. (It's certainly possible that someone will find an algebraic attack on AES.) >Let's update the question to today: Replace "widely-discussed hash >functions" with "SHA-1 and the related family". Keep the AES bet >intact. But let's got out 5 years. Now what odds do you give me? >Why? I don't know. If you had to build something today to be secure, it wouldn't be crazy to use SHA1, IMO. But you just can't ever rule out cryptanalytic advances of this kind. I think the difference between block ciphers and hash functions is that there's a much better developed theory of block cipher design and analysis in the public world than for hash function design and analysis. This may be changing, though. And new attacks (algebraic attacks, the integral attack that is so effective against reduced-round Rijndael versions) are always coming up, even so. I think seriously trying to beat up on o
Re: On hash breaks, was Re: First quantum crypto bank transfer
- Original Message - From: "Jerrold Leichter" <[EMAIL PROTECTED]> Subject: Re: On hash breaks, was Re: First quantum crypto bank transfer | (they all have backup | plans that involve the rest of the SHA series and at the very least | Whirlpool). Moving to a larger hash function with no underlying theory isn't very far from the "million-bit key" algorithms you see all over the place. Bigger probably can't be worse, but is it really better? The key expansion problem is why the rest of the SHA series is present, and Whirlpool is present because of the fundamental flaw problem. The truth is that having a diversity of options for this is simple enough, it takes only a small amount of additional work to allow a cryptographic function to be easily replaced, and making it replacable by 1000 is only marginally more difficult than 2, the four I listed are well-built, which is why they are the recommended ones. Suppose a year ago I offered the following bet: At the next Crypto, all but one of the widely-discussed hash functions will be shown to be fundamentally flawed. What odds would you have given me? I think it would be important to change the phrasing a bit to make the odds more quantifiable, simply chagne "At the next Crypto" to "By the end of the next Crypto." With that said considering history, I would've put the odds at ~~5:1 (Current hash functions seem to be broken quite often, and being the house I want the odds in my favor). But you are correct in that this represents a major advance in the state of the art, one that has taken large portions of the security community completely blind, I simply took the opportunity to push the concept of good business planning into this as a way that allows a good escape plan should anything happen. What odds would you have given me on the following bet: At the next Crypto, an attack against AES that is substantially better than brute force will be published? If the odds were significantly different, how would you have justified the difference? Very different odds actually, we as a group have a much better understanding of block ciphers than hash functions, as evidence the just published 4 for the price of 2 break (cryptography list post by "Hal Finney" Subject: More problems with hash functions 8/20/2004). However AES has one of the smallest security margins available, so let's put it around 10:1, I really don't expect a break, but I would not be excessively shocked to see one made. It is for this very reason that again I recommend to all my clients that the have backup plans here as well, all the AES finalists, and Camellia because of it's Nessie selection. Let's update the question to today: Replace "widely-discussed hash functions" with "SHA-1 and the related family". Keep the AES bet intact. But let's got out 5 years. Now what odds do you give me? Why? SHA series 1:1 AES 3:1 Whirlpool 3:1 (even though it wasn't asked) Camellia 3:1 Of SHA and Whirlpool being felled by the same attack in the next 5 years 100:1 AES and Camellia by the same attack within 5 years 30:1 SHA in five years because the SHA methodology is showing some cracks, there are only minor differences between SHA-0 and SHA-1, and the differences between SHA-1 and SHA-256/384/512 are basically just matters of scale, I expect to see a major break against the methodology within 10 years, and with the current renewed interest in hash functions I expect the manpower to be available very soon to find that break. AES is a very solid algorithm, but it's security margin is too close for me, this is always solid evidence that a break may be just around the corner, that the evidence is that various agencies don't have a break is irrelevant, the current evidence is that the general cryptographic community is < 10 years behind and gaining quickly.. Whirlpool has the same odds as AES because the underlying cipher is based on the same methodology, by the same people, so if it has a flaw it is likely to be extremely similar. Camellia simply does not have the examination behind it that the AES finalists do, something that makes me nervous and why it is only a backup algorithm. SHA and Whirlpool are unlikely to all at the same time because they have fundamentally different cores, SHA is a hash constructed primitive, Whirlpool a block cipher constructed primitive based on a chaining mode. This makes the odds of a single attack felling both slim at best. This odd is probably slanted too far in my favor. AES and Camellia by the same attack is more likely because the tools against block ciphers are generally cross borders capable, and the differences between the styles in Camellia and AES are simply not great enough to prevent this. The difference in the styles though represent
Re: On hash breaks, was Re: First quantum crypto bank transfer
Joe Ashwood writes: > Except for RIPEM there were known to be reasons for this, MD5 was > known to be flawed, SHA-0 was replaced because it was flawed (although > knowledge of the nature of the flaw was hidden). Even with RIPEM (and SHA-1 > for the same reason) I have plans in place (and have had for some time) the > move away from 160-bit hashes to larger ones, so the attack on RIPEM had > little effect on me and my clients... A minor terminology correction: the hash is RIPEMD, the more recent (and still unbroken) version being RIPEMD-160. RIPEMD is the RIPE Message Digest, where RIPE is the EU's RACE Integrity Primitives Evaluation project, and I haven't been able to find out what RACE stands for. RIPEM was an old implementation by Mark Riordan of the PEM (Privacy Enhanced Email) standard which preceded S/MIME. Hal Finney - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: On hash breaks, was Re: First quantum crypto bank transfer
| > Alternatively, how anyone can have absolute confidence in conventional | > crypto | > in a week when a surprise attack appears against a widely-fielded | > primitive | > like MD5 is beyond me. Is our certainty about AES's security really any | > better today than was our certainty about RIPEM - or even SHA-0 - was | > three | > weeks ago? | > -- Jerry | | Actually for years the cryptography community has been saying "retire MD5," ...because it's been seen as giving too short a hash, and because of a minor weakness - widely described as "certificational" - in the compression function that no one ever showed lead to an attack. (While the details of the current attack aren't yet completely clear, the fact that it worked on so many functions strongly indicates that the particular weakness in the MD5 compression function has nothing to do with it.) The advice may have been prudent, but it doesn't rise to the level of a theory for distinguishing good from bad hash functions. | SHA-0 has been required to be replaced by SHA-1 for some time, because the NSA said so. It turns out they were ahead of public crypto by a couple of years. I will grant you that this is indirect evidence that NSA has no attacks on AES, since this is now the second time that they've strengthened a proposed primitive against which no publically-known attacks existed. It tells us little about how strong AES actually is - and absolutely nothing about any other system out there, since NSA has no reason to comment on those and every reason not to. | the RIPEM | series is functionally-speaking unused ...but not because anyone thought there was a weakness. MD5 happened to be widely used, SHA-1 had standards pushing it; little room was left for another hash. |and represented the only real | surprise. Except for RIPEM there were known to be reasons for this, MD5 was | known to be flawed, SHA-0 was replaced because it was flawed (although | knowledge of the nature of the flaw was hidden). Even with RIPEM (and SHA-1 | for the same reason) I have plans in place (and have had for some time) the | move away from 160-bit hashes to larger ones, so the attack on RIPEM had | little effect on me and my clients, even a full attack on SHA-1 would have | little effect on the clients that actually listen (they all have backup | plans that involve the rest of the SHA series and at the very least | Whirlpool). Moving to a larger hash function with no underlying theory isn't very far from the "million-bit key" algorithms you see all over the place. Bigger probably can't be worse, but is it really better? | So basically I encourage my clients to maintain good business practices | which means that they don't need to have belief in the long term security of | AES, or SHA-1, or RSA, or . This is just good business, and it is a | process that evolved to deal with similar circumstances. Real good business practice has to make judgements about possible risks and trade them off against potential costs. I quite agree that your advice is sound. But that doesn't change the facts: Our theoretical bases for security are much weaker than we sometimes let on. We can still be surprised. Suppose a year ago I offered the following bet: At the next Crypto, all but one of the widely-discussed hash functions will be shown to be fundamentally flawed. What odds would you have given me? What odds would you have given me on the following bet: At the next Crypto, an attack against AES that is substantially better than brute force will be published? If the odds were significantly different, how would you have justified the difference? Let's update the question to today: Replace "widely-discussed hash functions" with "SHA-1 and the related family". Keep the AES bet intact. But let's got out 5 years. Now what odds do you give me? Why? -- Jerry - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
