--- title: 'Karma Fonksiyonları' source: 'https://academia.sh/tr/kurslar/kimlik-ve-kriptografi/karma-fonksiyonlari' course: 'Kimlik, Erişim ve Kriptografi' language: tr updated: '2026-08-17T18:08:36+00:00' license: 'CC BY-SA 4.0' --- # Karma Fonksiyonları Çakışma direncinin doğum günü sınırıyla ölçülmesi: sabit çıktı uzunluğu, tek bitlik girdi değişiminin çıktı bitlerinin yarısını çevirmesi, kısaltılmış çıktıda ilk çakışmanın 32 turluk ortalamada kuramsal sınırın 0,97–1,15 katında bulunması ve n bitlik çıktının 2^(n/2) ile sınırlanmasının 25.246 kalemlik kullanım kümesinde 12.502 kalemi çakışma direncine bağlaması. Ö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. ```js // 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. ```js // 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 bin**e bir**dir. 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.