Google के kernelCTF PoW को AVX512 से हराने का तरीका

 (anemato.de)
2 पॉइंट द्वारा GN⁺ 2025-05-31 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Crusaders of Rust टीम Linux packet scheduler के CVE-2025-38001 exploit को submit करना चाहती थी, लेकिन kernelCTF की first-come-first-served संरचना के कारण bug से ज़्यादा PoW को छोटा करना जीत का निर्णायक बिंदु बन गया
  • Submission प्रक्रिया 12:00 UTC पर connect करने, लगभग 4 सेकंड के PoW, लगभग 2.5 सेकंड VM boot, exploit चलाने और Google Form submit करने से गुजरती थी; पिछले round के 4.5 सेकंड submission record ने bottleneck को उजागर किया
  • Target PoW “sloth” VDF था, जो 1280-bit integer पर 2^1279 - 1 modular squaring को बार-बार करने वाली serial calculation थी, इसलिए CPU/GPU cores बढ़ाकर इसे कम करना मुश्किल था
  • GMP/C++ और Mersenne modular reduction से इसे 1.9 सेकंड, फिर -march=native static linking से लगभग 1.4 सेकंड तक घटाने के बाद, AVX512IFMA के 52-bit integer fused multiply-add से Ryzen 9950X पर लगभग 0.21 सेकंड तक छोटा किया गया
  • 16 मई 2025 को टीम ने Zen 5 Google Cloud server और optimized POST submission path के साथ 3.6 सेकंड में flag submit किया, और 28 मई को kernelCTF ने PoW हटाने की घोषणा की

Race condition: समस्या bug नहीं, उससे तेज़ submission था

  • मई 2025 में, Crusaders of Rust टीम के William Liu और Savy Dicanosa ने Linux packet scheduler में use-after-free bug CVE-2025-38001 खोजा और exploit develop किया
    • William ने अपनी master’s thesis के लिए Linux fuzz करते समय यह bug पाया
    • Savy ने exploit execution time को लगभग 0.55 सेकंड तक घटाया
  • Google kernelCTF में हर 2 सप्ताह UTC दोपहर को submission window खुलती थी, और server को exploit करके flag को Google Form में सबसे पहले submit करने वाली टीम को ही reward मिलता था
  • Submission हमेशा इसी क्रम में होता था
    • 12:00:00 UTC पर kernelCTF server से connect
    • proof of work solve करना, लगभग 4 सेकंड
    • instance boot का इंतज़ार, लगभग 2.5 सेकंड
    • exploit upload और run करना
    • flag को Google Form में submit करना
  • Expected bounty $51,000 थी
    • Base reward $21,337
    • Execution reliability reward $10,000
    • 0-day bug reward $20,000

पिछले submission record ने PoW bottleneck दिखाया

  • 2 मई 2025 की submission window में पहला submission दोपहर के बाद 4.5 सेकंड में आया
  • सिर्फ PoW लगभग 4 सेकंड और VM boot लगभग 2.5 सेकंड जोड़ने पर भी 6.5 सेकंड चाहिए थे, इसलिए 4.5 सेकंड का record simple calculation से मेल नहीं खाता था
  • kernelCTF server code की rounding behavior के कारण VM instance असल में 11:59:59 पर boot हो जाता था, इसलिए timing contradiction खत्म हो गया
  • फिर भी flag generation timestamp ने दिखाया कि winning team ने PoW को 1 सेकंड से कम में solve किया था
  • अगर rival team ने FPGA इस्तेमाल किया था, तो 1 सेकंड से कम PoW भी संभव रहा होगा
    • FPGA custom hardware है जो किसी specific task को बहुत तेज़ी से कर सकता है
    • यह general-purpose tasks के लिए उपयुक्त नहीं होता, और इसकी कीमत व programming difficulty ज्यादा होती है

