Birbitdeğişir,yarısıdevrilir

İyi bir özet fonksiyonundan ne bekleriz?#

Kriptografik bir özet fonksiyonu $H$, keyfi uzunluktaki bir girdiyi sabit uzunlukta bir çıktıya eşler. SHA-256 için bu çıktı 256 bittir. Üç direnç özelliği isteriz:

• Ön-görüntü direnci: bir $h$ verildiğinde $H(x) = h$ olan bir $x$ bulmak zor olmalı.
• İkinci ön-görüntü direnci: bir $x$ verildiğinde $H(x') = H(x)$ olan başka bir $x'$ bulmak zor olmalı.
• Çakışma direnci: $H(x) = H(x')$ olan herhangi bir $x \neq x'$ çifti bulmak zor olmalı.

Bu özelliklerin görünür yüzü çığ etkisidir. Katı çığ ölçütüne göre girdideki tek bir bit değiştiğinde çıktıdaki her bit 1/2 olasılıkla çevrilmelidir. Yani ortalama 128 bit devrilir ve devrilen bit sayısı yaklaşık $\mathcal{B}(256,\ 1/2)$ dağılımına uyar: ortalama 128, standart sapma 8.

İçeride ne oluyor?#

SHA-256, mesajı 512 bitlik bloklara böler ve her bloğu 64 turluk bir sıkıştırma fonksiyonundan geçirir (Merkle–Damgård yapısı). Her turda sekiz adet 32 bitlik çalışma değişkeni döndürme, XOR, çoğunluk ve seçim fonksiyonlarıyla karıştırılır:

const rotr = (x: number, n: number) => (x >>> n) | (x << (32 - n));
 
const S1 = rotr(e, 6) ^ rotr(e, 11) ^ rotr(e, 25);
const ch = (e & f) ^ (~e & g); // seçim: e bitine göre f ya da g
const t1 = (h + S1 + ch + K[i] + W[i]) | 0;
const S0 = rotr(a, 2) ^ rotr(a, 13) ^ rotr(a, 22);
const maj = (a & b) ^ (a & c) ^ (b & c); // çoğunluk
const t2 = (S0 + maj) | 0;
 
h = g; g = f; f = e; e = (d + t1) | 0;
d = c; c = b; b = a; a = (t1 + t2) | 0;

Doğrusal olmayan ch ve maj fonksiyonları ile farklı döndürme miktarları, tek bir bitlik farkın birkaç tur içinde bütün duruma yayılmasını sağlar. 64 tur, bu yayılmanın defalarca tamamlanması için fazlasıyla yeterlidir.

Doğum günü sınırı#

23 kişilik bir sınıfta iki kişinin aynı gün doğmuş olma olasılığı %50'yi aşar. Aynı hesap özet fonksiyonları için de geçerlidir: $k$ bitlik bir çıktıda ilk çakışmayı bulmak için beklenen deneme sayısı

olur. 16 bitlik kısmi bir çakışma yaklaşık 321 denemede, 32 bitlik bir çakışma yaklaşık 82 000 denemede bulunur. Tam 256 bit için bu sayı $2^{128}$ mertebesindedir: evrendeki bütün bilgisayarlarla bile ulaşılamaz. Deneydeki “kısmi çakışma avı” bu sınırı canlı olarak doğrular.