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

 (anemato.de)
2P by GN⁺ | ★ favorite | 댓글 1개
  • Crusaders of Rust 팀은 Linux packet scheduler의 CVE-2025-38001 익스플로잇을 제출하려 했지만, kernelCTF의 선착순 구조 때문에 버그 자체보다 PoW 단축이 승부처가 됨
  • 제출 과정은 12:00 UTC 접속, 약 4초 PoW, 약 2.5초 VM 부팅, 익스플로잇 실행, Google Form 제출로 이어졌고, 이전 라운드의 4.5초 제출 기록이 병목을 드러냄
  • 대상 PoW는 “sloth” VDF로, 1280비트 정수에 대해 2^1279 - 1 모듈러 제곱을 반복하는 직렬 계산이라 CPU/GPU 코어를 늘리는 방식으로는 줄이기 어려웠음
  • GMP/C++와 Mersenne 모듈러 축약으로 1.9초, -march=native 정적 링크로 약 1.4초까지 줄인 뒤, AVX512IFMA의 52비트 정수 fused multiply-add로 Ryzen 9950X에서 약 0.21초까지 단축함
  • 2025년 5월 16일 팀은 Zen 5 Google Cloud 서버와 최적화된 POST 제출 경로로 3.6초 만에 플래그를 제출했고, 5월 28일 kernelCTF는 PoW 제거를 발표함

경쟁 조건: 버그보다 빠른 제출이 문제였음

  • 2025년 5월, Crusaders of Rust 팀의 William Liu와 Savy Dicanosa는 Linux packet scheduler의 use-after-free 버그 CVE-2025-38001을 발견하고 익스플로잇을 개발함
    • William은 석사 논문을 위해 Linux를 퍼징하던 중 버그를 찾음
    • Savy는 익스플로잇 실행 시간을 약 0.55초까지 줄임
  • Google kernelCTF는 2주마다 UTC 정오에 제출 창을 열고, 서버를 익스플로잇해 플래그를 Google Form에 가장 먼저 제출한 팀만 보상을 받는 구조였음
  • 제출은 항상 같은 순서로 진행됨
    • 12:00:00 UTC에 kernelCTF 서버 접속
    • proof of work 풀이, 대략 4초
    • 인스턴스 부팅 대기, 대략 2.5초
    • 익스플로잇 업로드 및 실행
    • 플래그를 Google Form에 제출
  • 예상 바운티는 $51,000이었음
    • 기본 보상 $21,337
    • 실행 안정성 보상 $10,000
    • 0-day 버그 보상 $20,000

이전 제출 기록이 드러낸 PoW 병목

  • 2025년 5월 2일 제출 창에서 첫 제출은 정오 이후 4.5초에 들어옴
  • PoW 약 4초와 VM 부팅 약 2.5초만 합쳐도 6.5초가 필요하므로, 4.5초 기록은 단순 계산과 맞지 않았음
  • kernelCTF 서버 코드의 반올림 특성 때문에 VM 인스턴스는 실제로 11:59:59에 부팅되어 시간상 모순은 사라짐
  • 그래도 플래그 생성 타임스탬프는 우승 팀이 PoW를 1초 미만에 풀었음을 보여줌
  • 경쟁 팀이 FPGA를 사용했다면 1초 미만 PoW도 가능했을 수 있음
    • FPGA는 특정 작업을 매우 빠르게 수행할 수 있는 맞춤형 하드웨어임
    • 일반 목적 작업에는 적합하지 않고, 가격과 프로그래밍 난도가 높음

sloth VDF: 병렬화가 잘 안 되는 PoW

  • kernelCTF PoW는 “sloth”라는 검증 가능 지연 함수(VDF) 였음
  • VDF는 긴 직렬 계산으로 시간이 지났음을 증명하고, 결과 증명은 비교적 빠르게 검증할 수 있는 암호학적 기본 요소임
  • 계산 자체가 직렬이라 CPU나 GPU 코어를 더 투입해도 실행 시간을 줄이기 어려움
  • 최적화 대상 핵심 루프는 다음 구조였음
    • difficulty=7337
    • 각 difficulty 반복마다 1277번 x = (x * x) % (2 ** 1279 - 1) 수행
    • 이후 x의 최하위 비트를 뒤집음
  • Google 기준 구현은 Python에서 gmpy를 사용했고, gmpy는 GMP에 대한 Python 바인딩임
    • GMP는 플랫폼별 덧셈·곱셈 커널을 어셈블리로 구현한 다중 정밀도 정수 라이브러리임

