Diferansiyel Kriptanaliz Temelleri

Diferansiyel kriptanaliz (Biham ve Shamir, 1990), açık metin çiftlerindeki farkların bir şifre boyunca nasıl yayıldığını inceleyen seçilmiş açık metin saldırısıdır. Yüksek olasılıkla öngörülebilir çıktı farkları üreten girdi farklarını bularak saldırgan, anahtar bitlerini istatistiksel olarak kurtarır.

XOR tabanlı şifreler için: fark ΔX = X XOR X'. Toplama tabanlı şifreler için: fark ΔX = X - X' mod 2^n. XOR farkları en yaygındır; çünkü XOR ile anahtarlama işleminde XOR değişme özelliğine sahiptir (anahtar çizelgesinin etkileri diferansiyel çiftlerde birbirini götürür).

Bir diferansiyel çift (P, P'), girdi farkı ΔP = P XOR P' olan çifttir. Şifrelemeden sonra (C, C') ve çıktı farkı ΔC = C XOR C' elde edilir. Yararlı bir diferansiyel, yüksek olasılıklı p ile ΔP → ΔC'dir — yani ΔP farkına sahip çok sayıda (P, P') çifti ΔC çıktı farkını üretir.

DDT (Diferansiyel Dağılım Tablosu) şunu sayar: her girdi farkı Δx ve çıktı farkı Δy için, S(x) XOR S(x XOR Δx) = Δy koşulunu sağlayan kaç girdi x olduğu. 2^n'ye bölmek olasılığı verir. İyi bir S-kutusunun en yüksek DDT değeri 2'dir (olasılık 1/2^{n-1}); böylece güçlü diferansiyeller bulunmaz.

r turlu bir blok şifre için, her tur geçişinin bilinen bir olasılığa sahip olduğu ΔP → ΔU1 → ΔU2 → ... → ΔU_{r-1} dizisini bulun. Turların olasılıklarını çarpın: toplam olasılık p = p1 * p2 * ... * p_{r-1}. Saldırı, son tur anahtarını kurtarmak için 2/p çifti kullanır.

Yüksek olasılıklı bir r-1 tur diferansiyeliyle N = 2/p açık metin çifti toplayın. Her aday son tur anahtarı K' için iki şifreli metni bir tur geri çözün, sonuçları XOR'layın ve farkın ΔU_{r-1} ile eşleşip eşleşmediğini kontrol edin. Doğru K', yaklaşık N/2 kez eşleşir; yanlış anahtarlar yaklaşık N/2^{bit_size} kez eşleşir.

AES S-kutusu, GF(2^8) üzerindeki çarpımsal ters işleminin ardından gelen bir afin dönüşümdür. En yüksek DDT değeri 256 üzerinden 4'tür; bu da S-kutusu başına ≤ 4/256 = 1/64 diferansiyel olasılık verir. AES'te tur başına 4 S-kutusu bulunur, ancak Wide Trail tasarımı tam diferansiyel izlerin 2^{-100}'ün altında kalmasını sağlar.

Joan Daemen'in Wide Trail tasarımı (AES/Rijndael'de kullanılır): MixColumns işleminin dal sayısı B'yi tanımlayın. Bir turdan geçen her önemsiz olmayan diferansiyel iz, en az B etkin S-kutusunu etkinleştirir. 4 tur × tur başına 4 S-kutusu, en az 25 etkin S-kutusunu garanti eder → olasılık < 2^{-100}.

Kesilmiş diferansiyeller, farkın yalnızca bir bölümünü belirtir (örneğin, tam fark değerlerini değil, yalnızca hangi sütunların etkin olduğunu). Tam diferansiyellerin çok zayıf kaldığı daha fazla tura yönelik saldırıları mümkün kılar. Azaltılmış turlu AES, SERPENT ve diğer SPN şifrelerine karşı kullanılır.

İmkânsız diferansiyel, hiçbir anahtar için gerçekleşemeyecek bir (ΔP, ΔC) çiftidir. Bu farka sahip gözlemlenen bir çifti (P, P') eşleyen her anahtar elenir. Yeterli sayıda çift toplanarak tüm yanlış anahtarlar elenir ve doğru anahtar geriye kalır.

Bumerang saldırısı (Wagner, 1999), iki kısa diferansiyeli uyarlamalı seçilmiş açık metin/şifreli metin saldırısında birleştirir. Şifreyi, her birinde kısa ve yüksek olasılıklı bir diferansiyel bulunan iki yarıya ayırır ve tek bir diferansiyelin mümkün kılacağından daha uzun bir saldırı gerçekleştirir.

Kriptanalizde Diferansiyel Dağılım Tablosu'nun (DDT) amacı nedir?

Diferansiyel kriptanaliz, yüksek olasılıklı girdi→çıktı farkı yayılımından yararlanır. AES, DDT açısından en iyi S-kutusu ve Wide Trail tasarımı sayesinde buna direnç gösterir. Sıradaki konu: lineer kriptanaliz ve yaklaşım tabloları.