Misc - Simple Signing

Look at this signing service I made. I didnt want to implement my own hashing algorithm, so I just used python's. Nothing can go wrong right? - White

Challenge

from Crypto.Util.number import getPrime
from secrets import FLAG
ADMIN = b'adminTokenPlsNoSteal'


def sign(n: int, d: int, m: bytes):
    if m == ADMIN:
        print("no no")
        exit(0)
    
    h = hash(tuple(m))
    return pow(h, d, n)

def verify(n: int, e: int, m: bytes, s: int):
    h = hash(tuple(m))
    return pow(s, e, n) == h

if __name__ == "__main__":
    p, q = getPrime(1024), getPrime(1024)
    e = 0x10001
    n = p*q
    d = pow(e, -1, (p-1)*(q-1))

    print("""1. sign a message
             2. get flag""")
    while True:
        inp = input("> ")
        if int(inp) == 1:
            msg = bytes.fromhex(input("Message to sign (in hex): "))
            print("Signature:", sign(n, d, msg))
        else:
            sig = int(input("Give signature of admin token: "))
            if verify(n, e, ADMIN, sig):
                print("Congratz!!")
                print(FLAG)
                exit(0)
            else:
                print("You are not the admin")
                exit(0)

We are given the server file, which allows you to do to sign a message, and verify your signature.

The server allows you to sign any message other than the Admin token.

Let's look at how the signature is calculated

We need to give the signature of the Admin token inorder to get the flag

The signature scheme is similar to RSA Signing, except we sign a hash of the tuple of the message instead of the message itself.

So we need to find a collision for the hash or attack the signature scheme

Initially, I tried to find hashes for the factor of the hash, but since the factor of the hash is a large prime, it is equivalent of finding the corresponding hash for the prime which is the same as finding a collision

Therefore, we try to find a collision for the hash instead.

After searching for a long time, I was able to find this excellent writeup for a similar challenge (FCSC 2022). Here I will give a detailed description of that writeup.

FCSC 2022

The challenge is similar to the one given, except that it only allows ASCII values <128<128<128.

Since hashing a python integer is the same as taking mod 261−12^{61} -1 , we don't need to worry about python object hashing for integers.

First, let's go through the Cpython source files for tuple hashing Objects/tupleobject.c

If we convert this to python, it looks something like this

Here, go is used instead of python because it's faster and uses less memory

The hash size is 64 bits, therefore we can use the birthday attack to try to find a collision after generating 2n/22^{n/2} or 2322^{32} hashes.

We can expect a collision if we construct 2322^{32} hashes forward into a map A and 2322^{32} hashes in backward into a map B in order to produce a 64-bit collision

P5→Round(c1)→...→Round(c5)→AChall→Reverse(c10)→...→Reverse(c1)→BP_5 → Round(c_1) → ... → Round(c_5) → A \\ Chall → Reverse(c_{10}) → ... → Reverse(c_1) → B \\

However, this approach has significant time complexity, so we can relax the time complexity by constructing 4 forward rounds (4*7) + a partial round (1*3) for a total of 2312^{31} hashes forward and 4 rounds in reverse (4*7) for a total of 2282^{28} hashes backwards to cause a 56-bit collision.

P5→Round(c1)→...→Round(c5=a..h)→/P2⇒AChall→Reverse(c10)→...→Reverse(c7)→/P1→ROR(31)→/P2⇒BP_5 → Round(c_1) → ... → Round(c_5=a..h) → / P_2 ⇒ A\\ Chall → Reverse(c_{10}) → ... → Reverse(c_7) → / P_1 → ROR(31) → / P_2 ⇒ B

Instead of directly storing the hashes at the end of forward round 5 and backward round 7, we do a partial round to speed up the attack by taking inverse with P2 and P1. We do this because

h6=rotate(h5+c6∗P2)∗P1rotate−1(h6∗P1−1)∗P2=h5∗P2−1+c6h_6 = rotate(h_5 + c_6 * P_2) * P_1 \\ rotate^{-1}(h_6*P_1^{-1})*P_2 = h_5 *P_2^{-1} + c_6

Store all the partial forward hashes of h5∗P2−1h_5*P_2^{-1} into A and rotate−1(h6∗P1−1)∗P2rotate^{-1}(h_6*P_1^{-1})*P_2 into B. Then solve for c6c_6 in A+c6=BA +c_6 = B

To reduce the space complexity, we need to efficiently store (and index) the hashes. This is achieved using a clever bitset technique

Instead of storing all the bits of the forward rounds, we store 34 bits of the MSB by using 28 bits of the MSB as the index and remaining 6 bits of the MSB as the value. Since there can be multiple forward hash values having the same 28 bits of MSB, we use OR of 1 << (mid % 64) store the remaining 6 bits. In the backward rounds, if we want to check for possible collisions by checking the MSB, all we need to do is use the 28 bits of MSB as the index, and check if left shift of 8 bits of MSB is 1. This takes about 2 GB of RAM

Similarly for the backward round, we store 32 bits of the MSB by using 26 bits of the MSB as index and remaining 6 bits of the MSB as the value. However, we only store the backward hash values if the MSB of the forward round and MSB the backward round match. If they do match, we also store the 4 bytes c7...c10c_7...c_{10} of the backward round in a collisions map using 57 bits of the MSB instead of 64 bits as the index, because we still need to solve for the lower 7 bits which is c6c_6 in A+c6=BA +c_6 = B , where A and B are the forward and backward bitmaps.

Finally, we solve for c6c_6. We already have the last 4 bytes c7...c10c_7 ...c_{10} in a collisions map, now we compute the forward round to get the values of c1...c5c_{1}...c_{5} and using the map B from the backward rounds, we can check for possible collisions by checking if the MSB of the forward and backward rounds match. If they match, then we check if the value exists in the collisions map, which we use as the index to find backward round bytes. Now that we have the forward round bytes c1...c5c_1...c_5 and the backward round bytes c7...c10c_7...c_{10}, we solve for c6c_6 by hashing c1...c10c_1...c_{10} until it matches the hash of the challenge.

Full Implementation

After which we get the flag

PreviousUofTCTF 2025NextHTB CyberApocalypse

Last updated