InterKosenCTF writeup

はじめに

cryptoは全部解くぞ!!という気持ちで始めたがOh my Hashで撃沈した。ついでに裏で開催されていたInsomni'hack Teaser 2019 CTF も撃沈した。 f:id:kent056-n:20190120213355p:plain

[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でフィルターする。それらしい通信が一個だけあったので中身を見てみる。 f:id:kent056-n:20190120212609p:plain 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において,eが極端に小さく,m<\sqrt[e]{n} となる場合,RSAの暗号化c\ =\ m^{e}\ mod\ nの結果としてm^{e}が出力されてしまう(the Low Public Exponent Attack)。
そこで,この問題ではm^{e}nより大きくなるまで以下のコードでmを左シフトしている。

while pow(m, key.e) < key.n:
    m = m << 1

ここで,与えられた暗号文が生成された際に利用された初回のm^{e}nより小さく,上記のループに入ったと仮定する。上記のループはm^{e}\ >\ nとなった時点で抜けるので,nm^{e}がそれなりに近い値になっていると考えられる。よって,c\ =\ m^{e}\ mod\ nの商を総当たりで求め  c+i*n(i \in \mathbb{N}) からmがわかりそう。以下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)

以下は実行結果の一部です。 c+n*5=m^{e} だったようです。

count:  5
c + (n * 5) = 105311740325742980859942104707091180342805911957035657467818137022730454181076036779262237017787017049925349441259159342861847710615658093927109378944740198833467642007364002105409310950821681950249309627389494153310001846927690005596770204655415219153192197901168177869373506128629323319168192745974564595080462364946926806853052749073775857112170315195509206042580667047459312341751936510062789774783728325744305249127478243259376016154742430127166441013782896079903794673935480021552096754315358128780299840376042979007409800776140214488191271283821922828437138882711469377891209591452244768562107740303752437956608
m:  47223582418329825209745914667971590820722714318452791326821588181662319399773846734427941516181423981487302118538346612769422888886822520261688728358369123097589459238242699552111899674856615315187592855552

FLAGはKOSENCTF{THIS_ATTACK_DOESNT_WORK_WELL_PRACTICALLY}

おわりに

楽しかったです。