Biklik saldırı - Biclique attack - Wikipedia

Bir biclik saldırı bir varyantıdır ortada buluşmak (MITM) yöntemi kriptanaliz. Bir kullanır bisiklik MITM saldırısı tarafından olası saldırıya uğramış mermi sayısını artıracak yapı. Biklik kriptanaliz, MITM saldırılarına dayandığından, her ikisi için de geçerlidir. blok şifreleri ve (yinelenen) karma işlevler. Biklik saldırıların her ikisini de tam olarak kırdığı bilinmektedir. AES^[1] ve dolu FİKİR,^[2] ancak kaba kuvvete göre sadece küçük bir avantaja sahip. Aynı zamanda KASUMI şifreleme ve ön görüntü direnci Skein-512 ve SHA-2 hash fonksiyonları.^[3]

Biklik saldırı hala devam ediyor (Nisan 2019 itibarıyla^{[Güncelleme]}) alenen bilinen en iyi tek tuşlu saldırı AES. Saldırının hesaplama karmaşıklığı ${ displaystyle 2 ^ {126.1}}$, ${ displaystyle 2 ^ {189.7}}$ ve ${ displaystyle 2 ^ {254.4}}$ sırasıyla AES128, AES192 ve AES256 için. Bu, AES'e yapılan tüm tur sayısına saldıran herkesin bildiği tek tuşlu saldırıdır.^[1] Önceki saldırılar yuvarlak azaltılmış varyantlara saldırdı (tipik olarak varyantlar 7 veya 8 mermiye düşürüldü).

Saldırının hesaplama karmaşıklığı ${ displaystyle 2 ^ {126.1}}$, teorik bir saldırıdır, yani AES'in güvenliği bozulmamıştır ve AES kullanımı nispeten güvenli kalır. Biklik saldırı yine de ilginç bir saldırıdır ve blok şifrelerde kriptanaliz yapmak için yeni bir yaklaşım önermektedir. Saldırı ayrıca AES hakkında daha fazla bilgi verdi çünkü orada kullanılan mermi sayısındaki güvenlik marjını sorguladı.

Tarih

Orijinal MITM saldırısı ilk olarak Diffie ve Cehennem adamı 1977'de, DES'in kriptanalitik özelliklerini tartıştıklarında.^[4] Anahtar boyutunun çok küçük olduğunu ve DES'i birden çok kez farklı anahtarlarla yeniden uygulamanın anahtar boyutu için bir çözüm olabileceğini savundular; ancak, MITM saldırıları nedeniyle çift DES kullanılmamasını tavsiye ettiler ve minimum olarak üçlü DES önerdiler (MITM saldırıları, güvenliği azaltmak için çift DES'e kolayca uygulanabilir. ${ displaystyle 2 ^ {56 * 2}}$ sadece ${ displaystyle 2 * 2 ^ {56}}$, çünkü eğer düz ve şifreli metne sahiplerse, birinci ve ikinci DES şifrelemesini bağımsız olarak zorla çalıştırabilirsiniz).

Diffie ve Hellman, MITM saldırılarını önerdiğinden beri, temel MITM saldırısının uygulanamaz olduğu durumlarda yararlı olan birçok varyasyon ortaya çıktı. Biklik saldırı varyantı ilk olarak Dmitry Khovratovich, Hash-function kriptanaliz ile kullanım için Rechberger ve Savelieva.^[5] Bununla birlikte, AES'e yaptıkları saldırıları yayınladıklarında, bisiklik kavramını blok şifreleme kriptanalizini içeren gizli anahtar ortamına nasıl uygulayacaklarını gösteren Bogdanov, Khovratovich ve Rechberger'di. Bundan önce, MITM saldırısını kolaylaştırmak için iki 'MITM alt şifresi' arasında bağımsız anahtar bitlerine ihtiyaç duyulması nedeniyle, AES ve diğer birçok blok şifresine yönelik MITM saldırıları çok az ilgi görmüştü - bu, birçok kişiyle başarılması zor bir şey. AES'ninki gibi modern anahtar programlar.

