# Writeup: zer0pts CTF 2022

on nevi.dev

## Anti-Fermat (crypto, warmup)

I invented Anti-Fermat Key Generation for RSA cipher since I’m scared of the Fermat’s Factorization Method.

files

This task implements textbook RSA, but with some special key generation:

``````# Anti-Fermat Key Generation
p = getStrongPrime(1024)
q = next_prime(p ^ ((1<<1024)-1))
n = p * q
e = 65537
``````

It generates a (strong) 1024-bit prime `p` as usual. Then it generates `q` as the first prime number that follows the binary inverse of `p`.

This means that every bit posistion (except for some low-order bits) will be set in exactly one of `p` and `q` (that is, `p XNOR q` is zero except for some low-order bits). Furthermore, since a bit can only be set in one of `p` or `q`, assuming `p > q` (which implies that `p` has its 1024th bit set), the order for all possible values of `p * q` is the same as the order of the values of `q`.

In other words, if we “move” a bit from `p` to `q`, we get a larger number. This lets us leak each bit position (except for some low-order bits, but we can brute force those).

We start off with `p` as all 1’s (except for some 20 low-order bits) and `q` as zero.

``````p = ((1<<1024)-1) ^ ((1<<20)-1)
q = 0
``````

Then, for each bit position from 1023 down to 20, we check if the value of `(p ^ 1<<bit) * (q ^ 1<<bit)` is smaller than the challenge `n`. If the product is smaller than `n`, then we “move” the bit from `p` to `q`).

``````for i in range(1022, 19, -1):
cur = 1<<i
if (p^cur) * (q^cur) < n:
p ^= cur
q ^= cur
``````

After this, we can be confident we have the top 1024-20 bits of `p`. Run an exhaustive search for the remaining 20 bits, and decrypt `c` to obtain the flag.

``````while n%p != 0:
p = gmpy2.next_prime(p)
q = n//p

d = gmpy2.invert(0x10001, (p-1) * (q-1))
print(long_to_bytes(pow(c, d, n)).decode())
``````
``````\$ time ./solve.py
p = 153456316755201256456077648680293404551531181234956990242779099773886170192558263224753907666532907469313954439789378399786631549347700474488574017322863270205683350905558827922567834954626909259763623105532668671134932118937640401627676913585506492102157561689678418157863742997375967679975824876706628973287
q = 26312996731030334316852870398609068810266516659273667030650981383846505612942699907954569655874628551806159440082014957872158219466716148004273413316610854172084542519306657353734384646619184859689459846552337097703218563404822479846236196955320745061192948994907880082083502941103748624859531452917595165959
Good job! Here is the flag:
+-----------------------------------------------------------+
| zer0pts{F3rm4t,y0ur_m3th0d_n0_l0ng3r_w0rks.y0u_4r3_f1r3d} |
+-----------------------------------------------------------+

real    0m14.728s
user    0m14.724s
sys     0m0.004s
``````

solve.py

## MathHash (misc)

I invented a very fast yet secure hash algorithm!

`nc misc.ctf.zer0pts.com 10001`

files

The server has a hash function `MathHash`, which is fed with `flag + input`. Thus, we need to leak information about the flag in the hash output.

The hash function in question is like so:

``````def MathHash(m):
hashval = 0
for i in range(len(m)-7):
c = struct.unpack('<Q', m[i:i+8])
t = math.tan(c * math.pi / (1<<64))
hashval ^= struct.unpack('<Q', struct.pack('<d', t))
return hashval
``````

The hash function takes `tan(pi * c/1<<64)` for a rolling 8-byte window (taken as little-endian 64-bit unsigned integer) and XORs the resulting double into the hash output.

Since the 8-byte window is unpacked in little-endian, the last byte in the window is most significant. The `tan` result is XORed such that the most significant byte in the double is XORed into the most significant byte of the output.

For reference, a double is stored in memory like so1: Now, with lots of trial and error, we discover that the last byte of each 8-byte window is correlated with the most-significant byte of the `tan` output. In fact, we notice that for the range of values we need to deal with, exactly one of the 6th or 7th bit of the most-significant byte in the `tan` output is set. A notable exception is when the input is all zeroes, in which case the `tan` output is also zero.

This means that we can look at the 6th and 7th bits changing in the hash output to check whether we successfully guessed the hash output.

Starting with the 7 known bytes (`zer0pts`), we make a guess for the next character, and send an input such that it sums to 0 with the flag. If we guessed correctly, exactly one of the 6th or 7th bits should have flipped. Repeat this until we obtain the entire flag.

``````\$ ./solve.py
[+] Opening connection to misc.ctf.zer0pts.com on port 10001: Done
[*] zer0pts{
[*] zer0pts{s
[*] zer0pts{s1
[...]
[*] zer0pts{s1gn+|3xp^|fr4c.}
[+] zer0pts{s1gn+|3xp^|fr4c.}
[*] Closed connection to misc.ctf.zer0pts.com port 10001
``````

solve.py