[CCE 2023] - the miracle

 

 

작년에도 CCE 에 참가했었는데, 작년에는 너무 해킹을 입문하는 과정이기도 했고.. 너무 실력에 비해 어려운 문제들이 출제되어서 풀 엄두도 못 냈었다. 그래서 1년동안 내가 얼마나 성장했는지 알아보고 싶기도 하고,, 뭔가 한두문제 정도 풀고 싶어서 참가하게 되었는데 생각만큼 문제를 잘 풀지 못한 것 같아서 조금 부끄러운 상황,,

 

사실 지금 포스팅 하고자 하는 문제도 문제를 당시에는 해결하지 못했었는데, 끝나고 디스코드를 조금 보니까 풀지 못한 것에 화가 난다.. 분명 다 아는 이론들이였고, 구현만 하면 되는 상태였는데 왜 못풀었는지..

🖲️ Code Analysis

import os
import random as rand
from Crypto.Util.number import GCD, isPrime

print("Send Parameters!")
p = int(input())
q = int(input())
e = int(input())
n = p * q

def validate(p, q, e, n):
    assert isPrime(p) and isPrime(q)
    assert p.bit_length() == 512
    assert q.bit_length() == 512
    assert p != q
    assert GCD(e, (p - 1) * (q - 1)) == 1
    assert 65537 < e < (p - 1) * (q - 1) - 65537
    assert "3141592653589793238462643383279502884197169399375105820974944592307816406286" in str(e) # first digits of pi - nothing up my sleeve!
    assert "2718281828459045235360287471352662497757247093699959574966967627724076630353" in str(n) # first digits of E - nothing up my sleeve!

print("Validation!")
validate(p, q, e, n)

def inc_state(state):
    next_z = pow(state, e, n)
    next_out = next_z % (1 << 896)
    next_state = next_z >> 896
    return next_out, next_state

state = rand.randint(1, n >> 896)
next_out, state = inc_state(state)

print("First Outputs")
print(next_out)

next_out, state = inc_state(state)

claimed_next_out = int(input())
claimed_state = int(input())

if claimed_next_out == next_out and claimed_state == state:
    with open(os.path.join(os.path.abspath(os.path.dirname(__file__)), "flag.txt")) as f:
        FLAG = f.read().strip()
    print(FLAG)

생각보다는 간단한 코드.. 간단하게 말하면 p, q, e 를 우리가 입력하고, random 한 m 을 암호화한 값의 lsb 를 가지고 다음의 암호문을 예측하는 문제라고 생각하면 된다. 자세히 정리하자면 아래와 같다. 

 

1. p , q, e 를 입력받는다. (단, p 와 q 는 모두 512 비트여야 하고, p * q 와 e 에는 명시된 각 수들이 필수적으로 들어가야 한다. 추가적으로, e 와 phi(n) 은 서로소이고, e < phi(n) - 0x10001 을 만족해야 한다. 또한, p 와 q는 같아서는 안된다.)
2. 랜덤으로 128 비트의 수를 정의한다. 이 수를 RSA 암호화 작업을 통해서 암호화한다. 
3. 암호화된 수의 LSB 896 비트를 알려주고, 그 앞의 128 비트는 state가 된다. 
4. 이 state 를 다시 한번 암호화하고, 그 암호화된 수를 맞추게 되면 FLAG 가 출력된다. 

 

따라서, 결국 마지막의 encrypt 된 수를 맞추기 위해서는 random 수를 알거나, state 를 알아내야 한다는 소리가 된다. 

💡 Main Idea

여기서 우리는 e 를 조작할 수 있기 때문에, 다양한 특수한 e 들을 설정함으로써 state 를 복구하거나, 암호문을 악의적으로 고정시킬 수 있게 된다. 예를 들어서, e 가 $\frac{(p-1) \times (q-1)}{phi(p-1, q-1)} + 1$ 이라고 생각해보자. 

 

그렇게 되면 $ random^{\frac{(p-1) \times (q-1)}{phi(p-1, q-1)} + 1} = random \text{ (mod n) }$ 라는 식이 성립하게 되고, 따라서 state 는 0 이 되기 때문에 2번쨰 암호화를 거친 수 또한 0 이 되게 된다. 

 

하지만, 여기서 문제가 발생하는데, 

    assert "3141592653589793238462643383279502884197169399375105820974944592307816406286" in str(e) # first digits of pi - nothing up my sleeve!

라는 구문 때문이다. e 가 항상 저런 string 을 포함해야 하기 때문에, 이를 만족하는 p 와 q 를 찾기에는 뭔가 너무 힘들 것 같다는 생각이 들었다. (나중에 알았지만 어떤 분은 이런 e 를 찾아내서 문제를 해결했다.. 참 대단한 사람이 많은듯)

 

