networksolutions CRYPT-PW salt (was: Re: Insecure handling of NetSol maintainer passwords)

[jogata () NODC NOAA GOV (Jefferson Ogata)]

Trevor Schroeder wrote:
> On Tue, 9 Nov 1999, Jefferson Ogata wrote:
>
> > generate with their New Contact Form web system runs the password you
> > enter through crypt(), but the first two characters of the encrypted
> > value (the salt) are the same as the first two characters of the
> > password, indicating they use the password as its own salt. This
> > dramatically limits the usefulness of encrypting the password in the
> > first place, since you've already given away the first two characters,
> > and probably hamstrung the whole algorithm at the same time. (More
> > advanced crypto people than I can comment on this.) In any case,
>
> Your damn tooty this isn't the way to do this!!  If anyone gets ahold of
> your crypted password, they've got the first two chars of the password
> making the guess significantly easier.
>
> crypt() basically DES encrypts 0 with your password as the key.  That's why
> it's 8 chars.  8 ASCII chars = 7 bits/char * 8 char = 56 bits.
>
> 2^56 = 72057594037927936 possible keys.
>
> Of course, 7 bits => 128 chars, but we must subtract the 32 control chars
> which leaves us with 96 textual characters (including spaces).
>
> Now our keyspace is 96^8 = 7213895789838336, roughly 1/10th of the previous
> keyspace, but not unreasonable for non-critical applications.  (ie, nothing
> to trust your credit card to, but a non-trivial key nonetheless).
>
> However, if we can get the first two characters of your password, assuming
> that the rest is randomly distributed (ie, no dictionary based passwords),
> that leaves us with 6 unknown chars.
>
> Our unknown keyspace is now 96^6 = 782757789696, just over 1/10000th the
> previous and 1/100000th the space of a full 56 bit key.  This leaves us
> with roughly 40 bits (log2(782757789696) = 39.5) of entropy--again,
> assuming random characters.
>
> 40 bits keys can be broken pretty quickly.

A couple points of followup on this issue:

First of all, this was somebody else's thread and I shanghaied it. What
were we supposed to be talking about? Sorry about that.

Second, I found an earlier posting to bugtraq in the archives from
Oct 11, 1996, describing the same thing:

    
http://www.securityfocus.com/templates/archive.pike?list=1&date=1996-10-8&msg=Pine.LNX.3.95.961011120728.3070A-100000 
() socks litter717 net

The lone respondent:

    http://www.securityfocus.com/templates/archive.pike?list=1&date=1996-10-08&msg=199610120045.DAA08102 () noc ntua gr

saying:
> I believe the internic guys will change this to a random salt...

Ah, such innocence. I'm guessing the InterNIC wasn't paying close attention
to bugtraq at the time.

Third, the sort of primitive-crypto thought I had was that this makes
networksolutions' crypted passwords far more vulnerable to attack using a
pre-generated dictionary. Since every plaintext password has a unique salt,
one can pre-generate a very large dictionary: effectively there is no salt
at all. I wouldn't be at all surprised if such a dictionary already exists.

Finally, the sort of pseudo pop-crypto thought I had was that careful
analysis could conceivably reveal that passwords crypted using a substring
of themselves as salt might be more vulnerable inherently due to
mathematical cancellation between the salt and the plaintext during the
encryption. [The real crypto guys are laughing politely behind their hands
at this point. Hmm, some of them aren't so polite after all. I hurry on.]
Perhaps knowledge not only of the first two characters of the password but
also of the fact that the salt is identical to a substring of the password
would enable an algorithm to narrow the keyspace even further.

Oh, well. Happy Veterans Day to all who honor it, and to all others, happy
day. May the sun shine on your head.

--
Jefferson Ogata <jogata () nodc noaa gov> National Oceanographic Data Center
You can't step into the same river twice. -- Herakleitos