Re: SHA-1 vs. triple-DES for password encryption?

From: John Viega (viega@securesoftware.com)
Date: 11/11/02


Date: Mon, 11 Nov 2002 11:38:38 -0500
To: "Oscar Batyrbaev" <batyr@ix.netcom.com>
From: John Viega <viega@securesoftware.com>

While Dobbertin's break did extend to practice quite well, that was
more a consequence of the exact attack. Plenty of algorithms have been
totally discarded after being shown to be theoretically weak to things
like differential cryptanalysis, even if the attack wasn't practical.

The goal of hashing a password a large number of times is to provide
something that is computationally hard for password guessing attacks,
but somewhat easy on the server. Users can wait a fraction of a second
for a system to respond (they're used to network latency anyway), and
the computer can have resource limits put on the process. Or, you can
just decide to do half as many hashes, but you make the password
guessing attacks easier.

I think it is a rare case where anyone should find it acceptable to
trade off adequate security to gain more efficiency... usually
efficiency isn't a significant concern.

John

On Monday, November 11, 2002, at 10:02 AM, Oscar Batyrbaev wrote:

> John,
>
> Interesting comments, I am swamped right now to reply in a great
> detail, but just
> two points:
> Dobbertin, even after MD4 was considered to be very weak, actually
> still went
> ahead and "totally broke" it so to speak.
> Same did not happen against the full MD5 yet and who knows when/if it
> will. What
> is more difficult to do brute force with bday paradox (2^32 without
> salts) or
> somehow break MD5 that was not done since 1992?
>
> 2. It is an interesting comment - but looks at it may be from the
> client system
> perspective - if the password is actually send to the server and the
> server
> software performs hash to authenticate (of course this may not be
> ideal protocol -
> but is done in practice sometimes) - imagine the performance
> importance at 9am in
> the morning...
>
> Please feel free to comment.
> Regards,
>
> Oscar Batyrbaev
> CTO B3 Security Corporation
> Tel. (408) 615-7433
> Fax: (603) 649-6498
> email: batyr@ix.netcom.com
> email 2: oscar@b3security.com
> 1200 Ranchero Way, Suite 18, San Jose, CA, 95117
>
> B3 Security Corporation Confidential
>
>
>> -----Original Message-----
>> From: John Viega [mailto:viega@securesoftware.com]
>> Sent: Monday, November 11, 2002 6:35 AM
>> To: Oscar Batyrbaev
>> Cc: CraigSecurity@blazemail.com; secprog@securityfocus.com
>> Subject: Re: SHA-1 vs. triple-DES for password encryption?
>>
>>
>> On Sun, Nov 10, 2002 at 08:46:51AM -0800, Oscar Batyrbaev wrote:
>>> Craig, cc List:
>>>
>>> Just a few short answers/suggestions:
>>> 1. truncating to 8 bytes will increase the hazard from the
>>> "birthday" paradox;
>>> Thus The risk is not 2^64 as was suggested earlier but about 2^32
>>> that the
>>> birthday attack succeeds with probability 0.5 or 50%. The risk is too
>> high even
>>> when you deal with passwords.
>>
>> This is not true, particularly if password design is done properly.
>> The birthday attack does *not* apply if there is a sufficient salt or
>> nonce. That is, you might be able to find a collision after 2^32
>> operations, but due to the presense of salt attached to the stored
>> ciphertext, the odds of being able to use that solution push the
>> security back up to 64 bits. That should be pretty intuitive, but,
>> IIRC, Rogaway was the first to prove it.
>>
>> Additionally, even if there were no salt, then the attacker
>> would have to see O(2^32) known password-hash pairs just to find a
>> single collision. That isn't a real-world scenario.
>>
>>>
>>> 2. Why not use MD5? It is significantly faster (about 5 times) than
>> SHA-1 and the
>>> "attacks" on it are very highly theoretical and basically of no
>>> practical
>>> significance (yet). Cryptographers call an attack something that
>> would work on say
>>> 2 rounds of MD5 or its compress function or if they swamp the magic
>> constants of
>>> the IV, etc. There is no full pre-image or 2nd pre-image or collision
>> attack on
>>> full MD5. We work with these type of research every day.
>>> That way you also just have to store one hashed password like two: -
>>> 16 bytes;
>>> saves you 4 bytes :). Also Rivest designed MD5 to be significantly
>>> more secure
>>> than its precursor MD4. Under the hood, SHA-1 is actually from the
>> same family of
>>> the hash algorithms as MD5 and MD4.
>>> It is often the folk who get on a soapbox without full understanding
>>> of what
>>> theoretical cryptographers call an "attack" create FUD on this
>>> issue. Or some
>>> researches who have vested interest in promoting their own hash
>> algorithms (non
>>> MDx/SHAx family).
>>>
>>> IMHO, Risks with MD5 (especially since you are not dealing with an
>> appendix to a
>>> digital signature that needs to be stored for a very long time but
>> with passwords
>>> that (supposed) to be changed and suffer from dictionary attacks to
>> begin with)
>>> are acceptable and manageable from the description of the problem.
>>
>> First, see my previous mail on the issue. You do NOT want to speed up
>> computation. If you're using MD5, you need to run far more iterations
>> than you would of SHA1 to get the difficulty up to the same level. It
>> is not good advise to recommend MD5 for speed issues.
>>
>> Second, I think your attitude toward MD5 breaks is way too liberal.
>> Dobbertin's two major attacks were against the entire MD5 compression
>> function, the entire thing, not a reduced-round version. His second
>> major assult on MD5 found collisions where the two internal IVs were
>> set to identical values, which is pretty bad (that is, the IVs
>> associated with each of two inputs that give an identical hash value).
>> Granted, the attack fails to go the last mile, but it is a good enough
>> reason to abandon MD5, at least for all new applications. I recommend
>> you look at "Cryptanalisis of MD5 Compress" by Dobbertin in FSE '96.
>> Note that, by the time this was published, Dobbertin had entered the
>> german equivalent of the NSA. I know a couple of very good
>> cryptographers who are under the impression that Dobbertin has
>> probably found a full break right now, that he's not allowed to
>> publish. It's certainly a strong possibility given that we're
>> essentially seven years out from Dobbertin's attack.
>>
>> The cryptography community tends to have a habit of developing
>> theoretical breaks on algorithms, then moving on. Turning theoretical
>> breaks into practical ones isn't interesting for most cryptographers,
>> because theoretical breaks are generally enough to cause them to
>> consider an algorithm not worth using.
>>
>> MD5 was teetering on the edge in early '96. Many cryptographers
>> believed then that MD5 was not suitable for new applications due to
>> the theoretical break. Seven years have passed, and I don't think the
>> cryptography community has really expended any energy on finishing off
>> MD5. I think that it's reasonable to expect that someone who has more
>> interests in a practical break and fewer interests in publishing
>> (particularly governments) to have finished off MD5 and not published
>> it, particularly considering how long it's been since Dobbertin's
>> attack.
>>
>> Note that you are correct in saying that SHA1 is of the same family as
>> MD5. Both are MD4-derived. The major difference is that SHA1 was
>> changed subtlety enough that it was not resistant to Dobbertin's
>> attacks. There's a strong possibility that, when NIST was
>> standardizing SHA1, that the NSA probably already knew about potential
>> problems with the design, that the cryptography community didn't
>> discover until later, and that they made sure these problems were
>> fixed before the algorithm was standardized. Remember, the NSA has a
>> huge head start over the crypto community, and we don't know exactly
>> what they know. We've only gotten to see a sliver of what they
>> probably knew years ago, when algorithms they had a hand in are found
>> to be either hardened or weak with respect to new attacks.
>>
>> All that said, MD5 attacks are less risky compared to password
>> guessing attacks if you're worried about "script kiddies" and not
>> governments. Nonetheless, I cannot imagine a good reason to select
>> MD5 over SHA1. If you have space constraints, and the four extra
>> bytes of SHA1 output bother you, truncate the output. SHA1 is still a
>> very fast cryptographic primitive. Yes, MD5 is quicker, but SHA1 is
>> more than quick enough for almost any application MD5 would be
>> suitable for. For small messages, which are the norm, SHA1 performs
>> nearly as well as MD5. You could always recommend MD4 over MD5
>> because it's faster, too. I think recommending MD5 over SHA1 due to
>> speed concerns is just as wrong, considering MD5 carries a significant
>> risk in some communities that SHA1 does not carry. Sure, there are
>> applications where MD5 is probably an okay solution, but the security
>> community should not be instigating confusion by offering a more
>> complex answer than necessary. If you tell someone "Oh, don't worry
>> about MD5 IN THAT APPLICATION", and you happen to be right, then they
>> might take that as reason to use MD5 in applications where it is a
>> concern. MD5 comes with some significant security risks, no matter
>> how theoretical you think it is (just because you don't personally
>> have code that breaks it doesn't mean that no one does) and I think
>> that it's essentially irresponsible to be promoting its use over SHA1.
>>
>> John
>>
>>>
>>> Please feel free to comment.
>>> Regards,
>>>
>>> Oscar Batyrbaev
>>> CTO B3 Security Corporation
>>> Tel. (408) 615-7433
>>> Fax: (603) 649-6498
>>> email: batyr@ix.netcom.com
>>> email 2: oscar@b3security.com
>>> 1200 Ranchero Way, Suite 18, San Jose, CA, 95117
>>>
>>> B3 Security Corporation Confidential
>>>
>>>> -----Original Message-----
>>>> From: Craig Minton [mailto:CraigSecurity@blazemail.com]
>>>> Sent: Tuesday, November 05, 2002 1:01 PM
>>>> To: secprog@securityfocus.com
>>>> Subject: SHA-1 vs. triple-DES for password encryption?
>>>>
>>>>
>>>> We are considering changing our password storage from a home-grown
>>>> algorithm to a standard. We are mainframe based and only have
>>>> triple-DES and SHA-1 algorithms available. However, we many
>>>> questions
>>>> about the best way to proceed. We are leaning towards using SHA-1
>>>> for
>>>> a few of reasons. The password being "encrypted" using SHA-1 never
>>>> need be retrieved, just verified. Indeed, the password should not
>>>> be
>>>> retrievable. By not using triple-DES there is no need to secure a
>>>> key
>>>> used to encrypt them. Also, with triple-DES, if someone was to
>>>> obtain
>>>> the key, by whatever means, retrieving all of the passwords would be
>>>> trivial. The downside to SHA-1 is that we would have to increase
>>>> our
>>>> storage requirements for the encrypted portion from 8 bytes to 20
>>>> bytes.
>>>>
>>>> Is there anything inherently wrong with using SHA-1 to hash
>>>> passwords
>>>> for verification?
>>>>
>>>> Is there a benefit to using triple-DES instead?
>>>>
>>>> Is SHA-1 any more suseptible to attack, brute-force or cr
>>>> ypto-analytic, than triple-DES? My 2nd edition copy of Applied
>>>> Cryptography states that there is no known crypto-analytic attack
>>>> known
>>>> for SHA-1, but that book is now several years old.
>>>>
>>>> It was suggested to use SHA-1 and then remove all of the bytes from
>>>> the
>>>> hash except for 8 bytes (truncated from the beginning, end ,or
>>>> somewhere in between) and store this, thus not increasing storage
>>>> requirements. Would this compromise the algorithm? How much would
>>>> it
>>>> increase the chance that two passwords then had the same truncated
>>>> hash?
>>>>
>>>> I look forward to any insights you can provide and will be glad to
>>>> answer additional questions where possible.
>>>>
>>>> Craig
>>>>
>>>> _____________________________________________________________
>>>> Fight the power! BlazeMail.com
>>>>
>>>> _____________________________________________________________
>>>> Select your own custom email address for FREE! Get
>>>> you@yourchoice.com
>>>> w/No Ads, 6MB, POP & more!
>>>> http://www.everyone.net/selectmail?campaign=tag
>



Relevant Pages

  • RE: SHA-1 vs. triple-DES for password encryption?
    ... Same did not happen against the full MD5 yet and who knows when/if it will. ... Cryptographers call an attack something that ... > than you would of SHA1 to get the difficulty up to the same level. ... > cryptographers who are under the impression that Dobbertin has ...
    (SecProg)
  • [REVS] Multiple Collisions attack on MD5 and other Hashing Algorithms
    ... The following security advisory is sent to the securiteam mailing list, and can be found at the SecuriTeam web site: http://www.securiteam.com ... This collision attack might someday introduce a weakness in MD5 ... The presented attack can find many real collisions which are ...
    (Securiteam)
  • Re: MD5CRK is now LIVE
    ... >> We agree that a collision does not help against a password system. ... >> In the case of a contract, the attack won't work on a document ... note that unless MD5CRK is setup right from the start ... Anyone relying on the difficulty to find MD5 collision ...
    (sci.crypt)
  • Re: SHA-1 vs. triple-DES for password encryption?
    ... > birthday attack succeeds with probability 0.5 or 50%. ... > full MD5. ... > theoretical cryptographers call an "attack" create FUD on this issue. ... Note that you are correct in saying that SHA1 is of the same family as ...
    (SecProg)
  • Re: Lost password + MD5 ?
    ... >> hash M, and being able to produce a different plaintext B that has the ... which MD5 attack are you referring to? ...
    (comp.lang.php)