sloth VDF: ऐसा PoW जो आसानी से parallelize नहीं होता

  • kernelCTF PoW “sloth” नाम का verifiable delay function (VDF) था
  • VDF एक cryptographic primitive है जो लंबी serial calculation से समय बीतने का proof देता है, और result proof को तुलनात्मक रूप से जल्दी verify किया जा सकता है
  • Calculation खुद serial है, इसलिए CPU या GPU cores ज़्यादा लगाने से execution time घटाना मुश्किल है
  • Optimize करने वाला core loop इस structure का था
    • difficulty=7337
    • हर difficulty iteration में 1277 बार x = (x * x) % (2 ** 1279 - 1) execute करना
    • इसके बाद x का least significant bit flip करना
  • Google की reference implementation Python में gmpy इस्तेमाल करती थी, और gmpy GMP के लिए Python binding है
    • GMP एक multi-precision integer library है, जिसमें platform-specific addition और multiplication kernels assembly में implement किए गए हैं

GMP आधारित पहला optimization

  • पहला optimization इस बात का फायदा उठाना था कि 2^1279 - 1 एक Mersenne number है
    • 2560-bit intermediate product को lower 1279 bits और upper bits में बांटकर जोड़ा गया
    • अगर result modulus से बड़ा या बराबर हो, तो एक बार subtract करके % operation को replace किया गया
  • Python FFI overhead घटाने के लिए इसे C++ में port किया गया, और यह version M1 MacBook Pro पर 1.9 सेकंड में चला
  • William ने libgmp को locally -march=native के साथ compile करके statically link किया, जिससे Intel Ice Lake laptop पर यह लगभग 1.4 सेकंड तक घट गया
  • Rust में लिखा गया similar optimized solver वही Mersenne technique इस्तेमाल करता था, लेकिन लगभग 2.4 सेकंड लेता था
  • बाद में FLINT भी test किया गया, लेकिन उसकी speed लगभग GMP जैसी ही थी

AVX512IFMA से बड़े integer squaring को फिर से लिखना

  • AVX512 Intel x86 ISA extension है, जो vector registers की संख्या और width बढ़ाता है तथा mask predication और कई नए instructions जोड़ता है
    • Intel ने Alder Lake से client CPUs में AVX512 support disable कर दिया
    • Server segment में support जारी रहा, और AMD ने Zen 4 व Zen 5 में consumer और server CPU दोनों में AVX512 implement किया
  • असली key AVX512IFMA थी
    • vpmadd52luq: 52-bit product के lower half को 64-bit accumulator में जोड़ता है
    • vpmadd52huq: 52-bit product के upper half को 64-bit accumulator में जोड़ता है
  • ये instructions 52×52→104-bit product के lower और upper हिस्से calculate करके vector registers में accumulate करते हैं
  • Zen 5 के पास 512-bit data path था, इसलिए वह प्रति clock ऐसे 2 instructions शुरू कर सकता था
  • Natural radix 2^52 था, और 1280-bit integer को 25 52-bit limbs में represent किया गया
    • एक 512-bit zmm register 8 limbs रख सकता है
    • पूरा value 4 zmm registers में fit हो जाता है

Multiplication layout और Mersenne reduction

  • 1280-bit squaring को 25 52-bit limbs का square लेकर 50-limb intermediate result बनाने के तरीके से implement किया गया
  • Square की symmetry का उपयोग करके required multiplications की संख्या लगभग आधी कर दी गई
    • Diagonal terms ai^2
    • i < j वाले cross terms 2 * ai * aj
  • Cross-term calculation में 8 consecutive limbs की sliding window को single multiplier limb से multiply करके shuffles घटाए गए
  • AVX512 की merge masking से final sum में शामिल न होने वाली multiplications को accumulate न करने की व्यवस्था की गई
  • Modular reduction upper 1279 bits को lower 1279 bits में जोड़कर किया गया
    • Accumulator elements 2^52 - 1 से ऊपर जा सकते थे, इसलिए carry propagation को addition के बाद तक टाला गया
    • Result 2^1279 - 1 से बड़ा या बराबर है या नहीं, यह 1280th bit 1 है या नहीं देखकर तय किया गया
    • 2^1279 - 1 subtract करना 1280th bit clear करके least significant limb में 1 जोड़ने जैसा है
  • अंतिम step में बहुत छोटी overflow possibility बची हुई थी
    • अगर last limb ठीक 2^52 - 1 हो, तो carry propagation चाहिए
    • Random PoW के आधार पर occurrence probability लगभग प्रति run 2 अरब में 2 मानी गई, और इसे ignore किया गया

