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 RNG1 is set up, .

You‘re given the high bits of two consecutive states and the goal is to reconstruct the stream. So you have with 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 and completely, trying to just minimize the simple and linear expression with a small . 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 tumbled out. Was mostly a quick hack. The rest is trivial.


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: and . Because the message (probably) ends with } it is (probably) odd, which is relevant because now we have a non-trivial relation . (If the relation had been 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), # ???

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 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
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:])), 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)

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.

  1. fun fact: Blum-Blum-Shub was the first “strong“ RNGs I was properly exposed to, through the excellent calc command-line program.