Biklik

Biklik yapının ne olduğuna dair genel bir açıklama için şu makaleye bakın: bicliques.

Bir MITM saldırısında, anahtar bitler ${ displaystyle K_ {1}}$ ve ${ displaystyle K_ {2}}$birinci ve ikinci alt şifreye ait olanların bağımsız olması gerekir; yani, birbirlerinden bağımsız olmaları gerekir, aksi takdirde düz ve şifreli metin için eşleşen ara değerler MITM saldırısında bağımsız olarak hesaplanamaz (blokların anahtar bitlerinin paylaşılabildiği MITM saldırılarının varyantları vardır. Bkz. 3 alt kümeli MITM saldırısı ). Saldırıya uğrayan şifrenin yayılması nedeniyle, bu özellikten genellikle daha fazla sayıda turda yararlanılması zordur.
Basitçe söylemek gerekirse: Ne kadar çok tur atarsanız, o kadar büyük alt şifrelere sahip olursunuz. Sahip olduğunuz daha büyük alt şifrelere sahip olduğunuzda, alt şifreler arasındaki daha az bağımsız anahtar biti, bağımsız olarak kaba kuvvet uygulamak zorunda kalacaksınız. Elbette, her bir alt şifredeki bağımsız anahtar bitlerinin gerçek sayısı, anahtar çizelgesinin difüzyon özelliklerine bağlıdır.

Biclique'in yukarıdakilerin üstesinden gelmeye yardımcı olma yolu, örneğin, MITM saldırılarını kullanarak 7 tur AES'e saldırmasına ve ardından 3 uzunluğunda bir bislik yapı kullanarak (yani şifrenin 3 turunu kaplar) yararlanmasına izin vermesidir. 7. turun başlangıcındaki ara durumu son turun sonuna eşleyebilirsiniz, örneğin 10 (eğer AES128 ise), böylece temel bir MITM saldırısıyla bu kadar mermiye saldırmak mümkün olmasa bile şifrenin tüm tur sayısına saldırır.

Bu yüzden bisikliğin anlamı, MITM saldırısının sonundaki bir ara değeri en sondaki şifreli metne eşleyebilen bir yapıyı etkili bir şekilde inşa etmektir. Sonunda ara durumun hangi şifreli metne eşleneceği, elbette şifreleme için kullanılan anahtara bağlıdır. Durumu bislikteki şifreli metne eşlemek için kullanılan anahtar, MITM saldırısının birinci ve ikinci alt şifresinde zorlanan anahtar bitlerine dayanır.

Bu nedenle, biclique saldırılarının özü, MITM saldırısının yanı sıra, keybitlere bağlı olan bir biclique yapıyı etkin bir şekilde inşa edebilmektir. ${ displaystyle K_ {1}}$ ve ${ displaystyle K_ {2}}$ belirli bir ara durumu karşılık gelen şifreli metne eşleyebilir.

Biklik nasıl yapılır

Kaba kuvvet

Almak ${ displaystyle 2 ^ {d}}$ ara devletler ve ${ displaystyle 2 ^ {d}}$ ciphertexts, ardından aralarında eşleşen anahtarları hesaplayın. Bu gerektirir ${ displaystyle 2 ^ {2d}}$ her ara durumun tüm şifreli metinlere bağlanması gerektiğinden anahtar kurtarmalar.

Bağımsız ilişkili anahtar diferansiyeller

(Bu yöntem, Bogdanov, Khovratovich ve Rechberger tarafından makalelerinde önerilmiştir: Biclique Cryptanalysis of the Full AES^[1])

Ön hazırlık:
Biklikliğin işlevinin ara değerleri haritalamak olduğunu unutmayın. ${ displaystyle S}$, şifreli metin değerlerine, ${ displaystyle C}$, anahtara göre ${ displaystyle K [i, j]}$ öyle ki:
${ displaystyle forall i, j: S_ {j} { xrightarrow [{f}] {K [i, j]}} C_ {i}}$

