"Kata sandi terkuat"

11

Saya memiliki aplikasi yang dilindungi oleh PIN empat digit dan pengguna mendapat lima upaya masuk sebelum akun dikunci.

Sekarang, salah satu pelanggan saya ingin "memperkuat" keamanan dan mengadvokasi solusi lain:

  • enam digit PIN
  • TIDAK "angka yang sama di sebelah satu sama lain": mis: 11 3945 atau 39 55 94
  • TIDAK "nomor tiga-lari": mis .: 123 654 atau 53 789 3

Sekarang untuk pertanyaan: Solusi mana yang paling kuat?

Saya bisa menghitung empat digit dengan cukup mudah, tetapi bagaimana cara menghitung yang lain?

Terima kasih!

Memperbarui

Anda mendapatkan apa yang Anda minta - terutama ketika bekerja dengan matematika :)

Jadi, yang saya minta adalah jumlah kombinasi untuk kedua urutan nomor.

Setelah membaca jawaban dan komentar, sudah jelas bagi saya bahwa itu tidak masalah. Jika Anda memiliki 5 tebakan maka tidak masalah jika Anda memiliki 10.000 atau ~ 800.000 untuk dipilih. Lebih penting adalah mengesampingkan 1234 dan hari kelahiran. Dalam situasi saya, saya sebenarnya memiliki hari kelahiran pengguna sehingga saya memiliki sesuatu untuk diperiksa.

Terima kasih atas diskusi yang luar biasa!

Casper Jensen
sumber
4
Mengambil perspektif historis, Anda harus memperkenalkan diri dengan cryptanalysis dari mesin Enigma. Secara khusus, algoritma Enigma tidak pernah mengenkripsi surat ke dirinya sendiri. Ini dianggap membuatnya lebih aman oleh para insinyurnya, tetapi memiliki efek membuat mesin secara dramatis kurang aman. Ini adalah salah satu dari banyak langkah yang memungkinkan Kekuatan Sekutu untuk memecahkan Enigma. Saya bukan ahli crypto dengan cara apa pun, tetapi gagasan umum adalah bahwa Anda ingin ruang kunci Anda menjadi sebesar mungkin.
Sycorax berkata Reinstate Monica
2
Saya pikir ini milik Kriptografi , bukan di sini.
gung - Reinstate Monica
2
Casper, mohon klarifikasi - apakah Anda terutama khawatir tentang hal itu sebagai masalah keamanan (misalnya ada pertimbangan yang terkait dengan lebih dari sekadar probabilitas), dalam hal ini mungkin lebih cocok di tempat lain - atau apakah Anda mengajukan pertanyaan kemungkinan besar (yang cocok di sini)?
Glen_b -Reinstate Monica
3
Secara teoritis --- jika Anda hanya berfokus pada serangan brute force --- lebih banyak kemungkinan berarti lebih banyak keamanan sehingga pembatasan seperti no-same-digit atau no-run-of-3 mengurangi jumlah kemungkinan sehingga mereka benar-benar lebih lemah. Namun, secara praktis (seperti yang disentuh pengguna777) orang tidak memilih pin acak. Jika pengguna lebih malas daripada paranoid, banyak dari mereka mungkin memilih pin seperti "000000" atau "123456", yang kemudian membuat segalanya menjadi kurang aman.
Gregor Thomas
2
Saya memberikan suara untuk (sementara) menutup pertanyaan ini sebagai tidak jelas, dengan alasan bahwa niat OP belum jelas. Saya benar-benar lebih suka melihat pertanyaan @ Glen_b dijawab, jadi kami tahu apakah ini harus diperlakukan sebagai pertanyaan kombinatorik / probabilitas atau sebagai sesuatu yang lebih baik dimigrasi.
Silverfish

Jawaban:

8

Anda telah meminta bantuan forum statistik untuk pertanyaan ini, jadi saya akan memberikan jawaban berbasis statistik. Dengan demikian masuk akal untuk berasumsi bahwa Anda tertarik pada probabilitas menebak PIN secara acak (untuk beberapa definisi acak), tetapi itu lebih mengarah pada pertanyaan daripada yang disediakan.

