# zer0pts CTF 2021

## General Comments {#zer0pts2021}

I don‘t really have any comments regarding this CTF because I didn‘t really play much. I hardly logged in, I was “busy“ and not very motivated this weekend, but just noting it here in my CTF “diary.“

I know `poiko`

enjoyed it though, so it was probably good.

The motivation I *did* have was mostly to help out because I‘ve been a
shit team player for a while now, not really finding any will to
`li<code>^W</code>play`

{=html}. `poiko`

kept posting tasks to me on
Discord and I gave comments when able.

I only looked at the easy tasks. I skipped the two elliptic curve tasks completely because they weren‘t immediately obvious to me—I imagine they would involve googling stuff and/or Thinking, which I wanted to avoid.

## Easy Pseudo Random

An RNG^{1} is set up, $s_{i}=s_{i−1}+b(modp)$.

You‘re given the high bits of two consecutive states and the goal is to reconstruct the stream. So you have $(H_{0}⋅2_{85}+u)_{2}+b=H_{1}⋅2_{85}+v$ with $u,v$ being two unknown “small“ (85 bits) integers.

With high bits anything I immediately think of lattices as the obvious candidate, so that‘s what I tried here for a quick solve. I just ignored the terms $u_{2}$ and $v$ completely, trying to just minimize the simple and linear expression $2_{86}H_{0}v+b−2_{85}H_{1}(modp)$ with a small $u$. I can 100% guarantee that there‘s a cleaner and more robust way to attack the full polynomial, but I‘m dumb and would have to Think or google for it which, like I said, I wanted to avoid.

The error of the linear equation is expected to be around 170 bits, so I tried to find short vectors from a matrix like so:

```
[[ p+b-(H1<<85), 0, 1<<K0 ], # constant term
[ H0<<86, 1<<K1, 0 ], # linear factor of u
[ p, 0, 0 ]] # modulus
```

Starting with parameters `K1 ~ 86`

and `K2 ~ 171`

that I massaged a little until the correct solution for $u$ tumbled out.
Was mostly a quick hack. The rest is trivial.

## wa(rsa)mup

`poiko`

solved this one because he thought I wasn‘t going to play. I
was offline most of Friday and early Saturday.

I didn‘t know he had solved it and so I double-solved it. But no matter, it was a quick/standard problem.

Standard RSA setup. There‘s some code noise around padding but it‘s
irrelevant. The immediate suspect thing is you‘re given two
ciphertexts: $c_{0}=m_{e}(modn)$ and $c_{1}=⌊2m ⌋_{e}(modn)$. Because the message $m$ (probably) ends with
`}`

it is (probably) odd, which is relevant because now we
have a non-trivial relation $m_{0}=2m_{1}+1$. (If the relation had been
$m_{0}=2m_{1}$ instead, it wouldn‘t provide us with any more information.)

Plugging this relation into the ciphertext equations and treating the message as an “unknown“ we have two polynomial expressions which both have the message as a root and we can take their gcd:

```
>>> g = (x**e-c1).gcd(((x-1)/2)**e - c2)
>>> g
[113128245622357901252722513691018597529212818374857225068412230803117273431764336733611386199949429353010088688478215740193848150958821139378543874939689746528140403143114943900235798243884022251713648885768664407134358754271963457290992686093387882808160942022485994772070150575070443505280922344644888038580 1]
>>> (-g[0]).lift().bytes()
b'\x02\x81\xae\xed \xdd\x07\x12;\x99\xc7d:\x99\x1a8\x16\xfe\xe6<\x18\x1dw\xea&\xfb\xfc\x8a\xa7\xa8\xba\xfa\xd8\xbe\xdf\x01\x13\xcb\xd3\x99\x9c\xf3_\x18qw\xb99}\'Q\xd7~\x03&^\xcd\x9aw\xf0\xef\xb5\x04\x1b\xb7\n\xe1\xcd"\x95ff]\x0c(H\x99\xb5\xed\xc3\x82\x9dl\xe4\x8c\xddx\xfd\x00zer0pts{y0u_g07_47_13457_0v3r_1_p0in7}'
```

