it-swarm-id.com

Apa itu tabel Rainbow dan bagaimana mereka digunakan?

Di mana saya dapat menemukannya? Apakah ada pot emas di ujungnya?
Bagaimana saya melindungi mereka?


Dari proposal Area51

Pertanyaan ini adalah Pertanyaan Keamanan IT Minggu Ini.
Baca 09 Sep 2011 entri blog untuk lebih jelasnya atau kirim milik Anda sendiri Pertanyaan dalam Pekan ini.

149
AviD

Rainbow Tables biasanya dikacaukan dengan teknik lain yang lebih sederhana yang memanfaatkan waktu penyimpanan penyimpanan dalam pemulihan kata sandi: tabel hash.

Tabel hash dibuat dengan mem-hashing setiap kata dalam kamus kata sandi. Pasangan kata sandi hash disimpan dalam sebuah tabel, diurutkan berdasarkan nilai hash. Untuk menggunakan tabel hash, sederhana ambil hash dan lakukan pencarian biner di tabel untuk menemukan kata sandi asli, jika ada.

Tabel Pelangi lebih kompleks. Membangun tabel Rainbow membutuhkan dua hal: fungsi hashing dan fungsi reduksi. Fungsi hashing untuk satu set Rainbow Tables yang diberikan harus cocok dengan kata sandi hash yang ingin Anda pulihkan. Fungsi pengurangan harus mengubah hash menjadi sesuatu yang dapat digunakan sebagai kata sandi. Fungsi reduksi sederhana adalah untuk Base64 mengkodekan hash, kemudian memotongnya ke sejumlah karakter.

Tabel pelangi dibuat dari "rantai" dengan panjang tertentu: 100.000 misalnya. Untuk membangun rantai, pilih nilai benih acak. Kemudian terapkan fungsi hashing dan reduksi pada seed ini, dan outputnya, dan lanjutkan iterasi 100.000 kali. Hanya benih dan nilai akhir yang disimpan. Ulangi proses ini untuk membuat rantai sebanyak yang diinginkan.

Untuk memulihkan kata sandi menggunakan Tabel Pelangi, hash kata sandi menjalani proses di atas untuk panjang yang sama: dalam hal ini 100.000 tetapi setiap tautan dalam rantai dipertahankan. Setiap tautan dalam rantai dibandingkan dengan nilai akhir dari setiap rantai. Jika ada kecocokan, rantai dapat direkonstruksi, menjaga output dari masing-masing fungsi hashing dan output dari masing-masing fungsi reduksi. Rantai yang direkonstruksi itu akan berisi hash kata sandi yang dipermasalahkan serta kata sandi yang membuatnya.

Kekuatan dari tabel hash adalah bahwa memulihkan kata sandi cepat kilat (pencarian biner) dan orang yang membangun tabel hash dapat memilih apa yang masuk ke dalamnya, seperti 10.000 kata sandi teratas. Kelemahan dibandingkan dengan Rainbow Tables adalah bahwa tabel hash harus menyimpan setiap pasangan hash-password.

Rainbow Tables memiliki manfaat yang dapat digunakan oleh orang yang membuat tabel itu untuk memilih berapa banyak penyimpanan yang diperlukan dengan memilih jumlah tautan di setiap rantai. Semakin banyak tautan antara seed dan nilai akhir, semakin banyak kata sandi yang diambil. Salah satu kelemahannya adalah orang yang membuat rantai tidak memilih kata sandi yang mereka ambil sehingga Rainbow Tables tidak dapat dioptimalkan untuk kata sandi umum. Juga, pemulihan kata sandi melibatkan penghitungan rantai panjang hash, menjadikan pemulihan operasi yang mahal. Semakin lama rantai, semakin banyak kata sandi yang diambil di dalamnya, tetapi lebih banyak waktu diperlukan untuk menemukan kata sandi di dalamnya.

Tabel hash baik untuk kata sandi umum, Tabel Pelangi bagus untuk kata sandi sulit. Pendekatan terbaik adalah memulihkan sebanyak mungkin kata sandi menggunakan tabel hash dan/atau cracking konvensional dengan kamus kata sandi N teratas. Untuk yang masih ada, gunakan Rainbow Tables.

180
Crunge

Ada banyak penjelasan bagus tentang apa itu tabel Rainbow, yang satu ini Cara Kerja Rainbow Tables sangat baik. Juga artikel Wikipedia memiliki penjelasan yang sangat bagus juga. Untuk sedikit lebih dalam membaca makalah definitif pada subjek adalah Membuat Cryptanalytic Time-Memory Trade-Off Lebih Cepat .

