NSA'nın eliptik eğri tohumları çözüldü: P-256 bir şaka cümlesinden değil, 1997'deki bir saatten çıkmış

Tohum neden önemli?

ECDSA, eliptik eğriler üzerinde çalışan bir dijital imza yöntemi. NIST onu 2000’de FIPS 186-2 ile standartlaştırdı ve kullanılacak eğrileri de listeledi: P-192, P-224, P-256, P-384 ve P-521. Bunlardan P-256 bugün HTTPS sertifikalarında, DNSSEC imzalarında ve sayısız protokolde kullanılıyor.

Her eğrinin tanımında bir tohum (seed) var: 20 baytlık rastgele görünen bir sayı. Standarda göre tohum SHA-1’den geçiriliyor ve eğrinin bir katsayısı bu çıktıdan türetiliyor. Buna “doğrulanabilir rastgelelik” deniyor. Fikir şu: Katsayı bir hash’ten geliyorsa, eğriyi tasarlayan onu gizlice zayıf bir değere ayarlayamaz.

Sorun, tohumların kendisi. Onları NSA vermişti ve nereden geldiklerini hiç açıklamadı. Biri, zayıf olduğunu bildiği bir eğri bulana kadar milyonlarca tohum denediyse, hash bu oyunu engellemez. NSA’nın 2013’te ortaya çıkan Dual_EC_DRBG arka kapısından sonra bu şüphe daha da büyüdü.

25 yıllık bilmece

Koblitz ve Menezes 2015 tarihli makalelerinde tartışmanın tarihini anlattı. Tohumları hazırlayan NSA çalışanı Jerry Solinas, tohumların komik bir cümlenin hash’i olduğunu ama cümleyi hatırlamadığını söylemişti. Solinas 2023’te hayatını kaybetti. Aynı yıl kriptografi uzmanı Filippo Valsorda, tohumların kaynağını bulana bir ödül koydu. Ödül bir hayır kurumuna bağışlanırsa üç katına, 36.864 dolara çıkıyordu. Steve Weis da bilinenleri derleyen bir yazı tuttu. Kimse cümleyi bulamadı.

Claude ne buldu?

Anthropic’in Frontier Red Team ekibinin 16 Ekim’de yayımladığı yazıya göre, bir çalışan Ekim’de şirket içi bir araştırma modeline aynı soruyu sordu. Model, ipucu verilmeden, yarım saatten kısa sürede beş NIST eğrisinin tohumlarının hiçbir hash’ten gelmediğini buldu. Tohumlar, C kütüphanesindeki eski lrand48 rastgele sayı üretecinden çıkmış. Üreteç bir Unix zaman damgasıyla başlatılmış, yani o anki saatle.

Model nasıl buldu? Önce tohumların 1990’ların zayıf bir üretecinden gelmiş olabileceğini düşündü ve farklı üreteç ve bit dilimlerini tarayan bir program yazdı. Bazı tohumlarda her 32 bitlik kelimenin en üst biti sıfırdı. Bunun tesadüf olma ihtimali yaklaşık 5.810’da 1. Bu, 48 bitlik iç durumunun sadece üst 31 bitini veren lrand48’e işaret ediyordu. Diğer tohumlarda çıktının sadece 8 biti kullanıldığı için durum doğrudan görünmüyordu. Model iç durumu LLL kafes indirgemesi (lattice reduction) denen bir matematik tekniğiyle geri hesapladı. Bulunan her durum, tohumun 160 bitinin tamamını yeniden üretti. Bu tesadüfle açıklanamaz.

Somut sonuç: P-256’nın tohumu, 16 Ağustos 1997 01:52:34 UTC saatiyle başlatılan bir çalışmanın ürettiği 1.842. aday. Diğer eğrilerin saatleri Mayıs 1997 ile Nisan 1998 arasına düşüyor. Anthropic yazısında tohumları yeniden üreten Python kodunu da yayımladı.

Arka kapı yok mu yani?

Anthropic bunun bir kırılma, yeni bir saldırı ya da eğrilerde bir zayıflık olmadığını vurguluyor. “Yapılacak bir şey yok” diyor. Tersine, bulgu ekibin eğrilerin arka kapısız seçildiğine dair güvenini artırmış. Tohum bir zaman damgası ve bir aday sırasından ibaretse, zayıf eğri arayacak oyun alanı çok dar.

Yine de her şey çözülmedi. P-256’da 876. aday da uygun bir eğri veriyordu ve neden atlandığı bilinmiyor. Bir ikili eğrinin (B-163) tohumu ve P-256 dahil birkaç eğrinin taban noktası (base point) hâlâ açıklanamıyor. Ödül, Let’s Encrypt’i yürüten Internet Security Research Group’a bağışlanacak.

Senin için ne anlama geliyor?

P-256 kullanıyorsan değiştirmen gereken bir şey yok. Asıl ders iki tane. Birincisi, kriptografide “bu sabiti nereden buldun?” sorusunun cevabı yazılı olmalı. Cevabın unutulması 25 yıllık şüpheye yol açtı. İkincisi, kontrol etmesi kolay, bulması zor işlerde yapay zekâ artık ciddi bir araç: Model bir hipotez kurdu, kendi tarayıcısını yazdı ve sonucu herkesin çalıştırabileceği kodla kanıtladı.

Düşün

• Kodunda kaynağını kimsenin hatırlamadığı bir “sihirli sayı” var mı?
• Bir sabitin rastgele seçildiğini başkalarına nasıl kanıtlardın?

Kendi cümlelerimizle yazılmış bir özettir, çeviri değildir. Tüm kaynaklar yukarıda.