filippo.io/mlkem768: Go ekosistemi için kuantum dirençli kriptografi

 (words.filippo.io)
1 puan yazan GN⁺ 2024-02-02 | 1 yorum | WhatsApp'ta paylaş
  • filippo.io/mlkem768, NIST standardizasyon süreci devam eden ML-KEM-768'in saf Go ile yazılmış bir uygulamasını sunarak Go ekosisteminde kuantum dirençli anahtar değişimini değerlendirmeyi mümkün kılıyor
  • Yaklaşık 500 satır kod, 200 satır yorum ve 650 satır testten oluşuyor; golang.org/x/crypto/sha3 dışında bağımlılığı olmadığı için Go standart kütüphanesindeki dahili pakete alınması kolay bir yapıya sahip
  • pq-crystals referans uygulamasını port etmek yerine FIPS 203 belirtimini doğrudan izleyerek yazıldı; böylece yalnızca belirtime dayanarak birlikte çalışabilir bir uygulama geliştirmenin mümkün olup olmadığını doğruluyor
  • En zorlayıcı alanlar sıkıştırma-açma ve sabit zamanlı işlemler; Barrett reduction kullanarak referans uygulama ailesinde ortaya çıkabilen değişken zamanlı DIV komutu riskinden kaçınıyor
  • Performans birincil hedef olmasa da Bob yolu Go'nun X25519 ve P-256'sıyla benzer, Alice yolu da 2 katın altında kalarak basit bir uygulamayla bile pratik hızlar gösteriyor

ML-KEM-768'in saf Go uygulaması

  • filippo.io/mlkem768, ML-KEM-768'in saf Go ile yazılmış bir uygulaması ve önceliği doğruluk ile okunabilirlik
  • ML-KEM, daha önce Kyber olarak biliniyordu ve NIST standardizasyon sürecindeki kuantum dirençli anahtar değişim mekanizması
  • Paket, yaklaşık 500 satır kod, 200 satır yorum ve 650 satır testten oluşuyor
  • Tek bağımlılığı golang.org/x/crypto/sha3
  • Hedef, bunu Go standart kütüphanesine upstream etmek; ilk aşamada opt-in crypto/tls denemelerinde kullanılan yalnızca dahili bir paket olarak planlanıyor

FIPS 203'ü birebir izleyen uygulama yaklaşımı

  • Bu uygulama, pq-crystals referans kütüphanesini port etmiyor; başka kod tabanlarını ayrıntılı okumadan sıfırdan yazıldı
  • Temel amaç, yalnızca belirtimden yola çıkarak birlikte çalışabilir bir uygulama üretmenin mümkün olup olmadığını görmekti
  • FIPS 203 belgesi, ayrıntılı sözde kod, eksiksiz tanımlar ve tutarlı tür bilgileri sunduğu için iyi bir uygulama rehberi oldu
  • İşlev adları, değişken adları ve işlem sırası; inceleme ve öğrenmeyi kolaylaştırmak için mümkün olduğunca FIPS belirtimini yansıtıyor
  • ML-KEM uygulamak için gereken matematiksel arka plan ayrıca Enough Polynomials and Linear Algebra to Implement Kyber içinde derlenmiş

Sıkıştırma-açma ve sabit zamanlı uygulama

  • Geriye üç temel uygulama görevi kalmıştı
    • asal sayı 3329 için modüler aritmetik uygulamak
    • [0, 3329) değerlerini [0, 2ᵈ) aralığına eşleyip geri döndüren sıkıştırma-açma işlevlerini uygulamak
    • sabit zamanlı işlemleri garanti etmek
  • Modüler aritmetik, RSA ve eliptik eğri uygulamalarından gelen birikim sayesinde nispeten kolaydı; küçük asal sayı da uygulamayı basitleştirdi
  • Sıkıştırma ve açma en zor kısımdı
    • Belirtim bunu kesirler ve yuvarlama kurallarıyla soyut şekilde tanımlıyor
    • Gerçek uygulamada ise sabit zamanlı aritmetik ve bit işlemleriyle ele alınması gerekiyor
  • Referans uygulama ve onun birçok portu, derleyici optimizasyonuna ve platforma bağlı olarak değişken zamanlı DIV komutuna dönüşebilen bölme işlemleri kullanıyordu
  • Bu paket baştan itibaren Barrett reduction kullandığı için etkilenmedi; BoringSSL de aynı yaklaşımı kullanıyor

