이번에 푼 문제는 종강하고 문제를 좀 풀다가 난이도가 높은 문제 한번 풀어보자는 도전에 가까웠다.
근데 문제를 해석하다보니 암호학의 깊이보다는 알고리즘 구현의 깊이가 좀 더 중요한 문제로 느껴졌다.
일반적인 알고리즘 문제처럼 제한시간이 1초 이렇게 짧은 것도 아니니 몇시간이 걸리더라도 풀 수만 있으면 되겠다고 판단하고 호기롭게 코드를 짰다.
하지만 처음에 짠 코드는 대략 100분 정도면 계산을 완료할 것으로 예상되었는데 약 1시간 20분 정도면 문제 서버가 닫혀서 결국 알고리즘을 개선할 필요가 있었다.
더 자세한 내용은 차차차 보도록 하자.
문제 분석
문제에서 제공하는 코드는 아래와 같다.
import os
import hashlib
BSIZE = 26
def pad(s):
padlen = BSIZE-len(s)%BSIZE
return s+bytes([padlen])*padlen
L = 286
message = os.urandom(L).hex()
while True:
inp = input(">>> ")
if inp.strip() == "Yo Bro I got the answer":
break
output = ""
s = set(inp)
for c in message:
if c in s:
pass
else:
output += c
output = pad(output.encode())
out_len = len(output)
nonce = os.urandom(32)
out = ""
for i in range(0,out_len,BSIZE):
h = hashlib.sha256(output[i:i+BSIZE]+nonce).hexdigest()
out += h
print(f"Nonce = {nonce.hex()}")
print(f"Output = {out}")
answer = input("Answer >>> ")
if answer == message:
with open("flag.txt","r") as f:
print(f.read())구하는 거
큰 맥락을 보면 message를 추측해내면 되고, message는 286byte의 random 값을 16진수로 나타낸 것이다.
즉, message는 ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f']로 이루어진 572자의 문자열이다.
힌트
while문을 보면, 답을 알겠으면 "Yo Bro I got the answer"을 입력하라고 한다.
while문 내부의 for문은 message의 572자 중 내가 한 라운드에서 입력한 inp의 구성 문자열과 겹치지 않는 문자들을 순서대로 모은다.
그리고 이것을 BSIZE크기만큼 블럭으로 쪼개서 각각 nonce와 더해서 생성한 해시값을 단순하게 쭉쭉 더해서 h로 만들어 out으로 내놓는다.
해시 알고리즘이 SHA256이므로 해쉬 각 블럭은 64자릿수를 가진 16진수다.
뭐 요정도 알고 풀이로 가보자.
풀이
일단 가장 큰 히트는 힌트에서 말한 for문의 알고리즘이었다.
간단한 예시를 들어보자면 내가 inp로 23456789abcdef를 입력하면 output은 message 중 0, 1로 구성된 부분만을 쏙 빼내서 해시값을 보여준다.
그 해시값마저도 각 블럭들이 CBC mode처럼 혼돈상태도 아니고 독립적이니 길이가 26인 블럭에 대해서 브루트포싱을 진행하면 되는 것이다.
두 문자의 조합에 대해서만 계산한다면 천만단위면 간단한 계산의 경우 1초도 걸리지 않기에 굉장히 할만하다고 생각했다.
구하기 순서
처음에는 inp로 16개의 문자 중 하나의 문자만을 제외하고 입력을 16번 진행했다.
이를 통해서 각 문자들이 572개 중 몇번 등장하는지 알아낼 수 있다.
정답을 구한 프로세스에서는 아래와 같은 문자 구성을 얻었다.
[48, 34, 34, 37, 39, 36, 37, 38, 29, 40, 30, 37, 31, 31, 34, 37]
시행착오
이제 0과 1은 어떤 순서로 배열되어 있을지 따져보고,
그 후 temp_ans(생성된 큰 문자열)에다가 2를 섞고 3을 섞고 해서 마지막에 f까지 섞는 상상을 하고 코드를 짰었다.
코드를 실행해보니 시간이 너무 오래걸려 서버가 닫히기 전까지 도저히 안됬었다.
극복(?)
근데 생각해보면 random함수를 이용해 생성한 message이므로 모든 문자가 어느 정도 균형있게 나올 것이다.
그리고 나는 temp_ans에다가 계속 문자를 한 종류씩 섞는 작업을 진행하고 있기에 통계적으로 한 다여섯개의 문자를 이용해 큰 문자를 만드는 과정부터는 길이 26의 블럭에 한 종류의 문자가 한 4-5개 정도 들어간다.
그니까 결국 문자의 조합을 생각할 때, temp_ans에다가 섞으려고 하는 한 종류의 문자가 1개가 등장하는 블럭의 조합, 2개가 등장하는, 3개가 등장하는 이렇게 낮은 숫자부터 차차 높여가면 통계적으로 5개의 문자를 섞어 temp_ans를 만든 순간부터는 블럭 하나를 검증하는데 걸리는 시간이 굉장히 줄어든다.
이 방식의 경우 temp_ans에 섞인 문자열이 많을수록 블럭 검증과정이 기하급수적으로 빨라지는 결과를 일으켜서 실제 문제 해결시에도 초반에 10분이 걸리고 6번째 루프부터는 10초도 걸리지 않아 끝났다.
코드 간략히
def backtrack(which, start, length, num, ..., hash, nonce):
if(found_answer):
return True
if(len(word_list) >= num):
...
for i in range(length):
...
if(i == word_list[idx]):
candidate += comp[which] #섞을거 넣기
idx += 1
else:
candidate += temp_ans[one]
one += 1
temp = gen_hash(candidate, nonce)
if(temp == hash):
...
return True
return False
for j in range(start, length):
word_list.append(j)
if backtrack(which, j + 1, length, num, ..., hash, nonce):
return True
word_list.pop()
if(found_answer):
return True
return False
def block_verify(which, ..., word_num, length, hash, nonce):
for i in range(min(word_num, length)+1): #섞으려는 문자 수
if(found_answer):
return
...
if backtrack(which, 0, length, i, ... , hash, nonce):
return
for i in range(1, 16): #하나씩 다 비교교
inp = ""
for j in range(i+1, 16):
inp += comp[j]
...
nonce = io.recvline()
hash = io.recvline()
...
while(length> 0):
hash_part = hash[cnt*HSIZE : (cnt+1)*HSIZE]
if(length >= BSIZE):
block_verify(i, ... , word[i], BSIZE, hash, nonce)
else:
block_verify(i, ... , word[i], cand, hash, nonce)
length -= BSIZE
cnt += 1최대한 핵심만 써놨는데 역시 더럽다...
구현 화이팅!
