💻 computer science

A Novel Memory-Efficient MitM Attack on Ascon-Hash

이 논문은 SAT 모델링, 가우스 소거법, 그리고 삼각 측량을 활용하여 최적의 시간 복잡도를 유지하면서도 메모리 복잡도를 크게 줄인, 라운드 축소된 Ascon-Hash에 대한 새로운 메모리 효율적인 Meet-in-the-Middle 공격을 제안한다.

원저자: Zhiguo Wu, Bo Gao, Jianxiong Wan, Chuyi Liu, Xiaodong Zhang

게시일 2026-08-31

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Zhiguo Wu, Bo Gao, Jianxiong Wan, Chuyi Liu, Xiaodong Zhang

원본 논문은 CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

디지털 세계에서 보안은 종종 강도와 효율성 사이의 섬세한 균형에 의존합니다. 공장의 센서, 스마트 미터기, 의료 모니터와 같이 인터넷 사물(IoT)을 구성하는 수십억 개의 작은 배터리 구동 장치들에게 컴퓨팅 능력은 매우 희귀하며, 메모리는 훨씬 더 귀합니다. 이 장치들은 데이터를 안전하게 지킬 만큼 강력하면서도, 배터리를 소모하거나 아주 작은 칩을 가득 채우지 않을 만큼 가벼운 암호화 도구가 필요합니다. Ascon은 이러한 과제에 대한 선도적인 솔루션으로, 자원이 제한된 환경을 위해 특별히 설계된 암호화 및 해싱 방법 제품군입니다. Ascon이 안전하게 유지되도록 하기 위해, 연구자들은 코드를 깨뜨릴 수 있는 가장 짧은 경로를 찾으려 노력하며 정교한 공격을 통해 이를 끊임없이 테스트합니다. 이 무기 체계 중 가장 강력한 도구 중 하나는 "중간 만남(meet-in-the-middle)" 공격으로, 이는 공격자가 최종 결과로부터 역방향으로 작업하고 시작점으로부터 순방향으로 작업하여, 중간 지점에서 일치하는 값을 만나기를 기대하는 전략입니다. 그러나 이 전략은 전통적으로 수백만 개의 중간 단계를 저장하기 위해 방대한 양의 메모리를 필요로 했으며, 이러한 요구 사항은 Ascon이 보호하고자 하는 바로 그 장치들에게 이 공격을 실질적으로 불가능하게 만드는 경우가 많았습니다.

한 연구팀은 이제 이 공격을 실행할 때 필요한 메모리를 획기적으로 줄여, 이 테스트를 경량 시스템에 훨씬 더 현실적으로 만드는 새로운 방법을 개발했습니다. Ascon-Hash 함수에 초점을 맞춘 연구에서, 저자들은 계산 속도를 희생하지 않으면서도 이전에는 가능하다고 생각되었던 것보다 훨씬 적은 저장 공간을 사용하여 시스템의 축소된 버전에 대해 공격을 수행할 수 있음을 입증했습니다. 문제를 복잡한 논리적 제약 조건의 퍼즐로 취급함으로써, 그들은 데이터가 저장되기 전에 불필요한 데이터를 걸러내는 방법을 찾아냈습니다. 그들의 연구에 따르면, 3라운드 버전의 해시의 경우 메모리 복잡도가 2^24에서 2^14로 줄어들 수 있습니다. 4라운드 버전의 경우, 그 감소 폭은 더욱 극적이며, 요구되는 복잡도가 2^34에서 2^12로 떨어집니다. 이 성과는 단순히 공격 비용을 낮추는 것에 그치지 않고, 자원이 제한된 적을 마주했을 때 Ascon이 실제로 얼마나 안전한지에 대한 더 날카롭고 정확한 그림을 제공합니다.

