[🥇 Gold 1] 27455번 반복되는 누산도 결국 선형이다 — DreamHack multipoint 풀이 (2번 보류 끝에 해결)

문제: DreamHack — multipoint 분류: Reversing 난이도: 🥇 Gold 1 FLAG: DH{Poly_m0ly_mult1pl1c4t1on_m0dular~!}

이 문제는 사실 이번이 세 번째 시도다. 지난 두 세션 모두 "알고리즘을 잘못 읽은 것 같다"는 결론을 내리고 보류했었다. 결과적으로 그 결론 자체가 틀렸다 — 알고리즘을 읽은 건 처음부터 맞았고, 문제는 그 알고리즘이 도는 횟수를 두 번 다 과소평가하고 중간에 스캔을 멈춘 것이었다. 오늘은 그 실수를 정면으로 다시 확인하고, 진짜 구조를 끝까지 읽어서 풀었다.

문제 개요

file과 checksec부터 확인했다. PIE, 풀 RELRO, 스택 카나리, NX — 특별할 것 없는 기본 보호기법 조합의 x86-64 바이너리다. Strip돼 있어 심볼은 없다.

main을 objdump로 열어보면 로직 자체는 짧다. read()로 정확히 39바이트(0x27)를 입력받고, 39가 아니면 즉시 실패 메시지를 찍고 종료한다. 39바이트를 다 받으면 어떤 루프를 돌려 38바이트짜리 버퍼(buf1)를 채우고, 그걸 0x21bd60 위치의 38바이트 정답값과 memcmp로 비교한다. 그 비교가 통과하면 Correct, 아니면 다른 메시지가 나온다 — 전형적인 "입력 → 결정론적 변환 → 목표값과 비교" 구조다.

관건은 그 "결정론적 변환"이 정확히 뭘 하느냐였다. 루프 본문을 하나씩 따라가면서 주석을 달았다.

정리하면 루프 한 번(레코드 하나)이 하는 일은 이렇다.

f0, f1, f2, f3 = table[i*4 .. i*4+3]        # 레코드 4바이트
buf1[f0] = (buf1[f0] + f3 * input[f1] * table3[f2]) % 251
i += 1

그리고 종료 조건은 "정해진 횟수만큼"이 아니라 다음 레코드 4바이트를 32비트 정수로 읽었을 때 그게 0이면 멈춘다였다. 첫 세션에는 이걸 "39번 고정 반복"으로 잘못 짚었었고, 두 번째 세션에서 이 부분은 바로잡았다. 문제는 그다음이었다.

▶🕳️ 삽질 — 테이블이 이상한 게 아니라 정말 그만큼 컸다

종료 조건을 바로잡고 나서, "그럼 실제로 몇 개의 레코드가 있는지" 확인하려고 파일에서 테이블 시작 주소(0x201020)부터 4바이트씩 읽으며 all-zero 레코드를 찾는 스크립트를 돌렸다. 처음엔 1000개 레코드(4000바이트)만 훑어봤다.

Copy

for i in range(1000):
    off = table_off + i*4
    if struct.unpack('<I', data[off:off+4])[0] == 0:
        found = True
        break

1000개를 훑어도 종결 레코드가 하나도 안 나왔다. 여기서 "이건 뭔가 이상하다 — 진짜 이렇게 큰 테이블일 리가 없다, 내가 주소를 잘못 짚었거나 레코드 구조를 오독한 게 분명하다"고 판단해버렸다. 그 판단을 근거로 GDB에서 실제 실행 중인 buf1 값을 임의 입력(input[i] = i+1)에 대해 찍어보고 내 파이썬 모델의 예측값과 비교했는데, 완전히 다른 값이 나왔다. 이 불일치를 "알고리즘 모델 자체가 틀렸다"는 증거로 받아들이고 두 번째 세션도 그대로 보류했다.

돌이켜보면 이 GDB 비교 자체가 잘못된 실험이었다 — 애초에 모델이 "39번만 반복한다"고 (암묵적으로) 가정한 채로 만든 예측값과 실측을 비교했으니, 루프가 실제로는 훨씬 더 길게 도는 이상 안 맞는 게 당연했다. 진짜 원인은 알고리즘을 잘못 읽은 게 아니라 스캔을 중간에 멈추고 "이상하다"는 감(感)을 근거로 결론을 내려버린 것이었다.

