3
\$\begingroup\$

This is the robbers thread of this cops and robbers challenge. The cops thread is here.

Related, but hashes numbers instead of strings and uses a different scoring system.

Definitions

A hash collision is when two different strings produce the same hash.

Summary

In this challenge, the cops will make a hash function, with a collision they know of. Then, the robbers will try to crack it by finding a hash collision in the cop's hash algorithm. To crack an answer, the hash collision the robber finds does not have to be the intended solution.

If a cop submission is not cracked for 7 days, it is safe, so mark it as such and reveal the intended crack and the score.
If a cop submission is cracked, mark it as such and edit in a link to the crack.

Format

A robber answer has to contain the hash collision, a link to the cracked answer, and the score.

Scoring

The score of a robber answer is the sum of the number of bytes of the two strings with the hash collision, with the higher score being better.

The winner

With robbers and cops being ranked separately, the winner is the person with the best scoring answer.

Example

Cop:

Python

from hashlib import*
def singlecharhash(x):
  a = blake2b(digest_size=1)
  a.update(x)
  return a.hexdigest()

Robber:

4 Points, Cracks cop's answer

¯ and É, both 2 bytes.

Pinboard

I am thinking of changing the scoring system to make it the minimum of the two strings. Any thoughts?

\$\endgroup\$
6
  • \$\begingroup\$ What if cracker can construct collision of extremely long one? \$\endgroup\$
    – l4m2
    Commented Aug 15, 2023 at 0:47
  • \$\begingroup\$ @l4m2 then it’s totally fine. \$\endgroup\$ Commented Aug 15, 2023 at 8:35
  • \$\begingroup\$ It gives infinite score and can't compare \$\endgroup\$
    – l4m2
    Commented Aug 15, 2023 at 9:11
  • \$\begingroup\$ @l4m2 it’s a trade off. Post a crack with a short char length immediately or spend some time and then post a crack with a longer char length. \$\endgroup\$ Commented Aug 15, 2023 at 14:12
  • \$\begingroup\$ There's case where generating a longer one is easier \$\endgroup\$
    – l4m2
    Commented Aug 16, 2023 at 0:33

1 Answer 1

5
\$\begingroup\$

Cracks Sisyphus's, 1 byte

b'' and b'\x00'

Try it online!

I'm not sure if this is the intended solution but it's definitely the simplest.

As @gsitcia has pointed out in the comments, for SHA-256 if the key is less than 64 bytes HMAC pads it with null bytes to length 64. So by adding a null byte to any key with less than 64 bytes we get the same result.

As @gsitcia also points out, for any key longer than 64 bytes, it is replaced with its hash. We can see this in action here. It is trivial to generate arbitrarily long collisions in this way.

\$\endgroup\$
7
  • 2
    \$\begingroup\$ The reason this works is that HMAC (with SHA-256) right pads the string with null bytes to 64 bytes (only if the key starts with <= 64 bytes. If it starts with more, it instead replaces the key with the hash of the key) \$\endgroup\$
    – gsitcia
    Commented Aug 15, 2023 at 6:11
  • 2
    \$\begingroup\$ "The score of a robber answer is the sum of the number of bytes of the two strings with the hash collision, with the higher score being better" - perhaps you'd want to add some (a lot of) stuffer to your crack to increase its score...? \$\endgroup\$ Commented Aug 15, 2023 at 9:54
  • 1
    \$\begingroup\$ @DominicvanEssen Whoops, golf instincts. In any case, that seems strange. If the robber gets to choose, well in this case there's a cap but in general the largest possible collision may be arbitrarily large \$\endgroup\$ Commented Aug 15, 2023 at 13:59
  • \$\begingroup\$ @CursorCoercer You still have to find the crack. \$\endgroup\$ Commented Aug 15, 2023 at 14:12
  • 6
    \$\begingroup\$ There is a trivial infinite crack, set the first string to anything longer than 64 bytes, and set the second string to the sha-256 hash of the first string. \$\endgroup\$
    – gsitcia
    Commented Aug 15, 2023 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.