Talk:LM hash

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer Security / Computing   
WikiProject icon This article is within the scope of WikiProject Computer Security, a collaborative effort to improve the coverage of computer security on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
 ???  This article has not yet received a rating on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
Taskforce icon
This article is supported by WikiProject Computing.
 

Relevant historical question[edit]

Does anyone know where the KGS in "KGS!@#$%" comes from? For some reason I'm thinking it's related to the designers initials or something, but I can't really remember. This could be a point of interest for the main page if we can find the answer.

--Tom

Disabling LM hashes[edit]

Shouldn't this page have a note saying how to disable the use of LM hashes? --Wayne

(At least) an external link would be worthwhile; does Microsoft describe how to do this in any of their support pages? — Matt 18:49, 2 Nov 2004 (UTC)
Added. --Hawke666 22:45, 2 Nov 2004 (UTC)

fact check request (moved from main article)[edit]

The number of combinations seems incorrect. Usually the formula is (number of valid characters)^(length of password), or for a 7-character password using upper-case letter and numbers only, 36^7. 2^36 is far too small, unless there's a bug in LM Hash that I don't understand.

24.81.71.14
I get log2(367) = 36.189475... (so 236 is about right.) I'm not sure about 284 for mixed case and numbers, though. I get (26 + 26 + 10)7 = 241.68. — Matt 19:21, 2 Nov 2004 (UTC)
For the record, 84 \approx \log_2\left(\left(26+26+10\right)^{14}\right). That’s not quite exact, but close enough. —xyzzyn 14:40, 14 June 2006 (UTC)

Weird notes[edit]

I’ve moved the following from the article:

The effects of splitting the password into two and having two independent (note the emphasis) hashes on each half is that it enables a cryptanalyst to consider only one half at a time. In the context of a typical brute-force approach, this means the effective halving of the search schemata, which will yield a reduction in the search space by a factor of 2^18. This is because together, the two halves correspond to 2^36 discrete password combinations.
Given the ability to consider one half at the time amounts to 2 * 2^18 = 2^19 effort, as opposed to a full 2^36 effort, had the halves been made dependent. The effect is not different to a mergesort, which recursively splits the search space into halves which are each significantly simplier, and merges these together in a O(NlogN) effort.

I don’t think it’s correct; 2^{36} is already the size of the search space for one seven-character hash, which yields a size of 2^{35} per hash when looking for two hashes. Anyway, 2^{36} is the relevant number. —xyzzyn 14:40, 14 June 2006 (UTC)

Explanation: When we have a concatenation 2, 7-bit fields, such that the 2 fiels are related and, thus, inseparable, we have an equivalent of a 14-bit field. When you halve the number of combinations, yes, you subtract one from the index (power). But in this case are taking the square root of the entire search space, because we've managed to split the field in half.

Regarding 2^36. I made a mistake thinking that 2^36 is the entire search space. Actually, since we assume that a 7 bit field can take only 36 values (lower case plus digits), a 7 character password is 36^7. This is approximately 2^36.2 (found logarithmically). So for 2 halves, it is 2^37.2 ~ 2^37. I'm not sure where you got 2^35 from :) [Emil Koutanov]

When using brute force, it’s only necessary to do the search space once (in the worst case). This means checking 2^{36} combinations (the exact number doesn’t really matter there—it’s an estimate anyway). Since this gives solutions for both hashes (because the hash function is the same in both cases and checking for two matches instead of just one match for each combination is negligible for the time complexity), the number of combinations per one hash is the total number of combinations divided by the number of solutions we got, i. e. 2^{35}. The total number of combinations checked remains 2^{36}, of course. 2^{37} should not happen unless you actually run the entire brute force algorithm separately for each hash, which is an unnecessary (and costly) complication. Anyway, I think the article already covers the arithmetical aspect adequately.
By the way, please sign your posts using the Wikipedia method, by appending ~~~~ to your posts on talk pages (but never to your contributions in articles; those are automatically attributed in the article history). This automatically inserts an identifier and a timestamp. If you want to have a custom signature, why not create an account? —xyzzyn 22:17, 22 June 2006 (UTC)

In many of the discussions above, you guys assume that only alphanumeric characters are used. Actually, passwords hashed using LM hashes do use symbols and space in addition to letters and numbers. Assuming that only the 95 printable ASCII characters are used, minus the 26 lowercase letters, that would make 69 charaters in the character set to consider. --Spoon! 10:47, 31 August 2006 (UTC)

