Setelah membaca berbagai sumber tentang kekuatan kata sandi, saya mencoba membuat algoritma yang akan memberikan perkiraan kasar tentang seberapa banyak entropi kata sandi.

Saya mencoba membuat algoritma yang selengkap mungkin. Pada titik ini saya hanya memiliki pseudocode, tetapi algoritma mencakup yang berikut:

• panjang kata sandi
• karakter yang diulang
• pola (logis)
• ruang karakter berbeda (LC, UC, Numerik, Khusus, Diperpanjang)
• serangan kamus

Ini TIDAK mencakup yang berikut, dan HARUS menutupinya BAIK (walaupun tidak sempurna):

• pemesanan (kata sandi dapat dipesan secara ketat oleh output dari algoritma ini)
• pola (spasial)

Adakah yang bisa memberikan beberapa wawasan tentang apa algoritma ini mungkin lemah? Secara khusus, adakah yang bisa memikirkan situasi di mana memasukkan kata sandi ke algoritma akan melebih - lebihkan kekuatannya? Meremehkan kurang menjadi masalah.

Algoritma:

// the password to test
password = ?
length = length(password)

// unique character counts from password (duplicates discarded)
uqlca = number of unique lowercase alphabetic characters in password
uquca = number of uppercase alphabetic characters
uqd   = number of unique digits
uqsp  = number of unique special characters (anything with a key on the keyboard)
uqxc  = number of unique special special characters (alt codes, extended-ascii stuff)

// algorithm parameters, total sizes of alphabet spaces
Nlca = total possible number of lowercase letters (26)
Nuca = total uppercase letters (26)
Nd   = total digits (10)
Nsp  = total special characters (32 or something)
Nxc  = total extended ascii characters that dont fit into other categorys (idk, 50?)

// algorithm parameters, pw strength growth rates as percentages (per character)
flca = entropy growth factor for lowercase letters (.25 is probably a good value)
fuca = EGF for uppercase letters (.4 is probably good)
fd   = EGF for digits (.4 is probably good)
fsp  = EGF for special chars (.5 is probably good)
fxc  = EGF for extended ascii chars (.75 is probably good)

// repetition factors.  few unique letters == low factor, many unique == high
rflca = (1 - (1 - flca) ^ uqlca)
rfuca = (1 - (1 - fuca) ^ uquca)
rfd   = (1 - (1 - fd  ) ^ uqd  )
rfsp  = (1 - (1 - fsp ) ^ uqsp )
rfxc  = (1 - (1 - fxc ) ^ uqxc )

// digit strengths
strength =
( rflca * Nlca + 
  rfuca * Nuca +
  rfd   * Nd   +
  rfsp  * Nsp  +
  rfxc  * Nxc    ) ^ length

entropybits = log_base_2(strength)

Beberapa input dan output entropy_bits yang diinginkan dan aktual:

INPUT           DESIRED        ACTUAL
aaa             very pathetic  8.1
aaaaaaaaa       pathetic       24.7
abcdefghi       weak           31.2
H0ley$Mol3y_    strong         72.2
s^fU¬5ü;y34G<   wtf            88.9
[a^36]*         pathetic       97.2
[a^20]A[a^15]*  strong         146.8
xkcd1**         medium         79.3
xkcd2**         wtf            160.5

* these 2 passwords use shortened notation, where [a^N] expands to N a's.
** xkcd1 = "Tr0ub4dor&3", xkcd2 = "correct horse battery staple"

Algoritma tidak menyadari (dengan benar) bahwa meningkatkan ukuran alfabet (bahkan satu digit) sangat memperkuat kata sandi yang panjang, seperti yang ditunjukkan oleh perbedaan dalam entropy_bits untuk kata sandi ke-6 dan ke-7, yang keduanya terdiri dari 36 a, tetapi yang kedua adalah a. dikapitalisasi. Namun, mereka tidak memperhitungkan fakta bahwa memiliki kata sandi 36 a bukanlah ide yang baik, itu mudah rusak dengan cracker kata sandi yang lemah (dan siapa pun yang melihat Anda mengetiknya akan melihatnya) dan algoritma tidak mencerminkan bahwa .

Namun, hal itu mencerminkan fakta bahwa xkcd1 adalah kata sandi yang lemah dibandingkan dengan xkcd2, walaupun memiliki kepadatan kompleksitas yang lebih besar (apakah ini bahkan masalah?).

Bagaimana saya dapat meningkatkan algoritma ini?

Adendum 1

Serangan kamus dan serangan berbasis pola tampaknya menjadi hal besar, jadi saya akan berusaha keras untuk mengatasinya.

Saya bisa melakukan pencarian komprehensif melalui kata sandi untuk kata-kata dari daftar kata dan mengganti kata-kata dengan token yang unik untuk kata-kata yang diwakilinya. Token kata kemudian akan diperlakukan sebagai karakter dan memiliki sistem bobotnya sendiri, dan akan menambah bobotnya sendiri ke kata sandi. Saya memerlukan beberapa parameter algoritma baru (saya akan memanggil mereka lw, Nw ~ = 2 ^ 11, fw ~ = .5, dan rfw) dan saya akan memasukkan bobot ke dalam kata sandi seperti saya akan salah satu dari yang lain beban.

