Gökkuşağı masası - Rainbow table

Bir gökkuşağı tablo bir olan precomputed tablo çıktısını önbelleğe alma için kriptografik hash fonksiyonları genellikle şifre karmaları kırmak için. Tablolar genellikle , sınırlı sayıda karakterden oluşan belirli bir uzunluğa kadar bir anahtar türetme işlevinin (veya kredi kartı numaralarının vb.) kurtarılmasında kullanılır . Her denemede bir hash hesaplayan bir kaba kuvvet saldırısından daha az bilgisayar işlem süresi ve daha fazla depolama kullanan, ancak tek bir girişle basit bir anahtar türetme işlevinden daha fazla işlem süresi ve daha az depolama kullanan bir uzay-zaman değiş tokuşunun pratik bir örneğidir. karma başına. Tuz kullanan bir anahtar türetmenin kullanılması bu saldırıyı olanaksız kılar.

Gökkuşağı tabloları, Philippe Oechslin tarafından Martin Hellman'ın daha önceki, daha basit bir algoritmasının bir uygulaması olarak icat edildi .

Arka plan

Kullanıcı kimlik doğrulaması için parolalar düz metin veya karma olarak saklanır . Düz metin olarak saklanan parolalar, veritabanı erişimi tehlikeye girerse kolayca çalındığından, veritabanları genellikle bunun yerine karmaları depolar. Böylece, kimlik doğrulama sistemi de dahil olmak üzere hiç kimse, yalnızca veritabanında saklanan değere bakarak bir parola öğrenemez.

Bir kullanıcı kimlik doğrulaması için bir parola girdiğinde, bunun için bir hash hesaplanır ve daha sonra o kullanıcı için saklanan hash ile karşılaştırılır. İki karma eşleşirse kimlik doğrulama başarılı olur. (Öte yandan, oturum açmak için parola olarak karma değeri kullanmaya çalışmak, kimlik doğrulama sistemi ikinci kez karma oluşturacağından başarısız olur.)

Bir hash'den bir parola öğrenmek, hash fonksiyonuna girildiğinde aynı hash'i yaratan bir string bulmaktır. Bu, karma işlevini tersine çevirmekle aynıdır .

Gerçi kaba kuvvet saldırıları (örneğin Sözlük saldırıları ) bir karma işlev ters çevirmek için denemek için kullanılabilir olası şifreleri seti yeterince büyük olduğunda, bunlar mümkün olmayan hale gelebilir. Kaba kuvvete bir alternatif, önceden hesaplanmış karma zincir tablolarını kullanmaktır. Gökkuşağı masaları, belirli teknik zorlukların üstesinden gelen özel bir masa türüdür .

etimoloji

"Gökkuşağı Tabloları" terimi ilk olarak Dr. Oechslin'in ilk makalesinde kullanıldı. Terim, saldırının başarı oranını artırmak için farklı azaltma işlevlerinin kullanılma şeklini ifade eder. Hellman'ın orijinal yöntemi, her biri farklı bir indirgeme işlevine sahip birçok küçük tablo kullanır. Gökkuşağı tabloları çok daha büyüktür ve her sütunda farklı bir azaltma işlevi kullanır. İndirgeme işlevlerini temsil etmek için renkler kullanıldığında, gökkuşağı tablosunda bir gökkuşağı belirir. Dr. Oechslin'in makalesindeki Şekil 2, bu bölümlerin nasıl ilişkili olduğunu gösteren siyah beyaz bir grafik içermektedir. Crypto 2003 konferansındaki sunumu için Dr. Oechslin, gökkuşağı ilişkilendirmesini daha net hale getirmek için grafiğe renk ekledi. Konferansta sunulan geliştirilmiş grafik sağda gösterilir.

Önceden hesaplanmış karma zincirler

Bir parola hash fonksiyonumuz H ve sonlu bir parolalar P setimiz olduğunu varsayalım. Amaç, hash fonksiyonunun herhangi bir h çıktısı verildiğinde , H( p ) = olacak şekilde P'deki bir p öğesini bulabilen bir veri yapısını önceden hesaplamaktır. h , veya P'de böyle bir p olmadığını belirleyin. Bunu yapmanın en basit yolu, P'deki tüm p için H( p ) hesaplamaktır , ancak daha sonra tabloyu depolamak için Θ (|P| n ) bitlik alan gerekir, burada | P| P kümesinin boyutudur ve n , büyük |P| için yasak olan H çıktısının boyutudur. Hash zincirleri, bu alan gereksinimini azaltmak için bir tekniktir. Buradaki fikir, hash değerlerini tekrar P'deki değerlere eşleyen bir indirgeme fonksiyonu R tanımlamaktır. Bununla birlikte, indirgeme fonksiyonunun aslında karma fonksiyonunun bir tersi olmadığını, daha ziyade takas edilmiş etki alanı ve kod etki alanı olan farklı bir fonksiyon olduğuna dikkat edin. Özet fonksiyonu. Hash fonksiyonu ile indirgeme fonksiyonu değiştirilerek, alternatif şifreler ve hash değerleri zincirleri oluşturulur. Örneğin, P küçük harfli alfabetik 6 karakterli parolalar kümesiyse ve karma değerleri 32 bit uzunluğundaysa, bir zincir şöyle görünebilir:

${\displaystyle {\color {Kırmızı}{\mathtt {aaaaaa}}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {281DAF40}}\,{\xrightarrow[{ \;R\;}]{}}\,{\mathtt {sgfnyd}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {920ECF10}}\,{\xrightarrow [{\;R\;}]{}}\,{\color {Violet}{\mathtt {kiebgt}}}}$

Küçültme işlevi için tek gereksinim, belirli bir boyutta bir "düz metin" değeri döndürebilmektir.

Tabloyu oluşturmak için, P'den rastgele bir başlangıç ​​şifreleri seti seçiyoruz , her biri için sabit uzunluktaki k zincirlerini hesaplıyoruz ve her zincirde sadece ilk ve son şifreyi saklıyoruz. İlk parola başlangıç ​​noktası , son parola ise bitiş noktası olarak adlandırılır . Yukarıdaki örnek zincirde, "aaaaaa" başlangıç ​​noktası ve "kiebgt" bitiş noktası olacaktır ve diğer parolaların hiçbiri (veya karma değerleri) saklanmayacaktır.

Şimdi, tersine çevirmek istediğimiz bir h karma değeri verildiğinde (ilgili parolayı bulun), R, ardından H, ardından R vb. uygulayarak h ile başlayan bir zincir hesaplayın . Herhangi bir noktada tablodaki bitiş noktalarından biriyle eşleşen bir değer gözlemlersek, karşılık gelen başlangıç ​​noktasını alır ve zinciri yeniden oluşturmak için kullanırız. Bu zincirin h değerini içermesi için iyi bir şans var ve eğer öyleyse, zincirdeki hemen önceki değer aradığımız p parolasıdır .

Örneğin, 920ECF10 karma değeri verilmişse, önce R'yi uygulayarak zincirini hesaplarız:

${\displaystyle {\mathtt {920ECF10}}}\,{\xrightarrow[{\;R\;}]{}}\,{\color {Violet}{\mathtt {kiebgt}}}}$

" kiebgt " tablomuzdaki uç noktalardan biri olduğu için, ilgili başlangıç ​​şifresi " aaaaaa " alır ve 920ECF10'a ulaşılana kadar zincirini takip ederiz:

${\displaystyle {\color {Kırmızı}{\mathtt {aaaaaa}}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {281DAF40}}\,{\xrightarrow[{ \;R\;}]{}}\,{\mathtt {sgfnyd}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {920ECF10}}}$

Böylece parola " sgfnyd " (veya aynı hash değerine sahip farklı bir parola) olur.

Ancak bu zincirin her zaman hash değerini h içermediğine dikkat edin ; öyle olabilir ki, h'den başlayan zincir, farklı bir başlangıç ​​noktasına sahip bir zincirle birleşir. Örneğin, bize bir FB107E70 karma değeri verilebilir ve zincirini takip ettiğimizde kiebgt elde ederiz:

${\displaystyle {\mathtt {FB107E70}}}\,{\xrightarrow[{\;R\;}]{}}\,{\mathtt {bvtdll}}\,{\xrightarrow[{\;H\;}] {}}\,{\mathtt {0EE80890}}}\,{\xrightarrow[{\;R\;}]{}}\,{\color {Violet}{\mathtt {kiebgt}}}}$

Ancak FB107E70 , "aaaaaa" ile başlayan zincirde değil. Buna yanlış alarm denir . Bu durumda eşleşmeyi yok sayarız ve başka bir eşleşme arayarak h zincirini uzatmaya devam ederiz . Eğer h zinciri, iyi eşleşmeler olmadan k uzunluğuna kadar uzarsa , bu durumda hiçbir zincirde parola üretilmez.

Tablo içeriği, ters çevrilecek karma değerine bağlı değildir. Bir kez oluşturulur ve daha sonra değiştirilmemiş aramalar için tekrar tekrar kullanılır. Zincir uzunluğunun artması masanın boyutunu küçültür. Ayrıca arama yapmak için gereken süreyi de artırır ve bu, gökkuşağı tablosunun zaman-bellek değiş tokuşudur. Basit bir tek parça zincir durumunda, arama çok hızlıdır, ancak tablo çok büyüktür. Zincirler uzadığında arama yavaşlar, ancak masa boyutu azalır.

Basit karma zincirlerin birkaç kusuru vardır. En ciddi durum, herhangi bir noktada iki zincir çarpışırsa (aynı değeri üretirse ), birleşirler ve sonuç olarak, aynı hesaplama maliyetini ödemesine rağmen tablo o kadar çok parolayı kapsamaz. Önceki zincirler bütünlükleri içinde saklanmadıkları için, bunu verimli bir şekilde tespit etmek mümkün değildir. Örneğin, 3. zincirdeki üçüncü değer, 7. zincirdeki ikinci değerle eşleşirse, iki zincir hemen hemen aynı değer dizisini kapsayacaktır, ancak nihai değerleri aynı olmayacaktır. Karma işlevi H'nin çarpışma üretmesi olası değildir, çünkü genellikle bunu yapmaması önemli bir güvenlik özelliği olarak kabul edilir, ancak indirgeme işlevi R, olası düz metinleri doğru bir şekilde kapsama ihtiyacı nedeniyle çarpışmaya dayanıklı olamaz .

Diğer zorluklar, R için doğru işlevi seçmenin öneminden kaynaklanmaktadır. R'yi kimlik olarak seçmek, kaba kuvvet yaklaşımından biraz daha iyidir. Yalnızca saldırgan olası düz metinlerin ne olacağı konusunda iyi bir fikre sahip olduğunda, olası parolaların tüm alanı için değil, zaman ve alanın yalnızca olası düz metinler için kullanılmasını sağlayan bir R işlevi seçebilir. Gerçekte R, önceki karma hesaplamalarının sonuçlarını olası düz metinlere geri döndürür, ancak bu fayda, R'nin muhtemelen saldırganın kontrol etmek istediği sınıfta olası her düz metni üretmeyeceği dezavantajıyla birlikte gelir. seçilen sınıf Ayrıca, R fonksiyonunu, beklenen düz metin dağılımına uyacak şekilde tasarlamak zor olabilir.

Gökkuşağı masaları

Gökkuşağı tablo etkili bir sorunu çözmek çarpışmalar R ilgili indirgeme fonksiyonları bir dizisi ile bir azaltma fonksiyonu R değiştirerek sıradan karma zincirleri ile ₁ R, ile _k . Bu şekilde, iki zincirin çarpışması ve birleşmesi için aynı iterasyonda aynı değere ulaşmaları gerekir : sonuç olarak, bu zincirdeki son değerler aynı olacaktır. Son bir son işleme geçişi, tablodaki zincirleri sıralayabilir ve diğer zincirlerle aynı nihai değerlere sahip "yinelenen" zincirleri kaldırabilir. Daha sonra tabloyu doldurmak için yeni zincirler oluşturulur. Bu zincirler çarpışmasız değildir (kısa bir süre üst üste gelebilirler) ancak birleşmeyecekler ve toplam çarpışma sayısını büyük ölçüde azaltacaklar.

İndirgeme işlevlerinin dizilerini kullanmak, aramanın nasıl yapıldığını değiştirir: ilgilenilen karma değeri zincirdeki herhangi bir yerde bulunabileceğinden, k farklı zincir oluşturmak gerekir . İlk zincir, özet değerinin son özet konumunda olduğunu varsayar ve sadece R _k uygular ; sonraki zincir, özet değerinin sondan ikinci özet konumunda olduğunu varsayar ve R _{k -1} , ardından H, ardından R _k uygular ; ve bu, tüm indirgeme işlevlerini uygulayan ve H ile değişen son zincire kadar devam eder. Bu, yanlış bir alarm üretmenin yeni bir yolunu yaratır: karma değerinin konumunu yanlış "tahmin edersek", gereksiz yere bir zinciri değerlendirebiliriz.

Gökkuşağı tablolarının daha fazla zincir izlemesi gerekse de, bunu daha az tabloya sahip olarak telafi ederler: basit karma zincir tabloları, zincirlerin birleşmesi nedeniyle hızla verimsiz hale gelmeden belirli bir boyutun ötesine büyüyemez; bununla başa çıkmak için birden fazla tablo tutarlar ve her aramanın her tabloyu araması gerekir. Gökkuşağı tablolardır tablolarla benzer bir performans elde edebilirsiniz k onlara bir faktör gerçekleştirmek için izin kat daha büyük k az aramalarının.

Örnek

1. Aşağıdaki resimdeki karmadan ("re3xes") başlayarak, tabloda kullanılan son azaltma hesaplanır ve parolanın tablonun son sütununda görünüp görünmediği kontrol edilir (1. adım).
2. Test başarısız olursa ( tabloda rambo görünmüyor), son iki azalmaya sahip bir zincir hesaplanır (bu iki azalma 2. adımda gösterilir).

   Not: Bu yeni test tekrar başarısız olursa, şifre bulunana kadar 3 azaltma, 4 azaltma vb. ile devam edilir. Hiçbir zincir parolayı içermiyorsa, saldırı başarısız olmuştur.

3. Bu test pozitifse (adım 3, linux23 zincirin sonunda ve tabloda görünür), şifre, linux23 üreten zincirin başlangıcında alınır . Burada , tabloda depolanan ilgili zincirin başında passwd'yi buluyoruz .
4. Bu noktada (adım 4), bir zincir oluşturulur ve her yinelemede hash ile hedef hash karşılaştırılır. Test geçerlidir ve zincirdeki hash re3x'lerini buluruz . Geçerli parola ( kültür ), tüm zinciri oluşturan paroladır : saldırı başarılıdır.

Gökkuşağı tabloları, bir zincirdeki her "bağ" için farklı bir azaltma işlevine sahip rafine bir algoritma kullanır, böylece iki veya daha fazla zincirde bir karma çarpışma olduğunda, çarpışma meydana gelmediği sürece zincirler birleşmeyecektir. Her zincirde aynı pozisyon. Bu, arama başına gereken adım sayısının karesini alma pahasına belirli bir tablo boyutu için doğru bir çatlama olasılığını artırır, çünkü arama rutininin artık zincirde kullanılan ilk indirgeme fonksiyonunun indeksi boyunca yinelenmesi gerekir.

Rainbow tabloları oluşturuldukları özet işlevine özeldir, örneğin MD5 tabloları yalnızca MD5 karmalarını kırabilir. Bu teknikle teorisi hızlı bir formu olarak Philippe Oechslin tarafından icat edilmiştir zaman / bellek tradeoff diye uygulanan, , Windows şifre kırıcının Ophcrack . Daha sonra, LM hash , MD5 ve SHA-1 dahil olmak üzere çeşitli karakter kümeleri ve karma algoritmalar için gökkuşağı tabloları oluşturabilen ve kullanabilen daha güçlü RainbowCrack programı geliştirildi .

Küçültme işlevinin ve karma işlevinin çakışmadığı basit durumda, eksiksiz bir gökkuşağı tablosu (herhangi bir karma verilen karşılık gelen parolayı bulmanızı sağlayan) verilen parola kümesinin boyutu | P |, tabloyu hesaplamak için gereken T süresi, L tablosunun uzunluğu ve belirli bir karma ile eşleşen bir parola bulmak için gereken ortalama t süresi doğrudan ilişkilidir:

${\görüntüleme stili T=|P|}$

${\displaystyle t={\frac {|P|}{2L}}}$

Böylece, 8 karakterlik küçük harfli alfasayısal parola durumu (| P | ≃ 3×10 ¹² ) kişisel bir bilgisayarla kolayca izlenebilirken, 16 karakterlik küçük harfli alfasayısal parola durumu (| P | ≃ 10 ²⁵ ) tamamen anlaşılmaz olacaktır.

Gökkuşağı tablolarına karşı savunma

Gökkuşağı tablosu, büyük tuzlar içeren tek yönlü karmalara karşı etkisizdir . Örneğin, aşağıdaki işlev kullanılarak oluşturulan bir parola karmasını göz önünde bulundurun (" + " birleştirme operatörüdür):

saltedhash(password) = hash(password + salt)

Veya

saltedhash(password) = hash(hash(password) + salt)

Tuz değeri gizli değildir ve rastgele oluşturulabilir ve parola karması ile saklanabilir. Büyük bir tuz değeri, her kullanıcının parolasının benzersiz bir şekilde hash edilmesini sağlayarak, gökkuşağı tabloları da dahil olmak üzere ön hesaplama saldırılarını önler. Bu, aynı parolaya sahip iki kullanıcının farklı parola karmalarına sahip olacağı anlamına gelir (farklı tuzların kullanıldığı varsayılarak). Başarılı olmak için, bir saldırganın olası her tuz değeri için tabloları önceden hesaplaması gerekir. Tuz yeterince büyük olmalıdır, aksi takdirde saldırgan her tuz değeri için bir tablo oluşturabilir. 12 bitlik tuz kullanan daha eski Unix parolaları için bu, saldırgan için önemli bir maliyet artışı olan 4096 tablo gerektirir, ancak terabayt sabit disklerle pratik değildir. SHA2-kript ve bcrypt kullanılan yöntemler- Linux , BSD Unix ve Solaris 128 bitlik mü tuzlarıdır. Bu daha büyük tuz değerleri, neredeyse tüm parola uzunlukları için bu sistemlere yönelik ön hesaplama saldırılarını olanaksız hale getirir. Saldırgan saniyede bir milyon tablo oluşturabilse bile, olası tüm tuzlar için tablolar oluşturmak için yine de milyarlarca yıla ihtiyacı olacaktır.

Ön hesaplama saldırılarını önlemeye yardımcı olan bir başka teknik de anahtar germedir . Uzatma kullanıldığında, tuz, parola ve bazı ara karma değerleri, her bir parolayı karma hale getirmek için gereken hesaplama süresini artırmak için temeldeki karma işlevi aracılığıyla birden çok kez çalıştırılır. Örneğin, MD5-Crypt, tuzu, parolayı ve geçerli ara karma değerini tekrar temeldeki MD5 karma işlevine geri besleyen 1000 yineleme döngüsü kullanır. Kullanıcının parola karması, tuz değeri (gizli olmayan) ile son karmanın birleşimidir. Kullanıcılar her oturum açtıklarında bir saniyenin sadece bir kısmını beklemek zorunda oldukları için fazladan süre kullanıcılar tarafından fark edilmez. Öte yandan, esneme, iterasyon sayısıyla orantılı olarak kaba kuvvet saldırılarının etkinliğini azaltır çünkü süreyi azaltır. bir saldırganın belirli bir zaman diliminde gerçekleştirebileceği deneme sayısı. Bu ilke, MD5-Crypt ve bcrypt'te uygulanır. Ayrıca önceden hesaplanmış bir tablo oluşturmak için gereken süreyi de büyük ölçüde artırır, ancak tuzun yokluğunda bunun yalnızca bir kez yapılması gerekir.

Anahtar güçlendirme adı verilen alternatif bir yaklaşım, anahtarı rastgele bir tuzla genişletir, ancak daha sonra (anahtar uzatmanın aksine) tuzu güvenli bir şekilde siler. Bu, hem saldırganı hem de yasal kullanıcıları tuz değeri için kaba kuvvet araması yapmaya zorlar. Anahtar gerdirmeyi tanıtan makale, bu önceki tekniğe atıfta bulunup kasıtlı olarak farklı bir isim seçmiş olsa da, "anahtar güçlendirme" terimi şimdi sıklıkla (tartışmasız bir şekilde) anahtar uzatmayı ifade etmek için kullanılmaktadır.

Rainbow tabloları ve diğer ön hesaplama saldırıları, varsayılan aralığın dışında veya saldırgan tarafından önceden hesaplananlardan daha uzun semboller içeren parolalara karşı çalışmaz. Ancak, kullanıcıların sayı veya özel karakter ekleme gibi daha güvenli parolalar seçmeye çalıştıkları yaygın yolları dikkate alan tablolar oluşturulabilir. Hesaplama işlemine yapılan büyük yatırım nedeniyle, on dört yerden uzun gökkuşağı tabloları henüz yaygın değildir. Bu nedenle, on dört karakterden uzun bir parola seçmek, bir saldırganı kaba kuvvet yöntemlerine başvurmaya zorlayabilir.

Microsoft tarafından kullanılan daha eski bir karma algoritması olan LM hash'e odaklanan özel yoğun çabalar herkese açıktır. LM hash'i özellikle savunmasızdır, çünkü 7 karakterden uzun parolalar, her biri ayrı olarak hash'lenen iki bölüme ayrılır. On beş karakter veya daha uzun bir parola seçmek, bir LM karması oluşturulmayacağını garanti eder.

Yaygın kullanımlar

Unix , Linux ve BSD'nin neredeyse tüm dağıtımları ve varyasyonları, çoğu uygulama tuz içermeyen yalnızca bir karma (tipik olarak MD5 ) kullanmasına rağmen, tuzlu karmaları kullanır . Microsoft Windows NT/2000 ailesi, LAN Manager ve NT LAN Manager karma yöntemini ( MD4 tabanlı ) kullanır ve ayrıca tuzsuzdur, bu da onu en popüler oluşturulan tablolardan biri yapar. Tuzlamanın daha yaygın olması ve GPU tabanlı kaba kuvvet saldırıları daha pratik hale gelmesi nedeniyle Rainbow tablolarının kullanımı 2020'den itibaren azaldı . Ancak Rainbow tabloları sekiz ve dokuz karakterli NTLM parolaları için kullanılabilir.

Ayrıca bakınız

• A5/1
• kaba kuvvet saldırısı
• Dağıtıcı
• Pollard'ın kanguru algoritması

Notlar

Referanslar

• Oechslin, Philippe (2003-08-17). "Daha Hızlı Kriptanalitik Zaman-Bellek Takası Yapmak". Daha Hızlı Kriptanalitik Zaman-Bellek Değişimi Yapma (PDF) . Kriptolojideki Gelişmeler: CRYPTO 2003 Bildirileri, 23. Yıllık Uluslararası Kriptoloji Konferansı . Bilgisayar Bilimleri Ders Notları. 2729 . Santa Barbara, Kaliforniya , ABD: Springer. s. 617–630. doi : 10.1007/978-3-540-45146-4_36 . ISBN'si 978-3-540-40674-7.

Dış bağlantılar

• Ophcrack sayfası Philippe Oechslin tarafından Orijinal gökkuşağı tablosu araştırması
• Kriptografi at Curlie