Neden yalnızca ML-KEM-768 hedeflendi

  • Uygulama, ML-KEM'in üç güvenlik seviyesi -512, -768, -1024 arasından yalnızca ML-KEM-768'i hedefliyor
  • Kyber ekibi, yeni kriptoanalizlere karşı daha muhafazakâr bir güvenlik payı için -512 yerine -768 kullanımını öneriyor
  • -1024, 256 bit güvenlik seviyesiyle aynı gerekçelerle; yani mevzuat uyumu ve güç eşleştirme için bir seçenek olarak açıklanıyor
  • Deneysel veya standardizasyon sürecindeki protokollerin çoğu ML-KEM-768 etrafında toplandığı için tek seviyeye odaklanmanın maliyeti neredeyse artmıyor
  • Tek seviyeye odaklanmak, hareketli parçaları azaltarak okunabilirlik, güvenlik ve performans açısından fayda sağlıyor
    • Örneğin 1, 4, 10 ve 12 bit tamsayı serileştirmeleri tek bir genel kodlayıcıyla ele alınmak yerine ayrı kodlayıcılar ve kod çözücülerle işleniyor
    • Yalnızca ML-KEM-768 hedeflendiği için 5 bit ve 11 bit kodlamaları uygulamak gerekmiyor

Test stratejisi ve açık test vektörleri

  • Testler, bu paketin güvenlik güvencesi stratejisinde okunabilirlikten sonra gelen en önemli unsur
  • Temel testler; anahtar üretimi, encapsulation, decapsulation roundtrip'leri ve %95'in üzerinde test kapsamı içeriyor
  • Ek test kapsamı şunları içeriyor
    • NIST ve diğer uygulamalardan alınan test vektörleriyle birlikte çalışabilirliği doğrulama
    • 3329 modüler toplama, çıkarma ve çarpmanın tüm girdi kombinasyonlarını değişken zamanlı yöntemle hesaplanan beklenen değerlerle karşılaştırma
    • Sıkıştırma-açmayı math/big.Rat referansına göre kapsamlı biçimde test etme
    • Önceden hesaplanmış sabitlerin tanımlarla eşleştiğini doğrulama
    • Tüm işlev girdilerinde uzunluk fazla kısa ya da fazla uzun olduğunda uygun hataların üretildiğini kontrol etme
    • Sophie Schmieg tarafından sağlanan ve gelecekte Wycheproof'a eklenecek test vektörlerini çalıştırma
  • Kendi test vektörleri, başka uygulamalarda da yeniden kullanılabilsin diye CCTV projesinin bir parçası olarak yayımlanıyor
  • CCTV vektörleri, her ara adımı ve alt algoritmayı test edip hata ayıklamaya yarayan ara değerleri içeriyor

