読者です 読者をやめる 読者になる 読者になる

sonickun.log

備忘録

tkbctf4 Write-up rcrypto (cryptography200)

CTF セキュリティ

 tkbctfにチームm1z0r3として参加しました.結果は600点で71チーム中15位.自分が解いたのはrcryptoの1問だけでした.(つらい)
 javascriptの2問が解けそうで解けなかったのが悔しかったです.引き続き解いてみてWrite-upを書こうと思います.

rcrypto (cryptography200)

 encrypto.pyとresul.txtの2つのファイルが渡されます.

encrypto.py
import struct

N = 0xcd892c64f1803742a89e68567aea60283066b368d2c2454ad55f740fb0ff8e98e03f70cd9a2c9168294eee89a9f995d2596f2c0be881bfbfa72cccbb18a77287134e2ffc89e7bce766cca9136074a19f6807c3ff51e5cf53ec79838067cbefac809fccbbe2c1c4d170f3be58b34b9c3dfaeb2914341697d6503a826716073f9808b91c747030e2cdeaf20620b269c701d5ce96623c95c983678fd1175243b9eda7f6a310b4ccfd6c69fa836adb82271c56aa7ca267c1d47e64e69a0c3541f63432b4d75b881c1694a07b546eaee036521213967201cd91ff6a4e1e7c89027eb57096f2e3e5cd274d5cd272be44435b21648538f31760b4f8b50cbcd42f0873d5

def encrypt(M, B):
    return M * (M + B) % N

if __name__ == '__main__':
    s = open('flag', 'r').read()
    tkbctf = struct.unpack('<2I', 'tkbctf4\0')
    flag = int(s.encode('hex'), 16)
    print "1: %d" % encrypt(flag, tkbctf[0])
    print "2: %d" % encrypt(flag, tkbctf[1])
result.txt
1: 2302864379938375384787522457289953058762346515694717964988017701221632252068998721016780659512789645178039929483162432085291148128875938650563974652974607897108753247761759018159346471819526717450317624121005691577913298753406802656066710989103644069541226797561238591832001786871030959032526532824897381416113004865029523158041337929652792421367459253385313006702525506606665513325657107841851439410104118856833250549528309345600994438901026890993789031255524302387252820866177521016309668779564405438776186649089481716393902512049059686799788362854701624870108840227739233423565617147635810535089953364777452765391
2: 869821841437664579273841208702057334636310328092375384661895122870843280009327763942775667106913326453781559554453279690395959752854296081023254897131426262762124201024166059200347755016000992120349762030587256929453375758557293418778029046615012379759165445526510048231152939113590563355048407714266168812177988203610092674509339069396233061882191910214456155546393848777696938097852335164090584476493820466258280954729469300306911409684786367255431603152145902151223834708442564731418184393252984714050882676106734102146980036229108895568198263271905480015122766218776429803994468521463000793677542363327966917714


 encrypt.pyで暗号化された結果がresulet.txtに出力されています.暗号化前の平文がフラグになっているようです.
 暗号アルゴリズムは,平文(フラグ)をM,鍵をB,N,暗号文をRとすると

R = M * (M + B) (mod N)

 となっています.暗号化というよりハッシュっぽいですね.
 この式から単純にMを導くことは不可能ですが,今回はこの暗号化が以下のように2パターンあります.青字が既知の値で,赤字が未知の値です.

R1 = M * (M + B1) (mod N) ・・・①
R2 = M * (M + B2) (mod N) ・・・②

 この2式から未知の値Mを推定します.
 R1>R2かつB1>B2のとき,①式から②式を減算すると

R1 - R2 = M( B1 - B2 ) (mod N)

 が成り立ちます.(証明は省略)
 つまり

M( B1 - B2 ) - ( R1 - R2 ) = kN    (kは自然数)

⇒ M = {kN + ( R1 - R2)} / (B1-B2)

 となりM=の式が出来ます.この式において,Mが整数になるようにkをブルートフォースします.
 作成したスクリプトがこちら.

import struct

tkbctf = struct.unpack('<2I', 'tkbctf4\0')
t=tkbctf[0]-tkbctf[1]

