News for hackers. Stuff that matters.
Re:Engineyard SHA Contest Leaderboard I threw together by DocSavage on Tuesday July 21, 2009 @11:35PM (#717320)
I didn't scrutinize the sha-1 algorithm, but is it possible to optimize its computation (e.g., precompute intermediates) when using a small number of repeated words as input? This might explain why a group of people all arrived at similar solutions, since it only matters how quickly you can guess if all guesses are pretty much equal.

I lucked out and got a solution at 35. Coded something up in python and only got about 85k hashes/sec on one core. The CUDA program, though, was about 100x faster on my low-end Nvidia 8400 GS.

Re:Engineyard SHA Contest Leaderboard I threw together by gojomo on Wednesday July 22, 2009 @12:37AM (#717381)
Yes: very roughly, you could precompute the internal state after 'abcdefg' -- essentially checkpointing the algorithm -- and then compute SHA1('abcdefgX'), SHA1('abcdefgY'), etc. more easily than other strings. (In fact, you'd want your checkpoint aligned at some multiple -- maybe 512 bits? -- but that's the general idea.)

I figured the 'final 5 arbitrary characters' was a nod to this approach. So the best strategy I could think of -- and I didn't try coding anything up for the contest -- was to (1) guess the word dictionary; (2) precompute a whole bunch of checkpointed-except-for-last-five-characters function states; (3) at the moment the real dictionary and target was announced, try many different last-five-character extensions against any valid precomputed states.