Araştırmacılar çarpanlara ayırmadan RSA imza sahteleme saldırısı geliştirdi

Kriptograflar onlarca yıldır RSA'yı kırmanın tek yolunun büyük tam sayıları çarpanlara ayırmak olduğunu varsayıyordu. UC San Diego'dan Nadia Heninger'in liderliğindeki ekip, özel anahtarı çarpanlara ayırmadan geçerli RSA imzaları hesaplayan bir imza sahteleme saldırısı geliştirdi. Çalışma IACR ePrint arşivinde yayımlandı ve henüz hakem değerlendirmesinden geçmedi. Bulgu şu an için pratik bir tehdit oluşturmuyor; yalnızca birkaç özel durumda istisna olabilir.

Saldırı ne yapıyor

Heninger'e göre geçerli RSA imzaları üretmek için önce özel anahtarı çarpanlara ayırma yoluyla elde etmek gerektiği düşünülüyordu. 1024 bitlik RSA için bu çok pahalı ama büyük teknoloji şirketlerinin ya da NSA'nın üstesinden gelebileceği bir işti — tek anahtar için on milyonlarca dolarlık hesaplama süresi; 2048 bitlik için ise "ulaşılmaz" deniyordu.

Saldırı, "ders kitabı" (textbook) RSA'nın tahmini güvenlik seviyesini 1024, 2048 ve 4096 bitlik anahtarlar için 2^65, 2^90 ve 2^119 işleme düşürüyor — bu, NSA, NIST ve AB'nin ENISA kurumunun her kriptosistemden istediği 128 bitlik seviyenin (2^128 işlemden fazlası) kat kat altında. 1024 bitlik tek bir anahtarı çarpanlara ayırmanın yaklaşık 2^80 işlem ve 500 binden 1 milyona kadar CPU çekirdek-yılı gerektirdiği tahmin ediliyordu; yeni teknikle bir imza sahtelemek ise 2^65 işlem ve yalnızca 1.380 çekirdek-yılı sürdü. Ekip tüm kodu elle yazdı; yapay zekâ ve GPU kullanmadı. Heninger, bu araçların güvenlik seviyelerini "neredeyse kesinlikle" daha da düşüreceğini söyledi.

Neden henüz pratik tehdit değil

Saldırı yalnızca "kör imza" (blind-signature) RSA uygulamalarına karşı çalışıyor. Bugün kullanılan RSA'nın ezici çoğunluğu PKCS ya da PSS dolgusundan yararlanıyor; bu dolgu, şifrelemeden önce düz metne veri ekleyip söz konusu zayıflığı ortadan kaldırıyor. Yöntem, kullanımdan kalkmış 1024 bitlik anahtarlara karşı bile ulus-devletler ya da dev kaynaklı şirketler dışında kimsenin karşılayamayacağı kadar hesaplama gerektiriyor.

En bilinen örnek Privacy Pass: kullanıcıların kimliklerini açıklamadan doğrulanmasını sağlayan protokolü Apple ve Cloudflare gibi birçok kuruluş kullanıyor. Ona saldırmak, bu kuruluşlardan birinin sunucusunu ele geçirmeyi ve 2^43 imza üretmeyi gerektirirdi — Heninger'e göre bu sayı "kulağa çok geliyor ama Cloudflare'in bir günde işlediğini açıkladığı ağ trafiğiyle aynı mertebede". Çoğu Privacy Pass uygulaması anahtarları düzenli olarak değiştiriyor; bu, saldırganın şansını büyük ölçüde azaltıyor ama tamamen ortadan kaldırmıyor.

Neden önemli

Allurity'de inovasyon başkanı Karsten Nohl, sonuç hakem değerlendirmesinden geçerse bunun "kavramsal bir atılım" olacağını söyledi. Teknik, 2007'de icat edilen sayı cismi eleği algoritmasının varyantı ve belirli sorgulara evet/hayır yanıtı veren "kâhin" (oracle) zayıflığına karşı çalışıyor. Kriptograflar, pratik kuantum bilişiminin 3 ila 20 yıl içinde geleceği tahminiyle kuantum sonrası alternatifler üzerinde yoğun çalışıyor; yeni saldırı, RSA'dan tamamen uzaklaşmanın aciliyetini artırıyor.