Tuz ve Parola Saklama

Önceki dersteki bütün ölçümler tek bir varsayıma dayanıyordu: girdiler sayaçla üretiliyordu 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.

Bu derste ölçülen şey, o listenin nasıl pahalılaştırıldığıdır. İki ayrı çarpan vardır ve ikisi farklı şeyi çarpar. Aşağıdaki hesapların tamamı kendi modelimiz üzerindedir; gerçek bir parola kümesine karşı deneme yapmak, yazılı yetki ve tanımlı kapsam olmadan hem yasadışı hem meslek dışıdır.

Neyi Çarpan Çarpan

KT8: anahtar türetme fonksiyonunun iş çarpanı (work factor), tek bir denemenin birim maliyetini doğrusal olarak büyütür. Savunan taraf bu maliyeti giriş başına bir kez öder; deneyen taraf aday sayısı kadar öder. Asimetri buradadır.

KT9: ön hesaplanmış tablo (precomputed table) aynı tuzu paylaşan kayıtların tamamına birden uyar. Tuz kayıt başına ayrı üretilirse aynı tablo yalnızca tek bir kayda uyar.

İkisi çarpanın farklı yerine oturur. İş çarpanı deneme başına maliyeti, tuz ise tekrarlanacak deneme kümesi sayısını büyütür. Biri diğerinin yerine geçmez; birlikte kullanıldıklarında toplam iş ikisinin çarpımıdır. Bu ayrım, iki savunmanın ayrı ayrı ölçülmesini zorunlu kılar: iş çarpanı yükseltilip tuz atlanırsa toplam iş kayıt sayısına bölünür, tuz konulup çarpan düşük bırakılırsa birim maliyet ölçülemeyecek kadar küçük kalır.

Deneme Maliyeti Eğrisi

Aşağıdaki birim iş çarpanının maliyet üzerindeki etkisini ölçer. Ölçüm kalıbı özeldir: ham süre hiçbir yerde yazdırılmaz. Beklenen kat, girdiden — yani seçilen N değerlerinin oranından — türetilir; ölçülen değer yalnızca bir bant denetiminden geçirilir ve sonuç evet ya da hayır olarak yazılır. Bunun nedeni, mutlak sürenin makineye ve çalışma zamanına bağlı olmasıdır; ölçülmek istenen ise makineden bağımsız olan orandır.

// parola/carpan.mjs — is carpani ile deneme maliyeti egrisi. Sure ham olarak
// yazdirilmaz: beklenen kat girdiden (N oraninindan) turetilir, olculen deger yalnizca
// bant denetiminden gecirilip evet/hayir yazilir. Kurgu saha ekibi parolasi kullanilir.
import { scryptSync } from "node:crypto";

// KT8: anahtar turetme fonksiyonunun is carpani, tek bir denemenin birim maliyetini
//      dogrusal olarak buyutur; savunan taraf bu maliyeti bir kez, deneyen taraf aday
//      sayisi kadar oder.

const PAROLA = "kurgu-saha-ekibi-girisi";
const TUZ = Buffer.alloc(16, 3);                 // kurgu, sabit
const TABAN_US = 12;
const ayar = (us) => ({ N: 2 ** us, r: 8, p: 1, maxmem: 512 * 1024 * 1024 });
const olc = (us, kez) => {
  scryptSync(PAROLA, TUZ, 32, ayar(us));                       // isinma
  const t0 = process.hrtime.bigint();
  for (let i = 0; i < kez; i++) scryptSync(PAROLA, TUZ, 32, ayar(us));
  return Number(process.hrtime.bigint() - t0) / kez;
};
const taban = olc(TABAN_US, 8);
const ADAY = 1_000_000;                          // kurgu aday listesi buyuklugu
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 = [8, 9, 11, 13, 22];
console.log(`taban is carpani N=2^${TABAN_US}; birim = taban carpanda tek deneme`);
yaz(G, "N", "bellek", "beklenen", "bant icinde", "aday listesi (birim)");
for (const us of [12, 13, 14, 15, 16]) {
  const beklenen = 2 ** (us - TABAN_US);                       // girdiden turetildi
  const oran = olc(us, us > 14 ? 1 : 3) / taban;               // yalnizca bant denetimi
  const bantta = oran >= beklenen * 0.55 && oran <= beklenen * 1.8 ? "evet" : "hayir";
  yaz(G, "2^" + us, (128 * 8 * 2 ** us / 2 ** 20) + " MiB", beklenen + "x", bantta,
      (ADAY * beklenen).toLocaleString("tr-TR"));
}

