TokyoWesternCTF 2020 Crypto Write-Ups

I participated in TWCTF 2020 as a member of the team D0G$. We got 1st place!

easy hash

I tried to do something but then @yoshiking sensei solved it. :D

sqrt

from Crypto.Util.number import bytes_to_long, isPrime
from secret import flag, p
 
 
def encrypt(m, k, p):
    return pow(m, 1 << k, p)
 
 
assert flag.startswith("TWCTF{")
assert len(flag) == 42
assert isPrime(p)
 
k = 64
pt = bytes_to_long(flag.encode())
ct = encrypt(pt, k, p)
 
with open("output.txt", "w") as f:
    f.write(str(ct) + "\n")
    f.write(str(p) + "\n")
 
# 5602276430032875007249509644314357293319755912603737631044802989314683039473469151600643674831915676677562504743413434940280819915470852112137937963496770923674944514657123370759858913638782767380945111493317828235741160391407042689991007589804877919105123960837253705596164618906554015382923343311865102111160
# 6722156186149423473586056936189163112345526308304739592548269432948561498704906497631759731744824085311511299618196491816929603296108414569727189748975204102209646335725406551943711581704258725226874414399572244863268492324353927787818836752142254189928999592648333789131233670456465647924867060170327150559233

So we are given $m^{2^{64}} \pmod{p}$ and $p$. We need to find $m$. The first thing we note is that $\nu_2 (p-1) = 30$. Therefore, we have $\text{gcd}(2^{64}, p-1) = 2^{30}$ possibilities for $m$, if we disregard the length and "TWCTF{" condition. This is a large number of solutions, but it's not impossible to brute force. We first find any solution of $m^{2^{64}} \equiv enc \pmod{p}$ by repeated usage of Tonelli-Shanks. Now, we may write all solutions as $m \cdot g^{(p-1)/2^{30} \cdot k}$, where $g$ is some generator easily found by Sage. We go over each solution, check if it's small enough to be a candidate first (optimization), then convert it to bytes and see if it meets the desired conditions. 

It was estimated to run in ~1.5 hours in my computer, so I asked for some computational help. 

@theoldmoon0602 and @ironore15 were kind enough to help me in this brute force.

## Step 1 : Find any solution
def gogo(r, d, m):
    if d == 0:
        print(r)
        exit()
        return
    u = tonelli(m, r)
    if u == -1:
        return
    gogo(u, d-1, m)
    gogo((m-u)%m, d-1, m)
 
 
## Step 2 : Start Brute Force
res = 5602276430032875007249509644314357293319755912603737631044802989314683039473469151600643674831915676677562504743413434940280819915470852112137937963496770923674944514657123370759858913638782767380945111493317828235741160391407042689991007589804877919105123960837253705596164618906554015382923343311865102111160
p = 6722156186149423473586056936189163112345526308304739592548269432948561498704906497631759731744824085311511299618196491816929603296108414569727189748975204102209646335725406551943711581704258725226874414399572244863268492324353927787818836752142254189928999592648333789131233670456465647924867060170327150559233
ex = 1948865039294009691576181380771672389220382961994854292305692557649261763833149884145614983319207887860531232498119502026176334583810204964826290882842308810728384018930976243008464049012096415817825074466275128141940107121005470692979995184344972514864128534992403176506223940852066206954491827309484962494271
assert pow(ex, 1 << 64 , p) == res
 
def is_ascii(s):
    return all(c < 128 for c in s)
 
