Maplectf 2022 Crypto

An interesting game learned a lot

jwt

using flask frame, generate signature by own JWT

JWT using ES256, but replace random k with sk

def _sign(self, msg):
    z = sha256(msg.encode()).digest()
    k = self.private

    z = bl(z)

    r = (k * self.G).x
    s = inverse(k, self.order) * (z + r * self.private) % self.order

    return r, s

It has an obvious weakness. If we get a message m and it’s signature, we can calculate sk. Then forging the signature of “admin”. Finally, changing the cookie.

from Crypto.Util.number import bytes_to_long as bl, inverse
from fastecdsa.curve import secp256k1
from base64 import b64encode, urlsafe_b64decode, urlsafe_b64encode
from hashlib import sha256
from json import loads, dumps


def b64decode(msg: str) -> bytes:
    if len(msg) % 4 != 0:
        msg += "=" * (4 - len(msg) % 4)
    return urlsafe_b64decode(msg.encode())


def b64encode(msg: bytes) -> str:
    return urlsafe_b64encode(msg).decode().rstrip("=")


class ES256:
    def __init__(self,sk):
        self.G = secp256k1.G
        self.order = secp256k1.q
        self.private = sk
        self.public = self.G * self.private

    def _sign(self, msg):
        z = sha256(msg.encode()).digest()
        k = self.private

        z = bl(z)

        r = (k * self.G).x
        s = inverse(k, self.order) * (z + r * self.private) % self.order

        return r, s

    def _verify(self, r, s, msg):
        if not (1 <= r < self.order and 1 <= s < self.order):
            return False

        z = sha256(msg.encode()).digest()
        z = bl(z)

        u1 = z * inverse(s, self.order) % self.order
        u2 = r * inverse(s, self.order) % self.order

        p = u1 * self.G + u2 * self.public

        return r == p.x

    # return true if the token signature matches the data
    def verify(self, data, signature):
        r = int.from_bytes(signature[:32], "little")
        s = int.from_bytes(signature[32:], "little")

        return self._verify(r, s, data)

    # return the signed message and update private/public
    def sign(self, data):
        header = b64encode(
            dumps({"alg": "ES256", "typ": "JWT"}).replace(" ", "").encode()
        )
        data = b64encode(dumps(data).replace(" ", "").encode())

        r, s = self._sign(header + "." + data)
        signature = r.to_bytes(32, "little") + s.to_bytes(32, "little")

        return header + "." + data + "." + b64encode(signature)

    # return the decoded token as a JSON object
    def decode(self, token):
        _header, _data, _signature = token.split(".")
        header = loads(b64decode(_header))
        data = loads(b64decode(_data))
        signature = b64decode(_signature)

        if header["alg"] != "ES256":
            raise Exception("Algorithm not supported!")

        if not self.verify(_header + "." + _data, signature):
            raise Exception("Invalid signature")

        return {"user": data["user"]}


ord=secp256k1.q
msg='eyJhbGciOiJFUzI1NiIsInR5cCI6IkpXVCJ9.eyJ1c2VyIjoiaGFzaGhhc2gifQ'
z = sha256(msg.encode()).digest()
h=bl(z)
r=21636293118727726977265635476279874794445349002012576260859056953209657266927
s=102819800697865321507042085336309258398691558010316143016587408887929967868299
sk=(inverse(s-r,ord)*h%ord)
jwt = ES256(sk)
print(jwt.sign({"user": 'admin'}))

e000p

Just need to make Twist Edwards curve map onto Elliptic curve, and using sagemath to calculate

import gmpy2
from tqdm import tqdm
a=1
d = 3617
p = 2 ** 414 - 17
order = 2 ** 411 - 33364140863755142520810177694098385178984727200411208589594759
hint = 323811241263249292936728039512527915123919581362694022248295847200852329370976362254362732891461683020125008591836401372097
K=4*gmpy2.invert(a-d,p)%p
J=2*(a+d)*gmpy2.invert(a-d,p)%p
PR.<x>=PolynomialRing(Zmod(p))
'''
f=x^2-K
print(f.roots())
[(27048615771530228195825691602482238683620666057252797780378874564865444234468244072234247813233978088098098091776612500289230, 1), (15258966231045682137096888111615107865397233652461200253838648332696526404655682060577861654907800142147739477824882431183137, 1)]
'''
k=15258966231045682137096888111615107865397233652461200253838648332696526404655682060577861654907800142147739477824882431183137
x,y = (17319886477121189177719202498822615443556957307604340815256226171904769976866975908866528699294134494857887698432266169206165, 34)
s=(1+y)*gmpy2.invert(1-y,p)%p
t=s*gmpy2.invert(x,p)*k%p
E=EllipticCurve(GF(p),[0,J,0,1,0])
G=E((s,t))
x1,y1= (29389900956614406804195679733048238721927197300216785144586024378999988819550861039522005309555174206184334563744077143526515, 35393890305755889860162885313105764163711685229222879079392595581125504924571957049674311023316022028491019878405896203357959)
s1=(1+y1)*gmpy2.invert(1-y1,p)%p
t1=s1*gmpy2.invert(x1,p)*k%p
enc=E((s1,t1))
enc=enc-hint*G
G1=2^313*G
dic={}
for i in tqdm(range(1,2^22)): 
    enc=enc-G1
    dic[enc]=i
