Doğumgünü akını - Doğumgünü akını nedir? Doğumgünü akını Hakkında Bilgiler

[SoruCevap]

Doğumgünü akını - Doğumgünü akını nedir? Doğumgünü akını Hakkında Bilgiler

Vikipedi, özgür ansiklopedi


Git ve: kullan, ara
Doğumgünü akını, olasılık kuramındaki doğumgünü probleminin ardındaki matematiği kullanan bir kriptografik akındır. Akının amacı bir f işlevine girdi olarak verilen x1 ve x2'nin f(x1) = f(x2) koşulunu sağlamasıdır. Böyle bir x1,x2 ikilisi çakışma olarak adlandırılmaktadır. Çakışma bulma yöntemi, f işlevini gelişigüzel girdilerle hesaplayıp çakışma koşulunun sağlanıp sağlanmadığını incelemektir. Bu yöntem, yukarıda sözü edilen doğumgünü probleminden yararlanır. Şöyle ki; bir f(x) işlevi eşit olasılıklı H farklı sonuç üretiyorsa ve H yeterince büyükse f(x1) = f(x2) koşulunu sağlayan x1 ve x2 değerleri kolayca bulunabilir.

Matematiksel ifadesi


Bir H kümesinden gelişigüzel n değerlerini seçtiğimizi varsayalım. p(n;H) ifadesini de bir n değerinin birden çok kez seçilmesi olasılığı olarak tanımlayalım. Böylece,
eşitliğine ulaşılabilir.
n(p;H), seçilebilecek en küçük sayıyı gösteriyorsa bir çakışmanın meydana gelme olasılığı en az p'ye eşittir. Yukarıdaki eşitlik tersine çevrildiğinde aşağıdaki eşitliğe ulaşılır.

0.5'lik bir çakışma olasılığı temel alındığında
ifadesine ulaşılır.
Q(H)'nin ilk çakışma bulununcaya dek seçilen değer sayısını belirttiğini varsayalım. Bu sayı,
değerine yakınsar.
Örneğin, 64 bitlik bir öz kullanıldığında ortaya çıkan farklı sonuç sayısı yaklaşık 1.8 × 1019'dur. Tüm bu sonuçların gözlenme olasılıkları birbirine eşitse bir çakışmanın meydana gelmesi için en çok 5.1 × 109 denemeye gerek duyulacaktır. Bu değer, doğumgünü sınırı olarak adlandırılır. Bu değer, n bitlik kodlar için 2n / 2 olarak hesaplanmıştır.[1] Diğer örnekler ise aşağıdaki tabloda gösterilmiştir.
Bit sayısıOlası
sonuç sayısı
Gelişigüzel çakışma olasılığı (p)10−1810−1510−1210−910−60.1%1%25%50%75%324.3 × 1092222.9932.9 × 1039.3 × 1035.0 × 1047.7 × 1041.1 × 105641.8 × 10196.11.9 × 1026.1 × 1031.9 × 1056.1 × 1061.9 × 1086.1 × 1083.3 × 1095.1 × 1097.2 × 1091283.4 × 10382.6 × 10108.2 × 10112.6 × 10138.2 × 10142.6 × 10168.3 × 10172.6 × 10181.4 × 10192.2 × 10193.1 × 10192561.2 × 10774.8 × 10291.5 × 10314.8 × 10321.5 × 10344.8 × 10351.5 × 10374.8 × 10372.6 × 10384.0 × 10385.7 × 10383843.9 × 101158.9 × 10482.8 × 10508.9 × 10512.8 × 10538.9 × 10542.8 × 10568.9 × 10564.8 × 10577.4 × 10571.0 × 10585121.3 × 101541.6 × 10685.2 × 10691.6 × 10715.2 × 10721.6 × 10745.2 × 10751.6 × 10768.8 × 10761.4 × 10771.9 × 1077
Tablo, tüm öz değerlerinin oluşma olasılıklarının eşit olduğu durumda gerekli olan değer sayılarını göstermektedir.
İşlev çıktılarının farklı yoğunlukta dağıldığı durumların çakışma olasılığını artırdığı kolayca gözlenebilmektedir. Bir öz işlevinin 'dengesi' o işlevin doğumgünü akınlarına karşı direncini ifade etmekte, MD ve SHA gibi popüler özlerin zayıf noktalarının aydınlatılması çalışmalarını tetiklemektedir (Bellare ve Kohno, 2004).




Sayısal imzaların akına karşı duyarlığı


Sayısal imzalar, doğumgünü akınına duyarlı olabilmektedirler. Bir m iletisi önce f(m) ile imlenmektedir. Burada f bir kriptografik öz işlevini göstermektedir. Alice'in Bob'u kandırmaya çalıştığını varsayalım. Alice önce yasal bir m sözleşmesi hazırlar ve ardından sahte bir m' sözleşmesini imzalar. Alice daha sonra m üzerinde bazı yazım değişiklikleri yaparak birden fazla m sözleşmesi elde etmeye çalışır.
Alice, sahte m' sözleşmesini de aynı yolla çoğaltır ve öz işlevini yasal ve sahte sözleşmeler üzerine uygulayarak f(m) = f(m') koşulunun sağlandığı ilk değeri bulur. Yasal sözleşmeyi Bob'a imzalatan Alice, bu imzayı sahte sözleşmeye ekler. Böylece, Bob'un sahte sözleşmeye imza koyduğu "kanıtlanmış" olur.
Bu akının önüne geçebilmek amacıyla imzayı oluşturan öz işlevinin çıktı uzunluğu artırılmaktadır. Çalışma süresi katbekat artan bu akın böylece uygulanamaz hale dönüşmektedir.
Pollard'ın rho algoritması, ayrık logaritmaların hesaplanmasında doğumgünü akınını kullanan bir yöntemdir.

