Karma Fonksiyonları

Önceki ders karmanın kökünü tek cümleyle geçmişti: iki farklı girdi aynı çıktıyı vermez. Bu cümle olduğu gibi doğru olamaz. Karmanın çıktısı sabit uzunluktadır, olası girdi sayısı ise sınırsızdır; dolayısıyla aynı çıktıyı veren farklı girdiler kesinlikle vardır ve sayıları da sınırsızdır. Kök, çakışmanın var olmaması değil, bulunamamasıdır.

“Bulunamaz” ise bir sayıdır. Bu ders o sayıyı ölçer: bir çıktı kaç bit olduğunda ilk çakışma kaç denemede ortaya çıkar, ölçülen değer kuramsal sınırla ne kadar örtüşür ve çıktı uzunluğu iki katına çıktığında aranan deneme sayısı ne olur.

Dört Özellik, İki Ayrı Direnç

KT5: karmanın çıktı uzayı sonlu, girdi uzayı sınırsızdır; aynı çıktıyı veren farklı girdiler kesinlikle vardır. Kök, çakışmanın yokluğu değil, arama maliyetinin karşılanamaz olmasıdır.

KT6: n bitlik bir çıktıda çakışma arama maliyeti 2^(n/2) ile üst sınırlıdır ve bu sınır algoritmanın iç tasarımından bağımsızdır; yalnızca çıktı uzunluğundan gelir.

İki direnç birbirinden ayrılır. Ön görüntü direnci (preimage resistance) verilen bir çıktıyı üreten herhangi bir girdiyi bulmayı zorlaştırır; maliyeti 2^n mertebesindedir. Çakışma direnci (collision resistance) aynı çıktıyı veren herhangi iki girdiyi bulmayı zorlaştırır ve maliyeti 2^(n/2)’dir. Aradaki fark, saldıran tarafın çıktıyı seçme özgürlüğünden gelir: ilkinde hedef sabittir, ikincisinde iki girdi de serbesttir. Bu özgürlük maliyetin karekökünü alır.

// karma/ozellik.mjs — karmanin dort ozelligi olculur: sabit uzunluk, belirlenimcilik,
// cig etkisi ve cikti uzunlugunun getirdigi kuramsal sinir. Girdi, kurgu bolgesel olcum
// aginda bir sayac okumasidir. Rastgelelik yok; her kosum ayni sayilari verir.
import { createHash } from "node:crypto";

// KT5: karmanin cikti uzayi sonlu, girdi uzayi sinirsizdir; ayni ciktiyi veren farkli
//      girdiler kesinlikle vardir. Kok, cakismanin yoklugu degil bulunamamasidir.
// KT6: n bitlik ciktida cakisma arama maliyeti 2^(n/2) ile ust sinirlidir; bu sinir
//      algoritmanin ic tasariminden bagimsizdir, yalnizca cikti uzunlugundan gelir.

const OKUMA = "SAY-4417|2026-03-01T06:00Z|41982";
const ALG = ["md5", "sha1", "sha256", "sha512"];
const bitSay = (b) => { let n = 0; for (const x of b) n += (x.toString(2).match(/1/g) || []).length; return n; };
const yaz = (g, ...s) => console.log(s.map((v, i) =>
  (g[i] < 0 ? String(v).padEnd(-g[i]) : String(v).padStart(g[i]))).join(""));

const A = [-10, 7, 11, 12, 12];
yaz(A, "algoritma", "bayt", "cikti bit", "onceruntu", "cakisma");
for (const a of ALG) {
  const n = createHash(a).update(OKUMA).digest().length * 8;
  yaz(A, a, n / 8, n, "2^" + n, "2^" + n / 2);
}

