Bir doğum günü saldırı veya doğum günü paradoks saldırı saldırı türüdür kriptanaliz sömüren matematiksel kavramları tarafından kullanılanlara denk doğum günü paradoksu içinde olasılık teorisi . Bu saldırı, iki veya daha fazla kişi arasındaki iletişimi değiştirmek için kullanılabilir. Saldırı, çekmece prensibinde olduğu gibi, rastgele saldırı girişimleriyle daha yüksek çarpışma olasılığı ve sabit bir permütasyon seviyesi sayesinde mümkündür .
Doğum günleri paradoksuna bir örnek olarak, aşağıdaki senaryoyu düşünmek mümkündür.
“30 kişilik bir öğretmen, öğrencilerinden aynı gün doğum günlerini kutlayan iki öğrenci olup olmadığını belirlemek için doğum tarihlerini vermelerini ister - bu, hash çarpışmasına karşılık gelir . "
Sezgisel olarak, bunun gerçekleşme olasılığı düşük görünüyor. Öğretmen belirli bir gün sürdüyse, örneğin14 Ağustos, o zaman en az bir öğrencinin o belirli günde doğmuş olma olasılığı yaklaşık% 7,9'dur.
Öte yandan, en az bir öğrenci ile aynı doğum günü var olma olasılığı herhangi : Diğer öğrencilerin yani% 70 yaklaşık olarak eşit olduğu ile .
Bir fonksiyon olsun , saldırının amacı iki farklı öncülü bulmaktır , böyle bir çifte çarpışma denir . Bir çarpışma bulmak için kullanılan yöntem, karşılaştırma basitçe görüntü arasında rastgele seçilebilir ya da farklı öncülleri için psödo-rastgele aynı sonucu birden fazla kez kadar devam ettirilecektir. Doğum günleri paradoksu sayesinde bu yöntem çok etkili olabilir. Bir Özellikle, fonksiyon üzerinde tanımlı aynı olasılık ile farklı görüntüler sunar ve bir set büyük yeterince sonra biri farklı kökenden bir çift elde bekleyebilirsiniz ve neden sadece fonksiyonun görüntü hesapladıktan sonra ortalama farklı kökenlerden.
Aşağıdaki deneyi düşünün. Bir kardinal olarak ayarlanmış seçtiğimiz tekrarlar izin vererek rastgele değerler. Bu deney sırasında en az bir değerin birden fazla seçilme olasılığı olsun . Bu olasılık kabaca eşittir Seçmemiz gereken en küçük değer sayısı olsun , o zaman bir çarpışma bulma olasılığı en azından bu ifadeyi ters çevirerek aşağıdaki yaklaşımı buluruz ve çarpışma olasılığına 0,5'e eşit bir değer atadığımızda, İlk çarpışmayı bulmadan önce seçilecek beklenen değer sayısı olsun . Bu sayı yaklaşık olarak eşittir
Örneğin, 64 bitlik bir karma kullanılırsa, kabaca 1.8 × 10 19 farklı görüntü vardır. Onlar saldırgan için iyi senaryo olan elde edilecek muhtemel olarak ise, o zaman “sadece” × 10 5.1 alacaktır 9 kullanan bir çarpışma oluşturmak için, ya da milyar 5 hakkında denemeden kaba kuvvet . Bu değer yıldönümü sınırı olarak adlandırılır ) ve ikili olarak bu değer olarak hesaplanabilir .
Karma bit sayısı |
Olası görüntüler (H) |
İstenilen çarpışma olasılığı (p) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
10 −18 | 10 −15 | 10 −12 | 10 −9 | 10 −6 | % 0.1 | % 1 | % 25 | % 50 | % 75 | ||
16 | 65.536 | <2 | <2 | <2 | <2 | <2 | 11 | 36 | 190 | 300 | 430 |
32 | 4,3 × 10 9 | <2 | <2 | <2 | 3 | 93 | 2.900 | 9.300 | 50.000 | 77.000 | 110.000 |
64 | 1.8 × 10 19 | 6 | 190 | 6.100 | 190.000 | 6 100.000 | 1.9 × 10 8 | 6,1 × 10 8 | 3,3 × 10 9 | 5,1 × 10 9 | 7,2 × 10 9 |
128 | 3,4 × 10 38 | 2.6 × 10 10 | 8,2 × 10 11 | 2,6 × 10 13 | 8,2 × 10 14 | 2,6 × 10 16 | 8,3 × 10 17 | 2,6 × 10 18 | 1,4 × 10 19 | 2,2 × 10 19 | 3,1 × 10 19 |
256 | 1,2 × 10 77 | 4.8 × 10 29 | 1.5 × 10 31 | 4.8 × 10 32 | 1,5 × 10 34 | 4.8 × 10 35 | 1.5 × 10 37 | 4.8 × 10 37 | 2,6 × 10 38 | 4,0 × 10 38 | 5,7 × 10 38 |
384 | 3,9 × 10115 | 8,9 × 10 48 | 2,8 × 10 50 | 8,9 × 10 51 | 2,8 × 10 53 | 8,9 × 10 54 | 2,8 × 10 56 | 8,9 × 10 56 | 4.8 × 10 57 | 7,4 × 10 57 | 1.0 × 10 58 |
512 | 1,3 × 10154 | 1,6 × 10 68 | 5,2 × 10 69 | 1,6 × 10 71 | 5,2 × 10 72 | 1,6 × 10 74 | 5,2 × 10 75 | 1,6 × 10 76 | 8.8 × 10 76 | 1,4 × 10 77 | 1.9 × 10 77 |
Fonksiyonun görüntüleri eşit olmayan bir şekilde dağıtılırsa, bir çarpışmanın daha da hızlı bulunabileceğini görmek kolaydır. Bir karma işlevin "görüntü dağılımı" kavramı, işlevin doğum günü saldırılarına karşı direncini doğrudan etkiler. Bu zayıflık, MD ve SHA gibi popüler karmaları savunmasız hale getirir.
Denklemindeki alt ifade , anlam kaybı nedeniyle doğrudan bir programlama diline çevrildiğinde (en) küçük değerler için doğru hesaplanmaz . Örneğin mevcut olduğunda , bunun yerine eşdeğer ifade kullanılmalıdır. Aksi takdirde, tablonun ilk sütunu sıfırlarla doldurulur ve ikinci sütundaki birçok öğenin geçerli anlamlı basamakları yoktur. log(1/(1-p)) log1p-log1p(-p)
İşte Python'da yukarıdaki diziyi daha doğru bir şekilde oluşturabilen bir işlev :
def birthday(probability_exponent, bits): from math import log1p, sqrt probability = 10. ** probability_exponent outputs = 2. ** bits return sqrt(2. * outputs * -log1p(-probability))Kod, adlandırılmış bir dosyaya kaydedilirse , aşağıdaki örnekte olduğu gibi anniversaire.pybir terminalde başlatılabilir :
$ python -i anniversaire.py >>> birthday(-15, 128) 824963474247.1193 >>> birthday(-6, 32) 92.68192319417072İyi bir genel kural için kullanılabilir zihinsel hesaplamak ilişkisi ayrıca yazılabilir . 0,5'ten küçük veya ona eşit olasılıklar için iyi çalışır.
Bu yaklaşım şemasının, üslerle çalışırken kullanımı özellikle kolaydır. Örneğin, 32 bitlik karmalar ( ) oluşturduğunuzu ve çarpışma olasılığının en fazla milyonda bir ( ) olmasını istediğinizi varsayalım . Bu çarpışma riski için en fazla sahip olmanın mümkün olduğu hash sayısını hesaplamak için, 93 olan kesin cevaba yakındır.
Dijital imzalar bir doğum günü saldırıya karşı savunmasız olabilir. Bir ileti normalde ilk hesaplamada tarafından imzalanmış , bir olan kriptografik hash fonksiyonu ve daha sonra imzalamak için gizli bir anahtar kullanarak . Diyelim ki Mallory hileli bir sözleşme imzalayarak Bob'u dolandırmak istiyor . Mallory adil ve hileli bir sözleşme hazırlar . Ardından , sözleşmenin anlamının değişip değişmediği bir dizi kelime buluyor , örneğin eklemek için gereksiz bir virgül, boş bir satır, iki yerine bir boşluk karakteri, kelimeleri eşanlamlılarla değiştirme, vb. Bu değişiklikleri birleştirerek, sözleşmenin birçok farklı versiyonunu ve tüm sözleşmeyi onaylayan sayıyı oluşturabilir.
Aynı şekilde, Mallory dolandırıcılık sözleşmesinin çok sayıda farklı versiyonunu da oluşturur . Ardından, aynı hash değerine sahip iki sözleşme bulmak için tüm bu farklı sürümlere hash işlevini uygular . Bob'a imzalaması için adil sözleşmenin versiyonunu gösterir. Sözleşme imzalandıktan sonra, Mallory imzayı alır ve hileli sözleşmeyi ona ekler. İmza, Bob'un hileli sözleşmeyi imzaladığının "kanıtı".
Mallory, aynı hash ile iki adil sözleşme veya iki hileli sözleşme bularak hiçbir şey kazanmadığı için, olasılıklar orijinal doğum günleri probleminden biraz farklıdır. Mallory'nin stratejisi, adil bir sözleşme ve hileli bir sözleşme çiftleri oluşturmaktır. Doğum günü problemi denklemleri , çiftlerin sayısı olduğunda geçerlidir . Mallory'nin gerçekte ürettiği karma tabloların sayısı .
Bu saldırıdan kaçınmak için, bir imza şeması için kullanılan hash işlevinin uzunluğu, doğum günlerindeki saldırının matematiksel olarak imkansız hale gelmesine yetecek kadar büyük olacak şekilde seçilmelidir; normal bir kaba kuvveti önlemek için yaklaşık iki kat daha fazla bit. saldırı .
Logaritma Pollard rho algoritması hesaplamak için bir doğum günü saldırısı kullanarak bir örnektir logaritma gizli .