연구자들은 자동화된 탐색 도구를 사용하여 Ascon을 깨뜨리려는 이전의 시도들이 메모리 사용량이라는 벽에 부딪혔음을 인정하며 논의를 시작했습니다. 컴퓨터가 암호화 과정의 올바른 경로를 찾는 데는 더 빨라졌지만, 그 과정은 여전히 공격자가 중간 결과의 방대한 라이브러리를 메모리에 보관할 것을 요구했습니다. 이는 마치 미로를 풀 때 자신이 가는 모든 회전마다 별도의 종이에 기록하며 미로를 통과하려는 것과 같습니다. 미로가 충분히 크다면, 출구를 찾기도 전에 종이가 먼저 떨어질 것입니다. 연구팀은 이 문제를 해결하는 열쇠가 단순히 경로를 더 빨리 찾는 것이 아니라, 무엇을 기록할지에 대해 더 똑똑해지는 것임을 깨달았습니다. 그들은 "충족 가능성 해결(satisfiability solving)"이라고 불리는 방법을 사용했는데, 이는 본질적으로 컴퓨터에게 복잡한 논리적 문장을 참으로 만드는 조건들의 집합을 찾도록 요청하는 방식입니다. 이를 통해 그들은 순방향 및 역방향 계산이 잠재적으로 만날 수 있는 암호화 과정의 특정 지점들을 지도화할 수 있었습니다.

잠재적인 만남 지점들을 지도화한 후, 연구자들은 데이터를 정리하기 위해 일련의 대수적 필터를 적용했습니다. 그들은 암호화를 규정하는 많은 제약 조건이 단순한 선형 관계와 더 복잡한 비선형 관계로 분리될 수 있다는 점에 주목했습니다. 선형 부분은 간단했습니다. 표준 수학적 기법을 사용하여 중복된 정보를 제거함으로써 효과적으로 단순화할 수 있었고, 이는 컴퓨터가 추적해야 할 가능성의 목록을 실질적으로 줄여주었습니다. 비선형 부분은 더 까다로웠지만, 팀은 이를 삼각형 모양으로 재배열하여 다른 변수들에 기반해 특정 변수들을 풀 수 있는 방법을 개발했습니다. 이 과정은 해당 특정 변수들을 명시적으로 계산하거나 저장할 필요를 없애주어 메모리 사용량을 더욱 줄였습니다.

가장 중요한 혁신은 쉽게 단순화할 수 없는 남은 복잡한 제약 조건들을 처리하는 방식에서 나왔습니다. 모든 가능한 결과를 저장하는 대신, 연구자들은 이러한 남은 제약 조건들을 사용하여 일종의 "잔차 인덱스(residual index)", 즉 디지털 태그나 라벨을 만들었습니다. 그들은 잠재적인 순방향 경로들을 생성하면서, 각 경로의 특정 특성에 따라 태그를 할당했습니다. 결정적으로, 그들은 역방향 경로가 순방향 경로와 일치하려면 그들의 태그가 호환되어야 한다는 점을 깨달았습니다. 이는 컴퓨터가 모든 순방향 경로를 메모리에 유지할 필요가 없음을 의미했습니다. 오직 역방향 경로가 도달할 수 있는 태그를 가진 경로만을 유지하면 되기 때문입니다. 그들이 테스트한 특정 구성에서, 이 필터링은 매우 효과적이어서 전체 필수 순방형 경로 목록을 단 하나의 아주 작은 데이터 버킷으로 줄였습니다.

이 새로운 접근 방식의 결과는 놀라웠습니다. Ascon-Hash의 3라운드 버전에 적용했을 때, 이 방법은 이전 공격들과 동일한 속도를 유지하면서도 메모리 요구량을 2^24에서 2^14로 줄였습니다. 4라운드 버전의 경우, 메모리 요구량이 이전의 최선 방법과 비교하여 2^34에서 2^12로 줄어드는 더욱 심오한 감소를 보여주었습니다. 연구진은 이러한 공격적인 필터링이 실수로 유효한 솔루션을 폐기하지 않았음을 검증했습니다. 그들은 남은 데이터가 여전히 암호화 시스템의 원래 규칙들을 모두 충족하는지 확인했습니다. 이 연구는 암호화의 구조를 면밀히 분석하고 논리적 필터를 적용함으로써, 이전에는 필요하다고 생각되었던 자원의 아주 일부분만으로도 심층적인 보안 테스트를 수행할 수 있음을 확인시켜 줍니다. 이 작업은 자원이 제한된 환경에서 Ascon의 보안 마진이 더 높은 정밀도로 평가되고 있음을 시사하며, 우리의 연결된 세상을 보호하는 암호화 표준이 보이는 모습만큼이나 견고함을 보장합니다.