Penjelasan sederhana dari Rainbow Tables adalah bahwa mereka menggunakan teknik pertukaran waktu memori. Berarti alih-alih mengambil nilai hash target dan kamus kata, lalu hashing setiap Word dan melakukan perbandingan dengan cepat (pendekatan brute force menggunakan sesuatu seperti John ), Anda malah hash semua nilai dalam kamus di muka (ini mungkin memakan waktu sangat lama tergantung pada ukuran kamus). Tapi begitu selesai, Anda bisa membandingkan hash sebanyak yang Anda inginkan dengan nilai pre hash di tabel Rainbow ini secara signifikan lebih cepat daripada menghitung hash lagi.

Penjelasan yang saya tulis di sini sebelumnya sebagai upaya untuk menjadi pendek adalah menyesatkan, karena tidak menjelaskan penggunaan reduksi yang digunakan tabel Rainbow. Untuk penjelasan yang lebih baik sampai saya menulis ulang bit ini lihat @ Crunge answer .

Anda dapat membuat tabel Rainbow sendiri menggunakan aplikasi seperti RainbowCrack atau Anda dapat mengunduhnya dari sumber seperti Grup Shmoo , Tabel Rainbow Gratis proyek situs web, Ophcrack proyek dan banyak tempat lain tergantung pada jenis hash yang Anda perlukan untuk tabel.

Untuk melindungi terhadap serangan berbasis Rainbow Table metode yang paling efektif untuk memerangi itu adalah untuk memastikan bahwa setiap hash dalam sistem adalah asin . Ini membuat tabel Rainbow yang dihasilkan sebelumnya menjadi tidak berguna dan akan berarti penyerang harus membuat seperangkat tabel kustom untuk digunakan terhadap hash yang ditargetkan, yang hanya akan mungkin jika mereka tahu garam.

15
Mark Davidson

Tujuan dan relevansi

Tabel pelangi membantu memecahkan kata sandi yang sulit, yaitu yang bahkan tidak dapat ditemukan di kamus besar. Kata sandi secara historis disimpan sebagai hash dalam database, dan itulah yang efektif terhadap tabel Rainbow: buat tabel Rainbow tunggal (lambat) dan jalankan sejumlah database penuh hash terhadapnya (cepat).

Saat ini, semakin banyak sistem menggunakan algoritma penyimpanan kata sandi yang tepat seperti Bcrypt, Scrypt atau Argon2. Lihat: Bagaimana cara mengamankan kata sandi [toko]? Algoritma itu tidak lagi "rentan" terhadap tabel Rainbow: karena setiap hash unik, bahkan jika kata sandi sama, tabel Rainbow tidak lagi berfungsi.

Itu sebabnya tabel Rainbow tidak populer saat ini. Bahkan jika sesuatu yang modern seperti Argon2 tidak digunakan, pengembang saat ini biasanya tahu bahwa mereka setidaknya harus menggunakan garam. Itu sudah cukup untuk membuat meja Rainbow tidak berguna.

Bagaimana mereka bekerja

Membuat tabel

Bayangkan kita membuat tabel Rainbow dengan hanya dua rantai, masing-masing panjang 5. Tabel Rainbow adalah untuk fungsi hash fiksi MD48, yang menghasilkan 48 bit (hanya 12 karakter heksadesimal). Saat membangun rantai, kita melihat ini:

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

Kita mulai dengan 0 karena ini adalah rantai pertama (kita hanya perlu beberapa nilai untuk memulai). Ketika kita hash ini dengan MD48, itu berubah menjadi cfcd208495d5. Sekarang kita menerapkan fungsi "perkecil" yang pada dasarnya memformat hash ini kembali menjadi kata sandi, dan kita berakhir dengan "z". Ketika kita hash itu lagi, kita mendapatkan fbade9e36a3f, lalu kurangi lagi dan dapatkan renjaj820. Ada beberapa siklus lagi, dan hasil akhirnya adalah WLgOSj.

Sama untuk rantai kedua. Kami baru mulai dengan nilai lain dan melakukan hal yang sama. Ini berakhir dengan 0uUoAD.

Meja pelangi lengkap kami sekarang adalah ini:

WLgOSj => 0
0uUoAD => 1

Hanya itu yang harus Anda simpan.

Mencari hash

Katakanlah kita menemukan hash online, 7668b2810262. Mari kita crack menggunakan meja kita!

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

Untuk bermain-main dengan itu sendiri, contoh di atas dibuat menggunakan ini Python script: https://Gist.github.com/lgommans/83cbb74a077742be3b31d33658f65adb

Properti penskalaan

Pendeknya:

  • Pencarian cepat berarti tabel yang lebih besar, dengan asumsi cakupan tetap sama.
  • Cakupan yang lebih baik berarti pencarian yang lebih lambat, atau tabel yang lebih besar.
  • Tabel yang lebih kecil berarti pencarian yang lebih lambat, atau cakupan yang lebih buruk.

