Weekly Edition
Return to the Security page
| |||||||||||
Crypto researchers abuzz over flaws (News.com)
News.com reports from Crypto 2004, where researchers are presenting findings on weaknesses in secure hash algorithms.
"Biham's presentation was very preliminary, but it could call into question the long-term future of the wildly popular SHA-1 algorithm and spur researchers to identify alternatives.
Currently considered the gold standard of its class of algorithms, SHA-1 is embedded in popular programs like PGP and SSL. It is certified by the National Institute of Standards and Technology and is the only signing algorithm approved for use in the U.S. government's Digital Signature Standard."
(Log in to post comments)
Crypto researchers abuzz over flaws (News.com) Posted Aug 18, 2004 17:01 UTC (Wed) by niallm (subscriber, #3923) [Link] I think I speak for us all when I say "Oh fsck".
Crypto researchers abuzz over flaws (News.com) Posted Aug 18, 2004 17:38 UTC (Wed) by hamjudo (guest, #363) [Link] In one article we find out both that MD5 is mostly broken, and that the future doesn't look so good for SHA-1.Still, Hughes said that programmers should start moving away from MD5. "Right now the algorithm has been shown to be weak," he said. "Before useful (attacks) can be done, it's time to migrate away from it." Off the top of my head, I can think of some denial of service attacks based on the ability to create different files with the same MD5 checksum. I'm confident that others who are smarter or more devious than I, will think of some "usefull (attacks)" in short order. Where do we go from here, if we should abandon MD5, but not adopt SHA-1?
Where to, now? Posted Aug 18, 2004 17:49 UTC (Wed) by ncm (subscriber, #165) [Link] SHA-2, of course!
The SHA successors, for now Posted Aug 18, 2004 17:55 UTC (Wed) by jvotaw (subscriber, #3678) [Link] I'm sure Bruce Schneier will comment on this in the next Crypto-Gram, but my guess is: SHA-256, SHA-384 and SHA-512; they were designed after SHA-1 and hopefully are not susceptible.
-Joel
The SHA successors, for now Posted Aug 18, 2004 18:25 UTC (Wed) by mkettler (guest, #3933) [Link] Not necessarily. The design of SHA-256, etc, is the same as SHA-1. Thus, an algorithmic weakness in one is likely to be present in the other. The Ch(x,y,z) and Maj (x,y,z) that are the heart of the hash are the same for both.
The longer hash output makes SHA-256, etc, stronger against birthday attacks, but for algorithmic attacks you're not guaranteed any extra security over SHA1. You might increase the complexity, you might not. It depends on what part of the math gets attacked.
You can check for yourself reading FIPS-180-2:
http://csrc.nist.gov/publications/fips/fips180-2/fips180-...
The SHA successors, for now Posted Aug 18, 2004 19:30 UTC (Wed) by jvotaw (subscriber, #3678) [Link] I can believe that. This stuff is way over my head -- I should've emphasized the "hopefully" in my original message.
I was thinking of cases where people demonstrate a weakness in, say, a 9-round variant of an encryption algorithm, but feel safe with a 12- or 16-round variant, and was thinking the same thing *might* apply here.
But again, I'm way out of my depth.
-Joel
Collisions are not as benign as they seem Posted Aug 18, 2004 19:48 UTC (Wed) by proski (subscriber, #104) [Link] Wikipedia entry for Birthday attack describes how to exploit a hash collision for fraudulent purposes.
Collisions are not as benign as they seem Posted Aug 19, 2004 9:18 UTC (Thu) by copsewood (subscriber, #199) [Link] Interesting. One defence against the kind of birthday attack described in the Wikipedia entry would be to edit a contract before signing it, e.g. by altering whitespace in a very unpredictable manner. The meaning of the contract would be the same, but the cryptographic hash would be totally different.
may not be as bad as it appears Posted Aug 18, 2004 18:02 UTC (Wed) by ajax (guest, #7251) [Link] Generally speaking, an alternate file generating the same MD5checksum will look like gibberish rather than English or a C program or whatever. So, for example, if one download's what one thinks is apache sources, and the checksums match, and the source looks like apache, then one could have confidence that it is the unmodified Apache, even if MD5 proves to be flawed.
may not be as bad as it appears Posted Aug 18, 2004 18:24 UTC (Wed) by AnswerGuy (guest, #1256) [Link] Don't count on it.
While you may be write, and it's obvious that *most* checksum collisions would be obvious and visible (for text files) and non-functional (for executables) you're not accounting for the number of ways in which MD5 and other checksums are embedded into automated processes and protocols.
Nothing is "obviously wrong" to other software; that's a human value judgement.
Also it may be that someone might be able to pad out a file with non-obvious text or no-op code while generating a deliberate hash collision. For example one might append spaces and tabs to the ends of the(compromised/forged) document or the end of each line.
We can intuit that double checksums would make the attacker's job more difficult (using MD5 *and* SHA-1). But this intuition could be flawed and would require some qualified research to assess before it could be recommended for real business use.
I would say that the current weaknesses (theoretical and practical) are still overshadowed by more pragmatic concerns.
Most of us should continue to focus on key/signature management issues (how do we verify any given checksum, how to we verify the provenance of the checksumming utility) and social issues (did the user who generated the checksum use a compromised copy of the tool).
Meanwhile there are still niches for researchers to continue developing more secure (collision resistant) hashes and for them to continue trying to break the existing and newly proposed algorithms, and for them to quantify the security/weakness of existing, proposed, and combinations of hashes.
JimD
may not be as bad as it appears Posted Aug 19, 2004 14:46 UTC (Thu) by beejaybee (guest, #1581) [Link] Better still, for open source software, distribute checksums for object code (as compiled by a specific compiler on a specific hardware platform, which may not be the same as the platform the user of distributed source code intends to compile for, nor the same version of the compiler the user intends to use in a production environment) _in addition to_ checksums for the source code.
The point here is that even when it becomes economic to construct a fraudulent source file with a specific checksum, having the checksum of the object matching as well is at least several, possibly many, orders of magnitude more difficult. Downloading the extra checksums is a very marginal cost; whilst, if a very common compiler / hardware platform is chosen, finding a suitable system to run the integrity check on should not be too difficult.
So here's a security plus for OSS. Closed source (binary distribution) software products simply can't compete.
may not be as bad as it appears Posted Aug 18, 2004 18:47 UTC (Wed) by ncm (subscriber, #165) [Link] In principle it only takes 20 bytes of carefully-chosen garbage added to any text to give a chosen SHA-1 signature, once you've broken it.
It's often pretty easy to find a place to put that much extra stuff, buried in an ELF section or debug annotation of an executable, in extra compression table entries of a tarball, even in text of a diff that you know patch will skip, and that a human would ignore knowing that patch skips it--e.g. in a .sig.
If it must be base64, you need 30 bytes, instead; or 40 bytes of hex, or 70 decimal digits. 14 common lower-case four-letter English words suffice.
may not be as bad as it appears Posted Aug 18, 2004 20:32 UTC (Wed) by smoogen (subscriber, #97) [Link] Dont you mean SHA-0 versus SHA-1?
may not be as bad as it appears Posted Aug 19, 2004 7:24 UTC (Thu) by ekj (subscriber, #1524) [Link] That is not nessecarily so.
It depends on the details of the flaw. If the attack depends on custom-crafting the entire input, or worse yet, both inputs, to find a collision, then you are correct.
But it's possible to change only 20 bytes in a file and make the sha1sum equal. That little "garbage" could easily fit in say a comment in C code or an unused static variable in a binary program. The trick is, offcourse, how to select those 20 bytes.
With a good (as in cryptographically strong) hash there's no better way to do that than simply randomly try different garbage-strings until you find one that matches. That is impractical for a hash of sufficient size.
With a broken hash, all bets are off. It depends on the details.
Something that was always fishy... Posted Aug 18, 2004 18:12 UTC (Wed) by gproux (subscriber, #8286) [Link] Is the NSA not complaining loudly about people able to use encryption technologies. This could mean they already found how to crack it and routinely do it. I remember reading in a book that a facility that was used to host some dept of the NSA was sold after being completely cleaned-up. Still they had left some things like the comms backbone. The book was talking of literally kilometers of single-mode fibers at a time where multi-mode fiber just started to be used commercially at a large scale. Which means that the NSA is always 200 light-years ahead and that SHA-1 might have some issue that they ALREADY discovered...
Something that was always fishy... Posted Aug 18, 2004 18:34 UTC (Wed) by JoeBuck (subscriber, #2330) [Link] The spooks are ahead in some areas (for example, public-key crypto was first discovered by the British equivalent of the NSA, and only later rediscovered by Diffie and Hellman), but they aren't gods. In any case, you shouldn't think that the NSA's chief method is to apply advanced techniques no one else has to effortlessly break crypto systems. They may well do some of that, but they mainly "cheat", exploiting engineering flaws, back doors, hacking/cracking, social engineering, or the like to get access to the messages they want to read. If the NSA wants to read your encrypted traffic, they aren't going to bother breaking the algorithm. They can just 0wn your machine and retrieve the plaintext, as you type it or with a screen-reader; it's a lot easier.
Something that was always fishy... Posted Aug 18, 2004 20:16 UTC (Wed) by dfarning (subscriber, #24102) [Link] Thank God for Microsoft--
Fact: Windows has a lower cost of Total cost of 0wnership
Therefor: Widespread use MS windows reduces taxes.
I waiting to see this argument on the get the fact site;)
David Farning
Something that was always fishy... Posted Aug 18, 2004 22:56 UTC (Wed) by iabervon (subscriber, #722) [Link] On the contrary; the NSA's mission includes having the technology the government uses be secure. It probably also includes securing the nation's critical civilian infrastructure. If the NSA know about a flaw in a standard encryption component, they would immediately work on a replacement and tell people to use that. When IBM initially proposed DES, the NSA told them to change some things, which turned out to protect against an attack unknown to the cryptography community at the time.
The reason is that there have always been spies and double agents. If the USSR could get atomic secrets back then, Al Queda could get cryptography secrets today, and could destroy US finance. The only solution is to make sure that there are no such secrets.
Something that was always fishy... Posted Aug 19, 2004 6:12 UTC (Thu) by ncm (subscriber, #165) [Link] Are you smoking crack? The spooks specifically demanded that DES be weakened by reducing its key size to only 56 bits.
Something that was always fishy... Posted Aug 19, 2004 7:30 UTC (Thu) by barryn (subscriber, #5996) [Link] No, (s)he isn't smoking crack. While the NSA shortened the key length, they also changed DES to be resistant to differential cryptanalysis, well over a decade before differential cryptanalysis was discovered by anybody in the general public. (BTW, differential cryptanalysis is the basis of the attacks now being conducted against all these hash functions.)
Look at this Wikipedia article, particularly the "NSA's involvement in the design" section:
Something that was always fishy... Posted Aug 19, 2004 15:10 UTC (Thu) by mmarsh (subscriber, #17029) [Link] NSA wanted the shorter key length so that error-correction bits could be added. They didn't expect DES to be made public, from my understanding, and were somewhat upset when NBS released the DES specification.
Something that was always fishy... Posted Aug 19, 2004 15:13 UTC (Thu) by mmarsh (subscriber, #17029) [Link] NSA gave up on this because they had to, really. Once high-quality cryptography was openly being developed elsewhere in the world, keeping U.S. cryptography locked up under the provenance of NSA meant that U.S. companies, individuals, and government agencies would be at a distinct and significant disadvantage globally. Once the genie is out of the bottle, it's little worth your time trying to stuff it back in.
Crypto researchers abuzz over flaws (News.com) Posted Aug 19, 2004 9:40 UTC (Thu) by petegn (guest, #847) [Link] The obvious answer to all these problems is make the punishment for attacks on computers more of an deterant and i mean get seriously nasty with people/governments that attack other peoples computers .
None of this human rights pussy footing about smack hands naughty boy dont do it again stuff ,
10 years HARD labour down a quarry breaking rocks type thing is more like it
Want to stop things thats how get tough make life unbearable for those of a criminal leaning .
Pete .
Crypto researchers abuzz over flaws (News.com) Posted Aug 19, 2004 10:23 UTC (Thu) by rjw (guest, #10415) [Link] Are you insane?
Crypto researchers abuzz over flaws (News.com) Posted Aug 19, 2004 16:07 UTC (Thu) by dark (subscriber, #8483) [Link] I don't think you're going far enough here.Interference with a computer system is a crime so heinous, so terrible, that it warrants nothing short of the death penalty. And none of these endless appeals, either -- justice must be seen to be done. If you're dealing with a recalcitrant country that refuses to deliver its script kiddies for justice, then there's always the nuclear option.
Crypto researchers abuzz over flaws (News.com) Posted Aug 20, 2004 5:52 UTC (Fri) by vinsci (guest, #11945) [Link] You might like the The Yes Men. :-)
|
|||||||||||