RE: Messenger/Hotmail passwords at risk

[Michael Wojcik <Michael.Wojcik () merant com>]

> -----Original Message-----
> From: Ishikawa [mailto:ishikawa () yk rim or jp]
> Sent: Thursday, July 12, 2001 11:50 AM

> From the discussion, I think some readers missed
> the point of the original poster.
> Using "||" as string concatination operator, it seems that
>
>     MD5 (given-long-string || short-password-candidate )
>
> can now be brute forced to produce a given/observed hash value
> returned in challenge/response using fast and inexpensive CPU
> in a reasonable time.

[because the attack precomputes the hash of given-long-string]

> Now, however, why don't we use the reversed order for
> the two strings concatenated in the md5 calculation?
>
>    MD5 ( short-passwd || given-long-string)

See Bruce Schneier, _Applied Cryptography_, 2nd ed., 18.14 (Message
Authentication Codes), section "One-Way Hash Function MAC".  In essence,
using the hash of a known string combined in some fashion with a secret as a
password hash is equivalent to making the password the secret for a MAC of
the known string.

Schneier cites a private communication with Bart Preneel (author of
RIPE-MAC) on possible weaknesses of the obvious constructions

        H(known-string || password)
        H(password || known-string)
        H(password || known-string || password)
        H(password-1 || known-string || password-2)

and suggests one of the following instead (rewritten as password hashes):

        H(password-1 || H(password-2 || known-string))
        H(password || H(password || known-string))     [ie. pw-1 == pw-2]
        H(password || pad || known-string || password) [pad pw to full
block]

The simplest of these, in terms of retrofitting existing systems that use
one of the constructions Ishikawa mentions, is

        H(password || H(password || known-string))

Michael Wojcik             michael.wojcik () merant com
MERANT
Department of English, Miami University