Crypto writeup for zer0pts 2022

2022-03-22

字数统计: 115字 | 阅读时长≈ 1分

Last weekend I participated in zer0pts 2022 CTF online as a team member of Never Stop Exploiting (abbreviation: NeSE).We’re happy to get the first place in this high level competition. I focused on the crypto challenges and spent two days struggling with five challenges : Anti-Fermat、CurveCrypto、EDDH、OK、Karen, finally four of them solved. They are all well-designed and here are the writeups for Anti-Fermat、CurveCrypto、EDDH、OK.

Anti-Fermat

Challenge name	Author	Points	Solves
crypto/Anti-Fermat	ptr-yudai	90pts	125

Source code : task.py.

This is a warm-up challenge. Observe that p,q are generated in a special way : $q = next\_prime(p \oplus ((1<<1024)-1))$ . It’s equivalent to : $p+q=2^{1024}-1+y$ , where y is a small number. Therefore we can brute force the value of y with n=p×q known and construct a quadratic equation $n = (2^{1024}-1 + y)p - p^2$ to factor n.

Here is my solver : solve.ipynb.

CurveCrypto

Challenge name	Author	Points	Solves
crypto/CurveCrypto	theoremoon	156pts	36

Source code : task.py.

It seems like a curve problem? Haha, it’s just a blindfold. The ecc curve itself is secure. The crucial part of this problem is the unmatched block size. The modulus of ecc curve is 1024-bit but the cipher block length is just 16×8=128 bits, which means that we already have the 896 most significant bits leakage. Right, it’s coppersmith! Applying the bivariate coppersmith method to the ecc equations : $f(x,y)=(x+x0)^3 + a*(x+x0) + b-(y+y0)^2$ where x0 and y0 are the known high 896 bits of point (x,y) on ecc curve. Obliviously, $f(x,y)$ has small roots (x,y) upper bounded by $[2^{128},2^{128}]$ .

The solver in sagemath :

n = 144119247523820514307319742558945817289524321678464785828165262389987364282241677120346992289602773032781170623185859522408681068717004227361637296377314973988883717763449514502353544535632434189976809320943402560377421207936239458384129077990667822889168041784489265932700188699685494064706711885776064499497
a = 83982245487363010227377287615815704138676734572052340268107937333404040064487258387610318909300475704005267406361509228314981566916144028418544919408625857597243933586742790305821574823017061268314657578742703998273111267249007415214833152992932175602495617018238154444547422725699672732735594492967242602718
b = 102854241650706614574910858961148621902783569513613650939938174283440416794379436560775021794677794290971284767314108620894847399989166711219489947662922391647064573171363714323032220660223765035347554282052095512011142748460282601639626032525448005114625186640435086840602281790716023653081557628791656792754
c = [105112301098281496097034027523577403453326764144228787624401074405541577932642530851395484380691290162552636478481380927941044566041120344238783491322553291628678134801814105484196704974017218455216419335693731277825573231392222665423245586612395848380318111988284920983149197374154699808776545479724047776709, 119931822446994265076022490333904239240145849067899601686086810952135061724293475540637951596476598377673280140779509869539582077226280886787012312965074972316057414014195571814522208145587153069696640304889800585974357119323578638404957302760851214606619517664508954712497284900223656294050022339709410514520, 77449803463514047535477961978015960018035778347793833401263588747978475501148536780819549296447786417024775899457091074251167349568353877838782428368954481576827862607179873977973077737374411980559467128298050283927229354740670622117284854556777626729609958202274963553796799701913426256413699327094959918436, 19881898638980767541769585302774976337079209934548061143259050559139791898245439933411471322660256972236103364955342341822881304403603105610433373205174678091884754857958259183427619764249723943787639988589593508171175819610469625589807019978156747244656206732357606116993349990555417285468500357366492529137]
Cur=EllipticCurve(Zmod(n),[a,b])