(Here using some number theory wrappers (using NTL) that I wrote for regular Python so I didn‘t have to use Sage so much. A leap for a man, an insignificant stumble for mankind.)

## janken vs. yoshiking

Didn‘t really solve it so much as I just told `poiko`

my guess for the
solution after seeing it. He wrote the actual solution.

What I wrote on Discord + added corrections:

```
# assumption: secret key x is odd.
# re-run program until x is odd
# idea, match quadratic "residue-ness" of numbers to rule out
# possibilities.
# put the numbers in GF(p) åker etc.
c0sq = c0.is_square()
canbe = 7 # 1|2|4 == all
if c0sq != c1.is_square():
canbe ^= 1 # can't be rock
if c0sq != (c1/2).is_square():
canbe ^= 2 # can't be scissors
if c0sq != (c1/3).is_square():
canbe ^= 4 # can't be paper
choice = ['invalid',
3, # beat rock
1, # beat scissors
1, # 50-50 to win/draw
2, # beat paper
3, # 50-50
2, # 50-50
randint(1,3), # ???
][canbe]
```

Which apparently worked.

This was probably the best (as in “non-boring“) task of the ones I looked at.

## ot or not ot

This one too, I didn‘t actually write the code or interact with the server, I just wrote on Discord what I thought the solution would be:

```
# reasoning:
# X = bit0 ^ ( a^r * c^s )
# Y = bit1 ^ ( b^r * c^s )
# Z = ( d^r * t^s )
# a = 2 or whatever
# b = a^-1
# c = -1
# X*Y = (-1)^(2*s) = 1
# send:
# a = 2 or whatever
# b = pow(a, -1, p)
# c = -1 % p
# d = ??? doesn't matter?
# then get x,y (z doesn't matter???) and this should work:
def get_two_bits(X,Y):
for bit0, bit1 in product((0,1), (0,1)):
if (X^bit0)*(Y^bit1)%p == 1:
return bit0 + 2*bit1
```

Which it did. I don‘t really understand what the `d`

,
`t`

and `z`

variables were doing in the program,
they seemed completely superfluous? Perhaps the problem author had
overlooked the possibility of giving `-1`

for `c`

so that $c_{k}$ becomes a trivial factor?

## Triple AES

This was the last task I did because it took much longer than the others (hours vs minutes), and so felt I was getting “sucked in.“

Setup: you can decrypt/encrypt arbitrary messages with some cipher that chains three AES instances (different keys) working in different block modes (ECB, CBC, CFB). You don‘t control the IVs generated for encryptions. You‘re disconnected immediately when retrieving the encrypted flag.

Not very hard, but very fiddly and ugh. These are my notes from the comments (I tend to “work out“ my thinking in comments):

```
# encryption:
# PLAIN: m0 || m1
# ECB: E0(m0) || E0(m1)
# CBC: E1(iv0 + E0(m0)) || E1( E1(iv0 + E0(m0)) + E0(m1) )
# CFB: E2(iv1) + E1(iv0 + E0(m0)) || E2(E2(iv1) + E1(iv0 + E0(m0))) + E1( E1(iv0 + E0(m0)) + E0(m1) )
# decryption:
# PLAIN: c0 || c1
# CFB: E2(iv1) + c0 || E2(c0) + c1
# CBC: D1(E2(iv1) + c0) + iv0 || D1(E2(c0) + c1) + E2(iv1) + c0
# ECB: D0(D1(E2(iv1) + c0) + iv0) || D0(D1(E2(c0) + c1) + E2(iv1) + c0)
# dec(0) : D0( D1(E2(0)) ) || D0( D1(E2(0)) + E2(0) )
# : D0(D1( E20 )) || D0( D1(E20) + E20 )
# enc(0) : E2(R1) + E1(R0 + E0(0)) || E2(E2(R1) + E1(R0 + E0(0))) + E1(E1(R0 + E0(0)) + E1(0))
# : E2(R1) + E1(R0 + E00) || E2( E2(R1) + E1(R0 + E00) ) + E1( E1(R0 + E00) + E10 )
# dec0(enc0,iv1=R1,iv0=0) :
# D0( R0 + E0(0) )
```

