Bagaimana cara menghasilkan hash SHA1 acak untuk digunakan sebagai ID di node.js?

138

Saya menggunakan baris ini untuk menghasilkan id sha1 untuk node.js:

crypto.createHash('sha1').digest('hex');

Masalahnya adalah itu mengembalikan id yang sama setiap saat.

Apakah mungkin membuatnya menghasilkan id acak setiap kali sehingga saya dapat menggunakannya sebagai id dokumen database?

ajsie
sumber
2
Jangan gunakan sha1. Itu tidak lagi dianggap aman (tahan benturan). Inilah mengapa jawaban naomik lebih baik.
Niels Abildgaard

Jawaban:

62

Lihat di sini: Bagaimana cara menggunakan Crypto node.js untuk membuat hash HMAC-SHA1? Saya akan membuat hash dari stempel waktu saat ini + nomor acak untuk memastikan keunikan hash:

var current_date = (new Date()).valueOf().toString();
var random = Math.random().toString();
crypto.createHash('sha1').update(current_date + random).digest('hex');
Gabi Purcaru
sumber
45
Untuk pendekatan yang lebih baik, lihat jawaban @ naomik di bawah ini.
Gabi Purcaru
2
Ini juga jawaban yang bagus Gabi, dan hanya sedikit lebih cepat, sekitar 15%. Kerja bagus keduanya! Saya sebenarnya suka melihat Date () di dalam garam, ini memberi pengembang keyakinan yang mudah bahwa ini akan menjadi nilai unik di semua kecuali situasi komputasi paralel yang paling gila. Saya tahu itu konyol dan randomBytes (20) akan menjadi unik, tetapi itu hanya kepercayaan yang dapat kita miliki karena kita mungkin tidak terbiasa dengan internal dari generasi acak perpustakaan lain.
Dmitri R117
647

243.583.606.221.817.150.598.111.409x lebih banyak entropi

Saya akan merekomendasikan menggunakan crypto.randomBytes . Tidak sha1, tapi untuk tujuan id, ini lebih cepat, dan sama "acaknya".

var id = crypto.randomBytes(20).toString('hex');
//=> f26d60305dae929ef8640a75e70dd78ab809cfe9

String yang dihasilkan akan dua kali lebih panjang dari byte acak yang Anda hasilkan; setiap byte yang dikodekan menjadi hex adalah 2 karakter. 20 byte akan menjadi 40 karakter hex.

Menggunakan 20 byte, kami memiliki 256^20atau 1.461.501.637.330.902.918.203.684.832.716.283.019.655.932.542.976 nilai keluaran unik. Ini identik dengan kemungkinan output SHA1 160-bit (20-byte).

Mengetahui hal ini, tidak terlalu berarti bagi kami untuk shasumbyte acak kami. Ini seperti melempar dadu dua kali tetapi hanya menerima lemparan kedua; Apa pun yang terjadi, Anda memiliki 6 kemungkinan hasil setiap lemparan, jadi lemparan pertama sudah cukup.


Mengapa ini lebih baik?

Untuk memahami mengapa ini lebih baik, pertama-tama kita harus memahami cara kerja fungsi hashing. Fungsi hashing (termasuk SHA1) akan selalu menghasilkan keluaran yang sama jika masukan yang sama diberikan.

Katakanlah kita ingin menghasilkan ID tetapi input acak kita dihasilkan oleh lemparan koin. Kami memiliki "heads"atau"tails"

% echo -n "heads" | shasum
c25dda249cdece9d908cc33adcd16aa05e20290f  -

% echo -n "tails" | shasum
71ac9eed6a76a285ae035fe84a251d56ae9485a4  -

Jika "heads"muncul lagi, output SHA1 akan sama seperti saat pertama kali

% echo -n "heads" | shasum
c25dda249cdece9d908cc33adcd16aa05e20290f  -

Ok, jadi lemparan koin bukanlah generator ID acak yang bagus karena kita hanya memiliki 2 kemungkinan keluaran.

Jika kami menggunakan cetakan 6-sisi standar, kami memiliki 6 kemungkinan input. Tebak berapa banyak kemungkinan keluaran SHA1? 6!

input => (sha1) => output
1 => 356a192b7913b04c54574d18c28d46e6395428ab
2 => da4b9237bacccdf19c0760cab7aec4a8359010b0
3 => 77de68daecd823babbb58edb1c8e14d7106e83bb
4 => 1b6453892473a467d07372d45eb05abc2031647a
5 => ac3478d69a3c81fa62e60f5c3696165a4e5e6ac4
6 => c1dfd96eea8cc2b62785275bca38ac261256e278

Sangat mudah untuk menipu diri sendiri dengan berpikir hanya karena output dari fungsi kita terlihat sangat acak, bahwa itu adalah sangat acak.

Kami berdua setuju bahwa lemparan koin atau dadu 6 sisi akan menjadi generator id acak yang buruk, karena kemungkinan hasil SHA1 kami (nilai yang kami gunakan untuk ID) sangat sedikit. Tetapi bagaimana jika kita menggunakan sesuatu yang memiliki keluaran lebih banyak? Seperti stempel waktu dengan milidetik? Atau JavaScript Math.random? Atau bahkan kombinasi keduanya ?!

