Google’ın kernelCTF PoW’unu AVX512 ile Nasıl Yendik

 (anemato.de)
2 puan yazan GN⁺ 2025-05-31 | 1 yorum | WhatsApp'ta paylaş
  • Crusaders of Rust ekibi, Linux packet scheduler’daki CVE-2025-38001 exploit’ini göndermeye çalışıyordu; ancak kernelCTF’in ilk gelen kazanır yapısı nedeniyle yarışın belirleyici noktası hatanın kendisinden çok PoW süresini kısaltmak oldu
  • Gönderim süreci 12:00 UTC’de bağlanma, yaklaşık 4 saniyelik PoW, yaklaşık 2,5 saniyelik VM açılışı, exploit’in çalıştırılması ve Google Form gönderimi şeklinde ilerliyordu; önceki raunddaki 4,5 saniyelik gönderim rekoru darboğazı ortaya koydu
  • Hedef PoW, “sloth” adlı bir VDF idi; 1280 bitlik bir tamsayı üzerinde 2^1279 - 1 modüler karesini tekrarlayan seri bir hesaplama olduğundan CPU/GPU çekirdeği artırarak kısaltılması zordu
  • GMP/C++ ve Mersenne modüler indirgeme ile süre 1,9 saniyeye, -march=native statik linkleme ile yaklaşık 1,4 saniyeye indirildi; ardından AVX512IFMA’nın 52 bit tamsayı fused multiply-add komutlarıyla Ryzen 9950X üzerinde yaklaşık 0,21 saniyeye düşürüldü
  • 16 Mayıs 2025’te ekip, Zen 5 Google Cloud sunucusu ve optimize edilmiş POST gönderim yolu ile flag’i 3,6 saniyede gönderdi; 28 Mayıs’ta kernelCTF PoW’un kaldırıldığını duyurdu

Yarış koşulu: sorun hatadan çok hızlı gönderimdi

  • Mayıs 2025’te Crusaders of Rust ekibinden William Liu ve Savy Dicanosa, Linux packet scheduler’da use-after-free hatası olan CVE-2025-38001’i keşfedip bir exploit geliştirdi
    • William, yüksek lisans tezi için Linux’u fuzzing yaparken hatayı buldu
    • Savy, exploit çalışma süresini yaklaşık 0,55 saniyeye indirdi
  • Google kernelCTF, iki haftada bir UTC öğleninde gönderim penceresini açıyor; sunucuyu exploit ederek flag’i Google Form’a ilk gönderen ekip ödül alıyordu
  • Gönderim her zaman aynı sırayla ilerliyordu
    • 12:00:00 UTC’de kernelCTF sunucusuna bağlanma
    • proof of work çözümü, yaklaşık 4 saniye
    • instance’ın açılmasını bekleme, yaklaşık 2,5 saniye
    • exploit’i yükleme ve çalıştırma
    • flag’i Google Form’a gönderme
  • Beklenen bounty 51.000 $ idi
    • Temel ödül 21.337 $
    • Çalışma kararlılığı ödülü 10.000 $
    • 0-day hata ödülü 20.000 $

Önceki gönderim rekorunun ortaya çıkardığı PoW darboğazı

  • 2 Mayıs 2025 gönderim penceresinde ilk gönderim öğleden 4,5 saniye sonra geldi
  • Sadece yaklaşık 4 saniyelik PoW ile yaklaşık 2,5 saniyelik VM açılışı bile 6,5 saniye gerektirdiğinden, 4,5 saniyelik rekor basit hesapla uyuşmuyordu
  • kernelCTF sunucu kodunun yuvarlama özelliği nedeniyle VM instance’ı gerçekte 11:59:59’da açılıyordu; bu da zaman çelişkisini ortadan kaldırdı
  • Yine de flag üretim zaman damgası, kazanan ekibin PoW’u 1 saniyenin altında çözdüğünü gösteriyordu
  • Rakip ekip FPGA kullandıysa 1 saniye altı PoW mümkün olmuş olabilir
    • FPGA, belirli işleri çok hızlı yapabilen özel amaçlı donanımdır
    • Genel amaçlı işler için uygun değildir; fiyatı ve programlama zorluğu yüksektir

