구글의 kernelCTF PoW를 AVX512로 이긴 방법

• 팀 Crusaders of Rust가 Linux 패킷 스케줄러의 use-after-free 버그를 발견하고 익스플로잇을 개발함
• Google kernelCTF 대회에 빠른 PoW(Proof of Work) 해법의 필요성으로 인해 고성능 최적화를 시도함
• AVX512IFMA 명령어를 활용한 자체 어셈블리 및 SIMD 최적화로 기존 Python/GMP 및 Rust 구현 대비 7배 가까운 속도 성능 달성함
• 동작 원리, 모듈러 연산, 메모리 관리, 레지스터 활용까지 세밀하게 튜닝하여 0.21초까지 PoW 처리 시간을 단축함
• 최종적으로 사상 최단 시간(3.6초)으로 kernelCTF에 성공적 제출 후, PoW 정책이 공식적으로 폐지됨

개요 및 취지

• 2025년 5월, Crusaders of Rust 팀의 William Liu와 Savy Dicanosa는 Linux의 use-after-free 취약점을 찾아 Google의 kernelCTF 대회에 참가했음
• 이 글은 PoW(Proof of Work) 검증을 빠르게 해결하여, 제한된 bounty 경쟁에서 다른 글로벌 팀보다 빠르게 제출하기 위한 최적화 과정을 다루는 내용임

kernelCTF 제출 과정 및 경쟁 배경

• kernelCTF는 큰 현상금 때문에 전 세계의 전문 보안팀들이 제출 자동화 및 PoW 최적화에 사활을 걸고 참여하는 대회임
• 제출 창(2주마다 오픈)마다 가장 빠른 팀 한 곳만 상금을 받음
• 제출 절차:
  • 정각에 서버 접속
  • 수 초가 드는 PoW 풀이
  • VM 부팅 대기
  • 익스플로잇 코드 실행과 flag 획득
  • 구글 폼 제출
• 최근에는 4.5초 만에 flag 제출이 성공한 기록도 있었으나, PoW와 VM 부팅만 해도 6.5초가 걸리므로, PoW 풀이 속도 향상이 필수 과제였음

PoW(VDF-Sloth) 알고리듬 분석과 첫 번째 최적화

• kernelCTF PoW는 sloth VDF라는 순차적 연산 기반의 verifiable delay function을 사용함
  • 1280비트 정수 x에 대해 모듈러 제곱 & 비트 반전 반복 연산
• 기존 구현(Pyhton+gmpy 및 Rust)에서도 이미 다중 코어 병렬화가 소용없고, GMP도 충분히 최적화되어 있었음
• 그러나, 모듈로 연산이 Mersenne 수(2^1279-1) 기반임을 활용, 더 빠른 C++ 매뉴얼 모듈러 구현으로 1.9~1.4초까지 성능 향상에 성공함

AVX512IFMA로의 대전환과 SIMD 기반 초고속 구현

• 그 후, AVX512 ISA와 그 중에서도 AVX512IFMA(52비트 곱셈 및 누산 명령어) 에 착안
• 1280비트 수를 52비트 limb로 분할하여, SIMD 가속을 최대화함(25 limb → 4개 zmm 레지스터 활용)
• 모듈러 스퀘어 연산의 대칭성과, 누산 마스크, 메모리 브로드캐스트, 레지스터 어사인 최적화, 브랜치리스 비교 등 저수준 튜닝을 반복함
• ASM(inline assembly)을 사용해 컴파일러의 비효율적인 레지스터 spill/reload를 막고, 브로드캐스트 및 마스킹 최적화로 최종 0.21초까지 속도를 끌어올림

PoW 제출 자동화와 실제 대회 시나리오

• 최종 제출에서는 Zen 5 Google Cloud 서버(Amsterdam 지역)를 활용해, 구글 폼까지의 네트워크 지연도 최소화함
• 자동 제출 프로그램(구글 폼 POST 요청 패치, 내부 팀 협업으로 최적화)으로 사상 최단 기록인 3.6초 만에 성공적으로 flag 제출함
• 공식적으로 kernelCTF 운영진이 PoW 정책 폐기를 발표, PoW 최적화 경쟁에서 해방됨과 동시에 기법을 공개할 수 있게 됨

고급 구현 상세

모듈러 연산 최적화

• 2^1279-1(Prime) 모듈로 연산을 비트 쉬프트와 사칙연산 몇 번으로 치환해, 표준 GMP 대비 매우 빠른 모듈러 연산 달성

AVX512IFMA 기반 빅인트 스퀘어링

• AVX512의 52비트 곱셈 누산 명령(vpmadd52luq, vpmadd52huq)을 활용, 8개 limb 묶음 병렬 곱셈 및 누산
• 25 limb 구조이므로 4개 zmm에 분산, 쓸데없는 마스킹/누산 최소화 로직 설계

데이터 배치 및 레지스터 활용

• 오프셋별 유닛, 계단식 데이터 배치, 레지스터간 재배치(valignq, 브로드캐스트) 등 SIMD 병목 해소
• 누산기(accumulator) 2배로 늘려 곱셈 유닛 대기(레이지) 없이 최고 스루풋 확보
• 캐리 프로파게이션(carry propagation)까지 필요 최소만 수행

최종 제출 자동화 및 협업

• 새벽 시간대에 캠페인 타격을 위한 팀원 배치, 네트워크 위치와 exploit 실행 최적화
• 실제 제출에서는 PoW 풀이, 익스플로잇 실행, flag 삽입, Google Form POST 요청까지 일관된 자동화 수행

결론 및 의미

• kernelCTF PoW 최적화는 비트 수준부터 메모리, 레지스터, CNN 등 하드웨어 해부적 이해가 필요한 작업임
• PoW 정책이 사라지면서 “순수 네트워크/익스플로잇 속도”만이 경쟁의 초점이 됨
• 본 사례는 실전 해킹과 고성능 컴퓨팅의 만남을 보여주는 동시에, 앞으로도 알고리듬 최적화 노하우와 오픈소스 코드가 연구자 공동체에 기여할 것임

참고 및 부록

• PoW 알고리듬 전체 코드와 변환 함수(GMP <-> 52비트 배열), SIMD 기반 모듈러 연산, ASM 튜닝 코드가 모두 공개됨
• 약 12시간에 걸쳐 집약적으로 개발하여 실전 투입한 “거친” 코드지만, GNU AGPL 3.0 라이선스 하에 오픈됨
• 궁금한 점이나 VDF 관련 협업은 Discord(@forevermilk)로 연락 가능함