Özel test vektörlerinin yakaladığı hatalar

  • Negative test vectors, katsayıları 3329'dan büyük olan hatalı encapsulation anahtarları veriyor
    • Kyber ve NIST ekibinin vektörleri normal girdilere odaklandığı için bu tür vektörler sık talep ediliyor
    • 3329'dan 2¹²-1'e kadar tüm değerler ve tüm katsayı konumları tek tek test ediliyor
    • Kalan katsayıları paylaşarak 1–3MiB veriyi 12–28KiB'ye sıkıştırıyor
  • “Unlucky” vectors, XOF'tan anormal derecede fazla okuma gerektiren durumları test ediyor
    • SampleNTT içinde SHAKE-128 XOF'tan 575 bayttan fazla okunması gereken bir açık anahtarı ifade ediyor; bu normalde 2⁻³⁸ olasılıkla görülüyor
    • Sophie'nin vektörleri daha da brute-force edilerek en fazla 591 bayt gerektiriyor
  • strcmp vectors, ML-KEM.Decaps içinde strcmp() kullanan uygulamaları başarısızlığa uğratıyor
    • Decapsulation sırasında ciphertext ile K-PKE.Encrypt çıktısı karşılaştırılırken 0 baytı varsa strcmp() karşılaştırmayı erken sonlandırabiliyor
  • Accumulated vectors, referans pq-crystals uygulamasından türetilmiş
    • 300MB'lık rastgele vektör çıktısını saklamak yerine, test sırasında deterministik RNG ile yeniden üretip hash'i beklenen değerle karşılaştırıyor
    • Referans uygulamadaki 10 bin örneğin ötesine geçip 1 milyon rastgele test için de hash üretilebiliyor
  • Tamamlandıktan sonra eklenen birçok testte de filippo.io/mlkem768 ile ilgili sorun bulunmadı; negative vector'ların önemli uygulamalardaki kusurları yakaladığına dair raporlanmış en az bir örnek var

Performans sonuçları

  • Performans, bu paket ya da Go kriptografi paketleri için birincil hedef değil; ancak kullanışlı olacak kadar hızlı olması gerekiyor
  • ML-KEM yeterince hızlı ve bu basit uygulama bile Go'nun assembly ile optimize edilmiş P-256 ve X25519 uygulamalarıyla rekabet edebilecek düzeyde
  • Karşılaştırma, anahtar kurulumu sırasında her tarafın yapması gereken toplam iş yükü üzerinden yapılmalı
    • ECDH, sabit bir basepoint ile biri dahil olmak üzere 2 skaler çarpma gerçekleştiriyor
    • KEM'de bir taraf anahtar üretimi ve decapsulation, diğer taraf encapsulation yapıyor
    • ECDH simetrik, ML-KEM anahtar kurulumu ise asimetrik
  • Benchmark'larda “Alice” anahtar üretimi ve decapsulation yaparken, “Bob” encapsulation yapıyor
    • Decapsulation, girdi ciphertext'inin sonuçla eşleşip eşleşmediğini doğrulamak için tam bir şifrelemeyi de içeriyor
    • Alice; şifreleme, şifre çözme ve anahtar üretimi yaptığı için Bob'dan daha uzun sürüyor
  • Sonuç olarak Bob, X25519 veya P-256 kadar hızlı; Alice ise bunun 2 katından daha az sürede tamamlıyor
  • BoringSSL ve libcrux gibi hızlı ML-KEM uygulamalarıyla karşılaştırıldığında bu paket yaklaşık 2 kat daha uzun sürüyor

Benchmark sayıları ve optimizasyon alanı

  • Ölçülen sayılar şöyle
    • macOS arm64 üzerinde ECDH/P256-8 49.43µs, ECDH/X25519-8 77.46µs
    • Aynı ortamda RoundTrip/Alice-8 109.4µs, RoundTrip/Bob-8 56.19µs
    • Linux amd64 üzerinde ECDH/P256-4 78.88µs, ECDH/X25519-4 115.6µs
    • Aynı ortamda RoundTrip/Alice-4 223.8µs, RoundTrip/Bob-4 114.7µs
  • Uygulama, heap allocation'ı azaltmak gibi yüksek performanslı Go kalıplarını izliyor
  • x/crypto/sha3'ü heap allocation olmadan kullanılabilir hale getirmek için yeniden düzenlendi, ancak Apple M2'de olumsuz etki görüldüğü için henüz birleştirilmedi ve yukarıdaki benchmark'lara da dahil edilmedi
  • Kalan optimizasyon alanları açık
    • Anahtar üretimi ve decapsulation aynı değerlerden matris örneklediği için, Alice tarafında bu iki işlem art arda yapıldığında matris saklanırsa yaklaşık %10 zaman tasarrufu sağlanabilir
    • sha3 okuma yolunda kopyalamayı azaltma ihtimali var
    • Sonrasında alan uygulamasının optimize edilmesi gerekecek

