Cách đánh bại PoW kernelCTF của Google bằng AVX512

• Nhóm Crusaders of Rust định gửi exploit cho CVE-2025-38001 trong Linux packet scheduler, nhưng do cơ chế ai đến trước được trước của kernelCTF, điểm quyết định không phải bản thân lỗi mà là rút ngắn PoW
• Quy trình gửi gồm kết nối lúc 12:00 UTC, khoảng 4 giây PoW, khoảng 2,5 giây khởi động VM, chạy exploit rồi gửi Google Form; kỷ lục gửi 4,5 giây ở vòng trước đã cho thấy nút thắt cổ chai
• PoW mục tiêu là VDF “sloth”, một phép tính tuần tự lặp lại bình phương modulo 2^1279 - 1 trên số nguyên 1280 bit, nên khó rút ngắn bằng cách tăng số lõi CPU/GPU
• Sau khi giảm xuống 1,9 giây bằng GMP/C++ và phép rút gọn modulo Mersenne, rồi khoảng 1,4 giây bằng liên kết tĩnh với -march=native, họ dùng fused multiply-add số nguyên 52 bit của AVX512IFMA để rút xuống khoảng 0,21 giây trên Ryzen 9950X
• Ngày 16/5/2025, nhóm đã gửi flag chỉ trong 3,6 giây bằng máy chủ Google Cloud Zen 5 và đường gửi POST được tối ưu; đến 28/5, kernelCTF thông báo loại bỏ PoW

---

Điều kiện cạnh tranh: vấn đề là gửi nhanh hơn, không phải lỗi

• Tháng 5/2025, William Liu và Savy Dicanosa của nhóm Crusaders of Rust phát hiện lỗi use-after-free CVE-2025-38001 trong Linux packet scheduler và phát triển exploit
  • William tìm thấy lỗi khi fuzz Linux cho luận văn thạc sĩ
  • Savy giảm thời gian chạy exploit xuống còn khoảng 0,55 giây
• kernelCTF của Google mở cửa sổ gửi bài hai tuần một lần vào đúng trưa UTC, với cơ chế chỉ đội đầu tiên exploit được máy chủ và gửi flag lên Google Form mới nhận thưởng
• Việc gửi luôn diễn ra theo cùng một thứ tự
  • 12:00:00 UTC kết nối tới máy chủ kernelCTF
  • Giải proof of work, khoảng 4 giây
  • Chờ instance khởi động, khoảng 2,5 giây
  • Tải lên và chạy exploit
  • Gửi flag lên Google Form
• Tiền thưởng dự kiến là 51.000 USD
  • Thưởng cơ bản 21.337 USD
  • Thưởng độ ổn định khi thực thi 10.000 USD
  • Thưởng lỗi 0-day 20.000 USD

Kỷ lục gửi trước đó làm lộ nút thắt PoW

• Trong cửa sổ gửi ngày 2/5/2025, bài gửi đầu tiên đến sau đúng trưa 4,5 giây
• Chỉ riêng PoW khoảng 4 giây và khởi động VM khoảng 2,5 giây đã cần 6,5 giây, nên kỷ lục 4,5 giây không khớp với tính toán đơn giản
• Do đặc tính làm tròn trong mã máy chủ kernelCTF, instance VM thực tế được khởi động lúc 11:59:59, nên mâu thuẫn về thời gian biến mất
• Dù vậy, timestamp tạo flag cho thấy đội thắng đã giải PoW trong chưa tới 1 giây
• Nếu đội cạnh tranh dùng FPGA, PoW dưới 1 giây có thể đã khả thi
  • FPGA là phần cứng tùy biến có thể thực hiện một tác vụ cụ thể rất nhanh
  • Nó không phù hợp cho tác vụ mục đích chung, đắt và khó lập trình

sloth VDF: PoW khó song song hóa

