티스토리 뷰
크립토 첫번째 과제 레츠기릿~~
#!/usr/bin/env python3
from random import randint
import sys
flag = "FLAG{FAKE_FLAG}"
def die(*args):
pr(*args)
#quit()
def pr(*args):
s = " ".join(map(str, args))
sys.stdout.write(s + "\n")
sys.stdout.flush()
def sc():
return sys.stdin.readline().encode()
def did(n, l, K, A):
A, K = set(A), set(K)
R = [pow(_, 2, n) + randint(0, 1) for _ in A - K]
return R
def main():
#NOT ESSENTIAL#
border = "+"
pr(border*72)
pr(border, ".:: Hi all, she DID it, you should do it too! Are you ready? ::. ", border)
pr(border*72)
#NOT ESSENTIAL#
_flag = False
n, l = 127, 20
N = set(list(range(0, n)))
K = [randint(0, n-1) for _ in range(l)]
cnt, STEP = 0, 2 * n // l - 1
while True:
ans = sc().decode().strip()
try:
_A = [int(_) for _ in ans.split(',')]
print("K", K)
if len(_A) <= l and set(_A).issubset(N):
DID = did(n, l, K, _A)
pr(border, f'DID = {DID}')
print("set(_A) : ", set(_A))
print("set(K) : ", set(K))
if set(_A) == set(K):
_flag = True
else:
die(border, 'Exception! Bye!!')
except:
die(border, 'Your input is not valid! Bye!!')
if _flag:
die(border, f'Congrats! the flag: {flag}')
if cnt > STEP:
die(border, f'Too many tries, bye!')
cnt += 1
if __name__ == '__main__':
main()문제 전문 + 코드(로컬에서 실행되도록 일부 수정)
문제를 내가 이해한 바로 간단히 정리해보면
A. 1부터 126까지의 숫자 중 중복을 허용한 20개를 골라 그 숫자들이 포함된 집합 K를 정의한다. (이 때, | K | ≤ 20)
B. 사용자에게 숫자 집합 I를 입력받는다. (이 때, 0 < | I | < 20)
C. I - K (K와 I의 차집합)의 각 원소에 대해 제곱하고 127로 모듈러를 돌린 후 랜덤하게 0 또는 1을 더해 사용자에게 반환한다.
D. I == K이면 flag를 출력하고 아니면 B~C를 최대 11번 반복한다.
결국 I 를 적절히 보내 K를 추론해내야 한다.
1부터 8까지를 보낸 결과이다. 공집합이 반환된 3, 4, 5가 K의 원소임을 알 수 있다. (K의 원소라면 차집합에서 소거되므로)
그럼 이제, 정해진 제약(1회당 최대 20개의 정수를 최대 11번에 걸쳐 검사할 수 있음) 안에 해당 집합 K를 찾아내면 된다... 됐었다...
그냥 for문 돌리면서 숫자들 보내고, ((보낸값)^2%127) 또는 ((보낸값)^2%127) + 1이 DID에 있는지 보면 된다고 생각했는데... 분명히 그렇게 해서 추석 때 풀었는데... 재현이 안되는거다!!
이유를 분석해보니, DID의 원소 충돌 문제가 있었다.
어떤 두 수 a, b에 대해 (a^2)%127 = (b^2)%127 = m이라 하자.
a ∈ K이면서 b ∉ K일 때, 내가 보내는 페이로드에 a와 b가 모두 포함되면 집합 DID에는 m이 포함되므로 a는 K에 포함되지 않는다고 인식된다는 것이다.
이 문제를 해결하기 위해서 두가지 해결책을 시도해보았다.
1. I를 입력하는 순서와 연산 결과를 출력하는 순서가 일치한다고 (더 작은 입력값의 연산 결과가 앞에 출력) 간주하고 DID의 원소를 선형적으로 검사 (순서에 따라 검사하면 앞뒤의 값을 통해 진짜인지 판별 가능하기 때문)
=> 간주했던 전제가 거짓이었다. 어느 정도의 일관성은 있었으나, 항상 보장되지 않아 실패했다.
2. 충돌에 대해 최적화, 또는 충돌 검사
=> 원래 0부터 차례대로 20개씩 묶어서 검사를 돌렸는데, 이러니까 번번히 충돌나는 쌍이 몇개 있었다. 짝수끼리 검사, 홀수끼리 검사하는 식으로 바꾸니까 그런 충돌은 좀 줄었다. 그래도 충돌 나는 친구들이 있어서 그 값들을 따로 저장하고 다시 검증할 수 있게 코드를 작성했다.
최종적으로 작성한 코드는 아래와 같다.
from pwn import *
import time
def nsend(text, lp = None, end="\n"):
if not lp:
global p
lp = p
lp.send((str(text)+end).encode())
def nrecv(e = None, lp = None, strip = False):
if not lp:
global p
lp = p
data = ""
if not e:
data = lp.recv(1024).decode()
else:
data = lp.recvuntil(str(e).encode()).decode()
return data[:-1] if strip else data
#initialization
p = remote("115.85.183.207", 10007)
#time.sleep(1)
print(nrecv())
#check special case (0)
nsend("0")
nrecv("DID = ")
DID = eval(nrecv(strip = True))
KEYS = []
notKEY = []
if not DID:
notKEY.append(0)
start = 0
n = 127
COLLISION_BOX = [[], [], []]
COLLISION_IDX = 0
while start < 120:
end = start+40
cnt = 0
payload = ",".join([str(x) for x in range(start, (end if end < 120 else 120), 2)])
print("payload :", payload)
nsend(payload)
nrecv("DID = ")
DID = eval(nrecv(strip = True))
print(f"<{len(DID)}> {DID}")
for i in range(start, (end if end < 120 else 120), 2):
if pow(i, 2, n) not in DID and pow(i, 2, n) + 1 not in DID:
print(i, end=",")
KEYS.append(i)
cnt += 1
else:
if DID.count(pow(i, 2, n)) > 1 or DID.count(pow(i, 2, n) + 1) > 1:
COLLISION_BOX[COLLISION_IDX].append(i)
COLLISION_IDX = (COLLISION_IDX + 1) % 3
print("\n",cnt)
start = end
start = 1
while start < 120:
end = start+40
cnt = 0
payload = ",".join([str(x) for x in range(start, (end if end < 120 else 120), 2)])
print("payload :", payload)
nsend(payload)
nrecv("DID = ")
DID = eval(nrecv(strip = True))
print(f"<{len(DID)}> {DID}")
for i in range(start, (end if end < 120 else 120), 2):
if pow(i, 2, n) not in DID and pow(i, 2, n) + 1 not in DID:
print(i, end=",")
KEYS.append(i)
cnt += 1
else:
if DID.count(pow(i, 2, n)) > 1 or DID.count(pow(i, 2, n) + 1) > 1:
COLLISION_BOX[COLLISION_IDX].append(i)
COLLISION_IDX = (COLLISION_IDX + 1) % 3
print("\n",cnt)
start = end
print()
start=120
end=start+20
payload = ",".join([str(x) for x in range(start, (end if end < 127 else 127))])
print("payload :", payload)
nsend(payload)
nrecv("DID = ")
DID = eval(nrecv(strip = True))
print(f"<{len(DID)}> {DID}")
for i in range(start, (end if end < 127 else 127)):
if pow(i, 2, n) not in DID and pow(i, 2, n) + 1 not in DID:
print(i, end=",")
KEYS.append(i)
cnt += 1
print()
for BOX in COLLISION_BOX:
payload = ",".join([str(x) for x in BOX])
print("payload :", payload)
for i in BOX:
print(f" |{i}, {pow(i, 2, n)}| ", end=" ")
print()
nsend(payload)
nrecv("DID = ")
DID = eval(nrecv(strip = True))
print(f"<{len(DID)}> {DID}\n")
for i in BOX:
if pow(i, 2, n) not in DID and pow(i, 2, n) + 1 not in DID:
KEYS.append(i)
print(len(KEYS), KEYS)
nsend(",".join([str(x) for x in KEYS]))
print(nrecv())
nsend("")
print(nrecv())nsend, nrecv는 매번 인/디코딩도 귀찮고 개행 소거 등등 좀 편하게 만드려고 추가했다.
첨엔 예쁘게 짜려고 했는데 콜리젼 잡고 버그 잡고 하다 보니까 쓸데없이 좀 많이..? 길어졌다.
사실 페이로드 정하고 이중 포문 도는게 핵심.
중간에 콜리젼 나는지 검사해서 COLLISION_BOX에 저장해주고, 메인 포문 2개(짝, 홀)가 끝나면 걔네에 대한 검사를 해준다.
근데 이래도 충돌 안잡히는게 꽤 많이 있다.
충돌 나는 쌍이 많으면 11번 안에 검사하기에 다 나눠서 검사를 못해서 그런 듯 하다.
한 4번 ~ 10번 돌려주면 랜덤하게 풀린다ㅋㅋㅋ
어쩌면 눈으로 계산하는게 더 빨랐을지도... (추석에 풀 때 운이 지지리도 좋아서 콜리젼이 안나는 쌍만 있었나보다)
무튼, pwned!
'WRITE-UP > 크립토스터디(KERT)' 카테고리의 다른 글
| [KERT_Crypto_Study] 과제 "Compact XORs" 풀이 (0) | 2023.11.09 |
|---|