Rebound saldırısı - Rebound attack

ribaund saldırısı bir araçtır kriptanaliz nın-nin kriptografik hash fonksiyonları. Saldırı ilk olarak 2009 yılında Florian Mendel, Christian Rechberger, Martin Schläffer ve Søren Thomsen tarafından yayınlandı. Saldırmak için tasarlandı AES gibi işlevler gibi Girdap ve Grøstl, ancak daha sonra diğer tasarımlara da uygulanabileceği gösterildi. Keccak, JH ve Skein.

Saldırı

Rebound Attack, bir tür istatistiksel saldırıdır. karma işlevler gibi teknikleri kullanarak rotasyonel ve diferansiyel kriptanaliz çarpışmaları ve diğer ilginç özellikleri bulmak için.

Saldırının temel fikri, belirli bir şeyi gözlemlemektir. diferansiyel karakteristik içinde blok şifreleme (veya bir bölümünde), bir permütasyon veya başka bir tür ilkel. Bu özelliği karşılayan değerler bulmak, ilkel olanı bölerek elde edilir. ${ displaystyle E}$ üç parçaya böylelikle ${ displaystyle E = E _ { text {fw}} circ E _ { text {in}} circ E _ { text {bw}}}$. ${ displaystyle E _ { text {in}}}$ gelen faz olarak adlandırılır ve ${ displaystyle E _ { text {fw}}}$ ve ${ displaystyle E _ { text {bw}}}$ birlikte giden aşama denir. Saldırgan daha sonra, gelen fazdaki diferansiyel karakteristiğin bir kısmını deterministik olarak gerçekleştiren değerleri seçer ve karakteristiğin geri kalanını olasılıkçı bir şekilde yerine getirir.

Dolayısıyla ribaund saldırısı 2 aşamadan oluşur:

1. Gelen (veya ortadaki eşleştirme) aşaması, diferansiyel karakteristiğin olasılıksal bir şekilde karşılanması zor olan kısmını kapsar. Buradaki amaç, karakteristiğin bu kısmı için düşük ortalama ile birçok çözüm bulmaktır. karmaşıklık. Bunu başarmak için, bu aşamadaki karakteristiği tanımlayan karşılık gelen denklem sistemi tam olarak belirlenmemelidir. Bir çözüm ararken, birçok olası çözüm sunan birçok serbestlik derecesi vardır. Gelen faz, yeterli sayıda başlangıç ​​noktası elde etmek için birkaç kez tekrar edilebilir, böylece giden faz muhtemelen başarılı olur.
2. İçinde giden aşama Gelen fazın her bir çözümü, karakteristiğin bu aşamada da geçerli olup olmadığını kontrol ederken her iki yönde de dışarı doğru yayılır. Giden fazdaki karakteristiğin olasılığı mümkün olduğu kadar yüksek olmalıdır.

Bir gelen ve iki giden fazı kullanmanın avantajı, gelen fazdaki diferansiyel karakteristiğin zor kısımlarını verimli bir şekilde hesaplayabilme yeteneğidir. Ayrıca, çıkış aşamasında yüksek olasılık sağlar. Böylelikle, bir diferansiyel karakteristiği bulmanın genel olasılığı, standart diferansiyel teknikleri kullanmaktan daha yüksek hale gelir.

AES benzeri sıkıştırma işlevlerine sahip hash işlevlerine yapılan saldırının ayrıntılı açıklaması

Bir düşünün Özet fonksiyonu hangi kullanır AES benzeri ikame-permütasyon blok şifresi sıkıştırma işlevi. Bu sıkıştırma işlevi aşağıdakilerden oluşan bir dizi turdan oluşur: S kutuları ve doğrusal dönüşümler. Saldırının genel fikri, hesaplama açısından en pahalı kısmının ortada olduğu farklı bir özellik oluşturmaktır. Bu kısım daha sonra gelen faz tarafından kapsanacak, özelliğin daha kolay elde edilen kısmı ise giden fazda kapsanacaktır. Gelen fazdaki karakteristiği tanımlayan denklem sistemi, az belirlenmiş, öyle ki giden aşama için birçok başlangıç ​​noktası oluşturulabilir. Karakteristiğin daha zor kısmı gelen fazda bulunduğu için, burada standart diferansiyelleri kullanmak mümkündür, oysa kesik diferansiyeller daha yüksek olasılıklar elde etmek için giden fazda kullanılır.

Gelen faz tipik olarak birkaç aktif duruma sahip olacaktır bayt (bayt sıfır olmayan farklarla) başlangıçta, daha sonra çok sayıda etkin bayt düşük sayıdaki aktif sayıya dönmeden önce, turun ortasında bayt aşamanın sonunda. Fikir, çok sayıda etkin bayt girişinde ve çıkışında S-kutusu evrenin ortasında. Özellikler daha sonra, gelen fazın başlangıcındaki ve sonundaki farklılıklar için değerler seçerek, bunları ortaya doğru yayarak ve giriş ve çıkışındaki eşleşmeleri arayarak verimli bir şekilde hesaplanabilir. S-kutusu. İçin AES Şifreler gibi bu da tipik olarak satır veya sütun şeklinde yapılabilir, bu da prosedürü nispeten verimli hale getirir. Farklı başlangıç ​​ve bitiş değerlerinin seçilmesi, gelen fazda birçok farklı diferansiyel özelliğe yol açar.

