Doğum günü akını

Doğum günü akını, olasılık kuramındaki doğum günü probleminin ardındaki matematiği kullanan bir kriptografik akındır. Akının amacı bir f işlevine girdi olarak verilen  ve 'nin  koşulunu sağlamasıdır. Böyle bir  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ğum günü probleminden yararlanır. Şöyle ki; bir  işlevi eşit olasılıklı  farklı sonuç üretiyorsa ve  yeterince büyükse  koşulunu sağlayan  ve  değerleri kolayca bulunabilir.

Matematiksel ifadesi 

Bir  kümesinden gelişigüzel  değerlerini seçtiğimizi varsayalım.  ifadesini de bir n değerinin birden çok kez seçilmesi olasılığı olarak tanımlayalım. Böylece,
 eşitliğine ulaşılabilir.

, seçilebilecek en küçük sayıyı gösteriyorsa bir çakışmanın meydana gelme olasılığı en az '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.

'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ğum günü sınırı olarak adlandırılır. Bu değer, n bitlik kodlar için  olarak hesaplanmıştır. Diğer örnekler ise aşağıdaki tabloda gösterilmiştir.
{| class="wikitable" style="white-space:nowrap;"
|-
! rowspan="2" style="background:lightgrey;" | Bit sayısı
! rowspan="2" style="background:lightgrey;" | Olasısonuç sayısı(H)
! colspan="10" style="background:lightgrey;" | Gelişigüzel çakışma olasılığı (p)
|-
! style="background:lightgrey;" | 10−18
! style="background:lightgrey;" | 10−15
! style="background:lightgrey;" | 10−12
! style="background:lightgrey;" | 10−9
! style="background:lightgrey;" | 10−6
! style="background:lightgrey;" | 0.1%
! style="background:lightgrey;" | 1%
! style="background:lightgrey;" | 25%
! style="background:lightgrey;" | 50%
! style="background:lightgrey;" | 75%
|- align="center"
| bgcolor="lightgrey" | 32
| bgcolor="lightgrey" | 4.3 × 109
| 2
| 2
| 2
| 2.9
| 93
| 2.9 × 103
| 9.3 × 103
| 5.0 × 104
| 7.7 × 104
| 1.1 × 105
|- align="center"
| bgcolor="lightgrey" | 64
| bgcolor="lightgrey" | 1.8 × 1019
| 6.1
| 1.9 × 102
| 6.1 × 103
| 1.9 × 105
| 6.1 × 106
| 1.9 × 108
| 6.1 × 108
| 3.3 × 109
| 5.1 × 109
| 7.2 × 109
|- align="center"
| bgcolor="lightgrey" | 128
| bgcolor="lightgrey" | 3.4 × 1038
| 2.6 × 1010
| 8.2 × 1011
| 2.6 × 1013
| 8.2 × 1014
| 2.6 × 1016
| 8.3 × 1017
| 2.6 × 1018
| 1.4 × 1019
| 2.2 × 1019
| 3.1 × 1019
|- align="center"
| bgcolor="lightgrey" | 256
| bgcolor="lightgrey" | 1.2 × 1077
| 4.8 × 1029
| 1.5 × 1031
| 4.8 × 1032
| 1.5 × 1034
| 4.8 × 1035
| 1.5 × 1037
| 4.8 × 1037
| 2.6 × 1038
| 4.0 × 1038
| 5.7 × 1038
|- align="center"
| bgcolor="lightgrey" | 384
| bgcolor="lightgrey" | 3.9 × 10115
| 8.9 × 1048
| 2.8 × 1050
| 8.9 × 1051
| 2.8 × 1053
| 8.9 × 1054
| 2.8 × 1056
| 8.9 × 1056
| 4.8 × 1057
| 7.4 × 1057
| 1.0 × 1058
|- align="center"
| bgcolor="lightgrey" | 512
| bgcolor="lightgrey" | 1.3 × 10154
| 1.6 × 1068
| 5.2 × 1069
| 1.6 × 1071
| 5.2 × 1072
| 1.6 × 1074
| 5.2 × 1075
| 1.6 × 1076
| 8.8 × 1076
| 1.4 × 1077
| 1.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ğum gü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ğum günü akınına duyarlı olabilmektedirler. Bir  iletisi önce  ile imlenmektedir. Burada  bir kriptografik öz işlevini göstermektedir. Alice'in Bob'u kandırmaya çalıştığını varsayalım. Alice önce yasal bir  sözleşmesi hazırlar ve ardından sahte bir  sözleşmesini imzalar. Alice daha sonra  üzerinde bazı yazım değişiklikleri yaparak birden fazla  sözleşmesi elde etmeye çalışır.

Alice, sahte  sözleşmesini de aynı yolla çoğaltır ve öz işlevini yasal ve sahte sözleşmeler üzerine uygulayarak  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ğum günü akınını kullanan bir yöntemdir.

Ayrıca bakınız 
 Ortada buluşma akını

Kaynakça 

 Mihir Bellare, Tadayoshi Kohno: Öz İşlevinin Dengesi ve Doğum Gü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

Notlar

Dış bağlantılar 
 "Sayısal imza ve kimlik doğrulama nedir?"
 Kriptanalitik uygulamalarla koşut çakışma çalışması 

Kriptografik algoritmalar