HITCON CTF 2015 Quals Crypto 200 poooooooow write-up

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......}