console.log("\ncig etkisi: girdinin tek biti ceviriliyor, ciktida kac bit degisiyor");
const B = [-10, 10, 8, 10, 8, 10];
yaz(B, "algoritma", "cevrilen", "en az", "ortalama", "en cok", "beklenen");
for (const a of ALG) {
  const ozgun = createHash(a).update(OKUMA).digest();
  const bit = ozgun.length * 8;
  let en = Infinity, ust = 0, t = 0, kez = 0;
  for (let i = 0; i < OKUMA.length * 8; i++) {
    const g = Buffer.from(OKUMA); g[i >> 3] ^= 1 << (i & 7);
    const y = createHash(a).update(g).digest();
    let f = 0;
    for (let j = 0; j < y.length; j++) f += bitSay(Buffer.from([ozgun[j] ^ y[j]]));
    en = Math.min(en, f); ust = Math.max(ust, f); t += f; kez++;
  }
  yaz(B, a, kez, en, (t / kez).toFixed(1), ust, bit / 2);
}

console.log("\nayni girdi ayni ciktiyi veriyor mu:",
  createHash("sha256").update(OKUMA).digest("hex") ===
  createHash("sha256").update(OKUMA).digest("hex") ? "evet" : "hayir");

algoritma    bayt  cikti bit   onceruntu     cakisma
md5            16        128       2^128        2^64
sha1           20        160       2^160        2^80
sha256         32        256       2^256       2^128
sha512         64        512       2^512       2^256

cig etkisi: girdinin tek biti ceviriliyor, ciktida kac bit degisiyor
algoritma   cevrilen   en az  ortalama  en cok  beklenen
md5              256      50      64.1      78        64
sha1             256      62      79.7     100        80
sha256           256     110     128.8     149       128
sha512           256     219     256.4     288       256

ayni girdi ayni ciktiyi veriyor mu: evet

Çığ etkisi tablosu, karmanın girdi ile çıktı arasında hiçbir yapısal iz bırakmadığını ölçer. Girdinin tek bir biti çevrildiğinde SHA-256 çıktısının ortalama 128,8 biti değişiyor — 256 bitin yaklaşık yarısı. En düşük ölçüm 110, en yüksek 149; dört algoritmanın dördünde de ortalama, çıktı bitinin yarısına oturuyor. Yarım oran, çıktının girdiden bağımsız gibi davrandığının işaretidir. Kodlamada bir bitlik girdi değişikliği çıktının yalnız o bölgesine dokunurdu; burada değişimin yeri de miktarı da girdiyle ilişkisizdir.

Belirlenimcilik ile çığ etkisi birlikte, karmayı bir parmak izi hâline getiren şeydir. Belirlenimcilik olmasaydı aynı verinin iki özeti karşılaştırılamazdı; çığ etkisi olmasaydı benzer veriler benzer özetler üretir ve özete bakan taraf verinin bir bölümünü çıkarabilirdi. İkisi bir arada, “aynı mı” sorusunun verinin kendisi elde tutulmadan yanıtlanmasını sağlar.

Sağdaki iki sütun ise bu dersin asıl konusudur. Her algoritmanın çakışma sınırı, ön görüntü sınırının karekökü kadardır: 128 bitlik çıktı 2^64’e, 160 bitlik çıktı 2^80’e, 256 bitlik çıktı 2^128’e sınırlanır. Bu sayı algoritmanın kalitesiyle ilgili değildir — çıktı uzunluğunun kendisiyle ilgilidir ve kusursuz bir karma fonksiyonunda da aynıdır.

Doğum Günü Sınırı Ölçülüyor

Kuramsal sınır, ölçülebilir bir iddiadır. Aşağıdaki birim SHA-256 çıktısının yalnız ilk n bitini alır ve kendi kısalttığı bu çıktı üzerinde ilk çakışmayı arar. Ölçülen şey algoritma değildir; çıktı uzunluğunun getirdiği sınırdır. Her çıktı boyu için otuz iki bağımsız tur koşturulur ve ortalama alınır, çünkü tek bir turun sonucu geniş bir bantta salınır.

// karma/cakisma.mjs — cakisma direncinin dogum gunu siniriyla olculmesi. SHA-256
// ciktisinin ilk n biti alinir ve kendi kisalttigimiz bu cikti uzerinde ilk cakisma
// aranir. Olculen sey algoritmanin kendisi degil, cikti uzunlugunun getirdigi sinirdir.
// Girdiler sayacla uretilir; rastgelelik yok, her kosum ayni sayilari verir.
import { createHash } from "node:crypto";

