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

Bu makale genel bir liste içerir Referanslar, ancak büyük ölçüde doğrulanmamış kalır çünkü yeterli karşılık gelmiyor satır içi alıntılar. Lütfen yardım edin geliştirmek bu makale tanıtım daha kesin alıntılar. (Mart 2009) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin)

Bir gökkuşağı masa bir önceden hesaplanmış masa çıktısını önbelleğe almak için kriptografik hash fonksiyonları, genellikle parola karmalarını kırmak için. Tablolar genellikle bir anahtar türetme işlevi (veya kredi kartı numaraları, vb.), sınırlı sayıda karakterden oluşan belirli bir uzunluğa kadar. Pratik bir örnektir. uzay-zaman değiş tokuşu, daha az bilgisayar işlem süresi ve daha fazla depolama alanı kullanarak kaba kuvvet saldırısı bu, her denemede bir karma hesaplar, ancak basit bir işlemden daha fazla işlem süresi ve daha az depolama anahtar türetme işlevi Hash başına bir giriş ile. A kullanımı anahtar türetme kullanan tuz bu saldırıyı olanaksız kılar.

Gökkuşağı masaları Philippe Oechslin tarafından icat edildi^[1] daha eski ve daha basit bir algoritmanın uygulaması olarak Martin Hellman.^[2]

Arka fon

Şifre gerektiren herhangi bir bilgisayar sistemi kimlik doğrulama veya içinde bir şifre veritabanı içermelidir düz metin veya bir şekilde karma hale getirilmiş; bu nedenle çeşitli teknikler şifre saklama var olmak. Tablolar hırsızlığa karşı savunmasız olduğundan, düz metin parolayı saklamak tehlikelidir. Bu nedenle çoğu veritabanı bir kriptografik karma Veritabanındaki bir kullanıcının parolası. Böyle bir sistemde, kimlik doğrulama sistemi dahil hiç kimse, yalnızca veritabanında depolanan değere bakarak bir kullanıcının parolasının ne olduğunu belirleyemez. Bunun yerine, bir kullanıcı kimlik doğrulama için bir parola girdiğinde, sistem sağlanan parola için hash değerini hesaplar ve bu hash değeri, o kullanıcı için depolanan hash ile karşılaştırılır. İki karma eşleşirse kimlik doğrulama başarılı olur. Bir şifre karması topladıktan sonra, söz konusu karmanın şifre olarak kullanılması, kimlik doğrulama sistemi onu ikinci kez karma haline getireceği için başarısız olur. Bir kullanıcının şifresini öğrenmek için, genellikle kaba kuvvet veya sözlük saldırısı yoluyla aynı karma değeri üreten bir şifre bulunmalıdır.Rainbow tabloları, yalnızca karma bir değere bakarak şifre türetmek için geliştirilmiş bir araç türüdür. Daha basit düz metin kurtarma yöntemleri mevcut olduğundan, gökkuşağı tablolarına her zaman ihtiyaç duyulmaz. Kaba kuvvet saldırıları ve sözlük saldırıları mevcut en basit yöntemlerdir. Ancak bunlar, mevcut tüm seçenekleri depolamanın ve hash'in ters aramasını gerçekleştirmek için böylesine kapsamlı bir veritabanında arama yapmanın zorluğu nedeniyle uzun parolalar kullanan sistemler için yeterli değildir. Bu ölçek sorununu gidermek için, geriye doğru arama tabloları oluşturulmuştur. yalnızca daha küçük bir karma seçimi sakladı ve tersine çevrildiğinde uzun parola zincirleri oluşturabilir. Zincirlenmiş bir tablodaki karmanın ters aranması daha fazla hesaplama süresi gerektirse de, arama tablosunun kendisi çok daha küçük olabilir, bu nedenle daha uzun parolaların karmaları depolanabilir. Gökkuşağı masaları, bu zincirleme tekniğinin geliştirilmiş halidir ve zincir çarpışmaları adı verilen bir soruna çözüm sağlar.

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 nasıl kullanıldığını ifade eder. Hellman'ın orijinal yöntemi, her biri farklı bir azaltma 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ğı görünür. Dr. Oechslin'in makalesinin Şekil 2'si, bu bölümlerin nasıl ilişkili olduğunu gösteren siyah-beyaz bir grafik içeriyor. Dr. Oechslin, Crypto 2003 konferansındaki sunumu için, gökkuşağı ilişkisini daha net hale getirmek için grafiğe renk ekledi. Konferansta sunulan geliştirilmiş grafik sağda gösterilir.

Önceden hesaplanmış hash zincirleri

Bir şifre karma fonksiyonumuz H ve sonlu bir P şifrelerimiz olduğunu varsayalım.Amaç, herhangi bir çıktı verildiğinde bir veri yapısını önceden hesaplamaktır. h hash fonksiyonunun bir elemanını bulabilir p P'de öyle ki H (p) = hveya böyle olmadığını tespit edin p P.'de Bunu yapmanın en basit yolu H hesaplamaktır (p) hepsi için p P'de, ancak daha sonra tabloyu depolamak Θ (| P |n) uzay bitleri, nerede | P | P kümesinin boyutudur ve n büyük | P | için engelleyici olan bir H çıktısının boyutudur. Çarpma zincirleri bu alan gereksinimini azaltmak için bir tekniktir. Fikir, bir azaltma işlevi Karma değerlerini P'deki değerlere geri eşleyen R Bununla birlikte, azaltma işlevinin aslında karma işlevinin tersi olmadığını, bunun yerine takas edilmiş farklı bir işlev olduğunu unutmayın. alan adı ve ortak alan hash fonksiyonunun. Hash fonksiyonunu azaltma fonksiyonu ile değiştirerek, zincirler alternatif şifreler ve karma değerler oluşturulur. Örneğin, P, 6 karakterli küçük harfli alfabetik şifreler 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 ;}] {}} , { renk {Menekşe} { mathtt {kiebgt}}}}$

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

Tabloyu oluşturmak için rastgele bir dizi seçiyoruz ilk şifreler P'den itibaren, sabit uzunlukta hesaplama zincirleri k her biri için ve saklayın sadece her zincirdeki ilk ve son şifre. İlk şifreye başlangıç ​​noktası ve sonuncusunun adı uç nokta. Yukarıdaki örnek zincirde, "aaaaaa" başlangıç ​​noktası ve "kiebgt" bitiş noktası olacaktır ve diğer şifrelerin (veya karma değerlerin) hiçbiri depolanmayacaktır.

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

Örneğin, hash verilirse 920ECF10, ilk önce R'yi uygulayarak zincirini hesaplardık:

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

Dan beri "Kiebgt"tablomuzdaki uç noktalardan biridir, ardından ilgili başlangıç ​​şifresini alırız"aaaaaa"ve 920ECF10'a ulaşılana kadar zincirini takip edin:

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

Bu nedenle, şifre "sgfnyd"(veya aynı hash değerine sahip farklı bir parola).

Ancak bu zincirin her zaman karma değerini içerir h; o kadar olabilir ki zincir h farklı bir başlangıç ​​noktasına sahip bir zincirle birleşir. Örneğin, bize FB107E70 hash 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}}}}$

Fakat FB107E70 "aaaaaa" ile başlayan zincirde değil. Buna a yanlış alarm. Bu durumda, maçı görmezden gelir ve zincirini uzatmaya devam ederiz. h başka bir eşleşme arıyorum. Eğer zinciri h uzunluğa uzatılır k iyi eşleşmeler olmadığında şifre hiçbir zaman zincirlerde üretilmedi.

Tablo içeriği, tersine çevrilecek hash 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 arttırılması 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-hafıza değiş tokuşudur. Tek öğeli zincirlerin basit bir durumunda, arama çok hızlıdır, ancak tablo çok büyüktür. Zincirler uzadıkça arama yavaşlar, ancak tablo boyutu düşer.

Basit hash zincirlerinin birkaç kusuru vardır. Herhangi bir noktada iki zincir ise en ciddi çarpışmak (aynı değeri üretirler), birleşecekler ve sonuç olarak tablo, oluşturmak için aynı hesaplama maliyetini ödemiş olsalar bile bu kadar çok şifreyi kapsamayacaktır. Önceki zincirler bütünüyle depolanmadığından, bunun verimli bir şekilde tespit edilmesi imkansızdır. Örneğin, 3. zincirdeki üçüncü değer, 7. zincirdeki ikinci değerle eşleşirse, iki zincir neredeyse aynı değer dizisini kapsayacak, ancak son değerleri aynı olmayacaktır. Karma fonksiyonu H, genellikle bunu yapmaması için önemli bir güvenlik özelliği olarak kabul edildiğinden, çarpışma üretme olasılığı düşüktür, ancak indirgeme fonksiyonu R, muhtemel düz metinleri doğru şekilde kapama ihtiyacı nedeniyle, çarpışmaya dirençli olamaz.

Diğer zorluklar, R için doğru işlevi seçmenin öneminden kaynaklanmaktadır. Kimlik olarak R'yi seçmek, kaba kuvvet yaklaşımından biraz daha iyidir. Yalnızca saldırgan, olası düz metinlerin ne olacağına dair iyi bir fikre sahip olduğunda, zaman ve alanın olası parolaların tüm alanı için değil, yalnızca olası düz metinler için kullanılmasını sağlayan bir R işlevini seçebilir. Gerçekte R, önceki hash hesaplamalarının sonuçlarını olası düz metinlere geri götürür, ancak bu avantaj, R'nin muhtemelen sınıfta olası tüm düz metinleri üretmeyeceği dezavantajı ile birlikte gelir, saldırganın kendilerinden hiçbir parola gelmediğine dair kesinliği inkar etmeyi kontrol etmek isterler. seçilen sınıf. Ayrıca, R işlevini düz metinlerin beklenen dağılımına uyacak şekilde tasarlamak zor olabilir.^[2]

Gökkuşağı masaları

Rainbow tabloları, tek indirgeme işlevi R'yi ilgili indirgeme işlevleri dizisi ile değiştirerek sıradan hash zincirleriyle çarpışma sorununu etkili bir şekilde çözer.₁ R ile_k. Bu şekilde, iki zincirin çarpışması ve birleşmesi için aynı değere ulaşmaları gerekir. aynı yinelemede: sonuç olarak, bu zincirdeki nihai değerler aynı olacaktır. Son bir son işlem 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 (kısaca üst üste gelebilirler) ancak birleşmeyeceklerdir ve toplam çarpışma sayısını büyük ölçüde azaltacaktır.^{[kaynak belirtilmeli ]}

İndirgeme işlevlerinin sıralarını kullanmak, aramanın nasıl yapıldığını değiştirir: ilgilenilen hash değeri zincirdeki herhangi bir konumda bulunabileceğinden, k farklı zincirler. İlk zincir, hash değerinin son hash konumunda olduğunu varsayar ve sadece R'yi uygular_k; sonraki zincir, hash değerinin ikinci-son hash pozisyonunda olduğunu varsayar ve R'yi uygular_k−1, sonra H, sonra R_k; ve bu, H ile dönüşümlü olarak tüm indirgeme işlevlerini uygulayan son zincire kadar devam eder. Bu, yanlış alarm üretmenin yeni bir yolunu oluşturur: eğer hash değerinin konumunu yanlış "tahmin edersek", bir zinciri gereksiz yere değerlendirebiliriz.

Gökkuşağı masalarının daha fazla zinciri takip etmesi gerekmesine rağmen, bunu daha az masaya sahip olarak telafi ederler: basit karma zincir tabloları, birleşme zincirleri nedeniyle hızla verimsiz hale gelmeden belirli bir boyutun ötesine büyüyemezler; bunun üstesinden gelmek için, birden çok tablo tutuyorlar ve her arama her tabloda arama yapmalıdır. Rainbow masaları, aşağıdaki tablolarla benzer performans elde edebilir. k kat daha büyük, bir faktör gerçekleştirmelerine izin veriyor k daha az arama.

Misal

1. Aşağıdaki görüntüdeki hash'den ("re3xes") başlayarak, tabloda kullanılan son indirgeme hesaplanır ve şifrenin tablonun son sütununda görünüp görünmediği kontrol edilir (adım 1).
2. Test başarısız olursa (rambo tabloda görünmüyorsa), son iki indirgemeyle bir zincir hesaplanır (bu iki azalma 2. adımda gösterilmektedir)

   Not: Bu yeni test tekrar başarısız olursa şifre bulunana kadar 3 azaltma, 4 azaltma vb. İle devam edilir. Parola hiçbir zincir 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 üreten zincirin başlangıcında alınır linux23. Burada buluyoruz passwd Tabloda depolanan ilgili zincirin başında.
4. Bu noktada (4. adım), bir zincir oluşturulur ve her yinelemede hash ile hedef hash karşılaştırılır. Test geçerli ve hash'i buluyoruz re3xes zincirde. Mevcut şifre (kültür) tüm zinciri üreten kişidir: saldırı başarılıdır.

Rainbow tabloları, bir zincirdeki her "bağlantı" için farklı bir azaltma işlevine sahip rafine bir algoritma kullanır, böylece iki veya daha fazla zincirde bir hash çarpışması olduğunda, zincirler, çarpışma, zincirde meydana gelmediği sürece birleşmez. 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 çatlak olasılığını artırır, çünkü arama rutininin artık zincirde kullanılan ilk indirgeme fonksiyonunun indeksi boyunca yinelemesi gerekir.^[1]

Gökkuşağı tabloları, oluşturuldukları hash işlevine özeldir, ör. MD5 tablolar yalnızca MD5 karmalarını kırabilir. Bu tekniğin teorisi Philippe Oechslin tarafından icat edildi^[3] hızlı bir şekilde zaman / hafıza değiş tokuşu,^[1] uyguladığı pencereler şifre kırıcı Ophcrack. Daha güçlü RainbowCrack program daha sonra çeşitli karakter kümeleri ve karma algoritmalar için gökkuşağı tabloları oluşturabilen ve kullanabilen geliştirildi. LM karması, MD5, ve SHA-1.

İndirgeme fonksiyonunun ve hash fonksiyonunun çarpışmasının olmadığı basit durumda, eksiksiz bir gökkuşağı tablosu verildiğinde (herhangi bir hash verildiğinde karşılık gelen şifreyi bulmanızı sağlayan) şifre setinin boyutu |P| zaman T tabloyu hesaplamak için gerekli olan, tablonun uzunluğu L ve ortalama zaman t belirli bir hash ile eşleşen bir parola bulmak için gerekli olanlar doğrudan ilişkilidir:^{[kaynak belirtilmeli ]}

${ displaystyle T = | P |}$

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

Bu nedenle, 8 karakterli küçük alfanümerik parola durumu (|P| ≃ 3×10¹²) kişisel bir bilgisayarla kolayca izlenebilirken, 16 karakterli küçük harf alfanümerik parola durumu (|P| ≃ 10²⁵) tamamen inatçı olacaktır.

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

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

saltedhash (şifre) = karma (şifre + tuz)

Veya

saltedhash (şifre) = karma (karma (şifre) + tuz)

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 şifresinin benzersiz bir şekilde karma hale getirilmesini sağlayarak gökkuşağı tabloları 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, 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 sofra kurabilir. Daha yaşlı için Unix parolaları 12 bitlik bir tuz kullanıldığında, bu 4096 tablo gerektirir, bu da saldırgan için önemli bir maliyet artışı gerektirir, ancak terabayt sabit disklerde pratik değildir. SHA2-crypt ve bcrypt yöntemler — kullanılan Linux, BSD Unix'ler ve Solaris - 128 bitlik tuzlar var.^[4] Bu daha büyük tuz değerleri, bu sistemlere karşı ön hesaplama saldırılarını neredeyse tüm parolalar için olanaksız hale getirir. Saldırgan saniyede bir milyon tablo oluşturabilse bile, olası tüm tuzlar için tablo oluşturmak için yine de milyarlarca yıla ihtiyaç duyacaktır.

Ön hesaplama saldırılarını önlemeye yardımcı olan başka bir teknik de anahtar germe. Esnetme kullanıldığında, tuz, parola ve bazı ara hash değerleri, her parolanın hash'ını oluşturmak için gereken hesaplama süresini artırmak için temeldeki hash işlevi üzerinden birçok kez çalıştırılır.^[5] Örneğin, MD5-Crypt, tuzu, parolayı ve geçerli ara karma değerini, temeldeki MD5 karma işlevine tekrar tekrar besleyen bir 1000 yineleme döngüsü kullanır.^[4] Kullanıcının şifre karması, tuz değerinin (gizli olmayan) ve son karmanın birleştirilmesidir. Ekstra süre, her oturum açtıklarında saniyenin sadece bir kısmını beklemeleri gerektiğinden kullanıcılar tarafından fark edilmez. Öte yandan, germe, yineleme sayısı ile orantılı olarak kaba kuvvet saldırılarının etkinliğini azaltır çünkü belirli bir zaman diliminde bir saldırganın gerçekleştirebileceği deneme sayısı. Bu ilke MD5-Crypt ve bcrypt'de uygulanır.^[6] Aynı zamanda önceden hesaplanmış bir tablo oluşturmak için gereken süreyi de büyük ölçüde artırır, ancak tuz yoksa bunun yalnızca bir kez yapılması gerekir.

Adlı alternatif bir yaklaşım anahtar güçlendirme, 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 meşru kullanıcıları tuz değeri için kaba kuvvet araması yapmaya zorlar.^[7] Her ne kadar anahtar germe getiren kağıt^[8] Bu önceki tekniğe atıfta bulunulduğunda ve kasıtlı olarak farklı bir isim seçildiğinde, "anahtar güçlendirme" terimi artık sıklıkla (tartışmalı bir şekilde yanlış) anahtar genişletmeye atıfta bulunmak için kullanılmaktadır.

Gökkuşağı tabloları ve diğer ön hesaplama saldırıları, öngörülen aralığın dışında semboller içeren veya saldırgan tarafından önceden hesaplananlardan daha uzun olan parolalara karşı çalışmaz. Ancak, kullanıcıların bir sayı veya özel karakter eklemek gibi daha güvenli parolalar seçmeye çalıştıkları yaygın yolları hesaba katan tablolar oluşturulabilir. Bilgi işlem işlemine yapılan büyük yatırım nedeniyle, on dört yerin ötesinde 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.^{[kaynak belirtilmeli ]}

Odaklanan özel yoğun çabalar LM karması, Microsoft tarafından kullanılan daha eski bir karma algoritma halka açıktır. LM sağlaması özellikle savunmasızdır çünkü 7 karakterden uzun parolalar, her biri ayrı ayrı karma hale getirilmiş iki bölüme ayrılır. On beş karakter veya daha uzun bir parola seçmek, bir LM sağlamasının oluşturulmayacağını garanti eder.^[9]

Yaygın kullanımlar

Neredeyse tüm dağılımları ve varyasyonları Unix, Linux, ve BSD tuzlarla karmalar kullanın, ancak birçok uygulama yalnızca bir karma kullanır (tipik olarak MD5 ) tuzsuz. Microsoft Windows NT / 2000 ailesi, LAN Yöneticisi ve NT LAN Yöneticisi karma yöntemi (temel alan MD4 ) ve ayrıca tuzsuzdur, bu da onu en popüler oluşturulan tablolardan biri yapar.

Ayrıca bakınız

• A4 / 1
• Kaba kuvvet saldırısı
• DistrRTgen
• Pollard'ın kanguru algoritması

Notlar

Referanslar

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

Dış bağlantılar

• Ophcrack sayfası Philippe Oechslin Orijinal gökkuşağı masa araştırması
• Kriptografi -de Curlie