July 08, 2007

Challenge Solution: Cracking the Password

The password challenge has come to an end, and we have a winner :) The main goal of the challenge was not to show up your brute force capabilities, but to show up your analysis skills and real-world use of common cracking tools.

First of all, thanks everybody that took the time to participate. We have received multiple submissions and enjoyed reviewing all them while going through the reasoning and procedures you follow to guess/crack the password.

In order to obtain the cleartext password from the system/application after the compromise, and provide other details about this hash, you first need to identify what type it is. You can try to guess it based on its length (24 chars) and character set used (probably a daunting task), or you can try to use tools like John the Ripper (under Unix or Windows).

Please, find below the official RaDaJo answer.

Questions & Answers:

1. What is the system or application that use this kind of password string and for what purpose?

We have found ourselves confronted against this type of hashes in several occasions during our pen-test activities, and it is used by HP-UX in Trusted System mode. HP's proprietary Unix version has always used the /etc/password file to store the user credentials, and when other Unixes started to use /etc/shadow file to avoid local access to the hashes by non-privileged users, HP implemented the Trusted System mode, where the hashes are stored in a directory structure under /tcb/files/auth, only readable by root, using multi-DES hashes. These hashes use the bigcrypt() function (versus the standard Unix DES crypt() function).

Fortunately, nowadays HP-UX also supports the usage of the standard /etc/shadow mechanism and MD5 hashes.

2. What is the format and crypto algorithm(s) used on this password string?

This type of hash uses a format similar to the standard Unix DES hashes, but it extends the hash length. The standard Unix DES hashes are implemented on the crypt() function and generate an output of 13 characters. The first two characters are a random salt used to encrypt the user password. Specifically only 6 bits from these two character are used, for a total of 12 bits, or 4096 possible combinations (2^12). The next 11 characters represent a standard Unix hash generated using the DES algorithm (25 times), taking as input: the 12-bit salt, an all-zeros input block, and the user password truncated to 8 characters and taking only 7-bits per character – this conforms the 56-bit DES key. The output, salt plus final ciphertext, is encoded into a base 64 printable string.

Therefore, in the example, "VOhRrmhZvX7lEG9KvuF/6FVA", the first portion, "VOhRrmhZvX7lE", is a standard Unix hash that corresponds to the first 8 characters of the password, where "VO" is the salt and the rest, “hRrmhZvX7lE”, is the DES generated hash.

When the bigcrypt function is used, the first two bytes of the first hash ("hR" in this case) are used as the salt for the second part of the password, so these two characters plus the remaining 11 characters conform another standard Unix DES hash, "hR + G9KvuF/6FVA". This second portion corresponds to the last 8 characters (or less) of the password. The final hash is just the concatenation of the first hash portion plus the second portion. You can get all the details on the man page for bigcrypt().

This means we really have two shorter standard Unix DES hashes to break, instead of a longer one. Is this hash format somehow familiar to you? It starts with an "L" and ends with an "M". Yes!, the Microsoft Windows LM (LANMAN) hashes use a similar algorithm, splitting the original password in two 7 bytes portions and appending the output hashes. LM even converts the original password to uppercase, but that's another story...

It seems HP designed the algorithm this way in order to make it reversible. You can easily unconvert an HP-UX system from Trusted System mode to standard Unix mode. No action is required by the administrator on the users’ passwords after converting the system, because the operating system automatically leaves just the first portion of the hash as the user password (truncated to 8 characters) after the conversion, as in any standard Unix DES system.

Theoretically, it seems there are no limits on applying this algorithm, that is, on the number of hashes you can append, although the HP-UX password man page recommends a maximum of 40 character passwords. However, it works with passwords over that limit; we tested it with a 50 character password and it generated a valid seven parts hash.

3. What is the clear-text password of your critical system? Please, detail the process you followed and the tools you used to obtain the password.

What do you think it is much more complex to guess, one number between one and one million, or two numbers between one and one thousand? If you review the math, the right response is the first one, therefore, trying to crack this password hashing schema (two 8 character passwords) is much easier than expected, that is, cracking a 16 character password.

The 14 character password from where the "VOhRrmhZvX7lEG9KvuF/6FVA" hash was derived is "winniethepooh9".

By default, John the Ripper cannot crack the two part hash even if you have the complete password in your dictionary. The reason is that it tries to crack both parts individually, so it uses the same dictionary words (starting with the first character of each word) for both parts, independently.

In order to run John against this hash successfully, you simply need to create a new file, called "password" in the examples, containing a valid Unix username/password entry, such as:


If you run John with the default options, you immediately will get the following results:

$ john password
Loaded 2 password hashes with 2 different salts (Traditional DES [24/32 4K])
winnieth (root:1)

If you wait for the prompt to return back, depending on your CPU power, you can wait for hours till John finds the complete password using brute force techniques. The main hints to guess the hashing algorithm are the indications that John provides about the existence of multiple hash portions, with the "Loaded 2 password hashes with 2 different salts" message, and with the ":1" appended at the end of the username, indicating it found the first part of a hash.

With the knowledge of how the hashing algorithm works, you can create a new dictionary where you split the words that are bigger than 8 character on your dictionary, in multiple 8 character (or less) words, so that "winniethepooh" will become "winnieth" (first 8 characters) and "epooh"(remaining characters). The first word will be used and succeed breaking the first part of the hash, and the second word will be used to break the second part. Easy, isn't it? (elegance versus brute force)

This basic Perl script, "split_dict.pl", splits a dictionary file to be used against this type of hashes. It reads your dictionary file from the standard input and generates the new "splitted" dictionary on the standard output:

- On windows:

C:\>perl split_dict.pl <> password_splitted.lst

- On Unix:

$ cat password.lst | ./split_dict.pl > password_splitted.lst

Now, it is time to start auditing the strength of your HP-UX Trusted Systems passwords!

For the challenge example, John is able to provide the results immediately, without using any of its brute forcing capabilities, because "winniethepooh" is a word (apart from being a bear ;) ) included in the default John's dictionary file, called "password.lst" (nowadays, with 3107 word entries). We wanted you to solve the challenge without requiring a huge dictionary file, so we used the default one :) The single digit number at the end of the password is tried by one of the default John's rules.

Using John after processing and splitting the dictionary file, the results are:

$ john password
Loaded 2 password hashes with 2 different salts (Traditional DES [24/32 4K])
winnieth (root:1)
epooh9 (root:2)
guesses: 2 time: 0:00:00:00 100% (2) c/s: 119000 trying: tabatha9 - action9

Unfortunately, this type of hash is used in very critical environments world-wide, and breaking them is like breaking several individual traditional Unix hashes, no matter how long the password is.

Finally, John the Ripper by default cannot crack these hashes if they are bigger than 16 characters, or two-portion bigcrypt() hashes, but this doesn't mean you cannot modify John's source code to recursively apply the same algorithm on bigger hashes, using our "splitted "dictionary file.

The results:

The winner is Pieter Danhieux from Belgium. Congratulations Pieter! To win the challenge, all skills are useful, technical and social. Pieter could partially validate his technical submission by knowing some social details about our past/current professional life. I really enjoyed your submission ;) The autographed copy of Ed Skoudis' "Counter Hack" book is on your way!

An honorable mention goes to Rafael Serrada from Spain. Rafa, thanks for sending an image showing how Winnie (PEZ) finally surrendered and provided you the password :) (see below) Great job gathering most of the details!

I hope you all enjoyed this challenge and I encourage you to participate on new future RaDaJo challenges.