it-swarm-tr.com

Rainbow tabloları oluşturmak ne kadar sürer?

Gökkuşağı tablolarını okuyorum çünkü oldukça ilginç olduklarını çünkü aslında oldukça basit bir kavramlar.

Her neyse, merak ediyordum, biri gerçekten bir tane üretmekle ilgilendi mi? Muhtemelen nasıl yapılır? Her karakterin her kombinasyonunu oluşturmanın gerçekten mümkün olduğunu görmüyorum.

Özel karakterleri hariç tutarsak, bu miktarda karakter vardır.

ABCDEFGHIJKLMNOPQRSTUVWXYZ abcdefghijklmnopqrstuvwxyz 1234567890

26 + 26 + 10 = 62 karakter var gibi görünüyor

Bu, 8 uzunluğunda bir parolanın 62 ^ 8 kombinasyonuna sahip olduğu anlamına gelir.

218340105584896'ya eşit

Bu tek başına kulağa gelmesi yıllar sürecek gibi geliyor. Karakter sayısını 12'ye yükselttiğimizde ve özel karakterleri eklediğimizde (sadece shift - sayıya basarak aldığınız karakterlere bakarak 10 karakter daha olduğunu varsayalım) ne olacak?

72 ^ 12 = 19408409961765342806016 alırız

bu yıllar almak için yeterince büyük bir sayı.

27
stickman

Rainbow tablosu, önceden hesaplanmış karma değerleri tablosunun kompakt bir temsilidir. Rainbow tablosunun yapımı sırasında, birçok olası girdi denenir ve hash edilir. Tablo oluşturma sırasında karşılaşılan her girdiye bu tabloyla başarılı bir şekilde saldırılır ve başka hiçbir girdiye saldırılmaz. Karma değerlendirmesi, tablo oluşturma maliyetinin çoğunu yoğunlaştırır.

Yani, temelde, [~ # ~] n [~ # ~] şifreleri tersine çevirebilen bir Gökkuşağı tablosu oluşturmanın maliyeti kabaca bu [~ # ~] n [~ # ~] karma işlevi üzerinden parolalar - Rainbow tablosunun oluşturduğunuz nokta bir kez ve sonra kırmak için kullanabilirsiniz = birkaç şifreler. (Kesin olmak gerekirse, masa yapımı sırasındaki zincir çarpışmaları nedeniyle, maliyet aslında 1.7 * N, ancak şimdilik bunu görmezden gelelim.)

Bir keresinde SHA-1 ile bazı deneyimler kazandım. SHA-1 ile basit bir parola karması, yaklaşık 900 32 bit mantıksal veya aritmetik işlem gerektiren tek bir "blok" (MD5 gibi SHA-1, verileri 64 baytlık bloklarla işler) işleme maliyetine sahiptir. Intel Core2 x86 işlemcide optimize edilmiş bir uygulama bunu yaklaşık 500 saat döngüsünde yapabilir. Bununla birlikte, şifre saldırıları (ister doğrudan ister Rainbow tablo yapımı için olsun, önemli değil) oldukça paralel bir iştir, bu nedenle 128 bit kayıtlar sunan ve tek bir opcode'un gerçekleştirebileceği SSE2 talimatları kullanılabilir four Aynı anda 32 bit işlemler. SSE2'nin daha az çeşit operasyonu vardır (özellikle rotasyon sunmaz, sadece vardiya sunar), bu nedenle operasyon sayısı yaklaşık 1200'e yükselir; ancak, bazı koşullar altında, SSE2 ünitesi aynı anda birkaç opcod yürütecektir. Bu yüzden paralel olarak dört SHA-1 örneği için 800 saat döngüsüyle karşılaşıyoruz. Alt satır: Bilgisayarım dört çekirdeği 2,4 GHz hızında çalışan bir Intel Core2 Q6600. Her çekirdek SSE2 uygulamamı çalıştırabilir ve bunun sonucunda kabaca 48 milyon saniyede karma parolalar elde edilir.

Ayrıca çok küçük olmayan bir Nvidia grafik kartım var ve GPU, CUDA aracılığıyla rasgele kod çalıştırabilir. Bu 9800 GTX +, 128 çekirdeği 1.84 GHz'de çalışıyor. Her çekirdek, döngü başına bir 32 bit işlem gerçekleştirebilir (yüksek bir gecikme süresi vardır, ancak yüksek paralelleştirme sayesinde, döngü başına bu bir talimat verimi muhafaza edilebilir). Çekirdekler dönüşleri bilmez, bu nedenle her kod karma şifre başına 1200 saat döngüsünü kullanır. Toplam performans 160 milyon saniyede karma şifreli.

Bilgisayarım ve grafik kartım 2009 başlarında ve sıra dışı değil. Bugünlerde, 9800 GTX + 'dan yaklaşık üç kat daha hızlı şifreleri olan bir GPU bulabilirsiniz. Öyleyse, ortak bir bilgisayara sahip olan (1000 $ 'dan daha az maliyetli) bir saldırganın saniyede yarım milyar parola hash edebileceğini varsayalım.

