How and why I cracked a password hash

This was originally 2 years ago with references to the product and vendor. Unfortunately I got threatening legal letters, and almost lost my job! I’ve now stripped out the vendors references and am putting it up simply because I think others will find my methodologies and write up interesting.

Some software I was working with stored its password using a custom written encoding method – and charge people for professional services who want to decode their passwords. Recently I wanted to migrate users from this system to an alternate one, so I had no choice but to reverse engineer the hash. I’m publishing this here to demonstrate why people shouldn’t invent their own hash without fully understanding the consequences, and as an interesting example of crypto work.

The first step was to locate where the software stores its passwords – which I found was within the windows registry. Within the registry each user has a value containing among other things, the password.

This means that it is possible to change a users password, and observe the output hash – allowing us to build a dictionary for plain text to cipher text mappings. Having tried various entries, I came up with hashes like these below:

Plain	Cipher
a	%DgFf&kJo
b	%D4Ff&kJo
c	%DNFf&kJo
bbbbbb	%DZ()noaw
bbbbbbbbb	%DZ()noawDZ()
bbbbbbbbbbbb	%DZ()noawDZ()noaw

My list of plain to cipher mappings was longer than this, but I noticed a number of things as this stage:

• cipher text always begins with a %, and can therefore be ignored.
• cipher text is at least 8 chars long, and increases by 4 cipher chars for each 3 chars of plain text after that
• the result of encoding the same letter 12 times shows a pattern that repeats for every 8 cipher letters.

The 2nd point in the above was key for solving the problem, as it pointed me towards base64 encoding. The 2nd point I took away from the above was that it was not worth looking at plain text inputs longer than 6 chars.

My next step was to start inputting 6 character passwords, deciding I would focus mainly on repeating characters in my input text, such as ‘aaaaaa’ and ‘bbbbbb’. I would then compare the base64 encoded input, vs the output, such as below.

Plain text	Base64 plain text	Cipher text
111111	MTExMTEx	Whbo7D)f
222222	MjIyMjIy	W5)n7lbg
333333	MzMzMzMz	WO7m79fh
444444	NDQ0NDQ0	Vxvl6Sja

From trying out more and more inputs such as the above, I noticed a couple more things, that can be observed in the snipped above.

• repeated chars in the base64 of input text does not result in repeated chars in the cipher output (see 333333 above
• an ‘M’ in column 1 of the input base64’ed resulted in a ‘W’ in the output
• an ‘M’ in column 5 of the input base64’ed resulted in a ‘7’ in the output
• The cipher text has 64 unique symbols in its output , therefore further supporting the base64 theory.

The observations above lead me to suspect this encoding system simply used 8 ‘translation maps’, and working these out would be as simple as inputting enough samples to build a full table of results. This means that with an input of ‘abcdefghi’, ‘a’ would be translated using TM1 (translation map 1), ‘b’ would use TM2, ‘c’ would use TM3, and so on, up until the 9th char of ‘i’ which would use TM1

I quickly wrote a script to build up these translation maps for me, and this is the result:

== TM 1
cipher | $%&()*123456789ABCDEFGHIJLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwx
plain  | RQ             baZYfedcTSXWVULKJIPONM      w
25 translations found
== TM 2
cipher | $%&()*123456789ABCDEFGHIJLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwx
plain  | 23    n  ij             1  yz      q klmUVWX  ST        EFGH  CD
24 translations found
== TM 3
cipher | $%&()*123456789ABCDEFGHIJLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwx
plain  |    JI  xw  NMP ts  po  lkhg  98  54  1  FE  BA  dc  ZY  VU  RQ
32 translations found
== TM 4
cipher | $%&()*123456789ABCDEFGHIJLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwx
plain  | NMgjihcbaZYnmlkHGFEDCBAPOLKJIXWVUTSRQfedvutsrqpo321 zyxw/+987654
63 translations found
== TM 5
cipher | $%&()*123456789ABCDEFGHIJLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwx
plain  |   KJIL     NMPO     o                           dcfeZYbaVUXWRQTS
25 translations found
== TM 6
cipher | $%&()*123456789ABCDEFGHIJLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwx
plain  |   3 12       yz  STUVWX        CDEFGH       8     ijklmn
24 translations found
== TM 7
cipher | $%&()*123456789ABCDEFGHIJLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwx
plain  |    FE  98  BA  hg  lk  pots  xw  1   54 JI KNM  RQ  VU  ZY  dc
32 translations found
== TM 8
cipher | $%&()*123456789ABCDEFGHIJLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwx
plain  | WX7456HABCD89+/cdefYZabUVQRSTMNOPIJKLEFG 123wxyzstuvopqrklmnghij
63 translations found

288 / 384 translations found!

With these translation maps, I was able to build a decode method, which in turn revealed that passwords are padded with ‘+’ signs up to 6 letters, or multiples of 3 there after. Whilst my translation maps are not complete, they are sufficiently complete to decode the 500+ passwords I have tried so far. I imagine the reason that the tables are incomplete is because I’m using 7 bit chars for my input, and not even using all of those, for example you can’t have a newline, or delete char in your password.