Tags: sagemath crc crackme
Rating: 5.0
In this challenge we see a password-verification program. The password is quite long:
assert 16 < len(passwd) < 70
The first few checks verify md5, sha1 and sha3_224 digests. Due to long password, it is unlikely to use them to recover the password. Then, three transformations applied aiming to "destroy" the password: exponentiation modulo a prime, iterated encryption with DES and AES. Though, it is easy to see that they are trivially invertible. For the final "destroyed" value, the omnihash tool is used, which checks the password using 72 different hash functions, including many CRC variants. We are given the digests of these functions in the hash.json file.
CRC functions are totally not cryptographically secure: they are affine functions. Therefore, we can efficiently use them to deduce information about the hashed value. One may try to use the definition of CRC functions as modular reductions in the ring of polynomials over GF(2) and use the Chinese Remainder Theorem to reconstruct the value. However, CRCs have lots of subtle details, like order of bits, polynomial modulus, length encoding (padding), constant addition. Figuring out all of these details would be a real pain.
Instead, we can directly use the fact that the functions are affine and construct a system of linear equations. An m-bit CRC function applied to n-bit string s can be expressed as CRC(s) = A ⨉ s ⊕ c, where A is an m ⨉ n matrix and c is an m-bit vector. The matrix columns correspond to evaluations of the CRC function on unit vectors and c = CRC(0). In this way we can reconstruct them given a blackbox oracle to the CRC function. Recovering s is reduced to solving the system of linear equations.
Note that we have to use known 8-byte prefix and 8-byte suffix. After that, the kernel of the linear system has dimension 10, meaning that if there is a solution, then there are exactly 1024 of them. This is a small amount and we can enumerate over all of them. The right one can be identified using one of strong hash functions given in the hash.json file.
The final password (hex):
c7d0425d8f844bd7c5fc59005ca6b56f12e971d32a82004dda88d3ad4766e75c ed502149347257ffb0cd8a99bdc39598d2107cbdd35b501257156b095da5f31d
The flag: Balsn{Th3_M0r3__7He_bEtT3r??}