• PoW của kernelCTF là hàm trì hoãn có thể xác minh (VDF) tên “sloth”
• VDF là primitive mật mã chứng minh thời gian đã trôi qua bằng một phép tính tuần tự dài, còn bằng chứng kết quả có thể được xác minh tương đối nhanh
• Vì bản thân phép tính là tuần tự, việc đưa thêm lõi CPU hay GPU vào cũng khó giảm thời gian chạy
• Vòng lặp lõi cần tối ưu có cấu trúc như sau
  • difficulty=7337
  • Với mỗi vòng lặp difficulty, thực hiện 1277 lần x = (x * x) % (2 ** 1279 - 1)
  • Sau đó đảo bit thấp nhất của x
• Bản triển khai tham chiếu của Google dùng gmpy trong Python, còn gmpy là binding Python cho GMP
  • GMP là thư viện số nguyên đa độ chính xác triển khai các kernel cộng/nhân theo từng nền tảng bằng assembly

Tối ưu bước đầu dựa trên GMP

• Tối ưu đầu tiên là phép rút gọn modulo tận dụng việc 2^1279 - 1 là số Mersenne
  • Chia tích trung gian 2560 bit thành 1279 bit thấp và các bit cao rồi cộng lại
  • Nếu kết quả lớn hơn hoặc bằng modulus thì trừ một lần, thay cho phép toán %
• Để giảm overhead Python FFI, họ chuyển sang C++, và phiên bản này chạy trong 1,9 giây trên M1 MacBook Pro
• William biên dịch libgmp cục bộ với -march=native và liên kết tĩnh, giảm xuống khoảng 1,4 giây trên laptop Intel Ice Lake
• Một solver tối ưu tương tự viết bằng Rust cũng dùng kỹ thuật Mersenne này nhưng mất khoảng 2,4 giây
• Sau đó họ cũng thử FLINT, nhưng tốc độ gần như ngang GMP

Viết lại phép bình phương số nguyên lớn bằng AVX512IFMA

• AVX512 là phần mở rộng ISA x86 của Intel, tăng số lượng và độ rộng thanh ghi vector, đồng thời thêm dự đoán mask và nhiều lệnh mới
  • Từ Alder Lake, Intel đã vô hiệu hóa hỗ trợ AVX512 trên CPU client
  • Trong mảng máy chủ, hỗ trợ này vẫn tiếp tục; AMD triển khai AVX512 trên cả CPU tiêu dùng và máy chủ ở Zen 4 và Zen 5
• Điểm then chốt là AVX512IFMA
  • vpmadd52luq: cộng nửa thấp của tích 52 bit vào bộ tích lũy 64 bit
  • vpmadd52huq: cộng nửa cao của tích 52 bit vào bộ tích lũy 64 bit
• Các lệnh này tính phần thấp và cao của tích 52×52→104 bit rồi tích lũy vào thanh ghi vector
• Zen 5 có đường dữ liệu 512 bit nên có thể bắt đầu 2 lệnh như vậy mỗi chu kỳ xung
• Cơ số tự nhiên là 2^52, và số nguyên 1280 bit được biểu diễn bằng 25 limb 52 bit
  • Một thanh ghi zmm 512 bit chứa được 8 limb
  • Toàn bộ giá trị nằm trong 4 thanh ghi zmm

Bố trí phép nhân và rút gọn Mersenne

• Phép bình phương 1280 bit được triển khai bằng cách bình phương 25 limb 52 bit để tạo kết quả trung gian 50 limb
• Tận dụng tính đối xứng của phép bình phương để giảm gần một nửa số phép nhân cần thiết
  • Thành phần đường chéo ai^2
  • Hạng chéo 2 * ai * aj với i < j
• Khi tính hạng chéo, họ nhân cửa sổ trượt gồm 8 limb liên tiếp với một multiplier limb để giảm số lần shuffle
• Dùng merge masking của AVX512 để không tích lũy những phép nhân không nằm trong tổng cuối cùng
• Phép rút gọn modulo được thực hiện bằng cách cộng 1279 bit cao vào 1279 bit thấp
  • Vì phần tử bộ tích lũy có thể vượt 2^52 - 1, việc lan truyền carry được hoãn đến sau phép cộng
  • Việc kết quả có lớn hơn hoặc bằng 2^1279 - 1 hay không được xác định bằng bit thứ 1280 có bằng 1 hay không
  • Trừ 2^1279 - 1 tương đương với xóa bit thứ 1280 và cộng 1 vào limb thấp nhất
