Brute Forcing Encryption

[Andrew Schreiber]

A couple weeks ago there was a competition by EngineYard in which they challenged people to try to get hash collisions given a list of 1000 words and 5 arbitrary letters. Today I was reading through a thread and saw someone mention cracking the AES encryption on the game manual. So I was curious how often someone mentioned doing that, turns out someone mentions it pretty much every year when the encrypted manuals are released.

Now, I realize that discussion of illegal activities are illegal on this board, but I would assume that a good honest intellectual challenge is always appreciated. Here is the deal, I am going to post a phrase in various hashes (SHA1, MD5, and DES to be specific) I will give you one week to use whatever means you have at your disposal to either tell me the phrase or tell me a phrase that has a collision with the phrase.

Now, again I must cover my butt here and restate that the point of this exercise is NOT to teach how to crack encryptions. It is to encourage exploration of various encryption methods and how secure they are as well as writing efficient programs. If you just want to break things don't join in, this is for fun and learning, nothing more. The only prize is bragging rights and knowledge. One last requirement, if you get it you HAVE to describe how you cracked it so that others can learn. No secrets here (except for the actual phrase for the week)

So, now that my butt is thoroughly covered and I won't get myself banned(I HOPE) The hashes for this week are:

SHA1 Hash
3f900041799def330a812042b8ef4a6044fc2df6

DES
CRV3UuQ8DLxjM

MD5
c698abe95296466e1f339df792055192

This week's phrase is 12 characters long (shorter than the passwords for FIRST manuals) You can use any length string you like but my suggestion would be to limit yourself to strings of length 12 using the letters A-Z (upper and lower case) and spaces.

[to mods]
If this is against the rules I apologize, I felt that it was merely an intellectual challenge from which we may all benefit, please delete and just let me know so I know the bounds of what I can and cannot say.
[/mods]

Aside specifically to Joe Johnson re http://www.chiefdelphi.com/forums/sh...ad.php?t=41202
I have a feeling that this contest should have the opposite effect, it should let your mother rest easy knowing just how hard it is crack encryption.

[Jared Russell]

What, no AES?

Number of possible phrases:

53^12 = 4.91258904 × 10^20 (12 characters, each one in the set {a-z,A-Z,' '}, 53 elements total)

Guess I'll start at the top.

AAAAAAAAAAAA? Nope
AAAAAAAAAAAB? Nope
AAAA...

This is gonna be a long night.

[Jimmy Cao]

To the best of my knowledge, hashes for 12 character long passwords *tend* to be in rainbow tables... If I had enough hard disk space to store some rainbow tables, I'd try it, but that would only work on passwords up to a certain length. I'm sure the 40ish character length of the FIRST passwords makes them cryptographically strong to rainbow tables, unless you have Terabytes upon terabytes of them...

[Andrew Schreiber]

http://en.wikipedia.org/wiki/Rainbow_table For any one curious about what a Rainbow Table is.

[jtdowney]

Originally Posted by Lostmage333

To the best of my knowledge, hashes for 12 character long passwords *tend* to be in rainbow tables... If I had enough hard disk space to store some rainbow tables, I'd try it, but that would only work on passwords up to a certain length. I'm sure the 40ish character length of the FIRST passwords makes them cryptographically strong to rainbow tables, unless you have Terabytes upon terabytes of them...

Let me first say for the most part all previous posts in this thread are confusing cryptographic primitives. Please take no offense from this correction as cryptography is a difficult subject.

There are four separate topics here:
- Block ciphers (AES, DES, Blowfish) are what are used to encrypt some data with the use of a key. Then the same key can be used to reverse the process into the original input data. This is the cryptography the manual uses.
- Hash functions (SHA1, MD5, RIPEMD-160) are one-way functions that take some input and provide you with a set length output (SHA1 is 160bit, MD5 is 128bit). It is not possible to determine the original input with just the output and the knowledge of what function was used (hence one-way).
- Rainbow table is a pre-computed list of the outputs of one-way functions and the input that created them. Using a rainbow table of sufficient size it is possible to easily reverse a hash function but it is easily defeated by padding the input with a know value (salt).
- Hash function collisions (what the EngineYard contest was about) is the idea that there will exist more then one input for a possible function output. Since hash functions are the basis for digital signatures (used in SSL certificates for example) it is possible to forge an SSL certificate if you can find a way to pad your input with enough special values to make the hash output the same as an already signed certificate. Since the hash values are the same that same signature would work for both the original and the bad certificate.

Now in the original post Andrew provided us with three hash values (DES is not a hash function but I am assuming he means the crypt() function in UNIX that uses a variation on the DES algorithm to create a one-way hash function). A preliminary search of some of the free online rainbow tables yielded no results for me.

This would leave us with only the option of brute forcing the algorithm. Now he did indicate that the input was 12 characters which narrows the field somewhat and that the input consists of A-Z, a-z, 0-9, and space. This leaves us with 12 (r) spots for one of 63 (n) values. Using (n+r-1)!/r!(n-1)! we arrive at 21,944,067,106,416 possible values.