Outbound aşamasında amaç, gelen fazda bulunan özellikleri geriye ve ileriye doğru yaymak ve istenen özelliklerin takip edilip edilmediğini kontrol etmektir. Buraya, kesik diferansiyeller Bunlar daha yüksek olasılıklar verdiği için genellikle kullanılır ve farklılıkların belirli değerleri, bir bulmanın amacı ile ilgisizdir. çarpışma. Giden fazın istenen modelini takip eden karakteristiğin olasılığı, aktif olanların sayısına bağlıdır. bayt ve bunların karakteristikte nasıl düzenlendiği. Başarmak için çarpışma, giden fazdaki farklılıkların belirli bir türden olması yeterli değildir; herhangi bir aktif bayt karakteristiğin başlangıcında ve sonunda ayrıca herhangi bir ileri besleme işlemi iptal edilecek şekilde bir değere sahip olmalıdır. Bu nedenle, karakteristiği tasarlarken, herhangi bir sayıda aktif bayt giden fazın başlangıcında ve sonunda aynı konumda olmalıdır. Bunların olasılığı bayt iptal etme, giden özelliğin olasılığına eklenir.

Genel olarak, giden fazda birden fazla beklenen sayıda doğru özellik elde etmek için gelen fazda yeterince fazla özellik üretmek gerekir. Ayrıca, daha fazla sayıda raundda yakın çarpışmalar, giden fazın birkaç etkin bayt bu iptal etmez.

Whirlpool'a örnek saldırı

Ribaund Saldırısı, Özet fonksiyonu Girdap bulmak çarpışmalar varyantlarda sıkıştırma işlevi ( AES -sevmek blok şifreleme, W) 4,5 veya 5,5 mermiye düşürülür. Yakın çarpışmalar 6.5 ve 7.5 mermilerde bulunabilir. Aşağıda 4,5 mermi hücumunun bir açıklaması bulunmaktadır.

Ön hesaplama

Geri tepme saldırısını etkili kılmak için, S-kutusu farklılıklar saldırıdan önce hesaplanır. İzin Vermek ${ displaystyle S: {0,1 } ^ {8} - {0,1 } ^ {8}}$ temsil etmek S-kutusu. Sonra her çift için ${ displaystyle (a, b) {0,1 } ^ {8}} içinde$ çözümleri buluyoruz ${ displaystyle x}$ (eğer varsa) denkleme

${ displaystyle S (x) oplus S (x oplus a) = b}$,

nerede ${ displaystyle a}$ girdi farkını temsil eder ve ${ displaystyle b}$ çıktı farkını temsil eder S-kutusu. Bu 256'ya 256 tablo (fark dağıtım tablosu, DDT olarak adlandırılır), içinden geçen herhangi bir belirli giriş / çıkış çiftinin karakteristiğini izleyen değerleri bulmayı mümkün kılar. S-kutusu. Sağdaki tablo denklem için olası çözüm sayısını ve bunların ne sıklıkla meydana geldiğini gösterir. İlk satır imkansız diferansiyelleri açıklarken, son satır sıfır diferansiyeli tanımlar.

Saldırıyı gerçekleştirmek

Bulmak için çarpışma 4,5 turda Girdap aşağıdaki tabloda gösterilen tipte bir diferansiyel karakteristiği bulunmalıdır. Bu özellik, kırmızı ile işaretlenmiş minimum etkin bayta (sıfır olmayan farklara sahip bayt) sahiptir. Karakteristik, her turdaki aktif bayt sayısı ile tanımlanabilir, örn. 1 → 8 → 64 → 8 → 1 → 1.

4,5 tur Whirlpool hash fonksiyonunda kesilmiş diferansiyel karakteristik.

${ displaystyle E _ { text {bw}}}$
${ displaystyle E _ { text {in}}}$
${ displaystyle E _ { text {fw}}}$

Gelen faz

Gelen fazın amacı, 8 → 64 → 8 aktif bayt dizisi ile tanımlanan karakteristiğin bir kısmını yerine getiren farklılıkları bulmaktır. Bu, aşağıdaki üç adımda yapılabilir:

1. Çıkıştaki 8 etkin bayt için rastgele sıfır olmayan farkı seçin. MixRows 3. turda işlem. Bu farklılıklar daha sonra geriye doğru yayılır. SubBytes 3. turda işlem. MixRows işleminin özellikleri nedeniyle, tamamen aktif bir durum elde edilir. Bunun her satır için bağımsız olarak yapılabileceğini unutmayın.
2. 2. turda MixRows işleminin girdisindeki her etkin bayt için bir fark seçin ve bu farklılıkları 3. turdaki SubBytes işleminin girişine doğru ilerletin. Bunu her baytın 255 sıfır olmayan farkının tümü için yapın. Yine, bu her satır için bağımsız olarak yapılabilir.
3. İçinde ortadaki eşleştirme adımı, DDT tablosunu 3. turdaki SubBytes işlemiyle eşleşen giriş / çıkış farklılıklarını (adım 1 ve 2'de bulunduğu gibi) bulmak için kullanırız. Her satır bağımsız olarak kontrol edilebilir ve beklenen çözüm sayısı başına 2'dir. S-kutusu. Toplamda, diferansiyel karakteristiği izleyen beklenen değer sayısı 2'dir⁶⁴.

Bu adımlar 2 ile tekrar edilebilir⁶⁴ 1. adımda farklı başlangıç ​​değerleri, toplamda 2¹²⁸ gelen fazdaki diferansiyel karakteristiği izleyen gerçek değerler. Her 2 set⁶⁴ değerler ile bulunabilir karmaşıklık 2⁸ ön hesaplama adımı nedeniyle yuvarlak dönüşümler.

Giden aşama

Giden faz, diferansiyel karakteristiği olasılıklı bir şekilde tamamlar. Giden aşaması, kesik diferansiyeller Gelen fazın tersine. Gelen aşamada bulunan her bir başlangıç ​​noktası, ileri ve geri yayılır. İstenen karakteristiği takip etmek için, 8 aktif baytın her iki yönde de tek bir aktif bayta yayılması gerekir. Böyle bir 8'den 1'e geçiş 2 olasılıkla gerçekleşir⁻⁵⁶,^[1] bu nedenle özelliği yerine getirmek 2 olasılığa sahiptir⁻¹¹². Sağlamak için çarpışma, karakteristiğin başlangıcındaki ve sonundaki değerler, ileri besleme işlemi sırasında iptal edilmelidir. Bu yaklaşık 2 olasılıkla gerçekleşir⁻⁸ve bu nedenle, giden fazın genel olasılığı 2'dir⁻¹²⁰.

Bulmak için çarpışma, 2¹²⁰ gelen aşamada başlangıç ​​noktaları oluşturulmalıdır. Bu ortalama olarak yapılabileceğinden karmaşıklık başlangıç ​​noktası başına 1^[2] Genel olarak karmaşıklık saldırının yüzdesi 2¹²⁰.

Saldırıyı genişletmek

Temel 4,5 turluk saldırı, gelen aşamada iki tam aktif durum kullanılarak 5,5 turluk bir saldırıya kadar genişletilebilir. Bu artar karmaşıklık yaklaşık 2¹⁸⁴.^[3]

Giden fazın 8 aktif bayt ile başlayıp bitecek şekilde genişletilmesi, 52 baytlık bir çarpışmaya neden olur. Girdap ile 7.5 mermiye düşürüldü karmaşıklık 2¹⁹².^[4]

Saldırganın zincirleme değeri üzerinde kontrole sahip olduğunu ve dolayısıyla anahtar programına girdinin olduğunu varsayarak Girdap Saldırı, 52 baytlık yarı serbest başlangıçlı ve çarpışmaya yakın bir çarpışmada 9,5 mermiye kadar uzatılabilir. karmaşıklık 2¹²⁸.^[5]

Notlar

Referanslar

• Ribaund Saldırısı: Azaltılmış Girdap ve Grøstl'ün Kriptanalizi Florian Mendel, Christian Rechberger, Martin Schlaffer ve Soren S. Thomsen (Fast Software Encryption 2009: 260-276)
• Azaltılmış Grøstl Hash Fonksiyonuna Ribaund Saldırısı Florian Mendel, Christian Rechberger, Martin Schlaffer ve Soren S. Thomsen (The Cryptographer's Track at RSA Conference 2010: 350-365)
• Dengesiz Ribaund Saldırısı - Keccak'a Başvuru Alexandre Duc, Jian Guo, Thomas Peyrin, Lei Wei (IACR Cryptology ePrint Arşiv Yılı 2011/420)
• Rebound Saldırıları Nasıl İyileştirilir María Naya-Plasencia FHNW, Windisch, İsviçre (CRYPTO'11 Kriptolojide Gelişmelerle ilgili 31. yıllık konferansın Bildirileri Sayfaları 188-205)
• Rebound Attack ve Subspace Ayırıcıları: Whirlpool Uygulaması Mario Lamberger, Florian Mendel, Christian Rechberger, Vincent Rijmen ve Martin Schläffer (IACR Cryptology ePrint Arşivi, Yıl. 2010/198).
• AES tabanlı hash fonksiyonlarının kriptanalizi Martin Schläffer'ın doktora tezi