gen = 3
jp = pow(3, (p-1) // (2 ** 30), p)
 
for i in tqdm(range(0, 2**30)):
    ex = (ex * jp) % p
    if ex.bit_length() <= 400:
        u = long_to_bytes(ex)
        if is_ascii(u) and b"TWCTF{" in u:
            print(u)
            exit()

 

twin-d

require 'json'
require 'openssl'
 
p = OpenSSL::BN::generate_prime(1024).to_i
q = OpenSSL::BN::generate_prime(1024).to_i
 
while true
    d = OpenSSL::BN::generate_prime(1024).to_i
    break if ((p - 1) * (q - 1)).gcd(d) == 1 && ((p - 1) * (q - 1)).gcd(d + 2) == 1
end
 
e1 = OpenSSL::BN.new(d).mod_inverse(OpenSSL::BN.new((p - 1) * (q - 1))).to_i
e2 = OpenSSL::BN.new(d + 2).mod_inverse(OpenSSL::BN.new((p - 1) * (q - 1))).to_i
 
flag = File.read('flag.txt')
msg = OpenSSL::BN.new(flag.unpack1("H*").to_i(16))
n = OpenSSL::BN.new(p * q)
enc = msg.mod_exp(OpenSSL::BN.new(e1), n)
 
puts ({ n: (p*q).to_s, e1: e1.to_s, e2: e2.to_s, enc: enc.to_s }).to_json

So we have $e_1, e_2$ corresponding to $d_1, d_2$, which have a difference of $2$.

Basically what this says is that $e_2^{-1} - e_1^{-1} \equiv 2 \pmod{\phi(n)}$. Therefore, we can simply write $e_1-e_2 \equiv 2e_1e_2 \pmod{n}$. 

This implies that $2e_1e_2 + e_2 - e_1$ is a multiple of $\phi(n)$. It is very well-known fact that given $n$ and a multiple of $\phi(n)$, we can factorize $n$. So apply that method to factorize $n$. The rest is basic RSA. Happy to get first solve :)

n = 26524843197458127443771133945229625523754949369487014791599807627467226519111599787153382777120140612738257288082433176299499326592447109018282964262146097640978728687735075346441171264146957020277385391199481846763287915008056667746576399729177879290302450987806685085618443327429255304452228199990620148364422757098951306559334815707120477401429317136913170569164607984049390008219435634838332608692894777468452421086790570305857094650986635845598625452629832435775350210325954240744747531362581445612743502972321327204242178398155653455971801057422863549217930378414742792722104721392516098829240589964116113253433
e1 = 3288342258818750594497789899280507988608009422632301901890863784763217616490701057613228052043090509927547686042501854377982072935093691324981837282735741669355268200192971934847782966333731663681875702538275775308496023428187962287009210326890218776373213535570853144732649365499644400757341574136352057674421661851071361132160580465606353235714126225246121979148071634839325793257419779891687075215244608092289326285092057290933330050466351755345025419017436852718353794641136454223794422184912845557812856838827270018279670751739019476000437382608054677808858153944204833144150494295177481906551158333784518167127
e2 = 20586777123945902753490294897129768995688830255152547498458791228840609956344138109339907853963357359541404633422300744201016345576195555604505930482179414108021094847896856094422857747050686108352530347664803839802347635174893144994932647157839626260092064101372096750666679214484068961156588820385019879979501182685765627312099064118600537936317964839371569513285434610671748047822599856396277714859626710571781608350664514470335146001120348208741966215074474578729244549563565178792603028804198318917007000826819363089407804185394528341886863297204719881851691620496202698379571497376834290321022681400643083508905
enc = 18719581313246346528221007858250620803088488607301313701590826442983941607809029805859628525891876064099979252513624998960822412974893002313208591462294684272954861105670518560956910898293761859372361017063600846481279095019009757152999533708737044666388054242961589273716178835651726686400826461459109341300219348927332096859088013848939302909121485953178179602997183289130409653008932258951903333059085283520324025705948839786487207249399025027249604682539137261225462015608695527914414053262360726764369412756336163681981689249905722741130346915738453436534240104046172205962351316149136700091558138836774987886046
 
cc = 2 * e1 * e2 + e2 - e1
 
tt = 0
cv = cc
while cv % 2 == 0:
    cv //= 2
    tt += 1
 