0.45 सेकंड से 0.21 सेकंड तक की micro-optimizations

  • पहले AVX512IFMA version ने किराए पर लिए गए Ryzen 9950X पर PoW को लगभग 0.45 सेकंड में process किया
  • multiply-add instruction की latency 4 cycles थी और प्रति clock 2 शुरू किए जा सकते थे, इसलिए multiplication units को saturate करने के लिए कम से कम 8 accumulators चाहिए थे
    • पहले सिर्फ 7 accumulators थे
    • इसे lower half के लिए 7 और upper half के लिए 7, कुल 14 accumulators इस्तेमाल करने और अंत में merge करने के तरीके में बदला गया
    • इस बदलाव से समय लगभग 0.32 सेकंड तक घट गया
  • GCC और clang loop unroll करते समय vbroadcastsd zmm, m64 generate करते थे, और register allocation के दौरान vector registers कम पड़ने से stack spill और reload होते थे
    • Inline assembly से vpmadd52luq/vpmadd52huq को memory broadcast operand इस्तेमाल करने के लिए force किया गया
    • Multiplier limb को अलग vector register में रखने के बजाय memory से पढ़कर सभी vector elements में replicate किया गया
    • यह broadcast load vector ALU resources इस्तेमाल नहीं करता और load unit में process होता है
    • इस stage पर समय लगभग 0.23 सेकंड तक घटा
  • Integer को memory में aligned store करने और फिर unaligned load से window बनाने के तरीके से store-forwarding stall हो रहा था
    • valignq से zmm register के अंदर unaligned load की नकल करके memory accesses घटाए गए
    • अंतिम PoW time लगभग 0.21 सेकंड हो गया

16 मई 2025 का submission result

  • टीम ने 16 मई 2025 को सुबह 4:30 PST पर final submission तैयार किया
  • Google Form submission server के geographically करीब Netherlands में Zen 5 Google Cloud server इस्तेमाल करके latency घटाई गई
  • Submission से कुछ मिनट पहले dummy flag के साथ Google Form POST request intercept करके record कर ली गई
    • Bryce Casaje और Larry Yuan ने Form submission program design और optimize किया
    • Max Cai ने भी development और submission में मदद की
  • 5:00 पर server ने kernelCTF server से connect किया, PoW solve किया, Savy का optimized exploit चलाया, फिर flag को POST request में insert करके भेज दिया
  • Result 3.6 सेकंड submission था, जो उस समय kernelCTF इतिहास का सबसे तेज़ submission था
  • kernelCTF operator ने उसी दिन bounty eligibility confirm की

