it-swarm-id.com

Berapa lama hash harus benar-benar aman?

Apakah ada semacam aturan untuk menentukan seberapa besar hash seharusnya untuk memastikan keamanan (artinya persis satu pesan memetakan ke hash yang diberikan) dari suatu pesan? Sesuatu yang dapat diterapkan pada pesan apa pun, seperti nomor 32-bit atau 8 huruf ASCII kata sandi.

18
SecurityStudent

tepatnya satu pesan memetakan ke hash yang diberikan

Ini tidak mungkin karena prinsip pigeonhole. Selama pesan input ke fungsi hash dapat lebih besar dari hash itu sendiri, dijamin bahwa beberapa pesan saling bertabrakan dan memetakan ke hash yang sama. Ini normal dan bukan masalah bagi keamanan hash dengan sendirinya.

Anda hanya perlu memastikan bahwa fungsi hash begitu besar sehingga sengaja menemukan tabrakan tersebut (serangan tabrakan) secara komputasi tidak layak. Intisari hash n bit memiliki resistensi tabrakan n/2 bit. Untuk mencapai keamanan 128-bit terhadap serangan tabrakan, dengan demikian perlu untuk memiliki hash digest 256 bit. Ini, tentu saja, dengan asumsi hash aman secara kriptografis ( seperti SHA-256 ) untuk menghindari serangan yang mengambil jalan pintas dan dapat menemukan tabrakan lebih mudah daripada dengan kekerasan.

87
forest

Itu sangat tergantung pada apa yang ingin Anda capai. Pertama, seperti yang telah ditunjukkan oleh hutan, apa yang sebenarnya Anda inginkan dalam hal hanya satu peta input, satu hash - dalam kasus gerneral - tidak mungkin. Itu adalah mungkin dalam kasus-kasus khusus jika hash selama input, atau lebih lama. Karena Anda menyebutkan bilangan bulat 32-bit, memang ada hash integer-ke-integer 32-bit.
Namun perlu dicatat bahwa kemungkinan jumlah input sangat kecil pada 32 bit sehingga membangun tabel pencarian sebenarnya cukup layak (hanya membutuhkan 32GB, jadi pada komputer yang saya gunakan saat ini, tabel pencarian akan masuk sepenuhnya ke dalam RAM!). Tidak perlu dikatakan bahwa ini bukan, dan tidak mungkin aman, terlepas dari algoritma aktual apa yang Anda gunakan.

Jika Anda berencana untuk mengidentifikasi sesuatu (seperti file atau string) dengan hash, dan perusakan berbahaya bukan pertimbangan atau setidaknya bukan yang pertama Anda prioritas, maka Anda dapat mempertimbangkan 64 bit "cukup baik" dan 128 bit "benar-benar aman".
CRC32 yang bahkan tidak memberikan jaminan yang diberikan oleh hash yang aman secara kriptografis telah diterima sebagai "cukup baik" untuk membedakan hal-hal dan mengidentifikasi modifikasi modifikasi selama bertahun-tahun (dan 64 bit adalah urutan besarnya yang sangat berbeda dibandingkan dengan 32 !!!). ID 128 bit, dan dianggap "unik" padahal sebenarnya tidak. Tetapi untuk semua hal praktis, mereka.
Saya akan menambahkan GIT itu, yang digunakan antara lain untuk Host kernel Linux dan perangkat lunak yang relevan dengan keamanan yang digunakan dalam miliaran perangkat (sehingga menjadikannya target yang sangat menarik untuk serangan) ) menggunakan hash 128 bit untuk memisahkan barang dan mengamankan, tetapi sebenarnya 160 bit ...