GMP 기반 1차 최적화

  • 첫 최적화는 2^1279 - 1이 Mersenne 수라는 점을 이용한 모듈러 축약이었음
    • 2560비트 중간 곱을 하위 1279비트와 상위 비트로 나눠 더함
    • 결과가 모듈러스 이상이면 한 번 빼는 방식으로 % 연산을 대체함
  • Python FFI 오버헤드를 줄이기 위해 C++로 옮겼고, 이 버전은 M1 MacBook Pro에서 1.9초에 실행됨
  • William은 libgmp를 로컬에서 -march=native로 컴파일하고 정적으로 링크해 Intel Ice Lake 노트북에서 약 1.4초까지 줄임
  • Rust로 작성된 유사 최적화 솔버는 같은 Mersenne 기법을 사용했지만 약 2.4초가 걸림
  • 이후 FLINT도 시험했지만 GMP와 속도가 거의 같았음

AVX512IFMA로 큰 정수 제곱을 다시 작성

  • AVX512는 Intel x86 ISA 확장으로, 벡터 레지스터 수와 폭을 늘리고 마스크 예측 및 여러 새 명령을 추가함
    • Intel은 Alder Lake부터 클라이언트 CPU에서 AVX512 지원을 비활성화함
    • 서버 영역에서는 지원이 이어졌고, AMD는 Zen 4와 Zen 5에서 소비자·서버 CPU 모두에 AVX512를 구현함
  • 핵심은 AVX512IFMA였음
    • vpmadd52luq: 52비트 곱의 하위 절반을 64비트 누산기에 더함
    • vpmadd52huq: 52비트 곱의 상위 절반을 64비트 누산기에 더함
  • 이 명령들은 52×52→104비트 곱의 하위·상위 부분을 계산해 벡터 레지스터에 누산함
  • Zen 5는 512비트 데이터 경로를 갖고 있어 이 명령을 클럭당 2개 시작할 수 있었음
  • 자연스러운 기수는 2^52였고, 1280비트 정수는 25개 52비트 limb로 표현됨
    • 512비트 zmm 레지스터 하나는 8개 limb를 담을 수 있음
    • 전체 값은 zmm 레지스터 4개에 들어감

곱셈 배치와 Mersenne 축약

  • 1280비트 제곱은 25개 52비트 limb를 제곱해 50개 limb 중간 결과를 만드는 방식으로 구현됨
  • 제곱의 대칭성을 이용해 필요한 곱셈 수를 거의 절반으로 줄임
    • 대각 성분 ai^2
    • i < j인 교차항 2 * ai * aj
  • 교차항 계산에서는 8개 연속 limb의 슬라이딩 윈도우를 단일 multiplier limb와 곱해 셔플을 줄임
  • AVX512의 merge masking으로 최종 합에 포함되지 않는 곱셈은 누산하지 않도록 처리함
  • 모듈러 축약은 상위 1279비트를 하위 1279비트에 더하는 방식으로 수행함
    • 누산기 원소가 2^52 - 1을 넘을 수 있어 carry 전파는 덧셈 이후로 미룸
    • 결과가 2^1279 - 1 이상인지 여부는 1280번째 비트가 1인지로 판단함
    • 2^1279 - 1을 빼는 것은 1280번째 비트를 지우고 최하위 limb에 1을 더하는 것과 같음
  • 마지막 단계에는 매우 작은 overflow 가능성이 남아 있었음
    • 마지막 limb가 정확히 2^52 - 1이면 carry 전파가 필요함
    • 무작위 PoW 기준 발생 확률은 실행당 약 20억분의 2로 보고 무시함

0.45초에서 0.21초까지 줄인 미세 최적화

  • 첫 AVX512IFMA 버전은 대여한 Ryzen 9950X에서 PoW를 약 0.45초에 처리함
  • multiply-add 명령은 지연 시간이 4사이클이고 클럭당 2개를 시작할 수 있어, 곱셈 유닛을 포화하려면 최소 8개 누산기가 필요했음
    • 기존에는 누산기가 7개뿐이었음
    • 하위 절반용 7개와 상위 절반용 7개, 총 14개 누산기를 사용하고 마지막에 합치는 방식으로 바꿈
    • 이 변경으로 약 0.32초까지 줄어듦
  • GCC와 clang은 루프를 언롤하면서 vbroadcastsd zmm, m64를 생성했고, 레지스터 할당 과정에서 벡터 레지스터가 부족해 stack spill과 reload가 발생함
    • 인라인 어셈블리로 vpmadd52luq/vpmadd52huq가 memory broadcast operand를 쓰도록 강제함
    • multiplier limb를 별도 벡터 레지스터에 담지 않고 메모리에서 읽어 모든 벡터 원소로 복제함
    • 이 broadcast load는 벡터 ALU 자원을 쓰지 않고 load unit에서 처리됨
    • 이 단계에서 약 0.23초까지 줄어듦
  • 정수를 메모리에 정렬 저장한 뒤 비정렬 로드로 window를 만드는 방식은 store-forwarding stall을 일으킴
    • valignq로 zmm 레지스터 안에서 비정렬 로드를 흉내 내며 메모리 접근을 줄임
    • 최종 PoW 시간은 약 0.21초가 됨