Kaynakça


İngilizce Vikipedi'deki 20.02.2009 tarihli Birthday attack maddesi
Mihir Bellare, Tadayoshi Kohno: Öz İşlevinin Dengesi ve Doğumgünü Akınları Üzerindeki Etkisi. EUROCRYPT 2004: s. 401–418
Uygulamalı Kriptografi, 2. baskı, Bruce Schneier
CISSP Hepsi İçinde Çalışma Kılavuzu, 4. baskı, Shon Harris

 

[Editör]

Doğumgünü akını, olasılık kuramındaki doğumgünü problemi matematiğini kullanarak yapılan bir kriptografik saldırıdır. Bu akının temel amacı, bir fonksiyona girdi olarak verilen x1 ve x2'nin f(x1) = f(x2) koşulunu sağlamasını sağlamaktır. Bu durumda x1 ve x2 ikilisi "çakışma" olarak adlandırılır. Çakışma bulma yöntemi, rastgele girdilerle f fonksiyonunu hesaplayarak çakışma koşulunun sağlanıp sağlanmadığını kontrol etmeye dayanır.

Bu akın, doğumgünü probleminden esinlenmiştir. Bir f(x) fonksiyonu eşit olasılıklı H farklı sonuç üretiyorsa ve H yeterince büyükse f(x1) = f(x2) koşulunu sağlayan x1 ve x2 değerleri kolayca bulunabilir.

Doğumgünü sınırı olarak adlandırılan bir değer, n bitlik kodlar için 2^n / 2 olarak hesaplanmıştır. Bu değer, çakışmanın meydana gelme olasılığının en az %50 olduğu noktayı temsil eder. Örneğin, bir 64 bitlik öz kullanıldığında, tüm sonuçların eşit olasılığa sahip olduğu durumda bir çakışmanın meydana gelmesi için en fazla 5.1 x 10^9 deneme gerekecektir.

Doğumgünü akını, matematiksel ifadelerle de gösterilebilir ve sayısal imzalar üzerinde de etkili olabilir. Bu nedenle, kriptografik sistemlerin doğumgünü akınlarına karşı direncini artırmak için uygun önlemler alınmalıdır.

Kaynaklar:
- İngilizce Vikipedi'nin "Birthday attack" maddesi
- Mihir Bellare, Tadayoshi Kohno: Öz İşlevinin Dengesi ve Doğumgünü Akınları Üzerindeki Etkisi. EUROCRYPT 2004
- Uygulamalı Kriptografi, 2. baskı, Bruce Schneier
- CISSP Hepsi İçinde Çalışma Kılavuzu, 4. baskı, Shon Harris

 

[Editör]

Doğumgünü akını, olasılık kuramındaki doğumgünü problemine dayanan bir kriptografik saldırı türüdür. Bu saldırı türünde, belirli bir fonksiyona girdi olarak sunulan x1 ve x2 değerleri için f(x1) = f(x2) eşitliğini sağlayacak x1 ve x2 çiftlerini bulmayı amaçlar. Bu duruma çakışma denir.

Doğumgünü akını saldırısı genellikle f fonksiyonunu rastgele girdilerle hesaplayarak çakışma koşulunu kontrol etmek suretiyle gerçekleştirilir. Bu saldırı tipinde doğumgünü probleminden yararlanılır. Eğer bir f(x) fonksiyonu eşit olasılıklı H farklı sonuç üretiyorsa ve H yeterince büyükse, f(x1) = f(x2) koşulunu sağlayan x1 ve x2 değerlerini kolayca bulmak mümkündür.

Matematiksel olarak, H kümesinden rastgele n değer seçildiğinde aynı değerin birden fazla kez seçilme olasılığı p(n;H) ise, çakışmanın gerçekleşme olasılığı en az p'ye eşittir. Saldırının etkinliği açısından bu tür olasılıklar hesaplanarak saldırının başarımı değerlendirilir.

Doğumgünü akınına karşı duyarlılığı olan bir başka kriptografik öğe de sayısal imzalardır. Bir mesaj önce belirli bir kriptografik öz işlevi f(m) ile imzalanır. Bununla birlikte, doğumgünü akını saldırısı ile, sahte bir mesaj oluşturularak mevcut imzanın kullanılmasıyla güvenlik açıkları oluşturulabilir. Bu tip saldırılara karşı önlem almak için imzalama işlemi sırasında öz işlevinin çıktı uzunluğunun artırılması gibi önlemler alınabilir.

Doğumgünü akınları, özellikle kriptografi alanında önemli bir konudur ve bazı kriptografik işlemlerin güvenliğini değerlendirmek için kullanılır. Bu tür saldırılarla mücadele etmek ve güvenliği artırmak için sürekli olarak yeni teknikler ve yöntemler geliştirilmektedir.