Pencarian kata ini dapat secara khusus dimodifikasi untuk mencocokkan huruf kecil dan besar serta penggantian karakter umum, seperti E dengan 3. Jika saya tidak menambah bobot ekstra untuk kata-kata yang cocok seperti itu, algoritma akan meremehkan kekuatan mereka sedikit. atau dua per kata, yang OK. Kalau tidak, aturan umum akan, untuk setiap pertandingan karakter yang tidak sempurna, berikan sedikit kata bonus.

Saya kemudian dapat melakukan pengecekan pola sederhana, seperti pencarian untuk run karakter berulang dan tes turunan (mengambil perbedaan antara masing-masing karakter), yang akan mengidentifikasi pola seperti 'aaaaa' dan '12345', dan mengganti setiap pola yang terdeteksi dengan pola token, unik untuk pola dan panjangnya. Parameter algoritmik (khususnya, entropi per pola) dapat dihasilkan dengan cepat berdasarkan pola.

Pada titik ini, saya akan mengambil kata sandi yang panjang. Setiap kata token dan pola token akan dihitung sebagai satu karakter; setiap token akan menggantikan karakter yang diwakili secara simbolis.

Saya membuat semacam notasi pola, tetapi itu mencakup panjang pola l, urutan pola o, dan elemen dasar b. Informasi ini dapat digunakan untuk menghitung bobot acak untuk setiap pola. Saya akan melakukan sesuatu yang lebih baik dalam kode aktual.

Contoh yang Dimodifikasi:

Password:          1234kitty$$$$$herpderp
Tokenized:         1 2 3 4 k i t t y $ $ $ $ $ h e r p d e r p
Words Filtered:    1 2 3 4 @W5783 $ $ $ $ $ @W9001 @W9002
Patterns Filtered: @P[l=4,o=1,b='1'] @W5783 @P[l=5,o=0,b='$'] @W9001 @W9002

Breakdown:         3 small, unique words and 2 patterns
Entropy:           about 45 bits, as per modified algorithm

Password:          correcthorsebatterystaple
Tokenized:         c o r r e c t h o r s e b a t t e r y s t a p l e
Words Filtered:    @W6783 @W7923 @W1535 @W2285

Breakdown:         4 small, unique words and no patterns
Entropy:           43 bits, as per modified algorithm

Semantik yang tepat tentang bagaimana entropi dihitung dari pola siap untuk dibahas. Saya sedang memikirkan sesuatu seperti:

entropy(b) * l * (o + 1) // o will be either zero or one

Algoritma yang dimodifikasi akan menemukan kekurangan dengan dan mengurangi kekuatan setiap kata sandi dalam tabel asli, dengan pengecualian s^fU¬5ü;y34G<, yang tidak mengandung kata atau pola.

Lampiran A pada halaman 46 dari NIST SP 800-63 berbicara tentang karya Claude Shannon , yang memperkirakan entropi kata sandi menggunakan sejumlah bit. Memang, ini adalah dokumen yang digunakan kartun XKCD untuk menghitung bit entropi. Secara khusus:

• entropi dari karakter pertama dianggap 4 bit;
• entropi dari 7 karakter berikutnya adalah 2 bit per karakter; ini kira-kira konsisten dengan perkiraan Shannon bahwa "ketika efek statistik yang meluas tidak lebih dari 8 huruf dianggap entropi kira-kira 2,3 bit per karakter;"
• untuk karakter 9 hingga 20, entropi dianggap 1,5 bit per karakter;
• untuk karakter 21 dan di atas entropi dianggap 1 bit per karakter;
• "Bonus" dari 6 bit entropi diberikan untuk aturan komposisi yang membutuhkan karakter huruf besar dan non-alfabet. Ini memaksa penggunaan karakter-karakter ini, tetapi dalam banyak kasus, karakter hanya akan muncul di awal atau di akhir kata sandi, dan ini mengurangi ruang pencarian total, sehingga manfaatnya mungkin sederhana dan hampir tidak tergantung pada panjangnya karakter. kata sandi;
• Bonus hingga 6 bit entropi ditambahkan untuk pemeriksaan kamus yang luas. Jika penyerang mengetahui kamus, ia dapat menghindari pengujian kata sandi tersebut, dan dalam hal apa pun, akan dapat menebak banyak kamus, yang akan, bagaimanapun, menjadi kata sandi yang paling mungkin dipilih tanpa adanya aturan kamus. Asumsinya adalah bahwa sebagian besar manfaat menebak menebak untuk tes kamus bertambah dengan kata sandi yang relatif pendek, karena setiap kata sandi panjang yang dapat diingat harus selalu berupa "pass-phrase" yang terdiri dari kata-kata kamus, sehingga bonus menurun menjadi nol pada 20 karakter.