Prosedür:
Adım bir: Bir ara durum (${ displaystyle S_ {0}}$), bir şifreli metin (${ displaystyle C_ {0}}$) ve bir anahtar (${ displaystyle K [0,0]}$) şu şekilde seçilir: ${ displaystyle S_ {0} { xrightarrow [{f}] {K [0,0]}} C_ {o}}$, nerede ${ displaystyle f}$ belirli bir anahtar kullanarak ara durumu bir şifreli metne eşleyen işlevdir. Bu, temel hesaplama olarak belirtilir.

İkinci adım: İki boyutta ilgili anahtar seti ${ displaystyle 2 ^ {d}}$ seçilmiş. Anahtarlar şu şekilde seçilir:

• İlk anahtar seti, aşağıdaki diferansiyel gereksinimleri karşılayan anahtarlardır. ${ displaystyle f}$ temel hesaplamaya göre: ${ displaystyle 0 { xrightarrow [{f}] { Delta _ {i} ^ {K}}} Delta _ {i}}$
• İkinci anahtar seti, aşağıdaki fark gereksinimleri karşılayan anahtarlardır. ${ displaystyle f}$ temel hesaplamaya göre: ${ displaystyle nabla _ {j} { xrightarrow [{f}] { nabla _ {j} ^ {K}}} 0}$
• Anahtarlar, ${ displaystyle Delta _ {i}}$- ve ${ displaystyle nabla _ {j}}$-farklılar bağımsızdır - yani doğrusal olmayan herhangi bir aktif bileşeni paylaşmazlar.

Diğer bir deyişle:
0 giriş farkı, şu değerdeki bir çıktı farkıyla eşleşmelidir: ${ displaystyle Delta _ {i}}$ önemli bir fark altında ${ displaystyle Delta _ {i} ^ {K}}$. Tüm farklılıklar temel hesaplamaya göredir.
Giriş farkı ${ displaystyle nabla _ {j}}$ şunun temel farkı altında 0'lık bir çıktı farkıyla eşleşmelidir ${ displaystyle nabla _ {J} ^ {K}}$. Tüm farklılıklar temel hesaplamaya göredir.

Adım üç: İzler doğrusal olmayan bileşenleri (S kutuları gibi) paylaşmadığından, yollar birleştirilerek şunları elde edilebilir:
${ displaystyle 0 { xrightarrow [{f}] { Delta _ {i} ^ {K}}} Delta _ {i} oplus nabla _ {j} { xrightarrow [{f}] { nabla _ {j} ^ {K}}} 0 = nabla _ {j} { xrightarrow [{f}] { Delta _ {i} ^ {K} oplus nabla _ {j} ^ {K}} } Delta _ {i}}$,
2. adımdaki her iki farkın tanımlarına uymaktadır.
Tuple'ı görmek önemsizdir. ${ displaystyle (S_ {0}, C_ {0}, K [0,0])}$ Temel hesaplamadan, farklılıklar temel hesaplamaya göre olduğundan tanım gereği her iki farklılığa da uygundur. İkame ${ displaystyle S_ {0}, C_ {0}}$ ${ displaystyle K [0,0]}$ iki tanımdan herhangi birine girerseniz, ${ displaystyle 0 { xrightarrow [{f}] {0}} 0}$ dan beri ${ displaystyle Delta _ {0} = 0, nabla _ {0} = 0}$ ve ${ displaystyle Delta _ {0} ^ {K} = 0}$.
Bu, temel hesaplamanın demetinin birleştirilmiş izlere de XOR'lanabileceği anlamına gelir:${ displaystyle S_ {0} oplus nabla _ {j} { xrightarrow [{f}] {K [0,0] oplus Delta _ {i} ^ {K} oplus nabla _ {j} ^ {K}}} C_ {0} oplus Delta _ {i}}$