// KT7: n bitlik ciktida ilk cakismaya kadar beklenen deneme sayisi 1,2533 * 2^(n/2)'dir;
//      cikti uzunlugu iki katina cikinca beklenen deneme sayisi karesi kadar buyur.

const kes = (m, bit) => {                      // SHA-256 ciktisinin ilk `bit` biti
  const h = createHash("sha256").update(m).digest();
  let v = 0n;
  for (let i = 0; i < 8; i++) v = (v << 8n) | BigInt(h[i]);
  return (v >> BigInt(64 - bit)).toString(16);
};
const ilkCakisma = (bit, tur) => {             // `tur` her turda farkli girdi dizisi verir
  const gorulen = new Map();
  for (let i = 0; ; i++) {
    const m = `t${tur}-olcum-${i}`, k = kes(m, bit);
    if (gorulen.has(k)) return i + 1;
    gorulen.set(k, m);
  }
};
const TUR = 32;                                // her cikti boyu icin bagimsiz tur sayisi
const yaz = (g, ...s) => console.log(s.map((v, i) =>
  (g[i] < 0 ? String(v).padEnd(-g[i]) : String(v).padStart(g[i]))).join(""));
const G = [7, 17, 11, 11, 8, 10, 10];
yaz(G, "cikti", "olasi cikti", "kuramsal", "olculen", "oran", "en erken", "en gec");
for (const bit of [8, 12, 16, 20, 24, 28, 32]) {
  let toplam = 0, en = Infinity, ust = 0;
  for (let j = 0; j < TUR; j++) {
    const d = ilkCakisma(bit, j);
    toplam += d; en = Math.min(en, d); ust = Math.max(ust, d);
  }
  const ort = toplam / TUR, kuram = 1.2533 * 2 ** (bit / 2);
  yaz(G, bit + " bit", (2 ** bit).toLocaleString("tr-TR"), kuram.toFixed(0),
      ort.toFixed(0), (ort / kuram).toFixed(2), en, ust);
}

  cikti      olasi cikti   kuramsal    olculen    oran  en erken    en gec
  8 bit              256         20         21    1.03         7        48
 12 bit            4.096         80         92    1.15        28       188
 16 bit           65.536        321        368    1.15        91       675
 20 bit        1.048.576       1283       1397    1.09       127      3395
 24 bit       16.777.216       5134       4986    0.97      1630     11910
 28 bit      268.435.456      20534      21479    1.05      2771     48277
 32 bit    4.294.967.296      82136      86497    1.05     10808    167350

Yedi satırın yedisinde ölçülen değer kuramsal sınırın 0,97 ile 1,15 katı arasında kalıyor. Bu, formülün bir yaklaşıklık değil ölçülebilir bir tahmin olduğunun kanıtıdır. Kısaltılmış çıktı gerçek bir kırma girişimi değildir; SHA-256 çıktısının atılan bitleri hesaplanmaya devam eder ve arama yalnız elde tutulan n bit üzerinde yürür. Ölçülen şey, o n bitin taşıdığı sınırdır.

Asıl sonuç ikinci ve dördüncü sütunun karşılaştırılmasındadır. 32 bitlik çıktının dört milyarı aşkın olası değeri var; ilk çakışma ortalama 86.497 denemede bulunuyor. Oran yaklaşık kırk bine birdir. Sezgi burada yanılır: uzay büyüdükçe çakışma zorlaşıyor gibi görünür, oysa aranan şey belirli bir değere düşmek değil, herhangi iki denemenin birbirine düşmesidir ve deneme sayısı arttıkça çift sayısı karesel büyür.