Sekarang, jika perusakan berbahaya adalah masalah, Anda kemungkinan besar ingin aman = algoritma hash (jadi CRC tidak akan melakukan trik), tetapi Anda tidak tentu saja membutuhkan lebih banyak bit. Itu hanya tergantung pada apa yang ingin Anda lindungi, dan untuk berapa lama, dan terhadap jenis serangan apa.
Siphash atau Cityhash (secara default, dalam konfigurasi asli/umum, ada varian 32 dan 128 bit juga) hanya 64 bit. Mana yang sangat bagus, dan sangat aman jika Anda menggunakannya mis. untuk memastikan integritas beberapa pesan berukuran wajar yang Anda kirim melalui internet. Mungkinkah penyerang yang cukup kuat mungkin menemukan tabrakan dalam waktu 15-20 menit? Tentu. Tapi siapa yang peduli, setelah 15 menit 14 menit dan 59 detik sudah terlambat baginya untuk melakukan sesuatu dengannya.
Sebaliknya, tidak sama sekali baik jika Anda berencana menggunakannya untuk sesuatu yang disimpan untuk waktu yang lebih lama.

Dalam hal ini, Anda ingin setidaknya 128, lebih baik 160 bit, dan untuk mengatakan dengan kepastian yang masuk akal "benar-benar aman", Anda akan membutuhkan 256 bit atau ke atas, sekali lagi itu tergantung apa tepatnya yang Anda inginkan. AES-CGM, yang dianggap "cukup baik untuk semua orang" memiliki paling banyak 128 bit (hingga 96).

Apakah penyerang Anda dapat memilih dua input, sehingga serangan ulang tahun dapat diterapkan? Dalam hal ini, 128 bit hanya bernilai 64 bit (atau, jika proyeksi tahan, 42 bit pada komputer kuantum). Itu pasti agak sedikit dan tidak cukup untuk mengatakan "cukup baik", apalagi "benar-benar aman".

Apakah Anda hanya mengkhawatirkan preimage kedua serangan, mis. Anda harus memilih salah satu input? Dalam hal ini, 128 bit akan "sangat bagus", 160 bit akan "tidak bisa dipecahkan", dan 256 bit akan "tidak bisa dipecahkan". Kecuali jika algoritma itu sendiri rusak, yaitu.

tl; dr
Secara keseluruhan, jika Anda lebih suka jawaban tanpa syarat yang tidak mengharuskan Anda untuk mempertimbangkan terlebih dahulu, Anda harus mempertimbangkan jawaban itu menjadi 256 atau lebih .
256 bit berada dalam ranah "sangat mustahil", tetapi orang harus mempertimbangkan bahwa algoritma memang rusak seiring waktu, sehingga algoritma 256 bit mungkin hanya bernilai satu beban kerja 2 ^ 140 atau 2 ^ 150 dalam 10-20 tahun, tidak ada cara untuk mengetahui. Jika Anda agak paranoid, itu mungkin tidak cukup bagi Anda untuk mengatakan "benar-benar aman" (meskipun bagi kebanyakan orang saya kira itu masih cukup jalan).

Karenanya, tanpa mengetahui tingkat paranoia Anda, saya katakan "256 atau lebih". Beberapa bit tambahan tidak terlalu mahal, tetapi mereka memiliki dampak besar. Jadikan 384 atau bahkan 512, mengapa tidak. Jika algoritma 512-bit sangat, sangat signifikan rusak dan melemah menjadi beban kerja, katakanlah 2 ^ 300, dan komputer hyper-quantum-super-magic yang ditemukan oleh alien para-dimensional dapat, dengan menerapkan mustahil secara matematis dan fisik magic, lebih lanjut kurangi menjadi beban kerja 2 ^ 150 bit, maka Anda masih cukup bagus untuk melanjutkan.

12
Damon

Ukuran output dari fungsi hash menempatkan batas atas pada tingkat keamanannya. Tiga sifat utama yang diharapkan dimiliki fungsi hasrip kriptografis adalah resistensi terhadap benturan, preimage pertama, dan serangan preimage kedua.

