Differences with part 1

Compared to part 1, part 2 allowed the bandits to get in 2x the number of failed guesses (for a total of 10 failed guesses), and we need to succeed in tricking the bandit 100 times in a row. We can check for words that fit a similar strategy to part 1, but it quickly becomes evident that there aren't any candidates. Thus, we concluded that the hash must be weak somehow.

Understanding the hash function

Stealing a python reimpl of the hash function from the pins, we can start to piece together the routine of the hash function. It works roughly as follows:

1. The bandit's salt is used as the IV, and stored in the output array.
2. For each block of 16 bytes in the input data (which is padded to fit), the output array is modified with the following function:

def inner(ptr, block_data, bandit_salt):
    """
    Manipulate bytes in a1 based on a2 and a3.

    Args:
        ptr: the
        block_data: A bytearray of 16 bytes
        bandit_salt: A list of 2 integers (QWORDs)

    Returns:
        Nothing (modifies a1 in-place)
    """
    # Convert a1 to a bytearray for byte-level operations
    ptr_modifiable = bytearray(ptr)

    state = bytearray(24)

    for i in range(15):  # 0 to 14
        for j in range(16):  # 0 to 15
            index = j | (16 * i)
            shift = indexshiftbox[index] >> 4
            mask = indexshiftbox[index] & 0xF

            ptr_modifiable[j] ^= a1_xor_box[bandit_salt[shift] ^ block_data[j] ^ bandit_salt[mask]]
            state[j] = state_replace[ptr_modifiable[j]]
            ptr_modifiable[j] = 0

        for k in range(128):  # 0 to 127
            byte_index = k >> 3
            bit_index = k & 7

            shift1 = kshiftbox[k] >> 3
            shift2 = kshiftbox[k] & 7

            ptr_modifiable[byte_index] ^= (((state[shift1] >> shift2) & 1) << bit_index)

    return bytes(ptr_modifiable)

The bottom loop appears to just be shuffling the bits around in the array, and checking kshiftbox shows that they are all unique values, so it should just shuffle the bits around.

The top loop is a little more interesting. There's 2 sbox looking things, a1_xor_box and state_replace. It would be convenient if one of these were linear, and it turns out, state_replace is linear! Now, what exactly does this mean?

Abusing linearity

Examining what happens when we change the input data, we see that since each byte is processed independently, the linearity in the state_replace sbox means that changing the value of a byte provides a fixed linear transformation on the output. This means with 128 bytes of input data, we can forge any hash we want by solving the system of linear equations, since the hash is a 128 bit hash.

But, there seems to be a problem. There's a limit of 16 bytes for the salt!

However, using what we learned in part 1, it turns out we can just shove 112 bytes of the data into the word itself by just sending word + b'\x00' + our_salt[:112] as the word, and our_salt[-16:] as the salt (fixing the -17th index of the salt to be a null byte).

For the hangman part, we can just use 4 letter words and always claim the bandit chose letters that weren't in the words. After they ask for verification, we send the "word" and our 16 byte salt. Doing this 100 times, we retrieve the flag!