Bagian berikut mengasumsikan waktu per pengurangan hash + adalah 1µs, dan gagal menghitung tabrakan. Ini semua adalah angka rata-rata, dimaksudkan sebagai contoh dan bukan nilai yang tepat.

Waktu pencarian

Jika operasi pengurangan hash + membutuhkan mikrodetik, maka menghasilkan tabel dengan sejuta rantai dan 10.000 reduksi per rantai akan memakan waktu sekitar 3 jam:
chain_length × chain_count / reductions_per_second / seconds_per_hour
= 10 000 × 1 000 000 / 1 000 000 / 3600 = 2,8 jam.

Melakukan pencarian di tabel itu memakan waktu rata-rata 10 milidetik. Ini karena kita biasanya harus melalui chain_length/2 pengurangan sebelum kita menemukan rantai mana yang berisi hash. Sebagai contoh, kita mungkin harus melakukan 3.000 pengurangan hash sebelum kita menemukan nilai yang ada di dalam tabel. Selanjutnya, kita harus melakukan ulang rantai itu dari awal sampai kita menemukan nilai yang cocok. Jika kita hanya perlu melakukan 3000 untuk menemukannya di tabel kita, maka kita harus melakukan 7000 pengurangan dari awal untuk sampai ke titik yang tepat dalam rantai. Pada dasarnya, kami melakukan banyak operasi ketika melihat ke atas saat menghasilkan rantai tunggal. Oleh karena itu, waktu pencarian adalah 10.000 kali per detik, yang berarti sepuluh milidetik (atau satu detik, jika Anda mau).

Persyaratan penyimpanan

Saat Anda ingin membuat tabel pencarian lengkap dan cepat untuk fungsi hash, bahkan MD5, Anda masih membutuhkan penyimpanan seratus miliar miliar terabyte. Itu tidak terlalu membantu. Tetapi bagaimana jika kita hanya ingin menutupi kata sandi huruf kecil hingga 10 karakter?

Jika kita ingin menghabiskan paling banyak 30 detik mencari hash, dan dengan asumsi kita membutuhkan 1 mikrodetik (sepersejuta detik) per siklus hash + kurangi, maka kita dapat memiliki panjang rantai: 1 million × 30 = 30 juta. Ada 2610 (atau 1014) kemungkinan password huruf kecil 10 karakter, dan per rantai kami mencakup 30 juta nilai. Itu membuat kita dengan 4 juta rantai. Kita tahu bahwa setiap rantai hanya memiliki nilai awal dan akhir yang disimpan, dan bahwa nilainya masing-masing 10 karakter. Jadi 2 × 10 × 4 million = 76 data MIB.

Membuat tabel dengan mengulangi semua kata sandi 10 karakter membutuhkan waktu yang lama: 30 detik per rantai, kali 4 juta rantai adalah sekitar 91 tahun. Namun, banyak orang akan tertarik pada tabel seperti itu, jadi dengan mengumpulkan 1092 CPU (= 91 × 12), hanya dibutuhkan 1 bulan. Ini menunjukkan betapa kecilnya tabel tersebut dapat dibandingkan dengan ruang kata sandi yang tercakup: pencarian hanya membutuhkan waktu 30 detik dan Anda harus menyimpan hanya 76MiB data.

Kesimpulan

Rainbow table dapat dianggap sebagai trade-off time-memory : satu menyimpan hanya sebagian kecil dari tabel dan memulihkannya melalui beberapa perhitungan tambahan pada waktu pencarian. Ini adalah bagian dari alasan mengapa garam, atau lebih tepatnya, algoritma penyimpanan kata sandi yang baik seperti Scrypt atau Argon2 penting untuk menjaga keamanan kata sandi. Tabel Rainbow hanya dapat memulihkan kata sandi asin jika tabel tersebut berisi entri yang cukup besar untuk mengandung garam dan kata sandi, yang akan sangat tidak efisien dan mengalahkan seluruh tujuan.

Perhatikan bahwa hal serupa berlaku dengan enkripsi: ketika orang mengenkripsi file dengan kata sandi, tabel Rainbow dapat dibangun untuk memecahkan file. Katakanlah perangkat lunak menggunakan AES, dan blok pertama file harus didekripsi menjadi "passwordcorrect" menggunakan kata sandi yang diberikan pengguna, maka tabel Rainbow akan menggunakan AES alih-alih fungsi hash.

Setiap kali Anda menangani kata sandi (rahasia yang kekuatannya tidak diketahui, dan terutama jika pengguna dapat menggunakannya kembali), selalu jalankan melalui algoritma penyimpanan kata sandi yang tepat (lambat) untuk membuatnya lambat dan unik untuk di-crack.

7
Luc