DES Nasıl Kırıldı

DES'in 2^56 olası anahtarı vardır; bu sayı yaklaşık 72 katrilyon (72.057.594.037.927.936) anahtara eşittir. Bu sayı çok büyük görünse de sonlu bir uzaydır ve yeterli hesaplama gücüyle sistematik olarak taranabilir.

Anahtar uzayının tüketilmesi (kaba kuvvet), doğru anahtarı bulmadan önce ortalama olarak anahtar uzayının yarısının denenmesini gerektirir. DES için bu, her biri modern donanımda birkaç işlem gerektiren yaklaşık 2^55 deneme amaçlı şifre çözme işlemine karşılık gelir.

1997'de RSA Data Security, DES ile şifrelenmiş bir iletiyi kırana 10.000 ABD doları ödül teklif etti. Rocke Verser, internet'e bağlı on binlerce bilgisayarı kapsayan bir dağıtık hesaplama çalışmasını koordine etti.

96 günlük aramanın ardından anahtar bulundu. Açık metin "Güçlü kriptografi dünyayı daha güvenli bir yer hâline getirir." ifadesiydi. Bu çalışma, DES'in kırılabileceğini gösterdi; ancak bunun için aylar ve büyük ölçekli bir koordinasyon gerekti.

Elektronik Sınır Vakfı, 1998'de 250.000 ABD doları karşılığında Deep Crack'i geliştirdi. Sistem, her biri saniyede 2,5 milyon DES anahtarını deneyebilen 1.856 özel ASIC içeriyordu; bu da Deep Crack'e saniyede 90 milyardan fazla anahtarlık birleşik bir hız sağlıyordu.

Deep Crack, DES'in tüm anahtar uzayını ortalama yaklaşık 9 günde tüketebiliyordu. Bu, 250.000 ABD doları yatırım yapan kararlı bir saldırganın DES'i iki haftadan kısa sürede kırabileceğinin kanıtıydı.

DES Sınamaları II-1'de (Şubat 1998), Deep Crack ile distributed.net gönüllü hesaplama ağı birleşerek DES'i yalnızca 39 günde kırdı. Sınama II-2 (Temmuz 1998) ise 56 saatte sonuçlandı.

Yalnızca bir yıl içinde 96 günden 56 saate gerçekleşen hızlı ilerleme, donanım geliştirmelerinin ve daha iyi koordinasyonun kaba kuvvet saldırılarını ne kadar hızlı biçimde hızlandırabileceğini gösterdi.

Ocak 1999'da EFF'nin Deep Crack'i ile distributed.net birleşerek DES Sınaması III'ü yalnızca 22 saat 15 dakikada kırdı ve RSA Security tarafından verilen 10.000 ABD doları ödülü kazandı.

DES'in 24 saatten kısa sürede kırılabileceğine ilişkin bu kesin gösterim, DES'in güvenli olduğu yönündeki tüm savları fiilen sona erdirdi. Kısa süre sonra NIST, DES'in yerine geçecek algoritmayı seçme sürecini başlattı ve bu süreç AES ile sonuçlandı.

Distributed.net, sıradan internet kullanıcılarının CPU çevrimlerini DES sınamalarına bağışladığı gönüllü hesaplama çalışmalarını organize etti. En yoğun dönemde yüz binlerce bilgisayar katıldı.

Her bilgisayar, merkezi bir sunucu tarafından koordine edilen anahtar uzayının farklı bir bölümünü denedi. Bu çalışma, günümüzde eski şifreleri kırma gibi sınamalarda hâlâ kullanılan kriptanaliz amaçlı dağıtık hesaplama modelinin öncülüğünü yaptı.

Anahtar uzayının tüketilmesi mümkündür; çünkü her DES şifre çözme işlemi hızlıdır (donanımda mikrosaniyeler sürer) ve işlemler birbirinden bağımsızdır. N anahtarını denemek ile N+1 anahtarını denemek arasında hiçbir bağımlılık yoktur; bu nedenle arama, istenen sayıda makine arasında mükemmel biçimde paralelleştirilebilir.

