From daw@beijing.CS.Berkeley.EDU Tue Jan 23 19:42:03 PST 1996 Article: 28922 of hks.lists.cypherpunks Path: hks.net!daw From: daw@beijing.CS.Berkeley.EDU (David A Wagner) Newsgroups: hks.lists.cypherpunks Subject: Re: Lan Manager security Date: 22 Jan 1996 23:04:11 GMT Organization: University of California, Berkeley Lines: 70 Message-ID: <4e155b$fq8@old-bb.hks.net> References: <9601221620.AA11356@capybara.transarc.com> NNTP-Posting-Host: beijing.cs.berkeley.edu In article <9601221620.AA11356@capybara.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 , 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?