InterKosenCTF writeup
はじめに
cryptoは全部解くぞ!!という気持ちで始めたがOh my Hashで撃沈した。ついでに裏で開催されていたInsomni'hack Teaser 2019 CTF も撃沈した。
[Forensics 50pts]attack log
以下問題文。
Someone seems to have tried breaking through our authentication. Find out if he or she made it to the end.
問題ファイルとしてpcapngファイルが降ってくる。中身を見るとHTTPの401 Unauthorizedのパケットが大量にある。ここで200 OK
を返した通信もあるのではないかと思い,http.response.code == 200
でフィルターする。それらしい通信が一個だけあったので中身を見てみる。
Basic認証のパスワードがFLAGらしいのでデコードする。
KONSEN{bRut3F0rc3W0rk3D}
[Crypto 100pts]strengthened
以下問題文。
If you choose a tiny e as an RSA public exponent key, it may have the Low Public Exponent Attack vulnerability. So, I strengthened it.
問題のファイルは以下の2つ。
from Crypto.PublicKey import RSA from flag import flag assert(flag.startswith("KOSENCTF")) m = int(flag.encode("hex"), 16) key = RSA.generate(2048, e=3) while pow(m, key.e) < key.n: m = m << 1 c = pow(m, key.e, key.n) print("c={}".format(c)) print("e={}".format(key.e)) print("n={}".format(key.n))
c=4463460595992453701248363487821541441150903755360725278018226219397401710363861496059259094224390706180220952190225631877998805079875092397697611750633506584765344462795005248071815365597632474605092833538433542560077911683343354987797542811482161587946052311886487498036017642286567004537026772476444248546454191809039364154237333857544244714476659565633430727987398093807535598721617188645525580904749313860179445486488885745360135318781538863153023533787846418930231495508425497894530548826950697134882405386297339090051713047204435071147720540765043175338026604739425761557904004394283569956586190646684678673053 e=3 n=20169655945950105431738748243853927780331001640334986437959982160666610494142435056640595584712525268749025697813786742196769781107156600305882353438821338449740459508913799371467499117044809895128843358770212122149984787048869330121794532368786611513049229117856338074267497697268551262926233194699624069306801634627577488539763083043246322479538731125975155062918653790730355348606063864283452838775795802376825160728197871502803176167192178252802683495999009932194712635685410904731513241097681486329083486997949127983471617545787155883408710148611375930619822455594408723266661117411592239721104309931413551856711
RSAにおいて,が極端に小さく, となる場合,RSAの暗号化の結果としてが出力されてしまう(the Low Public Exponent Attack)。
そこで,この問題ではがより大きくなるまで以下のコードでを左シフトしている。
while pow(m, key.e) < key.n: m = m << 1
ここで,与えられた暗号文が生成された際に利用された初回のがより小さく,上記のループに入ったと仮定する。上記のループはとなった時点で抜けるので,とがそれなりに近い値になっていると考えられる。よって,の商を総当たりで求め からがわかりそう。以下solverです。
import gmpy2 c = 4463460595992453701248363487821541441150903755360725278018226219397401710363861496059259094224390706180220952190225631877998805079875092397697611750633506584765344462795005248071815365597632474605092833538433542560077911683343354987797542811482161587946052311886487498036017642286567004537026772476444248546454191809039364154237333857544244714476659565633430727987398093807535598721617188645525580904749313860179445486488885745360135318781538863153023533787846418930231495508425497894530548826950697134882405386297339090051713047204435071147720540765043175338026604739425761557904004394283569956586190646684678673053 n = 20169655945950105431738748243853927780331001640334986437959982160666610494142435056640595584712525268749025697813786742196769781107156600305882353438821338449740459508913799371467499117044809895128843358770212122149984787048869330121794532368786611513049229117856338074267497697268551262926233194699624069306801634627577488539763083043246322479538731125975155062918653790730355348606063864283452838775795802376825160728197871502803176167192178252802683495999009932194712635685410904731513241097681486329083486997949127983471617545787155883408710148611375930619822455594408723266661117411592239721104309931413551856711 e = 3 me = c + n m,result = gmpy2.iroot(me,e) i = 1 while (result != True): i += 1 me = c + (n * i) m,result = gmpy2.iroot(me,e) print("count: ", i) print("c + (n * {}) = {}".format(i, me)) print("m: ", m)
以下は実行結果の一部です。 だったようです。
count: 5 c + (n * 5) = 105311740325742980859942104707091180342805911957035657467818137022730454181076036779262237017787017049925349441259159342861847710615658093927109378944740198833467642007364002105409310950821681950249309627389494153310001846927690005596770204655415219153192197901168177869373506128629323319168192745974564595080462364946926806853052749073775857112170315195509206042580667047459312341751936510062789774783728325744305249127478243259376016154742430127166441013782896079903794673935480021552096754315358128780299840376042979007409800776140214488191271283821922828437138882711469377891209591452244768562107740303752437956608 m: 47223582418329825209745914667971590820722714318452791326821588181662319399773846734427941516181423981487302118538346612769422888886822520261688728358369123097589459238242699552111899674856615315187592855552
FLAGはKOSENCTF{THIS_ATTACK_DOESNT_WORK_WELL_PRACTICALLY}
おわりに
楽しかったです。