Re: Messenger/Hotmail passwords at risk

[Ishikawa <ishikawa () yk rim or jp>]

(I sm re-sending this afer minor editing
since I am not sure if this went out
or has been accepted/rejected after I switched my
subscription e-mail address.)

> 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.
(Provided that the given-long-string and short-password-candiate is
not so long after all.)

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)

I take that the original poster's brute force program
saves the intermediate state of md5 calculation
up to the last 16 words block where the block in which
the short-password is embedded. (The password
may span across block boundary, but the gist of
argument should hold.)

By using such saved state, the brute force calculation of
MD5 (given-long-string || short-passwd-candidate ) for each
short-passwd-candiate can be done
rather fast since,  by using the saved state,
only the update of the result array using the
last round of the calculation step (based on the block
in which the password candidate is placed) is now necessary.
We can re-calculate for each candidate short password string
repeatedly in this manner.
(This must be the gist of the original poster's
brute force program.)

However, using `short-passwd || given-long-string'
makes such brute-forcing rather difficult (comparatively speaking).
This is because now md5 calculation of
the full steps over all the blocks spanning the total string
must now be performed for each password candidate.
(We can't save the intermediate state as before to
speed up brute force attempts.)

Is this analysis correct?
If so, we should switch to the
  hash ( possibly-short-user-response || long-seed-string )
scheme where
  hash (long-seed-string || possibly-short-user-response)
is currently used (hash is md5 for example).
Many challenge/response seems to use the
former string.

However,  we should use rather long string and long password as well.