Kudos

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!

Challenge Description

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:

  • login, takes a username and binary password encoded as hex. If the hash matches the one stored for that user, login is successful. Login as admin results in the flag being displayed
  • register, creates a new user by adding the username and password hash to the user dict
  • (hidden) _debug, displays all users and their password hashes

The user dict is initialized with an 'admin' user that has a 42 byte urandom password, and passwords are hashed using the following function:

In [1]:
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.

Breaking The Hash

There are a couple of minor observations that make the hash function easier to deal with

  • 0 byte passwords are in fact not hashes, and the IV is returned instead of a hash value
  • Passwords less than 225 bytes in length only go through one round of the hash

With these details, the hash function looks a lot simpler if we know the password is between 1 and 224 bytes inclusive:

In [ ]:
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 Description

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 key scheduling algorithm iterates through all 255 states of the permutations, and does a swap on each one based on the key. The two indexes are also set to zero.
  • Each byte of the keystream is generated by using the values at the 2 indexes to determine the keystream byte, the values at the indexes are swapped, and the indexes are updated.

The code is easy to read, so I would recommend taking a look at the actual cipher code

Finding Colliding Keys

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:

  • With full control of the 256 bytes of the key, we can fully determine the 256 bytes of internal state after key scheduling
  • With only 100 bytes of carefully set state, we can fully control the first 32 bytes of the keystream
  • The last 32 bytes of the key are the IV which we do not control, but with the remaining bytes that we do control we are able to set the state up in a way that prevents the IV from interacting with our 100 bytes of state needed for output

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.

Getting the Flag

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}

In [ ]: