Re: Digital Unix 4 protected password database.

[nate () root org (Nate Lawson)]

Keith Piepho said:
> > At 05:47 PM 3/10/99 +0000, Alec wrote:
> > Paul Leyland told me, many years ago, that one or more of the
> > "Enhanced Security" crypt-replacements are actually less secure
> > than traditional crypt() in many respects.
> >
> > Consider the:
> >
> > crypt first 8 chars
> > crypt remaining 8 chars
> > join the two ciphertexts
> >
> > ...mechanism; assuming people choose passwords which are (a) plain
> > dictionary words and (b) only slightly longer than 8 characters, then:
>
> Focusing on the case in which the password is a dictionary word obscures
> the real problem:  to compensate for the insecurity of an 8 character
> password, DEC has replaced it with what appears to be a 16 character
> password scheme, but is in reality just 2 8 character passwords, doubling
> instead of squaring the size of the keyspace that must be searched.  (and
> much less than doubling, in the case of the all-too-frequent short second
> keys which will occur.)

It doesn't even double the amount of space required if there isn't a
separate salt.  In this case, just perform a trial encryption of the value
and do two compares, one against the first hash value and one against the
second.  Of course, the dictionary wouldn't include just actual words, but
also all suffixes >8 characters.  Several optimizations come to mind:

1.  As Alec said, test the common suffixes in the second hash value first
and then use that to decrease the search space of the prefix.

2.  Parallelize the attack by running prefixes on one machine (or group)
and suffixes on another.  The independent nature of prefix and suffix mean
the concatentation of the two can never be stronger than a single 8
character password.

> The alternate scheme you mention (in the part I cut) of encrypting the
> first 8 characters and the last 8 seems to me to result in a 16 char
> keyspace.  Clever.

Unfortunately, it doesn't perform strong mixing and thus does not produce
a result as strong as its 16 character length implies.  For the degenerate
case of a 16 character password, both halves are completely independent
just as in the original scheme.  Also, a search can be mounted by just
truncating all dictionary words to 8 characters, doing a trial encryption
and comparing the first half.  If there is a match, shift the word by the
requisite amount and encrypt the suffix with the second salt.

  So, with dictionary words "wheatsheaf", "wheatshed", and "wheatshards":

  1.  Encrypt the prefix "wheatshe" and compare to the first 8 chars
  2.  If there is no match, throw out all the above words
  3.  If there is, do a trial encryption with "eatsheaf", "heatshed", and
      "atshards" using the second salt.  Compare against the suffix.

As you can see, the only proper way of increasing the effective length of
a password is to use a cryptographic hash algorithm or implement a scheme
of thorough plaintext mixing.  Look into the efforts of expanding DES for
good examples of how to mix plaintext properly.

-Nate