Brute Forcing 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.