Idenya adalah bahwa sistem otentikasi akan memilih tingkat entropi tertentu sebagai ambang batas. Misalnya, 10 bit mungkin lemah, 20 sedang dan 30 kuat (angka dipilih secara sewenang-wenang sebagai contoh, bukan rekomendasi). Sayangnya, dokumen tersebut tidak merekomendasikan ambang tersebut, mungkin karena daya komputasi yang tersedia untuk memaksa atau menebak kata sandi meningkat seiring waktu:

Sebagai alternatif untuk memaksakan beberapa set aturan khusus yang arbitrer, sistem otentikasi mungkin menilai kata sandi pengguna, menggunakan aturan yang dinyatakan di atas, dan menerima aturan yang memenuhi standar entropi minimum. Sebagai contoh, anggaplah kata sandi dengan setidaknya 24-bit entropi diperlukan. Kita dapat menghitung estimasi entropi "IamtheCapitanofthePina4" dengan mengamati bahwa string memiliki 23 karakter dan akan memenuhi aturan komposisi yang membutuhkan huruf besar dan karakter non-alfabet.

Ini mungkin atau mungkin bukan yang Anda cari tetapi bukan titik referensi yang buruk, jika tidak ada yang lain.

[Sunting: Menambahkan yang berikut.]

Makalah Pengujian Metrik untuk Kebijakan Pembuatan Kata Sandi dengan Menyerang Kumpulan Besar Kata Sandi Terungkap (oleh Matt Weir, Sudhir Aggarwal, Michael Collins dan Henry Stern) menunjukkan model Shannon, yang dijelaskan di atas, bukan model entropi yang akurat untuk kata sandi yang dibuat oleh manusia. Saya akan merekomendasikan mencari di "Bagian 5 Menghasilkan Kebijakan Pembuatan Kata Sandi Baru" untuk proposal yang lebih akurat.

Lihatlah kode sumber untuk KeePass di bagian bawah halaman ini . The QualityEstimationkelas alat algoritma agak bagus yang tampaknya sejalan dengan apa yang Anda cari untuk memiliki di tempat. Hasil saya terlihat seperti ini:

aaa                              8
aaaaaaaaa                        9
abcdefghi                       18
H0ley$Mol3y_                    73
s^fU¬5ü;y34G<                   99
[a^36]*                         10
[a^20]A[a^15]*                  18
Tr0ub4dor&3                     66
correct horse battery staple    98

Anda bertanya

Secara khusus, adakah yang bisa memikirkan situasi di mana memasukkan kata sandi ke algoritma akan melebih-lebihkan kekuatannya?

Tetapi Anda memiliki contoh dalam pertanyaan itu. Secara desain, xkcd2 memiliki ~ 44 bit entropi, tetapi perkiraan Anda adalah 160,5 bit.

Adakah yang bisa memberikan beberapa wawasan tentang apa algoritma ini mungkin lemah? Secara khusus, adakah yang bisa memikirkan situasi di mana memasukkan kata sandi ke algoritma akan melebih-lebihkan kekuatannya?

Anda telah mengisyaratkan beberapa di pembukaan (serangan kamus, dll). Pada dasarnya, ada sejumlah praktik umum yang dapat ditebak oleh penyerang yang sangat menurunkan ruang pencarian. Saya cukup yakin bahwa algoritme Anda akan "melebih-lebihkan" hal-hal berikut:

• dimana mana
• Dimana mana
• Di mana-mana1

Kata sandinya cukup panjang, tetapi mudah retak karena kata aslinya muncul di kamus dasar, dan modifikasi dianggap cukup umum untuk membentuk bagian dari serangan kamus yang layak. Huruf khas -> konversi angka (yaitu 3v3rywh3r3) juga harus dianggap sangat lemah, dan Anda harus menghukumnya.

Pada tingkat yang jauh lebih rendah, kata sandi bermasalah lainnya mungkin adalah yang memiliki pola yang jelas, seperti:

• abcdefghijklmnop
• abcde12345

Meskipun ini kemungkinan kecil untuk ditargetkan dalam serangan kamus yang sebenarnya, mereka menderita masalah yang sama dengan contoh "aaaaa ..." Anda.

Saya tidak yakin apakah frasa kata sandi saat ini ditargetkan di sebagian besar serangan kamus, tetapi tidak diragukan lagi ketika mereka mendapatkan popularitas, mereka akan semakin ditargetkan. Saya pikir contoh xkcd yang terkenal memperhitungkan hal ini, karena hanya 11 bit yang diberikan untuk setiap "kata umum". Algoritme Anda juga menaksir terlalu tinggi jenis kata sandi ini.

Jadi, untuk meringkas, algoritma melakukan pekerjaan estimasi yang cukup baik, tetapi harus benar-benar mempertimbangkan struktur kata sandi dan pola umum yang diketahui.