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

 (anemato.de)
2 पॉइंट द्वारा GN⁺ 2025-05-31 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • टीम Crusaders of Rust ने Linux packet scheduler में use-after-free bug खोजा और उसका exploit विकसित किया
  • Google kernelCTF प्रतियोगिता में तेज़ PoW (Proof of Work) समाधान की आवश्यकता के कारण high-performance optimization की कोशिश की गई
  • AVX512IFMA instructions का उपयोग कर custom assembly और SIMD optimization के जरिए मौजूदा Python/GMP और Rust implementations की तुलना में लगभग 7 गुना तेज़ प्रदर्शन हासिल किया गया
  • working principle, modular arithmetic, memory management, और register उपयोग तक बारीकी से tuning करके PoW processing time को 0.21 सेकंड तक घटाया गया
  • अंत में अब तक के सबसे कम समय (3.6 सेकंड) में kernelCTF पर सफल submission के बाद PoW policy को आधिकारिक रूप से समाप्त कर दिया गया

अवलोकन और उद्देश्य

  • मई 2025 में Crusaders of Rust टीम के William Liu और Savy Dicanosa ने Linux में use-after-free vulnerability खोजी और Google की kernelCTF प्रतियोगिता में भाग लिया
  • यह लेख PoW (Proof of Work) verification को बहुत तेज़ी से हल करके, सीमित bounty प्रतियोगिता में अन्य global teams से पहले submission करने के लिए किए गए optimization process पर केंद्रित है

kernelCTF submission process और प्रतियोगी पृष्ठभूमि

  • kernelCTF एक ऐसी प्रतियोगिता है जिसमें बड़ी bounty के कारण दुनिया भर की professional security teams submission automation और PoW optimization पर पूरा ज़ोर लगाकर हिस्सा लेती हैं
  • हर submission window (हर 2 हफ्ते में खुलती है) में सबसे तेज़ केवल एक टीम को ही इनाम मिलता है
  • submission प्रक्रिया:
    • तय समय पर server से connect करना
    • कुछ सेकंड लेने वाला PoW solve करना
    • VM boot होने का इंतज़ार
    • exploit code चलाकर flag हासिल करना
    • Google Form submit करना
  • हाल के समय में 4.5 सेकंड में flag submit करने का रिकॉर्ड भी था, लेकिन केवल PoW और VM boot में ही 6.5 सेकंड लग जाते थे, इसलिए PoW solve की speed बढ़ाना अनिवार्य था

PoW(VDF-Sloth) algorithm का विश्लेषण और पहली optimization

  • kernelCTF PoW में sloth VDF नाम की sequential computation आधारित verifiable delay function का उपयोग होता है
    • 1280-bit integer x पर modular squaring और bit inversion की repeated operations की जाती हैं
  • मौजूदा implementations (Python+gmpy और Rust) में पहले से ही multi-core parallelization बेअसर थी, और GMP भी काफ़ी optimized था
  • फिर भी modulo operation के Mersenne number (2^1279-1) आधारित होने का लाभ उठाकर, तेज़ C++ manual modular implementation से performance को 1.9~1.4 सेकंड तक सुधारा गया

AVX512IFMA की ओर बड़ा बदलाव और SIMD आधारित ultra-fast implementation

  • इसके बाद AVX512 ISA, और खास तौर पर AVX512IFMA (52-bit multiplication और accumulation instructions) पर ध्यान गया
  • 1280-bit संख्या को 52-bit limbs में बाँटकर SIMD acceleration को अधिकतम किया गया (25 limbs → 4 zmm registers का उपयोग)
  • modular square operation की symmetry, accumulation masks, memory broadcast, register assignment optimization, branchless comparison जैसे low-level tuning को बार-बार लागू किया गया
  • ASM (inline assembly) का उपयोग कर compiler के अक्षम register spill/reload को रोका गया, और broadcast व masking optimization के साथ अंततः speed को 0.21 सेकंड तक पहुँचाया गया

PoW submission automation और वास्तविक प्रतियोगिता परिदृश्य

  • अंतिम submission में Zen 5 Google Cloud server (Amsterdam region) का उपयोग किया गया, ताकि Google Form तक network latency भी न्यूनतम रहे
  • automated submission program (Google Form POST request patching, internal team collaboration से optimized) के जरिए अब तक के सबसे कम 3.6 सेकंड में सफलतापूर्वक flag submit किया गया
  • आधिकारिक रूप से kernelCTF organizers ने PoW policy हटाने की घोषणा की, जिससे PoW optimization race समाप्त हो गई और इस technique को सार्वजनिक किया जा सका

उन्नत implementation विवरण

modular arithmetic optimization

  • 2^1279-1 (Prime) modulo operation को bit shift और कुछ basic arithmetic operations से बदलकर, standard GMP की तुलना में बहुत तेज़ modular arithmetic हासिल किया गया