import itertools
# from https://github.com/defund/coppersmith/blob/master/coppersmith.sage
def small_roots(f, bounds, m=1, d=None):
        if not d:
                d = f.degree()

        R = f.base_ring()
        N = R.cardinality()
        
        f /= f.coefficients().pop(0)
        f = f.change_ring(ZZ)

        G = Sequence([], f.parent())
        for i in range(m+1):
                base = N^(m-i) * f^i
                for shifts in itertools.product(range(d), repeat=f.nvariables()):
                        g = base * prod(map(power, f.variables(), shifts))
                        G.append(g)

        B, monomials = G.coefficient_matrix()
        monomials = vector(monomials)

        factors = [monomial(*bounds) for monomial in monomials]
        for i, factor in enumerate(factors):
                B.rescale_col(i, factor)

        B = B.dense_matrix().LLL()

        B = B.change_ring(QQ)
        for i, factor in enumerate(factors):
                B.rescale_col(i, 1/factor)

        H = Sequence([], f.parent().change_ring(QQ))
        for h in filter(None, B*monomials):
                H.append(h)
                I = H.ideal()
                if I.dimension() == -1:
                        H.pop()
                elif I.dimension() == 0:
                        roots = []
                        for root in I.variety(ring=ZZ):
                                root = tuple(R(root[var]) for var in f.variables())
                                roots.append(root)
                        return roots

        return []

from Crypto.Util.Padding import pad
from Crypto.Util.number import bytes_to_long,long_to_bytes
from tqdm import tqdm
P.<x,y>=PolynomialRing(Zmod(n))

res=b""
for i in range(len(c)//2):
    x0=(c[2*i]>>128)<<128
    y0=(c[2*i+1]>>128)<<128
    f=(x+x0)^3 + a*(x+x0) + b-(y+y0)^2
    r=small_roots(f,[2^128,2^128],m=4,d=3)
    res+=long_to_bytes(int(r[0][0])^^int(c[2*i]%2^128))
    res+=long_to_bytes(int(r[0][1])^^int(c[2*i+1]%2^128))
print(res)

EDDH

Challenge name	Author	Points	Solves
crypto/EDDH	theoremoon	188pts	24

Source code : server.py.

The author implements a DH protocol based on Edwards Curve and we’re supposed to break the DH protocol to get the server’s private key. Of course , the DH protocol on a valid curve with a non-smooth order q is hard to hack. So we do some observation on the modulus p and order q：

sage: factor(q)
2^4 * 4008813596126668177969229109004547757918317516793740452605321671090258497583
sage: factor(q-1)
7 * 359 * 1697309 * 22353507643 * 672723752029737196750690341089151895208427022727359340017
sage: factor(q+1)
3^2 * 8731 * 414857 * 134059463378879219 * 1588224359700172704654581 * 9241055866212299877660637
sage: factor(p+1)
2^3 * 3^2 * 7 * 97 * 13851989561 * 2116412438628327601 * 44752892864065123157027395440061784643030271
sage: factor(p-1)
2 * 91877347 * 4983572093 * 5393248331 * 5871788141 * 5984431231 * 7036447529 * 7114396253 * 7382806369

Oops, $p-1$ is deliberately smooth ! The first idea appears in my mind is to transform the Edwards Curve to a standard weierstrass curve. However the weierstrass curve’s order is still q. Then, we find that the author doesn’t check the validity of the point we submit, which means we can apply an invalid curve attack! In Edwards curve, if we submit an invalid point $tG=(0,y)$ , the mul operation becomes simply scalar power : $mul(s,tG)=(0, y^s)$ . In GF(p) field, the multiplication order is exactly p-1, smooth! We can use Pohlig–Hellman algorithm to solve the discrete log problem in a smooth order algebraic group. However, if we submit an invalid point, we’re not able to compute $s*tG$ given $sG$ and thus cannot get the shared secret. Luckily, the author provides us with a decryption oracle. The padding is also strange:

def pad(b, l):
    return b + b"\0" + b"\xff" * (l - (len(b) + 1))
def unpad(b):
    l = -1
    while b[l] != 0:
        l -= 1
    return b[:l]

The shared secret is in the form of : "\x00"*32 + long_to_bytes(y^s).If we upload a message m in form of : "\x00"*32 + 32*random bytes, after $\oplus$ operation and unpadding ,with a high probability, the message becomes m'="\x00"*31, as long as the 32 random bytes don’t have the same byte with long_to_bytes(y^s) in the same position. Therefore the results we receive from the server are exactly $pad(m')\oplus share$ and we can recover $share=(0,ys)$ from the results. Then compute the discrete log of $log_y\ ys$ to get server’s private key. It’s all done.

The python solver :

from pwn import *
from sympy import discrete_log
from random import randrange
from Crypto.Util.number import inverse, long_to_bytes,bytes_to_long
from Crypto.Cipher import AES
from hashlib import sha256
import ast
import os
def xor(xs, ys):
    return bytes(x^y for x, y in zip(xs, ys))