sloth VDF: iyi paralelleştirilemeyen PoW

  • kernelCTF PoW’u “sloth” adlı doğrulanabilir gecikme fonksiyonu (VDF) idi
  • VDF, uzun seri hesaplamalarla zaman geçtiğini kanıtlayan ve sonuç kanıtı görece hızlı doğrulanabilen kriptografik bir temel bileşendir
  • Hesaplamanın kendisi seri olduğundan daha fazla CPU veya GPU çekirdeği kullanmak çalışma süresini kısaltmayı zorlaştırır
  • Optimize edilen temel döngü şu yapıdaydı
    • difficulty=7337
    • Her difficulty yinelemesinde 1277 kez x = (x * x) % (2 ** 1279 - 1) çalıştırma
    • Ardından x’in en düşük anlamlı bitini tersine çevirme
  • Google’ın referans implementasyonu Python’da gmpy kullanıyordu; gmpy, GMP için Python binding’idir
    • GMP, platforma özgü toplama ve çarpma çekirdeklerini assembly ile uygulayan çok duyarlıklı tamsayı kütüphanesidir

GMP tabanlı ilk optimizasyon

  • İlk optimizasyon, 2^1279 - 1 değerinin bir Mersenne sayısı olmasından yararlanan modüler indirgemeydi
    • 2560 bitlik ara çarpım, alt 1279 bit ve üst bitler olarak bölünüp toplandı
    • Sonuç modülden büyük veya eşitse bir kez çıkarılarak % işlemi değiştirildi
  • Python FFI overhead’ini azaltmak için C++’a taşındı; bu sürüm M1 MacBook Pro’da 1,9 saniyede çalıştı
  • William, libgmp’yi yerelde -march=native ile derleyip statik linkleyerek Intel Ice Lake dizüstünde süreyi yaklaşık 1,4 saniyeye indirdi
  • Rust ile yazılmış benzer optimize solver aynı Mersenne tekniğini kullansa da yaklaşık 2,4 saniye sürdü
  • Daha sonra FLINT de denendi, ancak hızı GMP ile neredeyse aynıydı

AVX512IFMA ile büyük tamsayı karesini yeniden yazmak

  • AVX512, Intel x86 ISA uzantısıdır; vektör register sayısını ve genişliğini artırır, maskeli tahmin ve çeşitli yeni komutlar ekler
    • Intel, Alder Lake’ten itibaren istemci CPU’larda AVX512 desteğini devre dışı bıraktı
    • Sunucu tarafında destek devam etti; AMD ise Zen 4 ve Zen 5’te hem tüketici hem de sunucu CPU’larında AVX512’yi uyguladı
  • Kilit nokta AVX512IFMA idi
    • vpmadd52luq: 52 bitlik çarpımın alt yarısını 64 bitlik akümülatöre ekler
    • vpmadd52huq: 52 bitlik çarpımın üst yarısını 64 bitlik akümülatöre ekler
  • Bu komutlar 52×52→104 bitlik çarpımın alt ve üst bölümlerini hesaplayıp vektör register’larda biriktirir
  • Zen 5, 512 bitlik veri yoluna sahip olduğundan bu komutlardan saat çevrimi başına 2 tane başlatabiliyordu
  • Doğal taban 2^52 idi; 1280 bitlik tamsayı 25 adet 52 bit limb ile temsil edildi
    • Tek bir 512 bit zmm register 8 limb taşıyabilir
    • Değerin tamamı 4 zmm register’a sığar

