ImaginaryCTF 2021 Writeup
Crypto全完まであと一問…。悔しいですね。
来週のCrypto CTFがあるので精進します。
Result
Writeup
Chicken Caesar Salad 50pts
I remember the good old days when Caesar ciphers were easy…
ファイル：chicken-caesar-salad.txt
ROT18でした。
ictf{wHen_dID_cAEseR_cIphERs_gEt_sO_hARd}
Flip Flops 100pts
Yesterday, Roo bought some new flip flops. Let's see how good at flopping you are.
nc chal.imaginaryctf.org 42011
ファイル：flop.py
DawgCTF 2021 writeup - Attack All Around
こちらと同じ、byte flipping attackですね。
100点問題で難易度高くね！？とひたすらビビっていました。案の定、以降の問題のレベルも高かったです。
from Crypto.Util.number import * from functools import reduce from operator import mul from itertools import combinations import sys import socket, struct, telnetlib # --- common funcs --- def sock(remoteip, remoteport): s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect((remoteip, remoteport)) return s, s.makefile('rw') def read_until(f, delim='\n'): data = '' while not data.endswith(delim): data += f.read(1) return data #HOSTはIPアドレスでも可 HOST, PORT = "chal.imaginaryctf.org", 42011 s, f = sock(HOST, PORT) print(read_until(f)) print(read_until(f,"solution: ")) sol = input("> ") s.send(sol.encode()+b"\n") for _ in range(25-8+1): print(read_until(f)) print(read_until(f,"'gimmeflag'.")) for _ in range(2): print(read_until(f)) print(read_until(f,"> ")) s.send(b"1\n") pt = "31"*48 print(read_until(f,"(in hex): ")) s.send(pt.encode()+b"\n") enc = read_until(f).strip() print("got mes:",enc) print(read_until(f,"'gimmeflag'.")) for _ in range(2): print(read_until(f)) print(read_until(f,"> ")) s.send(b"2\n") val = bytes_to_long(b"gimmeflag"+b"\x07"*7) pt0 = int("31"*16,16) ct1 = int(enc[:32],16) key = pt0^ct1 ppt0 = val^key ans0 = hex(ppt0)[2:] while len(ans0) < 32: ans0 = "0"+ans0 ans0 += enc[32:64] print(read_until(f,"(in hex): ")) s.send(ans0.encode()+b"\n") while True: print(read_until(f))
ictf{fl1p_fl0p_b1ts_fl1pped_b6731f96}
Rock Solid Algorithm 100pts
Something was the wrong size here...
ファイル：secure.txt
nが素因数分解できませんが、e=5と小さいです。Low public exponent attackなのだろう。
c+k×nに5乗根が存在するかどうかbrute forceして、flagを出します。
import gmpy2 from Crypto.Util.number import * n = 18718668654839418101060350414897678724581774081742102287908765212690862231899547405582997157020093499506177632395430572542600019258424947803591395926472246347413986531437177801754324606200243710836609694453888894668656807471052095014376204102474311740080044776201105722801365112971807912406879483156845216746137339614577267869908065296042390812575960639865867729920434603853708907147465162697098688239587320232595412227310236678367 e = 5 c = 4061448515799106340420739691775850071489215699577921072934942485890519294380069123037340174441242842518682390853378784679825023237216051766738593812159344136064529711265570171627670665806072255545198689928996413238102114126558579154343844959868438278433954975590137693439216155482228025380904377837299357044104373966173149290333194304831238889245126840666444234215617022142380016275718234640045049962318290976661640301222078289152 tmpc = c while True: m,ch = gmpy2.iroot(tmpc,e) if ch: print(long_to_bytes(int(m))) break tmpc += n
ictf{3_isnt_th3_0nly_sm4ll_3xp0n3nt}
Lines 150pts
Try to crack my unbreakable™ encryption! I based it off of the Diffie-Helman key exchange!
ファイル：lines.py, out.txt
複雑なことをしているようですが、sを求めるだけです。a, bは求める必要ありません。
enc_msg = s × msg mod p s = enc_msg × msg^(-1) mod p
これでsが求まりました。
enc_flag = s × flag mod p flag = enc_flag × s^(-1) mod p
これでflagも求められました。
p = (省略) encrypt_flag = (省略) encrypt_msg = (省略) msg = bytes_to_long(b":roocursion:") s = (inverse(msg,p)*encrypt_msg)%p flag = (encrypt_flag*inverse(s,p))%p print(long_to_bytes(flag))
これを深夜にやり、翌朝残りをやろうとしていました。
ictf{m0d_4r1th_ftw_1c963241}
New Technology 300pts
If it's not Windows New Technology, what else could NT stand for?
ファイル：new_technology.py
朝起きて、オリンピック見ながらのんびりやるかと思ったらもう既に解かれていました。
まあ、とりあえずやってみるかとコード読んでみたけど分からない…。複雑すぎる。
一日考えて分からなかったので、先に解いた方の解法見てみるとびっくり。
実験してみたらkey = pub * pubであることがわかった
未証明
そんなんあり！？と確かめてみたら、本当でした。とりあえず手元で動かしてみて色々試してみるってのは必要ですね。証明できたら、追記します。
ictf{Would_number_theory_be_new_technology?}
Roll it back 300pts
Once you figure out what this is doing, it could be a straight line to the finish.
ファイル：roll_it_back.py
こちらも先に解かれていた問題です。
itertoolsのislice, cycle, gmpy2のpopcountを調べるのが面倒で放置。けど他の問題も分からんし、と渋々調べてみたらそんなに難しくない。
isliceはリストにするような感じのもの。cycleはリストを無限に長くして、中身はサイクルする感じのもの(a[0], a[1], ... a[n-1], a[0], ...)。popcountは、引数が整数値でいくつbitが立っているか個数を返すものです。
ということで、この部分の逆関数を頑張って考えます。
for _ in range(421337): flag = (flag >> 1) | ((popcount(flag & T) & 1) << (l - 1))
flagを1bit右シフトしたものとpopcountの結果を(l-1)bits左シフトのORが次のflagになります。flagは常にl (=420)bits以下です。
なので、flagの420bit目が立っていたら、popcount( (前のflag) & T) が1になります。ORの左側の演算では必ず419bits以下になるからですね。flagの420bit目が立っていない場合、popcount( (前のflag) & T) が0になります。
次に、前のflagを1bit右シフトしているので、前のflagの最下位ビットが分かりません。しかし、popcountの条件がある、且つTは奇数なのでpopcountの結果は前のflagの最下位ビットに依存します。つまり、前のflagの最下位ビットが一意的に決まります。
このfor文の逆関数はこのようになります。
binf = bin(flag)[2:] for i in range(421337): if binf[0] == "1": # (popcount(flag & T) & 1) == 1 tmp_flag = binf[1:] if (popcount(int(tmp_flag+"1",2) & T) & 1) == 1: binf = binf[1:]+"1" else: assert (popcount(int(tmp_flag+"0",2) & T) & 1) == 1 binf = binf[1:]+"0" else: #assert flag.bit_length() == l-1 # (popcount(flag & T) & 1) == 0 tmp_flag = binf[1:] if (popcount(int(tmp_flag+"1",2) & T) & 1) == 0: binf = binf[1:]+"1" else: assert (popcount(int(tmp_flag+"0",2) & T) & 1) == 0 binf = binf[1:]+"0" #assert flag.bit_length() == l-1 #print(i, flag.bit_length()) assert len(binf) == l
Tの値がコードに書いてあるものをそのまま実行していいのか、それともfake_flagのところもちゃんと本物のflagにしないといけないのか判断が出来ず、先に解いたチームメイトにヒントをもらいました。自力じゃないです(笑)
ictf{I_did_not_have_linear_relations_with_that_LFSR}
Primetime 300pts
Alice and Bob are meeting up to watch TV, but they've neglected to invite Elise and Gamal! Elise and Gamal intercepted the network traffic between the two, and managed to extract an encrypted message. Can you help them figure out what TV show Alice and Bob will be watching, and when?
Wrap the decrypted message in the flag format before submitting.
ファイル：primetime.py, output.txt
この問題難しかった分、解けて嬉しかったです！
まず、Elementクラスを見ていきましょう。
class Element: def __init__(self, n): self.n = Element.reduce(n) def __str__(self): return str(self.n) def __add__(self, other): return Element(self.n*other.n) def __eq__(self, other): return self.n == other.n def __mul__(self, n): if type(n) == int: ret = Element(1) for c in "{:0128b}".format(n): ret += ret if c == '1': ret += self return ret if type(n) == Element: ret = Element(1) primelist = list(islice(primes(), ELEMENT_LEN)) for i, num in enumerate(primelist[::-1]): cnt = 0 temp = n.n while gcd(temp, num) > 1: cnt += 1 temp //= num for c in "{:08b}".format(cnt): ret += ret if c == '1': ret += self return ret @staticmethod def encode(b): assert len(b) <= ELEMENT_LEN ret = 1 for i, num in enumerate(primes()): if i >= len(b): return Element(ret) ret *= num**b[i] @staticmethod def reduce(n): if n == 0: return 0 primelist = list(islice(primes(), ELEMENT_LEN)) for i, num in enumerate(primelist): while n % (num**256) == 0: n //= num**256 if num != primelist[-1]: n *= primelist[i+1] return n
まず、genを生成したencodeを見ていきます。numには素数が小さいものから入っていきます。[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53] の16個ですね。(素数)bytes列bでのb[i]の積が返されます。
素因数分解するとこうなりました。
gen 53 116 47 112 43 95 41 114 37 48 31 43 29 97 23 114 19 51 17 110 13 51 11 103 7 95 5 51 3 104 2 43
(左側)右側という感じですね。
これを、乱数akey, bkeyでgenとの積を取ります。その積がapub, bpubとなり公開された値となります。
apubをgenで割ったらakeyが出るだろう、とapub%genを見てみると0じゃない。なんで？？？
Elementクラスでのmulを見てみましょう。
def __mul__(self, n): if type(n) == int: ret = Element(1) for c in "{:0128b}".format(n): ret += ret if c == '1': ret += self return ret
retにどんどんretを足したり、掛けられる数に該当するselfを足しています。では、addを見てみましょう。
def __add__(self, other): return Element(self.n*other.n)
なんとかけ算しています。足し算がかけ算になるのであったら、かけ算はべき乗になるのでは？と手元でやってみます。Element(23)×11とすると、2311が返ってきました。予想的中！
じゃあなぜ、apub%genが0でないのでしょう。途中でmodとかされているのかなと思ったら、initに罠が。なんと返す時にreduceを通しています。
@staticmethod def reduce(n): if n == 0: return 0 primelist = list(islice(primes(), ELEMENT_LEN)) for i, num in enumerate(primelist): while n % (num**256) == 0: n //= num**256 if num != primelist[-1]: n *= primelist[i+1] return n
先程の素数の指数が256を越えると、その次の素数の指数が1増えるようです。元の素数の指数は256減るようです。これが原因でした。
つまり、apubはgenのakey乗で、素因数分解して256乗を越えるものはreduce関数でごちゃごちゃさせられます。
途中で繰り上がりのようなものがあって、それを離散対数問題なんて解けるわけ…。ん？繰り上がり？
解法の鍵は繰り上がりでした！
gen, apub, bpubを素因数分解して、その指数を256進数に見立てます。先程のgenで考えると、2の指数が最下桁となりその値は43です。これが256を越えると、その一つ上の位3の指数部分に繰り上がります。また、一番大きい素数53の指数が256を越えた場合は、ただ指数%256になるだけです。つまり、mod 25616 ということです。
このように考えると、genを2乗するとこの256進数を2倍するだけです。つまり、(genの256進数方式) × akey = (apubの256進数方式) mod 25616 となり、akeyを簡単に求められます。
akey = (apubの256進数方式) × (genの256進数方式)^(-1) mod 256^16
これと同様にして、bkeyを求めます。
akey, bkeyが求められたので、sを求めます。これはprimetime.pyにある通りに実行すればOKです。
最後に、mを求めます。
ct及びsを先程と同様に256進数方式で計算します。
ct = m × s m = (ctの256進数方式) × (sの256進数方式)^(-1) mod 256^16
これでmが求まり、flagが出ました。
from Crypto.Util.number import * from itertools import islice from math import gcd from random import randint ELEMENT_LEN = 16 def primes(): num = 2 while True: prime = 1 for i in range(2, num): if num%i == 0: prime = 0 if prime: yield num num += 1 class Element: def __init__(self, n): self.n = Element.reduce(n) def __str__(self): return str(self.n) def __add__(self, other): return Element(self.n*other.n) def __eq__(self, other): return self.n == other.n def __mul__(self, n): if type(n) == int: ret = Element(1) for c in "{:0128b}".format(n): ret += ret if c == '1': ret += self return ret if type(n) == Element: ret = Element(1) primelist = list(islice(primes(), ELEMENT_LEN)) for i, num in enumerate(primelist[::-1]): cnt = 0 temp = n.n while gcd(temp, num) > 1: cnt += 1 temp //= num for c in "{:08b}".format(cnt): ret += ret if c == '1': ret += self return ret @staticmethod def encode(b): assert len(b) <= ELEMENT_LEN ret = 1 for i, num in enumerate(primes()): if i >= len(b): return Element(ret) ret *= num**b[i] @staticmethod def reduce(n): if n == 0: return 0 primelist = list(islice(primes(), ELEMENT_LEN)) for i, num in enumerate(primelist): while n % (num**256) == 0: n //= num**256 if num != primelist[-1]: n *= primelist[i+1] return n gen = (省略) apub = (省略) bpub = (省略) ct = (省略) Primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53] assert len(Primes) == 16 def frame(x): ret = [] for pri in Primes[::-1]: cnt = 0 while True: if x%pri == 0: cnt += 1 x //= pri else: break print(pri,cnt) ret.append(cnt) assert x == 1 return ret #gen, apub, bpubを素因数分解 print("gen") gg = frame(gen) print() print("apub") aa = frame(apub) print() print("bpub") bb = frame(bpub) #256進数方式で値にする Gen = 0 for G in gg: Gen *= 256 Gen += G print(Gen) Apub = 0 for A in aa: Apub *= 256 Apub += A Bpub = 0 for B in bb: Bpub *= 256 Bpub += B Gen_inv = inverse(Gen,pow(256,16)) assert (Gen_inv*Gen)%pow(256,16) == 1 #akey, bkeyを求める akey = (Apub*Gen_inv)%pow(256,16) bkey = (Bpub*Gen_inv)%pow(256,16) print(akey) print(bkey) gEn = Element.encode(b"+h3_g3n3ra+0r_pt") s = gEn*akey*bkey print(s) # sの値 S = (省略) ss = frame(S) print(ss) CT = frame(ct) print(CT) Ss = 0 for tmps in ss: Ss *= 256 Ss += tmps Ct = 0 for tmpct in CT: Ct *= 256 Ct += tmpct s_inv = inverse(Ss,pow(256,16)) assert (s_inv*Ss)%pow(256,16) == 1 m = Ct*s_inv print(m%pow(256,16)) print(long_to_bytes(m%pow(256,16))[::-1])
ictf{M1st3rRob0t_2045}