def pad(b, l):
    return b + b"\0" + b"\xff" * (l - (len(b) + 1))

def unpad(b):
    l = -1
    while b[l] != 0:
        l -= 1
    return b[:l]
def add(P, Q):
    (x1, y1) = P
    (x2, y2) = Q

    x3 = (x1*y2 + y1*x2) * inverse(1 + d*x1*x2*y1*y2, p) % p
    y3 = (y1*y2 - a*x1*x2) * inverse(1 - d*x1*x2*y1*y2, p) % p
    return (x3, y3)

def mul(x, P):
    Q = (0, 1)
    x = x % q
    while x > 0:
        if x % 2 == 1:
            Q = add(Q, P)
        P = add(P, P)
        x = x >> 1
    return Q

io=remote("crypto.ctf.zer0pts.com" ,10929)
context.log_level="debug"

n = 256
p = 64141017538026690847507665744072764126523219720088055136531450296140542176327
a = 362
d = 1
q = 64141017538026690847507665744072764126693080268699847241685146737444135961328
c = 4
gx = 36618472676058339844598776789780822613436028043068802628412384818014817277300
gy = 9970247780441607122227596517855249476220082109552017755637818559816971965596
G=(gx,gy)
y = randrange(0, p)
payload=b"00"*32+b"31"*32

sG=eval(io.recvline().decode("iso8859").strip().split("=")[1])
io.recvuntil(b"tG = ")

io.sendline(f"(0,{y})".encode())
io.sendline(payload)
print("[+] sG: ",sG)
share_=bytes.fromhex(io.recvline().decode("iso8859").strip())
xor_m=pad(b"\x00"*31,64)
share=xor(xor_m,share_)
ys=bytes_to_long(share)
s=discrete_log(p,ys,y)
print(s)
print(mul(s,G))
print(sG)
# If any byte of share equals to the the byte of payload in the same posiyion
# xor_m is not the above one , then just try again
# maybe I should add a `while` loop here.
assert sG==mul(s,G)
msg=xor(pad(b"flag",64),share)
print(msg)
io.sendline(msg.hex())


aes = AES.new(key=sha256(long_to_bytes(s)).digest(), mode=AES.MODE_ECB)
encflag=xor(bytes.fromhex(io.recvline().decode("iso8859").strip()),share)
print("encflag=",encflag)
encflag=unpad(encflag)
print(aes.decrypt(encflag))

OK

This is a standard 1-2 oblivious transfer with almost no vulnerability. We can’t get the two messages simultaneously and therefore we focus on recovering $encflag=m_0 \oplus m_1$ . This writeup is written by thiner ThinerDAS and roadicing of NeSE.

v = int(input("v: "))

k1 = pow(v - x1, d, n)
k2 = pow(v - x2, d, n)

print("c1 = {}".format((k1 + key) % n))
print("c2 = {}".format((k2 + ciphertext) % n))

We can easily observe that, if we set $v \equiv \frac{x_1 + x_2}{2}$ , then $k_1+k_2\equiv 0$ , so $c_1+c_2\equiv \text{key} + \text{ciphertext} \equiv \text{key} + (\text{key} \oplus \text{secret})$ , where secret := pow(flag, e, P).

(Note: since $d×e= k×(p-1)×(q-1)+1$ and the RHS of this equation is odd,we deduce that d must be odd number.)

Here we naturally ask the question: if we collect enough $x + (x \oplus s)$ , can we recover s?

The answer seems to be yes. By intuition we can find out, for each digit i, if s[i] is 1, then it only contributes 1 in this digit; otherwise in this digit it can contribute 0 or 2.

This intuition extends naturally for several digits.

def calc_distribution(k=4):
    # b = x + (x^a)
    # first dim: value of a
    # second dim: distribution of b
    dist = [{} for i in range(1 << k)]
    for a in range(1 << k):
        for x in range(1 << k):
            for c in range(2): # carry
                view1 = (x+(x ^ a)+c) & ((1 << k)-1)
                dist[a].setdefault(view1, 0)
                dist[a][view1] += 1
    return dist
