stupid-password-rule.js

"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)), '%');
        });    
    });
});

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 %
$