First things first, thanks to diracdelta from our team "The Additional Payphones" for taking a rough cut of the collider code and actually converting it into a flag with some points!
The challenge source code can be found here, and it is fairly straitforward.
A command-line service is exposed over tcp which allows the user to enter up to 10 commands. Possible commands are:
The user dict is initialized with an 'admin' user that has a 42 byte urandom password, and passwords are hashed using the following function:
def harc4(x):
ksz = ARC4.key_size[-1]
csz = ksz - len(IV)
state = IV
for i in range(0, len(x), csz):
key = x[i:i+csz] + state
cipher = ARC4.new(key)
state = cipher.encrypt(state)
return state.hex()
Where IV
is 32 uandom bytes generated at startup so the same 32 bytes are used.
The point of the challenge is to break this hash function and log in as admin.
There are a couple of minor observations that make the hash function easier to deal with
With these details, the hash function looks a lot simpler if we know the password is between 1 and 224 bytes inclusive:
def harc4_simple(x):
key = x + IV
cipher = ARC4.new(key)
state = cipher.encrypt(IV)
return state.hex()
RC4 is a stream cipher, so cipher.encrypt(IV)
just takes the first 32 bytes of the key stream and XORs it with the IV - since we have the IV we can extract the keystream and the problem boils down to finding a colliding password x2
such that the first 32 bytes of the keystream matches the 32 bytes of the keystream that we observed.
This requires attacking RC4. After a review of the literature, the only useful detail readily available was that to use RC4 safely it is necessary to discard the first 512 bytes of the keystream and that it is probably possible to construct a key tha would produce a collision.
I am going to describe such an algorithm here at a high level, but really the only way to understand it in depth is to look at the code
RC4 is a surprisingly simple encryption algorithm. The cipher maintains an internal state of two indexes and a permutation of the numbers {0, ..., 255}. First the permutation is seeded with the secret key using the key scheduling algorithm, and then the bytes are encrypted using the keystream generation function.
The code is easy to read, so I would recommend taking a look at the actual cipher code
In the end I was able to derive an algorithm that constructs a key prefix that, when appended to the IV will generate the target 32 bytes as the prefix of its keystream. The principles at play are:
In the end, a lot of things are possible but because of comprimises made to get it to work in time the algorithm ends up "quarantining" the IV so that it only modifies indexes 0, 64, 128, and 196 and the 100 bytes of output state avoid these indexes. As a result of this compromise, the algorithm only works for about half of the IV/keystream pairs. For the other half it is unable to quarantine the IV. It could be improved to work in all cases, but that was not required for this CTF.
In the end, through the help of the team we were able to use this attack to log in as admin and get the flag.
Balsn{f0rG1ng_7He_w0Rld}