taban is carpani N=2^12; birim = taban carpanda tek deneme
       N   bellek   beklenen  bant icinde  aday listesi (birim)
    2^12    4 MiB         1x         evet             1.000.000
    2^13    8 MiB         2x         evet             2.000.000
    2^14   16 MiB         4x         evet             4.000.000
    2^15   32 MiB         8x         evet             8.000.000
    2^16   64 MiB        16x         evet            16.000.000

Beş satırın beşinde ölçülen oran beklenen katın bandı içinde kaldı. Eğri doğrusaldır: N iki katına çıktığında hem birim maliyet hem de bellek tüketimi iki katına çıkar. Son sütun bunun deneyen taraftaki karşılığıdır — bir milyonluk aday listesinin tamamı taban çarpanda bir milyon birim, N=2^16 çarpanında on altı milyon birim tutar.

Asimetri bu tabloda görünmez ama tabloyu okumanın tek yolu odur. Savunan taraf çarpanı on altı katına çıkardığında giriş başına on altı kat öder ve bu, kullanıcının fark etmediği bir gecikmedir. Deneyen taraf aynı kararın bedelini aday başına öder. Bir tarafta günde birkaç bin giriş, öteki tarafta bir milyon aday vardır; aynı çarpan iki tarafta çok farklı toplamlara gider.

Asimetriyi sayıya çevirmek için iki tarafın toplamını yazmak yeterlidir. Kurgu ağda 340 saha hesabı var ve her hesap günde ortalama üç kez giriş yapıyor; bu, günde 1.020 doğrulamadır. N=2^16 çarpanında savunan tarafın günlük toplamı 16.320 birimdir. Deneyen taraf ise tuz nedeniyle listeyi her kayıt için baştan geçmek zorundadır: 340 × 16.000.000, yani 5,44×10^9 birim. İki toplamın oranı üç yüz binin üzerindedir. Çarpanı büyütmenin savunan tarafa maliyeti gündelik ve sabittir; deneyen tarafa maliyeti kayıt sayısıyla çarpılır.

Bellek sütunu ikinci ve ayrı bir kaldıraçtır. N=2^16 için her deneme 64 MiB tutar. Bu miktar tek bir doğrulama yapan sunucu için önemsizdir; çok sayıda denemeyi koşut yürütmek isteyen taraf için belirleyicidir, çünkü koşutluk artık işlem birimi sayısıyla değil bellek miktarıyla sınırlanır. İş çarpanı hesabı yavaşlatır, bellek katsayısı hesabı ucuz donanıma dağıtılamaz kılar.

Tablo Kaç Kalemde İşe Yaramaz Olur

İş çarpanının kapatmadığı bir yol vardır. Aday listesinin karmaları bir kez hesaplanıp saklanırsa, sızmış bir kayıt için yapılacak iş bir arama işlemine iner; hesap zaten yapılmıştır. Tuzun ölçülen etkisi tam olarak buradadır ve etkisi kalem sayısıyla yazılır.

// parola/tuz.mjs — on hesaplanmis tablonun tuz karsisinda kac kalemde ise yaramaz hale
// geldigi ve tuz uzunlugunu neyin belirledigi (model). Kurgu bolgesel olcum aginda 340
// saha ekibi hesabi var. Rastgelelik yok; her kosum ayni sayilari verir.

