2) Indeed Cuda can be used with success, and this is probably the way to go. Unfortunately I don't have any board at hand, but I'll buy one later in order to experiment with this technology.
3) This is not going to save you any time. Basically the part that alters the five chars at the end is nothing compared to the rest of the computation.
There are other tricks that can be used, like to compute a fast hamming distance, just xor the bytes of the two strings and count the bits using a lookup table. Or even use some specific asm instruction for bit counting. But again unless you are doing this stuff of the xor in a very slow way this is a negligible amount of work: I commented out the hammer distance computation in my code and the numbers are exactly the smae, 3.5 million comparison per second per core more or less.
Another obvious optimization is of course to avoid doing too much permutations of the words. For every permutation there are a lot of tries to do just altering the final five chars.
Basically there is no way to win without to resort to fast hardware and parallelization, being it a large set of computers, CUDA, or a very lucky run that outputs in 30 hours an entry with an hamming distance of 31 or 32 just... against the probabilities ;)
The only reason I'm running the contest is that it's funny and a very good way to teach something interesting to the programmers working in my company. We care a lot about having fun programming.
However, I think a good solution (if you're going to use CUDA, which I was thinking about doing as well) might be to load one permuation of words from the dictionary into the shared memory, and then have each thread compute one permuation of the various capitalizations for that string. This way you're mostly working out of the "cache" and that's about the best thing you can do on CUDA.
I actually started a thread in the CUDA general discussion forum, perhaps you could come by there and discuss it:
1. SHA-1 is done in 64 byte chunks, with the result of one chunk being the base of the next. Padding and length only factor in at the last chunk. This means you can half the number of computations (or even 1/3 it...) by computing the first block of a "prefix string" then going from there.
2. Cuda is good on integer ops. SHA-1 is integer ops.
3. All the combinations of <= 5 printable chars can be represented in <60 MB meaning they don't have to keep being generated.
Not saying anything the article says was wrong per-say Im saying that large amounts of computation can be factored out from the naive approach, large enough to be meaningful that is.