for i in range(3, 100):
    t = pow(i, cv, n)
    for j in range(0, tt):
        g = GCD(t-1, n)
        if g != 1 and g != n:
            print(g) ## this is p
            exit()
        t = (t * t) % n
 
p = 177276401739167429751099686272064967069179029118915820763787396008698833618702905602522557760805466539182350759150950532254737829482867347218636052172454990031666206911810532732619372311183056810552780771197878348351916381506465238562588760944922289622011858546760490648690942678177540128777265354408766804279
q = n // p
 
phi = (p-1) * (q-1)
d = inverse(e1, phi)
print(long_to_bytes(pow(enc, d, n)))

The Melancholy of Alice

from Crypto.Util.number import getStrongPrime, getRandomRange
 
N = 1024
 
def generateKey():
    p = getStrongPrime(N)
    q = (p - 1) // 2
    x = getRandomRange(2, q)
    g = 2
    h = pow(g, x, p)
    pk = (p, q, g, h)
    sk = x
    return (pk, sk)
 
def encrypt(m, pk):
    (p, q, g, h) = pk
    r = getRandomRange(2, q)
    c1 = pow(g, r, p)
    c2 = m * pow(h, r, p) % p
    return (c1, c2)
 
def main():
    with open("flag.txt") as f:
        flag = f.read().strip()
 
    pk, sk = generateKey()
    with open("publickey.txt", "w") as f:
        f.write(f"p = {pk[0]}\n")
        f.write(f"q = {pk[1]}\n")
        f.write(f"g = {pk[2]}\n")
        f.write(f"h = {pk[3]}\n")
 
    with open("ciphertext.txt", "w") as f:
        for m in flag:
            c = encrypt(ord(m), pk)
            f.write(f"{c}\n")
 
 
if __name__ == "__main__":
    main()
 

I had good fun solving this problem, so I'll write my thought process as well. 

This honestly looks like a perfect code, but the key line that left a question mark for me was line 35. 

$ord(m)$ is incredibly small, so maybe we can bypass the entire discrete logarithm?

To think further in this direction, we need some knowledge on $p-1$. I first checked if $q$ was prime - it was not.

Then I checked the factors of $q$ - I could brute force small primes, but I just went to FactorDB. Why not?

I found out that $3, 5, 19$ were factors of $q$, which was quite surprising to me.

I thought StrongPrimes generated a prime of a form $2 \cdot q + 1$ where $q$ is a prime. Oops?

Anyways, since $3 \cdot 5 \cdot 19$ was pretty large, so it seems this should be fine.

Discrete Logarithm calculation is hard, but calculation modulo a small prime is easy by Pohlig-Hellman style thinking.

Can we abuse this? Well, given the signature data we can calculate the logarithm of the $ord(m)$ modulo $3 \cdot 5 \cdot 19$.

So if we precompute all logarithms of 0 to 255 modulo $3 \cdot 5 \cdot 19$, we can find the "candidates" for each letter.

I did this, but found there are multiple solutions. I tried to fix this by working with $5710354319$, which is another prime divisor.

I thought this should also work using sage's BSGS and stuff, but it was way too slow.

I posted my partial result (candidates) on discord and asked for guesswork/recovery, then @yoshiking found the solution.

def crt(a, b):
    u, v = 0, 1
    for i in range(len(a)):
        u, v = CRT(u, v, a[i], b[i])
    return u
 