Bu kareselliği tablodaki sayılarla doğrulamak mümkündür. 86.497 denemede birbiriyle karşılaştırılabilecek çift sayısı 86.497 × 86.496 / 2, yani yaklaşık 3,74 milyardır; 32 bitlik çıktı uzayı ise 4,29 milyar değer taşır. İki sayının aynı mertebeye gelmesi çakışmanın beklendiği andır. Aranan şey deneme sayısının çıktı uzayına yaklaşması değil, çift sayısının yaklaşmasıdır ve çift sayısı deneme sayısının karesiyle büyür. Doğum günü sınırının tamamı bu tek gözlemden çıkar.

Son iki sütun bandın genişliğini gösterir. 32 bit için en erken çakışma 10.808. denemede, en geç 167.350. denemede bulundu — on beş kat fark. Ortalama kuramla örtüşse de tek bir koşum örtüşmez. Bu, güvenlik sınırlarının neden ortalamayla değil en erken durumla yazıldığının nedenidir: bir savunma, koşumların yarısında değil hepsinde tutmak zorundadır.

Satırdan satıra geçiş de sayılabilir. Çıktı 16 bitten 32 bite çıktığında olası çıktı sayısı 65.536’dan dört milyarın üzerine, yani karesine gider; ölçülen deneme sayısı ise 368’den 86.497’ye, yaklaşık aynı oranda çıkar. Çıktıya eklenen her bit aranan deneme sayısını yalnız 1,41 katına çıkarır. Sekiz bit eklemek onaltı kat, altmış dört bit eklemek dört milyar kat getirir. Kök buradadır: çakışma direnci, çıktı uzunluğunun yarısı kadar bit güvenlik verir ve bu oran hiçbir tasarımla değiştirilemez.

Kısaltmanın Bedeli

Yukarıdaki ölçüm, kursun güvenlik kuralı gereği gerçek bir algoritmaya karşı değil kendi kısalttığımız çıktı üzerinde yapıldı. Bu kısaltma yalnız bir ölçüm hilesi değildir; kurulumda gerçekten karşılaşılan bir karardır. Bir kütük satırında ya da bir veritabanı sütununda yer kazanmak için özetin tamamı değil ilk birkaç baytı saklanır ve bu, çoğu zaman yalnız bir depolama tercihi sanılır.

Sayı bunun bir depolama tercihi olmadığını gösterir. 256 bitlik bir çıktının ilk 64 biti saklanırsa çakışma sınırı 2^128’den 2^32’ye iner. Tablonun son satırında ölçülen tam olarak budur: 32 bitlik çıktıda ilk çakışma ortalama 86.497 denemede bulundu. 64 bitlik çıktıda aynı formül yaklaşık 5,4 milyar deneme verir — büyük bir sayı gibi görünür, ama sıradan bir makinenin saatler mertebesinde yapabileceği bir iştir. Kısaltmanın maliyeti doğrusal değildir: çıktının yarısını atmak, güvenliğin yarısını değil karekökünü bırakır.

Kısaltma her kullanımda aynı sonucu doğurmaz. Kütükteki bir eşleştirme alanı için 64 bit yeterli olabilir, çünkü orada aranan şey aynı özeti veren iki kayıt değil, belirli bir kaydın izlenmesidir. Bütünlük denetiminde ise aynı kısaltma doğrudan kökü kırar. Ölçüt tek cümleyle yazılır: alanın taşıdığı iddia çakışma direncine dayanıyorsa çıktı kısaltılmaz.

Hangi Kullanım Hangi Dirence Bağlı

Kırılan bir kökün bedeli, o köke bağlı kalem sayısıdır. Kurgu bölgesel ölçüm ağında karma beş ayrı yerde kullanılıyor ve beşi aynı dirence dayanmıyor.

Kullanım	Dayandığı direnç	Kalem	Çakışma direnci düşerse
Aygıt yazılımı bütünlük özeti	çakışma	12.400	düşer
Kütükteki seri numarası özeti	ön görüntü	12.400	ayakta
Şubeler arası imzalanan özet	çakışma	6	düşer
Saha ekibi parola kaydı	ön görüntü	340	ayakta
Yedek dosya parmak izi	çakışma	96	düşer