G2=2^13*G
g=0
for i in tqdm(range(1,2^22)): 
    g=g+G2
    if g in dic.keys(): 
        print(i) 
        print(dic[g])

from Crypto.Util.number import *
i=577508
j=1927017
hint=323811241263249292936728039512527915123919581362694022248295847200852329370976362254362732891461683020125008591836401372097
order = 2 ** 411 - 33364140863755142520810177694098385178984727200411208589594759
m=j*2**313+i*2**13+hint
print(long_to_bytes(inverse(m,order)))

qotp-real

An OTP system, the key generate is strange.

class Qstate:
    def __init__(self, x: float, y: float):
        assert(abs(x * x + y * y - 1.0) < EPS)
        self.x = x
        self.y = y

    def __mul__(self, other):
        return self.x * other.x + self.y * other.y


class Base:
    def __init__(self, q1: Qstate, q2: Qstate):
        assert(abs(q1 * q2) < EPS)
        self.q1 = q1
        self.q2 = q2

    def measure(self, q: Qstate):
        alpha = (self.q1 * q)**2
        return int(uniform(0, 1) >= alpha)

It looks like make ‘01’ sequence become the vector of random base in

def get_random_bases(n: int):
    angles = [pi / 4 * uniform(-pi, pi) + pi / 4 for _ in range(n)]
    bases = [Base(Qstate(cos(angle), sin(angle)), Qstate(-sin(angle), cos(angle))) for angle in angles]
    return bases

We can know 0 means the vector which angle is smaller

green is ‘0’ vector area, blue is ‘1’ vector area

if we choose the angle of purple to decrypt, we will more likely to get 0 if the bit is ‘1’

So we just need to decrypt the result of same message enough times, to record The number of corresponding 0 or 1

from pwn import *
from tqdm import tqdm
from math import sin, cos, tan, pi
from Crypto.Util.number import *

x=x=pi/4*(pi)+pi/2
a=cos(x)
b=sin(x)
c=cos(x+pi/2)
d=sin(x+pi/2)

time=20
t0=0
t1=0
m=[0]*352

for i in tqdm(range(10)):
  p=remote('qotp.ctf.maplebacon.org',1337)
  #p=process('./otp.py')
  for j in (range(time)):
   p.sendlineafter('Enter choice: ','3')
   p.sendlineafter('q1.x: ',str(a))
   p.sendlineafter('q1.y: ',str(b))
   p.sendlineafter('q2.x: ',str(c))
   p.sendlineafter('q2.y: ',str(d))
   re=str(p.recvline()[:-1])[2:-1]
   for k in range(len(re)):
    sign=int(re[k])
    if sign:
     m[k]-=1
    else:
     m[k]+=1
  p.close()
  
for i in range(len(m)):
 if m[i]>0:
  m[i]='1'
 else:
  m[i]='0'
  
m=int(''.join(m),2)
print(long_to_bytes(m))

Spiral-baby&Spiral

It is my first time to learn the attack on block cipher

I use differential attack to solve baby-spiral, but did not find the good method to solve spiral in time.

After the game, I find the attack is similar to 4rouds-AES attack(Square attack)

procedure

Square attack is check the key probability byte by byte, using encyption’s wondeful structure

from pwn import *
from Crypto.Util.number import *

p=remote('spiral-baby.ctf.maplebacon.org',1337)

def rev_add_key(state,idx):
 for i in range(4):
  for j in range(4):
   state[i][j] = (state[i][j] - keys[idx][i][j]) % 255
 return state

def rev_substitute(state):
 for i in range(4):
  for j in range(4):
   state[i][j] = SBOX.index(state[i][j])
 return state

def rotate(state):
 state = spiralRight(state)
 return state

def spiralRight(matrix):
 right = []
 for j in range(4):
  for i in range(3, -1, -1):
   right.append(matrix[i][j])
 return bytes2matrix(right)