// KT9: on hesaplanmis tablo, ayni tuzu paylasan kayitlarin tamamina birden uyar; tuz
//      kayit basina ayri uretilirse ayni tablo yalnizca tek bir kayda uyar.
// KT10: tuz uzunlugunu belirleyen sey tablo boyutu degil, tuzlarin kendi aralarinda
//       cakismamasidir; olcut ikinci derste olculen dogum gunu sinirdir.

const ADAY = 1_000_000;                            // kurgu aday listesi
const KAYIT = 340;                                 // kurgu saha ekibi hesabi sayisi
const cift = (n) => (n * (n - 1)) / 2;
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 say = (x) => x === 0 ? "0" : x >= 1e6 ? x.toExponential(2)
  : x >= 1 ? x.toLocaleString("tr-TR", { maximumFractionDigits: 2 })
  : x >= 1e-3 ? x.toFixed(3).replace(".", ",") : x.toExponential(1);

console.log(`aday listesi ${say(ADAY)}, kayit ${KAYIT}, kayit cifti ${say(cift(KAYIT))}`);
const G = [9, 10, 14, 14, 18];
yaz(G, "tuz biti", "ayri tuz", "tablo kalemi", "uydugu kayit", "beklenen cakisma");
for (const bit of [0, 8, 16, 32, 64, 128]) {
  const uzay = 2 ** bit;
  const ayri = Math.min(uzay, KAYIT);              // kullanimda olan ayri tuz sayisi
  yaz(G, bit, say(ayri), say(ADAY * ayri),         // tumunu kapsayan tablo kalemi
      say(Math.max(1, Math.round(KAYIT / uzay))), say(cift(KAYIT) / uzay));
}
const esik = Math.ceil(Math.log2(KAYIT));
console.log(`\ntuz uzayi ${KAYIT} kaydi astigi anda (${esik} bit) tablo kalemi ` +
  `${say(ADAY * KAYIT)} olur: kayit basina bastan is yapmakla ayni.`);

console.log("\ncakisma olcutu daha sikidir: beklenen tuz cakismasi 1'in altina insin");
const H = [12, 16, 12, 20];
yaz(H, "kayit", "kayit cifti", "en az bit", "128 bitte cakisma");
for (const n of [340, 12_400, 1e6, 1e9])
  yaz(H, say(n), say(cift(n)), Math.ceil(Math.log2(cift(n))), say(cift(n) / 2 ** 128));

aday listesi 1.00e+6, kayit 340, kayit cifti 57.630
 tuz biti  ayri tuz  tablo kalemi  uydugu kayit  beklenen cakisma
        0         1       1.00e+6           340            57.630
        8       256       2.56e+8             1            225,12
       16       340       3.40e+8             1             0,879
       32       340       3.40e+8             1            1.3e-5
       64       340       3.40e+8             1           3.1e-15
      128       340       3.40e+8             1           1.7e-34

tuz uzayi 340 kaydi astigi anda (9 bit) tablo kalemi 3.40e+8 olur: kayit basina bastan is yapmakla ayni.

cakisma olcutu daha sikidir: beklenen tuz cakismasi 1'in altina insin
       kayit     kayit cifti   en az bit   128 bitte cakisma
         340          57.630          16             1.7e-34
      12.400         7.69e+7          27             2.3e-31
     1.00e+6        5.00e+11          39             1.5e-27
     1.00e+9        5.00e+17          59             1.5e-21

İlk satır tuzsuz kurulumdur ve kritik sayı oradadır: bir milyon kalemlik tek bir tablo, 340 kaydın tamamına uyar. Yapılan iş bir kez yapılır ve kayıt sayısı kadar bölüşülür.