Mari kita hitung berapa banyak id unik yang akan kita dapatkan ...


Keunikan stempel waktu dengan milidetik

Saat menggunakan (new Date()).valueOf().toString(), Anda mendapatkan nomor 13 karakter (misalnya, 1375369309741). Namun, karena ini adalah nomor yang diperbarui secara berurutan (sekali per milidetik), hasilnya hampir selalu sama. Mari lihat

for (var i=0; i<10; i++) {
  console.log((new Date()).valueOf().toString());
}
console.log("OMG so not random");

// 1375369431838
// 1375369431839
// 1375369431839
// 1375369431839
// 1375369431839
// 1375369431839
// 1375369431839
// 1375369431839
// 1375369431840
// 1375369431840
// OMG so not random

Agar adil, untuk tujuan perbandingan, dalam satu menit (waktu pelaksanaan operasi yang murah hati), Anda akan memiliki 60*1000atau 60000unik.


Keunikan Math.random

Sekarang, saat menggunakan Math.random, karena cara JavaScript mewakili bilangan titik mengambang 64-bit, Anda akan mendapatkan nomor dengan panjang antara 13 dan 24 karakter. Hasil yang lebih panjang berarti lebih banyak digit yang berarti lebih banyak entropi. Pertama, kita perlu mencari tahu panjang mana yang paling memungkinkan.

Skrip di bawah ini akan menentukan panjang mana yang paling memungkinkan. Kami melakukan ini dengan menghasilkan 1 juta nomor acak dan menambah penghitung berdasarkan .lengthjumlah masing-masing nomor.

// get distribution
var counts = [], rand, len;
for (var i=0; i<1000000; i++) {
  rand = Math.random();
  len  = String(rand).length;
  if (counts[len] === undefined) counts[len] = 0;
  counts[len] += 1;
}

// calculate % frequency
var freq = counts.map(function(n) { return n/1000000 *100 });

Dengan membagi setiap penghitung dengan 1 juta, kita mendapatkan probabilitas panjang angka yang dikembalikan Math.random.

len   frequency(%)
------------------
13    0.0004  
14    0.0066  
15    0.0654  
16    0.6768  
17    6.6703  
18    61.133  <- highest probability
19    28.089  <- second highest probability
20    3.0287  
21    0.2989  
22    0.0262
23    0.0040
24    0.0004

Jadi, meskipun itu tidak sepenuhnya benar, mari bermurah hati dan katakan Anda mendapatkan keluaran acak sepanjang 19 karakter; 0.1234567890123456789. Karakter pertama akan selalu 0dan ., jadi kami hanya mendapatkan 17 karakter acak. Ini menyisakan 10^17 +1(untuk kemungkinan 0; lihat catatan di bawah) atau 100.000.000.000.000.001 unik.


Jadi, berapa banyak masukan acak yang dapat kita hasilkan?

Oke, kami menghitung jumlah hasil untuk stempel waktu milidetik dan Math.random

      100,000,000,000,000,001 (Math.random)
*                      60,000 (timestamp)
-----------------------------
6,000,000,000,000,000,060,000

Itu adalah satu mati 6.000.000.000.000.000.000.060.000 sisi. Atau, untuk membuat angka ini lebih mudah dicerna, ini kira - kira sama dengan angka

input                                            outputs
------------------------------------------------------------------------------
( 1×) 6,000,000,000,000,000,060,000-sided die    6,000,000,000,000,000,060,000
(28×) 6-sided die                                6,140,942,214,464,815,497,21
(72×) 2-sided coins                              4,722,366,482,869,645,213,696

Kedengarannya cukup bagus, bukan? Nah, mari kita cari tahu ...

SHA1 menghasilkan nilai 20-byte, dengan kemungkinan hasil 256 ^ 20. Jadi kami benar-benar tidak menggunakan SHA1 secara maksimal. Berapa banyak yang kita gunakan?

node> 6000000000000000060000 / Math.pow(256,20) * 100

Stempel waktu milidetik dan Math.random hanya menggunakan 4,11e-27 persen dari potensi 160-bit SHA1!

generator               sha1 potential used
-----------------------------------------------------------------------------
crypto.randomBytes(20)  100%
Date() + Math.random()    0.00000000000000000000000000411%
6-sided die               0.000000000000000000000000000000000000000000000411%
A coin                    0.000000000000000000000000000000000000000000000137%

Kucing suci, bung! Lihat semua angka nol itu. Jadi seberapa jauh lebih baik itu crypto.randomBytes(20)? 243.583.606.221.817.150.598.111.409 kali lebih baik.


Catatan tentang +1dan frekuensi nol

Jika Anda bertanya-tanya tentang +1, itu mungkin untuk Math.randommengembalikan 0yang berarti ada 1 lagi kemungkinan hasil unik yang harus kami perhitungkan.