이번엔 그 의심을 버리고 스캔을 끝까지 이어갔다. table3가 시작되는 주소(0x21bd20)까지 파일을 있는 그대로 계속 읽었더니, 정확히 i=27455에서 진짜 종결 레코드(4바이트 모두 0)가 나왔다. table 시작부터 table3 시작까지의 간격은 109824바이트 — 27455 × 4 + 4(종결 레코드) 와 정확히 일치한다. 테이블은 이상한 게 아니라, 정말로 그만큼 컸을 뿐이었다.

참고로 이 바이너리는 GDB로 다룰 때도 한 가지 더 함정이 있었다 — PIE 베이스가 통상 가정하는 0x555555554000이 아니라 .text는 0x555555400000, .data는 0x555555600000으로 따로 로드된다(.data가 별도의 큰 LOAD 세그먼트를 요구할 만큼 크기 때문). 파일 오프셋 그대로 브레이크포인트를 걸면 곧바로 실패한다.

이번 풀이 자체엔 결국 GDB가 필요 없었지만(파일에서 직접 읽어 정적으로 풀렸다), 이 바이너리를 다시 만질 일이 있다면 info proc mappings부터 확인해야 한다는 걸 다시 한번 확인한 셈이다.

💣 핵심 — 27455번 누산돼도, 계수가 상수면 그냥 선형이다

레코드 하나의 연산을 다시 보자.

buf1[f0] += f3 * input[f1] * table3[f2]     (mod 251)

여기서 f0, f1, f2, f3는 전부 테이블에 박혀 있는 고정 바이트고, table3[f2]도 파일 안의 정적 룩업 테이블 값이다. 즉 f3 * table3[f2]는 매 레코드마다 컴파일 시점에 이미 정해진 하나의 상수다. 이 상수를 c라고 하면 레코드 하나가 하는 일은 결국 buf1[f0] += c * input[f1] 뿐이다 — input[f1]에 대해 완전히 1차식이다.

mod 251은 덧셈에 분배된다((a+b) mod n = ((a mod n) + (b mod n)) mod n이 반복 적용되므로). 그러니 27455번을 도는 동안 중간에 매번 mod를 취하든, 다 더한 다음 마지막에 한 번만 mod를 취하든 최종 결과는 같다. 결국 buf1[f0]의 최종값은 그 f0를 대상으로 하는 모든 레코드의 c * input[f1] 항을 전부 더한 것과 같다.

이건 정확히 행렬-벡터 곱이다.

buf1 = M · input   (mod 251)

여기서 M은 38×39 행렬이고, M[f0][f1]은 "그 (f0, f1) 조합을 갖는 모든 레코드의 f3 * table3[f2] 값을 다 더한 것"이다. 27455개 레코드를 한 번 순회하며 이 행렬을 그대로 조립할 수 있다.

M = [[0]*39 for _ in range(38)]
i = 0
while True:
    rec = data[table_off + i*4 : table_off + i*4 + 4]
    if struct.unpack('<I', rec)[0] == 0:
        break
    f0, f1, f2, f3 = rec
    M[f0][f1] = (M[f0][f1] + f3 * table3[f2]) % 251
    i += 1

이제 M · input ≡ target (mod 251)을 푸는 표준 선형대수 문제로 바뀐다. 251은 소수라서 나눗셈(모듈러 역원)이 항상 존재하고, GF(251) 위에서 가우스 소거를 그대로 쓸 수 있다.

🎯 자체 완결 solve

M을 조립한 뒤 [M | target] 증강행렬을 GF(251)에서 표준 가우스 소거로 행 사다리꼴로 만들면 된다. 각 열(피벗 열)에서 0이 아닌 원소를 찾아 그 행을 정규화(모듈러 역원을 곱해 1로 만듦)하고, 다른 모든 행에서 그 열 성분을 제거해나가는 방식이다.

def inv(a):
    return pow(a, 251 - 2, 251)   # 페르마 소정리로 모듈러 역원
 
A = [row[:] + [target[r]] for r, row in enumerate(M)]
pivot_cols = []
r = 0
for c in range(39):
    piv = next((rr for rr in range(r, 38) if A[rr][c] % 251), None)
    if piv is None:
        continue
    A[r], A[piv] = A[piv], A[r]
    iv = inv(A[r][c])
    A[r] = [(x * iv) % 251 for x in A[r]]
    for rr in range(38):
        if rr != r and A[rr][c]:
            f = A[rr][c]
            A[rr] = [(A[rr][k] - f * A[r][k]) % 251 for k in range(40)]
    pivot_cols.append(c)
    r += 1