Bu utanç verici derecede paralel yapı, donanımı iki katına çıkarmanın süreyi tam olarak yarıya indirmesi anlamına gelir. Daha fazla makine eklemek doğrusal bir hızlanma sağlar ve bu da saldırganlar açısından maliyet-fayda hesabını elverişli hâle getirir.

Eli Biham ve Adi Shamir, şifre turlarında giriş çiftleri arasındaki farkların nasıl yayıldığından yararlanan bir teknik olan diferansiyel kriptanalizi 1990'da yayımladı. DES için bu yöntem teorik olarak 2^47 seçilmiş açık metin gerektirir.

DES'in S kutularının, diferansiyel kriptanalize karşı direnç gözetilerek tasarlandığı sonradan ortaya çıkarıldı; bu da NSA'nın bu tekniği 1970'lerde bildiğini düşündürmektedir. Saldırı teorik açıdan etkileyicidir; ancak pratikte donanım tabanlı kaba kuvvet karşısında geride kalır.

Mitsuru Matsui, DES'e saldırmak için 2^43 bilinen açık metin gerektiren doğrusal kriptanalizi 1993'te yayımladı. Saldırıyı uyguladı ve 1994'te DES'i deneysel olarak kırarak teorik analizi doğruladı.

Doğrusal kriptanaliz, S kutusunun davranışına ilişkin doğrusal yaklaşımlar bulur ve istatistiksel bir sapmadan yararlanarak anahtar bitlerini kurtarır. Teoride kaba kuvvetten çok daha az veri gerektirir; ancak donanım saldırılarından önce pratik değildi.

Diferansiyel kriptanaliz 1990'da yayımlandı; ancak seçilmiş açık metinler gerektirir ve bu, gerçek senaryoların çoğunda uygulanabilir değildir. Doğrusal kriptanaliz 1993'te yayımlandı ve bilinen açık metinlerle çalışır; ancak bunlardan 2^43 tane gerektirir.

Donanım tabanlı kaba kuvvet saldırısı olan Deep Crack, 1999'da DES'i 22 saatte kırdı. Pratikte donanım saldırısı, teorik kriptanaliz ilerlemelerinden daha yıkıcı oldu; çünkü özel açık metin-şifreli metin çiftlerine hiç ihtiyaç duymuyordu.

DES'in kamuya açık ve belgelenmiş biçimde kırılması, politika açısından hemen sonuçlar doğurdu. NIST, DES Sınaması I'in başarıya ulaştığı 1997'de AES yarışması sürecini başlattı. Yarışma, DES standardizasyonu sürecindeki zayıflıklardan kaçınmak üzere açıkça tasarlanmıştı.

AES geliştirilirken bankalar ve devlet kurumları geçici bir önlem olarak 3DES'e geçmeye başladı. DES'in kırılma zaman çizelgesi, AES'in benimsenmesi çalışmalarının aciliyetini ve zamanlamasını doğrudan belirledi.

DES'in kırılma tarihçesini anladığınızı sınayın.

DES giderek daha kısa sürede kırıldı: 1997'de 96 gün, 1998'de 56 saat ve 1999'da 22 saat. EFF'nin 250.000 ABD doları değerindeki Deep Crack sistemi, özel ASIC'ler kullanarak saniyede 90 milyar anahtar denedi.

Hem diferansiyel kriptanaliz (2^47 seçilmiş açık metin) hem de doğrusal kriptanaliz (2^43 bilinen açık metin) teorik olarak DES'i kırar; ancak pratikte asıl etkili yöntem donanım tabanlı kaba kuvvetti. 22 saatlik kırılma, DES'in uygulanabilir bir şifre olarak kullanımını sona erdirdi.