Pendekatan saya adalah menghitung semua opsi yang mungkin tanpa membatasi, lalu kurangi opsi yang tidak berlaku. Namun, ini memiliki sudut tajam, yang disebut prinsip inklusi-pengecualian, yang sesuai dengan gagasan intuitif bahwa Anda tidak ingin mengurangi hal yang sama dari perangkat dua kali!

Dalam PIN enam digit tanpa batasan dan sistem angka desimal, ada kemungkinan kombinasi, dari hingga setiap digit memiliki 10 opsi.106000000999999:

Perhatikan seperti apa angka "dua yang berdekatan, identik": , di mana posisi berlabel sama dan dapat berupa angka desimal. Sekarang perhatikan berapa banyak cara lain string dapat diatur dalam enam digit: , , , dan . Jadi untuk setiap pemesanan tertentu (salah satu opsi itu), setidaknya ada kombinasi, karena ada digit tanpa batasan. Sekarang, berapa banyak pilihan yang ada? Kami bekerja dengan angka desimal, jadi harus ada 10. Jadi adaAAXXXXAXAAXAAXXXXXAAXXXXXAAXXXXXAA104104A105pilihan untuk pemesanan tertentu. Ada lima urutan seperti itu, jadi ada pengaturan yang memenuhi definisi ini. (Apa artinya ini dalam hal keamanan mungkin diukur dalam hal ukuran informasi-teori tentang seberapa banyak ini mengurangi entropi ruang PIN.)5×105

Sekarang perhatikan seperti apa bentuk angka berurutan. Dalam string , jika kita tahu A, kita juga tahu B dan C *: jika A adalah 5, maka B adalah 6 dan C adalah 7. Jadi kita dapat menyebutkan opsi-opsi ini:ABCXXX

  • 012XXX
  • 123XXX
  • 234XXX
  • 456XXX
  • 789XXX

dan pada titik ini tidak jelas apakah ada "pembungkus". Jika ada, kami juga sertakan

  • 890XXX
  • 901XXX

Setiap solusi memiliki kombinasi terkait, dengan alasan yang sama seperti di atas. Jadi hitung saja berapa banyak solusi yang harus ada. Ingatlah untuk menghitung pemesanan alternatif, seperti103XABCXX.

Sekarang kita sampai ke sudut yang tajam, yang merupakan prinsip inklusi-pengecualian. Kami telah membuat set semua PIN enam digit menjadi tiga set:

A. PIN yang diizinkan B. Membatalkan PIN karena "digit yang berdekatan" C. Membatalkan PIN karena "digit berurutan"

Tapi ada kehalusan tambahan, yang adalah bahwa ada beberapa nomor 6-digit yang dapat dialokasikan untuk kedua dan . Jadi jika kita menghitung kita mengurangi angka-angka itu dua kali, dan jawaban kita salah. Perhitungan yang benar adalah di mana adalah himpunan elemen di kedua dan . Jadi kita harus menentukan berapa banyak cara bisa sejumlah jatuh di kedua dan .C | S | = | A | - | B | - | C | , | S | = | A | - | B | - | C | + | B C | , B C B C B CBC|S|=|A||B||C|,|S|=|A||B||C|+|BC|,BCBCBC

Ada beberapa cara ini dapat terjadi:

  • AABCXX
  • ABCXDD dan sebagainya. Jadi, Anda harus melakukan pendekatan sistematis untuk ini juga, serta cara untuk melacak pemesanan alternatif. Menggunakan logika yang sama yang saya terapkan di atas, ini harus sangat mudah ditelusuri, jika sedikit membosankan. Hanya perlu diingat berapa banyak cara alternatif yang mungkin ada untuk memuaskan B dan C.

Pendekatan yang sedikit lebih maju akan mengambil keuntungan dari hasil kombinatorik dasar dan teorema dasar penghitungan, tetapi saya memilih jalan ini karena menempatkan beban teknis terkecil pada pembaca.