실행해보면 랭크가 38로 나온다 — 방정식 38개(buf1의 38바이트)가 전부 독립이라는 뜻이다. 미지수는 39개(input의 39바이트)이므로 자유도가 정확히 1 남는데, 그 자유변수가 하필 input[38](입력의 마지막 바이트) 그 자체였다. 어떤 레코드도 f1=38을 참조하지 않는다 — 이 바이트는 애초에 검증 로직에 전혀 관여하지 않는다.

input[0..37]은 유일하게 결정되고, input[38]은 뭘 넣어도 검증에 영향을 주지 않는다 — read()가 요구하는 39바이트를 채우기 위한 자리일 뿐이다(터미널에 flag를 입력하고 Enter를 치면 자연스럽게 그 개행 문자가 39번째 바이트로 채워지는 구조로 보인다). 나온 결과를 그대로 로컬 바이너리에 넣어 실제로 검증했다.

DH{Poly_m0ly_mult1pl1c4t1on_m0dular~!}

Input : Correct, exit=0. 이 문제는 needs_vm=False라 별도 원격 서버 없이 이 바이너리 자체가 곧 채점기다 — 로컬에서 통과한 게 곧 정답이라는 뜻이다. 드림핵에 제출해 "정답! 해결 처리됨"으로 확정됐다.

📝 결론

이 문제가 준 진짜 교훈은 리버싱 알고리즘 자체보다 "이상하다"는 직감을 검증 없이 결론으로 승격시키면 안 된다는 쪽에 더 가까웠다.

• "말이 안 되게 크다/이상하다"는 판단이 들면, 그 판단 자체를 의심하기 전에 먼저 끝까지 확인해야 한다. 1000개 레코드를 스캔해서 종결 조건을 못 찾았을 때, "테이블이 27000개가 넘을 리 없다"는 전제를 세우고 알고리즘 오독 쪽으로 방향을 틀었던 게 두 세션을 날린 근본 원인이었다. 파일에서 직접 끝까지 읽어보는 데는 몇 초도 안 걸린다 — 검증 비용이 이렇게 낮을 땐 감으로 판단을 내릴 이유가 없다.
• 누산 루프가 아무리 길어도, 각 항의 계수가 입력과 무관한 상수라면 전체는 선형이다. "복잡해 보이는 반복문"과 "실제로 복잡한 문제"는 다르다. 27455번 반복이라는 숫자 자체에 겁먹지 않고 각 항의 구조(f3 * input[f1] * table3[f2]에서 input을 뺀 나머지가 전부 상수)를 짚어내면, 문제는 순식간에 표준 선형대수로 환원된다. 이런 패턴은 다항식 평가, 체크섬, 해시류 검증기에서 반복적으로 나타난다 — "값을 누적한다"는 것과 "그 누적이 입력에 대해 비선형이다"는 것은 별개의 이야기다.
• 자유도가 남는 시스템에서는 "검증되지 않는 바이트"가 어디인지부터 확인하는 게 빠르다. 랭크가 미지수 개수보다 하나 작을 때, 그 자유변수가 정확히 어떤 입력 바이트에 대응하는지 보면(이번엔 input[38]) 그 바이트가 검증 로직에서 완전히 배제됐다는 걸 바로 알 수 있다 — 임의값을 넣어도 되는 이유를 추측할 필요 없이 시스템이 스스로 알려준다.
• GDB로 실측하는 습관은 좋지만, 비교 대상이 되는 "예측 모델" 자체가 틀렸다면 불일치는 아무것도 증명하지 못한다. 그동안은 GDB 실측과 예측의 불일치를 "정적분석이 틀렸다"는 확증으로 삼았는데, 사실 예측 모델이 애초에 루프 길이를 잘못 가정한 채로 만들어졌으니 안 맞는 게 당연했다. 동적 검증은 "이 모델이 맞는지"를 확인하는 도구지, 모델의 전제 자체가 잘못됐을 때 원인을 알려주는 도구는 아니다.

방어자 관점에서 보면, 이런 "표면적으로는 복잡해 보이지만 실제로는 선형인" 검증 로직은 리버싱 난이도를 올리는 데 그다지 효과적이지 않다. 진짜 비선형성(S-box, 라운드 함수의 비트연산, 조건 분기에 따른 경로 다양화)이 섞이지 않는 한, 아무리 반복 횟수를 늘려도 선형대수 한 방으로 풀리는 구조라는 걸 이번 문제가 잘 보여준다.