Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

I've been reading about the LANMAN (LM) hash and I'm curious about a particular part of the algorithm.

The LM hash is computed as follows:

  1. The user’s ASCII password is converted to uppercase.
  2. This password is null-padded to 14 bytes.
  3. The 14-byte password is split into two 7-byte halves.
  4. These values are used to create two DES keys, one from each 7-byte half.
  5. Each of the two keys is used to DES-encrypt the constant ASCII string “KGS!@#$%”, resulting in two 8-byte ciphertext values.
  6. These two ciphertext values are concatenated to form a 16-byte value, which is the LM hash.

There are a lot of security weaknesses outlined in the linked Wikipedia article and talked about elsewhere, but I'm particularly interested in steps 3 through 6. I'm curious about what led to this design. Is there any real security advantage to splitting a password, encrypting the two halves separately, then combining the two halves to form one hash again? Or is this just an example of "security through obscurity"?

share|improve this question

3 Answers 3

up vote 24 down vote accepted

Splitting the password into hashes is not an advantage. It was done for obscure reasons that are no longer relevant today.

The reason that the LanMan hash works this way is because the LanMan hash is built upon DES. DES accepts a 56-bit key. Therefore, it is natural to treat a chunk of 7 bytes as forming a DES key. There's no good way to use DES to hash more than 7 bytes at a time, and we need some way to build a hash for longer passwords out of DES, so the designers of the LanMan hash decided to split the password into two halves.

Today, we'd never build a password hash this way. We'd just use Bcrypt, Scrypt, PBKDF2, or some equivalent -- or we'd build something similar based upon existing primitives, like SHA256. But at the time, Bcrypt, Scrypt, SHA256, etc., didn't exist, opening up the opportunity for the LanMan designers to make this kind of devastating error.

By modern standards, the LanMan hash is a crummy design. There are many many attacks on it. It's very weak. Nobody should use the LanMan hash today if they can possibly avoid it. (As others have pointed out, its security is crummy even by the standards of the time. A fair point.)

share|improve this answer
8  
Good answer! But re: "modern standards" ... by what standards would the LanMan hash not be a crummy design? When was it developed, in the '80's? Even Unix crypt(3) from Unix version 7 in 1979 had a salt and 25 iterations. minnie.tuhs.org/cgi-bin/utree.pl?file=V7/usr/src/libc/gen/… Nor did it reduce entropy by converting to upper case. It also seems better to just truncate the password than to independently hash the second half which may be very short and crackable and give valuable hints as to what the first half is. –  nealmcb Apr 6 '11 at 3:17
3  
I would argue that it was crummy even at the time. Take 3DES for example, which manages to safely shoehorn a 168-bit key into DES by re-encoding with successive keys. If LanMan had used the second key-half to encode the result of the first round (not outputting the intermediate result), it wouldn't have been nearly as disastrous as what they have now. –  tylerl Jan 9 '13 at 16:55
    
Note that by "SHA256 or some equivalent", today we would never take a single pass of any hashing algorithm. Instead, we would use BCrypt, SCrypt, or PBKDF2 (quite possibly PBKDF2-HMAC-SHA-256) with a random salt and a sufficiently high work factor or iteration count. –  Anti-weakpasswords Apr 2 at 6:16
    
Thanks, @Anti-weakpasswords! Good point. I've revised my answer accordingly. I appreciate the feedback. –  D.W. Apr 2 at 7:07
    
@D.W. No problem; that's what I do, and thank you for revising your answer! I can even give another level: "or build something similar based on existing primitives" ALSO boils down to "See the Password Hashing Competition" :). Have an upvote! –  Anti-weakpasswords Apr 3 at 5:53

Splitting the password is a weakness, not an advantage. It allows breaking each password half independently. Beginning with ASCII characters (codes from 32 to 126, inclusive), then removing the lowercase letters, you end up with 127-32-26 = 69 possible characters in the password alphabet. This leads to 697 possible halves, which is somewhat below 243. In other words, this is highly tractable through brute force. You do not even need a dictionary.

This is not security through obscurity. This is insecurity through incompetence.

Edit: "highly tractable with brute force" also opens the road for various optimizations. Note that LanMan is not salted, thus precomputed tables can be efficient (you pay the cost of table building once, then you attack several half-passwords -- it is actually worth it even for a single password, since one password is two half-passwords). In 2003, Philippe Oechslin published an improved time-memory trade-off (it is the article in which he coined the term "rainbow table") and computed tables for cracking LanMan passwords. He restricted himself to alphanumeric passwords (letters and digits, but no special signs), thus a space of 237. The cumulative size of the tables would then be 1.4 GB, with cracking efficiency of 99.9%, and attack time under one minute.

With a 243 space, i.e. 64 times larger, table size and attack time both rise by a factor 16 (that's 642/3), so we are talking about 23 GB or so (that's not much for today's disks) and a 15-minute attack. Actually, the attack would be faster than that, because the bottleneck is lookups on the hard-disk, and the smart attacker will use a SSD which can do lookups 50 times faster than a mechanical hard-disk (a 32 GB SSD costs less than 70$...). The table-building effort (a one-time expenditure) could take a few weeks on a single PC, or a few days on any decent cloud, so it is rather cheap.

Apparently, such tables already exist...

share|improve this answer
1  
I do wonder about the history also. IIRC the original Unix crypt did 8 characters because they used something related to DES directly without a key derivation function. Probably similar with LANMAN, despite updates in theory and practice before they designed it. –  nealmcb Apr 4 '11 at 19:39
5  
I'd like to add an early 2014 update: A) that 23GB lookup table fits in RAM on even modern desktop computers, and B) now a single PC with 8 AMD R290X GPUs at stock clock can do an exhaustive brute force/Markov search/build a lookup table of the entire 2^43 LM keyspace in only 13.65 minutes with oclHashcat. Math: 2^43 possible passwords/10.74 billion tries/second = 819 seconds. 819/60=13.65 minutes. –  Anti-weakpasswords Apr 2 at 6:23

Just because something is more complex does not necesarily make it more secure. I ran a password cracker on my windows box and it appeared to break the passwords up into 8 character strings, and it broke each string independantly of the other string, making the process go extremely quickly.

So from a practical standpoint splitting a password is not beneficial, and @Thomas already covered why it is not beneficial mathmatically.

share|improve this answer
    
Windows Vista and newer don't do this. –  user29387 Aug 10 '13 at 21:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.