def spiralLeft(matrix):
 left = []
 for j in range(3, -1, -1):
  for i in range(4):
   left.append(matrix[i][j])
 return bytes2matrix(left)

def bytes2matrix(bytes):
 return [list(bytes[i : i + 4]) for i in range(0, len(bytes), 4)]

def matrix2bytes(matrix):
 return bytes(sum(matrix, []))

SBOX = [184, 79, 76, 49, 237, 28, 54, 183, 106, 24, 192, 7, 43, 111, 175, 44, 46, 199, 182, 115, 83, 227, 61, 230, 6, 57, 165, 137, 58, 14, 94, 217, 66, 120, 53, 142, 29, 150, 103, 75, 186, 39, 31, 196, 18, 207, 244, 16, 213, 243, 114, 251, 96, 4, 138, 197, 10, 176, 157, 91, 238, 155, 254, 71, 86, 37, 130, 12, 52, 162, 220, 56, 88, 188, 27, 208, 25, 51, 172, 141, 168, 253, 85, 193, 90, 35, 95, 105, 200, 127, 247, 21, 93, 67, 13, 235, 84, 190, 225, 119, 189, 81, 250, 117, 231, 50, 179, 22, 223, 26, 228, 132, 139, 166, 210, 23, 64, 108, 212, 201, 99, 218, 160, 240, 129, 224, 233, 242, 159, 47, 126, 125, 146, 229, 0, 252, 161, 98, 30, 63, 239, 164, 36, 80, 151, 245, 38, 107, 3, 65, 73, 204, 8, 205, 82, 78, 173, 112, 219, 136, 123, 149, 118, 32, 215, 163, 74, 134, 248, 68, 110, 45, 59, 145, 178, 156, 100, 177, 221, 2, 92, 20, 40, 144, 101, 140, 169, 116, 143, 202, 1, 113, 209, 104, 133, 128, 70, 89, 216, 147, 122, 131, 9, 249, 121, 109, 191, 77, 124, 246, 55, 198, 187, 185, 17, 60, 180, 203, 19, 158, 97, 206, 148, 5, 87, 170, 236, 222, 194, 15, 214, 241, 211, 234, 42, 41, 153, 62, 102, 152, 69, 181, 34, 48, 226, 11, 195, 154, 174, 167, 135, 232, 72, 171, 33]

SPIRAL = [
    [1, 19, 22, 23],
    [166, 169, 173, 31],
    [149, 212, 176, 38],
    [134, 94, 59, 47],
]

def diff_attack(S,a,b,m):
 z=[]
 for x in range(len(S)):
  if (S[x]-S[(x+a)%255])%255==b:
   z.append((x-m)%255)
 return z

key=[0]*16
diff=0x34

idx=0
while True:
 sign=0
 tmp=[]
 x=1
 while True:
  se=hex(x)[2:].rjust(2,'0')*16
  p.sendlineafter('>>> ','2')
  sleep(0.01)
  p.sendline(se)
  re=int(p.recvline()[:-1],16)
  cipher1=bytes2matrix(long_to_bytes(re))
  for i in range(3):
   cipher1=rotate(cipher1)
  xx=(x+diff)%255
  se=hex(xx)[2:].rjust(2,'0')*16
  p.sendlineafter('>>> ','2')
  sleep(0.01)
  p.sendline(se)
  re=int(p.recvline()[:-1],16)
  cipher2=bytes2matrix(long_to_bytes(re))
  for i in range(3):
   cipher2=rotate(cipher2)
  beta=(cipher1[idx//4][idx%4]-cipher2[idx//4][idx%4])%255
  print(diff_attack(SBOX,diff,beta,x))
  if sign==0:
   tmp.extend(diff_attack(SBOX,diff,beta,x))
  sign+=1
  if len(tmp)==1:
   key[idx]=tmp[0]
   idx+=1
   break
  tmp=list(set(tmp).intersection(diff_attack(SBOX,diff,beta,x)))
  x+=1
 if key[len(key)-1]!=0:
  break
 print(key)

key=bytes(key)
keys=[bytes2matrix(key)]
keys.append(spiralLeft(keys[-1]))
p.sendlineafter('>>> ','1')
re=p.recvline()[:-1]
for i in range(0,len(re),32):
 tmp=int(re[i:i+32],16)
 c=bytes2matrix(long_to_bytes(tmp))
 c=rev_add_key(c,1)
 for j in range(3):
  c=rotate(c)
 c=rev_substitute(c)
 m=rev_add_key(c,0)
 print(matrix2bytes(m))