선택 암호문 공격(Chosen Ciphertext Attack) - testbook rsa

 

testbook rsa 문제파일을 받아 열어보니 

#!/usr/bin/python3
from Crypto.Util.number import getStrongPrime, bytes_to_long, inverse


class RSA(object):
    def __init__(self):
        self.p = getStrongPrime(512)
        self.q = getStrongPrime(512)
        self.N = self.p * self.q
        self.e = 0x10001
        self.d = inverse(self.e, self.N - self.p - self.q + 1)

    def encrypt(self, pt):
        return pow(pt, self.e, self.N)

    def decrypt(self, ct):
        return pow(ct, self.d, self.N)


rsa = RSA()
FLAG = bytes_to_long(open("flag", "rb").read())
FLAG_enc = rsa.encrypt(FLAG)

print("Welcome to dream's RSA server")

while True:
    print("[1] Encrypt")
    print("[2] Decrypt")
    print("[3] Get info")

    choice = input()

    if choice == "1":
        print("Input plaintext (hex): ", end="")
        pt = bytes_to_long(bytes.fromhex(input()))
        print(rsa.encrypt(pt))

    elif choice == "2":
        print("Input ciphertext (hex): ", end="")      #2번을 누르고 플래그 값이나 암호문보다 값이 작은 N을 입력하면 치트를 쓰지말라고 한다 
        ct = bytes_to_long(bytes.fromhex(input()))
        if ct == FLAG_enc or ct > rsa.N:
            print("Do not cheat !")
        else:
            print(rsa.decrypt(ct))

    elif choice == "3":                       #3번을 누르면 공개키 (E,n)과 암호문을 준다.
        print(f"N: {rsa.N}")
        print(f"e: {rsa.e}")
        print(f"FLAG: {FLAG_enc}")

    else:
        print("Nope")

 

이런식으로 운영되는 방식이였다 



근데 공개키로 평문을 암호문으로 만들지 않나? 그럼 어떻게 공격하지..  싶었는데 찾아보니
선택 암호문 공격 (CCA) 를 알아야한다 

선택 암호문 공격은 임의로 선택된 암호문과 일치하는 평문으로부터 암호키를 알아내기 위해 시도하는 공격이다.
즉 원하는 암호문을 복호화해주는 경우 사용할 수 있는 공격 방법이다.
RSA에서 쓰이는 경우는 "곱셈에 대한 준동형사상(Homomorphism)의 성질"이라고 한다

곱셈에 대한 준동형사상은 다음 식으로 정리될 수 있으며, 이를 이용하면 다음과 같은 공격이 가능해진다.

암호화된 flag가 있고, 암/복호화 기능이 존재한다고 가정하면

1. 숫자 2를 암호화 한다.

2. 숫자 2를 암호화 한 값 *  flag를 암호화 한 값을 곱한다.

3. 결과 값을 숫자 2로 나누면 flag가 된다.





덧붙여, 이 방법을 막기 위해서 고안된 방법은 RSA-OAEP를 제안하였다.

RSA-OAEP는 암호화 단계에서 평문 해시값과 정해진 개수의 '0' 등으로 만들어진 "인증 정보"를 평문의 앞에 추가하고 RSA로 암호화한다.

이후 복호화단계에서 이 "인증 정보"가 보이지 않을 경우 평문을 알고 있는 사람이 만든 암호문이 아니라고 판단하여 복호화를 진행하지 않는다.

실제로 RSA-OAEP에서는 난수를 이용하는 등 암호문이 매번 다른 패턴이 되도록 하여 안전성을 높였다





즉, 이 문제에서는 

2^e * flag_enc 를 [2] Decrypt에 넣어 1/2 해주면 된다.



내가 참고한 blog에서는 pwn 툴을 사용했는데 처음 써봐서 베끼는 수준 이였지만..

이 문제를 통해 pwn툴의 이해와 CCA의 개념을 이해했다

 

from pwn import *
from Crypto.Util.number import *

p = remote('host3.dreamhack.games', 21275) # 서버랑 연결 

p.sendlineafter('info\n', '3') #기다렸다가, 3번째 메뉴 선택

p.recvuntil('N: ')             # N값 받아오기(개행문자 제거해 정수로 변환한 값을 n에 저장)
n = int(p.recvline()[:-1])

p.recvuntil('e: ')            # e값 받아오기 (개행문자 제거해 정수로 변환한 값을 e에 저장)
e = int(p.recvline()[:-1])

p.recvuntil('FLAG: ')        # FLAG값 받아오기(개행문자 제거해 정수로 변환한 값을 flag_enc에 저장)
flag_enc = int(p.recvline()[:-1])

exploit_flag = (pow(2,e) * flag_enc) % n  # exploit_flag에 2^e * flag_enc % n 값을 저장

p.sendlineafter('info\n', '2')                  # 2번째 메뉴 선택
p.sendlineafter('hex): ', hex(exploit_flag)[2:])# exploit_flag값을 16진수로 변환해 전송 16진수 변환시 0x가 붙으므로 [2:]로 0x를 제거

verflag = int(p.recvline()[:-1])  # verflag에 받아온 값을 정수로 변환해 저장
flag  = verflag // 2      # verflag값을 2로 나눈 몫을 flag에 저장
log.info("REAL FLAG: " + str(long_to_bytes(flag))) # flag값을 바이트로 변환해 출력

 

 

참고 / 인용 블로그 출처

https://m.blog.naver.com/PostView.naver?blogId=apple8718&logNo=222256582723&categoryNo=0&proxyReferer=

DreamHack - Textbook-RSA

https://dokhakdubini.tistory.com/289