기술 요약: Ascon-Hash에 대한 새로운 메모리 효율적 MitM 공격

문제 정의
Ascon은 NIST에 의해 선택되어 SP 800-232에 표준화된 경량 암호 표준으로, IoT와 같이 자원이 제한된 환경을 위해 특별히 설계되었습니다. 이러한 환경에서는 계산 능력보다 메모리가 더 결정적인 제약 사항인 경우가 많습니다. Meet-in-the-Middle (MitM) 공격은 축소된 라운드의 Ascon에 대한 역상 저항성(preimage resistance)을 평가하는 주요 도구이지만, 기존의 자동화된 접근 방식들은 상당한 메모리 병목 현상에 직면해 있습니다. Degré 등이 제안한 SAT 기반 프레임워크와 같은 이전 연구들은 시간 복잡도를 성공적으로 줄였으나, 온라인 단계에서 해시 테이블에 중간값을 저장하기 위해 여전히 상당한 메모리(예: 4라운드 Ascon-Hash의 경우 $2^{34}$ )를 필요로 했습니다. 본 논문은 MitM 공격의 최선 알려진 시간 복잡도를 유지하면서 Ascon-Hash의 총 메모리 사용량을 최소화하는 과제를 다룹니다.

방법론
저자들은 SAT 기반 MitM 탐색을 기반으로 구축하되, 저장되는 RED 측 테이블의 크기를 획기적으로 줄이기 위해 사후 처리 대수적 정교화(algebraic refinement) 단계를 도입한 새로운 프레임워크를 제안합니다. 방법론은 다음 단계로 진행됩니다:

SAT 기반 구성 탐색: 프로세스는 SAT 솔버를 사용하여 목표 시간 지수를 달est하는 유효한 MitM 구성(RED 측 변수, BLUE 측 변수, 매칭 위치 및 캔슬레이션 위치 정의)을 식별하는 것으로 시작됩니다.
대수적 분리: 찾아낸 각 시간 최적 구성에 대해, 유도된 캔슬레이션 관계를 재구성하고 그 대수적 형태에 따라 선형 부분과 비선형 부분으로 분리합니다.
선형 감소: 선형 캔슬레이션 관계(XOR 제약 조건)를 추출하고 GF(2) 상의 가우스 소거법을 사용하여 축소합니다. 이 선형 시스템의 계수(rank)는 자유로운 RED 측 변수의 수를 결정합니다.
비선형 관계의 삼각 분해: 비선형 캔슬레이션 관계는 불리언 다항식에 대한 삼각 분해 알고리즘을 사용하여 처리됩니다. 이 단계는 특정 RED 측 변수를 다른 변수의 함수로 표현하도록 시도하여, 명시적 열거로부터 해당 변수들을 효과적으로 제거합니다.
잔여 인덱스 필터링 (Residual-Index Filtering): 삼각 분해를 통해 제거할 수 없는 비선linear 관계를 위해, 저자들은 "잔여 인덱스"를 정의합니다. 이 인덱스는 RED 측 할당을 버킷(bucket)으로 분할합니다. 공격 중에, BLUE 측으로부터 계산 가능한 값과 일치하는 인덱스를 가진 RED 버킷만 유지됩니다. 이 필터링 단계는 최종 매칭 단계 이전에 호환되지 않는 RED 할당을 폐기합니다.
호환성 검증: 저자들은 필터링 과정이 매칭 방정식의 해 집합을 변경하지 않음을 검증합니다. 만약 매칭 표현식 내의 혼합 RED-BLUE 단항식들이 유지된 도메인 상에서 0이 된다면, MitM 공격에 사용된 분리 결합(separable join)이 전체 매칭 방정식을 푸는 것과 동일하게 유지됨을 증명합니다.

