Wild Assumptions About Entropy

Posted by Spencer on May 8th, 2019

I recently conducted a brief audit of two factor auth recovery codes patterns employed by major tech companies. One of the factors I considered was how “complex” their patterns were. In other words, how hard it would be for someone (or some machine) to guess the recovery code. As these codes are generated randomly, brute forcing would be the only way to break them.

In computer science, this type of complexity is represented as “bits of entropy”, and the formula for calculating it is pretty straightforward. Unfortunately, it’s a bit too complex for me to do in my head, so I created some JavaScript functions to help.

/**
 * Calculate bits of entropy.
 * 
 * @param {number} charset The number of possible characters in a set.
 * @param {number} length The length of the set.
 * @return {number} Bits of entropy.
 */
function entropy(charset, length) {
    return Math.round(Math.log2(Math.pow(charset, length)));
}

Sometimes it’s helpful to know the “attack cost” as well.

/**
 * Attack cost. 
 * 
 * @param {number} bits Bits of entropy.
 * @return {number} Attack cost.
 */
function attackCost(bits) {
    return Math.pow(2, (bits - 1));
}

That’s all pretty straightforward and well-founded math. But I promised wild assumptions and I intend to deliver! Inspired by this stack overflow answer, I was curious about how bcrypt cost factors and password entropy stacked up against “real world” brute force cracking attempts.

To find out, I implemented the algorithm described in that answer as a function:

/**
 * How long would it take to brute force this string?
 * 
 * @param {number} charset The number of possible characters in a set.
 * @param {number} length The length of the set.
 * @param {number} cost 
 */
function howLongToCrack(charset, length, cost) {
	// per S.O., the benchmarked rig could do 100k rounds
	// when the bcrypt cost was set to 5
	const nvidiaRateAtCost5 = 100000;

	let bits = entropy(charset, length);
	let attack = attackCost(bits);

	let roundsAtCost5 = Math.pow(2, 5);
	let roundsAtCostActual = Math.pow(2, cost);
	let slownessFactor = Math.round(roundsAtCostActual / roundsAtCost5);

	let nvidiaRateAtCostActual = nvidiaRateAtCost5 / slownessFactor;

	let seconds = attack / nvidiaRateAtCostActual;
	let days = seconds / 86400;
	let years = Math.round(days / 365.25);

	return {
		seconds: seconds,
		days: days,
		years: years
	};
}

The assumptions are wild because I have no idea whether the “100k rounds at cost of 5” benchmark is realistic- not to mention, up to date, as a few years have passed since that answer and presumably these rigs are constantly getting more powerful. If you happen to have more accurate benchmarks though, you can edit nvidiaRateAtCost5 in that last function to match.

Posted in Coding, How To