• Ở bước cuối vẫn còn khả năng overflow rất nhỏ
  • Nếu limb cuối cùng đúng bằng 2^52 - 1 thì cần lan truyền carry
  • Với PoW ngẫu nhiên, xác suất xảy ra được xem là khoảng 2 trên 2 tỷ mỗi lần chạy nên bị bỏ qua

Các vi tối ưu giúp giảm từ 0,45 giây xuống 0,21 giây

• Phiên bản AVX512IFMA đầu tiên xử lý PoW trong khoảng 0,45 giây trên Ryzen 9950X thuê
• Lệnh multiply-add có độ trễ 4 chu kỳ và có thể bắt đầu 2 lệnh mỗi chu kỳ, nên để bão hòa đơn vị nhân cần ít nhất 8 bộ tích lũy
  • Trước đó họ chỉ có 7 bộ tích lũy
  • Họ chuyển sang dùng tổng cộng 14 bộ tích lũy, gồm 7 cho nửa thấp và 7 cho nửa cao, rồi cộng lại ở cuối
  • Thay đổi này giúp giảm xuống khoảng 0,32 giây
• Khi unroll vòng lặp, GCC và clang sinh vbroadcastsd zmm, m64; trong quá trình cấp phát thanh ghi, thiếu thanh ghi vector gây stack spill và reload
  • Họ dùng inline assembly để buộc vpmadd52luq/vpmadd52huq dùng memory broadcast operand
  • Không đặt multiplier limb vào thanh ghi vector riêng, mà đọc từ bộ nhớ và sao chép sang mọi phần tử vector
  • Broadcast load này không dùng tài nguyên vector ALU mà được xử lý ở load unit
  • Ở bước này thời gian giảm xuống khoảng 0,23 giây
• Cách lưu số nguyên đã căn chỉnh vào bộ nhớ rồi dùng tải không căn chỉnh để tạo window gây store-forwarding stall
  • Họ dùng valignq để mô phỏng tải không căn chỉnh bên trong thanh ghi zmm, giảm truy cập bộ nhớ
  • Thời gian PoW cuối cùng là khoảng 0,21 giây

Kết quả gửi ngày 16/5/2025

• Nhóm chuẩn bị lượt gửi cuối cùng lúc 4:30 sáng PST ngày 16/5/2025
• Họ giảm độ trễ bằng cách dùng máy chủ Google Cloud Zen 5 tại Hà Lan, gần về mặt địa lý với máy chủ gửi Google Form
• Vài phút trước khi gửi, họ chặn và ghi lại yêu cầu POST Google Form bằng một flag giả
  • Bryce Casaje và Larry Yuan thiết kế và tối ưu chương trình gửi Form
  • Max Cai cũng hỗ trợ phát triển và gửi
• Lúc 5:00, máy chủ kết nối tới kernelCTF, giải PoW, chạy exploit tối ưu của Savy, rồi chèn flag vào yêu cầu POST và gửi đi
• Kết quả là lượt gửi trong 3,6 giây, nhanh nhất trong lịch sử kernelCTF khi đó
• Cùng ngày, nhà vận hành kernelCTF xác nhận đủ điều kiện nhận bounty

Loại bỏ PoW và công bố solver cuối cùng

• Ngày 28/5/2025, nhà vận hành kernelCTF koczkatamas thông báo loại bỏ PoW
• Khi PoW biến mất, cuộc cạnh tranh slot chuyển trọng tâm sang thời gian chạy exploit và độ trễ mạng
• Thay đổi này giúp các đội có thể cạnh tranh trong cùng điều kiện với đội chuyên nghiệp mà không cần FPGA hay kiến thức tối ưu inline assembly
• Mã solver cuối cùng là kết quả của khoảng 12 giờ làm việc trong ngày 14–15/5/2025 và được phát hành theo GNU AGPL 3.0
• Ví dụ build là gcc main.c -O3 -march=znver5 -masm=intel -lgmp

[GN⁺]

Ý kiến trên Hacker News

