▲

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

 (anemato.de)
2P by GN⁺ 5일전 | ★ favorite | 댓글 1개
  • 팀 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)로 연락 가능함
▲
GN⁺ 5일전  [-]
Hacker News 의견

  • 3.6초에 우승한 팀과 2위는 3.73초 혹은 3.74초 기록 보임, 2위도 PoW 최적화를 했거나 FPGA 사용 가능성 있다는 생각, 예전 4초 넘는 FPGA 제출과 비교하면, 저자가 이번 주 2위 기록도 역대급 기록일 수 있다는 점을 언급했다면 좋겠다는 아쉬움 남음

  • 이 방법이 AVX-512 최적화된 RSA 구현에서 사용하는 방식과 매우 비슷하다는 인상, RSA도 매우 큰 거듭제곱 연산이 필요하기 때문, 논문(https://dpitt.me/files/sime.pdf)에서 윈도잉 기법 및 윈도 크기가 임의로 조정 가능함을 다룸, AVX-512 RSA 구현에서는 곱셈 결과를 [0..2^{window-size}) 범위로 테이블에 저장해 각 윈도마다 결과를 사용한다는 점이 추가, 실제 예시는 aws-lc 코드의 rsaz-2k-avx512.pl에서 확인 가능

    • 이런 내용 미리 봤으면 개발에 참고가 되었을 것이라는 아쉬움, Zen 5에선 zmm 레지스터 활용으로 2배 곱셈 처리량 기대, 기존 코드에서 마스크 레지스터가 GPR로 전환되는데 Zen 4/5에선 비효율적임, 캐리 전파가 반드시 한 번에 이루어져야 하는지 의문, 실제로 코드에서는 캐리가 한 번만 발생한다고 가정하고 반복, 이는 대부분 상황에서 지연 감소에 도움, 단 브랜치로 인한 타이밍 공격 가능성 남음

  • AVX512를 여러 세대에 걸쳐 소비자용 CPU에서 지원한다는 주장에 대해, Rocket Lake(11세대) 전까진 AVX512가 엔수지스트, Xeon, 일부 모바일 프로세서에서만 이용 가능했던 것으로 기억, 12세대와 P/E코어 도입 이후엔 몇 달 만에 비활성화되고 사라짐, AMD가 AVX512에서 성공하면 Intel이 다시 도입할 거라는 예측 남김, 자신은 i9-11900 사용 중임

    • 12세대 P코어 CPU는 아예 AVX512 지원이나 광고를 하지도 않았고 기본으로 비활성화, E코어 공간 때문으로 전체 CPU에서 AVX512 미탑재, 단 BIOS 옵션 꼼수로 E코어 비활성화하고 나머지 코어에서 AVX512 활성화하는 정도만 가능, 대신 E코어를 포기해야 했던 점 언급
    • 최근 Intel AVX10 기술백서(https://cdrdv2.intel.com/v1/dl/getContent/784343)에서 P코어와 E코어 모두에서 512비트 AVX를 표준으로 제시, 256비트 한정 구성을 탈피해 AVX-512가 서버뿐 아니라 향후 소비자 CPU에도 본격 복귀 예고, 이는 AMD의 AVX-512 확대에 따라 Intel이 뒤따르려는 것으로 해석

  • CTF 대회 본질에 의문, 제출 속도 경쟁이 아닌 일정 제출 윈도 내에 플래그를 제출한 팀 모두가 상금 나눠 갖는 방식이 더 나을 것이라는 의견

    • 이런 방식은 참가자들이 익스플로잇 정보를 곧바로 공개하지 않고 이후 라운드 도전을 위해 보류하게 만들어 즉각적 보고를 저해하는 메타게임 유발 가능성 제기, 또 제출 타이밍 전략 등 비건설적인 경쟁 유도 부작용 우려
    • 메타게임 구조가 달라지고, 오히려 참여 의욕이 줄어들어 kernelCTF 제출을 고려하지 않는 사람도 늘어날 가능성 언급

  • 내가 이해한게 맞다면 4초 proof of work와 월 1회 지급 구조라는 점, 매달 이렇게 많은 익스플로잇이 등장해 치열하게 경쟁하는 상황인지 궁금

    • 서버가 2주마다 열렸고 PoW는 과도한 접속 요청을 방지하기 위한 목적으로 약간의 지연을 주기 위함, 공공 CTF는 종종 DDoS 유사 작전이 시도될 만큼 치열함, 이후 Google에서 proof of work 단계를 삭제
    • 리눅스 커널 보안에 대한 신화가 실제로는 환상일 뿐이라는 주장
    • 이번 CTF는 원격 코드 실행이 아니라 권한 상승(일반 사용자에서 루트로 상승) 익스플로잇에 해당, 권한 상승 버그는 정말 흔한 현상

  • 놀라운 도전이지만, 우승을 위한 장애물의 복잡함과 우스꽝스러운 분위기 인상, 마치 룹 골드버그 기계 같은 상황이라는 재미있는 표현

  • 본문에서 언급한 base-52 관련 내용을 더 알고 싶으면 오늘 핫했던 이 글(https://news.ycombinator.com/item?id=44132673) 참조 추천

  • 수학이 멋지다는 감상

  • proof of work에 쓰인 sloth라는 VDF(Verifiable Delay Function) 소개, 일련의 긴 계산을 요구해 시간 경과를 증명하고, 계산 결과는 신속하게 검증 가능, 계산이 직렬적이어서 여러 코어 동원해도 런타임 단축 불가, 이런 분야가 CPU 제조사들에게 새로운 시장이 될 수 있을지 궁금, sloth 반복 및 결과에 대한 전용 명령어와 HW 기반 오버클럭 방지 기능 탑재 제안, CPU uptime을 모니터링 후 챌린지와 함께 서명하는 방식도 아이디어로 제시, 이는 CPU를 생산 활용하면서도 n초간 CPU 소유권을 증명하는 proof of stake 개념 유사

  • 블로그에 나온 파이썬 함수가 구글 PoW 구현과 어떻게 등가인지 궁금, 따라가기 까다롭다는 인상

    • 구글 코드에서 "exponent = (p + 1) // 4"가 2^1277이라는 점, 숫자를 그런 거대한 지수로 올리려면 1277번 제곱해야 하고 파이썬 함수가 실제로 이를 구현, 최초 값이 x라면 각각의 제곱마다 2배씩 곱해져 마지막엔 2^1277개가 됨, 이런 원리 설명
답변달기