Skip to content

Instantly share code, notes, and snippets.

@bjouhier
Last active September 15, 2017 19:43
Show Gist options
  • Save bjouhier/94479643cf11a96d8bb320c55b0ddb3c to your computer and use it in GitHub Desktop.
Save bjouhier/94479643cf11a96d8bb320c55b0ddb3c to your computer and use it in GitHub Desktop.
"use strict";
// experimental value
// nsyms is size of alphabet (62 for letters + digits)
// len is password length
// maxReapeat is the max number of repeats we allow
// returns the probability of a password reject.
function expe(nsyms, len, maxRepeat) {
// generate random array of len symbols
const gen = len => {
const vals = [];
for (let i = 0; i < len; i++) vals.push(Math.floor(nsyms * Math.random()));
return vals;
}
const accepts = vals => {
// sort the array of vals to easily find repeat groups
vals.sort((x, y) => x - y);
// iterate to find repeat groups
let old = -1, repeat = 0;
for (let i = 0; i < vals.length; i++) {
if (vals[i] === old) {
if (++repeat >= maxRepeat) return false;
} else {
repeat = 0;
}
old = vals[i];
}
return true;
}
// run large number of iterations
const iterations = 1000000;
let accepted = 0;
for (let i = 0; i < iterations; i++) {
const vals = gen(len);
if (accepts(vals)) accepted++;
}
// rejected proba
return 1 - accepted / iterations;
}
// exact value
// same params and return as above
function theo(nsyms, len, maxRepeat) {
const fact = n => n > 1 ? n * fact(n - 1) : 1;
const anp = (n, p) => fact(n) / fact(n - p);
const cnp = (n, p) => anp(n, p) / fact(p);
// number of cases that do not contain any repeat group of size > maxRepeat
const repeating = (nsyms, len, maxRepeat) => {
// if maxRepeat is 1, easy, just anp
if (maxRepeat === 1) return anp(nsyms, len);
let total = 0;
// max number of groups of exactly maxRepeat identical syms
const max = Math.floor(len / maxRepeat);
// loop over number of possible groups
for (let ngroups = 0; ngroups <= max; ngroups++) {
let ncases = 1;
for (let i = 0; i < ngroups; i++) {
// for each group we need to choose the sym among nsyms - 1
// and then choose the positions (a subset of maxRepeat in what remains)
ncases *= (nsyms - i) * cnp(len - maxRepeat * i, maxRepeat);
}
// divide by the number of permutations of the groups
ncases /= fact(ngroups);
// multiply by the number of cases with maxRepeat - 1 in the remaining positions.
ncases *= repeating(nsyms - ngroups, len - maxRepeat * ngroups, maxRepeat - 1);
// aggregate
total += ncases;
}
return total;
}
// rejected proba.
// total number of cases is just nsyms^len
return 1 - repeating(nsyms, len, maxRepeat) / Math.pow(nsyms, len);
}
// show the results
[1, 2, 3, 4, 5].forEach(maxRepeat => {
console.log('maxRepeat', maxRepeat);
[5, 10, 20, 30, 40, 50, 60].forEach(len => {
[expe, theo].forEach(f => {
const rounded = x => Math.round(x * 1000000) / 10000;
console.log('\t', f.name, 'len', len, '=>', rounded(f(62, len, maxRepeat)), '%');
});
});
});
@bjouhier
Copy link
Author

bjouhier commented Sep 14, 2017

What are the odds of finding a character (chosen among nsyms chars) repeated more than maxRepeat times in a random password of length len.

See https://twitter.com/bjouhier/status/908390924526473217

Output:

$ node stupid-password-rule.js
maxRepeat 1
	 expe len 5 => 15.2354 %
	 theo len 5 => 15.2393 %
	 expe len 10 => 53.4908 %
	 theo len 10 => 53.513 %
	 expe len 20 => 96.8152 %
	 theo len 20 => 96.8203 %
	 expe len 30 => 99.9803 %
	 theo len 30 => 99.9798 %
	 expe len 40 => 100 %
	 theo len 40 => 100 %
	 expe len 50 => 100 %
	 theo len 50 => 100 %
	 expe len 60 => 100 %
	 theo len 60 => 100 %
maxRepeat 2
	 expe len 5 => 0.2575 %
	 theo len 5 => 0.2539 %
	 expe len 10 => 2.8698 %
	 theo len 10 => 2.8547 %
	 expe len 20 => 22.3831 %
	 theo len 20 => 22.364 %
	 expe len 30 => 57.1248 %
	 theo len 30 => 57.1111 %
	 expe len 40 => 86.0176 %
	 theo len 40 => 85.9866 %
	 expe len 50 => 97.6746 %
	 theo len 50 => 97.6902 %
	 expe len 60 => 99.8422 %
	 theo len 60 => 99.8394 %
maxRepeat 3
	 expe len 5 => 0.0021 %
	 theo len 5 => 0.0021 %
	 expe len 10 => 0.0814 %
	 theo len 10 => 0.0815 %
	 expe len 20 => 1.6256 %
	 theo len 20 => 1.6473 %
	 expe len 30 => 7.9739 %
	 theo len 30 => 8.0245 %
	 expe len 40 => 22.1929 %
	 theo len 40 => 22.1769 %
	 expe len 50 => 43.6464 %
	 theo len 50 => 43.6408 %
	 expe len 60 => 67.0446 %
	 theo len 60 => 67.1176 %
maxRepeat 4
	 expe len 5 => 0 %
	 theo len 5 => 0 %
	 expe len 10 => 0.0017 %
	 theo len 10 => 0.0016 %
	 expe len 20 => 0.0899 %
	 theo len 20 => 0.0857 %
	 expe len 30 => 0.6973 %
	 theo len 30 => 0.6877 %
	 expe len 40 => 2.7861 %
	 theo len 40 => 2.7609 %
	 expe len 50 => 7.6934 %
	 theo len 50 => 7.6462 %
	 expe len 60 => 16.6544 %
	 theo len 60 => 16.6253 %
maxRepeat 5
	 expe len 5 => 0 %
	 theo len 5 => 0 %
	 expe len 10 => 0 %
	 theo len 10 => 0 %
	 expe len 20 => 0.0034 %
	 theo len 20 => 0.0035 %
	 expe len 30 => 0.0425 %
	 theo len 30 => 0.0465 %
	 expe len 40 => 0.2629 %
	 theo len 40 => 0.2615 %
	 expe len 50 => 0.94 %
	 theo len 50 => 0.9416 %
	 expe len 60 => 2.5682 %
	 theo len 60 => 2.5728 %
$

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment