Cách Google kernelCTF bị đánh bại ở PoW bằng AVX512

• Nhóm Crusaders of Rust đã phát hiện lỗi use-after-free trong bộ lập lịch gói của Linux và phát triển mã khai thác
• Do cần một lời giải PoW (Proof of Work) thật nhanh cho cuộc thi Google kernelCTF, nhóm đã thử tối ưu hóa hiệu năng ở mức cao
• Bằng assembly tự viết và tối ưu SIMD tận dụng lệnh AVX512IFMA, họ đạt tốc độ gần gấp 7 lần so với các bản triển khai Python/GMP và Rust trước đó
• Tinh chỉnh chi tiết từ nguyên lý hoạt động, phép toán mô-đun, quản lý bộ nhớ đến cách dùng thanh ghi đã rút thời gian xử lý PoW xuống còn 0,21 giây
• Cuối cùng, nhóm gửi bài thành công lên kernelCTF với thời gian ngắn nhất từng có (3,6 giây), sau đó chính sách PoW đã chính thức bị bãi bỏ

---

Tổng quan và mục đích

• Vào tháng 5 năm 2025, William Liu và Savy Dicanosa của nhóm Crusaders of Rust đã tìm ra một lỗ hổng use-after-free trong Linux và tham gia cuộc thi kernelCTF của Google
• Bài viết này nói về quá trình tối ưu hóa để giải nhanh cơ chế kiểm chứng PoW (Proof of Work), nhằm gửi bài nhanh hơn các đội toàn cầu khác trong cuộc đua bounty đầy giới hạn thời gian

Quy trình nộp kernelCTF và bối cảnh cạnh tranh

• kernelCTF là một cuộc thi có tiền thưởng rất lớn, nên các đội bảo mật chuyên nghiệp trên khắp thế giới tham gia với quyết tâm tối đa, từ tự động hóa nộp bài đến tối ưu PoW
• Mỗi đợt mở cửa nộp bài (2 tuần một lần), chỉ đội nhanh nhất duy nhất nhận được tiền thưởng
• Quy trình nộp bài:
  • Kết nối tới máy chủ đúng giờ
  • Giải PoW mất vài giây
  • Chờ VM khởi động
  • Chạy mã khai thác và lấy flag
  • Gửi Google Form
• Gần đây đã từng có kỷ lục gửi flag thành công chỉ trong 4,5 giây, nhưng riêng PoW và khởi động VM đã mất tới 6,5 giây, nên tăng tốc phần giải PoW là yêu cầu bắt buộc

Phân tích thuật toán PoW (VDF-Sloth) và tối ưu đầu tiên

• PoW của kernelCTF dùng sloth VDF, một verifiable delay function dựa trên tính toán tuần tự
  • Với số nguyên 1280 bit x, lặp lại phép bình phương mô-đun và đảo bit
• Ngay cả ở các bản triển khai sẵn có (Pyhton+gmpy và Rust), song song đa lõi cũng không giúp ích và GMP vốn đã được tối ưu khá tốt
• Tuy nhiên, bằng cách tận dụng việc phép toán mô-đun dựa trên số Mersenne (2^1279-1), họ đã viết tay phần mô-đun nhanh hơn bằng C++ và cải thiện hiệu năng xuống còn 1,9~1,4 giây

Bước ngoặt sang AVX512IFMA và triển khai siêu nhanh dựa trên SIMD

• Sau đó, nhóm chuyển hướng sang ISA AVX512, đặc biệt là AVX512IFMA (lệnh nhân và tích lũy 52 bit)
• Số 1280 bit được chia thành các limb 52 bit để tối đa hóa tăng tốc SIMD (25 limb → dùng 4 thanh ghi zmm)
• Họ lặp đi lặp lại việc tinh chỉnh ở mức thấp như tính đối xứng của phép bình phương mô-đun, mặt nạ tích lũy, broadcast bộ nhớ, tối ưu gán thanh ghi và so sánh không nhánh
• Bằng cách dùng ASM (inline assembly) để ngăn compiler tạo ra các thao tác spill/reload thanh ghi kém hiệu quả, đồng thời tối ưu broadcast và masking, tốc độ cuối cùng được đẩy xuống 0,21 giây

Tự động hóa nộp PoW và kịch bản thi đấu thực tế

• Trong lần nộp cuối cùng, họ sử dụng máy chủ Google Cloud Zen 5 (khu vực Amsterdam) để giảm cả độ trễ mạng đến Google Form
• Với chương trình nộp tự động (vá POST request tới Google Form, tối ưu nhờ phối hợp nội bộ trong nhóm), họ đã gửi flag thành công chỉ trong 3,6 giây, mức nhanh nhất từng có
• Sau đó, ban tổ chức kernelCTF chính thức công bố hủy bỏ chính sách PoW, giúp chấm dứt cuộc đua tối ưu PoW và cho phép công khai kỹ thuật này

Chi tiết triển khai nâng cao

Tối ưu phép toán mô-đun

• Phép toán mô-đun theo 2^1279-1 (Prime) được thay bằng vài phép dịch bit và số học cơ bản, cho tốc độ rất cao so với GMP tiêu chuẩn

Bình phương big-int dựa trên AVX512IFMA

• Tận dụng các lệnh nhân-tích lũy 52 bit của AVX512 (vpmadd52luq, vpmadd52huq) để nhân và cộng dồn song song theo từng cụm 8 limb
• Do cấu trúc 25 limb nên dữ liệu được phân tán trên 4 zmm, với logic được thiết kế để giảm tối đa việc masking/tích lũy dư thừa

Bố trí dữ liệu và sử dụng thanh ghi

• Loại bỏ nút thắt SIMD bằng cách sắp xếp dữ liệu theo offset, bố trí kiểu bậc thang và tái sắp xếp giữa các thanh ghi (valignq, broadcast)
• Tăng gấp đôi số accumulator để giữ thông lượng tối đa mà không phải chờ đơn vị nhân bị nhàn rỗi
• Ngay cả carry propagation cũng chỉ được thực hiện ở mức tối thiểu cần thiết

Tự động hóa nộp bài cuối cùng và cộng tác

• Bố trí thành viên để “đánh chiến dịch” vào khung giờ rạng sáng, đồng thời tối ưu vị trí mạng và việc thực thi exploit
• Trong lần nộp thực tế, toàn bộ quá trình từ giải PoW, chạy exploit, chèn flag đến gửi POST request tới Google Form đều được tự động hóa nhất quán

Kết luận và ý nghĩa

• Việc tối ưu PoW cho kernelCTF là công việc đòi hỏi hiểu biết giải phẫu phần cứng từ mức bit, bộ nhớ, thanh ghi cho đến CNN
• Khi chính sách PoW biến mất, trọng tâm cạnh tranh giờ chỉ còn là tốc độ mạng và tốc độ exploit thuần túy
• Trường hợp này cho thấy sự giao thoa giữa hacking thực chiến và tính toán hiệu năng cao, đồng thời hứa hẹn kiến thức tối ưu thuật toán và mã nguồn mở tiếp tục đóng góp cho cộng đồng nghiên cứu

Tham khảo và phụ lục

• Toàn bộ mã của thuật toán PoW, các hàm chuyển đổi (GMP <-> mảng 52 bit), phép toán mô-đun dựa trên SIMD và mã ASM tinh chỉnh đều đã được công khai
• Dù là mã khá “thô” được phát triển dồn dập trong khoảng 12 giờ để đưa ngay vào thực chiến, nó vẫn được phát hành theo giấy phép GNU AGPL 3.0
• Nếu có câu hỏi hoặc muốn cộng tác về VDF, có thể liên hệ qua Discord(@forevermilk)

[GN⁺]

Ý kiến trên Hacker News

• Đội chiến thắng với 3,6 giây và đội về nhì ghi nhận 3,73 hoặc 3,74 giây; điều này khiến tôi nghĩ đội hạng hai cũng đã tối ưu PoW hoặc có thể dùng FPGA. So với các bài nộp FPGA trước đây đều trên 4 giây, tôi thấy hơi tiếc là tác giả không nhắc rằng thành tích hạng nhì tuần này cũng có thể là một kỷ lục lịch sử.