Jika suatu algoritma memiliki n - keamanan bit, itu berarti bahwa tidak ada serangan yang merusak properti keamanan yang relevan yang akan membutuhkan lebih sedikit dari 2 n langkah (kira-kira dan rata-rata) untuk berhasil. Jika n cukup besar, maka kita dapat dipastikan bahwa tidak ada yang memiliki kekuatan komputasi yang cukup untuk menyerang suatu sistem.

Dari fungsi hash dengan n - output bit, kita dapat mengharapkan hingga n - keamanan bit ketika datang ke serangan preimage, tetapi tidak ada lebih tinggi. Seseorang dapat secara hipotetis mencari preimage dengan kekerasan dan berhasil setelah, rata-rata, 2 n mencoba.)

Namun, untuk resistensi tabrakan, masalah ulang tahun berarti Anda membutuhkan 2 * n bit, bukan n bit.

Kami sering bertujuan untuk keamanan 128-bit, sehingga itu berarti ukuran digest terkecil yang dapat diterima adalah 256 bit. Keamanan 128-bit membuat Anda memiliki margin keamanan yang cukup besar sehingga Anda mungkin masih aman menggunakan bit output yang lebih sedikit, tetapi menggunakan bit yang terlalu sedikit berisiko.

Catatan: Ini adalah batas atas. Meskipun algoritma seperti Murmur3, CityHash, xxHash, dan lainnya mungkin mengklaim berkualitas tinggi dan memiliki output yang panjang, mereka tidak memberikan keamanan yang berarti.

Tentunya jangan memilih algoritma hanya berdasarkan ukuran outputnya. Ukuran output hanya menentukan kekuatan teoritis maksimum hash. Bukan kekuatan sebenarnya.

Alih-alih memilih fungsi hash yang tahan benturan yang disetujui orang aman, mis. Blake-2, SHA-3, Skein, atau SHA-2.

Catatan 2: Jika Anda menggunakan sesuatu seperti SHA-512, maka Anda dapat memperlakukan algoritma seolah-olah input yang berbeda akan selalu menghasilkan output yang unik. Dengan probabilitas yang hampir sama dengan satu, Anda tidak akan mendapatkan duplikat intisari untuk set input dunia nyata.

Kemungkinan aktual melihat colliding digest bergantung pada berapa banyak pesan yang Anda coba hash dan berapa banyak kemungkinan output yang ada. Jumlah pesan berbeda yang bisa Anda coba hash secara alami terbatas karena kekuatan Anda untuk menghitung hash terbatas.

Fungsi hash tidak benar-benar injeksi, tetapi pengembang perangkat lunak dapat menggunakan fungsi hash besar yang tahan benturan dan memperlakukannya seolah-olah itu benar. Peluang untuk secara tidak sengaja menghasilkan satu atau lebih tabrakan secara teknis tidak nol, tetapi otak seseorang tidak dapat memahami betapa sangat mustahilnya itu.

4
Future Security

Jika kita harus memilikinya sehingga setiap pesan yang dicerna sesuai dengan satu pesan, maka pesan kita harus sebesar pesan terpanjang yang mungkin.

Kami menerima pesan sebagai bilangan bulat N-bit raksasa dan menghitung bilangan bulat N-bit lainnya menggunakan fungsi yang tidak bisa dibalik. Salah satu cara untuk melakukan ini adalah dengan mengenkripsi pesan dengan sandi simetris (yang kuncinya menentukan fungsi hashing).

Tentu saja, hash yang sepanjang pesan terpanjang tidak praktis, karena persyaratan utama untuk pesan intisari adalah hash berukuran kecil, yang seringkali jauh lebih kecil daripada pesan yang dicerna sendiri.

Namun, jika karena alasan apa pun Anda perlu mengubah pesan kecil menjadi kode yang bebas dari tabrakan, dan dari mana pesan tersebut sulit dipulihkan, hal di atas akan menjadi cara untuk melakukannya.

1
Kaz