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  12345678910111213141516171819202122 from Crypto.Util.number import bytes_to_long, isPrimefrom secret import flag, p def encrypt(m, k, p): return pow(m, 1 << k, p) assert flag.startswith("TWCTF{")assert len(flag) == 42assert isPrime(p) k = 64pt = 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 cs 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.  1234567891011121314151617181920212223242526272829303132 ## Step 1 : Find any solutiondef 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 Forceres = 5602276430032875007249509644314357293319755912603737631044802989314683039473469151600643674831915676677562504743413434940280819915470852112137937963496770923674944514657123370759858913638782767380945111493317828235741160391407042689991007589804877919105123960837253705596164618906554015382923343311865102111160p = 6722156186149423473586056936189163112345526308304739592548269432948561498704906497631759731744824085311511299618196491816929603296108414569727189748975204102209646335725406551943711581704258725226874414399572244863268492324353927787818836752142254189928999592648333789131233670456465647924867060170327150559233ex = 1948865039294009691576181380771672389220382961994854292305692557649261763833149884145614983319207887860531232498119502026176334583810204964826290882842308810728384018930976243008464049012096415817825074466275128141940107121005470692979995184344972514864128534992403176506223940852066206954491827309484962494271assert pow(ex, 1 << 64 , p) == res def is_ascii(s): return all(c < 128 for c in s) gen = 3jp = 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()Colored by Color Scripter cs twin-d  1234567891011121314151617181920 require 'json'require 'openssl' p = OpenSSL::BN::generate_prime(1024).to_iq = 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) == 1end e1 = OpenSSL::BN.new(d).mod_inverse(OpenSSL::BN.new((p - 1) * (q - 1))).to_ie2 = 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 cs 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 :)  12345678910111213141516171819202122232425262728 n = 26524843197458127443771133945229625523754949369487014791599807627467226519111599787153382777120140612738257288082433176299499326592447109018282964262146097640978728687735075346441171264146957020277385391199481846763287915008056667746576399729177879290302450987806685085618443327429255304452228199990620148364422757098951306559334815707120477401429317136913170569164607984049390008219435634838332608692894777468452421086790570305857094650986635845598625452629832435775350210325954240744747531362581445612743502972321327204242178398155653455971801057422863549217930378414742792722104721392516098829240589964116113253433e1 = 3288342258818750594497789899280507988608009422632301901890863784763217616490701057613228052043090509927547686042501854377982072935093691324981837282735741669355268200192971934847782966333731663681875702538275775308496023428187962287009210326890218776373213535570853144732649365499644400757341574136352057674421661851071361132160580465606353235714126225246121979148071634839325793257419779891687075215244608092289326285092057290933330050466351755345025419017436852718353794641136454223794422184912845557812856838827270018279670751739019476000437382608054677808858153944204833144150494295177481906551158333784518167127e2 = 20586777123945902753490294897129768995688830255152547498458791228840609956344138109339907853963357359541404633422300744201016345576195555604505930482179414108021094847896856094422857747050686108352530347664803839802347635174893144994932647157839626260092064101372096750666679214484068961156588820385019879979501182685765627312099064118600537936317964839371569513285434610671748047822599856396277714859626710571781608350664514470335146001120348208741966215074474578729244549563565178792603028804198318917007000826819363089407804185394528341886863297204719881851691620496202698379571497376834290321022681400643083508905enc = 18719581313246346528221007858250620803088488607301313701590826442983941607809029805859628525891876064099979252513624998960822412974893002313208591462294684272954861105670518560956910898293761859372361017063600846481279095019009757152999533708737044666388054242961589273716178835651726686400826461459109341300219348927332096859088013848939302909121485953178179602997183289130409653008932258951903333059085283520324025705948839786487207249399025027249604682539137261225462015608695527914414053262360726764369412756336163681981689249905722741130346915738453436534240104046172205962351316149136700091558138836774987886046 cc = 2 * e1 * e2 + e2 - e1 tt = 0cv = ccwhile 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 = 177276401739167429751099686272064967069179029118915820763787396008698833618702905602522557760805466539182350759150950532254737829482867347218636052172454990031666206911810532732619372311183056810552780771197878348351916381506465238562588760944922289622011858546760490648690942678177540128777265354408766804279q = n // p phi = (p-1) * (q-1)d = inverse(e1, phi)print(long_to_bytes(pow(enc, d, n)))Colored by Color Scripter cs The Melancholy of Alice  1234567891011121314151617181920212223242526272829303132333435363738394041 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() Colored by Color Scripter cs 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.  123456789101112131415161718192021222324252627282930313233343536373839 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) Colored by Color Scripter cs XOR and shift encryptor  12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182 #!/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)) Colored by Color Scripter cs 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.  123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103 N = 64F = 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) Colored by Color Scripter cs circular  123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657 ## 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 * qFile.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_ik = 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" endend Colored by Color Scripter cs 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.

 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091 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 = 25299128324054183472341067223932160732879350179758036557232544635970111090474692853470743347443422497121006796606102551210094872253782062717537548880909979729182337501587763866901367212812697076494080678616385493076865655574412317879297160790121009524506015912113098690685202868184636344610142590510988192306870694667596904330867479578103616304053889409982447653859514868824002960431331342963562137691362725961627846051021103954795862501700267818317148154520620016172888281127685503677751830350686839873220480306266506898497203511851305686566444690384065880667273398255172752236076702247451872387522388546088290187449k = 31019613858513746556266176233462864650379070310554671955689986199007361221356361736128815989480106678809272137963430923820800280374078610631771089089882153619351592434728588050285853284795554255483472955286848474793299446184220594124878818081534965835159741218233013815338595300394855159744354636541274026478456851924371621879725248093305782590590080796638483359868136648681381332610536250576568502512250581068814961097404403694071264894656697723213779631364079010490113719021172301802643377777927176399460547584115127172190000090756708138720022664973312744713394243720961199400948876916817452969615149776530401604593 % ngoal = 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)Colored by Color Scripter cs

#### 'CTF' 카테고리의 다른 글

SECCON 2020 OnlineCTF Crypto Write-Ups  (0) 2020.10.11 2020.09.30 2020.09.19 2020.09.06 2020.08.16