Adım dört: Bunu görmek önemsiz:
${ displaystyle S_ {j} = S_ {0} oplus nabla _ {j}}$
${ displaystyle K [i, j] = K [0,0] oplus Delta _ {i} ^ {K} oplus nabla _ {j} ^ {K}}$
${ displaystyle C_ {i} = C_ {0} oplus Delta _ {i}}$
Bu, yukarıdaki birleşik farklı yollarla değiştirilirse, sonuç şöyle olacaktır:
${ displaystyle S_ {j} { xrightarrow [{f}] {K [i, j]}} C_ {i}}$
Tanımla aynı olan, daha önce bir biclik için vardı:
${ displaystyle forall i, j: S_ {j} { xrightarrow [{f}] {K [i, j]}} C_ {i}}$

Böylelikle bir bislik boyut oluşturmak mümkündür ${ displaystyle 2 ^ {2d}}$ (${ displaystyle 2 ^ {2d}}$ her şeyden beri ${ displaystyle 2 ^ {d}}$ ilk tuş takımının tuşları ile birleştirilebilir. ${ displaystyle 2 ^ {d}}$ ikinci anahtar grubundaki anahtarlar). Bu, bir bislik boyut anlamına gelir ${ displaystyle 2 ^ {2d}}$ sadece kullanılarak oluşturulabilir ${ displaystyle 2 * 2 ^ {d}}$ diferansiyellerin hesaplamaları ${ displaystyle Delta _ {i}}$ ve ${ displaystyle nabla _ {j}}$ bitmiş ${ displaystyle f}$. Eğer ${ displaystyle Delta _ {i} neq nabla _ {j}}$ için ${ displaystyle i + j> 0}$ sonra tüm anahtarlar ${ displaystyle K [i, j]}$ biclikte de farklı olacaktır.

AES'e yapılan önde gelen biklik saldırıda biklik bu şekilde inşa edilir. Bu teknikle biklik inşa etmede bazı pratik sınırlamalar vardır. Biklik ne kadar uzunsa, farklı yolların kapsaması gereken turlar o kadar fazladır. Şifrenin difüzyon özellikleri, bu nedenle, bisikliği oluşturmanın etkinliğinde önemli bir rol oynar.

Biklik yapmanın diğer yolları

Bogdanov, Khovratovich ve Rechberger ayrıca, "Tam AES'nin Biklik Kriptanalizi" adlı makalede "Interleaving Related-Key Differential Trails" olarak adlandırılan, bisikliği inşa etmenin başka bir yolunu açıklamaktadır:^[1]".

Biklik Kriptanaliz prosedürü

Adım bir: Saldırgan, tüm olası anahtarları, boyutun anahtar alt kümelerine gruplandırır ${ displaystyle 2 ^ {2d}}$ bazı ${ displaystyle d}$, bir gruptaki anahtarın indekslendiği ${ displaystyle K [i, j]}$ boyut matrisinde ${ displaystyle 2 ^ {d} times 2 ^ {d}}$. Saldırgan şifreyi iki alt şifreye böler, ${ displaystyle f}$ ve ${ displaystyle g}$ (öyle ki ${ displaystyle E = f circ g}$), normal bir MITM saldırısında olduğu gibi. Alt şifrelerin her biri için anahtar seti esas niteliğindedir ${ displaystyle 2 ^ {d}}$ve denir ${ displaystyle K [i, 0]}$ ve ${ displaystyle K [0, j]}$. Alt şifrelerin birleşik anahtarı yukarıda belirtilen matris ile ifade edilir. ${ displaystyle K [i, j]}$.