PoW हटाना और final solver release

  • 28 मई 2025 को kernelCTF operator koczkatamas ने PoW removal की घोषणा की
  • PoW हटने के बाद slot competition exploit execution time और network latency पर केंद्रित हो गया
  • इस बदलाव से FPGA या inline assembly optimization knowledge के बिना भी specialized teams जैसी conditions में compete करना संभव हुआ
  • Final solver code 14–15 मई 2025 को लगभग 12 घंटे के काम का result था, और GNU AGPL 3.0 के तहत release किया गया
  • Build example gcc main.c -O3 -march=znver5 -masm=intel -lgmp था

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2025-05-31
Hacker News की टिप्पणियाँ

  • बढ़िया सामग्री है। यह तरीका AVX-512 अनुकूलित RSA इम्प्लीमेंटेशन से भी काफ़ी मिलता-जुलता है, क्योंकि RSA में भी बहुत बड़े exponent ऑपरेशन करने पड़ते हैं
    यह पेपर[1] बताता है कि RSA में windowing कैसे की जाती है, और इसमें यह दिखाने वाला फ़ॉर्मूला भी शामिल है कि window size मनमाना हो सकता है। AVX-512 RSA इम्प्लीमेंटेशन में अतिरिक्त रूप से [0..2^{window-size}) रेंज के multiplication results को एक table में स्टोर किया जाता है, फिर हर window के लिए उस result को table[2] से निकालकर सिर्फ shift/पुनर्व्यवस्था की जाती है

    1. https://dpitt.me/files/sime.pdf (जर्नल से लिया गया, इसलिए मेरे domain पर होस्ट किया है)

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

    • दिलचस्प है। डेवलप करते समय यह देख लिया होता तो अच्छा रहता। उदाहरण के लिए उस कोड का Zen 5 के लिए एक अलग वर्ज़न होना अच्छा होता, और zmm registers इस्तेमाल करने पर multiplication throughput 2 गुना हो सकता है
      साथ ही, वहाँ arithmetic operations की वजह से mask registers को general-purpose registers में move किया जा रहा है, जो Zen 4/5 पर optimal नहीं है। अलग से यह भी सोचने वाली बात है कि क्या carry को सच में एक ही बार में propagate करना ज़रूरी है। मेरे कोड में मैंने माना था कि carry सिर्फ एक बार आएगा और ज़रूरत होने पर loop में वापस जाएगा, ताकि सामान्य मामले में latency कम रहे। हालाँकि branch होने पर timing attack की समस्या हो सकती है
    • dpitt.me/files/sime.pdf को archive.org पर भी अपलोड किया जा सकता है: https://archive.org/download/sime_20250531/sime.pdf

  • “consumer CPU पर कई पीढ़ियों तक [AVX512] को support किया गया” वाला हिस्सा थोड़ा अजीब लगता है
    Rocket Lake (11th gen) से पहले AVX-512 सिर्फ high-end hobbyist CPU, Xeon CPU, और कुछ mobile processors में था, और mobile processors को consumer CPU कहना थोड़ा अस्पष्ट है। 12th gen में performance/efficiency core structure की वजह से कुछ महीनों बाद उस core पर इसे disable कर दिया गया और फिर यह दिखा नहीं। फिर भी अगर AMD को AVX-512 से कुछ सफलता मिलती है, तो मुझे लगता है Intel इसे फिर से लाने की पूरी संभावना रखता है। संदर्भ के लिए, मैं अभी भी Intel i9-11900 इस्तेमाल कर रहा हूँ

    • यह सही रुझान है। कुछ महीने पहले Intel के अपडेटेड AVX10 whitepaper[1] से भी यह बात पुष्ट होती दिखती है। उसमें साफ़ लिखा है कि 512-bit AVX, P cores और E cores दोनों के लिए standard बनेगा, और 256-bit-only configuration से आगे बढ़ा जाएगा
      यह एक मज़बूत संकेत लगता है कि AVX-512 सिर्फ servers में नहीं, बल्कि E cores वाले भविष्य के consumer CPU में भी ठीक से लौट रहा है। शायद Intel, AMD के AVX-512 के व्यापक adoption की बराबरी करना चाहता है

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

    • 12th gen performance core वाले CPU ने शुरू से AVX512 support दिखाया ही नहीं था, और यह default रूप से enabled भी नहीं था
      efficiency cores में die area की समस्या के कारण AVX512 डाला ही नहीं गया था, इसलिए पूरे CPU को AVX512 unsupported माना गया। बस कुछ अजीब BIOS option behavior का फायदा उठाकर efficiency cores को बंद करके बाकी CPU पर AVX512 चालू किया जा सकता था, लेकिन उसकी कीमत E cores छोड़कर चुकानी पड़ती थी

  • जीत का रिकॉर्ड 3.6 सेकंड था, लेकिन दूसरे स्थान पर 3.73 सेकंड था, और अगर जीत के रिकॉर्ड जैसी ही decimal precision पर गोल करें तो 3.74 सेकंड बनता है। तो क्या दूसरे स्थान वाले ने भी proof of work को optimize किया था या FPGA इस्तेमाल किया था?
    लेखक ने कहा था कि पिछला submission महंगे FPGA-based setup से था, और फिर भी 4 सेकंड से ऊपर था। ऐसे में क्या उस हफ़्ते का दूसरा स्थान भी अब तक का दूसरा सबसे तेज़ submission नहीं रहा होगा? लगता है इस बारे में कुछ तो ज़िक्र होना चाहिए था

    • इमेज में dupe लिखा है। शायद मूल पोस्ट वाली टीम ने कई accounts से parallel submissions की कोशिश की होगी

  • प्रभावशाली है, लेकिन लगता है optimization गलत चीज़ पर हो रही है। CTF को submission operations की लड़ाई नहीं बनना चाहिए
    submission window के भीतर flag भेजने वाली सभी teams में prize बाँट देना शायद सबके लिए बेहतर होगा

    • ऐसी संरचना लोगों को exploit तुरंत report करने के बजाय रोककर रखने के लिए भी प्रेरित कर सकती है। अगर इस बार नहीं मिला, तो अगली submission को निशाना बनाने के लिए, submission timing trick न भी हो, तब भी उसे रोके रखने की incentive बनती है
      इसलिए व्यवहार में यह “गलत” आचरण को सक्रिय रूप से बढ़ावा भी दे सकती है
    • तब वह एक अलग meta-game बन जाएगा। मैंने इस पर बहुत गहराई से नहीं सोचा, लेकिन अंत में शायद लोग demotivate हो जाएँ और kernelCTF submission पर विचार ही न करें
    • सही है, लेकिन लगभग हर CTF में किसी न किसी रूप में यह तत्व होता ही है

  • अगर मैं सही समझ रहा हूँ, तो यहाँ 4 सेकंड का proof of work है, और prize महीने में एक बार दिया जाता है
    क्या सच में हर महीने लोगों के प्रतिस्पर्धा करने लायक इतने exploits होते हैं?

    • server हर 2 हफ़्ते में खुलता था। proof of work का मकसद connection requests की ज़्यादा से ज़्यादा spam भेजने की incentive को कम करने के लिए connection को थोड़ा धीमा करना था
      public CTF मुश्किल होते हैं। आख़िरकार कोई team finish line तक दौड़ते-दौड़ते DDoS जैसे व्यवहार करने लगती है। बाद में Google ने proof of work step हटा दिया
    • यह remote code execution नहीं, बल्कि local privilege escalation exploit है, यानी सामान्य user से root बनने वाला प्रकार। privilege escalation bugs बहुत आम हैं
    • Linux kernel security का मिथक सचमुच बस एक मिथक ही है

  • सामग्री शानदार है, लेकिन इस challenge को जीतने के लिए पार करनी पड़ने वाली बाधाओं को देखें तो यह किसी कॉमेडी जैसा पढ़ा जाता है। बिल्कुल एक Rube Goldberg machine जैसा

  • अगर आप इस लेख में बताए गए base-52 representation के बारे में और जानना चाहते हैं, तो आज के front page का एक दूसरा लेख भी देखने लायक है: https://news.ycombinator.com/item?id=44132673

  • छोटी-सी आपत्ति, लेकिन static linking inlining नहीं कराती, वह सिर्फ PLT overhead हटाती है। inlining के अवसर बढ़ाने वाली चीज़ LTO है

  • समझ नहीं आता कि इसे प्रतियोगिता क्यों बनाया गया है। हर unique exploit पर सीधे reward क्यों नहीं दिया जाता?

    • क्योंकि ऐसे शानदार program को चलाने के लिए ऊपर के लोग सख़्ती से fixed budget चाहते हैं। कम से कम आंशिक रूप से ऐसे program का उद्देश्य bugs खरीदना नहीं, बल्कि exploits और mitigations के रुझान को मापना भी होता है
      और Linux में bugs इतने ज़्यादा हैं कि अगर हर 0-day के लिए पैसे देने शुरू कर दिए जाएँ तो बात नियंत्रण से बाहर हो जाएगी। Google ने एक समय बिना competition वाला limited-time promotion भी चलाया था ताकि लोग जमा किए हुए bugs बाहर निकालें, और जब सभी 0-day को स्वीकार किया गया तो submissions की बाढ़ आ गई। साथ ही वे community को नाराज़ भी नहीं करना चाहते, इसलिए यह ढाँचा बना

  • इतना समय बीत जाने के बाद भी यह थोड़ा उदास करता है कि experts अब भी सिर्फ 3 सेकंड में Linux machine पर क़ब्ज़ा कर सकते हैं