Hash Functions

A hash function is a function which takes an arbitrary long string of bits and produces a fixed-length output. Hash functions have applications in data structures, string-searching and even in video game design. Here we're interested in a subset of hash functions which are suitable for cryptographic purposes.

Cryptographic hash functions are designed to be one-way: functions that are practically impossible to invert. This is in contrast to the functions used in asymmetric cryptography, where trapdoor functions are infeasible to invert unless some additional secret knowledge is known.

Cryptographic hash functions are used to verify message integrity, compute digital signatures, and safely store passwords in databases. In asymmetric cryptography, hash functions are particularly useful in compressing arbitrary length messages to a value which has a smaller bit-length than the modulus when signing messages with RSA or protocols such as (EC)DSA or Elgamal.

For a hash function to be cryptographically secure, it must be resistant to the following three attacks:

  • Pre-image attacks: given the output of a hash function x = hash(m), it must be practically impossible to find a message m0 such that hash(m0) = x. This is another way of saying that the hash must be a one-way function.
  • Second pre-image resistance: given a message m1, it must be practically impossible to find a message m2 such that hash(m1) = hash(m2).
  • Collision resistance: it should be practically impossible to find two messages m1, m2 such that hash(m1) = hash(m2). Note the difference to the second pre-image attack, in that we can vary both m1 and m2.

We can think of this as a linked set of dependencies, if a pre-image attack is known, so are second pre-image attacks and collision attacks. But if a collision attack is known, this doesn't generically allow pre-image attacks against the hash function.

Ultimately, it is impossible for a hash function to be totally secure against these attacks, in the same way symmetric and asymmetric ciphers can have their protocols brute forced. Even given a perfect one-way function, as the output has a fixed length, there will be infinitely many inputs that yield any chosen output. The goal for a cryptographic hash function is then to have algorithms designed to make the above problems "sufficiently" hard assuming an attackers compute power.

In the following challenges, we present custom hash functions which do not meet these criteria, or older cryptographic hash functions which have been found to be vulnerable to attacks.

Probability

 Toggle
  • Jack's Birthday Hash
    20 pts · 1626 Solves · 7 Solutions

    Today is Jack's birthday, so he has designed his own cryptographic hash as a way to celebrate.

    Reading up on the key components of hash functions, he's a little worried about the security of the JACK11 hash.

    Given any input data, JACK11 has been designed to produce a deterministic bit array of length 11, which is sensitive to small changes using the avalanche effect.

    Using JACK11, his secret has the hash value: JACK(secret) = 01011001101.

    Given no other data of the JACK11 hash algorithm, how many unique secrets would you expect to hash to have (on average) a 50% chance of a collision with Jack's secret?

    You must be logged in to submit your flag.


  • Jack's Birthday Confusion
    30 pts · 1396 Solves · 6 Solutions

    The last computation has made Jack a little worried about the safety of his hash, and after doing some more research it seems there's a bigger problem.

    Given no other data of the JACK11 hash algorithm, how many unique secrets would you expect to hash to have (on average) a 75% chance of a collision between two distinct secrets?

    Remember, given any input data, JACK11 has been designed to produce a deterministic bit array of length 11, which is sensitive to small changes using the avalanche effect.

    You must be logged in to submit your flag.


Collisions

 Toggle
  • Collider
    50 pts · 1195 Solves · 5 Solutions

    Check out my document system about particle physics, where every document is uniquely referenced by hash.

    Connect at nc socket.cryptohack.org 13389

    Challenge files:
      - 13389.py

    You must be logged in to submit your flag.


  • Hash Stuffing
    50 pts · 653 Solves · 11 Solutions

    With all the attacks on MD5 and SHA1 floating around, we thought it was time to start rolling our own hash algorithm. We've set the block size to 256 bits, so I doubt anyone will find a collision.

    Connect at nc socket.cryptohack.org 13405

    Challenge files:
      - source.py

    You must be logged in to submit your flag.


  • PriMeD5
    100 pts · 459 Solves · 7 Solutions

    Primality checking is expensive so I made a service that signs primes, allowing anyone to quickly check if a number is prime.

    The solution requires ~5 minutes to calculate on a commodity PC.

    Connect at nc socket.cryptohack.org 13392

    Challenge files:
      - 13392.py


    Challenge contributed by randomdude999

    You must be logged in to submit your flag.


  • Twin Keys
    100 pts · 323 Solves · 2 Solutions

    Cryptohack's secure safe requires two keys to unlock its secret. However, Jack and Hyperreality can't remember the keys, only the start of one of them. Can you help find the lost keys to unlock the safe?

    Connect at nc socket.cryptohack.org 13397

    Challenge files:
      - 13397.py


    Challenge contributed by ciphr

    You must be logged in to submit your flag.


  • No Difference
    175 pts · 356 Solves · 14 Solutions

    It's easy to come across a collision for MD5, but can you find one in my custom hash function?

    Connect at nc socket.cryptohack.org 13395

    Challenge files:
      - 13395.py


    Challenge contributed by VincBreaker

    You must be logged in to submit your flag.


Length Extension

 Toggle

  • I've invented a nice simple version of HMAC authentication, hopefully it isn't vulnerable to the same problems as Merkle–Damgård construction hash functions...

    Connect at nc socket.cryptohack.org 13388

    Challenge files:
      - 13388.py


    Challenge contributed by randomdude999

    You must be logged in to submit your flag.


  • MDFlag
    125 pts · 193 Solves · 5 Solutions

    MD0 had a serious weakness, here is a new improved MD5-based HMAC.

    Connect at nc socket.cryptohack.org 13407

    Challenge files:
      - 13407.py


    Challenge contributed by giladk

    You must be logged in to submit your flag.


Pre-image attacks

 Toggle
  • Mixed Up
    120 pts · 356 Solves · 2 Solutions

    Due to the properties of XOR and hash functions, it shouldn't be possible to unmix the flag... or is it?

    Connect at nc socket.cryptohack.org 13402

    Challenge files:
      - 13402.py


    Challenge contributed by giladk

    You must be logged in to submit your flag.


  • Invariant
    250 pts · 151 Solves · 3 Solutions

    It's said that you shouldn't roll your own hash function. But how easy is it to break one?

    Connect at nc socket.cryptohack.org 13393

    Challenge files:
      - 13393.py


    Challenge contributed by Cryptanalyse

    You must be logged in to submit your flag.


Level Up

level up icon

You are now level Current level