DEV Community

Cover image for SHA256le in 16 guesses (or less)
Donald Sebastian Leung
Donald Sebastian Leung

Posted on

SHA256le in 16 guesses (or less)

Disclaimer: The author of this post is not affiliated with the creator of SHA256le.

SHA256le is a variant of the viral word game Wordle by GitHub user keftcha, where the mystery word is replaced with a mystery SHA256 hash.

Recall that a hash is just a value comprised of a fixed number of bits - in the case of SHA256, 256 bits. So basically, this variant of the game asks you to guess a 256-bit value, though unlike the original, there is no limit to the number of guesses you can make.

Note that bits in hashes are typically represented as hexadecimal digits, by arranging the bits in groups of 4. So instead of entering 256 ones and zeroes as your guess, you should enter 256 / 4 = 64 hexadecimal digits instead.

My claim

At first glance, the game seems insanely difficult as you have to guess the contents of a random, long sequence of characters that look like total gibberish instead of proper English words. But it turns out, there is a strategy that ensures you never have to make too many guesses. In particular, I claim that given the correct strategy, you only ever need to make 16 guesses at most. What is that strategy, and why does it work?

I'll give you some time to think about it. If you would rather receive the explanation directly, continue reading ;-)

Proof of my claim

A hexadecimal digit is just a group of 4 bits. Since each bit has two possible values {0, 1}, a group of 4 bits has 2 ** 4 == 16 possible values. In fact, we can list all possible hexadecimal digits as below:

0123456789abcdef

So, a possible strategy is as follows:

  1. Start by guessing all zeroes
  2. For all incorrect guesses in step 1, replace them with ones
  3. Repeat step 2, cycling through every possible hexadecimal digit until all such digits have been tried or you arrive at the correct guess, whichever comes first

If you arrive at the correct guess before cycling through all possible digits, then you used less than 16 guesses. Otherwise, at the end of the 15th guess, you know that whatever incorrect digits remaining must be the only digit that you have not tried.

The strategy in action

Optimal strategy in action

Going further

The strategy highlighted above gives a worst-case scenario of 16 guesses. Here are some more food for thought:

  • If you are well versed in probability, what is the expected number of guesses with such a strategy? (Intuition tells me it will be just under 16)
  • Is it possible to come up with a strategy with a better worst-case scenario, and if so, what is that strategy and why does it work? If not, why not?
  • Is it possible to come up with a strategy with a better expected number of guesses?

I hope you enjoyed this article ;-)

Discussion (1)

Collapse
davidalinford profile image
David Linford

I have a method that consistently gets it in 13, 14 max. Also your pic of your completion in 16 doesn't look real because all the non green characters are yellow, except for line 3. There should be lots more grey cells. Maybe this is an old version.