>>> for i in calc_distribution(4): print(i)
... 
{0: 2, 1: 2, 2: 2, 3: 2, 4: 2, 5: 2, 6: 2, 7: 2, 8: 2, 9: 2, 10: 2, 11: 2, 12: 2, 13: 2, 14: 2, 15: 2}
{1: 4, 2: 4, 5: 4, 6: 4, 9: 4, 10: 4, 13: 4, 14: 4}
{2: 4, 3: 4, 4: 4, 5: 4, 10: 4, 11: 4, 12: 4, 13: 4}
{3: 8, 4: 8, 11: 8, 12: 8}
{4: 4, 5: 4, 6: 4, 7: 4, 8: 4, 9: 4, 10: 4, 11: 4}
{5: 8, 6: 8, 9: 8, 10: 8}
{6: 8, 7: 8, 8: 8, 9: 8}
{7: 16, 8: 16}
{8: 2, 9: 2, 10: 2, 11: 2, 12: 2, 13: 2, 14: 2, 15: 2, 0: 2, 1: 2, 2: 2, 3: 2, 4: 2, 5: 2, 6: 2, 7: 2}
{9: 4, 10: 4, 13: 4, 14: 4, 1: 4, 2: 4, 5: 4, 6: 4}
{10: 4, 11: 4, 12: 4, 13: 4, 2: 4, 3: 4, 4: 4, 5: 4}
{11: 8, 12: 8, 3: 8, 4: 8}
{12: 4, 13: 4, 14: 4, 15: 4, 0: 4, 1: 4, 2: 4, 3: 4}
{13: 8, 14: 8, 1: 8, 2: 8}
{14: 8, 15: 8, 0: 8, 1: 8}
{15: 16, 0: 16}

By experimenting we find out that, the more “1” digits the s have, the more likely the result is restricted to a small subset of numbers. So for a bit interval, we can count its statistics and easily find out what values of s are impossible to be here - for example, if we see a 14 appear in one of our samples, then this part in s cannot be 15 since 15 in s must entail either 15 or 0 here.

We can expect that as long as we have collected enough $x + (x \oplus s)$ , we can recover s. However, the case is different in this challenge, where we have $[x + (x \oplus s)] \text{ mod } N$ . Actually it is no different. We can guess the LSB of s. If we believe that the LSB for s is 0, then we will add N to all samples whose LSB is 1; if we believe that the LSB for s is 1, the same ways around. Therefore, we have divided the problem in this challenge into 2 sub-problems of $x + (x \oplus s)$ .

Now finally we handle the $x + (x \oplus s)$ . Here I did not investigate the gory detail of a perfect algorithm, and only used a heuristic way of determining the answer. For each bit of s, I look ahead 12 bits of samples and find the largest number that satisfy all the samples, and I take the LSB of the number to be the corresponding digit of s. The proof of concept is as follows:

import random

random.seed(42)


class Chal(object):
    def __init__(self):
        self.secret = random.randint(2**32, 2**999)

    def sample(self):
        N = random.randint(2**1023, 2**1024) | 1
        x = random.randint(2**32, N-99999)
        return (x+(x ^ self.secret)) % N, N


def calc_distribution(k=4):
    # b = x + (x^a)
    # first dim: value of a
    # second dim: distribution of b
    dist = [{} for i in range(1 << k)]
    for a in range(1 << k):
        for x in range(1 << k):
            for c in range(2):
                view1 = (x+(x ^ a)+c) & ((1 << k)-1)
                dist[a].setdefault(view1, 0)
                dist[a][view1] += 1
    return dist


NN = 64
KK = 12
dist = calc_distribution(KK)


def slide_window(samples, pos, width):
    return set([(i >> pos) & ((1 << width)-1) for i in samples])


def solve(chal):
    samples = [chal.sample() for i in range(NN)]
    sample1 = [i if i & 1 else i+N for i, N in samples]
    sample0 = [i if not i & 1 else i+N for i, N in samples]
    return solve_uni(sample0), solve_uni(sample1)


def solve_uni(samples):
    guess = 0
    step = 1
    width = KK
    for i in range(1005//step):
        window = slide_window(samples, i*step, width)
        x = max([i for i in range(len(dist)) if all(j in dist[i]
                                                    for j in window)])
        guess |= (x & ((1 << step)-1)) << (i*step)
    return guess


chal = Chal()
print(hex(chal.secret))
sv = solve(chal)
print(hex(sv[0]))
print(hex(sv[1]))
print(hex(sv[0] ^ chal.secret))
print(hex(sv[1] ^ chal.secret))

I am surprised to find out that NN=64 is enough to deduce s without error most of the time; NN=16 even seems to work.

Here is the final exp.py.