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.

def verify(n: int, e: int, m: bytes, s: int):
    h = hash(tuple(m))
    return pow(s, e, n) == h
sig = int(input("Give signature of admin token: "))
if verify(n, e, ADMIN, sig):
    print("Congratz!!")
    print(FLAG)
    exit(0)

Let's look at how the signature is calculated

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)

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

#!/usr/bin/env python3.9
try:
	flag = tuple(open("flag.txt", "rb").read())
	assert len(flag) == 70

	challenge = hash(flag)
	print(f"{challenge = }")

	T = tuple(input(">>> ").encode("ascii"))
	if bytes(T).isascii() and hash(T) == challenge:
		print(flag)
	else:
		print("Try harder :-)")
except:
	print("Error: please check your input")

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

Since hashing a python integer is the same as taking mod $2^{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 SIZEOF_PY_UHASH_T > 4
#define _PyHASH_XXPRIME_1 ((Py_uhash_t)11400714785074694791ULL)
#define _PyHASH_XXPRIME_2 ((Py_uhash_t)14029467366897019727ULL)
#define _PyHASH_XXPRIME_5 ((Py_uhash_t)2870177450012600261ULL)
#define _PyHASH_XXROTATE(x) ((x << 31) | (x >> 33))  /* Rotate left 31 bits */
#else
#define _PyHASH_XXPRIME_1 ((Py_uhash_t)2654435761UL)
#define _PyHASH_XXPRIME_2 ((Py_uhash_t)2246822519UL)
#define _PyHASH_XXPRIME_5 ((Py_uhash_t)374761393UL)
#define _PyHASH_XXROTATE(x) ((x << 13) | (x >> 19))  /* Rotate left 13 bits */
#endif

/* Tests have shown that it's not worth to cache the hash value, see
   https://bugs.python.org/issue9685 */
static Py_hash_t
tuplehash(PyTupleObject *v)
{
    Py_ssize_t i, len = Py_SIZE(v);
    PyObject **item = v->ob_item;

    Py_uhash_t acc = _PyHASH_XXPRIME_5;
    for (i = 0; i < len; i++) {
        Py_uhash_t lane = PyObject_Hash(item[i]);
        if (lane == (Py_uhash_t)-1) {
            return -1;
        }
        acc += lane * _PyHASH_XXPRIME_2;
        acc = _PyHASH_XXROTATE(acc);
        acc *= _PyHASH_XXPRIME_1;
    }

    /* Add input length, mangled to keep the historical value of hash(()). */
    acc += len ^ (_PyHASH_XXPRIME_5 ^ 3527539UL);

    if (acc == (Py_uhash_t)-1) {
        return 1546275796;
    }
    return acc;
}

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

P1 = 11400714785074694791
P2 = 14029467366897019727
P5 = 2870177450012600261
M = 1<<64
def pyhash(tup):
    x = P5
    for b in tup:
        x += P2 * b
        x &= M-1
        x = (x >> 33) | (x << 31) & (M-1)
        x *= P1
        x &= M-1
    x += (P5 ^ 3527539 ^ len(tup))
    return x & (M-1)

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

const (
    P1 = 11400714785074694791
    P2 = 14029467366897019727
    P5 = 2870177450012600261
    
    P1inv = 614540362697595703   // pow(P1, -1, 2**64)
    P2inv = 839798700976720815   // pow(P2, -1, 2**64)
    P5inv = 14236653164957433613 // pow(P5, -1, 2**64)
)
func hash(s []byte) uint64 {
    h := uint64(P5)
    for _, b := range s {
        h = round(h, uint64(b))
    }
    h += uint64(len(s)) ^ P5 ^ 3527539
    return h
}

func round(acc uint64, c uint64) uint64 {
    acc += c * P2
    acc = bits.RotateLeft64(acc, 31)
    acc *= P1
    return acc
}

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

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

$$P_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 $2^{31}$ hashes forward and 4 rounds in reverse (4*7) for a total of $2^{28}$ hashes backwards to cause a 56-bit collision.

$$P_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

$$h_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 $h_5*P_2^{-1}$ into A and $rotate^{-1}(h_6*P_1^{-1})*P_2$ into B. Then solve for $c_6$ in $A +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

const BITMAP_SIZE = 34
bitmap := make([]uint64, 1<<34/64)
for c1 := uint64(0); c1 < 128; c1++ {
    if c1%8 == 0 {
        fmt.Println("c1 = ", c1)
    }
    h1 := round(h0, c1)
    for c2 := uint64(0); c2 < 128; c2++ {
        h2 := round(h1, c2)
        for c3 := uint64(0); c3 < 128; c3++ {
            h3 := round(h2, c3)
            for c4 := uint64(0); c4 < 128; c4++ {
                h4 := round(h3, c4)
                for c5 := 'a'; c5 <= 'h'; c5++ {
                    h5 := round(h4, uint64(c5))
                    mid := h5 * P2inv
                    mid >>= (64 - BITMAP_SIZE)
                    bitmap[mid/64] |= 1 << (mid % 64)
                }
            }
        }
    }
}

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 $c_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 $c_6$ in $A +c_6 = B$ , where A and B are the forward and backward bitmaps.

bitmap2 := make([]uint64, 1<<32/64)
collisions := make(map[uint64][4]byte)
h10 := challenge - (10 ^ P5 ^ 3527539)
for c10 := uint64(0); c10 < 128; c10++ {
    if c10%8 == 0 {
        fmt.Println("c10 = ", c10)
    }
    h9 := bits.RotateLeft64(h10*P1inv, 33) - c10*P2
    for c9 := uint64(0); c9 < 128; c9++ {
        h8 := bits.RotateLeft64(h9*P1inv, 33) - c9*P2
        for c8 := uint64(0); c8 < 128; c8++ {
            h7 := bits.RotateLeft64(h8*P1inv, 33) - c8*P2
            for c7 := uint64(0); c7 < 128; c7++ {
                h6 := bits.RotateLeft64(h7*P1inv, 33) - c7*P2
                mid := bits.RotateLeft64(h6*P1inv, 33) * P2inv
                m := mid >> (64 - BITMAP_SIZE)
                if bitmap[m/64]&(1<<(m%64)) != 0 {
                    collisions[mid>>7] = [4]byte{byte(c7), byte(c8), byte(c9), byte(c10)}
                    bitmap2[mid>>32/64] |= 1 << ((mid >> 32) % 64)
                }
            }
        }
    }
}

Finally, we solve for $c_6$. We already have the last 4 bytes $c_7 ...c_{10}$ in a collisions map, now we compute the forward round to get the values of $c_{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 $c_1...c_5$ and the backward round bytes $c_7...c_{10}$, we solve for $c_6$ by hashing $c_1...c_{10}$ until it matches the hash of the challenge.

h0 = uint64(P5)
Loop:
    for c1 := uint64(0); c1 < 128; c1++ {
        if c1%8 == 0 {
            fmt.Println("c1 = ", c1)
        }
        h1 := round(h0, c1)
        for c2 := uint64(0); c2 < 128; c2++ {
            h2 := round(h1, c2)
            for c3 := uint64(0); c3 < 128; c3++ {
                h3 := round(h2, c3)
                for c4 := uint64(0); c4 < 128; c4++ {
                    h4 := round(h3, c4)
                    for c5 := 'a'; c5 <= 'h'; c5++ {
                        h5 := round(h4, uint64(c5))
                        mid := h5 * P2inv
                        // check bitmap (fast path)
                        m := mid >> 32
                        if (bitmap2[m/64]>>(m%64))&1 == 0 {
                            continue
                        }
                        // check map
                        if tail, ok := collisions[mid>>7]; ok {
                            for c6 := uint64(0); c6 < 128; c6++ {
                                word := [10]byte{
                                    byte(c1), byte(c2), byte(c3), byte(c4),
                                    byte(c5), byte(c6), tail[0], tail[1],
                                    tail[2], tail[3]}
                                if hash(word[:]) == challenge {
                                    fmt.Printf("%q => %d\n", word[:], challenge)
                                    break Loop
                                }
                            }
                        }
                    }
                }
            }
        }
    }

Full Implementation

//https://remyoudompheng.github.io/ctf/fcsc2022/crypto-khalhash.html
package main

import (
    "fmt"
    "math/bits"
    "os"
    "strconv"
    "time"
)

const (
    P1 = 11400714785074694791
    P2 = 14029467366897019727
    P5 = 2870177450012600261

    P1inv = 614540362697595703   // pow(P1, -1, 2**64)
    P2inv = 839798700976720815   // pow(P2, -1, 2**64)
    P5inv = 14236653164957433613 // pow(P5, -1, 2**64)
)

func main() {
    challenge, err := strconv.ParseUint(os.Args[1], 10, 64)
    if err != nil {
        panic(err)
    }

    const BITMAP_SIZE = 34
    bitmap := make([]uint64, 1<<34/64)  // 2048MB
    bitmap2 := make([]uint64, 1<<32/64) // 512MB
    collisions := make(map[uint64][4]byte)
    // Forward map (31 bits)
    // P5 => round1 => round2 => round3 => round4 => round5 / P2 = A
    t0 := time.Now()
    h0 := uint64(P5)
    for c1 := uint64(0); c1 < 128; c1++ {
        if c1%8 == 0 {
            fmt.Println("c1 = ", c1)
        }
        h1 := round(h0, c1)
        for c2 := uint64(0); c2 < 128; c2++ {
            h2 := round(h1, c2)
            for c3 := uint64(0); c3 < 128; c3++ {
                h3 := round(h2, c3)
                for c4 := uint64(0); c4 < 128; c4++ {
                    h4 := round(h3, c4)
                    for c5 := 'a'; c5 <= 'h'; c5++ {
                        h5 := round(h4, uint64(c5))
                        mid := h5 * P2inv
                        mid >>= (64 - BITMAP_SIZE)
                        bitmap[mid/64] |= 1 << (mid % 64)
                    }
                }
            }
        }
    }
    fmt.Println("forward bitmap generated in", time.Since(t0).Round(time.Second/10))
    // Backward map (28 bits)
    // Challenge => round10inv => round9inv => round8inv => round7inv / P1 invrot / P2 = B
    t0 = time.Now()
    h10 := challenge - (10 ^ P5 ^ 3527539)
    for c10 := uint64(0); c10 < 128; c10++ {
        if c10%8 == 0 {
            fmt.Println("c10 = ", c10)
        }
        h9 := bits.RotateLeft64(h10*P1inv, 33) - c10*P2
        for c9 := uint64(0); c9 < 128; c9++ {
            h8 := bits.RotateLeft64(h9*P1inv, 33) - c9*P2
            for c8 := uint64(0); c8 < 128; c8++ {
                h7 := bits.RotateLeft64(h8*P1inv, 33) - c8*P2
                for c7 := uint64(0); c7 < 128; c7++ {
                    h6 := bits.RotateLeft64(h7*P1inv, 33) - c7*P2
                    // h6 == rotate(h5 + c6 * P2) * P1
                    // invrot(h6 * P1inv) * P2inv == h5 * P2inv + c6
                    mid := bits.RotateLeft64(h6*P1inv, 33) * P2inv
                    m := mid >> (64 - BITMAP_SIZE)
                    if bitmap[m/64]&(1<<(m%64)) != 0 {
                        collisions[mid>>7] = [4]byte{byte(c7), byte(c8), byte(c9), byte(c10)}
                        bitmap2[mid>>32/64] |= 1 << ((mid >> 32) % 64)
                    }
                }
            }
        }
    }
    fmt.Println("backward bitmap generated in", time.Since(t0).Round(time.Second/10))
    fmt.Println(len(collisions), "possible collisions")

    // Forward map (31 bits)
    // Resolve A + c6 == B
    t0 = time.Now()
    h0 = uint64(P5)
Loop:
    for c1 := uint64(0); c1 < 128; c1++ {
        if c1%8 == 0 {
            fmt.Println("c1 = ", c1)
        }
        h1 := round(h0, c1)
        for c2 := uint64(0); c2 < 128; c2++ {
            h2 := round(h1, c2)
            for c3 := uint64(0); c3 < 128; c3++ {
                h3 := round(h2, c3)
                for c4 := uint64(0); c4 < 128; c4++ {
                    h4 := round(h3, c4)
                    for c5 := 'a'; c5 <= 'h'; c5++ {
                        h5 := round(h4, uint64(c5))
                        mid := h5 * P2inv
                        // check bitmap (fast path)
                        m := mid >> 32
                        if (bitmap2[m/64]>>(m%64))&1 == 0 {
                            continue
                        }
                        // check map
                        if tail, ok := collisions[mid>>7]; ok {
                            for c6 := uint64(0); c6 < 128; c6++ {
                                word := [10]byte{
                                    byte(c1), byte(c2), byte(c3), byte(c4),
                                    byte(c5), byte(c6), tail[0], tail[1],
                                    tail[2], tail[3]}
                                if hash(word[:]) == challenge {
                                    fmt.Printf("%q => %d\n", word[:], challenge)
                                    break Loop
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    fmt.Println("explored collisions in", time.Since(t0).Round(time.Second/10))
}

func hash(s []byte) uint64 {
    h := uint64(P5)
    for _, b := range s {
        h = round(h, uint64(b))
    }
    h += uint64(len(s)) ^ P5 ^ 3527539
    return h
}

func round(acc uint64, c uint64) uint64 {
    acc += c * P2
    acc = bits.RotateLeft64(acc, 31)
    acc *= P1
    return acc
}

After which we get the flag

'uoftctf{py7h0n_h45h_15_n07_cryp706r4ph1c4lly_53cur3}'