HITCON CTF 2015の予選にチームfuzzi3のメンバーとして参加して1問だけ解いた。
Crypto 200 poooooooow
問題サーバーに整数x
を投げると、x^flag mod p
を返してくる。p
は、
p = 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723
p-1
を素因数分解すると、
p-1 = 2 * 3^336 * 4759647095086827597559114855685975263112106458932414012998147177848303887783492510354911068366203455488902018600593880874117783509946030773587965941
となる。(msieveにp-1
をそのまま指定したらなぜか値が化けたので、(p-1)/2
を計算して渡した。何故だろう?)
指数の底を任意に指定できる場合、位数の小さな底を渡すと逆算が可能になるという問題がある。例えば、p-1
の位数は2((p-1)^2=1
となる)ので、x=p-1
とすると、x^flag
の値はflag
が偶数ならば1、奇数ならばp-1
となる。同様に、位数がk
の整数を底に指定すると、k
が総当たり可能な程度に小さければ、flag mod k
の値が分かる。
位数k
を持つ底が存在する条件は、p-1
が約数にk
を持つこと。この問題の場合は、k = 2, 3, 6, 9, …
などに対して、flag mod k
の値が分かる。最初は中国人の剰余定理を使うのかなと思い、小さな素因数が2と3しかないので、法が互いに素という中国人の剰余定理の条件を満たさなあと悩んでいた。よくよく考えてみると、flag mod 3^k
の値が分かっているときに、flag mod 3^(k+1)
の値を求めるのは簡単だった。
位数がk
の底の値(k乗根)は、離散対数などと違って大きな数字に対しても計算できるらしい。計算方法は分からないが、PARI/GPを使ったら出てきた。
(00:02) gp > p = 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723 %3 = 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723 (00:02) gp > for (i=0, 336, sqrtn(Mod(1,p), 3^i, &z); print(z)) 1 Mod(104014548352862869844938168699037346159667005020653232215280909315013887004134868071692786470598745196869723476863259041566021786143181633190908349324551845723794609926567304576385405504723391936863098403039412007235326783702521959959990403821231826220564014204004925465542563989453628264120514916708791295289, 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723) Mod(184652117342066002125654235724672107296479548524944232819111563903191006442841910870258588328187042859006937684077703029415354169137811839089174205147468046219075692488717893872876980963114118329358013489256502574078197180921037431791591430810377557558530731446903392174481754139833226637153091225821181459427, 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723) Mod(184703592399630395992436694563840651821345959648882665358650769365293715003098677483460150685414076439977481202237026725692730858348800757738575025587940041796479236394368440075581490376984436883703286883100998351356645756513111907638957133347344001275568620875776030118946807467426690617366314494522903230861, 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723) Mod(110911870833244863188457786643721493610784303513579129522393811396028723726659740858323669743224481525481653274103693005011435072682119191684346088511737934950819776631108869567490910585606931573400726494033281267128656345029354355593639402681259953259490212087559197723833793933264120796188614403292964375754, 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723) :
下記のコードで、x=3^k
に対してのflag mod x
が手に入る。前半のSHA-1の計算はブルートフォース防止の問題を解くため。
p = 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723 p3 = [1, 104014548352862869844938168699037346159667005020653232215280909315013887004134868071692786470598745196869723476863259041566021786143181633190908349324551845723794609926567304576385405504723391936863098403039412007235326783702521959959990403821231826220564014204004925465542563989453628264120514916708791295289, 60596460703939283816039205007643327134157148193137267625175827451053986819941320545425174147667596081382708012312681744811027758187030913123958296233100508255282449193369626634505358810006112813774496917212618041107392205938556674774459583844872217984025489695097001179157787176195328504655348838631849663942, 10441323002096004510770587886741164350611625346463303011098537719084211549367934812572712892322805795870488891233845379359846218253172487403746893055076258863370778801037982921324392236506419913883778765063307635117884863379930809028657037691697264628883957391135108525171201634495578625408183792572214453266, : ] from socket import * from time import * from hashlib import * s = socket(AF_INET, SOCK_STREAM) s.connect(("52.69.244.164", 9003)) sleep(1) t = s.recv(1024) print t prefix = t[99:99+11].replace(" ","").decode("hex") try: for a in range(32,256): for b in range(32,256): for c in range(32,256): for d in range(32,256): w = prefix+chr(a)+chr(b)+chr(c)+chr(d) if sha1(w).hexdigest()[:6]=="000000": raise except: pass for i in range(len(p3)): s.send("%s\n"%p3[i]) sleep(0.1) print "<%s>"%i, s.recv(10240)
あとは、返ってきた値からflag
を求めれば良い。
flag = 0 for i in range(1,len(p3)): for j in range(3): if pow(root3[i], flag+j*3**(i-1), p) == res[i]: flag += j*3**(i-1) print flag print ("%x"%flag).decode("hex")
hitcon{CBRT_cbrt_Cbrt_CbRt_cBrT_cBRT_RePeAt......}