Most people don't use special characters, but a fully random LM password selected from a 69 character alphabet would require searching a space of 2^43 possibilities. Because salt is not used, time-memory tradeoffs can be used to make searches very fast.--agr 21:39, 31 August 2006 (UTC)

Contradiction in the article?[edit]

This password is either null-padded or truncated to 14 bytes.

Users can also prevent a LM hash from being generated for their password by using a password at least 15 characters in length.

Isn't that a contradiction? How could the hash generating function ever be reached with a >= 15 character password if the second quote is true? -- Aeluwas (talk) 19:34, 20 June 2009 (UTC)

Wrong understanding of DES encryption[edit]

"These values are used to create two DES keys, one from each 7-byte half, by converting the seven bytes into a bit stream, and inserting a zero bit after every seven bits. This generates the 64 bits needed for the DES key."

DES encryption standard using de facto 56-bit key, rest 8 bits are a parity-bits, so it's wrong to say what I highlighted above.

DES key:
???????P ???????P ???????P ???????P ???????P ???????P ???????P ???????P
Legend:
? - some bit
P - parity bit from last 7 bits

Parity-bits must be evaluated! Can't be just set to zero. —Preceding unsigned comment added by 83.18.27.218 (talk) 07:30, 8 August 2009 (UTC)

There must be a null bit added not a parity bit- I implemented the algorithm with a parity bit and it was giving wrong results, but it WORKS fine with a null bit. Anoymous, 13:25, 6 June 2010 UTC —Preceding unsigned comment added by 83.9.40.16 (talk)

It's even weaker than that![edit]

I'm surprised to see no mention of how much it facilitates dictionary attacks! While all the existing remarks about attacks are correct, they omit the most devastating attack against a very common case. The attacks described in the article totally kill LM Hash with modern computing resources, but the attack I am about to discuss usually killed it with the sort of desktop computing resources that were available even in the late 1980s, when rainbow tables were a pipe dream.

Consider passwords that are dictionary words, weakly perturbed dictionary words, or have some other similar sort of structure; and that are slightly longer than 7 characters. (Such passwords are very common in practice, in fact probably the most common type of password that is not totally trivial to crack.) The attacker can brute force the second half of the password in N^{L - 7} trials where N is the size of the symbol set and L is the full length of the password. For example, if a password is assumed to be composed of a random collection of printable characters then N = 96, and for L = 10 this yields 96^{10 - 7} = 884,736 trials, which even in the late 1980s was trivial to crack on a home PC -- say about 2 hours on a 4 MHz machine. If we assume the tail of the password is likely restricted to either single case alphabetic (one or the other case) or numerics, then with about the same effort we can hit L = 11 ( 26^{11 - 7} + 26^{11 - 7} + 10^{11 - 7} = 923,952.)

Here's the kicker: most passwords (except truly random ones) have some sort of structure which means that those last L - 7 characters will leak information about the first 7 once they are revealed (and of course it immediately reveals the length.) For example, "970" looks like it would fit very nicely with MM/DD/1970 or MM-DD-1970 (or DD/MM/1970 or DD-MM-1970) and you can confirm or disprove that hypothesis in just 1,172 trials taking just a few seconds even way back then. Thus under LM Hash, passwords with slightly more than 7 characters are actually weaker than ones with exactly 7!! As the password gets longer, cracking the tail gets harder but the attacker gets more information to help attack the head. Depending on the power of the attacker's computing resources the "sweet spot" probably falls somewhere between L = 10 and L = 12, where password strength is minimised. That happens also to be about the maximum length that people used to use for critical admin passwords, thinking such a length would be highly secure ... Needless to say, this is a highly undesirable property!

Now, all of the foregoing can't be published, due to the original research rule. However, I didn't invent it; I'm sure if we look hard enough, we'll find an old description of this technique. -- 202.63.39.58 (talk) 12:30, 18 August 2009 (UTC)

Is L0phtCrack open source or reviewed somewhere perhaps? Socrates2008 (Talk) 12:51, 18 August 2009 (UTC)

Timeline?[edit]

It would help a lot to add a timeline to the article. When was this scheme cooked up (vs the use in Unix of salts and iteration counts in 1974, as I recall), and when was it first deployed? When was it in peak usage? When did it start being exploited frequently? ★NealMcB★ (talk) 15:52, 18 February 2011 (UTC)