İkinci adım: Saldırgan, her grup için bir biclik oluşturur. ${ displaystyle 2 ^ {2d}}$ anahtarlar. Biklik, eşlendiği için boyut-d'dir. ${ displaystyle 2 ^ {d}}$ iç durumlar ${ displaystyle S_ {j}}$, için ${ displaystyle 2 ^ {d}}$ şifreli metinler, ${ displaystyle C_ {i}}$, kullanma ${ displaystyle 2 ^ {2d}}$ anahtarlar. "Biklik nasıl yapılır" bölümü, "Bağımsız ilişkili anahtar farklılıkları" kullanılarak bisikliğin nasıl inşa edileceğini gösterir. Biclik, bu durumda, anahtar setinin diferansiyelleri kullanılarak inşa edilmiştir, ${ displaystyle K [i, 0]}$ ve ${ displaystyle K [0, j]}$, alt şifrelere ait.

Adım üç: Saldırgan, ${ displaystyle 2 ^ {d}}$ olası şifreli metinler, ${ displaystyle C_ {i}}$ve bir şifre çözme oracle'dan eşleşen düz metinleri sağlamasını ister, ${ displaystyle P_ {i}}$.

Adım dört: Saldırgan dahili bir durum seçer, ${ displaystyle S_ {j}}$ ve karşılık gelen düz metin, ${ displaystyle P_ {i}}$ve her zamanki MITM saldırısını gerçekleştirir. ${ displaystyle f}$ ve ${ displaystyle g}$ iç durumdan ve düz metinden saldırarak.

Beşinci adım: Eşleşen bir anahtar aday bulunduğunda ${ displaystyle S_ {j}}$ ile ${ displaystyle P_ {i}}$, bu anahtar başka bir düz / şifreli metin çiftinde test edilir. anahtar diğer çiftte geçerliyse, büyük olasılıkla doğru anahtartır.

Örnek saldırı

Aşağıdaki örnek, "Biclique Cryptanalysis of the Full AES^[1]".
Örnekteki açıklamalar saldırının yazarlarının kullandığı terminolojinin aynısını kullanır (yani değişken isimler vb. İçin).
Basit olması açısından, aşağıda ele alınan AES128 varyantına yapılan saldırıdır.
Saldırı, bislik ile son 3 turu kapsayan 7 mermi MITM saldırısından oluşur.

Anahtar bölümleme

Anahtar alanı, ${ displaystyle 2 ^ {112}}$ her grubun oluştuğu anahtar grupları ${ displaystyle 2 ^ {16}}$ anahtarlar.
Her biri için ${ displaystyle 2 ^ {112}}$ gruplar, benzersiz bir temel anahtar ${ displaystyle K [0,0]}$ temel hesaplama için seçilir.
Temel anahtar, aşağıdaki tabloda gösterilen sıfıra ayarlanmış iki belirli bayta sahiptir (bu, anahtarı AES'nin AES128 için 4x4 matriste yaptığı gibi temsil eder):

${ displaystyle { begin {bmatrix} - & - & - & 0 0 & - & - & - - & - & - & - - & - & - & - end {bmatrix}}}$

Anahtarın kalan 14 baytı (112 bit) daha sonra numaralandırılır. Bu verir ${ displaystyle 2 ^ {112}}$ benzersiz temel anahtarlar; her anahtar grubu için bir tane.
Sıradan ${ displaystyle 2 ^ {16}}$ daha sonra her gruptaki anahtarlar, temel anahtarlarına göre seçilir. Temel tuşla neredeyse aynı olacak şekilde seçilirler. Yalnızca 2 bayt olarak değişir (ya ${ displaystyle i}$s veya ${ displaystyle j}$aşağıda gösterilen 4 bayt):

${ displaystyle { begin {bmatrix} - & - & i & i j & - & j & - - & - & - & - - & - & - & - end {bmatrix}}}$

Bu verir ${ displaystyle 2 ^ {8} K [i, 0]}$ ve ${ displaystyle 2 ^ {8} K [0, j]}$hangi kombine verir ${ displaystyle 2 ^ {16}}$ farklı anahtarlar, ${ displaystyle K [i, j]}$. bunlar ${ displaystyle 2 ^ {16}}$ tuşlar, ilgili temel anahtar için gruptaki anahtarları oluşturur.

Biklik yapı

${ displaystyle 2 ^ {112}}$ bisiklikler, "Biklik nasıl inşa edilir" bölümünde açıklandığı gibi "Bağımsız ilişkili anahtar farklılıkları" tekniği kullanılarak oluşturulur.
Bu tekniğin kullanılmasının gerekliliği, birleştirilmesi gereken ileri ve geri diferansiyel izlerin herhangi bir aktif doğrusal olmayan öğeyi paylaşmamasıydı. Durumun böyle olduğu nasıl bilinir?
1. adımdaki anahtarların temel anahtara göre seçilme şekli nedeniyle, diferansiyel izler ${ displaystyle Delta _ {i}}$ anahtarları kullanmak ${ displaystyle K [i, 0]}$ Asla herhangi bir aktif S-box'ı (AES'deki doğrusal olmayan tek bileşen) diferansiyel izlerle paylaşmayın ${ displaystyle nabla _ {j}}$ anahtarı kullanmak ${ displaystyle K [0, j]}$. Bu nedenle, farklı yolları XOR ve biklik oluşturmak mümkündür.

