From 6422c1cd57afbb4f0c71b0157ba6ad9598f82bc4 Mon Sep 17 00:00:00 2001 From: Ian Coleman Date: Thu, 17 Nov 2016 14:28:26 +1100 Subject: [PATCH] Entropy library assumes cards are discarded and removed the duplicate logic from the UI logic. --- src/js/entropy.js | 46 +++++++++++++++++++++++++++++++++++++++++ src/js/index.js | 52 +++++++++-------------------------------------- tests.js | 50 ++++++++++++++++++++++----------------------- 3 files changed, 81 insertions(+), 67 deletions(-) diff --git a/src/js/entropy.js b/src/js/entropy.js index c28620a..5900346 100644 --- a/src/js/entropy.js +++ b/src/js/entropy.js @@ -117,6 +117,40 @@ window.Entropy = new (function() { while (entropyBin.length < expectedBits) { entropyBin = "0" + entropyBin; } + // Assume cards are NOT replaced. + // Additional entropy decreases as more cards are used. This means + // entropy is measured using n!, not base^n. + // eg the second last card can be only one of two, not one of fifty two + // so the added entropy for that card is only one bit at most + if (base.asInt == 52) { + // Get the maximum value without replacement + var totalDecks = Math.ceil(base.parts.length / 52); + var totalCards = totalDecks * 52; + var totalCombos = factorial(52).pow(totalDecks); + var totalRemainingCards = totalCards - base.parts.length; + var remainingDecks = Math.floor(totalRemainingCards / 52); + var remainingCards = totalRemainingCards % 52; + var remainingCombos = factorial(52).pow(remainingDecks).multiply(factorial(remainingCards)); + var currentCombos = totalCombos.divide(remainingCombos); + var numberOfBits = Math.log2(currentCombos); + var maxWithoutReplace = BigInteger.pow(2, numberOfBits); + // aggresive flooring of numberOfBits by BigInteger.pow means a + // more accurate result can be had for small numbers using the + // built-in Math.pow function. + if (numberOfBits < 32) { + maxWithoutReplace = BigInteger(Math.round(Math.pow(2, numberOfBits))); + } + // Get the maximum value with replacement + var maxWithReplace = BigInteger.pow(52, base.parts.length); + // Calculate the new value by scaling the original value down + var withoutReplace = entropyInt.multiply(maxWithoutReplace).divide(maxWithReplace); + // Left pad with zeros based on number of bits + var entropyBin = withoutReplace.toString(2); + var numberOfBitsInt = Math.floor(numberOfBits); + while (entropyBin.length < numberOfBitsInt) { + entropyBin = "0" + entropyBin; + } + } // Supply a 'filtered' entropy string for display purposes var entropyClean = base.parts.join(""); var entropyHtml = base.parts.join(""); @@ -221,4 +255,16 @@ window.Entropy = new (function() { return BigInteger.log(x) / BigInteger.log(2); }; + // Depends on BigInteger + function factorial(n) { + if (n == 0) { + return 1; + } + f = BigInteger.ONE; + for (var i=1; i<=n; i++) { + f = f.multiply(new BigInteger(i)); + } + return f; + } + })(); diff --git a/src/js/index.js b/src/js/index.js index f4163ee..254b62f 100644 --- a/src/js/index.js +++ b/src/js/index.js @@ -791,20 +791,21 @@ } function showEntropyFeedback(entropy) { + var numberOfBits = entropy.binaryStr.length; var strength = "extremely weak"; - if (entropy.binaryStr.length >= 64) { + if (numberOfBits >= 64) { strength = "very weak"; } - if (entropy.binaryStr.length >= 96) { + if (numberOfBits >= 96) { strength = "weak"; } - if (entropy.binaryStr.length >= 128) { + if (numberOfBits >= 128) { strength = "strong"; } - if (entropy.binaryStr.length >= 160) { + if (numberOfBits >= 160) { strength = "very strong"; } - if (entropy.binaryStr.length >= 192) { + if (numberOfBits >= 192) { strength = "extremely strong"; } // If time to crack is less than one day, and password is considered @@ -825,38 +826,17 @@ console.log("Error detecting entropy strength with zxcvbn:"); console.log(e); } - var bitsStr = getNumberOfEntropyBits(entropy); - var wordCount = Math.floor(entropy.binaryStr.length / 32) * 3; var entropyTypeStr = getEntropyTypeStr(entropy); + var wordCount = Math.floor(numberOfBits / 32) * 3; + var bitsPerEvent = Math.log2(entropy.base.asInt).toFixed(2); DOM.entropyFiltered.html(entropy.cleanHtml); DOM.entropyType.text(entropyTypeStr); DOM.entropyStrength.text(strength); DOM.entropyEventCount.text(entropy.base.ints.length); - DOM.entropyBits.text(bitsStr); + DOM.entropyBits.text(numberOfBits); DOM.entropyWordCount.text(wordCount); DOM.entropyBinary.text(entropy.binaryStr); - DOM.entropyBitsPerEvent.text(Math.log2(entropy.base.asInt).toFixed(2)); - } - - function getNumberOfEntropyBits(entropy) { - var bitsStr = entropy.binaryStr.length.toString(); - // If using cards, assume they are not reused, thus additional entropy - // decreases as more cards are used. This means entropy is measured - // using n!, not base^n. - // eg the second last card can be only one of two, not one of fifty two - // so the added entropy for that card is only one bit at most - if (entropy.base.asInt == 52) { - var totalDecks = Math.ceil(entropy.base.parts.length / 52); - var totalCards = totalDecks * 52; - var totalCombos = factorial(52).pow(totalDecks); - var totalRemainingCards = totalCards - entropy.base.parts.length; - var remainingDecks = Math.floor(totalRemainingCards / 52); - var remainingCards = totalRemainingCards % 52; - var remainingCombos = factorial(52).pow(remainingDecks) * factorial(remainingCards); - var currentCombos = totalCombos.divide(remainingCombos); - bitsStr = currentCombos.toString(2).length.toString(); - } - return bitsStr + DOM.entropyBitsPerEvent.text(bitsPerEvent); } function getEntropyTypeStr(entropy) { @@ -922,18 +902,6 @@ return typeStr; } - // Depends on BigInteger - function factorial(n) { - if (n == 0) { - return 1; - } - f = BigInteger.ONE; - for (var i=1; i<=n; i++) { - f = f.multiply(new BigInteger(i)); - } - return f; - } - var networks = [ { name: "Bitcoin", diff --git a/tests.js b/tests.js index 13f2c76..03ce9e1 100644 --- a/tests.js +++ b/tests.js @@ -2185,10 +2185,9 @@ page.open(url, function(status) { try { var cards = [ [ "ac", "00000" ], - [ "acac", "00000000000" ], - [ "acac2c", "00000000000000001" ], - [ "acks", "00000110011" ], - [ "acacks", "00000000000110011" ], + [ "acqs", "00000110001" ], + [ "acks", "00000110010" ], + [ "2cac", "00000110011" ], [ "2c", "00001" ], [ "3d", "01111" ], [ "4h", "11101" ], @@ -2201,8 +2200,8 @@ page.open(url, function(status) { [ "jd", "10111" ], [ "qh", "100101" ], [ "ks", "110011" ], - [ "ks2c", "101001011101" ], - [ "KS2C", "101001011101" ], + [ "ks2c", "101000101001" ], + [ "KS2C", "101000101001" ], ]; for (var i=0; i