it-swarm-id.com

berapa lama untuk menghasilkan tabel Rainbow?

Saya sudah membaca tentang tabel Rainbow karena saya pikir mereka cukup menarik karena sebenarnya konsep yang cukup sederhana.

Ngomong-ngomong, saya bertanya-tanya, adakah yang benar-benar terlibat dalam menghasilkan satu? Bagaimana itu bisa dilakukan? Saya hanya tidak melihat bagaimana sebenarnya memungkinkan untuk menghasilkan setiap kombinasi dari setiap karakter.

Jika kita mengecualikan karakter khusus, ada sejumlah karakter ini.

ABCDEFGHIJKLMNOPQRSTUVWXYZ abcdefghijklmnopqrstuvwxyz 1234567890

Kedengarannya seperti ada 26 + 26 + 10 = 62 karakter

Itu berarti bahwa kata sandi dengan panjang 8 memiliki 62 ^ 8 kombinasi.

yang sama dengan 218340105584896

Itu saja terdengar seperti butuh waktu lama untuk menghasilkan. Bagaimana ketika kita menambah jumlah karakter menjadi 12 dan menambahkan karakter khusus (katakan ada 10 karakter lagi hanya dengan melihat karakter yang Anda dapatkan dengan menekan shift-number)?

Kami akan mendapatkan 72 ^ 12 = 19408409961765342806016

itu angka yang cukup besar untuk bisa bertahun-tahun.

27
stickman

Rainbow table adalah "hanya" representasi kompak dari tabel nilai hash yang dikomputasi. Selama pembangunan tabel Rainbow, banyak input yang mungkin dicoba dan di-hash. Setiap input yang telah ditemukan selama konstruksi tabel akan berhasil diserang dengan tabel itu, dan tidak ada yang lain. Evaluasi hash memusatkan sebagian besar biaya pembuatan tabel.