MITM saldırısı

Biklikler oluşturulduğunda, MITM saldırısı neredeyse başlayabilir. MITM saldırısını yapmadan önce, ${ displaystyle 2 ^ {d}}$ düz metinden ara değerler:
${ displaystyle P_ {i} { xrightarrow [{}] {K [i, 0]}} { xrightarrow [{v_ {i}}] {}}}$,
${ displaystyle 2 ^ {d}}$ şifreli metinden ara değerler:
${ displaystyle { xleftarrow [{v_ {j}}] {}} { xleftarrow [{}] {K [0, j]}} S_ {j}}$,
ve ilgili ara durumlar ve alt anahtarlar ${ displaystyle K [i, 0]}$ veya ${ displaystyle K [0, j]}$ancak önceden hesaplanır ve saklanır.

Artık MITM saldırısı gerçekleştirilebilir. Bir anahtarı test etmek için ${ displaystyle K [i, j]}$, yalnızca şifrenin bazı bölümlerinin yeniden hesaplanması gereklidir, ${ displaystyle P_ {i} { xrightarrow [{}] {K [i, 0]}} { xrightarrow [{v_ {i}}] {}}}$ ve ${ displaystyle P_ {i} { xrightarrow [{}] {K [i, j]}} { xrightarrow [{v_ {i}}] {}}}$. Geriye dönük hesaplama için ${ displaystyle S_ {j}}$ -e ${ displaystyle { xleftarrow [{v_ {j}}] {}}}$, bu yeniden hesaplanması gereken 4 S kutusudur. İleriye dönük hesaplama için ${ displaystyle P_ {i}}$ -e ${ displaystyle { xrightarrow [{v_ {i}}] {}}}$, sadece 3'tür (gerekli yeniden hesaplama miktarı için ayrıntılı bir açıklama "Tam AES'in Biclique Cryptanalysis'i bulunabilir.^[1]"bu örneğin alındığı kağıt).

Ara değerler eşleştiğinde, bir anahtar aday ${ displaystyle K [i, j]}$ arasında ${ displaystyle P_ {i}}$ ve ${ displaystyle S_ {j}}$ bulunan. Anahtar adayı daha sonra başka bir düz / şifreli metin çifti üzerinde test edilir.

Sonuçlar

Bu saldırı, AES128'in hesaplama karmaşıklığını düşürür. ${ displaystyle 2 ^ {126.18}}$, bruteforce yaklaşımından 3-5 kat daha hızlıdır. Saldırının veri karmaşıklığı ${ displaystyle 2 ^ {88}}$ ve hafıza karmaşıklığı ${ displaystyle 2 ^ {8}}$.

Referanslar