Doğrusal Kriptanaliz ve Yaklaşım Tabloları

Lineer kriptanaliz (Matsui, 1993), bir şifrenin p ≠ 1/2 olasılıkla geçerli olan lineer yaklaşımlarını (belirli bitlerin XOR'u) bulan bilinen açık metin saldırısıdır. Çok sayıda açık metin-şifreli metin çifti kullanılarak istatistiksel yanlılık, anahtar bitlerini açığa çıkarır.

Bir S-kutusu için lineer yaklaşım: seçilen girdi bitlerinin toplamı XOR seçilen çıktı bitlerinin toplamı = 0 (mod 2) eşitliği p olasılığıyla sağlanır. Şöyle ifade edilir: P[a·x XOR b·y = 0] = 1/2 + ε; burada a ve b bit maskeleridir, ε ise yanlılıktır (|ε| >> 0 olması istenir).

LAT şunu sayar: her girdi maskesi a ve çıktı maskesi b için (a·x) XOR (b·S(x)) = 0 koşulunu sağlayan girdi x'lerin sayısını. Yanlılığı elde etmek için 2^{n-1} değerini çıkarın. İyi bir S-kutusunda |max_bias| = 1'dir (olasılık 1/2 ± 1/2^{n/2}); tablo mümkün olduğunca düzdür.

Birden fazla turdaki bağımsız lineer yaklaşımlar için yanlılıklar çarpılır: ε_total = 2^{r-1} * ε_1 * ε_2 * ... * ε_r. Her tur yaklaşımı etkin yanlılığı yarıya indirir. Çok sayıda turdan sonra toplam yanlılık 0'a yaklaşır ve bunu saptamak için üstel olarak daha fazla çift gerekir.

r turlu bir şifreye saldırmak için: r-1 tur boyunca bir ε lineer izi bulun. N = 1/ε^2 bilinen açık metin toplayın. Her aday son tur anahtar baytı k' için son turu kısmen XOR ile çözün ve lineer yaklaşımın N/2 kereden fazla geçerli olup olmadığını kontrol edin. Doğru k', doğru yanlılığı gösterir.

Matsui, 1993'te DES'in 16 turuna, yanlılığı 2^{-21.4} olan 14 turlu bir lineer yaklaşım kullanarak saldırdı. 2^{43} bilinen açık metin gerekti. İlk aşamada 26 anahtar bitini, kalan 30 biti ise kapsamlı aramayla kurtardı. Bu, DES'in tamamında kaba kuvvetten daha hızlı olan ilk pratik saldırıydı.

AES S-kutusunun S-kutusu başına en yüksek LAT girdisi |ε| = 4/256 = 1/64'tür. Wide Trail Stratejisi, herhangi bir 4 turlu izdeki etkin S-kutusu sayısını ≥ 25 ile sınırlar. Toplam yanlılık ≤ (1/64)^{25/2} ≈ 2^{-75} olur. Bu saldırı 2^{150} bilinen açık metin gerektirir ve uygulanabilir değildir.

Diferansiyel: bilinen/seçilmiş açık metin çiftleri; çıktı farklarından yararlanır. Lineer: bilinen açık metinler; istatistiksel lineer yaklaşımlardan yararlanır. Her ikisi de pratik saldırılarda seçilmiş açık metin saldırısı olarak kullanılabilir. Her ikisi de tasarım ölçütüdür: S-kutuları her ikisine de direnç göstermelidir (düşük DDT maksimumu VE düşük LAT maksimumu).

Veri karmaşıklığını azaltmak için birden fazla lineer yaklaşımı aynı anda kullanın. Nyberg ve Leander, Matsui'nin yöntemini genişletti: M yaklaşımının birleştirilmesi veriyi log(M) katsayısı kadar azaltır. PRESENT, SIMON ve diğer hafif şifrelere uygulanır.

Akış şifrelerine uygulanan lineer yaklaşım: anahtar akışı ile LFSR çıktısının lineer bir işlevi arasındaki korelasyonu bulun. Bu korelasyon sıfırdan farklıysa daha hızlı bir anahtar kurtarma saldırısı mümkün olur. Bu yaklaşım, akış şifrelerindeki doğrusal olmayan birleştirme işlevlerinin tasarımına ilham vermiştir.

İntegral kriptanalizde (Knudsen-Wagner), bazı baytların 256 değerin tümünü aldığı, diğerlerinin ise sabit kaldığı bir açık metin kümesi seçilir. Birkaç turdan sonra belirli konumlardaki tüm çıktıların XOR'u 0 olur (dengeli kalır). AES'in yapısından yararlanır ve azaltılmış turlu AES'i verimli biçimde kırar.

Yığılma lemması, lineer yaklaşımların birleştirilmesi hakkında ne söyler?

Lineer kriptanaliz, S-kutuların yanlı lineer yaklaşımlarını bulur. AES, LAT açısından en iyi S-kutusu ve Wide Trail tasarımı sayesinde direnç gösterir. Matsui, 14 turlu bir iz kullanarak 2^43 bilinen açık metinle DES'i kırdı. Sıradaki konu: doğum günü saldırıları ve çakışma bulma.