Araştırmacılar anahtarı çarpanlara ayırmadan 1024 bit RSA imzası taklit etti

UC San Diego ve Inria Nancy'deki araştırmacılar, anahtarı çarpanlara ayırmadan 1024 bit RSA imzalarını isteğe göre sahteleyebilen bir saldırıyı uyguladı. "Forging 1024-bit RSA signatures in nearly SNFS time" başlıklı ön baskı 20 Eylül'de IACR ePrint arşivine eklendi; yazarlar Laura Shea, Miro Haller, Adam Suhl, Nadia Heninger ve Emmanuel Thomé.

Çalışma, Joux, Naccache ve Thomé'nin 2007 tarihli, yazarlara göre yeterince değer görmemiş algoritmasını uyguluyor. Süresi özel sayı cisim eleğine (SNFS) yakın, RSA anahtar boyutlarını belirleyen genel sayı cisim eleğinden (GNFS) ise belirgin biçimde kısa.

Saldırı neyi gerektiriyor

Tehdit modeli bir "öğle yemeği" (lunchtime) saldırısı, biçimsel adıyla uyarlanmayan seçili şifreli metin saldırısı (IND-CCA1): saldırgan belirli bir anahtar için ham RSA imzalama oracle'ına geçici olarak erişir, sonra bu erişimi kaybeder. Ardından çevrimdışı olarak istediği imzayı sahteler ve bunu yeni sorgu olmadan her hedef için tekrarlayabilir.

Hesaplama toplamda beş takvim ayı boyunca 1380 CPU çekirdek-yılı ve yaklaşık 2^32 sorgu gerektirdi. Yalnızca modüle bağlı ön hesaplama yaklaşık 1200 çekirdek-yılı alıyor, tek bir sahteleme ise sonrasında yaklaşık 180. Karşılaştırma için makale, 1024 bit RSA modülünü çarpanlara ayırmanın 500.000 ile 1.000.000 CPU çekirdek-yılı sürdüğünü aktarıyor.

HSM'ler ve kör imzalar

Yazarlar sorguları bir donanım güvenlik modülü (HSM) üzerinden yaptı ve kara kutu API erişiminin anahtarı çıkarmadan HSM'yi taklit etmeye yettiğini gösterdi. Neredeyse tüm HSM'lerin uyguladığı PKCS #11 standardı, saldırının istediği ham RSA işlemlerini doğrudan sunuyor. RSA tabanlı kör imza şemaları da aynı oracle'ı sağlıyor; makaleye göre yaygın 2048 bit anahtarlar burada çok düşük bir güvenlik marjı veriyor.

15-30 bit daha düşük güvenlik

Ölçülen sürelerin ekstrapolasyonuyla yazarlar, imza oracle'ı bulunan RSA'nın somut güvenliğinin 1024-4096 bit arası yaygın parametrelerde çarpanlara ayırma temelli tahminlerden 15-30 bit daha düşük olduğu sonucuna varıyor. Genelde 80 bit kabul edilen 1024 bit RSA için saldırı yaklaşık 2^65 sürüyor. 2048 bit (112 bit) için tahmin yaklaşık 2^90 ve 2^43 sorgu; 4096 bit için yaklaşık 2^119 ve 2^57 sorgu. Yani bu modelde 4096 bit RSA bile 128 bit güvenlik düzeyine ulaşmıyor.

RSA varsayımlarındaki boşluk

Yazarlar RSA'nın günlük kullanımda kırıldığını öne sürmüyor: saldırı akademik anlamda pratik, herkesin uygulayabileceği türden değil ve ham oracle modeli oldukça güçlü. Yine de bunun bir boşluğu ortaya koyduğunu savunuyorlar: one-more RSA varsayımı ön hesaplamalı saldırıları kapsamıyor ve bu senaryoya "delayed-target RSA" adını öneriyorlar. NIST, RSA'yı 2030'a kadar kullanımdan kaldırmayı, 2035'te yasaklamayı planlıyor; yazarlar sonucu geçişi hızlandırmak için bir gerekçe daha sayıyor. Kod GitHub'da yayımlandı.