[Zer0pts 2023] - squarerng

이번 대회는 CyKor 에서 전통적으로 1 ~ 3 등을 항상 가져왔다는 그 대회이다. 이런 전통이 있는 만큼 스스로도 열심히 해보자 !! 라고 마음을 먹게 되기도 했고, 생일을 맞이하는 대회 느낌이라 더욱 열심히 하려고 했다. 예전에 RBTree 님의 블로그에서 Zer0pts 문제들을 보고 GF, Polynomial 등을 이해하고 공부했던 경험이 있기 때문에 뭔가 조금 친숙한 대회였던 것 같다.

 

대회 당시에는 CyKor 사람들이 너무나 문제를 빠르고 잘 풀어서 이미 풀린 문제를 볼 이유가 없었기 때문에 본 문제가 많지는 않지만, 대회가 종료된 시점에서 다시 여러 문제들을 스스로 풀어보는 중이다.

🖲️ Code Analysis

#!/usr/bin/env python3
import os
from Crypto.Util.number import getPrime, getRandomRange

def isSquare(a, p):
    return pow(a, (p-1)//2, p) != p-1

class SquareRNG(object):
    def __init__(self, p, sa, sb):
        assert sa != 0 and sb != 0
        (self.p, self.sa, self.sb) = (p, sa, sb)
        self.x = 0

    def int(self, nbits):
        v, s = 0, 1
        for _ in range(nbits):
            self.x = (self.x + 1) % p
            s += pow(self.sa, self.x, self.p) * pow(self.sb, self.x, self.p)
            s %= self.p
            v = (v << 1) | int(isSquare(s, self.p))
        return v

    def bool(self):
        self.x = (self.x + 1) % self.p
        t = (pow(self.sa, self.x, self.p) + pow(self.sb, self.x, self.p))
        t %= self.p
        return isSquare(t, self.p)

p = getPrime(256)

sb1 = int(input("Bob's seed 1: ")) % p
sb2 = int(input("Bob's seed 2: ")) % p
for _ in range(77):
    sa = getRandomRange(1, p)
    r1 = SquareRNG(p, sa, sb1)
    print("Random 1:", hex(r1.int(32)))
    r2 = SquareRNG(p, sa, sb2)
    print("Random 2:", hex(r2.int(32)))

    guess = int(input("Guess next bool [0 or 1]: "))
    if guess == int(r1.bool()):
        print("OK!")
    else:
        print("NG...")
        break
else:
    print("Congratz!")
    print(os.getenv("FLAG", "nek0pts{*** REDACTED ***}"))

코드 자체는 매우 간단한 문제이다. 대충 중요한 부분만 설명하자면, SquareRNG 라는 객체를 이용해서 주어진 정수들에 대한 값을 일련의 계산을 통해서 이차 잉여인지를 나타내어준다. $int$ 함수의 경우에는 32번 반복하여 32 비트로써 이를 알아낼 수 있게 해준다. 

 

$ f(sb, n) = 1 + sa^1sb^1 + sa^2sb^2 + \cdots + sa^nsb^n $ 꼴에 해당하는 식들의 이차 잉여를 계산할 수 있다는 말과 같다. 

 

전체적인 코드의 진행을 살펴보면 다음과 같다.
 
1. 정해진 소수 $P$ 에 대해서 주어진 정수 $sa$ 를 통해, 입력한 $sb1, sb2$ 를 이용해 $f(sb1, 1 \cdots 32), f(sb2, 1 \cdots 32)$ 를 알려준다. (32 비트로 표현함으로써 알 수 있다. )

2. 주어진 데이터들을 통해서 $sa^{33} + sb1^{33}$ 이 이차 잉여인지를 판단한다. 

3. 이 과정을 77번 동안 모두 통과하게 되면 $flag$ 를 구해낼 수 있다. 

💡 Main Idea

먼저, $sa^{33} + sb^{33}$ 의 값이 이차 잉여인지를 판단할 수 있는 방법은 총 2가지로 볼 수 있다. 하나는 P, sa, sb 를 모두 구해내서 이 수가 정말 이차 잉여인지 판단하는 방법, 그리고 두번째 방법은 $sa^{33} + sb^{33}$ 을 인수분해가 가능하게 만들어서 각각이 이차 잉여인지 판단하는 방법이다. (르장드르 기호는 곱셈 연산이 성립한다.)

 

르장드르 기호 - 위키백과, 우리 모두의 백과사전

 

누가봐도 sa, sb, P 를 모두 구하는 것보다는 두번째 방법이 훨씬 쉽다는 것을 알 수 있을 것이고, 256 비트나 되는 P를 구해내기는 정말 쉽지 않을 것이다. 따라서 $sa^{33} + sb^{33}$ 을 인수분해 가능하게 만들어야 한다는 것이 핵심이다. 또, 그 와중에 f(sb, n) 꼴로 표현이 되게끔 하면 아주 기분좋은 풀이가 될 수 있을 것이다. 

 

눈치가 빠른 사람이라면 이미 어떻게 인수분해를 해야 하는지 알 것이라고 생각한다. 

$$ sa^{33} + (-1)^{33} = (sa - 1) \times (sa^{32} + sa^{31} + \cdots + sa + 1)$$ 로 인수분해가 되기 때문에 충분히 $sb1, sb2$ 에 1, -1 을 대입한다면 역연산해낼 수 있을 것이다 !!

📖 Exploit Code

from pwn import *
from tqdm import *

# context.log_level = "debug"

REMOTE = 1
if REMOTE:
    io = remote("crypto.2023.zer0pts.com", 10666)
else:
    io = process(["python3", "server.py"])

sb1, sb2 = 1, -1
io.sendlineafter(b"Bob's seed 1: ", str(sb1).encode())
io.sendlineafter(b"Bob's seed 2: ", str(sb2).encode())

for _ in trange(77):
    io.recvuntil(b"Random 1: ")
    res1 = int(io.recvline().strip().decode(), 16)
    io.recvuntil(b"Random 2: ")
    res2 = int(io.recvline().strip().decode(), 16)

    res1 = res1 >> 31
    res2 = res2 & 1
    
    ans = res1 ^ res2 ^ 1

    io.sendlineafter(b"Guess next bool [0 or 1]: ", str(ans).encode())

io.interactive()

이렇게 -1 을 $sb$ 로 넣어주면 1번째 비트가 $1 - sa$ 의 이차 잉여 여부를 알려줄 것이고, 1 을 넣어줄 때의 msb가 $ 1 + sa + sa^2 + \cdots + sa^{32}$ 의 이차 잉여 여부를 알려줄 것이다. 

 

따라서 이 둘을 곱한 후에 XOR 1 로 비트 반전을 하게 되면 결국 우리가 원하는 식이 나오게 된다. ( 여기서 둘을 곱했을 때의 식은 $ 1 - sa^{33}$ 이 되기 때문에 -1 이 비이차잉여라고 가정하고 비트를 반대로 보내주게 된다.)