Sonraki satırlarda uydugu kayit sütunu 1’e iner ve bir daha yükselmez. Tuz sekiz bit olduğunda bile bir tablo artık ortalama tek bir kayda uymaktadır. Bu, tuzun asıl etkisinin uzunluktan değil kayıt başına ayrı olmasından geldiğini gösterir.

Bu ayrım kurulumdaki en yaygın kusuru da ölçer. Uygulama genelinde tek bir tuz kullanmak, tuzun uzunluğu 128 bit bile olsa tabloda sıfır bit satırına düşer: ayrı tuz sayısı birdir, tablo bir milyon kalemdir ve 340 kaydın tamamına uyar. Tuzu uzatmak bu satırı hiç değiştirmez; onu değiştiren tek şey tuzun kayıt başına ayrı üretilmesidir. Aynı biçimde, kullanıcı kodundan ya da kayıt zamanından türetilen tuz da tabloyu geri getirir, çünkü tablo o türetimi de önceden yapabilir.

Eşik tablo kalemi sütununda okunur. Tuz uzayı kayıt sayısını aştığı anda — burada dokuz bit — tabloyu bütün kayıtlara uydurmak 3,4×10^8 kalem ister ve bu, her kayıt için baştan iş yapmakla aynıdır. Dokuz bitten sonra sütun sabitlenir; daha uzun tuz, tabloyu daha fazla işe yaramaz kılmaz, çünkü zaten tamamen işe yaramaz durumdadır. Ön hesaplama, tuz karşısında 9 kalemde avantajını yitirir.

Tuz Uzunluğunu Ne Belirliyor

KT10: tuz uzunluğunu belirleyen şey tablo boyutu değil, tuzların kendi aralarında çakışmamasıdır; ölçüt önceki derste ölçülen doğum günü sınırıdır.

Dokuz bit yetiyorsa, yerleşik seçim neden on altı bayttır? İkinci tablo yanıtı verir ve ölçüt önceki dersten gelir. Tuz kayıt başına ayrı olmalıdır; iki kaydın aynı tuza düşmesi, o iki kayıt arasında tek tablo avantajını geri getirir. Aynı tuza düşme olasılığı ise doğum günü sınırına tabidir.

Tablo bunu sayıya çevirir. 340 kayıtta beklenen çakışmanın birin altına inmesi için en az on altı bit gerekir — dokuz değil. Kayıt sayısı 12.400’e çıkınca eşik yirmi yediye, bir milyona çıkınca otuz dokuza, bir milyara çıkınca elli dokuza gider. Eşik kayıt sayısıyla birlikte hareket eder ve bir kurulumda kaç kayıt olacağı yazılırken bilinmez.

On altı baytlık tuz bu belirsizliği ortadan kaldıran seçimdir. 128 bitte beklenen çakışma bir milyar kayıtta bile 1,5×10^-21’dir; kayıt sayısı hangi mertebeye giderse gitsin ölçüt sağlanır. Seçimin gerekçesi “daha uzun daha iyidir” değil, eşiğin hesaplanmasına gerek bırakmamasıdır. Tuz gizli olmadığı ve karmanın yanında saklandığı için uzatmanın bir maliyeti de yoktur: 340 kayıt için on altışar bayt, toplam 5.440 bayttır ve bu, tek bir kaydın geri kalanının yanında ölçülemeyecek kadar küçüktür. Son sütunun dört satırında da çakışma olasılığı sıfıra yuvarlanacak mertebede kalır; parametreyi bir kez fazlasıyla seçmek, her kurulumda yeniden hesaplamaktan ucuzdur.

İki Çarpanın Onaramadığı Kök

Bu dersin üçüncü sayısı, ilk ikisinin yetmediği yerdedir. İş çarpanı birim maliyeti çarpar, tuz tekrarlanacak küme sayısını çarpar; ikisi de aday listesinin kendisine dokunmaz.