Yirmi beş bin iki yüz kırk altı kalemin 12.502’si çakışma direncine, 12.740’ı ön görüntü direncine bağlıdır. Ayrım keskindir: çakışma direnci düştüğünde, aynı özeti veren iki farklı aygıt yazılımı üretilebilir hâle gelir ve bütünlük denetimi ikisini de kabul eder. Parola kaydında ise saldıran tarafın elinde hedef bir çıktı vardır ve ona düşen bir girdi araması gerekir; bu ön görüntü sorunudur ve çakışma direncinin düşmesi onu kolaylaştırmaz.

MD5 ve SHA-1 bu ayrımın somut örneğidir. İkisi de açık şartnamedir, ikisi de hâlâ hesaplanabilir ve ikisinin de ön görüntü direnci kırılmış değildir. Kullanımdan kaldırılmalarının nedeni çakışma tarafındadır: 2^64 ve 2^80’lik sınırlar erişilebilir mertebeye indi ve yapısal zayıflıklar bu sınırların da altına inilmesine yol açtı. Sonuç, tablodaki iki sütunun ayrı ayrı etkilenmesidir — bu algoritmalarla üretilmiş bir parola kaydı ile bir bütünlük özeti aynı aciliyette değildir.

Yenilemenin bedeli üçüncü sütundur ve kalem kalem sayılır. Aygıt yazılımı özetleri için yenileme tek bir toplu işlemdir: 12.400 özet yeniden hesaplanır ve elle dokunulan kalem sayısı sıfırdır. Yedek dosya parmak izlerinde durum farklıdır — 96 yedeğin özgün özeti eski kayıtlarda durur ve yenisiyle eşleştirilmesi elle yapılır. Şubeler arası imzalanan özette ise yalnız özet değil imza da yenilenir; altı şube için altı ayrı onay adımı gerekir ve yenileme penceresinde aktarımların doğrulaması yapılamaz. Aynı kök kırılmasının bedeli üç kullanımda sıfır, 96 ve 6 elle kalemdir; kalem sayısını belirleyen şey kaç kaydın etkilendiği değil, kaç kaydın yenilenmesi için insan kararı gerektiğidir.

Özet

• Karmanın çıktı uzayı sonlu olduğu için çakışma kesinlikle vardır; güven kökü çakışmanın yokluğu değil, arama maliyetinin karşılanamaz olmasıdır.
• Girdinin tek biti çevrildiğinde çıktı bitlerinin yaklaşık yarısı değişir: SHA-256 için ölçülen ortalama 256 bitte 128,8’dir.
• n bitlik çıktıda ilk çakışmaya kadar beklenen deneme sayısı 2^(n/2) mertebesindedir; yedi ayrı çıktı boyunda ölçülen değer kuramsal sınırın 0,97–1,15 katı çıkmıştır.
• Ortalama kuramla örtüşse de tek koşum örtüşmez: 32 bitte en erken çakışma 10.808, en geç 167.350 denemededir; güvenlik sınırı en erken duruma göre yazılır.
• Çakışma direnci çıktı uzunluğunun yarısı kadar bit güvenlik verir; kurgu ağdaki 25.246 kalemin 12.502’si bu dirence, 12.740’ı ön görüntü direncine bağlıdır.

Sonraki Adım

Bu derste ölçülen maliyet, saldıran tarafın hiçbir bilgisi olmadığı varsayımına dayanıyordu: girdiler sayaçla üretildi ve her deneme eşit olasılıklıydı. Parola söz konusu olduğunda bu varsayım düşer. İnsanların seçtiği dizgiler olası girdi uzayına eşit dağılmaz; birkaç yüz milyonluk bir aday listesi, uzayın hesaplanabilir bir bölümünü kaplar. O durumda 2^256’lık ön görüntü sınırının hiçbir hükmü kalmaz, çünkü arama uzayın tamamında değil listenin içinde yapılır. Sonraki ders bu duruma karşı iki ayrı savunmayı ölçer: her denemenin birim maliyetini büyüten iş çarpanı ve ön hesaplanmış tabloyu kayıt sayısıyla çarpan tuz. İkisinin de kendi sınırı vardır ve o sınır sayılabilir.