R1=2302864379938375384787522457289953058762346515694717964988017701221632252068998721016780659512789645178039929483162432085291148128875938650563974652974607897108753247761759018159346471819526717450317624121005691577913298753406802656066710989103644069541226797561238591832001786871030959032526532824897381416113004865029523158041337929652792421367459253385313006702525506606665513325657107841851439410104118856833250549528309345600994438901026890993789031255524302387252820866177521016309668779564405438776186649089481716393902512049059686799788362854701624870108840227739233423565617147635810535089953364777452765391
R2=869821841437664579273841208702057334636310328092375384661895122870843280009327763942775667106913326453781559554453279690395959752854296081023254897131426262762124201024166059200347755016000992120349762030587256929453375758557293418778029046615012379759165445526510048231152939113590563355048407714266168812177988203610092674509339069396233061882191910214456155546393848777696938097852335164090584476493820466258280954729469300306911409684786367255431603152145902151223834708442564731418184393252984714050882676106734102146980036229108895568198263271905480015122766218776429803994468521463000793677542363327966917714
x=R1-R2

N=0xcd892c64f1803742a89e68567aea60283066b368d2c2454ad55f740fb0ff8e98e03f70cd9a2c9168294eee89a9f995d2596f2c0be881bfbfa72cccbb18a77287134e2ffc89e7bce766cca9136074a19f6807c3ff51e5cf53ec79838067cbefac809fccbbe2c1c4d170f3be58b34b9c3dfaeb2914341697d6503a826716073f9808b91c747030e2cdeaf20620b269c701d5ce96623c95c983678fd1175243b9eda7f6a310b4ccfd6c69fa836adb82271c56aa7ca267c1d47e64e69a0c3541f63432b4d75b881c1694a07b546eaee036521213967201cd91ff6a4e1e7c89027eb57096f2e3e5cd274d5cd272be44435b21648538f31760b4f8b50cbcd42f0873d5

k=1
while(1):
	if (k*N+x)%t==0:
		print (k*N+x)/t
		break
	else:
		k+=1
	print k
Result
k=569111799
M=8874284088105576854948238238614457044505028639011349374021861498995036023097152049555857239549350287166006347100199983957544356840501980854784901113821946197380611177705292212987004478484951309819182405098846767765333862409425926812573611864910204824928321142829182839508679805462040296761411851272619037561124670207800113160725445151643233355853069817035845548582628939322952705418085312089629008831113802005771457751200233715401850140367028206001736592528758851066145310031045563613680644635600425736132514865977264503188118025685603053077990165729300195014737832785024786331903041102248425142311946913492026078519

 計算に1時間以上かかりました.(途中何度諦めかけたことか・・・)
 きっともっと効率のいい解法があると思います.

 あとは得られたMをASCII文字に変換するだけ.

$ python
>>>a=8874284088105576854948238238614457044505028639011349374021861498995036023097152049555857239549350287166006347100199983957544356840501980854784901113821946197380611177705292212987004478484951309819182405098846767765333862409425926812573611864910204824928321142829182839508679805462040296761411851272619037561124670207800113160725445151643233355853069817035845548582628939322952705418085312089629008831113802005771457751200233715401850140367028206001736592528758851066145310031045563613680644635600425736132514865977264503188118025685603053077990165729300195014737832785024786331903041102248425142311946913492026078519
>>> s = hex(a)[2:]
>>> z=''
>>> for i in range(0, len(s), 2):
...   z += chr(int( (s[i]+s[i+1]), 16))
...
>>> z
'FLAG{R4b1n cryp705y573m 15 v3ry 1n73r3571ng!!!}FLAG{R4b1n cryp705y573m 15 v3ry 1n73r3571ng!!!}FLAG{R4b1n cryp705y573m 15 v3ry 1n73r3571ng!!!}FLAG{R4b1n cryp705y573m 15 v3ry 1n73r3571ng!!!}FLAG{R4b1n cryp705y573m 15 v3ry 1n73r3571ng!!!}FLAG{R4b1n cryp705y57'

 ということで,フラグはR4b1n cryp705y573m 15 v3ry 1n73r3571ng!!!でした.
 
 ほぼ数学の問題でした.