def get_DL(x, pr):
    gg = pow(x, (p-1) // pr, p)
    for i in range(0, pr):
        gt = pow(g, i * (p-1) // pr, p)
        if gt == gg:
            return i
 
def get_DLs(x):
    p_1 = get_DL(x, 3)
    p_2 = get_DL(x, 5)
    p_3 = get_DL(x, 19)
    return crt([p_1, p_2, p_3], [3, 5, 19])
 
cc = [-1]
for i in range(1, 255):
    cc.append(get_DLs(i))
 
xx = get_DLs(h)
 
res = []
fin = []
fom = ""
for x, y in res:
    s = ""
    u = get_DLs(x)
    v = get_DLs(y)
    ## v = xx * u + get_DLs(desire)
    res = (v - xx * u) % (3 * 5 * 19)
    for j in range(0, 255):
        if cc[j] == res and j <= 128:
            s += chr(j)
    print(s)
 

XOR and shift encryptor

#!/usr/bin/python3
 
s = []
p = 0
 
def init():
  global s,p
  s = [i for i in range(0,64)]
  p = 0
  return
 
def randgen():
  global s,p
  a = 3
  b = 13
  c = 37
  s0 = s[p]
  p = (p + 1) & 63
  s1 = s[p]
  res = (s0 + s1) & ((1<<64)-1)
  s1 ^= (s1 << a) & ((1<<64)-1)
  s[p] = (s1 ^ s0 ^ (s1 >> b) ^ (s0 >> c))  & ((1<<64)-1)
  return res
 
def jump(to):
 
  # Deleted...
 
  return
 
def check_jump():
  init()
  jump(10000)
  assert randgen() == 7239098760540678124
 
  init()
  jump(100000)
  assert randgen() == 17366362210940280642
 
  init()
  jump(1000000)
  assert randgen() == 13353821705405689004
 
  init()
  jump(10000000)
  assert randgen() == 1441702120537313559
 
  init()
  for a in range(31337):randgen()
  for a in range(1234567):randgen()
  buf = randgen()
  for a in range(7890123):randgen()
  buf2 = randgen()
  init()
  jump(31337+1234567)
  print (buf == randgen())  
  jump(7890123)
  print (buf2 == randgen())
 
check_jump()
 
init()
for a in range(31337):randgen()
 
flag = open("flag.txt").read()
assert len(flag) == 256
 
enc = b""
 
for x in range(len(flag)):
  buf = randgen()
  sh = x//2
  if sh > 64:sh = 64
  mask = (1 << sh) - 1
  buf &= mask
  jump(buf)
  enc += bytes([ ord(flag[x]) ^ (randgen() & 0xff) ])
  print ("%r" % enc)
 
open("enc.dat","wb").write(bytearray(enc))
 
 

So basically what we have to do is efficiently "advance" the RNG large amount of times. 

The given RNG state transition can be regarded as a linear transformation over the $64^2$ bits in the state.

Therefore, we can model this by matrix multiplication, where the size of the matrix is $64^2$. 

Using binary exponentiation, we can get our random numbers relatively quickly.

I had thought of this but believed this would be way too slow, but @theoldmoon0602 wrote a beautiful code in sage and managed to find the flag. The code took about 30 minutes ~ 1 hour to run, according to the solver. 

The below code, by @theoldmoon0602, derives the key sequence. 

Also, for the write-up written by the actual solver @theoldmoon0602, check here.

N = 64
F = GF(2)
 
def L(n):
  m = [[0 for x in range(N)] for y in range(N)]
 
  for i in range(N - n):
    m[i + n][i] = 1
 
  return matrix(F, m)
 
def R(n):
  m = [[0 for x in range(N)] for y in range(N)]
 
  for i in range(N - n):
    m[i][i + n] = 1
 
  return matrix(F, m)
 
 
def I():
  m = [[0 for x in range(N)] for y in range(N)]
 
  for i in range(N):
    m[i][i] = 1
 
  return matrix(F, m)
 
def O():
  m = [[0 for x in range(N)] for y in range(N)]
  return matrix(F, m)
 
def genM():
  a = 3
  b = 13
  c = 37
 
  o = O()
  i = I()
  la = L(a)
  rb = R(b)
  rc = R(c)
 
  blocks = [
    [i + rc, i + la + rb + la*rb] + [o for _ in range(62)]
  ]
  for j in range(1, N):
    row = [o for _ in range(N)]
    row[(j+1) % N] = i
    blocks.append(row)
 
  M = block_matrix(F, [*zip(*blocks)])
 
  return M
 
def initial_state():
  s = "".join(["{:064b}".format(i) for i in range(N)])
  vec = []
  for c in s:
    vec.append(F(int(c)))
  return Matrix(F, vec)
 
def getvalue(row, index):
  v = 0
  for i in range(N):
    v = v*2 + int(row[0][index*N + i])
  return v
 
def dumpstate(a):
  xs = []
  for i in range(N):
    xs.append(getvalue(a, i))
  print(xs)
 
s = initial_state()
M = genM()
 
def init():
  global s, M
  s = initial_state()
  M = genM()
 
def randgen():
  global s, M
  res = (getvalue(s, 0) + getvalue(s, 1)) % ((1<<64)-1)
  s = s * M
  return res
 
def jump(n):
  global s,M
  s = s * (M^n)
 
init()
jump(31337)
for x in range(256):
  buf = randgen()
  sh = x//2
  if sh > 64:sh = 64
  mask = (1 << sh) - 1
  buf &= mask
  jump(buf)
  print(randgen() & 0xff) 
 

circular

## keygen
 
require "openssl"
require "json"
 
p = OpenSSL::BN.generate_prime(1024)
q = OpenSSL::BN.generate_prime(1024)
k = OpenSSL::BN.generate_prime(2048, false)
n = p * q
File.write("pubkey.txt", { n: n.to_s, k: k.to_s }.to_json)
 
## interaction
 
require "functions_framework"
require "digest/sha2"
 
fail unless ENV["FLAG"]
 
key = JSON.parse(File.read("pubkey.txt"))
n = key["n"].to_i
k = key["k"].to_i
 
EXPECTED_MESSAGE = 'SUNSHINE RHYTHM'
 
FunctionsFramework.http("index") do |request|
  if request.request_method != "POST"
    return "Bad Request"
  end
 
  data = JSON.parse(request.body.read)
  cmd = data["cmd"]
  if cmd == "pubkey"
    return { pubkey: { n: n.to_s, k: k.to_s } }
  elsif cmd == "verify"
    x = data["x"].to_i
    y = data["y"].to_i
    msg = data["msg"].to_s
    hash = ""
    4.times do |i|
      hash += Digest::SHA512.hexdigest(msg + i.to_s)
    end
    hash = hash.to_i(16) % n
    signature = (x ** 2 + k * y ** 2) % n
 
    if signature == hash
      if msg == EXPECTED_MESSAGE
        return { result: ENV["FLAG"] }
      end
      return { result: "verify success" }
    else
      return { result: "verify failed" }
    end
  else
    return "invalid command"
  end
end
 

Basically, we have to find $x, y$ such that $x^2 + ky^2 \equiv HASH \pmod{n}$. 

We know $k, HASH, n$, but not the factorization of $n$. This seemed to be very difficult. 

First few ideas of mine included the Brahmagupta's Identity and Pell's Equation. 

I tried to work on Pell's Equation + continued fractions, but it failed as well.

After a while, @ironore15 notified us that this scheme has a name - OSS signature.

I was quite surprised because I didn't think this would be an actual scheme in the literature.

Anyways, after a bit of googling I was able to find a paper that describes the attack.

The rest was relatively straightforward implementation. I was glad to see one of my ideas used in the attack.

def comb(x1, y1, x2, y2, k, n):
    return (x1 * x2 + k * y1 * y2) % n, (x1 * y2 - x2 * y1) % n
 
def solve(k, m, n): ## solve x^2 + ky^2 == m mod n
    print("solve", k, m, n)
    fu = kthp(m, 2)
    if fu * fu == m:
        return (fu, 0)
    if k < 0:
        se = kthp(-k, 2)
        if se * se == -k:
            retx = (m+1) * inverse(2, n) % n 
            rety = (m-1) * inverse(2 * se, n) % n
            return retx, rety
    if m == 1:
        return (1, 0)
    if m == k % n:
        return (0, 1)
    while True:
        u = random.getrandbits(1024)
        v = random.getrandbits(1024)
        m_0 = (m * (u * u + k * v * v)) % n
        if isPrime(m_0):
            if GCD(m_0, n) != 1:
                print("LOL", m_0)
                exit()
            x_0 = tonelli(m_0, (-k) % m_0)
            if (x_0 * x_0 + k) % m_0 == 0:
                break
    ms = [m_0]
    xs = [x_0]
    sz = 1
    while True:
        new_m = (xs[sz-1] * xs[sz-1] + k) // ms[sz-1]
        ms.append(new_m)
        if k > 0 and xs[sz-1] <= ms[sz] <= ms[sz-1]:
            sz = sz + 1
            break
        if k < 0 and abs(ms[sz]) <= kthp(abs(k), 2):
            sz = sz + 1
            break
        xs.append(min(xs[sz-1] % ms[sz], ms[sz] - (xs[sz-1] % ms[sz])))
        sz = sz + 1
    assert sz == len(ms)
    assert sz - 1 == len(xs)
    uu, vv = xs[0], 1
    dv = 1
    for i in range(1, sz-1):
        assert (xs[i] ** 2 + k) % n == (ms[i] * ms[i+1]) % n
        uu, vv = comb(uu, vv, xs[i], 1, k, n)
        dv = (dv * ms[i]) % n
    dv = (dv * ms[sz-1]) % n
    uu = (uu * inverse(dv, n)) % n 
    vv = (vv * inverse(dv, n)) % n
    X, Y = solve(-ms[sz-1], (-k) % n, n)
    soly = inverse(Y, n)
    solx = (X * soly) % n
    finx, finy = comb(solx, soly, uu, vv, k, n)
    godx = ((finx * u - k * finy * v) * inverse(u * u + k * v * v, n)) % n
    gody = ((finx * v + finy * u) * inverse(u * u + k * v * v, n)) % n
    return godx, gody
 
msg = 'SUNSHINE RHYTHM'
hsh = ''
 
for i in range(0, 4):
    cc = msg + chr(ord('0') + i)
    hsh += hashlib.sha512(cc.encode()).hexdigest()
 
request = {
    'cmd': 'pubkey'
}
X = web_request('POST', 'https://crypto02.chal.ctf.westerns.tokyo', request, False)
 
 
n = 25299128324054183472341067223932160732879350179758036557232544635970111090474692853470743347443422497121006796606102551210094872253782062717537548880909979729182337501587763866901367212812697076494080678616385493076865655574412317879297160790121009524506015912113098690685202868184636344610142590510988192306870694667596904330867479578103616304053889409982447653859514868824002960431331342963562137691362725961627846051021103954795862501700267818317148154520620016172888281127685503677751830350686839873220480306266506898497203511851305686566444690384065880667273398255172752236076702247451872387522388546088290187449
k = 31019613858513746556266176233462864650379070310554671955689986199007361221356361736128815989480106678809272137963430923820800280374078610631771089089882153619351592434728588050285853284795554255483472955286848474793299446184220594124878818081534965835159741218233013815338595300394855159744354636541274026478456851924371621879725248093305782590590080796638483359868136648681381332610536250576568502512250581068814961097404403694071264894656697723213779631364079010490113719021172301802643377777927176399460547584115127172190000090756708138720022664973312744713394243720961199400948876916817452969615149776530401604593 % n
goal = int(hsh, 16) % n 
 
x, y = solve(k, goal, n)
print((x * x + k * y *y - goal) % n)
 
request = {
    'cmd': 'verify',
    'x': str(x),
    'y': str(y),
    'msg': msg
}
 
X = web_request('POST', 'https://crypto02.chal.ctf.westerns.tokyo', request, False)
print(X)