AVX512IFMA आधारित big-int squaring

  • AVX512 की 52-bit multiply-accumulate instructions (vpmadd52luq, vpmadd52huq) का उपयोग कर 8-limb blocks की parallel multiplication और accumulation की गई
  • 25-limb structure होने के कारण इसे 4 zmm में बाँटा गया, और बेकार masking/accumulation को न्यूनतम रखने वाला logic तैयार किया गया

data layout और register उपयोग

  • offset-आधारित units, stepped data layout, register-to-register rearrangement (valignq, broadcast) आदि से SIMD bottleneck हटाए गए
  • accumulators को 2 गुना बढ़ाकर multiplication units को idle हुए बिना अधिकतम throughput हासिल किया गया
  • carry propagation भी केवल न्यूनतम आवश्यक स्तर तक ही किया गया

अंतिम submission automation और collaboration

  • देर रात के समय अभियान को साधने के लिए team members की तैनाती, network location और exploit execution optimization किया गया
  • वास्तविक submission में PoW solving, exploit execution, flag insertion, और Google Form POST request तक लगातार automation किया गया

निष्कर्ष और महत्व

  • kernelCTF PoW optimization ऐसा काम था जिसमें bit level से लेकर memory, registers, CNN आदि तक hardware की गहरी संरचनात्मक समझ की आवश्यकता थी
  • PoW policy हटने के बाद अब प्रतियोगिता का केंद्र केवल शुद्ध network/exploit speed रह गया है
  • यह उदाहरण व्यावहारिक hacking और high-performance computing के संगम को दिखाता है, और आगे भी algorithm optimization की जानकारी तथा open-source code शोध समुदाय के लिए उपयोगी रहेंगे

संदर्भ और परिशिष्ट

  • PoW algorithm का पूरा code, conversion functions (GMP <-> 52-bit array), SIMD आधारित modular arithmetic, और ASM tuning code सभी सार्वजनिक किए गए हैं
  • लगभग 12 घंटों में गहन रूप से विकसित कर वास्तविक उपयोग में लाया गया यह “rough” code, GNU AGPL 3.0 license के तहत open किया गया है
  • सवाल या VDF-संबंधित collaboration के लिए Discord(@forevermilk) पर संपर्क किया जा सकता है

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