ML-KEM uygulamasıyla Kyber v3 desteği

  • NIST, Kyber Round 3 başvurusunda birkaç küçük değişiklik yaptı; bunlar FIPS taslağının 1.3 bölümünde özetleniyor
  • Kyber v3 ya da “draft00” temelinde birkaç deneysel protokol var ve buna büyük dağıtımlardaki PQ TLS anahtar değişimi de dahil
  • Ayrı bir paket olmadan, ML-KEM uygulamasıyla Kyber v3 desteklenebilir
  • Değişikliklerden biri, açık anahtardaki normalleştirilmemiş katsayı kodlaması gibi istisna durumlarına doğrulama ekliyor
    • Normal bir uygulama böyle anahtarlar üretmeyeceği için FIPS taslağı uyarınca bunlar reddedilebilir
    • Bu davranış, Kyber-on-ML-KEM uygulamasını ayırt edilebilir hale getiriyor ama bunun dışında zararlı değil
  • Diğer bir değişiklik, CSPRNG girdisine uygulanan hashing adımının kaldırılması
    • Girdi baytları rastgele olduğu için hiçbir taraf farkı ayırt edemez
  • En büyük değişiklik, ciphertext'in paylaşılan sırra hash edilmesi davranışı
    • Bu fark birlikte çalışabilirliği engelleyebilir
    • ML-KEM ile paylaşılan sır K üretildikten sonra SHAKE-256(K || SHA3-256(c))[:32] uygulanırsa Kyber paylaşılan sırrı elde edilebilir
    • ML-KEM soyutlamasını bozmak gerekmez
  • Hem Kyber hem de ML-KEM, decapsulation sırasında implicit rejection için sır ve ciphertext'i hash'liyor
    • ML-KEM üzerine yukarıdaki anahtar türetme uygulanırsa implicit rejection sırasında ciphertext iki kez hash'lenmiş olur
    • implicit rejection çıktısı tasarım gereği öngörülemez ve birlikte çalışabilirlik hedefi değildir; bu yüzden sorun oluşturmaz

İlgili okumalar