Çarpma düzeni ve Mersenne indirgeme

  • 1280 bitlik kare alma, 25 adet 52 bit limb’in karesini alıp 50 limb’lik ara sonuç üretme şeklinde uygulandı
  • Karenin simetrisinden yararlanılarak gereken çarpma sayısı neredeyse yarıya indirildi
    • Diyagonal bileşenler ai^2
    • i < j için çapraz terimler 2 * ai * aj
  • Çapraz terim hesaplamasında, shuffle sayısını azaltmak için ardışık 8 limb’lik sliding window tek bir multiplier limb ile çarpıldı
  • AVX512’nin merge masking özelliğiyle nihai toplama dahil edilmeyen çarpmaların akümüle edilmemesi sağlandı
  • Modüler indirgeme, üst 1279 bitin alt 1279 bite eklenmesiyle yapıldı
    • Akümülatör elemanları 2^52 - 1 değerini aşabileceğinden carry propagation toplama sonrasına ertelendi
    • Sonucun 2^1279 - 1 değerinden büyük veya eşit olup olmadığı, 1280’inci bitin 1 olup olmadığına bakılarak belirlendi
    • 2^1279 - 1 değerini çıkarmak, 1280’inci biti temizleyip en düşük limb’e 1 eklemekle eşdeğerdir
  • Son aşamada çok küçük bir overflow olasılığı kalıyordu
    • Son limb tam olarak 2^52 - 1 ise carry propagation gerekiyordu
    • Rastgele PoW için gerçekleşme olasılığı çalıştırma başına yaklaşık 2 milyarda 2 olarak görülüp yok sayıldı

0,45 saniyeden 0,21 saniyeye inen mikro optimizasyonlar

  • İlk AVX512IFMA sürümü, kiralanan Ryzen 9950X üzerinde PoW’u yaklaşık 0,45 saniyede işledi
  • multiply-add komutunun gecikmesi 4 çevrimdi ve saat çevrimi başına 2 tane başlatılabiliyordu; çarpma birimini doyurmak için en az 8 akümülatör gerekiyordu
    • Mevcut sürümde yalnızca 7 akümülatör vardı
    • Alt yarı için 7 ve üst yarı için 7 olmak üzere toplam 14 akümülatör kullanıp sonda birleştirme yöntemine geçildi
    • Bu değişiklik süreyi yaklaşık 0,32 saniyeye indirdi
  • GCC ve clang, döngüyü unroll ederken vbroadcastsd zmm, m64 üretiyor; register allocation sırasında vektör register’lar yetmediği için stack spill ve reload oluşuyordu
    • Inline assembly ile vpmadd52luq/vpmadd52huq komutlarının memory broadcast operand kullanması zorlandı
    • multiplier limb ayrı bir vektör register’a koyulmadan bellekten okunup tüm vektör elemanlarına çoğaltıldı
    • Bu broadcast load, vektör ALU kaynağı kullanmadan load unit üzerinde işlendi
    • Bu aşamada süre yaklaşık 0,23 saniyeye indi
  • Tamsayıyı belleğe hizalı kaydedip hizasız yüklemeyle window oluşturmak store-forwarding stall’a yol açıyordu
    • valignq ile zmm register içinde hizasız yükleme taklit edilerek bellek erişimi azaltıldı
    • Nihai PoW süresi yaklaşık 0,21 saniye oldu

16 Mayıs 2025 gönderim sonucu

  • Ekip, 16 Mayıs 2025 saat 04:30 PST’de nihai gönderime hazırlandı
  • Gecikmeyi azaltmak için Google Form gönderim sunucusuna coğrafi olarak yakın Hollanda’daki Zen 5 Google Cloud sunucusu kullanıldı
  • Gönderimden birkaç dakika önce sahte flag ile Google Form POST isteği yakalanıp kaydedildi
    • Bryce Casaje ve Larry Yuan, Form gönderim programını tasarlayıp optimize etti
    • Max Cai de geliştirme ve gönderime yardımcı oldu
  • Saat 05:00’te sunucu kernelCTF sunucusuna bağlandı, PoW’u çözdü, Savy’nin optimize exploit’ini çalıştırdı ve flag’i POST isteğine ekleyip gönderdi
  • Sonuç 3,6 saniyelik gönderimdi; o sırada kernelCTF tarihindeki en hızlı gönderimdi
  • kernelCTF operatörü aynı gün bounty uygunluğunu doğruladı

PoW’un kaldırılması ve nihai solver’ın yayımlanması

  • 28 Mayıs 2025’te kernelCTF operatörü koczkatamas PoW’un kaldırıldığını duyurdu
  • PoW ortadan kalkınca slot rekabeti exploit çalışma süresi ve ağ gecikmesi eksenine kaydı
  • Bu değişiklik, FPGA veya inline assembly optimizasyon bilgisi olmadan da profesyonel ekiplerle aynı koşullarda yarışmayı mümkün kıldı
  • Nihai solver kodu, 14–15 Mayıs 2025’te yaklaşık 12 saatlik çalışmanın ürünüydü ve GNU AGPL 3.0 ile yayımlandı
  • Build örneği gcc main.c -O3 -march=znver5 -masm=intel -lgmp idi

