3 ms·
Yes: very roughly, you could precompute the internal state after 'abcdefg' -- essentially checkpointing the algorithm -- and then compute SHA1('abcdefgX'), SHA1
by gojomo 17y ago
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.