From: daw@beijing.CS.Berkeley.EDU (David A Wagner)
Date: Mon, 22 Jan 96 15:08:34 PST
To: cypherpunks@toad.com
Subject: Re: Lan Manager security
Message-ID: <199601222305.SAA11398@bb.hks.net>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

In article <9601221620.AA11356@capybara.transarc.com>,
 <lws@transarc.com> wrote:
     [ ... the LanMan / Samba(?) password authentication protocol ... ]
> The password is uppercased and truncated to 14 bytes (or padded to 14 
> bytes with nulls).  This is split (0..6,7..13) into two DES keys 
> which are each used to encrypt a static 8-byte value. The resulting 
> 16 byte key is stored at the server. 
     [...]
> To authenticate a connection, the server issues an 8 byte random challenge.
     [...]
> The client then pads the 16-byte key to 21 bytes (with zeros, natch), 
> splits it in thirds, {0..6}, {7..13}, {14,15,NUL,NUL,NUL,NUL,NUL}, 
> uses each third to DES-encrypt the challenge, concatenates the 
> ciphertexts, and returns the response to the server.

Oh yeah, this protocol again.  I remember looking at it a while ago; many
thanks to Andy Brown <a.brown@nexor.co.uk>, who showed it to me and kindly
gave me lots of information.

It's pretty crappy, IMHO.  It's very weak against dictionary attacks
(assuming I have a sniffer).

For instance, if you use a password which is less than 12-14 characters
long, it will be very easy to recover bytes 7..13 of your password.
After that, it will often be simple enough to extend the password backwards
if it is based on a dictionary word; even if the password is purely random,
this reduces the strength of the password to an effective length of 7 bytes.

Also, there is no salt used in the password hashing function, so precomputed
dictionary attacks are easy (e.g. the "Exabyte attack", where you precompute
the hash of each likely password and store each result on a huge tape.)

Unfortunately, I don't have time right now to follow up with a sample
exploit program or anything.  Sorry 'bout that.

Microsoft should have used a real crypto-quality hash function (e.g. MD5),
instead of trying to synthesize one from multiple concatenations of DES.

The technical details on the attacks follow.




Call the bytes of the password P_0 .. P_13, the 16-byte key K_0 .. K_15,
and the response R_0 .. R_23; and call the challenge C and the static 8-byte
server key S; K is generated by DES encrypting S with P, and R by DES
encrypting C with K.

I know C,R and want to find P_7 .. P_13.  First, try all possible values of
K_14, K_15; the right value can be recognized when C_16 .. C_23 encrypts to
R_16 .. R_23 under K_14, K_15, 0, 0, 0, ..  Now that we know K_14, K_15,
I can try the likely values of P_7 .. P_13; wrong values can be quickly
discarded by trial encrypting S under P_7 .. P_13 and noting whether the
last two bytes of the ciphertext equal K_14, K_15.  Each remaining guess
for P_7 .. P_13 gives me a candidate for K_8 .. K_13; I can check all K_7
possibilities to see if there's any for which C_8 .. C_15 encrypts to
R_8 .. R_15 under the K_7 .. K_13 candidate.  If there is such a K_7, the
guess for P_7 .. P_13 is almost certainly correct; if not, try another
candidate for P_7 .. P_13.  If there are N likely values of P_7 .. P_13,
this recovers the true value of P_7 .. P_13 with about N trial encryptions.

Note that there is no salt used; in fact, if I'm willing to do N precomputed
trial encryptions, recovering the true value of P_7 .. P_13 takes N / 2^16
work.

Once I've found P_7 .. P_13, if I'm willing to do M precomputations [where
M is the number of likely values of P_0 .. P_6], then recovering the true
value of P_0 .. P_6 can be done with about M / 2^8 trial encryptions.
(If I'm not willing to do precomputations, it'll take M trials.)

Did that make any sense?
- ---
[This message has been signed by an auto-signing service.  A valid signature
means only that it has been received at the address corresponding to the
signature and forwarded.]

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
Comment: Gratis auto-signing service

iQBFAwUBMQQYSioZzwIn1bdtAQFKkAGAqcC2ZoZsSHEUiqU8envvqHLI9vfi4xnf
aexUGBX10peIeh3TSzq9RcMU2c8FxT45
=xQGr
-----END PGP SIGNATURE-----