Password Strength – "at least one"

at_least_one.js

/** Convenient utilities in functional form */
const reduce = Function.prototype.call.bind(Array.prototype.reduce);
const filter = Function.prototype.call.bind(Array.prototype.filter);
const pow = Math.pow;
const log2 = Math.log2;
const size = (set) => set.size;

/** Iterable conversions */
const toSet = (iterable) => new Set(iterable);
const toArray = (iterable) => [...iterable];
const toString = (iterable) => toArray(iterable).join("");
const toSetOfSets = (iterable) => toSet([...(iterable || [])].map(toSet))

/** Set operations */
const emptySet = () => toSet([]);
const union = (a, b) => toSet([...a, ...b]);
const isSubsetOf = (subset, superset) => [...subset].every((e) => superset.has(e));
const areEqualSets = (a, b) => size(a) === size(b) && isSubsetOf(a, b);

/** Mimic the mathematical sum operator */
const sumAll = (iterable, expression) => reduce(
	toArray(iterable),
	(total, element) => total + expression(element),
	0,
);

/** Mimic the mathematical big union (bigcup) operator */
const unionAll = (iterable, expression) => reduce(
	toArray(iterable),
	(result, element) => union(result, expression(element)),
	emptySet(),
);

/**
 * Produce the power set of a given set
 * @param {Set} set - The set
 */
const powerSet = (set) => {
	if (size(set) === 0) {
		return toSet([emptySet()]);
	}

	const [next, ...rest] = set;
	return unionAll(
		powerSet(toSet(rest)),
		(subsetOfRest) => toSet([
			subsetOfRest,
			union(subsetOfRest, toSet([next]))
		]),
	);
};

/**
 * Recipe type definition
 * @typedef {Object} Recipe
 * @property {Set<Set>|Array<Set>} required - The set of character sets that must be represented in the password
 * @property {Set<Set>|Array<Set>} optional - The set of character sets that may be represented in the password or may not
 * @property {number} length - The length of the password
 */

/**
 * Produce number of possible outputs of the given password recipe
 * @param {Recipe} recipe - The recipe for generating the password
 */
const possibleStrings = ({ required, optional, length }) => {
	const optionalSets = toSetOfSets(optional);
	const requiredSets = toSetOfSets(required);

	// totalCount is the total number of permutations possible when a
	// password of length n is generated from the set R, which is the
	// union of all sets in the password recipe.
	const n = length;
	const R = unionAll(
		union(requiredSets, optionalSets),
		(s) => s
	);
	const totalCount = pow(size(R), n);

	// Each of these sets of sets represents a password recipe that we
	// will reject and thus must subtract from our total count.
	// We want to reject all subsets of the set of required sets except
	// the set of required sets itself.
	// For example, if L and D are required, rejectedSubsets
	// will contain {L} and {D} and will not contain {L, D}.
	// Optional sets are not part of this at all because they will
	// simply be tacked on at the end.
	const rejectedSubsets = filter(
		toArray(powerSet(requiredSets)),
		(set) => !areEqualSets(requiredSets, set),
	);

	// When requiredSets is {{}} (it is a set containing only the empty set),
	// powerSet(requiredSets) will also be {{}};
	// thus, rejectedSubsets will be empty, the reducing
	// function below will not run, and rejectedCount will be 0,
	// terminating the recursion.
	const rejectedCount = sumAll(
		rejectedSubsets,
		(subset) => possibleStrings({
			required: subset,
			optional,
			length
		}),
	);

	return totalCount - rejectedCount;
};

/**
 * Produce the entropy in bits of the given password recipe
 * @param {Recipe} recipe - The recipe for generating the password
 */
const entropy = (recipe) => log2(possibleStrings(recipe));


const upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const lower = "abcdefghijklmnopqrstuvwxyz";
const digits = "0123456789";
const expectations = [
	{ required: [""], length: 1, result: 0 },
	{ required: ["a"], length: 0, result: 0 },
	{ required: ["a"], length: 1, result: 1 },
	{ required: ["a"], length: 5, result: 1 },
	{ required: ["abcde"], length: 1, result: 5 },
	{ required: ["abcde"], length: 2, result: 25 },
	{ required: ["a", "1"], length: 2, result: 2 },
	{ required: ["ab", "123"], length: 2, result: 12 },

	{ required: [upper, lower, digits], length: 0, result: 0 },
	{ required: [upper, lower, digits], length: 1, result: 0 },
	{ required: [upper, lower, digits], length: 2, result: 0 },
	{ required: [upper, lower, digits], length: 3, result: 40560 },
	{ required: [upper + lower, digits], length: 3, result: 96720 },

	{ required: [upper], length: 3, result: 17576 },
	{ optional: [upper], length: 3, result: 17576 },
	{ required: [upper + lower + digits], length: 3, result: 238328 },
	{ optional: [upper, lower, digits], length: 3, result: 238328 },

	{ required: ["a", "1"], length: 1, result: 0 },
	{ required: ["a"], optional: ["1"], length: 1, result: 1 },
	{ required: ["a"], optional: ["A", "1"], length: 2, result: 5 },
	{ required: ["a"], optional: ["A1"], length: 2, result: 5 },
	{ required: ["a", "A"], optional: ["1"], length: 2, result: 2 },
	{ required: ["a", "A"], optional: ["1"], length: 3, result: 12 },
]

const test = () => expectations.every((e) => {
	const { required, optional, length, result } = e;
	const expected = result;
	const actual = possibleStrings({ required, optional, length });
	const testResult = actual === expected;

	if (!testResult) {
		console.error(
			`Expected: ${expected}`
			+ `\nActual: ${actual}`
			+ `\nTest: ${JSON.stringify(e)}`
		);
	}

	return testResult;
});

I really have a though time reading idiomatic JS. Can you help me understand what combine is returning? (And should be be doing this in haskell?)

It would be fun to write this in Haskell! I don't know that I'm proficient enough in it just yet though. Also, JS allows easy testing via browser console.

The combine function produces all possible combinations (order does not matter) of the elements of the array. So an array [a, b, c] would produce [[a], [b], [c], [a, b], [a, c], [b, c], [a, b, c]]. This implementation will not produce the combinations in that order, but those are the combinations it produces.

If combine also had an empty array in its output then it would be the power set of a set. If adding the empty array does no harm, I would recommend doing that and calling this something like "powerSet".

To explain this all a bit further, here's what we have:

One character set

P1(S, n) = |S|^n

Alternatively, to fit the pattern of subsequent definitions, we could write

P1(S, n) = |S|^n - (|∅|^n)

Two character sets

P2(S1, S2, n) = |S1 ∪ S2|^n - (|S1|^n + |S2|^n)

This can be rewritten in terms of P1 as

P2(S1, S2, n) = |S1 ∪ S2|^n - (P1(S1, n) + P1(S2, n))

Three character sets