Bu hızda, 8 alfasayısal karakterden (büyük ve küçük harfler ve rakamlar) oluşan tüm şifreler yaklaşık 5 gün içinde geçer. 1000 $ PC ile. MD5 kullanıyorsanız, işler yaklaşık% 30 daha hızlıdır (MD5, SHA-1'den biraz daha az işlem kullanır). İyi parola karma şemaları basit bir karma çağırma kullanmazlar: 2000 iç içe karma çağırma ile yinelenen karma kullanırlar: bu, saldırganın maliyetini aynı 2000 faktörü ile çarpar (böylece "5 gün" ü yaklaşık 28'e dönüştürür yıl, kelimenin tam anlamıyla "yaşlandıkça".

30
Thomas Pornin

Tek bir yineleme kullanarak çok basit bir karma için bir Rainbow tablosu oluşturmak ne kadar sürer? Bir saat sürer! İsterseniz daha az.

Yukarıdaki cevaplar tamamen doğru olsa da, bahsetmedikleri önemli bir gelişme var. Amazon EC2 ve diğer 'bulut bilişim' sunucu sağlayıcıları.

Bugün kredi kartı olan herkes aws.Amazon.com'a gidebilir ve yüz dolardan daha az bir süre için bir avuç EC2 spot örneği biriktirebilir. Veya iyi bir CUDA kodunuz varsa, Amazon'un daha pahalı "Cluster GPU" örneklerinden 50'sini iki NVIDIA Tesla M2050 grafik işlemcisi ile kiralayın.

(Havayolları gibi, Amazon'un fiyatlandırması farklıdır. Garantili kullanılabilirliğe sahip belirli bir EC2 sunucusuna ihtiyacınız varsa, fiyatlandırma daha yüksektir. Örneğin, saatte 0,68 USD karşılığında 8 sanal CPU çekirdeği olan bir "Hi-CPU Large" örneği alabilirsiniz. Çalışma saatleri dışında fazla tedarik izni ile aynı örneği satın almak istiyorsanız, bunu alabilirsiniz % 40 -% 50 indirim ile .)

Rainbow tabloları oluşturmak doğrusal performans artışı ile paralel olarak yapılabilir, yani 100 bilgisayar çalışırken tek bir bilgisayardan 100 kat daha hızlıdır.

Amazon örnek başına ücret almaz, örnek saat başına ücret alır. Bu nedenle bir saat için 1.000 sunucunun çalıştırılması, 1.000 saat boyunca bir sunucu ile aynı ücrete tabidir.

Rainbow tablo oluşturmanın paralel doğası, Amazon EC2 gibi servislerle birlikte, artık "ne kadar zaman alıyor" sorusunun artık olmadığı anlamına geliyor. "Daha az ödeme yapmak ve birkaç gün içinde almak yerine hızlı almak için ne kadar ödemeye hazırsınız?" Maliyet ve zaman farkı, Amazon'un 'normal' EC2 bulut sunucuları ile daha ucuz 'spot bulut sunucuları' arasındaki fiyat farkından kaynaklanmaktadır.

18
Jesper M

Basit bir 26 ^ 5 test çalıştırması kullanarak, Ruby saniyede 228488 MD5 çıkışı üreten bir ascii hex tablosu oluşturabildim. 11881376 girişlerin tümü 52 saniye sürdü Programımda herhangi bir iyileştirme yapmazsam, 62 ^ 8 listenizi oluşturmak için 26 hafta boyunca çalışmasını beklerdim.

Sorun alanını bölümlere ayırmak için her biri hiper iş parçacığı başına sekiz ayrı program çalıştırarak programımda muhtemelen iyileştirmeler yapabilirim. Her program çıktıyı kendi sürücüsüne kaydederse, IO bant genişliği için rekabet etmezler. 4-6 için aptal tek iş parçacıklı programımla karşılaştırıldığında dört ila altı hızlanma faktörü beklerdim. Eğer C'de yeniden yazacak olsaydım, başka bir 1.5 hızlanma faktörü bekleyebilirdim. (Belki daha fazla? Bir yandan basit bir program, diğer yandan, 13 bayt uzunluğunda, çalışma zamanında değiştirilmiş, muhtemelen Ruby string nesneleri) oluşturma ve yok etme ile karşılaştırıldığında çok daha az bellekte çalışacak ve elbette çöp toplama olmayacak.

Bir öğleden sonra çalışmasını beklerdim ve birkaç yüz dolarlık yeni donanım, iki hafta boyunca mal donanımında 62 ^ 8 tabloları bitirmeme izin verir.

Ve elbette, hiç kimse parolalarda tek çalıştırma MD5 kullanmıyor; sadece tek yönlü karma MD5 daha çok daha pahalı sonuç sonuçları ölçeklendirin. :)

6
sarnold

Bitcoin madencilik ağı karma oranı hesaplamalarımı Şifreleri nasıl güvenli bir şekilde nasıl elde edebilirim? - BT Güvenliği daha modern GPU kartlarına sahip kararlı kişilerin ham karmaşa açısından başarabilecekleri için bakın. Topluluk, Temmuz 2011 başında 11 Thash/s (11 * 10 ^ 12 karma/s) hızında çalışıyor ....

1
nealmcb