The intuition was that the special values of `enc(0)`

,
`dec(0,iv1=0,iv2=0)`

, or `dec(0,iv1=X,iv2=0)`

etc would somehow be
instrumental in unwrapping some of these constructs and finding
“primitives“ (like `aes_ecb_encrypt(key,0)`

) that can be
looked up in precomputed tables. (The keyspace for each of the three
keys was only 24 bits so each on its own is easily brute forceable.)

The last part of the comment above is me discovering the starting point
for recovering `key0`

and after that everything becomes easy.

The server has a very generous timeout which seems to indicate that some of this brute forcing could take place to dynamically construct messages for the server to encrypt/decrypt. Thus there‘s probably a better way of doing this, but I didn‘t look very hard. The only benefit to how I did is that no computation is needed when connected to server, just fetch a few key values and disconnect. Code:

```
from flagmining.all import *
z = byte(0)*16
n_keys = 2**24
ecb = lambda k: AES.new(k, mode=AES.MODE_ECB)
print("generating keys...")
keys = [md5(bytes(b)).digest() for b in tqdm(product(range(256), repeat=3), total=n_keys)]
print('making lookup table...')
enc_to_key = {ecb(k).encrypt(z): k
for k in tqdm(keys, total=n_keys)}
r = remote('crypto.ctf.zer0pts.com', 10929)
# [..] wrapping server communication in enc(), dec(), get_flag()
Ez, R0, R1 = enc(z)
Pz = dec(Ez, z, R1) # = D0(R0 ^ E0(0))
Dz = dec(z+z, z, z) # = D0(D1(E2(0))) || D0(D1(E2(0)) ^ E2(0))
flag3, flag_iv0, flag_iv1 = get_flag()
# Done with server.
# Find the key0 which makes D(R0 ^ E(0)) == Pz.
k0 = None
for x,k in tqdm(enc_to_key.items(), total=n_keys):
if ecb(k).decrypt(xor_bytes(x, R0)) == Pz:
k0 = k
break
assert k0
print("found key0:", k0)
# Now unwrap Dz and just look up key2 from table.
ciph0 = ecb(k0)
k2 = enc_to_key.get(xor_bytes(
ciph0.encrypt(Dz[:16]),
ciph0.encrypt(Dz[16:])), None)
assert k2
print("found key2:", k2)
flag2 = AES.new(k2, mode=AES.MODE_CFB, iv=flag_iv1, segment_size=8*16).decrypt(flag3)
# Now find the middle key that gives the flag.
print("finding k1...")
for k1 in tqdm(keys):
flag0 = ciph0.decrypt( AES.new(k1, mode=AES.MODE_CBC, iv=flag_iv0).decrypt(flag2) )
if b'zer0' in flag0:
print("found k1:", k1)
print("found flag:", flag0)
break
```

## Kantan Calc

No, I forgot one, but it kinda doesn‘t count. Sunday I went for my
usual walk across the ice, and feeling refreshed I opened this one.
`poiko`

had mentioned it briefly before, but I misunderstood the task
slightly and hadn‘t seen the source, so my suggestions at the time were
dead ends.

But now (with source) I got the right idea (or at least *a* right idea):

```
// 012345678901234567890123456789/* flag */})()
// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
// });(function x() {return x
// });(()=>()=>{
// });u=(s)=>()=>[...''+s];u(()=>{
// });((s)=>()=>[...''+s])(()=>{
```

Again I‘m sort of “thinking“ in comments.

The first two return the string of the function but are blocked by the
app because the substring `zer0pts`

is blacklisted. That was a bit
annoying to circumvent because I know next to nothing about JS. With the
last two the idea is to convert the string to an array so it gets
`t,r,a,n,s,f,o,r,m,e,d`

and bypasses the blacklist. The last
one is below length limit and works.

Should have also checked the main site tho, because turns out the CTF was already over when I did this one.

fun fact: Blum-Blum-Shub was the first “strong“ RNGs I was properly exposed to, through the excellent

`calc`

command-line program.↩