1 टिप्पणियां

 
GN⁺ 2025-05-31
Hacker News राय

  • 3.6 सेकंड में जीतने वाली टीम और दूसरे स्थान पर आई टीम ने 3.73 सेकंड या 3.74 सेकंड का रिकॉर्ड दिखाया, इसलिए लगा कि दूसरे स्थान वाली टीम ने भी PoW optimization किया होगा या FPGA का इस्तेमाल किया होगा; पहले के 4 सेकंड से अधिक वाले FPGA submissions से तुलना करें तो अच्छा होता अगर लेखक यह भी बताते कि इस हफ्ते का दूसरा स्थान वाला रिकॉर्ड भी अब तक के सबसे बेहतरीन रिकॉर्ड्स में से एक हो सकता है

  • यह तरीका AVX-512 optimized RSA implementation में इस्तेमाल होने वाले तरीके से काफ़ी मिलता-जुलता लगा, क्योंकि RSA में भी बहुत बड़े exponentiation operations की ज़रूरत होती है; paper(https://dpitt.me/files/sime.pdf) में windowing technique और window size को मनचाहे ढंग से adjust करने की बात है, और AVX-512 RSA implementation में multiplication results को [0..2^{window-size}) रेंज की table में store करके हर window पर result इस्तेमाल किया जाता है; इसका वास्तविक उदाहरण aws-lc code के rsaz-2k-avx512.pl में देखा जा सकता है

    • अफ़सोस रहा कि यह बातें पहले देखी होतीं तो development में काम आतीं; Zen 5 पर zmm registers के इस्तेमाल से 2x multiplication throughput की उम्मीद है, जबकि मौजूदा code में mask registers को GPR में बदला जाता है जो Zen 4/5 पर अप्रभावी है; यह भी सवाल है कि क्या carry propagation सचमुच एक ही बार में करना ज़रूरी है; वास्तव में code में यह मानकर loop चलता है कि carry केवल एक बार होगा, जो ज़्यादातर स्थितियों में latency कम करने में मदद करता है, हालाँकि branch के कारण timing attack की संभावना बनी रहती है

  • कई पीढ़ियों तक consumer CPU में AVX512 support होने के दावे पर, याद है कि Rocket Lake (11वीं पीढ़ी) से पहले AVX512 सिर्फ enthusiast, Xeon और कुछ mobile processors में ही उपलब्ध था; 12वीं पीढ़ी और P/E cores आने के बाद यह कुछ ही महीनों में disable होकर गायब हो गया; अनुमान है कि अगर AMD को AVX512 में सफलता मिलती है तो Intel इसे फिर से लाएगा; मैं खुद i9-11900 इस्तेमाल कर रहा हूँ

    • 12वीं पीढ़ी के P-core CPU में AVX512 का न तो समर्थन था न ही उसका प्रचार, और यह default रूप से disabled था; E-core की जगह की वजह से पूरे CPU में AVX512 मौजूद ही नहीं था, बस BIOS option वाले workaround से E-cores disable करके बाकी cores पर AVX512 enable किया जा सकता था, लेकिन इसके लिए E-cores छोड़ने पड़ते थे
    • हाल की Intel AVX10 technical whitepaper(https://cdrdv2.intel.com/v1/dl/getContent/784343) में P-core और E-core दोनों पर 512-bit AVX को standard के रूप में पेश किया गया है, जो 256-bit तक सीमित configuration से आगे बढ़ते हुए संकेत देता है कि AVX-512 सिर्फ server तक सीमित नहीं रहेगा बल्कि आगे consumer CPU में भी गंभीर वापसी कर सकता है; इसे AMD के AVX-512 विस्तार के जवाब में Intel के पीछे-पीछे आने के रूप में देखा जा रहा है

  • CTF प्रतियोगिता की प्रकृति पर सवाल है; submission speed competition की बजाय ऐसा मॉडल बेहतर हो सकता है जिसमें तय submission window के भीतर flag submit करने वाली सभी teams इनाम साझा करें

    • लेकिन ऐसी व्यवस्था यह meta-game पैदा कर सकती है कि प्रतिभागी exploit जानकारी तुरंत सार्वजनिक न करें और अगले rounds की कोशिश के लिए रोककर रखें, जिससे immediate reporting प्रभावित हो; साथ ही submission timing strategy जैसी गैर-रचनात्मक प्रतिस्पर्धा के दुष्प्रभाव का भी डर है
    • यह भी कहा गया कि meta-game structure बदल जाएगा, और शायद भागीदारी की इच्छा और घटे, जिससे kernelCTF submission पर विचार करने वाले लोग और कम हो सकते हैं

  • अगर मैं सही समझा हूँ, तो यहाँ 4 सेकंड का proof of work और महीने में एक बार payout structure है; क्या सचमुच हर महीने इतने exploits आते हैं कि इतनी कड़ी प्रतिस्पर्धा होती है?

    • server हर 2 हफ़्ते में खुलता था, और PoW का मकसद बहुत ज़्यादा connection requests को रोकने के लिए थोड़ा delay देना था; public CTF अक्सर इतने प्रतिस्पर्धी होते हैं कि कभी-कभी DDoS जैसी कार्रवाइयाँ भी कोशिश की जाती हैं; बाद में Google ने proof of work चरण हटा दिया
    • यह दावा भी किया गया कि Linux kernel security के बारे में जो मिथक है, वह वास्तव में सिर्फ भ्रम है
    • यह CTF remote code execution नहीं बल्कि privilege escalation exploit के बारे में था, यानी सामान्य user से root तक अधिकार बढ़ाने वाला exploit; privilege escalation bugs वास्तव में बहुत आम हैं

  • यह एक हैरतअंगेज़ challenge है, लेकिन जीतने के रास्ते में आने वाली बाधाओं की जटिलता और उसकी लगभग हास्यास्पद प्रकृति ने ध्यान खींचा; इसे Rube Goldberg machine जैसी स्थिति कहना मज़ेदार लगा

  • अगर मुख्य लेख में आए base-52 वाले हिस्से के बारे में और जानना हो, तो आज hot रहे इस post(https://news.ycombinator.com/item?id=44132673) को देखने की सिफ़ारिश की गई

  • गणित शानदार है

  • proof of work में इस्तेमाल हुए sloth नाम के VDF(Verifiable Delay Function) का परिचय दिया गया, जो लंबे क्रमिक computation की माँग करके समय बीतने का प्रमाण देता है, जबकि उसके result को तेज़ी से verify किया जा सकता है; क्योंकि computation serial है, इसलिए कई cores जोड़कर भी runtime कम नहीं किया जा सकता; सवाल उठा कि क्या यह क्षेत्र CPU निर्माताओं के लिए नया बाज़ार बन सकता है; sloth iterations और results के लिए dedicated instructions तथा HW-आधारित overclocking prevention feature जोड़ने का सुझाव दिया गया; CPU uptime को monitor करके challenge के साथ sign करने का विचार भी रखा गया, जो CPU को productive उपयोग में रखते हुए भी n सेकंड तक CPU ownership साबित करने वाले proof of stake जैसा लगता है

  • blog में दी गई Python function Google के PoW implementation के बराबर कैसे है, यह समझना मुश्किल लगा

    • Google code में exponent = (p + 1) // 4 वास्तव में 2^1277 है; किसी संख्या को इतने बड़े exponent तक उठाने के लिए 1277 बार squaring करनी पड़ती है, और Python function वास्तव में यही करती है; अगर शुरुआती मान x हो तो हर squaring के साथ घात 2 गुना होती जाती है और अंत में 2^1277 तक पहुँचती है; इसी सिद्धांत की व्याख्या की गई