P3(S1, S2, S3, n) = |S1 ∪ S2 ∪ S3|^n - [(|S1|^n + |S2|^n + |S3|^n) + ([|S1 ∪ S2|^n - (|S1|^n + |S2|^n)] + [|S1 ∪ S3|^n - (|S1|^n + |S3|^n)] + [|S2 ∪ S3|^n - (|S2|^n + |S3|^n)])

which of course can be written in terms of P2 and P1:

P3(S1, S2, S3, n) = |S1 ∪ S2 ∪ S3|^n - [(P1(S1, n) + P1(S2, n) + P1(S3, n)) + (P2(S1, S2, n) + P2(S1, S3, n) + P2(S2, S3, n))]

Recursion

The goal of course is to define a recursive function P that accepts a list of sets of any size. Without defining it, we could use it in P3 as follows:

P3(S1, S2, S3, n) = |S1 ∪ S2 ∪ S3|^n - (P([S1], n) + P([S2], n) + P([S3], n) + P([S1, S2], n) + P([S1, S3], n) + P([S2, S3], n))

or

P3(S1, S2, S3, n) = |S1 ∪ S2 ∪ S3|^n - (Reduce([[S1], [S2], [S3], [S1, S2], [S1, S3], [S2, S3]], (T, S) => T + P(S, n)))

This list of combinations [[S1], [S2], [S3], [S1, S2], [S1, S3], [S2, S3]] is what the combine function produces (minus itself).

combine([a]) => [[a]]
combine([a, b]) => [[a], [b], [a, b]]
combine([a, b, c]) => [[a], [b], [c], [a, b], [a, c], [b, c], [a, b, c]]

When we filter out the combination that matches the input we get

[]
[[a], [b]]
[[a], [b], [c], [a, b], [a, c], [b, c]]

And you can see that matches our implementation above:

[[S1], [S2], [S3], [S1, S2], [S1, S3], [S2, S3]]

If combine also had an empty array in its output then it would be the power set of a set. If adding the empty array does no harm, I would recommend doing that and calling this something like "powerSet".

@jpgoldberg, that's smart! I made that change and I think it makes powerSet more understandable. 👍

Is this logic going to work when include sets which are not required?

That is we might allow letters, digits, and symbols but only require digits and symbols?

Why would we do that?

But yes, the basic logic is still the same, we'd just need to pass the optional sets and required sets separately and only subtract sets that don't include the required sets. I can write that up if you'd like, but I don't understand why we would want to introduce that complexity.

Basically, the filter that produces rejectedSets would simply filter out any sets that contain all of the required sets.

We'd also need to pass the actual unique sets instead of their sizes since the sizes of two different sets (like uppercase and lowercase) could be the same. Something like this:

const includesAll = (req, candidate) => req.every((e) => candidate.includes(e))

// param optional: ["ABC", "abc"]
// param required: ["123", "!@#"]

const allSets = [...optional, ...required];
const rejectedSets = filter(
	powerSet(allSets),
	(a) => 0 < a.length && includesAll(required, a),
);

Of course we could optimize this by using actual JS Set objects and such instead of arrays.

Of course we could optimize this by using actual JS Set objects and such instead of arrays.

Yes!

(The golang standard library doesn't have a Set type, so I started writing my own last night. Then I found (unsurprisingly) that others already have and have done a much better job of it than I was doing.)

@jpgoldberg I've updated the gist to use JS Set and to allow for optional character sets. Tests all pass.

This is going to be fun to write up! And it a spectacularly elegant solution as well.

The hardest part, I think, will be in explaining why the (non-recursive) expression for the three character set case does the right thing. That is, the rationale for that.

Do you mean for two character sets? The non-recursive equation you had works for two required sets but not for three.

Do you mean for two character sets? The non-recursive equation you had works for two required sets but not for three.

No. I was saying that we need to explain why mine gave the wrong results. So I think we need to explain why what you had (before you introduced recursion)

P3(S1, S2, S3, n) = |S1 ∪ S2 ∪ S3|^n - [(|S1|^n + |S2|^n + |S3|^n) + ([|S1 ∪ S2|^n - (|S1|^n + |S2|^n)] + [|S1 ∪ S3|^n - (|S1|^n + |S3|^n)] + [|S2 ∪ S3|^n - (|S2|^n + |S3|^n)])

is the right thing for three sets. Once that is grasped, we can then explain why

• That way will get exceedingly message when trying this for four sets (and worse for five, etc ...)
• But yields to a nice recursive statement

But I was trying to say that before we talk about the recursive (and general) characterization, we need to explain that the various terms in the non-recursive statement for P3 are about.

Ah, yes.

I've revised it one more time to abstract my uses of reduce into two functions that mimic mathematical expressions more closely, sumAll and unionAll. I also renamed some functions and removed a couple of preemptive conditional checks to make the algorithm match your mathematical expression more closely.

Thanks for going over the mathematical description. I want to make sure that it matches the algorithm.

I spent way too much time last night trying to make equation (12) moderately legible. But it doesn't really matter. No one is going to try to read it.

It's kind of cool that the final form doesn't need to state the base for recursion. Everything should nicely zero out and R is empty, giving just a number of A alone.

It's kind of cool that the final form doesn't need to state the base for recursion. Everything should nicely zero out and R is empty, giving just a number of A alone.

Yeah that's really cool. It ended up being a pretty tidy function after all. :)

The consumer of PossibleStrings will need to check that the return value isn't 0 before trying to take a logarithm of it. This also serves as a nice test of whether the combined constraints can be satisfied.