Jadi, pada dasarnya, biaya membangun tabel Rainbow yang dapat membalikkan [~ # ~] n [~ # ~] kata sandi kira-kira setara dengan biaya mencoba kata sandi tersebut [~ # ~] n [~ # ~] melalui fungsi hash - titik dari tabel Rainbow adalah Anda membuatnya satu kali dan kemudian dapat menggunakannya untuk memecah beberapa kata sandi. (Tepatnya, karena tabrakan berantai selama konstruksi tabel, biayanya sebenarnya lebih dekat ke 1.7 * N , tapi mari kita abaikan itu untuk saat ini. )

Saya pernah membuat beberapa pengalaman dengan SHA-1. Hash kata sandi sederhana dengan SHA-1 memiliki biaya pemrosesan satu "blok" tunggal (SHA-1, seperti MD5, memproses data dengan blok 64-byte), yang membutuhkan sekitar 900 operasi logis-atau-aritmatika 32-bit. Implementasi yang dioptimalkan pada prosesor Intel Core2 x86 dapat melakukannya dalam sekitar 500 siklus clock. Namun, serangan kata sandi (baik langsung atau untuk konstruksi tabel Rainbow, itu tidak masalah) adalah pekerjaan yang sangat paralel, sehingga orang dapat menggunakan instruksi SSE2 yang menawarkan register 128-bit, dan di mana satu opcode tunggal dapat melakukan empat operasi 32-bit secara bersamaan. SSE2 memiliki lebih sedikit jenis operasi yang tersedia (khususnya, ia tidak menawarkan rotasi, hanya bergeser), sehingga jumlah operasi naik menjadi sekitar 1200; tetapi, dalam beberapa kondisi, unit SSE2 akan menjalankan beberapa opcode secara bersamaan. Jadi kita berakhir dengan 800 siklus clock, untuk empat instance SHA-1 secara paralel. Intinya: PC saya adalah Intel Core2 Q6600, dengan empat core berjalan pada 2,4 GHz. Setiap inti dapat menjalankan implementasi SSE2 saya, menghasilkan kira-kira 48 juta kata sandi hash per detik.

Saya juga punya kartu grafis Nvidia yang tidak terlalu kecil, dan GPU dapat menjalankan kode arbitrary melalui CUDA . Ini adalah 9800 GTX +, dengan 128 core berjalan pada 1,84 GHz. Setiap core dapat menjalankan satu operasi 32-bit per siklus (ada latensi tinggi, tetapi, berkat paralelisasi yang tinggi, throughput satu-instruksi-per-siklus ini dapat dipertahankan). Core tidak tahu tentang rotasi, sehingga setiap kode akan menggunakan 1.200 siklus jam per kata sandi hash. Total kinerja adalah 160 juta kata sandi hash per detik.

PC dan kartu grafis saya berasal dari awal 2009 dan bukan top-of-line. Satu dapat menemukan saat ini, untuk beberapa ratus dolar, GPU yang akan hash kata sandi sekitar tiga kali lebih cepat daripada 9800 GTX + saya. Jadi mari kita asumsikan bahwa penyerang dengan PC biasa (yang harganya kurang dari $ 1000) dapat memotong setengah miliar kata sandi per detik.

Pada kecepatan itu, semua kata sandi dengan 8 karakter alfanumerik (huruf besar dan kecil, dan angka) dilalui dalam waktu sekitar 5 hari . Dengan $ 1000 PC. Jika Anda menggunakan MD5, semuanya sekitar 30% lebih cepat (MD5 menggunakan operasi sedikit lebih sedikit daripada SHA-1). Skema hashing kata sandi yang baik tidak menggunakan doa hash sederhana, meskipun: mereka menggunakan hashing iterated dengan, katakanlah, 2000 hash hashing: ini mengalikan biaya untuk penyerang dengan faktor 2000 yang sama (sehingga mengubah "5 hari" menjadi sekitar 28 tahun, secara harfiah "usia" seperti yang Anda katakan).

30
Thomas Pornin

Berapa lama untuk menghasilkan tabel Rainbow untuk hash yang sangat sederhana, hanya menggunakan satu iterasi? Dibutuhkan satu jam! Atau kurang, jika Anda menginginkannya.

Meskipun jawaban di atas sepenuhnya benar, ada satu perkembangan penting yang tidak mereka sebutkan. Amazon EC2 dan penyedia server 'cloud computing' lainnya.

Hari ini semua orang dengan kartu kredit dapat mengunjungi aws.Amazon.com dan mengumpulkan beberapa contoh EC2 spot , dengan harga kurang dari seratus dolar. Atau jika Anda memiliki kode CUDA yang bagus, sewalah 50 instance Amazon "Cluster GPU" yang lebih mahal dengan dua prosesor grafis NVIDIA Tesla M2050.

(Agak seperti maskapai penerbangan, Amazon memiliki harga berbeda. Jika Anda memerlukan server EC2 spesifik dengan ketersediaan terjamin, harga lebih tinggi. Misalnya, Anda bisa mendapatkan contoh "Hi-CPU Besar" dengan 8 core CPU virtual seharga 0,68 USD per jam Jika Anda bersedia membeli contoh yang sama dengan kelebihan izin pasokan di luar jam kerja, maka Anda bisa mendapatkannya dengan potongan harga 40% -50% .)

Membuat tabel Rainbow dapat dilakukan secara paralel dengan peningkatan kinerja linier, mis. Dengan 100 komputer yang berfungsi, 100 kali lebih cepat daripada komputer tunggal.

Amazon tidak membebankan biaya per instance, dikenakan biaya per instance-jam. Dengan demikian menjalankan 1.000 server untuk satu jam harganya sama sebagai satu server selama 1.000 jam.

Sifat paralel dari pembuatan tabel Rainbow, yang disatukan dengan layanan seperti Amazon EC2, berarti tidak ada lagi pertanyaan "berapa lama waktu yang dibutuhkan". Ada "berapa banyak yang Anda bayarkan untuk mendapatkannya cepat, dibandingkan membayar lebih sedikit dan mendapatkannya dalam beberapa hari?". Perbedaan dalam biaya & waktu terutama berasal dari diferensiasi harga Amazon antara instance EC2 'reguler' versus 'instance instance' yang lebih murah.

18
Jesper M

Dengan menggunakan uji coba 26 ^ 5 yang sederhana, saya dapat menghasilkan ascii hex table dalam Ruby yang menghasilkan 228488 keluaran MD5 per detik. Semua entri 11881376 membutuhkan waktu 52 detik pada Core i7 saya yang berusia 1,5 tahun Jika saya tidak melakukan perbaikan pada program saya, saya harapkan program ini berjalan selama 26 minggu untuk menghasilkan daftar 62 ^ 8 Anda.

Saya mungkin bisa melakukan perbaikan pada program saya dengan menjalankan delapan program terpisah, satu per hyperthread, untuk mempartisi ruang masalah. Jika setiap program menyimpan output ke drive sendiri, mereka tidak akan bersaing untuk bandwidth IO. Saya akan mengharapkan faktor empat hingga enam percepatan dibandingkan dengan program single-threaded bodoh saya untuk 4-6 minggu runtime. Jika saya menulis ulang dalam C, saya mungkin mengharapkan faktor percepatan 1,5 lainnya. (Mungkin lebih? Di satu sisi itu adalah program sederhana, di sisi lain, panjang array C 13 byte, dimodifikasi saat runtime, mungkin akan berjalan dalam memori yang jauh lebih sedikit dan tentu saja tidak ada pengumpulan sampah dibandingkan dengan membuat dan menghancurkan objek string Ruby.)

Saya berharap pekerjaan sore dan beberapa ratus dolar perlengkapan baru akan membiarkan saya menyelesaikan tabel 628 dua minggu pada perangkat keras komoditas.

Dan tentu saja, tidak ada yang menggunakan MD5 sekali pakai pada kata sandi; hanya skala hasil akhir saya dengan namun jauh lebih mahal hash satu arah Anda daripada MD5. :)

6
sarnold

Lihat kalkulasi tingkat hash jaringan penambangan bitcoin saya di Bagaimana cara mengamankan kata sandi hash? - Keamanan IT untuk apa yang dapat dicapai oleh orang-orang dengan kartu GPU lebih modern dalam hal hashing mentah. Komunitas berjalan pada 11 Thash/s (11 * 10 ^ 12 hash/s) pada awal Juli 2011 ....

1
nealmcb