17

I want to know the mathematical time required for cracking hashes based off different sets of characters.

For example, using only 7 letter, US-ASCII alphabetic characters we know that there are 267 possible sequences that could be used. Knowing how many of these could be generated by a computer each minute would give me an idea of how long it would take to generate all possible hashes and crack a certain 7 character hash (birthday attacks aside).

For example, taking the number above, if a modern quad core could generate 1 million hashes each minute it would take 8031810176 / 1000000 / 60 = 133.86 hours to find all possible hashes in that range.

Also, how does the new Sandy Bridge Intel chips with native AES play into this?

Charles
  • 50,943
  • 13
  • 104
  • 142
Xeoncross
  • 55,620
  • 80
  • 262
  • 364

2 Answers2

14

I wrote this test in C using the OpenSSL SHA256 implementation.

#include <stdio.h>
#include <string.h>
#include "openssl/sha.h"

// http://stackoverflow.com/questions/4764608/generate-all-strings-under-length-n-in-c/4764686#4764686
int inc(char *str) {
    if (!str[0]) return 0;

    if (str[0] == 'z') {
        str[0] = 'a';
        return inc(str + sizeof(char));
    }

    str[0]++;
    return 1;
}

unsigned char buffer[65];
char* hashstring(char *str, int len) {
    char hash[SHA256_DIGEST_LENGTH]; // the openssl hash
    SHA256_CTX sha256;
    int i; // counter

    SHA256_Init(&sha256);
    SHA256_Update(&sha256, str, len);
    SHA256_Final(hash, &sha256);

    for (i = 0; i < SHA256_DIGEST_LENGTH; i++) {
        sprintf(buffer + (i * 2), "%02x", hash[i]); // convert openssl hash to mortal human string
    }

    return buffer;
}

int main(int argc, char *argv[]) {
    int N = 4; // max length string
    char str[N+1]; // the string holder
    int i; // counter

    unsigned int tot = 0; // number of hashes calculated

    for (i = 0; i < N; i++) str[i] = 'a';
    str[N] = 0;

    do {
        hashstring(str, N);
        tot++;
    } while(inc(str));

    printf("%d\n", tot);
}

Compile:

gcc -lcrypto -O3 -o test test.c

And results (I know, I'm not very creative with computernames):

nightcracker@nightcracker-pc:~/c/sha256$ time ./test
11881376

real    3m2.431s
user    3m2.335s
sys 0m0.008s

So that's 11881376 / 182.4 = 65139 hashes per second. Then it's 26^7/101821/3600 = 34 hours to compute all the hashes. Please note, all of this was done on a Q6600 quad-core CPU in a single-threaded application and excluded writing the hashes to file.

EDIT

Woops, I was calculating all the hashes of strings with N characters and below. Corrected and data updated.

orlp
  • 112,504
  • 36
  • 218
  • 315
  • so - spin up 4 of your programs and you can generate around 400k hashes/sec. – nos Jan 22 '11 at 01:03
  • I was generating the wrong strings, but now it's OK. I also apparently got lucky on one run (note, this is a PC, lot's of other stuff running too). – orlp Jan 22 '11 at 01:07
  • Thanks, I happen to have the Q8200 so this is very applicable to myself. I wonder how fast a new Sandy Bridge CPU could move. – Xeoncross Jan 24 '11 at 01:37
  • The number you picked (26) is only lowercase English letters. Upper, lower and numbers would be 62^7. All ASCII printable would be 95^7. SHA256 and other similar hashes are best cracked by GPUs. – 01100110 Mar 04 '12 at 03:13
  • @user1200129: I followed the requirements of the question: `For example, using only 7 letter, US-ASCII alphabetic characters we know that there are 267 possible sequences that could be used.`. – orlp Mar 04 '12 at 12:34
10

Remember that a GPU can hash 50x - 100x faster than a CPU. Its harder to program, but more efficient. See www.bitcointalk.com for numbers. I know I do 622 million SHA-256's per sec on a Radeon HD5830.

lordcirth
  • 101
  • 1
  • 2