İlgili okumalar

1 yorum

 
GN⁺ 2025-05-31
Hacker News yorumları

  • Harika bir içerik. Bu yöntem, AVX-512 için optimize edilmiş RSA uygulamasına da çok benziyor; çünkü RSA da çok büyük üs alma işlemleri yapmak zorunda
    Bu makale[1], RSA’nın windowing’i nasıl yaptığını ele alıyor ve pencere boyutunun keyfi olabileceğini gösteren bir formül de içeriyor. AVX-512 RSA uygulaması ayrıca [0..2^{window-size}) aralığındaki çarpım sonuçlarını bir tabloda saklıyor; her pencere için o sonucu tablo[2]dan alıp yalnızca shift/yeniden düzenleme yapıyor

    1. https://dpitt.me/files/sime.pdf (bir dergiden aldığım için kendi alan adımda barındırıyorum)

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

    • İlginç. Geliştirirken bunu görmüş olmalıydım. O kodun örneğin Zen 5 için bir sürümü daha olsa iyi olurdu; zmm register’ları kullanılırsa çarpma throughput’u 2 katına çıkabilecek gibi görünüyor
      Ayrıca maske register’larını aritmetik işlemler nedeniyle genel amaçlı register’lara taşıyor; bu Zen 4/5’te optimum değil. Ayrı olarak, carry’nin gerçekten tek seferde yayılması gerekip gerekmediğini de merak ediyorum. Kendi kodumda carry’nin yalnızca bir kez oluştuğunu varsaydım ve gerekirse döngüye geri dönecek şekilde yaptım; böylece yaygın durumdaki gecikmeyi azalttım. Ancak dallanma olursa zamanlama saldırısı sorunu doğabilir
    • dpitt.me/files/sime.pdf archive.org’a da yüklenebilir: https://archive.org/download/sime_20250531/sime.pdf

  • “Tüketici CPU’larında birkaç nesildir [AVX512] desteklenmesine rağmen” kısmı biraz tuhaf
    Rocket Lake’ten (11. nesil) önce AVX-512 yalnızca üst seviye hobi CPU’larında, Xeon CPU’larda ve bazı mobil işlemcilerde vardı; mobil işlemcilere tüketici CPU’su demek de biraz tartışmalı. 12. nesilde performans/verimlilik çekirdeği yapısı nedeniyle birkaç ay sonra o çekirdeklerde devre dışı bırakıldı ve bir daha görünmedi. Yine de AMD AVX-512 ile bir ölçüde başarılı olursa Intel’in bunu tekrar getirme ihtimalinin yüksek olduğunu düşünüyorum. Bu arada hâlâ Intel i9-11900 kullanıyorum

    • Doğru gidişat bu. Intel’in birkaç ay önce güncellediği AVX10 teknik dokümanı[1] da bunu doğruluyor gibi. 512 bit AVX’in hem P çekirdeklerinde hem de E çekirdeklerinde standart olacağını açıkça söylüyor ve 256 bit’e özel yapılandırmadan uzaklaşıldığını belirtiyor
      Bu, AVX-512’nin yalnızca sunuculara değil, E çekirdekli gelecekteki tüketici CPU’larına da düzgün biçimde geri döneceğine dair güçlü bir işaret gibi görünüyor. Muhtemelen AMD’nin daha geniş AVX-512 benimsemesini yakalamaya çalışıyorlar

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

      1. nesil performans çekirdekli CPU’lar zaten AVX512 desteği gösterilmiyor ve varsayılan olarak etkin de değildi
        Verimlilik çekirdeklerine alan maliyeti nedeniyle AVX512 konmadığı için tüm CPU AVX512 desteklemiyor kabul edildi. Yalnızca bazı BIOS seçeneklerinin tuhaf davranışından yararlanarak verimlilik çekirdeklerini kapatıp kalan CPU’da AVX512’yi açabiliyordunuz; bunun bedeli de E çekirdeklerinden vazgeçmekti

  • Kazanan kayıt 3,6 saniyeydi ama ikinci 3,73 saniyeydi; kazanan kayıtla aynı basamak sayısına yuvarlarsak 3,74 saniye. O halde ikinci olanın da proof-of-work’ü optimize ettiğini ya da FPGA kullandığını mı düşünmek gerekir?
    Yazar, önceki gönderimin pahalı FPGA tabanlı olduğunu söylemesine rağmen 4 saniyenin üzerindeydi demişti. O zaman o haftanın ikincisinin tarihteki en hızlı ikinci gönderim olma ihtimali de vardı; bunun hakkında bir şeylerden bahsetmesini beklerdim

    • Görselde dupe yazıyor. Muhtemelen orijinal yazının ekibi birden fazla hesapla paralel gönderim denedi

  • Etkileyici ama optimizasyon hedefi yanlış gibi görünüyor. CTF, gönderim operasyonu savaşına dönüşmemeli
    Gönderim penceresi içinde flag gönderen tüm takımların ödülü paylaşması herkes için daha iyi olmaz mı?

    • Bu tür bir yapı, exploit’i hemen bildirmek yerine elde tutmaya da yol açar. Bu sefer alamazsa bir sonraki gönderimi hedeflemek için, gönderim zamanlaması oyunu olmasa bile bekletme teşviki doğar
      Bu yüzden pratikte “yanlış” davranışı aktif biçimde teşvik edebilir
    • Bu da başka bir metagame olurdu. Üzerine derin düşünmedim ama sonuçta insanların hevesini kırıp kernelCTF’ye gönderim yapmayı hiç düşünmemelerine yol açması daha olası görünüyor
    • Doğru, ama aslında neredeyse tüm CTF’lerde böyle bir unsur var

  • Doğru anladıysam 4 saniyelik proof-of-work var ve ödül ayda bir kez ödeniyor
    Gerçekten her ay insanların rekabet edeceği kadar çok exploit var mı?

    • Sunucu iki haftada bir açılıyordu. Proof-of-work, mümkün olduğunca çok bağlantı isteği spam’leme teşvikini azaltmak için bağlantıyı biraz yavaşlatan bir mekanizmaydı
      Herkese açık CTF zor. Sonunda bazı ekipler bitiş çizgisine koşarken DDoS’a benzer davranışlar sergiliyor. Sonrasında Google proof-of-work adımını kaldırdı
    • Bu uzaktan kod çalıştırma değil, yerel yetki yükseltme exploit’i; yani normal kullanıcıdan root’a geçme türünden. Yetki yükseltme bug’ları çok yaygın
    • Linux kernel güvenliği miti, kelimenin tam anlamıyla yalnızca bir mit

  • Harika bir içerik ama bu challenge’ı kazanmak için aşılması gereken engellere bakınca komedi gibi okunuyor. Tam bir Rube Goldberg makinesi gibi

  • Bu yazıda bahsedilen 52 tabanlı gösterim hakkında daha fazlasını öğrenmek istiyorsanız bugün ana sayfadaki başka bir yazıya da bakmaya değer: https://news.ycombinator.com/item?id=44132673

  • Küçük bir düzeltme: statik linkleme inlining sağlamaz, yalnızca PLT overhead’ini kaldırır. Inlining fırsatlarını artıran şey LTO’dur

  • Neden yarıştırdıklarını anlamıyorum. Her benzersiz exploit için doğrudan ödül verilemez mi?

    • Çünkü böyle harika bir programı yürütürken yöneticiler katı biçimde sabitlenmiş bir bütçe istiyor. Bu tür programların gerekçesi, en azından kısmen, bug satın almaktan ziyade exploit ve mitigasyon tekniklerindeki eğilimleri ölçmek
      Ayrıca Linux o kadar çok bug içeriyor ki tüm 0-day’lere para vermeye başlarsanız iş kontrolden çıkar. Google da bir dönem insanların biriktirdiği bug’ları boşaltmak için rekabetsiz, sınırlı süreli bir promosyon yapmıştı; tüm 0-day’ler kabul edilince gönderimler patladı. Aynı zamanda topluluğu kızdırmak istemedikleri için yapı böyle oldu

  • Aradan bunca yıl geçmişken uzmanların 3 saniyede bir Linux makinesini ele geçirebilmesi biraz moral bozucu