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:
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.m1
, it must be practically impossible to find a message m2
such that hash(m1) = hash(m2)
.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.
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.
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.
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
13392.py
Challenge contributed by randomdude999
You must be logged in to submit your flag.
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
13397.py
Challenge contributed by ciphr
You must be logged in to submit your flag.
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
13395.py
Challenge contributed by VincBreaker
You must be logged in to submit your flag.
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
13388.py
Challenge contributed by randomdude999
You must be logged in to submit your flag.
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
13393.py
Challenge contributed by Cryptanalyse
You must be logged in to submit your flag.
You are now level Current level