[*CTF Writeup] Crypto - GuessKey2

문제 설명

from random import randint
import os
from flag import flag
N=64
key=randint(0,2**N)
# print key
key=bin(key)[2:].rjust(N,'0')
count=0
while True:
    p=0
    q=0
    new_key=''
    zeros=[0]
    for j in range(len(key)):
        if key[j]=='0':
            zeros.append(j)
    p=zeros[randint(0,len(zeros))-1]
    q=zeros[randint(0,len(zeros))-1]
    try:
        mask=int(raw_input("mask:"))
    except:
        exit(0)
    mask=bin(mask)[2:]
    if p>q:
        tmp=q
        q=p
        p=tmp
    cnt=0
    for j in range(0,N):
        if j in range(p,q+1):
            new_key+=str(int(mask[cnt])^int(key[j]))
        else:
            new_key+=key[j]
        cnt+=1
        cnt%=len(mask)
    key=new_key
    try:
        guess=int(raw_input("guess:"))
    except:
        exit(0)
    if guess==int(key,2):
        count+=1
        print 'Nice.'
    else:
        count=0
        print 'Oops.'
    if count>2:
        print flag

처음에 무작위 64비트로 key가 정해진다. 매 시행마다 다음과 같은 작업을 반복할 수 있다. 0과 비트가 0인 인덱스의 집합을 zeros라고 하자. 이때 프로그램은 zeros에서 무작위 수 p, q를 골라 이를 범위 [p, q]로 삼는다. 당신은 정확히 64비트인 mask를 프로그램에 입력으로 줄 수 있다(64비트가 아니어도, 64비트를 입력한 것과 동일하게 동작하도록 구성되어 있다). 그러면 프로그램은 범위 안의 각 인덱스 i에 대해 key[i] ^= mask[i] 를 수행한다. 그 이후 당신은 현재 key의 값을 맞출 기회가 한 번 있다. 이를 세 번 연속해서 맞추면 플래그를 얻을 수 있다.

문제 풀이

가장 먼저 해야 하는 접근은 프로그램이 고른 인덱스 p와 q는 높은 확률로 둘 다 0이라는 것이다. 가장 왼쪽에 있는 0인 비트 L과 가장 오른쪽에 있는 0인 비트 R이 있다고 하자. 그러면 L보다 왼쪽에 있는 비트는 높은 확률로 골라지지 않을 것이고, R보다 오른쪽에 있는 비트는 1의 확률로 골라지지 않을 것이다. 그렇다면, 우리가 mask를 모든 비트가 1인 64비트 수로 두고 시행을 반복했을 때 R-L은 어떻게 변할까? 프로그램이 p와 q로 L 또는 R을 고른다면 R-L은 1 이상 줄어들 것이고, 고르지 않는다면 R-L은 유지될 것이다. 이때 L 또는 R을 고를 확률은 현재 0인 비트 개수의 역수에 비례하고, 이는 우리가 시행을 무한정 반복할 수 있다는 것을 고려해 볼 때 절대 낮지 않다. 따라서 우리는 프로그램이 p=0을 골라 트롤하지 않으면서 p 또는 q로 L 또는 R을 골라 R-L을 매우 작게 줄일 때 까지 기다릴 수 있다. 그러면 R-L=0이 되는 순간 모든 비트를 1로 만들 수 있고, 결과적으로 답을 맞출 수 있다.

한 번 답을 맞춘 후에는 mask를 0으로 놓으면 어떤 경우에도 key가 바뀌지 않는다. 똑같은 답을 두 번 더 제출하면, 플래그를 얻을 수 있다.

소스 코드

from pwn import remote

rm = remote('52.163.228.53', 8082)

cnt = 0
while True:
    rm.recvuntil(":")
    rm.sendline(str((1<<64)-1).encode())
    rm.recvuntil(":")
    rm.sendline(str((1<<64)-1).encode())

    r = rm.recvline()
    if r == b'Nice.\n':
        break

print('Success')
for _ in range(2):
    rm.recvuntil(":")
    rm.sendline(str(0).encode())
    rm.recvuntil(":")
    rm.sendline(str((1 << 64) - 1).encode())


rm.interactive()