풀이 날짜: 2026-09-16 (사용자 확정). 익스플로잇 성공은 2026-09-16 사용자 확인에 따른다. 아래 실행 결과는 보존된 원본 기록이며 이번 감사에서 새로 실행한 결과가 아니다.
GF(256)의 다변수 이차 검증
Aglio Olio는 Dreamhack Invitational 2026 crypto 문제다. 공개키는 44변수·20출력의 동차 이차사상을 표현하고, 메시지와 서명 벡터가 공개 검증식을 만족해야 한다. deploy/prob.sage의 검증 핵심은 다음과 같다.
H = self.hash_message(msg)
sig = self.bytes_to_vector(sig)
H_calc = vector(FF, [sig * P_k * sig for P_k in self.P])
return H == H_calc
hash_message는 SHA-256 digest의 앞 20바이트를 각각 체 원소로 해석한다. digest 전체를 하나의 정수로 바꾸는 모델과 다르다. GF(256)의 덧셈은 표수 2에 따른 연산이며 정수 mod 256의 곱셈을 대신 쓸 수 없다.
Oil–Vinegar 구조가 실제로 보이는 곳
키 생성은 비밀 좌표를 vinegar 24개와 oil 20개로 나누고 oil–oil 항을 만들지 않는다. 이를 행렬과 다항식으로 적으면 다음과 같다.
F_k = [ A_k D_k ]
[ 0 0 ]
y = (a,b), a∈K^24, b∈K^20, K=GF(256)
f_k(a,b) = aᵀ A_k a + aᵀ D_k b
공개 좌표는 가역 변환으로 숨겨져 있고 공개 행렬을 상삼각화하는 함수는 같은 이차다항식의 계수를 다시 배치한다. '행렬 표현이 다르다'와 '다항식이 다르다'를 구분해야 한다. 특히 표수 2에서 비대각 계수의 합과 대각 제곱항의 역할을 혼동하면 검증식이 달라진다.
왜 구조를 복구하는 분석이 중요한가
비밀 좌표에서 a를 고정하면 b에 대해서는 선형식이다. 정상 서명 함수의 수학적 의미는 L(a)b = h(M) − c(a)이며, 일관성 조건은 다음과 같다.
rank L(a) = rank [ L(a) | h(M)-c(a) ]
정칙성만이 해 존재의 필요조건은 아니다. 특이행렬이어도 우변이 상공간에 있으면 해가 있을 수 있다. 반대로 변수 수가 식보다 많다는 사실만으로 모든 키·모든 목표의 해를 보장할 수는 없다.
이 식은 공개키만으로 숨은 좌표를 이미 안다는 뜻이 아니다. 기존 분석과 solver는 공개 구조에서 숨은 대수 구조를 분석하는 작업을 수행했다고 기록한다. 위 정상 서명 구조와 실제 구조 복구 근거를 혼동하지 않으며, 본문에는 공개키 공격의 실행 알고리즘을 재구성하지 않는다.
서비스 경로와 결과
클래스에 sign과 privkey가 있어도 실행 서비스가 그 기능을 제공하는 것은 아니다. 원본 main의 실제 경로는 공개키 출력 후 메시지·서명 검증으로 이어지므로 서명 오라클을 자유롭게 사용할 수 있다는 가정을 배제했다.
ANALYSIS에는 후속 원격 검증 수락과 실제 응답 기록이 있다. 이는 배포의 예시 flag 파일과 다른 수준의 근거다. 사용자의 성공 확인과 함께 보존하되 실제 flag는 싣지 않는다. 이번 감사에서는 원격에 접속하거나 solver를 실행하지 않았고, 전달되지 않은 임시 공개키·서명 파일까지 보존되어 있다고 주장하지 않는다.
근거 자료
sources/aglio_olio/deploy/prob.sagesources/aglio_olio/ANALYSIS.mdsources/aglio_olio/analysis_facts.json
원본 문서·solver·검증 로그는 전달 staging에 보존되어 있다. 이 경로들은 provenance이며 CMS의 다운로드 첨부 링크가 아니다.