rsa_oracle
authored by Geoffrey Njogu
Can you abuse the oracle?
An attacker was able to intercept communications between a bank and a fintech company. They managed to get the message (ciphertext) and the password that was used to encrypt the message.
接続すると、encryptかdecryptか選べます。
*****************************************
****************THE ORACLE***************
*****************************************
what should we do for you?
E --> encrypt D --> decrypt.
E
enter text to encrypt (encoded length must be less than keysize): hello
hello
encoded cleartext as Hex m: 68656c6c6f
ciphertext (m ^ e mod n) 4771018253433448725341325390782696752299209399308439583683919865061394557092076060859425893425263580055602339828574579252384704080957097568606541920108672
what should we do for you?
ここで、我々が得られる情報は平文$m$と暗号文$c$です。また、暗号文は同じなので、$e,n$は固定であると推測できます。
what should we do for you?
E --> encrypt D --> decrypt.
E
enter text to encrypt (encoded length must be less than keysize): hello
hello
encoded cleartext as Hex m: 68656c6c6f
ciphertext (m ^ e mod n) 4771018253433448725341325390782696752299209399308439583683919865061394557092076060859425893425263580055602339828574579252384704080957097568606541920108672
what should we do for you?
E --> encrypt D --> decrypt.
E
enter text to encrypt (encoded length must be less than keysize): hello
hello
encoded cleartext as Hex m: 68656c6c6f
ciphertext (m ^ e mod n) 4771018253433448725341325390782696752299209399308439583683919865061394557092076060859425893425263580055602339828574579252384704080957097568606541920108672
what should we do for you?
E --> encrypt D --> decrypt.
Dを選択し、$c$を渡すと復元できます。
what should we do for you?
E --> encrypt D --> decrypt.
D
Enter text to decrypt: 4771018253433448725341325390782696752299209399308439583683919865061394557092076060859425893425263580055602339828574579252384704080957097568606541920108672
decrypted ciphertext as hex (c ^ d mod n): 68656c6c6f
decrypted ciphertext: hello
ただし、passwordを暗号化したものを入力すると怒られます。
what should we do for you?
E --> encrypt D --> decrypt.
D
Enter text to decrypt: 4228273471152570993857755209040611143227336245190875847649142807501848960847851973658239485570030833999780269457000091948785164374915942471027917017922546
Lol, good try, can't decrypt that for you. Be creative and good luck
我々の目的はopensslで使用するpasswordを復元し、フラグを得ることです。
解法
私達は任意の平文を用いて暗号文を生成できます。そのため、chosen cipher attackをすることができます。
https://crypto.stackexchange.com/questions/2323/how-does-a-chosen-plaintext-attack-on-rsa-work/2331
さて、passwordの値$m$はpassword.encの値は以下のように生成されています。
$$
c \equiv m^e \pmod n
$$
さて、ここで、任意の文字列を暗号化してみましょう。例えば、2を暗号化すると、
$$
ｃ_a \equiv 2^e \pmod n
$$
となります。
さて、ここで、$c, c_a$を掛け算した暗号文$c_b$を考えると
$$
c_b \equiv c\cdot c_b \equiv m^e\cdot2^e \pmod n
$$
となります。
これを復号すると、
$$
(c_b)^d \equiv (m^e\cdot2^e)^d \equiv (m^e)^d\cdot (2^e)^d \pmod n
$$
となります。
ここで、$ed \equiv 1 \pmod {\phi(n)}$より
$$
(c_b)^d \equiv m\cdot 2
$$
となるため、復号した結果から2を割ることで$m$を求めることができます。
from pwn import *
from Crypto.Util.number import long_to_bytes
HOST = "titan.picoctf.net"
PORT = 54804
io = remote(HOST, PORT)
enc = 4228273471152570993857755209040611143227336245190875847649142807501848960847851973658239485570030833999780269457000091948785164374915942471027917017922546
io.sendlineafter(b"D --> decrypt. ", b"E")
io.sendlineafter(b"keysize): ", b"\x02")
io.recvuntil(b"mod n) ")
c_a = int(io.recvline())
io.sendlineafter(b"D --> decrypt. ", b"D")
io.sendlineafter(b"decrypt: ", str(enc*c_a).encode())
io.recvuntil(b"mod n): ")
m = io.recvline().strip().decode()
m = int(m, 16)//2
print(long_to_bytes(m).decode())
実行すると以下が得られます。
da099
よって、openssl enc -aes-256-cbc -d -in secret.encを実行し、da009を渡すと以下になります。
enter AES-256-CBC decryption password:
*** WARNING : deprecated key derivation used.
Using -iter or -pbkdf2 would be better.
picoCTF{su((3ss_(r@ck1ng_r3@_da099d93}
Flag: picoCTF{su((3ss_(r@ck1ng_r3@_da099d93}