주요 기여

메모리 최적화 프레임워크: 본 논문은 캔슬레이션 관계를 대수적으로 처리함으로써 SAT 유도 MitM 구성을 정교화하고, 특히 온라인 메모리 복잡도를 줄이는 데 특화된 체계적인 방법을 도입합니다.
삼각 분해 및 필터링: 불리언 다항식 삼각 분해와 잔여 인덱스 필터링의 통합은 시간 복잡도를 증가시키지 않으면서 변수를 제거하고 탐색 공간을 가지치기(pruning)할 수 있게 합니다.
분리 가능성 검증: 본 연구는 메모리 감소 기술이 유지된 도메인에서의 혼합 항의 소멸(vanishing)을 검증함으로써 MitM 공격의 정확성을 해치지 않는다는 것을 보장하는 공식적인 검증(Proposition 1)을 제공합니다.

실험 결과
저자들은 3라운드 및 4라운드 Ascon-Hash에 대해 자신들의 방법을 평가하였으며, Degré 등의 SAT 기반 베이스라인[1]과 결과를 비교하였습니다.

3-Round Ascon-Hash:
- 시간 복잡도: $2^{114}$ 로 유지됨.
- 메모리 복잡도: $2^{24}$ (베이스라인)에서 $2^{14}$ 로 감소.
- 메커니-즘: 해당 구성은 14개의 RED 변수를 활용했습니다. 선형 계수 감소(rank 1) 및 잔여 인덱스 필터링(zero-index 버킷만 유지) 후, 대칭성이 감소된 모델에서의 유지된 RED 테이블 크기는 $2^7$ 이었으며, 이는 전체 설정에서 $2^{14}$ 에 해당합니다.
4-Round Ascon-Hash:
- 시간 복잡도: $2^{124}$ 로 유지됨.
- 메모리 복잡도: $2^{34}$ (베이스라인)에서 $2^{12}$ 로 감소.
- 메커니-즘: 해당 구성은 38개의 RED 변수를 활용했습니다. 삼각 분해를 통해 5개의 변수가 제거되었고, 잔여 인덱스 필터링이 유지된 테이블을 더욱 축소했습니다. 최종 64-컬럼 설정에서의 메모리 복잡도는 $2^{12}$ 였습니다.

논문의 표 1은 이러한 개선 사항을 요약하며, 이전의 최첨단 기술(state-of-the-art)의 시간 지수를 유지하면서 메모리 지수의 일관된 감소를 보여줍니다.

의의 및 주장
본 논문의 주요 의의는 메모리가 제한된 환경에서 Ascon의 축소된 라운드 보안 마진을 더욱 정밀하게 평가하는 데 있다고 주장합니다. Ascon은 메모리가 부족한 IoT 및 임베디드 시스템을 위해 설계되었으므로, MitM 공격이 훨씬 낮은 메모리 요구 사항(예: 4라운드에 대해 $2^{34}$ 에서 $2^{12}$ 로 감소)으로 실행될 수 있음을 입증하는 것은 정확한 보안 평가를 위해 매우 중요합니다.

저자들은 자신들의 프레임워크가 시간 최적 구성을 찾는 것을 넘어, 캔슬레이션 관계에 대한 추가적인 대수적 처리가 온라인 저장 요구 사항을 효과적으로 줄일 수 있음을 보여준다고 명시합니다. 저자들은 전체 Ascon 표준을 깨뜨린다고 주장하는 것이 아니라, 축소된 라운드 변형들에 대한 분석을 정교화하는 것입니다. 이 연구는 향후 연구가 더 많은 라운드, 다른 Ascon 모드 및 다른 스펀지 기반 경량 프리미티브로 확장될 수 있음을 시사합니다.

유사한 논문