Sekarang, untuk ini menjadi pertanyaan probabilitas yang dibentuk dengan baik, kita harus memiliki beberapa ukuran probabilitas untuk setiap pengaturan. Dengan asumsi serangan naif, orang mungkin berasumsi bahwa semua kombinasi digit memiliki probabilitas yang sama. Dalam skenario ini, probabilitas kombinasi yang dipilih secara acak adalah Jika itu jenis serangan yang paling Anda minati, maka kriteria yang diajukan jelas melemahkan sistem, karena beberapa kombinasi dilarang, jadi hanya penyerang bodoh yang akan mencobanya. Saya menyerahkan sisa latihan kepada pembaca.1|S|

Kerutan "lima hingga penguncian" jelas merupakan penjagaan yang lebih baik terhadap akses yang tidak sah, karena dalam skema 4-digit atau 6-digit, ada sejumlah besar opsi, dan bahkan lima tebakan acak yang berbeda pun memiliki probabilitas keberhasilan. Untuk pertanyaan probabilitas yang diajukan dengan baik, dimungkinkan untuk menghitung kemungkinan serangan seperti itu berhasil.

Tetapi faktor-faktor lain selain probabilitas urutan angka dapat memengaruhi keamanan mekanisme PIN. Terutama, orang cenderung tidak memilih PIN secara acak! Misalnya, beberapa orang menggunakan tanggal lahir mereka, atau DOB anak-anak, atau beberapa nomor yang terkait secara pribadi sebagai PIN. Jika penyerang mengetahui DOB pengguna, maka itu mungkin akan menjadi salah satu hal pertama yang mereka coba. Jadi untuk pengguna tertentu, beberapa kombinasi mungkin lebih mungkin daripada yang lain.

* Urutan yang Anda daftarkan benar-benar meningkat, dan tidak jelas apakah keduanya meningkat dan menurun ketika Anda mengatakan "nomor tiga berjalan."

Sycorax berkata Reinstate Monica
sumber
1

Memperoleh formula tertutup tampaknya rumit. Namun, cukup mudah untuk menyebutkannya. Ada beberapa 568 916kode yang mungkin untuk solusi kedua. Yang lebih besar dari jumlah solusi dengan kode PIN empat digit. Kode untuk menghitungnya ada di bawah. Meski tidak dioptimalkan, hanya perlu beberapa detik untuk berjalan.

Catatan. Saya berasumsi bahwa urutannya harus dalam urutan yang meningkat (yang dapat dengan mudah dimodifikasi three_running)

N = 999999

candidates = range(N)

def same_consecutive_digits(x):
    x_string = str(x).zfill(6)
    for i in range(1,len(x_string)):
        if x_string[i] == x_string[i-1]:
            return True
    return False

def three_running(x):
    x_string = str(x).zfill(6)
    for i in range(2,len(x_string)):
        if int(x_string[i]) == int(x_string[i-1]) + 1 and int(x_string[i-1]) == int(x_string[i-2]) + 1:
            return True
    return False

def valid(x):
    return not same_consecutive_digits(x) and not three_running(x)

assert(same_consecutive_digits(88555))
assert(same_consecutive_digits(123))
assert(not same_consecutive_digits(852123))
assert(three_running(123456))
assert(not three_running(4587))
assert(valid(134679))
assert(not valid(123894))
assert(not valid(111111))
assert(not valid(151178))
assert(valid("031278"))

accepted = [i for i in range(N) if valid(i)]
print(len(accepted))
RUser4512
sumber
Tersirat dalam kode, tetapi tidak dalam deskripsi Anda, adalah asumsi bahwa PIN tidak akan pernah dimulai dengan angka "0". Biasanya itu tidak berlaku untuk PIN atau kata sandi. Jawaban yang benar, memungkinkan untuk nol seperti itu, adalah 568.916. Namun, mari kita ingat bahwa jawaban yang relevan akan mempertimbangkan bahwa serangan pada PIN dalam masalah terbatas ini dapat dibuat lebih efisien dengan mengeksploitasi kendala, yang menyiratkan bahwa hanya penghitungan kemungkinan tidak cukup mewakili "kekuatan" dari sistem, sebagaimana ditunjukkan dalam komentar untuk pertanyaan itu.
Whuber