그래서 다른 방법을 찾아보던 중,, 디스코드에 힌트를 얻어 $e = k \times (p-1) + 1$ 이라는 방정식을 보게 되었다. 이 방정식 대로라면, 1번째 암호화 후에 나오는 값을 p 로 나눈 결과, random 값과 동일한 것을 알 수 있다. 따라서

 

$$random^e = state \times 2^{896} + output \text{ (mod n)}$$

$$random^e = state \times 2^{896} + output = random \text{ (mod p)}$$

$$ state \times 2^{896} + output = random + p \times k$$

 

라는 식으로 유도할 수 있게 되고, output, p, 2^896 모두 512 비트를 넘어서고, random 과 state 가 128 비트이기 때문에 다른 수들에 비해서 trivial 한 값임을 예측할 수 있다. 

 

이는 곧 LLL 로 풀 수 있다는 의미가 된다 ㅎㅎ,, 

 

$$\begin{bmatrix}
output & 1 & 0\\ 
2^{896} & 0 & 1\\ 
p & 0 & 0
\end{bmatrix}$$

 

솔직히 말해서 LLL을 사용하기 위해서 어떻게 행렬을 구성했냐고 물어보면 설명은 못할 것 같은데, 이 ouput 을 1번만 사용하도록 하기 위해서 1번쨰 열에 둔 것이 전부이긴 하다. 

 

따라서 이를 LLL 을 사용하게 되면, matrix[0][2] 가 state 를 의미하지 않을까? 라는 생각이 든다 !! (그리고 이게 맞았다 ㅎㅎ)

📖 Exploit Code

from pwn import *
from Crypto.Util.number import *
import random as rand
from sage.all import *

str_e = "3141592653589793238462643383279502884197169399375105820974944592307816406286"
str_n = "12718281828459045235360287471352662497757247093699959574966967627724076630353"

REMOTE = 1
if REMOTE:
    io = remote("20.196.200.237", int(2580))
else:
    io = process(["python3", "chal.py"])


def validate(p, q, e, n):
    try:
        assert isPrime(p) and isPrime(q)
        assert p.bit_length() == 512
        assert q.bit_length() == 512
        assert p != q
        assert GCD(e, (p - 1) * (q - 1)) == 1
        assert 65537 < e < (p - 1) * (q - 1) - 65537
        assert "3141592653589793238462643383279502884197169399375105820974944592307816406286" in str(e) # first digits of pi - nothing up my sleeve!
        assert "2718281828459045235360287471352662497757247093699959574966967627724076630353" in str(n) # first digits of E - nothing up my sleeve!
        return True
    except:
        return False

p = getPrime(512)
n = int(str_n)

i = 0
while True:
    if n * pow(10, i) >= pow(2, 1022):
        break
    i += 1

n *= pow(10, i)
q = n // p

while True:
    if isPrime(q):
        break
    q += 1

e = int(str_e)
i = 0
while True:
    if pow(10, i) > p:
        break
    i += 1

e *= pow(10, i)
plus = p - (e % (p-1))
e += plus

'''
p = 12146486317742316926919276981541234437965175905093155495112585959171041099014267329502753672418049854810701245876305871689259742461855803796250644992553141
q = 10470749726101044731813917707155981933181747378557820252001229062060409450551277866476393147475010454339485723979538628227409565217845800185712909902470049
e = 314159265358979323846264338327950288419716939937510582097494459230781640628611860201113293950942162800938871593187899666194773084736049918567749607350762590729495850091046470790868563012802430503219995348817835677768261807906702441
'''

assert e % (p-1) == 1
assert validate(p, q, e, p * q) == True

def inc_state(state):
    next_z = pow(state, e, p*q)
    next_out = next_z % (1 << 896)
    next_state = next_z >> 896
    return next_out, next_state

io.sendline(str(p).encode())
io.sendline(str(q).encode())
io.sendline(str(e).encode())
io.recvuntil(b"First Outputs\n")
output = int(io.recvline().strip().decode())

res = output % p

M = matrix([
    [res, 1, 0],
    [pow(2,896), 0, 1],
    [p, 0, 0],
])

M = M.LLL()
small_2 = -int(M[0][2])
ans1, ans2 = inc_state(small_2)

io.sendline(str(ans1).encode())
io.sendline(str(ans2).encode())

io.interactive()

추가적으로 설명하자면, $ e = k \times (p-1) + 1$ 로 정의하고, e 에 주어진 string 이 존재하기 위해서, e 의 윗쪽 digit이 주어진 string 이 되게 하면, mod p-1 을 했을 때 나머지가 1 이 나오기 위해서 추가적으로 더 더해주는 수가 있더라도 윗쪽 digit 이 바뀌지 않게 된다. 

 

따라서 p 와 q 만 정의해주면 다음과 같이 문제를 해결할 수 있었다 !!