1 yorum

 
GN⁺ 2024-02-02
Hacker News yorumları

  • Kudelski Security’den selamlar. Go için kuantuma dayanıklı kriptografi kütüphaneleri arasında neredeyse tek alternatif olan diğerini kısa süre önce durdurmak zorunda kaldığımız için çok yerinde bir zamanlama
    Hikâyenin tamamı burada: https://research.kudelskisecurity.com/2024/02/01/the-kybersl...

    • Kyber-512, NIST’in NSA tarafındaki üyeleri tarafından kasıtlı olarak zayıflatılmamış mıydı?

  • Böyle bir şeye ihtiyaç duyulacak kadar kuantum bilişimin gerçekte hangi seviyeye geldiğini merak ediyorum
    AI’da olduğu gibi gerçekten bir şeyler ortaya çıkmasından ziyade, mevcut bir ad altında yeni ürünler çıkarabilmek için tanımın değiştirildiği bir durum mu oldu?

    • Kriptografinin kuantum bilgisayar tehdidini ele alma biçimi ilginç. Çünkü bugün şifrelenen verilerin ve bağlantıların bir kısmının 30, 50 yıl sonra çözülebilir hâle gelmemesi gerekiyor
      Bu yüzden soru “kuantum bilgisayarlar yakında mı geliyor” değil, “önümüzdeki yarım yüzyıl içinde kuantum bilgisayarların makul biçimde ortaya çıkması mümkün mü” oluyor. Kesin bir uzlaşı yok ama yanıt “hayır” değil; bu yüzden bugün böyle bir yönelim oluşuyor
      Bu nedenle imzalardan çok PQC anahtar değişimi tarafında daha fazla ilerleme görüyoruz. Bugünkü imza doğrulaması 50 yıl sonraki kuantum bilgisayarlardan etkilenmez, ama şifreleme etkilenir
    • Mesele bugünkü kuantum bilgisayarları engellemek değil
      Risk, saldırganın bugünün şifreli metinlerini saklayıp gelecekte çözebilmesi. Kuantuma karşı güvenli kriptografiye ne kadar hızlı geçersek, gelecekteki saldırılara açık “birikmiş şifreli metinleri” o kadar az bırakırız
    • Eğer yanıt “NSA zaten üretimde kuantum kriptoanalizi çalıştırıyor ve ECDH’nin tamamen kırılmış sayılması gerekiyor” ise, bunu bilen kişinin söylemesi onu büyük bir sıkıntıya sokar
      Gerçekte bunun olasılığı düşük görünüyor, ama bu soruya bir ölçüde yanıt vermek zor. Şimdilik bilinen bir tehdit değil; fakat potansiyeli konusunda ne kadar paranoyak olunacağı öznel
    • Son 2 yıl civarında NIST birkaç post-kuantum kriptografi algoritması belirledi ve sonrasında uygulamalar da giderek artıyor. Kuantum bilişim hâlâ uzak ama yaklaşım “şimdiden başlamanın ne zararı var?” gibi görünüyor
      Emin değilim, ama eliptik eğri kriptografisinin de yaygın kullanılmasından çok önce epey uygulaması yapılmış olmalı. O dönemleri yaşamış biri yanılıyorsam düzeltsin
    • Bir kuantum bilgisayarın RSA-2048’i kırabilmesi için mevcut fiziksel kübitlerin kalitesinin kabaca 10 kat, sayısının ise 10 bin kat artması gerekiyor. Bunlar çok kaba rakamlar
      İzlenecek bir sonraki önemli kilometre taşı, onu oluşturan fiziksel kübitlerden 1000 kat daha yüksek doğruluğa sahip mantıksal kübit olacak. Bu ortaya çıkarsa, fiziksel kübit kalitesinin yeterli olduğu ve artık yalnızca sayıyı ölçeklemeye başlamak gerektiği anlamına gelir

  • İlgili tartışma için John Arundel’in en yeni Go sürümünü temel alan kripto sistemleri uygulama giriş kitabı yararlı olabilir. Son bölümde post-kuantum kriptografiye kısaca değiniliyor; NIST PQ standartlaştırıldığında John ileride bu kütüphaneyi ekleyerek kitabı güncelleyebilir
    Explore Go: Cryptography (Go 1.22 edition):
    https://bitfieldconsulting.com/books/crypto

  • Yanılıyorsam düzeltin ama saf Go ile yazıldıysa zamanlama/güç yan kanal saldırılarına açık hâle gelmez mi?

    • Go’nun C’den daha açık olduğunu söylemek zor; hatta daha az bile olabilir. Fark şu: Go’da başlıca tek bir derleyici var ve genelde aşırı optimizasyon yapmıyor; C’de ise derleyicinin niyeti fark edip kodu daha verimli değişken zamanlı dallara çevirmesini engellemek için giderek daha karmaşık hilelere ihtiyaç duyuluyor
      Bu uygulama, gizli değerlere bağlı olarak değişen kod yollarından kaçınacak şekilde yazılmış. Fiziksel erişim gerektiren güç yan kanalları Go’nun tehdit modelinin dışında
    • “Tüm çekirdek işlemler sabit zamanda gerçekleştirilir” deniyor
      Proje belgelerine kadar linkleri takip etmeliydim; görünüşe göre bu konu dikkate alınmış
    • Güç yan kanal saldırılarına bağışık bir dil var mı? Bu fikrin kendisi anlamsız görünüyor
      Zamanlama saldırıları konusunda da Go’nun zamanlama yan kanallarına diğer dillerden neden daha açık olacağını bilmiyorum

  • Java, C# gibi diğer diller için uygulama bilen var mı?

  • draft00/kyber v3 ile de çalışabilmesi güzel
    SHA-3 olmadan hızlı Kyber 90’s modunu desteklemek ne kadar zor olurdu? Muhtemelen bu durumda soyutlamayı kırmak gerekir

    • Hash’i değiştirmek için fork gerekir. Bu uygulama CPU zamanının yalnızca yaklaşık %20’sini SHA-3 için harcıyor, bu yüzden kazanç çok büyük olmaz
      Alan uygulaması optimize edilirse bu oran artar ama standartlaştırılmamış ve daha az test edilmiş bir modu kullanmaya değecek kadar pek muhtemel değil

  • Alakasız ama Filo, 32 bit sistem çağrısı tablosu hâlâ ‘coming soon’ :')

    • Haha, kabul. O sayfayı elden geçirmeyi her düşündüğümde, çekirdek kaynağından CI ile otomatik üretilsin gibi fikirlerle kapsam sürekli büyüyor, ondan :)

  • Bu algoritmanın ya da uygulamanın kalitesini değerlendirecek yetkinliğim yok ama değişken adlarında Unicode kullanılmasını çok beğendim
    ρ, σ := G[:32], G[32:]
    Nedense "rho", "sigma" görmekten çok daha iyi

    • Katılmak zor. Görünüşte havalı ama gerçek kodda pek görmek istemem
      Öncelikle klavyede nasıl yazacağımı bilmiyorum. Ayrıca çoğu kişi bu sembollerin adlarını bile bilmez. Elbette o koda bakan kişilerin bilme olasılığı daha yüksek olabilir ama bunun nazik bir kod olduğunu düşünmüyorum
      Netlik temel mesele ve "rho" ya da "sigma" oldukça net. Üstelik sabit "n" ile sabit "η" de birlikte varsa kafa karıştırmaya çok müsait
    • Hiç hoşuma gitmiyor. Klavyemde olmayan karakterler girişte ek adım gerektiriyor; bu da çok fazla sürtünme yaratıyor. Ayrıca ρ karakterini p diye yanlış okuyup garip bir derleme hatası ile karşılaşacakmışım gibi geliyor
      Harflere aksan işareti ya da çengel eklemeye ne dersiniz? Sadece karmaşıklığı artırır. En düşük ortak paydada kalmak daha iyi
    • Go değişken adlarında Unicode alt indislerine izin veriyor mu?
      Kontrol ettiğim diller arasında Perl, Python ve JavaScript Chrome ile Firefox'ta izin vermedi; PHP ise izin verdi

  • Bunu yapan kişi https://github.com/FiloSottile/age projesini de yapan aynı kişi
    Bu aracı gerçekten seviyorum

    • İçinde makul inkâr edilebilirlik özelliğinin yerleşik olmaması üzücü. Yani en az iki dosyayı şifreleyip, hangi anahtarı verdiğinize bağlı olarak bunlardan birini çözebilmeniz gerekir
      Bu tür araçların çoğunda görülen bir güvenlik zayıflığı gibi duruyor. Olası tek bir anahtar varsa elinde çekiç olan biri o anahtarı söyletmeyi başarabilir. Ama anahtar sayısı bilinmiyorsa birkaçını verip asıl korunan dosyayı gizli tutarak saldırganın gitmesini umabilirsiniz
    • Bu aracı sevmek istiyorum ama tipik kullanımı anlatan kılavuz veya öğretici eksik. Komut satırı kullanımından bahsetmiyorum; anahtarların nasıl yönetilip dağıtılması gerektiğini ve nelere dikkat edilmesi gerektiğini bilmek istiyorum
      Teknolojinin üzerine oturan tüm sosyal katman benim için belirsiz. Alice ve Bob'un yer aldığı örnek bir hikâye iyi olurdu
    • Age fena değil ama durağan kalmış gibi. Son sürüm 2022'de çıkmış ve argon gibi daha modern parola tabanlı anahtar türetme işlevleri kullanmıyor
      Gizli veri saklama/paylaşma için tasarlanmış bir şey arıyorsanız rot'a da bakabilirsiniz: https://github.com/candiddev/rot

  • Spesifikasyon: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.ipd.pdf makalede de bağlantı verilmiş