Güven kökü buradadır ve adı şudur: parolanın aday listesinde bulunmaması. Kök tutuyorsa arama listede değil uzayın tamamında yapılır ve önceki dersin 2^n sınırı geçerli olur. Kök kırıldığında — yani parola listedeyse — kırılan tek kalem o hesabın kaydıdır, ama kırılmanın maliyeti listedeki sırasıyla orantılıdır. Bir milyonluk listenin başındaki bir aday, N=2^16 çarpanında birkaç birime bulunur; iş çarpanının on altı katı da bunu değiştirmez.

Kalem sayısı bu yüzden asimetriktir. Tuz ve iş çarpanı, 340 kaydın tamamını birden düşmekten korur: kırılma kayıt kayıt olur, toplu olmaz. Öngörülemezlik kökü ise kayıt başına ayrıdır ve tek bir kaydın kırılması diğer 339’unu etkilemez. Üç savunma üç ayrı şeyi yapar ve hiçbiri ötekinin yerini almaz.

Yenileme bedeli üç savunmada üç ayrı sayıdır. İş çarpanını yükseltmek elle sıfır kalemdir: kayıt, kullanıcının bir sonraki başarılı girişinde yeni çarpanla yeniden üretilir ve kimse bir şey yapmaz. Tuzu yenilemek de sıfır kalemdir, çünkü tuz zaten her parola değişikliğinde yenilenir. Kayıtların sızması durumunda ise yenileme 340 elle kalemdir — her hesabın parolası yeniden belirlenmek zorundadır ve bu, tek tek insan eylemi gerektirir. Sızıntı penceresinde duran meşru iş de sayılır: parolalar yenilenene kadar saha ekiplerinin girişi ya kapalı kalır ya da kırılmış sayılan bir kayıtla açık tutulur. Bu kursun üçüncü sütunu her derste aynı biçimde okunur — kırılmanın büyüklüğü değil, kırılmadan sonra elle dokunulan kalem sayısı.

Özet

• İş çarpanı deneme başına birim maliyeti doğrusal büyütür: N 2^12’den 2^16’ya çıktığında beş ölçümün beşi de beklenen katın bandı içinde kalır ve bir milyonluk liste 1 milyon birimden 16 milyon birime çıkar.
• Aynı karar iki tarafta farklı toplama gider: savunan taraf giriş başına, deneyen taraf aday başına öder; bellek katsayısı ayrıca koşutluğu bellekle sınırlar.
• Tuzsuz kurulumda bir milyon kalemlik tek tablo 340 kaydın tamamına uyar; tuz kayıt başına ayrı olduğunda aynı tablo tek bir kayda uyar.
• Ön hesaplama tuz karşısında 9 kalemde avantajını yitirir; bundan sonrası tabloyu daha işe yaramaz kılmaz.
• Tuz uzunluğunu belirleyen ölçüt tablo boyutu değil çakışmadır: 340 kayıtta eşik 16 bit, bir milyarda 59 bittir; 128 bit eşiğin hesaplanmasını gereksiz kılar.

Sonraki Adım

Buraya kadarki üç ders tek yönlü işlemlerin etrafında döndü: karma geri dönmüyordu ve amaç zaten geri dönmemekti. Oysa kurgu ölçüm ağının asıl trafiği geri dönmek zorundadır — sahadan gelen okuma merkezde açılıp faturaya dönüşür. Birinci derste bu işlem iki kaleme bağlanmıştı: anahtar ve bozulmamış şifreli metin. Sonraki ders o birinci kalemi asıl sorunuyla birlikte ele alıyor. Aynı anahtarı iki tarafın da bilmesi gerekiyorsa, o anahtar oraya nasıl gitti? Altı şube ve merkez arasında kaç ayrı anahtar tutulur, ağa yeni bir şube eklendiğinde kaç kalem eklenir ve tek bir anahtar sızdığında kaç bağlantı yenilenmek zorunda kalır — hepsi sayılabilir.