• Tôi có cảm giác phương pháp này rất giống với cách dùng trong các triển khai RSA tối ưu cho AVX-512, vì RSA cũng cần các phép lũy thừa rất lớn. Bài báo (https://dpitt.me/files/sime.pdf) bàn về kỹ thuật windowing và việc có thể điều chỉnh kích thước cửa sổ tùy ý. Điểm bổ sung trong triển khai RSA AVX-512 là kết quả phép nhân được lưu vào bảng trong phạm vi [0..2^{window-size}) để dùng cho từng cửa sổ. Có thể xem ví dụ thực tế trong rsaz-2k-avx512.pl của aws-lc.

  • Tôi cũng thấy tiếc vì nếu biết trước những nội dung này thì có lẽ đã tham khảo được khi phát triển. Trên Zen 5, có thể kỳ vọng thông lượng nhân đôi nhờ tận dụng thanh ghi zmm. Trong mã hiện tại, thanh ghi mask bị chuyển sang GPR, điều này không hiệu quả trên Zen 4/5. Tôi cũng băn khoăn liệu việc truyền carry có nhất thiết phải hoàn tất trong một lần hay không. Trên thực tế, mã giả định carry chỉ phát sinh một lần rồi lặp lại, điều này giúp giảm độ trễ trong đa số trường hợp, dù vẫn còn khả năng bị timing attack do nhánh rẽ.

• Về nhận định rằng AVX512 đã được hỗ trợ trên CPU tiêu dùng qua nhiều thế hệ, tôi nhớ là trước Rocket Lake (thế hệ 11), AVX512 chỉ có trên dòng enthusiast, Xeon và một số bộ xử lý di động. Sau khi thế hệ 12 và kiến trúc P/E core xuất hiện thì nó bị vô hiệu hóa và biến mất chỉ sau vài tháng. Tôi đoán nếu AMD thành công với AVX512 thì Intel sẽ đưa nó trở lại. Hiện tôi đang dùng i9-11900.

  • CPU P-core thế hệ 12 hoàn toàn không hỗ trợ hay quảng bá AVX512, và mặc định bị tắt. Vì diện tích dành cho E-core nên toàn bộ CPU không tích hợp AVX512. Chỉ có thể dùng mẹo trong BIOS để tắt E-core rồi bật AVX512 trên các core còn lại, nhưng phải đánh đổi bằng việc bỏ E-core.
  • Trong whitepaper Intel AVX10 gần đây (https://cdrdv2.intel.com/v1/dl/getContent/784343), Intel đưa ra AVX 512-bit như một tiêu chuẩn cho cả P-core lẫn E-core. Điều này cho thấy AVX-512 không còn bị giới hạn ở cấu hình 256-bit và chỉ dành cho máy chủ, mà có thể thực sự quay lại với CPU tiêu dùng trong tương lai. Có thể hiểu đây là động thái Intel theo sau việc AMD mở rộng AVX-512.

• Tôi nghi ngờ về bản chất của cuộc thi CTF này. Thay vì thi tốc độ nộp bài, có lẽ sẽ tốt hơn nếu mọi đội nộp được flag trong một khung thời gian nhất định đều chia nhau tiền thưởng.

  • Có ý kiến cho rằng cách đó có thể tạo ra metagame khiến người tham gia không công bố ngay thông tin exploit mà giữ lại cho các vòng sau, từ đó cản trở việc báo cáo ngay lập tức. Ngoài ra còn có lo ngại về các tác dụng phụ như khuyến khích cạnh tranh không mang tính xây dựng xoay quanh chiến lược chọn thời điểm nộp bài.
  • Cấu trúc metagame sẽ thay đổi, và thậm chí có thể làm giảm động lực tham gia, khiến nhiều người không còn cân nhắc nộp bài cho kernelCTF.

• Nếu tôi hiểu đúng thì đây là proof of work 4 giây và cơ chế trả thưởng mỗi tháng một lần; tôi tò mò không biết có thật là mỗi tháng lại xuất hiện nhiều exploit đến mức cạnh tranh khốc liệt như vậy không.

  • Máy chủ được mở hai tuần một lần, và PoW chỉ nhằm tạo ra một chút độ trễ để ngăn các yêu cầu truy cập quá mức. Các CTF công khai đôi khi cạnh tranh đến mức có cả những chiến dịch giống DDoS. Sau đó Google đã loại bỏ bước proof of work.
  • Có người cho rằng huyền thoại về bảo mật của nhân Linux thực chất chỉ là ảo tưởng.
  • CTF lần này không phải remote code execution mà là exploit leo thang đặc quyền, tức từ người dùng thường lên root; lỗi leo thang đặc quyền thực sự rất phổ biến.

• Đây là một thử thách đáng kinh ngạc, nhưng tôi ấn tượng với sự phức tạp và phần nào khôi hài của các chướng ngại cần vượt qua để chiến thắng. Cảm giác như một cỗ máy Rube Goldberg vậy.

• Nếu muốn tìm hiểu thêm về phần base-52 được nhắc trong bài, tôi khuyên nên xem bài này đang rất hot hôm nay (https://news.ycombinator.com/item?id=44132673).

• Toán học thật tuyệt.

• Giới thiệu về sloth, một VDF (Verifiable Delay Function) được dùng trong proof of work: nó yêu cầu một chuỗi tính toán dài để chứng minh thời gian đã trôi qua, trong khi kết quả có thể được xác minh rất nhanh. Vì việc tính toán mang tính tuần tự nên dù huy động nhiều core cũng không thể rút ngắn thời gian chạy. Tôi tự hỏi liệu lĩnh vực này có thể trở thành một thị trường mới cho các hãng sản xuất CPU hay không. Cũng có đề xuất thêm lệnh chuyên dụng cho các vòng lặp sloth và kết quả của nó, cùng với tính năng chống ép xung ở mức phần cứng. Một ý tưởng khác là theo dõi uptime của CPU rồi ký xác nhận cùng với challenge. Điều này giống một dạng proof of stake, vừa cho phép dùng CPU vào mục đích sản xuất vừa chứng minh quyền sở hữu CPU trong n giây.

• Tôi thắc mắc hàm Python trong blog tương đương với triển khai PoW của Google như thế nào; cảm giác khá khó theo dõi.

  • Trong mã của Google, exponent = (p + 1) // 4 chính là 2^1277. Muốn nâng một số lên số mũ khổng lồ đó thì phải bình phương 1277 lần, và hàm Python thực sự làm đúng việc đó. Nếu giá trị ban đầu là x, thì sau mỗi lần bình phương số mũ sẽ nhân đôi, và đến cuối sẽ thành 2^1277; đó là nguyên lý ở đây.