setodaNoteCTF Writeup [Crypto]
Crypto
base64
base64 decodeするだけ
ZmxhZ3tJdCdzX2NhbGxlZF9iYXNlNjQhfQ==
ROT13
ROT13するだけ
synt{Rira_lbh_Oehghf?}
pui_pui
以下の文字列が与えられる
\x41\x3a\x44\x6f\x20\x79\x6f\x75\x20\x6b\x6e\x6f\x77\x20\x4d\x6f\x6c\x63\x61\x72\x3f\x0a\x0a\x42\x3a\x4f\x66\x20\x63\x6f\x75\x72\x73\x65\x21\x20\x49\x20\x6c\x6f\x76\x65\x20\x74\x68\x65\x20\x73\x63\x65\x6e\x65\x20\x77\x68\x65\x72\x65\x20\x68\x65\x20\x73\x69\x6e\x6b\x73\x20\x69\x6e\x74\x6f\x20\x74\x68\x65\x20\x62\x6c\x61\x73\x74\x20\x66\x75\x72\x6e\x61\x63\x65\x20\x77\x68\x69\x6c\x65\x20\x67\x69\x76\x69\x6e\x67\x20\x74\x68\x65\x20\x74\x68\x75\x6d\x62\x73\x20\x75\x70\x2e\x0a\x0a\x41\x3a\x2e\x2e\x2e\x20\x57\x68\x61\x74\x3f\x0a\x0a\x42\x3a\x62\x74\x77\x2c\x20\x74\x68\x65\x20\x66\x6c\x61\x67\x20\x69\x73\x20\x66\x6c\x61\x67\x7b\x48\x61\x76\x65\x5f\x79\x6f\x75\x5f\x65\x76\x65\x72\x5f\x68\x65\x61\x72\x64\x5f\x6f\x66\x5f\x48\x65\x78\x64\x75\x6d\x70\x3f\x7d\x2e\x0a
謎の会話とflagがでてくる
A:Do you know Molcar? B:Of course! I love the scene where he sinks into the blast furnace while giving the thumbs up. A:... What? B:btw, the flag is flag{Have_you_ever_heard_of_Hexdump?}.
tkys_secret_service
問題文をROT13してみるとThe~となる
The priteftoiu ic Ciutrilled Uuflazzocoed Iucirmatoiu (CUI) rezodeut ou uiucederal zyztemz aud irgauosatoiuz oz ic paraminut ompirtaufe ti cederal ageufoez aud fau doreftly ompaft the aboloty ic the cederal giverumeut ti znffezzcnlly fiudnft otz ezzeutoal mozzoiuz aud cnuftoiuz. Thoz pnblofatoiu privodez ageufoez woth refimmeuded zefnroty reqnoremeutz cir priteftoug the fiucodeutoaloty ic CUI wheu the oucirmatoiu oz rezodeut ou uiucederal zyztemz aud irgauosatoiuz; wheu the uiucederal irgauosatoiu oz uit filleftoug ir maoutaououg oucirmatoiu iu behalc ic a cederal ageufy ir nzoug ir iperatoug a zyztem iu behalc ic au ageufy; aud where there are ui zpefocof zacegnardoug reqnoremeutz cir priteftoug the fiucodeutoaloty ic Flag oz clag{pnopno_far_ic_mil} CUI prezfrobed by the anthirosoug law, regnlatoiu, ir giverumeutwode pilofy cir the CUI fategiry lozted ou the CUI Regoztry. The reqnoremeutz apply ti all fimpiueutz ic uiucederal zyztemz aud irgauosatoiuz that prifezz, ztire, aud/ir trauzmot CUI, ir that privode priteftoiu cir znfh fimpiueutz. The zefnroty reqnoremeutz are outeuded cir nze by cederal ageufoez ou fiutraftnal vehoflez ir ither agreemeutz eztablozhed betweeu thize ageufoez aud uiucederal irgauosatoiuz.
Flagの文字列がある
Flag oz clag{pnopno_far_ic_mil}
Flag is flag{~}にみえる
一部の文字を入れ替えるのか
o -> i
z -> s
c -> f
flag{pnipni_far_if_mil}
だめ
英単語と仮定して法則を見つける
aud -> and
u -> n
aud/ir -> and/or
privode -> provide
i -> o
flag{pnipni_far_of_mol}
まだだめ
agreemeutz -> agreements
z -> s
Uuflazzocoed -> Unclassified
f -> c?
大文字はそのまま?
モルカーっぽい
n -> u
lets_bake
150
あなたはシェフ帽の人物からレシピを受け取りました。どうやら組織からの秘密のメッセージのようです。 レシピを解読し、秘密のメッセージを入手してください。 Input: NzRmNDRiMWE0Y2M2ZGNiNzc3NTMyNTcwZjk0MTE4NTMyNTcxZjE1YTE1NTJkY2M0 Recipe: RnJvbV9CYXNlNjQoJ0EtWmEtejAtOSsvPScsdHJ1ZSkN]b2[sRnJvbV9IZXgoJ05vbmUnKQ0=]b2[sRm9yaygnJScsJ18nLGZhbHNlKQ0=]b2[sUkM0KHsnb3B0aW9uJzonVVRGOCcsJ3N0cmluZyc6J2NoZWYnfSwnTGF0aW4xJywnTGF0aW4xJyk=
問題文からサイバーシェフを使うとわかる
Recipeをどう解読するのか非常に苦戦したが、以下のように区切り、
それぞれBASE64デコードしたらうまくいった
RnJvbV9CYXNlNjQoJ0EtWmEtejAtOSsvPScsdHJ1ZSkN]b2[s RnJvbV9IZXgoJ05vbmUnKQ0=]b2[s Rm9yaygnJScsJ18nLGZhbHNlKQ0=]b2[s UkM0KHsnb3B0aW9uJzonVVRGOCcsJ3N0cmluZyc6J2NoZWYnfSwnTGF0aW4xJywnTGF0aW4xJyk=
↓BASE64デコード
From_Base64('A-Za-z0-9+/=',true) ok From_Hex('None') ok Fork('%','_',false) ok RC4({'option':'UTF8','string':'chef'},'Latin1','Latin1') ok
vul_rsa_01
200
あなたは組織の定期研修に参加しています。 教官から RSA 暗号の禁止事項くらいは覚えておくようにと課題が出題されました。 どうやら暗号文 c を解くことができればそれだけ早く帰れるようです。 以下の RSA 暗号を解読してフラグを入手してください。 c: 39119617768257067256541748412833564043113729163757164299687579984124653789492591457335 n: 13373801376856352919495636794117610920860037770702465464324474778341963699665011787021257 e: 65537
以下を参考に解いていく
RSA暗号解読問題を解く
https://k-mawa.hateblo.jp/entry/2018/06/07/192242
https://k-mawa.hateblo.jp/entry/2018/06/19/141347
Msieve(高速に素因数分解を行ってくれるプログラム)のインストール
https://inaz2.hatenablog.com/entry/2016/01/09/032521
Ubuntuにて必要となるパッケージをインストール
$ sudo apt-get install build-essential libgmp3-dev zlib1g-dev libecm-dev
ダウンロードとコンパイル
$ wget "http://downloads.sourceforge.net/project/msieve/msieve/Msieve%20v1.52/msieve152.tar.gz?r=&ts=1452107977&use_mirror=jaist" -O msieve152.tar.gz $ tar xvf msieve152.tar.gz $ cd msieve-1.52/ $ make all ECM=1
nの値を使い、解析を行う
$ ./msieve -e -p -q -v "13373801376856352919495636794117610920860037770702465464324474778341963699665011787021257" Msieve v. 1.52 (SVN unknown) :(略) prp43 factor: 3058517013146002381763962882964790715736519 prp46 factor: 4372642466716249946441875327733923056149624303 elapsed time 00:29:31
ログより、30分ほどかかっている
nを素因数分解した場合の、2つの素数pとqが判明
pycryptoをインストール
$ pip install pycrypto
参考サイトの通り、スクリプトを書く
from Crypto.PublicKey import RSA from Crypto import Random from Crypto.Util.number import * #inverse()を使う import Crypto.PublicKey.RSA as RSA C = 39119617768257067256541748412833564043113729163757164299687579984124653789492591457335 N = 13373801376856352919495636794117610920860037770702465464324474778341963699665011787021257 E = 65537 p = 3058517013146002381763962882964790715736519 q = 4372642466716249946441875327733923056149624303 d = inverse(E,(p-1)*(q-1)) print (d) #秘密鍵 rsa_key = RSA.construct((p*q, E, d)) print (rsa_key) print (rsa_key.decrypt(C)) int = rsa_key.decrypt(C) print (long_to_bytes(int))
スクリプトを実行
$ python3 rsa_test.py 4897557609358873156657999039608506066811736904039482454770352974851826510011931551945473 <_RSAobj @0x7f98fd45cda0 n(293),e,d,p,q,u,private> 46327402297761911070944293204953074319567693047395802794186233938451290661245 b'flag{weak_rsa_can_be_decrypted!}'
vul_rsa_02
250
あなたは引き続き組織の定期研修に参加しています。教官は昨日と同じ人物です。 「早く帰れると言ったな。あれは嘘だ」昨日の信じられない光景が脳裏に蘇ります。 RSA 暗号の禁止事項くらいは覚えておくようにと再び RSA 暗号の課題が出題されました。 もはや誰も信じていませんがどうやら暗号文 c を解くことができればそれだけ早く帰れるようです。 以下の RSA 暗号を解読してフラグを入手してください。 c: 227982950403746746755552239763357058548502617805036635512868420433061892121830106966643649614593055827188324989309580260616202575703840597661315505385258421941843741681 n: 314346410651148884346780415550080886403387714336281086088147022485674797846237037974025946383115524274834695323732173639559408484919557273975110018517586435379414584423 e: 66936921908603214280018123951718024245768729741801173248810116559480507532472797061229726239246069153844944427944092809221289396952390359710880636835981794334459051137
ROCAの脆弱性を試してみる
ROCAに必要なパッケージのインストール
$ sudo apt install git $ sudo apt install libgmp-dev $ sudo apt install cmake
necaのダウンロードとインストール
$ git clone https://gitlab.com/jix/neca $cd neca $cmake . $make
./neca (nの値)のように実行
$ ./neca 314346410651148884346780415550080886403387714336281086088147022485674797846237037974025946383115524274834695323732173639559408484919557273975110018517586435379414584423 NECA - Not Even Coppersmith's Attack ROCA weak RSA key attack by Jannis Harder (me@jix.one) *** Currently only 512-bit keys are supported *** *** OpenMP support enabled *** N = 314346410651148884346780415550080886403387714336281086088147022485674797846237037974025946383115524274834695323732173639559408484919557273975110018517586435379414584423 Given key does not seem to be weak.
失敗
(参考)以下サイトでROCAの脆弱性があるかチェックできる
https://keychest.net/roca
(ここまで)
RSA暗号運用でやってはいけないnのこと
https://www.slideshare.net/sonickun/rsa-n-ssmjp
eの値が大きすぎてはいけない
Wiener's Attack が適用可能
eが大きいと相対的にdが小さくなることを利用
上記が使えそう
Pragyan CTF 2019 "Easy RSA" writeup
https://ctftime.org/writeup/13831
rsa-wiener-attack
https://github.com/pablocelayes/rsa-wiener-attack
上記を少し変更して問題に合わせる
import ContinuedFractions, Arithmetic, RSAvulnerableKeyGenerator def hack_RSA(e,n): ''' Finds d knowing (e,n) applying the Wiener continued fraction attack ''' frac = ContinuedFractions.rational_to_contfrac(e, n) convergents = ContinuedFractions.convergents_from_contfrac(frac) for (k,d) in convergents: #check if d is actually the key if k!=0 and (e*d-1)%k == 0: phi = (e*d-1)//k s = n - phi + 1 # check if the equation x^2 - s*x + n = 0 # has integer roots discr = s*s - 4*n if(discr>=0): t = Arithmetic.is_perfect_square(discr) if t!=-1 and (s+t)%2==0: print("Hacked!") return d # TEST functions def test_hack_RSA(): print("Testing Wiener Attack") times = 1 while(times>0): e = 66936921908603214280018123951718024245768729741801173248810116559480507532472797061229726239246069153844944427944092809221289396952390359710880636835981794334459051137 n = 314346410651148884346780415550080886403387714336281086088147022485674797846237037974025946383115524274834695323732173639559408484919557273975110018517586435379414584423 d = 0 print("(e,n) is (", e, ", ", n, ")") print("d = ", d) hacked_d = hack_RSA(e, n) print("d = ", d, ", hacked_d = ", hacked_d) print("-------------------------") times -= 1 if __name__ == "__main__": #test_is_perfect_square() #print("-------------------------") test_hack_RSA()
実行してみる
$ python3 RSAwienerHacker_m.py Testing Wiener Attack (e,n) is ( 66936921908603214280018123951718024245768729741801173248810116559480507532472797061229726239246069153844944427944092809221289396952390359710880636835981794334459051137 , 314346410651148884346780415550080886403387714336281086088147022485674797846237037974025946383115524274834695323732173639559408484919557273975110018517586435379414584423 ) d = 0 Hacked! d = 0 , hacked_d = 19780253153570454414022314122363673676673 -------------------------
以下スクリプトにて復号する
(参考にしたサイト)https://tech.kusuwada.com/entry/2018/06/02/013904
from Crypto.PublicKey import RSA from Crypto import Random from Crypto.Util.number import * #inverse()を使う import Crypto.PublicKey.RSA as RSA E = 66936921908603214280018123951718024245768729741801173248810116559480507532472797061229726239246069153844944427944092809221289396952390359710880636835981794334459051137 N = 314346410651148884346780415550080886403387714336281086088147022485674797846237037974025946383115524274834695323732173639559408484919557273975110018517586435379414584423 C = 227982950403746746755552239763357058548502617805036635512868420433061892121830106966643649614593055827188324989309580260616202575703840597661315505385258421941843741681 d = 19780253153570454414022314122363673676673 key = RSA.construct(map(int, (N, E, d))) print(long_to_bytes(key.decrypt(C)))
実行
$ python3 rsa_test.py b'\x02my\xa6\xfb\xa2t\x19X\xce\x82F(U\xa9n\xc4\xdc\x16#\x13<\xfc4\x15y\x92\x0b\xef\xc0.\xb7\xb9\xe0\xa3\xbb\xb8r\x00flag{197_Michael_J_Wiener_673}'
なんか、フラグ以外に余計な出力がでているが・・・不明
WEARECIA
300
家に帰ると黒い封筒が郵便受けに入っていました。 封筒の中身は英字が羅列されたメモが一枚。 青銅色の紙に白いインクで書かれており右下には同じインクで WEARECIA と記載されています。 どうやら暗号文のようです。暗号文を解析してメッセージを受け取る必要がありそうです。 以下の暗号文を解読し、隠されたメッセージを見つけてください。 フラグは得られたメッセージを flag{} で囲んで回答してください。 EMUFPHZLRFAXYUSDJKZLDKRNSHGNFIVJYQTQUXQBQVYUVLLTREVJYQTMKYRDMFDRCDNKFRHHMKVLLTGBMFDUTMALDUMKYQTGLWLWCM
(解けていない)
(追記)
https://github.com/satoki/ctf_writeups/tree/master/setodaNote_CTF/WEARECIA
以下を使うらしい
https://www.dcode.fr/vigenere-cipher
ALPHABET
にKRYPTOSABCDEFGHIJLMNQUVWXZ
KNOWING THE KEY/PASSWORD:
にPALIMPSEST
FLAGISを含む文字となる
BETWEENSUBTLESHADINGANDTHEABSENCEOFLIGHTLIESTHENUANCEOFIQLUSIONFLAGISWEARETHENATIONSFIRSTLINEOFDEFENSE