• Nội dung rất hay. Cách này cũng rất giống với triển khai RSA tối ưu hóa cho AVX-512, vì RSA cũng phải thực hiện phép lũy thừa với số mũ rất lớn.
  Bài báo này[1] bàn về cách RSA thực hiện windowing, và cũng có công thức cho thấy kích thước cửa sổ có thể là tùy ý. Triển khai RSA bằng AVX-512 còn lưu sẵn kết quả phép nhân trong phạm vi [0..2^{window-size}) vào bảng; với mỗi cửa sổ, nó lấy kết quả đó từ bảng[2] rồi chỉ thực hiện shift/tái sắp xếp.

  1. https://dpitt.me/files/sime.pdf (lấy từ tạp chí nên tôi host trên domain của mình)

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

  • Thú vị thật. Có lẽ lúc phát triển tôi nên xem cái này. Đoạn code đó, chẳng hạn, nên có thêm một phiên bản dành cho Zen 5, và nếu dùng thanh ghi zmm thì có vẻ throughput phép nhân có thể tăng gấp đôi.
    Ngoài ra, họ đang chuyển thanh ghi mask sang thanh ghi đa dụng để làm phép toán số học, nhưng trên Zen 4/5 thì đó không phải là tối ưu. Riêng chuyện có thật sự cần lan truyền carry trong một lần hay không cũng làm tôi tò mò. Trong code của tôi, tôi giả định carry chỉ xảy ra một lần và nếu cần thì quay lại bằng vòng lặp, nhờ đó giảm latency trong trường hợp thông thường. Tuy nhiên nếu có nhánh thì có thể phát sinh vấn đề tấn công timing.
  • dpitt.me/files/sime.pdf cũng có thể đưa lên archive.org: https://archive.org/download/sime_20250531/sime.pdf

• Phần nói “dù [AVX512] đã được hỗ trợ trên CPU tiêu dùng qua nhiều thế hệ” nghe hơi lạ.
  Trước Rocket Lake (thế hệ 11), AVX-512 chỉ có trên CPU cho giới đam mê cao cấp, CPU Xeon và một số bộ xử lý di động; gọi bộ xử lý di động là CPU tiêu dùng thì cũng hơi gượng. Ở thế hệ 12, do kiến trúc gồm core hiệu năng/hiệu quả nên vài tháng sau nó bị vô hiệu hóa trên các core đó và không xuất hiện lại nữa. Dù vậy, nếu AMD đạt được mức thành công nhất định với AVX-512 thì tôi nghĩ khả năng cao Intel sẽ đưa nó trở lại. Nhân tiện, tôi vẫn đang dùng Intel i9-11900.

  • Đúng hướng rồi. Sách trắng AVX10[1] được Intel cập nhật vài tháng trước dường như cũng xác nhận điều này. Tài liệu nêu rõ AVX 512-bit sẽ trở thành chuẩn cho cả P-core lẫn E-core, và sẽ rời khỏi cấu hình chỉ 256-bit.
    Đây có vẻ là tín hiệu mạnh rằng AVX-512 sẽ thực sự quay lại không chỉ trên server mà cả trên CPU tiêu dùng tương lai có E-core. Có lẽ là để bắt kịp việc AMD áp dụng AVX-512 rộng hơn.

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

  • CPU thế hệ 12 có core hiệu năng vốn dĩ không hề báo hỗ trợ AVX512, cũng không được bật mặc định.
    Vì E-core không có AVX512 do vấn đề diện tích, toàn bộ CPU bị xem là không hỗ trợ AVX512. Chỉ là có thể lợi dụng hành vi đặc biệt của một số tùy chọn BIOS để tắt E-core rồi bật AVX512 trên phần CPU còn lại, đổi lại phải từ bỏ E-core.