Now I for one don't have enough time on the University supercomputer to brute force that but if someone has a few graphics cards laying around you could probably build a computer that could crack it in a weeks time.

[Jared Russell]

Originally Posted by jtdowney

This would leave us with only the option of brute forcing the algorithm. Now he did indicate that the input was 12 characters which narrows the field somewhat and that the input consists of A-Z, a-z, 0-9, and space. This leaves us with 12 (r) spots for one of 63 (n) values. Using (n+r-1)!/r!(n-1)! we arrive at 21,944,067,106,416 possible values.

Now I for one don't have enough time on the University supercomputer to brute force that but if someone has a few graphics cards laying around you could probably build a computer that could crack it in a weeks time.

1) Andrew defined his alphabet as A-Z, a-z, space. He did not say that 0-9 were in the input. The alphabet size is therefore 53, not 63.

2) You used (n+r-1)! / r!(n-1)! to compute the number of possible inputs. This is the formula for the number of COMBINATIONS with repetition. A combination is an un-ordered collection of elements. Order is important for the input string (as "123" hashes to something different from "321" with all of the schemes discussed in this thread); the correct formula to use is therefore the number of PERMUTATIONS with repetition. This is simply n^r as I had done above.

n^r = 53^12 = 4.91258904 × 10^20

Originally Posted by jtdowney

Let me first say for the most part all previous posts in this thread are confusing cryptographic primitives. Please take no offense from this correction as cryptography is a difficult subject.

None taken

[Andrew Schreiber]

It has been just over a week, was anyone able to complete the challenge? Did anyone get close?

[Akash Rastogi]

Originally Posted by Andrew Schreiber

It has been just over a week, was anyone able to complete the challenge? Did anyone get close?

Abhi wasjust about to send it out to a college computer lab =(

[Andrew Schreiber]

Originally Posted by Akash Rastogi

Abhi wasjust about to send it out to a college computer lab =(

New challenge coming probably tomorrow around 12 (as soon as I think of a 12 letter phrase) The staying up to post at 12 thing was a little late for my non build season sleep schedule.

[Andrew Schreiber]

New phrases

DES - CRKRc/vgbyLyc
MD5 - 5bd4c87976f48e6a53919d53e14025e9
SHA1 - 27ceb60ff69ef41a393942a25dcdea0ce5b6c844

This weeks phrase is simpler, 6 letters, no spaces, capital and lower case letters.

Also, I encourage participants to post their best Hamming Distance for scoring purposes. Lower scores are better.

For anyone curious, PM me if you want to know last week's phrase (if some people are still trying I dont want to ruin it)

[Andrew Schreiber]

Lostmage333 Has gotten the phrase used to generate these hashes. In the interest of not ruining this week for everyone though the answer won't be revealed yet.

As a hint, the length of this phrase is short enough that rainbow tables become a viable option.

[Andrew Schreiber]

Pat Fairbanks has also gotten a solution using Python to brute force the answer. It took roughly 14 hours.

[Akash Rastogi]

Originally Posted by Andrew Schreiber

Pat Fairbanks has also gotten a solution using Python to brute force the answer. It took roughly 14 hours.

Could we learn what computers these were done on?

[Pat Fairbank]

Here's the code I used for my solution. Note that since I'm not in any way a Python guru, there may be a more elegant and/or faster solution; I just didn't want to take the time to figure out how to do hashes in C/C++.

import hashlib
import time

hash = '5bd4c87976f48e6a53919d53e14025e9'
digits = [65, 65, 65, 65, 65, 65]

t0 = time.clock()

while 1:
  phrase = ''
  for i in range(0, 6):
    phrase += chr(digits[i])
  
  if hash == hashlib.md5(phrase).hexdigest():
    print phrase
    break
  
  for i in range(5, -1, -1):
    digits[i] += 1
    if digits[i] == 123:
      digits[i] = 65
      continue
    if digits[i] == 91:
      digits[i] = 97
    break

print time.clock() - t0

This was run on a 2 GHz Core 2 Duo; I ran two instances of the script at the same time so as to use both cores, with one starting at AAAAAA and the other at aAAAAA. I imagine that if you had access to something like MapReduce it would go a whole lot faster.

[Andrew Schreiber]

Congrats to LostMage and Pat on getting the correct phrase.

Sorry for the delay in posting but since we should have been celebrating the last days of summer ANYWAY Im sure most people don't mind.

MD5 3ad751c9436de4cd139e6809ac20eb07
SHA1 1dfb6ecb052c4aa08267a1a3f6be392cdb0aebd8
SHA256 46322a7ae53c06c6a52ca845229ee0753dc3f777b0c1f1598a f736f37e1185f0

14 letters, 2 words, all lower case. Keep in mind that I cannot spell. As an additional hint, this clue is related, very loosely, to the way Pat solved last weeks puzzle and my favorite colour.

Good Luck.