Berdasarkan pembahasan yang terjadi di bawah ini, saya penasaran dengan frekuensi yang 0akan muncul. Ini sedikit script random_zero.js,, saya buat untuk mendapatkan beberapa data

#!/usr/bin/env node
var count = 0;
while (Math.random() !== 0) count++;
console.log(count);

Kemudian, saya menjalankannya dalam 4 utas (saya memiliki prosesor 4-inti), menambahkan output ke file

$ yes | xargs -n 1 -P 4 node random_zero.js >> zeroes.txt

Jadi ternyata a 0tidak sulit didapat. Setelah 100 nilai dicatat, rata-rata adalah

1 dari 3.164.854.823 randoms adalah 0

Keren! Diperlukan lebih banyak penelitian untuk mengetahui apakah angka itu setara dengan distribusi seragam Math.randomimplementasi v8

Terima kasih
sumber
2
Silakan lihat pembaruan saya; bahkan satu milidetik adalah waktu yang lama di javascript land lightspeed! Pada catatan yang lebih serius, 10 digit pertama dari nomor tersebut tetap sama setiap detik; inilah yang membuat Dateburuk dalam menghasilkan benih yang baik.
Terima kasih
1
Benar. Meskipun saya benar-benar hanya memasukkan yang memberikan kontribusi tertinggi ke jawaban lain untuk menunjukkan bahwa 20 byte acak masih mendominasi dalam hal entropi. Saya tidak berpikir Math.randomakan pernah menghasilkan0.
Terima kasih
8
Suara positif 14x lebih banyak daripada jawaban yang diterima ... tapi siapa yang menghitung? :)
zx81
2
@ moka, dadu adalah bentuk jamak dari dadu . Saya menggunakan bentuk tunggal.
Terima kasih
2
crypto.randomBytespasti cara untuk pergi ^^
Terima kasih
28

Lakukan juga di browser!

EDIT: ini tidak benar-benar sesuai dengan aliran jawaban saya sebelumnya. Saya meninggalkannya di sini sebagai jawaban kedua untuk orang-orang yang mungkin ingin melakukan ini di browser.

Anda dapat melakukan ini di sisi klien di browser modern, jika Anda mau

// str byteToHex(uint8 byte)
//   converts a single byte to a hex string 
function byteToHex(byte) {
  return ('0' + byte.toString(16)).slice(-2);
}

// str generateId(int len);
//   len - must be an even number (default: 40)
function generateId(len = 40) {
  var arr = new Uint8Array(len / 2);
  window.crypto.getRandomValues(arr);
  return Array.from(arr, byteToHex).join("");
}

console.log(generateId())
// "1e6ef8d5c851a3b5c5ad78f96dd086e4a77da800"

console.log(generateId(20))
// "d2180620d8f781178840"

Persyaratan browser

Browser    Minimum Version
--------------------------
Chrome     11.0
Firefox    21.0
IE         11.0
Opera      15.0
Safari     5.1
Terima kasih
sumber
3
Number.toString(radix)tidak selalu menjamin nilai 2 digit (misalnya: (5).toString(16)= "5", bukan "05"). Ini tidak masalah kecuali Anda bergantung pada hasil akhir Anda agar memiliki lenpanjang karakter yang tepat . Dalam hal ini Anda dapat menggunakan return ('0'+n.toString(16)).slice(-2);di dalam fungsi peta Anda.
The Brawny Man
1
Kode bagus, terima kasih. Hanya ingin menambahkan: jika Anda akan menggunakannya untuk nilai idatribut, pastikan ID dimulai dengan huruf: [A-Za-z].
GijsjanB
Jawaban luar biasa (dan komentar) - sangat kami hargai karena Anda juga menyertakan persyaratan browser dalam jawabannya!
kevlarr
Persyaratan browser salah. Array.from () tidak didukung di IE11.
T_Conroy
1
Itu diambil dari wiki pada saat jawaban ini. Anda dapat mengedit jawaban ini jika Anda mau, tetapi siapa yang benar-benar peduli dengan IE? Jika Anda mencoba untuk mendukungnya, Anda harus mem-polyfill setengah dari JavaScript ...
Terima kasih
0

Menggunakan cryptoadalah pendekatan yang baik karena ini adalah modul asli dan stabil, tetapi ada beberapa kasus di mana Anda dapat menggunakan bcryptjika Anda ingin membuat hash yang sangat kuat dan aman. Saya menggunakannya untuk kata sandi, ia memiliki banyak teknik untuk hashing, membuat salt, dan membandingkan kata sandi.

Teknik 1 (menghasilkan salt dan hash pada pemanggilan fungsi terpisah)

const salt = bcrypt.genSaltSync(saltRounds);
const hash = bcrypt.hashSync(myPlaintextPassword, salt);

Teknik 2 (membuat garam dan hash secara otomatis):

const hash = bcrypt.hashSync(myPlaintextPassword, saltRounds);

Untuk contoh lainnya, Anda dapat memeriksa di sini: https://www.npmjs.com/package/bcrypt

Eduard
sumber