🙆
Ricerca CTF 2023 Writeup (crackme, RSALCG)
crackme
radare2でpddする
[0x000011a0]> s main
[0x000010e0]> pdd
/* r2dec pseudo code output */
/* crackme @ 0x10e0 */
#include <stdint.h>
int32_t main (void) {
int64_t var_68h;
/* [16] -r-x section size 1445 named .text */
rsi = "Password: ";
edi = 1;
r12d = 1;
rax = *(fs:0x28);
*((rsp + 0x68)) = rax;
eax = 0;
eax = printf_chk ();
eax = 0;
ecx = 0xc;
rdi = rbp;
do {
*(rdi) = rax;
rcx--;
rdi += 8;
} while (rcx != 0);
rsi = rbp;
*(rdi) = 0;
rdi = "%99s";
eax = isoc99_scanf ();
if (eax != 1) {
goto label_0;
}
r12d = eax;
eax = strcmp (rbp, "N1pp0n-Ich!_s3cuR3_p45$w0rD");
if (eax != 0) {
goto label_1;
}
r12d = 0;
puts ("[+] Authenticated");
fcn_00001290 (rbp, rsi, rdx, rcx, r8);
do {
label_0:
rax = *((rsp + 0x68));
rax ^= *(fs:0x28);
if (eax != 0) {
goto label_2;
}
eax = r12d;
return rax;
label_1:
puts ("[-] Permission denied");
} while (1);
label_2:
return stack_chk_fail ();
}
eax = strcmp (rbp, "N1pp0n-Ich!_s3cuR3_p45$w0rD");
いかにもな文字列があるので、それをパスワードとして入力するとflagが返ってくる。
flag
RicSec{U_R_h1y0k0_cr4ck3r!}
RSALCG
encrypt関数のの中身を見ると、randの次の値とmsgをintにしたものでxorを取ったものを返している。
次の表はそれぞれのencryptに関する値についてわかっているかどうかをまとめたものである。
| num | msg | rand | encrypt |
|---|---|---|---|
| 1 | ○ | ☓ | ○ |
| 2 | ☓ | ☓ | ○ |
| 3 | ○ | ☓ | ○ |
encryptはxorを取ったものなので、表の列について2つわかっているものがあれば残りの一つを復元できる。そのため、1番目と3番目のrandの値は復元できる。
次のコードで1番目と3番目のrandを復元できる。
from Crypto.Util.number import getPrime, getRandomNBitInteger
def decrypt(msg, enc) -> int:
assert len(msg) < 128
m = int.from_bytes(msg, 'big')
e = int.from_bytes(enc, 'big')
return m ^ e
a = 104932596701958568145159429432079350581741243925294416012169671604384908382893445168447905864839450402111868722373005467040643335329799448356719960809485814400987619457043584576651627652936429829564657705560266433066823589229257859375942917575729874731586891094997845427952093627170472382405528285663530612106
b = 146908709759837063143862302770110984437045635655026319928249954800644806528614554086681623417268963974691959251767647958752898163761641238519061717835899588252518767306816402052353874469376243689011218283173950163484015487529897260943257598915903245695362042234335492571429369281809958738989439275152307290506
n = 68915438454431862553872087841423255330382510660515857448975005472053459609178709434028465492773792706094321524334359097372292237742328589766664933832084854448986045922250239618283612819975877218019020936022572963433202427817150998352120028655478359887600473211365524707624162292808256010583620102295206287739
enc1 = bytes.fromhex('05d7913ff5cd9b6a706249ac05779f2501013ecc05caec697d9270a8a1d3bdaabf898d73410aa0ffbd361a6032adbbfa35386b2e19ec812e9f6bd52e6a2ca1b3760b3076a86ffc94dd6007d74a272e0e3d5326d9e5b01b9211a803338f5899ad6cc29877cc02ca2ff923db79e3ad477bf3820e73596088f54a8cfb187f812201')
enc2 = bytes.fromhex('1913ba387e6f847dce455dc47092bf83571c34914b7df5875da536f11e68c8a39c78dfe69517ef4b389ea51434e071ce033854fd27c831996aa214cdc02225747a517d44408fbd0232672679bc189f26f6e9b6852a1e68e93ac14e2ce5afc1e050a44733094fe68b0477d4c4b609043e4da4e58390c4f9cf372005653c7f2529')
enc3 = bytes.fromhex('45054a08d594bd8af1d0fac759ccc799214d0ccce8ae9c5183ef4fba296819bcdf6306f72ee34dcd5d85967fae314d6d3d65a7693b4187adce1d5375dd00c472c0310393cd5bb114602e24d481e276a4926e8886bdcfed96bb8bf9c5812d594f66e46b1737849e8e2f2c3f7b6a45e284c754cf6caf71df34efe143636b5e9079')
r1 = decrypt(b"The quick brown fox jumps over the lazy dog", enc1)
r3 = decrypt(b"https://translate.google.com/?sl=it&tl=en&text=ricerca", enc3)
print(f'{r1 = }')
print(f'{r3 = }')
RSALCG関数の中身を見ると、randはそれぞれ
r1 = pow(s, e, n)
r2 = pow(a*s+b, e, n)
r3 = pow(a*(a*s+b)+b, e, n)
と表せる。
r1とr3はわかっているので、ここからr2を求めたい。sがわかればr2を求められそうだ。
ソースコードや問題名を見ると、これはRSA暗号だとわかる。
RSAの攻撃方法を調べていると、Franklin-Reiter's Related Message Attackというものがあった。これは、2つの平文m1, m2が線形の関係m2 = a*m1+b mod nにある場合にm2を消去してm1が根となる多項式を2つ用意して公約式を求めるという攻撃である。[1]
r1とr3はsという共通する根を持つのでこの攻撃でsを求めることができる。
Franklin-Reiter's Related Message Attackは、SageMathというPythonと互換性のある数式処理システムを使って求めることができる。以下はFranklin-Reiter's Related Message Attackによって、sを求めるコードである。
def gcd(a, b):
while b:
a, b = b, a % b
return a.monic()
def franklinreiter(c_1, c_3, e, N, a, b):
P.<X> = PolynomialRing(Zmod(N))
g_1 = X^e - c_1
g_3 = (a * (a * X + b) + b)^e - c_3
# get constant term
result = -gcd(g_1, g_3).coefficients()[0]
return result
e = 65537
a = 104932596701958568145159429432079350581741243925294416012169671604384908382893445168447905864839450402111868722373005467040643335329799448356719960809485814400987619457043584576651627652936429829564657705560266433066823589229257859375942917575729874731586891094997845427952093627170472382405528285663530612106
b = 146908709759837063143862302770110984437045635655026319928249954800644806528614554086681623417268963974691959251767647958752898163761641238519061717835899588252518767306816402052353874469376243689011218283173950163484015487529897260943257598915903245695362042234335492571429369281809958738989439275152307290506
n = 68915438454431862553872087841423255330382510660515857448975005472053459609178709434028465492773792706094321524334359097372292237742328589766664933832084854448986045922250239618283612819975877218019020936022572963433202427817150998352120028655478359887600473211365524707624162292808256010583620102295206287739
r1 = 4102434106008043579936488837699378039360740641774006237755552189529630453777178015000201653079102153928246129458697629301427158512591001899659737157207216302745938866622695626799523364382964475057798609466557515152510664039360090456457928040650333558012115747413108061729062627660070246922529236717924601190
r3 = 48467956371893933851600953666931836976312066706660607925719661744510295044597265883414984748843780444732309151356819832562457100617302905248142548305927916140847514255226414550803745393462775451231059756917693825185620785264405996707488045696278901936585328722064287649170470801913233908842908023279774921496
print("[+] attack!")
s = franklinreiter(r1, r3, e, n, a, b)
print(s)
Franklin-Reiter's Related Message Attackはe=65537の場合、単純な実装だと数十分かかるらしい[1]。Half GCDを使うと計算量を抑えられるらしいが、わからなかったので数十分待った。
sがわかると、r2がわかるのでflagを求められる。
from Crypto.Util.number import getPrime, getRandomNBitInteger
def msg_decrypt(r, enc) -> str:
e = int.from_bytes(enc, 'big')
msg = int.to_bytes(e ^ r, 128, 'big')
return msg.decode()
e = 65537
a = 104932596701958568145159429432079350581741243925294416012169671604384908382893445168447905864839450402111868722373005467040643335329799448356719960809485814400987619457043584576651627652936429829564657705560266433066823589229257859375942917575729874731586891094997845427952093627170472382405528285663530612106
b = 146908709759837063143862302770110984437045635655026319928249954800644806528614554086681623417268963974691959251767647958752898163761641238519061717835899588252518767306816402052353874469376243689011218283173950163484015487529897260943257598915903245695362042234335492571429369281809958738989439275152307290506
n = 68915438454431862553872087841423255330382510660515857448975005472053459609178709434028465492773792706094321524334359097372292237742328589766664933832084854448986045922250239618283612819975877218019020936022572963433202427817150998352120028655478359887600473211365524707624162292808256010583620102295206287739
r1 = 4102434106008043579936488837699378039360740641774006237755552189529630453777178015000201653079102153928246129458697629301427158512591001899659737157207216302745938866622695626799523364382964475057798609466557515152510664039360090456457928040650333558012115747413108061729062627660070246922529236717924601190
enc2 = bytes.fromhex('1913ba387e6f847dce455dc47092bf83571c34914b7df5875da536f11e68c8a39c78dfe69517ef4b389ea51434e071ce033854fd27c831996aa214cdc02225747a517d44408fbd0232672679bc189f26f6e9b6852a1e68e93ac14e2ce5afc1e050a44733094fe68b0477d4c4b609043e4da4e58390c4f9cf372005653c7f2529')
s = 24802524094892764390816794384944308370251473692747012993557713187868617403697786865826271497911602639637398953294654319149624621364866253360994793748814761871690304319490763736872357370208364272487213480564047610144477968270750943374949200574139205920020277550279625690810213446711486577844974516092267761366
# check
assert(r1 == pow(s, e, n))
r2 = pow(a*s+b, e, n)
flag = msg_decrypt(r2, enc2)
print(flag)
flag
RicSec{1_7h1nk_y0u_uNd3r5t4nd_ev3ry7h1ng_4b0ut_Franklin-Reiter's_a7t4ck}
参考資料
[1] RSA暗号攻撃で他でも使える n のこと
Discussion