Simple Crypto - 0x07(2023 HW - Oracle)
Background
POA/RSA
Source code
:::spoiler Oracle.py
from Crypto.Util.number import bytes_to_long
from Crypto.Cipher import AES
from random import randbytes
from secret import aes_key, p, q
def pad(m):
length = 16-len(m) % 16
return m + chr(length).encode()*length
def unpad(c):
length = c[-1]
for char in c[-length:]:
if char != length:
raise ValueError
return c[:-length]
def asymmetric_encryption(message, N, e):
# encrypt message with RSA
# message must be 16 bytes
# padding 100 bytes random value
padded_message = randbytes(100) + message
return pow(bytes_to_long(padded_message), e, N)
def symmetric_encryption(message, key):
# ecrypt message with AES + CBC Mode
# message can be arbitrary length
cipher = AES.new(key, AES.MODE_CBC)
ct = cipher.encrypt(pad(message))
iv = cipher.iv
return iv, ct
## Alice: This is my public key.
# p = getPrime(512)
# q = getPrime(512)
N = p * q
e = 65537
print( f"{N = }, {e = }" )
# N = 69214008498642035761243756357619851816607540327248468473247478342523127723748756926949706235406640562827724567100157104972969498385528097714986614165867074449238186426536742677816881849038677123630836686152379963670139334109846133566156815333584764063197379180877984670843831985941733688575703811651087495223
# e = 65537
## Bob: I want to send message to Alice! But my message is too looooooong......
flag = open("flag.png", "rb").read()
## Bob: Oh! I can use symmetric encryption.
iv, ct = symmetric_encryption(flag, aes_key)
encrypted_key = asymmetric_encryption(aes_key, N, e)
encrypted_iv = asymmetric_encryption(iv, N, e)
print( f"{encrypted_key = }" )
print( f"{encrypted_iv = }" )
open("encrypted_flag.not_png", "wb").write(ct)
## Bob: Ha ha! Now no one can decrypt my message except Alice!
# encrypted_key = 65690013242775728459842109842683020587149462096059598501313133592635945234121561534622365974927219223034823754673718159579772056712404749324225325531206903216411508240699572153162745754564955215041783396329242482406426376133687186983187563217156659178000486342335478915053049498619169740534463504372971359692
# encrypted_iv = 35154524936059729204581782839781987236407179504895959653768093617367549802652967862418906182387861924584809825831862791349195432705129622783580000716829283234184762744224095175044663151370869751957952842383581513986293064879608592662677541628813345923397286253057417592725291925603753086190402107943880261658
::: :::spoiler Alice.py
from Crypto.Util.number import long_to_bytes, inverse
from Crypto.Cipher import AES
from secret import p, q
import signal
def alarm(second):
def handler(signum, frame):
print('Timeout!')
exit()
signal.signal(signal.SIGALRM, handler)
signal.alarm(second)
def pad(m):
length = 16-len(m) % 16
return m + chr(length).encode()*length
def unpad(c):
length = c[-1]
for char in c[-length:]:
if char != length:
raise ValueError
return c[:-length]
## Alice: Okay! AES with CBC mode. I know it.
if __name__ == "__main__":
alarm(300)
N = p * q
e = 65537
d = pow(e, -1, (p-1)*(q-1))
while True:
try:
encrypted_key = int( input("Give me the encrypted key: ") )
encrypted_iv = int( input("Give me the encrypted iv: ") )
ct = bytes.fromhex( input("Give me the ciphertext: ") )
# decrypt asymmetric_encryption()
aes_key = long_to_bytes(pow(encrypted_key, d, N))[-16:]
iv = long_to_bytes(pow(encrypted_iv, d, N))[-16:]
# decrypt symmetric_encryption()
cipher = AES.new(aes_key, AES.MODE_CBC, iv)
tmp = cipher.decrypt(ct)
pt = unpad(tmp)
print(f"OK! Got it.")
except ValueError:
print("I do not understand.")
except:
print("Bye~~")
break
:::
:::spoiler 加密的圖片檔案(Hex Ver.)
1 |
|
:::
Recon
這一題真的非常難，而且要通靈很久，首先Oracle.py的工作是把一張flag image用AES加密，並且把AES會用到的key/iv都用RSA再加密，然後通通傳給Alice，而Alice.py的工作才是本次作業實際上的Oracle，他會吃key/iv/ciphertext，前兩者是decimal，後者是hex形式，一開始可以先試看看把這三者傳過去，理論上只要格式對了就會回傳OK! Got it.
encrypted_key = 65690013242775728459842109842683020587149462096059598501313133592635945234121561534622365974927219223034823754673718159579772056712404749324225325531206903216411508240699572153162745754564955215041783396329242482406426376133687186983187563217156659178000486342335478915053049498619169740534463504372971359692
encrypted_iv = 35154524936059729204581782839781987236407179504895959653768093617367549802652967862418906182387861924584809825831862791349195432705129622783580000716829283234184762744224095175044663151370869751957952842383581513986293064879608592662677541628813345923397286253057417592725291925603753086190402107943880261658
enc_png = open('./Crypto/HW/Oracle/encrypted_flag_d6fbfd5306695c4a.not_png', 'rb').read()
r = remote("10.113.184.121", 10031)
r.sendlineafter(b'key: ', str(encrypted_key).encode())
r.sendlineafter(b'iv: ', str(encrypted_iv).encode())
r.sendlineafter(b'ciphertext: ', enc_png.hex().encode())
print(r.recvline().decode().strip())
解題的手法經@Yaan的小提示，完整如下:
-
首先我們手上可控的地方，就是key/iv/ciphertext，一開始的想法是，由於此次的flag是一張png，所以一開始的magic header一定都一樣，所以可以透過這個magic header推測出IV是多少，但這樣的作法卻沒辦法知道key，所以這個方法行不通
- 正確的作法是控制key/iv，變成自己設定的東西，然後試圖加密plaintext(同樣也是自己設定)，然後把自己設定的ciphertext/key以及原本題目給的encrypted_key或是encrypted_iv丟到oracle，要解密的部分(也就是encrypted_key/encrypted_iv)就當作是iv的部分輸入，這樣神奇的操作如下圖所示
- 為甚麼這樣可以解出我們想要解的東西?那就要取決於如何控制plaintext/iv，key可以隨便控，而plaintext則是從零開始，iv也是全部都是零，這樣的好處是pt用AES加密前的部份是我們知道的，換句話說，在解密的時候和iv XOR前的數值也是知道的，此時我們可以從oracle output知道padding正確與否，我們又知道和iv XOR的數值是多少，則我們一定可以利用POA的方式推出原本的IV是多少
-
舉個例子 若
encrypted_iv=b'0123456789abcdef'$\to$ unknown(也是我們想知道的部分)self_pt=b'0000000000000000'$\to$ self definedself_iv=b'0000000000000000'$\to$ self defined 則我們開始改變self_pt的最後一個byte，也就是b'0...00',b'0...01',b'0...02'…，讓他和encrypted_iv進行XOR之後判斷padding正確與否如果padding正確也就代表目前的padding結果是
0x01，而此時的self_pt=b'0...0e'，所以想當然encrypted_iv=XXX...f，而換到下一round，我們也改造一下self_pt，首先原本最後一個byte(0xe)要改成$0xe\oplus 0x2=0xc$，因為下一round的padding必須要是0x0202才會正確，然後我們就可以改變倒數第二個byte(一樣從零開始)，也就是b'0...0c',b'0...1c',b'0...2c'…，以此類推就可以得出真正的IV是多少了，而encrypted_key的做法也和IV一模一樣
Exploit
:::spoiler SpeedUp Version(只考慮同一個byte只有一種可能的版本)
from pwn import *
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.Cipher import AES
from random import randbytes
def unpad(c):
length = c[-1]
for char in c[-length:]:
if char != length:
raise ValueError
return c[:-length]
def asymmetric_encryption(message, N, e):
# encrypt message with RSA
# message must be 16 bytes
# padding 100 bytes random value
padded_message = b'\x01' * 100 + message
return pow(bytes_to_long(padded_message), e, N)
def symmetric_encryption(message, key, iv):
# ecrypt message with AES + CBC Mode
# message can be arbitrary length
cipher = AES.new(key, AES.MODE_CBC, iv)
ct = cipher.encrypt(message)
iv = cipher.iv
return iv, ct
def compute_know_part(padding_idx, known_key):
if known_key == '':
return b''
known_part = b''
for i in range(len(known_key)//2):
known_part += bytes([int(known_key[i*2:i*2+2], 16) ^ padding_idx])
return known_part
def construct_payload_and_verify(i, known_part, enc_self_key, encrypted_key):
# candidate = []
for byte in range(256): # 每一個byte要猜最多256次
# 自己控制
self_pt = b'\x00' * (15-i) + bytes([byte]) + known_part
log.info(f"self pt = {self_pt}")
_, self_ct = symmetric_encryption(self_pt, self_key, self_iv)
# 連線oracle並驗證
r = remote("10.113.184.121", 10031)
r.sendlineafter(b'key: ', str(enc_self_key).encode())
r.sendlineafter(b'iv: ', str(encrypted_key).encode())
r.sendlineafter(b'ciphertext: ', self_ct.hex().encode())#enc_png.hex().encode()
res = r.recvline().decode().strip()
# log.info(f'key = {enc_self_key}, iv = {encrypted_key}, ct = {self_ct.hex()}')
print(res)
if res == 'OK! Got it.':
tmp = hex(byte ^ (i+1))[2:]
if len(tmp) < 2:
tmp = '0' + tmp
return tmp
r.close()
# 題目給的資訊
enc_png = open('./Crypto/HW/Oracle/encrypted_flag_d6fbfd5306695c4a.not_png', 'rb').read()
N = 69214008498642035761243756357619851816607540327248468473247478342523127723748756926949706235406640562827724567100157104972969498385528097714986614165867074449238186426536742677816881849038677123630836686152379963670139334109846133566156815333584764063197379180877984670843831985941733688575703811651087495223
e = 65537
encrypted_key = 65690013242775728459842109842683020587149462096059598501313133592635945234121561534622365974927219223034823754673718159579772056712404749324225325531206903216411508240699572153162745754564955215041783396329242482406426376133687186983187563217156659178000486342335478915053049498619169740534463504372971359692
encrypted_iv = 35154524936059729204581782839781987236407179504895959653768093617367549802652967862418906182387861924584809825831862791349195432705129622783580000716829283234184762744224095175044663151370869751957952842383581513986293064879608592662677541628813345923397286253057417592725291925603753086190402107943880261658
# 自己控制的資訊
self_iv = b'\x00' * 16
self_key = b'\x00' * 16
enc_self_key = asymmetric_encryption(self_key, N, e)
# Try to POA Key
real_key = ''
for i in range(16): # iv共有16bytes
known_part = compute_know_part(i+1, real_key)
real_key = construct_payload_and_verify(i, known_part, enc_self_key, encrypted_key) + real_key
# Try to POA IV
real_iv = ''
for i in range(16): # iv共有16bytes
known_part = compute_know_part(i+1, real_iv)
real_iv = construct_payload_and_verify(i, known_part, enc_self_key, encrypted_iv) + real_iv
# Final Testing
test_key = pow(int(real_key, 16), e, N)
test_iv = pow(int(real_iv, 16), e, N)
r = remote("10.113.184.121", 10031)
r.sendlineafter(b'key: ', str(test_key).encode())
r.sendlineafter(b'iv: ', str(test_iv).encode())
r.sendlineafter(b'ciphertext: ', enc_png.hex().encode())
assert r.recvline().decode().strip() == 'OK! Got it.'
# Final Decrypt Flag Image
# real_key = '49276d5f345f357472306e395f6b3379'
# real_iv = '4ba3cb1c134651c3bb5cd6e381c2909b'
real_iv = bytes.fromhex(real_iv)
real_key = bytes.fromhex(real_key)
cipher = AES.new(real_key, AES.MODE_CBC, real_iv)
pt = unpad(cipher.decrypt(enc_png))
open("./Crypto/HW/Oracle/decrypted_flag.png", "wb").write(pt)
::: :::spoiler 有考慮同一個byte多種可能的版本
from pwn import *
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.Cipher import AES
from random import randbytes
def unpad(c):
length = c[-1]
for char in c[-length:]:
if char != length:
raise ValueError
return c[:-length]
def asymmetric_encryption(message, N, e):
# encrypt message with RSA
# message must be 16 bytes
# padding 100 bytes random value
padded_message = b'\x01' * 100 + message
return pow(bytes_to_long(padded_message), e, N)
def symmetric_encryption(message, key, iv):
# ecrypt message with AES + CBC Mode
# message can be arbitrary length
cipher = AES.new(key, AES.MODE_CBC, iv)
ct = cipher.encrypt(message)
iv = cipher.iv
return iv, ct
def compute_know_part(padding_idx, known_key):
if known_key == '':
return b''
known_part = b''
for i in range(len(known_key)//2):
known_part += bytes([int(known_key[i*2:i*2+2], 16) ^ padding_idx])
return known_part
def construct_payload_and_verify(i, known_part, enc_self_key, encrypted_key):
candidate = []
for byte in range(256): # 每一個byte要猜最多256次
# 自己控制
self_pt = b'\x00' * (15-i) + bytes([byte]) + known_part
log.info(f"self pt = {self_pt}")
_, self_ct = symmetric_encryption(self_pt, self_key, self_iv)
# 連線oracle並驗證
r = remote("10.113.184.121", 10031)
r.sendlineafter(b'key: ', str(enc_self_key).encode())
r.sendlineafter(b'iv: ', str(encrypted_key).encode())
r.sendlineafter(b'ciphertext: ', self_ct.hex().encode())#enc_png.hex().encode()
res = r.recvline().decode().strip()
# log.info(f'key = {enc_self_key}, iv = {encrypted_key}, ct = {self_ct.hex()}')
print(res)
if res == 'OK! Got it.':
tmp = hex(byte ^ (i+1))[2:]
if len(tmp) < 2:
tmp = '0' + tmp
candidate.append(tmp)
r.close()
if len(candidate) == 0:
raise ValueError
return candidate
# 題目給的資訊
enc_png = open('./Crypto/HW/Oracle/encrypted_flag_d6fbfd5306695c4a.not_png', 'rb').read()
N = 69214008498642035761243756357619851816607540327248468473247478342523127723748756926949706235406640562827724567100157104972969498385528097714986614165867074449238186426536742677816881849038677123630836686152379963670139334109846133566156815333584764063197379180877984670843831985941733688575703811651087495223
e = 65537
encrypted_key = 65690013242775728459842109842683020587149462096059598501313133592635945234121561534622365974927219223034823754673718159579772056712404749324225325531206903216411508240699572153162745754564955215041783396329242482406426376133687186983187563217156659178000486342335478915053049498619169740534463504372971359692
encrypted_iv = 35154524936059729204581782839781987236407179504895959653768093617367549802652967862418906182387861924584809825831862791349195432705129622783580000716829283234184762744224095175044663151370869751957952842383581513986293064879608592662677541628813345923397286253057417592725291925603753086190402107943880261658
# 自己控制的資訊
self_iv = b'\x00' * 16
self_key = b'\x00' * 16
enc_self_key = asymmetric_encryption(self_key, N, e)
# Try to POA Key
i = 0
real_key = ''
known_part = compute_know_part(i+1, real_key)
candidate = construct_payload_and_verify(i, known_part, enc_self_key, encrypted_key)
i += 1
while(len(real_key) != 32): # iv共有16bytes
for candidate_tmp in candidate:
known_part = compute_know_part(i+1, candidate_tmp + real_key)
try:
candidate = construct_payload_and_verify(i, known_part, enc_self_key, encrypted_key)
i += 1
real_key = candidate_tmp + real_key
break
except:
pass
if len(real_key) == 30:
real_key = candidate[0] + real_key
break
# Try to POA IV
real_iv = ''
i = 0
known_part = compute_know_part(i+1, real_iv)
candidate = construct_payload_and_verify(i, known_part, enc_self_key, encrypted_iv)
i += 1
while(len(real_iv) != 32): # iv共有16bytes
for candidate_tmp in candidate:
known_part = compute_know_part(i+1, candidate_tmp + real_iv)
try:
candidate = construct_payload_and_verify(i, known_part, enc_self_key, encrypted_iv)
i += 1
real_iv = candidate_tmp + real_iv
break
except:
pass
if len(real_iv) == 30:
real_iv = candidate[0] + real_iv
break
# Final Testing
test_key = pow(int(real_key, 16), e, N)
test_iv = pow(int(real_iv, 16), e, N)
r = remote("10.113.184.121", 10031)
r.sendlineafter(b'key: ', str(test_key).encode())
r.sendlineafter(b'iv: ', str(test_iv).encode())
r.sendlineafter(b'ciphertext: ', enc_png.hex().encode())
assert r.recvline().decode().strip() == 'OK! Got it.'
# Final Decrypt Flag Image
# real_key = '49276d5f345f357472306e395f6b3379'
# real_iv = '4ba3cb1c134651c3bb5cd6e381c2909b'
real_iv = bytes.fromhex(real_iv)
real_key = bytes.fromhex(real_key)
cipher = AES.new(real_key, AES.MODE_CBC, real_iv)
pt = unpad(cipher.decrypt(enc_png))
open("./Crypto/HW/Oracle/decrypted_flag.png", "wb").write(pt)
:::
:::spoiler Flag
Flag: FLAG{Rea11yu5efu110rac1eisntit?}
:::
SpeedUp的意思是只考慮一個byte只有一種可能的結果，換句話說，256種可能中只有唯一解，而另外一個script就考慮的比較全面了，有可能在256種結果中，有另外一種可能導致padding正確(雖然機率很低)