2025년 5월 16일 제출 결과

  • 팀은 2025년 5월 16일 오전 4:30 PST에 최종 제출을 준비함
  • Google Form 제출 서버와 지리적으로 가까운 네덜란드의 Zen 5 Google Cloud 서버를 사용해 지연 시간을 줄임
  • 제출 몇 분 전에는 더미 플래그로 Google Form POST 요청을 가로채 기록해둠
    • Bryce Casaje와 Larry Yuan이 Form 제출 프로그램을 설계·최적화함
    • Max Cai도 개발과 제출을 도왔음
  • 5:00에 서버가 kernelCTF 서버에 연결하고, PoW를 풀고, Savy의 최적화 익스플로잇을 실행한 뒤 플래그를 POST 요청에 삽입해 전송함
  • 결과는 3.6초 제출이었고, 당시 kernelCTF 역사상 가장 빠른 제출이었음
  • kernelCTF 운영자는 같은 날 바운티 자격을 확인함

PoW 제거와 최종 솔버 공개

  • 2025년 5월 28일 kernelCTF 운영자 koczkatamas는 PoW 제거를 발표함
  • PoW가 사라지면서 slot 경쟁은 익스플로잇 실행 시간과 네트워크 지연 시간 중심으로 바뀜
  • 이 변화로 FPGA나 인라인 어셈블리 최적화 지식 없이도 전문 팀과 같은 조건에서 경쟁할 수 있게 됨
  • 최종 솔버 코드는 2025년 5월 14~15일 약 12시간 작업의 결과물이며, GNU AGPL 3.0으로 공개됨
  • 빌드 예시는 gcc main.c -O3 -march=znver5 -masm=intel -lgmp였음

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 멋진 내용임. 이 방식은 AVX-512 최적화 RSA 구현과도 매우 비슷한데, RSA도 아주 큰 지수 연산을 해야 하기 때문임
    이 논문[1]은 RSA가 윈도잉을 어떻게 하는지 다루고, 창 크기가 임의일 수 있음을 보여주는 공식도 포함. AVX-512 RSA 구현은 추가로 [0..2^{window-size}) 범위의 곱셈 결과를 표에 저장해 두고, 각 창마다 그 결과를 표[2]에서 꺼낸 뒤 시프트/재배치만 수행함

    1. https://dpitt.me/files/sime.pdf (저널에서 가져온 것이라 내 도메인에 호스팅함)

    2. https://github.com/aws/aws-lc/blob/9c8bd6d7b8adccdd8af4242e0...

    • 흥미롭다. 개발할 때 이걸 봤어야 했을 듯함. 저 코드는 예를 들어 Zen 5용 버전이 하나 더 있으면 좋겠고, zmm 레지스터를 쓰면 곱셈 처리량이 2배가 될 수 있어 보임
      또 마스크 레지스터를 산술 연산 때문에 범용 레지스터로 옮기고 있는데, Zen 4/5에서는 최적이 아님. 별개로 자리올림을 정말 한 번에 전파해야 하는지도 궁금함. 내 코드에서는 자리올림이 한 번만 난다고 가정하고 필요하면 루프로 돌아가게 해서 일반적인 경우의 지연 시간을 줄였음. 다만 분기가 있으면 타이밍 공격 문제가 생길 수는 있겠음
    • dpitt.me/files/sime.pdf는 archive.org에도 올릴 수 있음: https://archive.org/download/sime_20250531/sime.pdf

  • “소비자용 CPU에서 여러 세대 동안 [AVX512]를 지원했음에도”라는 부분은 좀 이상함
    Rocket Lake(11세대) 전에는 AVX-512가 고급 취미용 CPU, Xeon CPU, 일부 모바일 프로세서에만 있었고, 모바일 프로세서를 소비자용 CPU라고 부르긴 애매함. 12세대에서는 성능/효율 코어 구조 때문에 몇 달 뒤 해당 코어에서 비활성화됐고 다시 보이지 않았음. 그래도 AMD가 AVX-512로 어느 정도 성공하면 Intel이 다시 도입할 가능성이 높다고 봄. 참고로 아직 Intel i9-11900을 쓰고 있음

    • 맞는 흐름임. 몇 달 전 Intel의 업데이트된 AVX10 백서[1]도 이를 확인해 주는 듯함. 512비트 AVX가 P 코어와 E 코어 모두의 표준이 될 것이라고 명시하고, 256비트 전용 구성에서 벗어난다고 함
      이는 AVX-512가 서버뿐 아니라 E 코어가 있는 미래 소비자용 CPU에도 제대로 돌아온다는 강한 신호로 보임. 아마 AMD의 더 넓은 AVX-512 채택을 따라잡으려는 듯함

      [1] - https://cdrdv2.intel.com/v1/dl/getContent/784343 (PDF)

    • 12세대 성능 코어 탑재 CPU는 애초에 AVX512 지원을 표시하지도 않았고 기본으로 활성화되지도 않았음
      효율 코어에는 면적 문제로 AVX512가 들어가지 않았기 때문에 전체 CPU가 AVX512 미지원으로 간주됐음. 일부 BIOS 옵션의 특이한 동작을 이용해 효율 코어를 끄고 남은 CPU에서 AVX512를 켤 수 있었을 뿐이고, 그 대가로 E 코어를 포기해야 했음

  • 우승 기록은 3.6초였지만 2위는 3.73초, 우승 기록과 같은 자릿수로 맞추면 3.74초였음. 그렇다면 2위도 작업 증명을 최적화했거나 FPGA를 쓴 것으로 봐야 하나?
    작성자가 이전 제출을 비싼 FPGA 기반이라고 설명했는데도 4초 이상이었다고 했음. 그렇다면 해당 주의 2위가 역대 두 번째로 빠른 제출이었을 가능성도 있었을 텐데, 그에 대해 뭔가 언급했을 법하지 않나 싶음

    • 이미지에 dupe라고 되어 있음. 아마 원글 팀이 여러 계정으로 병렬 제출을 시도한 것 같음

  • 인상적이지만, 최적화 대상이 잘못된 것처럼 보임. CTF가 제출 운영 싸움이 되어서는 안 됨
    제출 창 안에 플래그를 보낸 모든 팀이 상금을 나눠 갖는 편이 모두에게 더 낫지 않을까 싶음

    • 이런 구조는 익스플로잇을 즉시 보고하지 않고 쥐고 있게 만들기도 함. 이번에 못 받았으면 다음 번 제출을 노리려고, 제출 타이밍 장난이 없어도 보류할 유인이 생김
      그래서 실제로는 “잘못된” 행동을 적극적으로 장려할 수도 있음
    • 그건 또 다른 메타게임이 될 것임. 깊게 생각해 보진 않았지만, 결과적으로는 사람들이 의욕을 잃고 kernelCTF 제출 자체를 고려하지 않게 될 가능성이 높아 보임
    • 맞지만 사실상 거의 모든 CTF에는 이런 요소가 있음

  • 이해한 게 맞다면 4초짜리 작업 증명이 있고, 상금은 한 달에 한 번 지급되는 구조임
    정말 매달 사람들이 경쟁할 만큼 익스플로잇이 그렇게 많나?

    • 서버는 2주마다 열렸음. 작업 증명은 최대한 많은 연결 요청을 스팸으로 보내려는 유인을 줄이기 위해 연결을 약간 느리게 만드는 장치였음
      공개 CTF는 어렵다. 결국 어떤 팀은 결승선까지 달리는 과정에서 DDoS와 비슷한 행동을 하게 됨. 이후 Google은 작업 증명 단계를 제거했음
    • 이건 원격 코드 실행이 아니라 로컬 권한 상승 익스플로잇, 즉 일반 사용자에서 root가 되는 종류임. 권한 상승 버그는 흔해 빠졌음
    • Linux 커널 보안이라는 신화는 말 그대로 신화일 뿐임

  • 대단한 내용이지만, 이 챌린지에서 이기기 위해 넘어야 하는 장애물들을 보면 코미디처럼 읽힘. 진짜 루브 골드버그 장치 같음

  • 이 글에서 언급한 52진수 표현을 더 알고 싶다면 오늘 프런트페이지의 다른 글도 볼 만함: https://news.ycombinator.com/item?id=44132673

  • 사소한 지적이지만, 정적 링크는 인라이닝을 해 주는 게 아니라 PLT 오버헤드만 제거함. 인라이닝 기회를 늘리는 건 LTO임

  • 왜 경쟁을 시키는지 이해가 안 됨. 고유 익스플로잇마다 그냥 보상하면 안 되나?

    • 이런 멋진 프로그램을 운영하는 데 상사가 엄격하게 고정된 예산을 원하기 때문임. 이런 프로그램의 명분은 적어도 일부는 버그 구매가 아니라 익스플로잇과 완화 기법의 동향을 측정하는 데 있음
      그리고 Linux는 너무 버그가 많아서 모든 0-day에 돈을 주기 시작하면 통제 불가능해짐. Google도 한때 사람들이 쌓아 둔 버그를 털어내려고 경쟁 없는 기간 한정 프로모션을 했고, 모든 0-day를 인정했더니 제출이 폭주했음. 동시에 커뮤니티를 화나게 하고 싶지는 않으니 이런 구조가 된 것임

  • 세월이 이렇게 흘렀는데도 전문가들이 3초만에 Linux 머신을 장악할 수 있다는 건 좀 우울함

답변달기