RSA LSB Oracle Attack ( + 키 값 계속 바뀔 시도 가능)

RSA LSB Oracle Attack에서 키값이 바뀌거나 고정되어있을때 공격할 수 있는 방법이다.

이전과 다른 점은 N값이 계속 바뀐다는 점인데, 이는 한 비트씩 추출하는 방법으로 풀 수 있다.

2의 제곱들의 역원을 이용해서 한비트씩 추출해내는 방법으로 문제를 푸는 것인데,

기존의 LSB Attack 공격에 쓰이는 방법과 비교했을때, (기존에 이 블로그 writeup에 쓰인 방법들은 이진탐색 방법이였다.)

한 bit씩 추출하여 flag를 찾아낸다는 점에서 더 괜찮은 공격방법일 수 있다.

생각해보니 이 방법 자체가 엄청 좋은 것같다. ㅎㅎ...

example server

from Crypto.PublicKey import RSA
from Crypto.Util.number import long_to_bytes, bytes_to_long
 
menu = """
1. Get PublicKey
2. Encrypt
3. Decrypt
4. Print FLAG
"""
 
with open("./flag", "r") as f:
    flag = f.read().strip()
    
privkey = RSA.generate(1024)
N = privkey.n
e = privkey.e
d = privkey.d
 
def encrypt(p):
    return pow(p, e, N)
 
def decrypt(c):
    return pow(c, d, N)%2
    
def main():
    global N,e,d
    print(menu.strip())
    choice = int(input("> "))
    if choice == 1:
        print("n is "+str(N))
        print("e is "+str(e))
    elif choice == 2:
        data = raw_input("msg : ")
        print("enc : "+str(encrypt(bytes_to_long(data))))
    elif choice == 3:
        data = input("msg (demical number) : ")
        print("dec : "+str(decrypt(data)))
        privkey = RSA.generate(1024)
        N = privkey.n
        e = privkey.e
        d = privkey.d
    elif choice == 4:
        print(str(encrypt(bytes_to_long(flag))))
    else:
        print("invalid menu")
 
welcome = """
 /$$$$$$$   /$$$$$$   /$$$$$$         /$$$$$$  /$$     /$$ /$$$$$$  /$$$$$$$$ /$$$$$$$$ /$$      /$$
| $$__  $$ /$$__  $$ /$$__  $$       /$$__  $$|  $$   /$$//$$__  $$|__  $$__/| $$_____/| $$$    /$$$
| $$  \ $$| $$  \__/| $$  \ $$      | $$  \__/ \  $$ /$$/| $$  \__/   | $$   | $$      | $$$$  /$$$$
| $$$$$$$/|  $$$$$$ | $$$$$$$$      |  $$$$$$   \  $$$$/ |  $$$$$$    | $$   | $$$$$   | $$ $$/$$ $$
| $$__  $$ \____  $$| $$__  $$       \____  $$   \  $$/   \____  $$   | $$   | $$__/   | $$  $$$| $$
| $$  \ $$ /$$  \ $$| $$  | $$       /$$  \ $$    | $$    /$$  \ $$   | $$   | $$      | $$\  $ | $$
| $$  | $$|  $$$$$$/| $$  | $$      |  $$$$$$/    | $$   |  $$$$$$/   | $$   | $$$$$$$$| $$ \/  | $$
|__/  |__/ \______/ |__/  |__/       \______/     |__/    \______/    |__/   |________/|__/     |__/

version 3.2.7                                                    
"""
 
print(privkey.d)
 
if __name__ == '__main__':
    print(welcome)
    while True:
        try: main()
        except: break

attack code

from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from pwn import *
 
conn = process(["python", "server.py"])
 
def get_key():
    conn.sendlineafter("4. Print FLAG", "1")
    conn.recvuntil("n is ")
    return int(conn.recvline().strip())
    
def get_flag():
    conn.sendlineafter("4. Print FLAG", "4")
    conn.recvuntil("> ")
    return int(conn.recvline().strip())
 
def decrypt(ct):
    conn.sendlineafter("4. Print FLAG", "3")
    conn.sendline(str(ct))
    conn.recvuntil("dec : ")
    result = int(conn.recvline().strip())
    return result
    
flag_enc = get_flag()
init_N = get_key()
 
# Public exponent
e = 65537
 
bits = "1"
flag = ""
i = 1
while True:
    enc = get_flag()
    N = get_key()
 
    inv = inverse(2**i, N)
    chosen_ct = (enc*pow(inv, e, N))%N
    output = decrypt(chosen_ct)
    flag_char = (output - ((int(bits, 2)*inv) % N)) % 2
 
    bits = str(flag_char) + bits
    if len(bits) % 8 == 0:
        flag = long_to_bytes(int(bits, 2))
        print(flag)
        if flag_enc == pow(int(bits, 2), e,init_N):
            break
    i+=1