Results 1 to 8 of 8

Thread: Flaws in MD5, SHA-0, and SHA-1 algorithm!

  1. #1
    AO French Antique News Whore
    Join Date
    Aug 2001

    Flaws in MD5, SHA-0, and SHA-1 algorithm!

    Encryption circles are buzzing this week with news that mathematical functions embedded in common security applications might have previously unknown weaknesses.
    The excitement began last Thursday with an announcement that French computer scientist Antoine Joux had uncovered a flaw in a popular algorithm called MD5, often used with digital signatures. Then four Chinese researchers released a paper that reported a way to circumvent a second algorithm, SHA-0.

    While their results are preliminary, these discoveries could eventually make it easier for intruders to insert undetectable back doors into computer code or to forge an electronic signature--unless a different, more secure algorithm is used.

    A third, widely anticipated announcement, which could be even more dramatic, is scheduled to take place Tuesday evening at the Crypto 2004 conference in Santa Barbara, Calif.

    Eli Biham and Rafi Chen, researchers at the Israel Institute of Technology, originally were scheduled to present a paper identifying ways to assail the security in the SHA-0 algorithm, which is known to have imperfections. Now they're promising to discuss "breaking news information" about the SHA-1 algorithm at a conference session that was set to begin at 7 p.m. PDT.

    News of serious flaws in the SHA-1 algorithm could, depending on the details, roil the computer security industry. Currently considered the gold standard of its class of algorithms, SHA-1 is embedded in popular programs like PGP and SSL. It's 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. SHA-1 yields a 160-bit output, which is longer than MD5's 128-bit output and is considered more secure.

    Jim Hughes, general chairman of the Crypto 2004 conference, said on Tuesday morning that the news was sufficiently important that he was organizing the first Webcast in the conference's 24-year history. "There are three significant rump session papers on hash collisions that will be presented," including an update on Joux's findings, Hughes said in a message to a cryptography-related mailing list.

    "If you could find two contracts that hash out to the same signature, you could replace one with the other and in a court of law there would be at least an ambiguity about which one is valid," Hughes, a senior fellow at StorageTek, said in a telephone interview. "That's a very significant possibility."

    The MD5, SHA-0, and SHA-1 algorithms are known to computer scientists as hash functions. They take all kinds of input, from an e-mail message to an operating-system kernel, and generate what's supposed to be a unique fingerprint. Changing even one letter in the input file results in a completely different fingerprint.

    Security applications rely on these fingerprints being unique. But if a malicious attacker could generate the same fingerprint with a different input stream, the cloned fingerprint--known as a hash collision--would certify that software with a back door is safe to download and execute. It would help a crook who wanted to falsely sign an e-mail instructing that someone's bank account be emptied.

    Because researchers have long known that no practical encryption algorithm can be completely secure, they attempt to design ones that take an inordinately long time to generate duplicate fingerprints. SHA-1 is regarded as secure because it is not possible to knowingly generate hash collisions using existing techniques.

    But if similar vulnerabilities in SHA-0 are discovered in SHA-1, that would mean that attempts to forge a fingerprint would be accelerated by about 500 million times--putting it within reach of a network of fast PCs.

    The weakness in the MD5 algorithm may be the more immediate threat. The open-source Apache Web server product uses MD5 hashes to assure the public that source code on dozens of mirror sites is not modified and is safe to run. So does Sun Microsystems' Solaris Fingerprint Database, which the company says can "verify that a true file in an official binary distribution is being used, and not an altered version that compromises system security."

    MD5's flaws that have been identified in the past few days mean that an attacker can generate one hash collision in a few hours on a standard PC. To write a specific backdoor and cloak it with the same false hash collision may be much more time-intensive.

    Still, Hughes says 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."
    Source : http://zdnet.com.com/2100-1105_2-5313655.html
    -Simon \"SDK\"

  2. #2
    If your databases, cookies, and htdocs are secure, then you've got no problem. But in the meantime, what is a good alternative?

  3. #3
    Senior Member
    Join Date
    Jul 2003
    A link to the /. article was posted by muert0 in the Identifying Encryption Techniques thread [Soda's]. That's only so as to etend credit where it is due

    As for this, the fact that SHA-0 was broken is more or less of a worry. With the part that a collision for MD5 is already rumored, along with the even more troublesome 'thing' identified in SHA-1, many applications would be made vulnerable quickly, or at least, not trustworthy anymore.

    And although the 32, respectively 40 bytes in MD5/SHA allow for enough combinations, I am sure there would be collisions? Since the outputs are of a fixed length [both size-wise and as a range of possible values], while the inputs are virtually infinite. But proving this theory without a doubt is definitely a step ahead for ensuring that newer, safer methods of data encryption are devised.

  4. #4
    Senior Member
    Join Date
    Sep 2001
    Well, in the meantime, there's no real cause to panic just yet...
    While it's true that SHA-0 as been shown to generate collisions, they didn't use quite regular widely availible computing power...:

    "The computation was performed on TERA NOVA (a 256 Intel-Itanium2 system
    developped by BULL SA, installed in the CEA DAM open laboratory
    TERA TECH). It required approximatively 80 000 CPU hours.
    The complexity of the attack was about 2^51."

    And all that power was applied to find a collision on meaningless 2048 bits binary messages; for the moment at least it doesn't allow you to modify the original message at your will and have it match the same hash...

    So for now the moment the possibility of an attack based on this algorithmic flaw is very remote at best. It is, however, rather concerning for the future of SHA as when such flaws are found it often leads to bigger discoveries in the algorithms... That and that for now, AFAIK, there is no better alternative to SHA-X (and most other crypto hash funcitons have already been proven unsecure...)

    Credit travels up, blame travels down -- The Boss

  5. #5
    AO Antique pwaring's Avatar
    Join Date
    Aug 2001
    Originally posted here by hypronix
    Since the outputs are of a fixed length [both size-wise and as a range of possible values], while the inputs are virtually infinite.
    It's not so much whether the collisions exist as finding them. If someone created a malicious program and wanted to upload it to apache.org for people to download they'd need to make sure that it had the same checksum (using MD5) as the existing code otherwise when people downloaded it and ran md5sum they'd know something was wrong.
    Paul Waring - Web site design and development.

  6. #6
    Senior Member
    Join Date
    Jul 2003
    I feel like such an idiot. The link was posted about Maestr0 not muert0. I guess it was the ending 0 that threw me off, anyway sorry about that.

  7. #7
    Leftie Linux Lover the_JinX's Avatar
    Join Date
    Nov 2001
    Beverwijk Netherlands

    A very good explanation (although a bit technicsl, but what'd you expect.. )
    ASCII stupid question, get a stupid ANSI.
    When in Russia, pet a PETSCII.

    Get your ass over to SLAYRadio the best station for C64 Remixes !

  8. #8
    Senior Member
    Join Date
    Oct 2001
    It required approximatively 80 000 CPU hours.
    That means it took under 2 weeks! On an Itanic2 processor! There are a lot of processors out there overall faster than this for some things, such as the Intel Xeon 2.8GHz, Opertron 144 (lowest end Opertron avaliable), and possibly the AMD AthlonXP 3200+. Of course these aren't as fast in floating point computations as the Itanium2 1.5GHz (Doubtful they had this fast of one though), but I'm pretty sure MD5 is integer math so it would get it's butt handed to it by any recent processor. So take this as a warning -- it can be done faster than that article makes is appear -- just use a faster, more recent processor farm! But luckily, by the time anyone finds a way to program a vuln and hide it in a collision, the software would probably be updated to a newer version with a new MD5 for them to crack.

    (SPEC2000 benchmarks of Opertrons / Xeon / Itanium 2 -- http://www.psds.com/products/servers/benchmark.htm)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts