it-swarm-tr.com

Rainbow tabloları nedir ve nasıl kullanılır?

Nerede bulabilirim? Sonunda bir altın kap var mı?
Onlara karşı nasıl korurum?


Area51 teklifinden

Bu soru Haftanın BT Güvenlik Sorus idi.
Daha fazla ayrıntı için 09 Eyl 2011 blog girişi bölümünü okuyun veya kendinizinkini gönderin Haftanın Sorusu.

149
AviD

Gökkuşağı Tabloları genellikle parola kurtarma işleminde hesaplama zaman depolama dengesinden yararlanan başka, daha basit bir teknikle karıştırılır: karma tablolar.

Karma tablolar, her Word'ü bir parola sözlüğüne ayırarak oluşturulur. Parola karma çiftleri, karma değerine göre sıralanmış bir tabloda saklanır. Karma tablo kullanmak için, karma değerini alın ve varsa orijinal parolayı bulmak için tabloda ikili bir arama yapın.

Gökkuşağı Tabloları daha karmaşıktır. Rainbow tablosu oluşturmak iki şey gerektirir: bir karma işlevi ve bir azaltma işlevi. Belirli bir Rainbow Tables kümesi için karma işlevi, kurtarmak istediğiniz karma parolayla eşleşmelidir. İndirgeme işlevi, bir karmayı parola olarak kullanılabilen bir şeye dönüştürmelidir. Basit bir azaltma işlevi, Base64 karmayı kodlamak, sonra belirli sayıda karaktere kısaltmaktır.

Gökkuşağı tabloları belirli bir uzunlukta "zincirlerden" oluşur: örneğin 100.000. Zinciri oluşturmak için rastgele bir tohum değeri seçin. Daha sonra bu tohuma ve çıkışına hash ve redüksiyon fonksiyonlarını uygulayın ve 100.000 kez tekrarlamaya devam edin. Sadece tohum ve nihai değer kaydedilir. İstediğiniz kadar zincir oluşturmak için bu işlemi tekrarlayın.

Rainbow Tables kullanarak bir parolayı kurtarmak için, parola karması aynı işleme göre yukarıdaki işleme tabi tutulur: bu durumda 100.000 ancak zincirdeki her bağlantı korunur. Zincirdeki her halka, her zincirin nihai değeri ile karşılaştırılır. Bir eşleşme varsa, zincir, her bir karma fonksiyonunun çıktısını ve her bir azaltma fonksiyonunun çıktısını koruyarak yeniden yapılandırılabilir. Yeniden yapılandırılan zincir, söz konusu şifrenin karmasını ve onu üreten şifreyi içerecektir.

Karma tablonun güçlü yanları, bir parolayı kurtarmanın yıldırım hızında (ikili arama) olması ve karma tablosunu oluşturan kişinin, en iyi 10.000 parola gibi içine girecek olanı seçebilmesidir. Rainbow Tables'a göre zayıflık, karma tabloların her bir karma şifre çiftini saklaması gerektiğidir.

Gökkuşağı Tabloları, bu tabloları oluşturan kişinin, her bir zincirdeki bağlantı sayısını seçerek ne kadar depolama alanı gerektiğini seçebileceği yararına sahiptir. Tohum ve son değer arasındaki bağlantı ne kadar çok olursa, o kadar çok şifre yakalanır. Bir zayıf nokta, zincirleri oluşturan kişinin yakaladıkları şifreleri seçmemesidir, bu nedenle Rainbow Tables yaygın şifreler için optimize edilemez. Ayrıca, parola kurtarma, uzun karma zincirlerinin hesaplanmasını içerir, bu da kurtarmayı pahalı bir işlem haline getirir. Zincirler ne kadar uzun olursa, içinde o kadar çok şifre yakalanır, ancak içeride bir şifre bulmak için daha fazla zaman gerekir.

Karma tablolar yaygın şifreler için iyidir, Gökkuşağı Tablolar zor şifreler için iyidir. En iyi yaklaşım, karma tabloları ve/veya en iyi N parolalarının sözlüğüyle geleneksel çatlamaları kullanarak mümkün olduğunca çok sayıda parolayı kurtarmaktır. Kalanlar için Rainbow Tables kullanın.

180
Crunge

Rainbow tablolarının ne olduğuna dair birçok iyi açıklama var, bu Rainbow Tables'ın nasıl çalıştığı özellikle iyi. Ayrıca Wikipedia makalesi de çok iyi bir açıklamaya sahiptir. Biraz daha derinlemesine okumak için konuyla ilgili kesin kağıt Daha Hızlı Kriptanalitik Zaman-Hafıza Değişimi yapmaktır.

Rainbow Tables'ın basit bir açıklaması, zaman hafızası değiş tokuş tekniğini kullanmalarıdır. Bir hedef karma değeri ve bir sözlük sözlüğü alıp daha sonra her bir Word'ü karma yapmak ve anında karşılaştırma yapmak yerine anlam ( John gibi bir şey kullanarak kaba kuvvet yaklaşımı ), bunun yerine sözlükteki tüm değerleri önceden hash edersiniz (bu, sözlük boyutuna bağlı olarak çok uzun sürebilir). Ancak yapıldıktan sonra, Rainbow tablolarındaki önceden hashed değerleriyle istediğiniz kadar hash karşılaştırabilirsiniz, bu, hashleri ​​tekrar hesaplamaktan çok daha hızlıdır.

Burada daha önce kısa olmak için yazdığım açıklama yanıltıcıydı, çünkü Rainbow tablolarının kullandığı azaltımların kullanımını açıklamıyordu. Bu biti yeniden yazana kadar daha iyi bir açıklama için bkz. @ Crunge yanıtı .

Rainbow tablolarını RainbowCrack gibi bir uygulama kullanarak kendiniz oluşturabilir veya Shmoo gibi kaynaklardan indirebilirsiniz. Grup , Ücretsiz Gökkuşağı Tabloları proje web sitesi, Ophcrack proje ve tablolara ihtiyaç duyduğunuz türlere bağlı olarak birçok başka yer.

Gökkuşağı Tablosu tabanlı bir saldırıya karşı korunmak için, bununla mücadelede en etkili yöntem, bir sistemdeki her karmanın tuzlanmış olmasını sağlamaktır. Bu, önceden oluşturulmuş Rainbow tablolarını işe yaramaz hale getirir ve bir saldırganın, hedeflenen karmalara karşı kullanmak için özel bir tablo kümesi oluşturmak zorunda kalacağı anlamına gelir; bu, yalnızca tuzu bilseydi mümkün olurdu.

15
Mark Davidson

Amaç ve alaka düzeyi

Gökkuşağı tabloları zor şifreleri kırmaya yardımcı olur, yani büyük bir sözlükte bile bulunamayanlar. Parolalar tarihsel olarak veritabanlarında düz karma olarak saklandı ve Rainbow tablolarının etkili olduğu şey: tek bir Rainbow tablosu oluşturun (yavaş) ve buna karşı karmalarla dolu (hızlı) herhangi bir sayıda veritabanı çalıştırın.

Günümüzde giderek daha fazla sistem Bcrypt, Scrypt veya Argon2 gibi uygun şifre depolama algoritmalarını kullanıyor. Bakınız: Şifreleri güvenli bir şekilde nasıl saklarsınız? Bu algoritmalar artık Rainbow tablolarına karşı "savunmasız" değildir: her karma benzersiz olduğundan, şifreler eşit olsa bile, Rainbow tabloları artık çalışmaz.

Bu yüzden Rainbow masaları bugün popüler değil. Argon2 gibi modern bir şey kullanılmasa bile, günümüzde geliştiriciler genellikle en azından bir tuz kullanmaları gerektiğini biliyorlar. Bu bir Rainbow masasını işe yaramaz hale getirmek için zaten yeterli.

Onlar nasıl çalışır

Tablo oluşturma

Her biri 5 uzunluğunda, sadece iki zincirli bir Gökkuşağı tablosu oluşturduğumuzu düşünün. Gökkuşağı tablosu, 48 bit (sadece 12 onaltılık karakter) çıktısı veren hayali karma işlevi MD48 içindir. Zinciri oluştururken şunu görüyoruz:

Chain 0: 0=cfcd208495d5 => z=fbade9e36a3f => renjaj820=7668b2810262 => aL=8289e8a805d7 => ieioB=2958b80e4a3a => WLgOSj
Chain 1: 1=c4ca4238a0b9 => ykI4oLkj=140eda4296ac => Dtp=1b59a00b7dbe => W=61e9c06ea9a8 => 6cBuqaha=d4d2e5280034 => 0uUoAD

0 İle başlıyoruz çünkü bu ilk zincir (başlangıç ​​olarak sadece bir değere ihtiyacımız var). Bunu MD48 ile hash ettiğimizde, cfcd208495d5 Olur. Şimdi, bu karmayı temel olarak bir parolaya dönüştüren bir "azaltma" işlevi uyguluyoruz ve sonunda "z" ile sonuçlanıyoruz. Tekrar hash ettiğimizde, fbade9e36a3f Alırız, sonra tekrar azaltır ve renjaj820 Alırız. Daha fazla döngü var ve nihai sonuç WLgOSj.

İkinci zincir için de aynı. Sadece başka bir değerle başlıyoruz ve aynı şeyi yapıyoruz. Bu, 0uUoAD İle bitiyor.

Komple Rainbow masamız şimdi:

WLgOSj => 0
0uUoAD => 1

Saklamanız gereken tek şey bu.

Karma arama

Çevrimiçi bir karma bulduğumuzu varsayalım, 7668b2810262. Hadi masamızı kullanarak kıralım!

Looking for hash '7668b2810262', reduced to 'aL'.
hashed=>reduced 'aL' to ieioB
hashed=>reduced 'ieioB' to WLgOSj
Found a match, 'WLgOSj' is in our Rainbow table:
    WLgOSj => 0
The chain starts with '0'. Let's walk that chain and look for the hash.
hashed '0' to cfcd208495d5
hashed 'z' to fbade9e36a3f
hashed 'renjaj820' to 7668b2810262
That hash matches! Found the password: renjaj820

Bununla birlikte oynamak için yukarıdaki örnekler bu Python komut dosyası kullanılarak oluşturuldu: https://Gist.github.com/lgommans/83cbb74a077742be3b31d33658f65adb

Ölçekleme özellikleri

Kısacası:

  • Hızlı aramalar, kapsama alanının aynı kaldığı varsayılarak daha büyük tablolar anlamına gelir.
  • Daha iyi kapsama alanı, daha yavaş aramalar veya daha büyük tablolar anlamına gelir.
  • Daha küçük tablolar daha yavaş arama veya daha kötü kapsama alanı anlamına gelir.

Aşağıdaki bölümlerde karma + azaltma başına süre 1µs olduğu ve çarpışmalar hesaba katılmadığı varsayılmaktadır. Bunların hepsi kesin değerler değil örnek olarak ifade edilen basketbol sahası sayılarıdır.

Arama süresi

Bir karma + azaltma işlemi mikrosaniye alırsa, bir milyon zincir ve bir zincir başına 10.000 azaltma içeren bir tablo oluşturmak yaklaşık 3 saat sürer:
chain_length × chain_count / reductions_per_second / seconds_per_hour
= 10 000 × 1 000 000 / 1 000 000 / 3600 = 2.8 saat.

Bu tabloda arama yapmak ortalama 10 milisaniye sürer. Bunun nedeni, hangi zincirin karmayı içerdiğini bulmadan önce genellikle chain_length/2 İndirimden geçmemiz gerekeceğidir. Örneğin, tablodaki bir değeri bulmadan önce bir karma üzerinde 3000 azaltma yapmak zorunda kalabiliriz. Daha sonra, eşleşen değeri bulana kadar bu zinciri baştan yapmalıyız. Masamızda bulmak için 3000 yapmamız gerekiyorsa, zincirde doğru noktaya ulaşmak için baştan 7000 indirim yapmalıyız. Temel olarak, bakarken tek bir zincir oluştururken olduğu kadar çok işlem yaparız. Bu nedenle, arama süresi mikrosaniyenin 10.000 katıdır, bu on milisaniyedir (veya eğer bir santisaniyedir).

Depolama alanı gereksinimleri

Karma işlevi için tam ve hızlı bir arama tablosu yapmak istediğinizde, MD5 bile, yine de yüz milyar milyar terabayt depolama alanına ihtiyacınız olacaktır. Bu çok yardımcı değil. Ancak 10 karaktere kadar yalnızca küçük harfleri kapsamak istiyorsak ne olur?

Bir hash aramak için en fazla 30 saniye harcamak istiyor ve her hash + azaltma döngüsü için 1 mikrosaniye (saniyenin milyonda biri) ihtiyacımız olduğunu varsayarsak, zincir uzunluğuna sahip olabiliriz: 1 million × 30 = 30 milyon . 26 tane var10 (veya 1014) 10 karakterlik olası küçük harfler ve zincir başına 30 milyon değeri kapsar. Bu bize 4 milyon zincir bırakıyor. Her zincirin yalnızca bir başlangıç ​​ve bitiş değeri depolandığını ve değerlerin her birinin 10 karakter olduğunu biliyoruz. Yani 2 × 10 × 4 million = 76 MiB verisi.

Tüm 10 karakterlik şifreleri yineleyerek tablo oluşturmak uzun zaman alır: zincir başına 30 saniye, 4 milyon zincirin süresi yaklaşık 91 yıldır. Bununla birlikte, birçok insan böyle bir tabloya ilgi duyacaktır, bu nedenle 1092 CPU'yu (= 91 × 12) bir araya getirerek sadece 1 ay sürer. Bu, böyle bir tablonun kapsadığı parola alanı ile ne kadar küçük olabileceğini gösterir: aramalar sadece 30 saniye sürer ve yalnızca 76MiB veri depolamanız gerekir.

Sonuç

Gökkuşağı tabloları bir zaman-bellek değiş tokuş : biri tablonun sadece küçük bir bölümünü depolar ve arama zamanında ekstra bir hesaplama yoluyla kurtarır. Bu, tuzların veya Scrypt veya Argon2 gibi iyi bir şifre depolama algoritmasının şifreleri güvende tutmak için önemli olmasının nedenlerinden biridir. Gökkuşağı tablosu, yalnızca tuz ve parolayı içerecek kadar büyük bir girdi içeriyorsa, tuzlu bir parolayı ancak son derece verimsiz ve tüm amacı yendiğinde kurtarabilir.

Benzer bir şeyin şifreleme için de geçerli olduğunu unutmayın: insanlar dosyaları bir şifre ile şifrelediğinde, dosyaları kırmak için bir Gökkuşağı tablosu oluşturulabilir. Yazılımın AES kullandığını ve dosyanın ilk bloğunun kullanıcının sağladığı parolayı kullanarak "parola düzeltmesi" için şifresini çözmesi gerektiğini, ardından Rainbow tablosunda karma işlevi yerine AES kullanacağını varsayalım.

Bir parolayı (gücü bilinmeyen bir sır olan ve özellikle kullanıcı yeniden kullanabiliyorsa) işlediğinizde, yavaş ve kırılmasını engellemek için her zaman uygun (yavaş) bir şifre depolama algoritması ile çalıştırın.

7
Luc