• Kỷ lục thắng cuộc là 3,6 giây, nhưng vị trí thứ hai là 3,73 giây; nếu làm tròn cùng số chữ số như kỷ lục thắng thì là 3,74 giây. Vậy có nên xem rằng đội thứ hai cũng đã tối ưu hóa proof-of-work, hoặc dùng FPGA không?
  Tác giả nói các bài nộp trước dùng FPGA đắt tiền nhưng vẫn trên 4 giây. Vậy có khả năng bài nộp hạng hai tuần đó là bài nộp nhanh thứ hai trong lịch sử; nếu vậy có lẽ họ cũng đã nhắc gì đó về nó chứ?

  • Trong ảnh có ghi dupe. Có lẽ đội của bài gốc đã thử nộp song song bằng nhiều tài khoản.

• Ấn tượng đấy, nhưng có vẻ tối ưu hóa nhầm mục tiêu. CTF không nên trở thành cuộc chiến vận hành nộp bài.
  Có lẽ sẽ tốt hơn cho tất cả nếu mọi đội gửi flag trong khung nộp bài đều chia nhau tiền thưởng.

  • Cấu trúc kiểu này cũng khiến người ta giữ exploit lại thay vì báo ngay. Nếu lần này không nhận được, họ sẽ nhắm lần nộp sau; ngay cả không có trò căn thời điểm nộp, vẫn có động cơ trì hoãn.
    Vì vậy trên thực tế nó có thể đang tích cực khuyến khích hành vi “sai”.
  • Điều đó lại sẽ trở thành một metagame khác. Tôi chưa nghĩ kỹ, nhưng có vẻ kết cục là người ta mất động lực và không còn cân nhắc nộp kernelCTF nữa.
  • Đúng, nhưng thực tế gần như mọi CTF đều có yếu tố như vậy.

• Nếu tôi hiểu đúng thì có một proof-of-work mất 4 giây, và tiền thưởng được trả mỗi tháng một lần.
  Thật sự có nhiều exploit đến mức mọi người cạnh tranh hằng tháng sao?

  • Server được mở hai tuần một lần. Proof-of-work là cơ chế làm chậm kết nối một chút để giảm động cơ spam càng nhiều yêu cầu kết nối càng tốt.
    CTF công khai rất khó. Rốt cuộc một số đội sẽ có hành vi gần giống DDoS trong quá trình chạy tới vạch đích. Sau đó Google đã bỏ bước proof-of-work.
  • Đây không phải thực thi mã từ xa mà là exploit leo thang đặc quyền cục bộ, tức từ người dùng thường lên root. Lỗi leo thang đặc quyền thì nhiều vô kể.
  • Huyền thoại về bảo mật kernel Linux đúng nghĩa chỉ là huyền thoại.

• Nội dung rất đáng nể, nhưng nhìn các chướng ngại phải vượt qua để thắng thử thách này thì đọc như hài. Đúng là một cỗ máy Rube Goldberg.

• Nếu muốn tìm hiểu thêm về biểu diễn cơ số 52 được nhắc trong bài này, có thể xem một bài khác trên trang nhất hôm nay: https://news.ycombinator.com/item?id=44132673

• Bắt lỗi nhỏ thôi, nhưng liên kết tĩnh không giúp inline; nó chỉ loại bỏ overhead PLT. Thứ làm tăng cơ hội inline là LTO.

• Tôi không hiểu vì sao phải cho cạnh tranh. Sao không thưởng đơn giản cho mỗi exploit độc nhất?

  • Vì sếp muốn có ngân sách cố định nghiêm ngặt để vận hành một chương trình hay ho như thế này. Lý do tồn tại của chương trình kiểu này ít nhất một phần là để đo xu hướng exploit và kỹ thuật giảm thiểu, chứ không chỉ để mua bug.
    Và Linux có quá nhiều bug, đến mức nếu bắt đầu trả tiền cho mọi 0-day thì sẽ mất kiểm soát. Google cũng từng có một đợt khuyến mãi có thời hạn, không cạnh tranh, nhằm để mọi người xả các bug đã tích trữ; khi họ công nhận mọi 0-day thì lượng bài nộp bùng nổ. Đồng thời họ cũng không muốn làm cộng đồng tức giận, nên mới thành cấu trúc như vậy.

• Sau ngần ấy năm mà các chuyên gia vẫn có thể chiếm quyền một máy Linux chỉ trong 3 giây thì hơi buồn.