Card entropy has improved conversion to binary

See http://crypto.stackexchange.com/q/41886
and https://github.com/iancoleman/bip39/issues/33#issuecomment-263021856

2 files changed, 117 insertions, 267 deletions

diff --git a/src/js/entropy.js b/src/js/entropy.js
index 8a0c799..d04d861 100644
--- a/src/js/entropy.js
+++ b/src/js/entropy.js
@@ -120,97 +120,9 @@ 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
-        // total possible 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
+        // Cards binary must be handled differently, since they're not replaced
         if (base.asInt == 52) {
-            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);
-            // Use a bunch of sorted decks to measure entropy from, populated
-            // as needed.
-            var sortedDecks = [];
-            // Initialize the final entropy value for these cards
-            var entropyInt = BigInteger.ZERO;
-            // Track how many instances of each card have been used, and thus
-            // how many decks are in use.
-            var cardCounts = {};
-            // Track the total bits of entropy that remain, which diminishes as
-            // each card is drawn.
-            var totalBitsLeft = numberOfBits;
-            // Work out entropy contribution of each card drawn
-            for (var i=0; i<base.parts.length; i++) {
-                // Get the card that was drawn
-                var cardLower = base.parts[i];
-                var card = cardLower.toUpperCase();
-                // Initialize the deck for this card if needed, to track how
-                // much entropy it adds.
-                if (!(card in cardCounts)) {
-                    cardCounts[card] = 0;
-                }
-                // Get the deck this card is from
-                var deckIndex = cardCounts[card];
-                while (deckIndex > sortedDecks.length-1) {
-                    sortedDecks.push(getSortedDeck());
-                }
-                // See how many bits this card contributes (depends on how many
-                // are left in the deck it's from)
-                var deckForCard = sortedDecks[deckIndex];
-                var cardsLeftInDeck = deckForCard.length;
-                var additionalBits = Math.log2(cardsLeftInDeck);
-                // Work out the min and max value for this card
-                var nextTotalBitsLeft = totalBitsLeft - additionalBits;
-                var minPossibleNewEntropy = TWO.pow(nextTotalBitsLeft).subtract(1);
-                var maxPossibleNewEntropy = TWO.pow(totalBitsLeft).subtract(1);
-                var diff = maxPossibleNewEntropy.subtract(minPossibleNewEntropy);
-                // BigInteger aggresively floors numbers which greatly affects
-                // the small numbers. In that case, use native Math library
-                var useBigInt = totalBitsLeft >= 32;
-                if (!useBigInt) {
-                    minPossibleNewEntropy = Math.round(Math.pow(2, nextTotalBitsLeft)-1);
-                    maxPossibleNewEntropy = Math.round(Math.pow(2, totalBitsLeft)-1);
-                    diff = maxPossibleNewEntropy - minPossibleNewEntropy;
-                }
-                // Scale the value between possible min and max depending on
-                // this card value
-                var thisCardIndex = deckForCard.indexOf(card);
-                var toAdd = BigInteger.ZERO;
-                if (cardsLeftInDeck > 1) {
-                    if (useBigInt) {
-                        toAdd = diff.multiply(thisCardIndex)
-                            .divide(deckForCard.length - 1)
-                            .add(minPossibleNewEntropy);
-                    }
-                    else {
-                        var ratio = thisCardIndex / (deckForCard.length -1);
-                        var f = diff * ratio;
-                        toAdd = new BigInteger(f).add(minPossibleNewEntropy);
-                    }
-                }
-                // Add this card entropy to existing entropy
-                entropyInt = entropyInt.add(toAdd);
-                // Remove this card from the deck it comes from
-                deckForCard.splice(thisCardIndex,1);
-                // Ensure the next insance of this card uses the next deck
-                cardCounts[card] = cardCounts[card] + 1;
-                // Next card drawn has less total remaining bits to work with
-                totalBitsLeft = nextTotalBitsLeft;
-            }
-            // Convert to binary
-            var entropyBin = entropyInt.toString(2);
-            var numberOfBitsInt = Math.floor(numberOfBits);
-            while (entropyBin.length < numberOfBitsInt) {
-                entropyBin = "0" + entropyBin;
-            }
+            entropyBin = getCardBinary(base.parts);
         }
         // Supply a 'filtered' entropy string for display purposes
         var entropyClean = base.parts.join("");
@@ -319,6 +231,83 @@ window.Entropy = new (function() {
         }
     }
 
+    // Assume cards are NOT replaced.
+    // Additional entropy decreases as more cards are used. This means
+    // total possible 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
+    function getCardBinary(cards) {
+        // Track how many instances of each card have been used, and thus
+        // how many decks are in use.
+        var cardCounts = {};
+        var numberOfDecks = 0;
+        // Work out number of decks by max(duplicates)
+        for (var i=0; i<cards.length; i++) {
+            // Get the card that was drawn
+            var cardLower = cards[i];
+            var card = cardLower.toUpperCase();
+            // Initialize the count for this card if needed
+            if (!(card in cardCounts)) {
+                cardCounts[card] = 0;
+            }
+            cardCounts[card] += 1;
+            // See if this is max(duplicates)
+            if (cardCounts[card] > numberOfDecks) {
+                numberOfDecks = cardCounts[card];
+            }
+        }
+        // Work out the total number of bits for this many decks
+        // See http://crypto.stackexchange.com/q/41886
+        var gainedBits = Math.log2(factorial(52 * numberOfDecks));
+        var lostBits = 52 * Math.log2(factorial(numberOfDecks));
+        var maxBits = gainedBits - lostBits;
+        // Convert the drawn cards to a binary representation.
+        // The exact technique for doing this is unclear.
+        // See
+        // http://crypto.stackexchange.com/a/41896
+        // "I even doubt that this is well defined (only the average entropy
+        // is, I believe)."
+        // See
+        // https://github.com/iancoleman/bip39/issues/33#issuecomment-263021856
+        // "The binary representation can be the first log(permutations,2) bits
+        // of the sha-2 hash of the normalized deck string."
+        //
+        // In this specific implementation, the first N bits of the hash of the
+        // normalized cards string is being used. Uppercase, no spaces; eg
+        // sha256("AH8DQSTC2H")
+        var totalCards = numberOfDecks * 52;
+        var percentUsed = cards.length / totalCards;
+        // Calculate the average number of bits of entropy for the number of
+        // cards drawn.
+        var numberOfBits = Math.floor(maxBits * percentUsed);
+        // Create a normalized string of the selected cards
+        var normalizedCards = cards.join("").toUpperCase();
+        // Convert to binary using the SHA256 hash of the normalized cards.
+        // If the number of bits is more than 256, multiple rounds of hashing
+        // are used until the required number of bits is reached.
+        var entropyBin = "";
+        var iterations = 0;
+        while (entropyBin.length < numberOfBits) {
+            var hashedCards = sjcl.hash.sha256.hash(normalizedCards);
+            for (var j=0; j<iterations; j++) {
+                hashedCards = sjcl.hash.sha256.hash(hashedCards);
+            }
+            var hashHex = sjcl.codec.hex.fromBits(hashedCards);
+            for (var i=0; i<hashHex.length; i++) {
+                var decimal = parseInt(hashHex[i], 16);
+                var binary = decimal.toString(2);
+                while (binary.length < 4) {
+                    binary = "0" + binary;
+                }
+                entropyBin = entropyBin + binary;
+            }
+            iterations = iterations + 1;
+        }
+        // Truncate to the appropriate number of bits.
+        entropyBin = entropyBin.substring(0, numberOfBits);
+        return entropyBin;
+    }
+
     // Polyfill for Math.log2
     // See https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/log2#Polyfill
     Math.log2 = Math.log2 || function(x) {
diff --git a/tests.js b/tests.js
index c7d92e4..4f8f60f 100644
--- a/tests.js
+++ b/tests.js
@@ -2149,10 +2149,11 @@ page.open(url, function(status) {
         catch (e) {
             return e.message;
         }
-        // Leading zeros for card entropy as binary string
+        // Leading zeros for card entropy as binary string.
+        // Card entropy is hashed so 2c does not produce leading zeros.
         try {
-            e = Entropy.fromString("2c");
-            if (e.binaryStr != "00001") {
+            e = Entropy.fromString("4c");
+            if (e.binaryStr != "0001") {
                 return "Card entropy as binary has leading zeros";
             }
         }
@@ -2184,24 +2185,24 @@ page.open(url, function(status) {
         // [ cards, binary ]
         try {
             var cards = [
-                [ "ac", "00000" ],
-                [ "acqs", "00001100011" ],
-                [ "acks", "00001100100" ],
-                [ "2cac", "00001100101" ],
-                [ "2c", "00001" ],
-                [ "3d", "01111" ],
-                [ "4h", "11101" ],
-                [ "5s", "101011" ],
-                [ "6c", "00101" ],
-                [ "7d", "10011" ],
-                [ "8h", "100001" ],
-                [ "9s", "101111" ],
-                [ "tc", "01001" ],
-                [ "jd", "10111" ],
-                [ "qh", "100101" ],
-                [ "ks", "110011" ],
-                [ "ks2c", "101001011100" ],
-                [ "KS2C", "101001011100" ],
+                [ "ac", "0100" ],
+                [ "acqs", "10111101" ],
+                [ "acks", "11110000" ],
+                [ "2cac", "11000010" ],
+                [ "2c", "1000" ],
+                [ "3d", "1111" ],
+                [ "4h", "0011" ],
+                [ "5s", "1001" ],
+                [ "6c", "1011" ],
+                [ "7d", "1101" ],
+                [ "8h", "1011" ],
+                [ "9s", "1010" ],
+                [ "tc", "1101" ],
+                [ "jd", "1101" ],
+                [ "qh", "1100" ],
+                [ "ks", "1111" ],
+                [ "ks2c", "10000001" ],
+                [ "KS2C", "10000001" ],
             ];
             for (var i=0; i<cards.length; i++) {
                 var card = cards[i][0];
@@ -2644,7 +2645,7 @@ page.open(url, function(status) {
             entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqhkhas2s3s4s5s6s7s8s9stsjsqsks3d",
             type: "card (full deck, 1 duplicate: 3d)",
             events: 53,
-            bits: 231,
+            bits: 254,
             words: 21,
             strength: "extremely strong",
         },
@@ -2652,7 +2653,7 @@ page.open(url, function(status) {
             entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqhkhas2s3s4s5s6s7s8s9stsjsqs3d4d",
             type: "card (2 duplicates: 3d 4d, 1 missing: KS)",
             events: 53,
-            bits: 231,
+            bits: 254,
             words: 21,
             strength: "extremely strong",
         },
@@ -2660,8 +2661,8 @@ page.open(url, function(status) {
             entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqhkhas2s3s4s5s6s7s8s9stsjsqs3d4d5d6d",
             type: "card (4 duplicates: 3d 4d 5d..., 1 missing: KS)",
             events: 53,
-            bits: 242,
-            words: 21,
+            bits: 264,
+            words: 24,
             strength: "extremely strong",
         },
         // Next test was throwing uncaught error in zxcvbn
@@ -2670,8 +2671,8 @@ page.open(url, function(status) {
             entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqhkhas2s3s4s5s6s7s8s9stsjsqsksac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqhkhas2s3s4s5s6s7s8s9stsjsqsks",
             type: "card (full deck, 52 duplicates: ac 2c 3c...)",
             events: 104,
-            bits: 451,
-            words: 42,
+            bits: 499,
+            words: 45,
             strength: "extremely strong",
         },
         // Case insensitivity to duplicate cards
@@ -2679,7 +2680,7 @@ page.open(url, function(status) {
             entropy: "asAS",
             type: "card (1 duplicate: AS)",
             events: 2,
-            bits: 12,
+            bits: 9,
             words: 0,
             strength: "extremely weak",
         },
@@ -2687,7 +2688,7 @@ page.open(url, function(status) {
             entropy: "ASas",
             type: "card (1 duplicate: as)",
             events: 2,
-            bits: 12,
+            bits: 9,
             words: 0,
             strength: "extremely weak",
         },
@@ -2696,23 +2697,23 @@ page.open(url, function(status) {
             entropy: "ac2c3c4c5c6c7c8c  tcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqhkhas2s3s4s5s6s7s8s9stsjsqsks",
             type: "card (1 missing: 9C)",
             events: 51,
-            bits: 225,
-            words: 21,
+            bits: 221,
+            words: 18,
             strength: "extremely strong",
         },
         {
             entropy: "ac2c3c4c5c6c7c8c  tcjcqckcad2d3d4d  6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqhkhas2s3s4s5s6s7s8s9stsjsqsks",
             type: "card (2 missing: 9C 5D)",
             events: 50,
-            bits: 224,
-            words: 21,
+            bits: 216,
+            words: 18,
             strength: "extremely strong",
         },
         {
             entropy: "ac2c3c4c5c6c7c8c  tcjcqckcad2d3d4d  6d7d8d9dtdjd  kdah2h3h  5h6h7h8h9hthjhqhkhas2s3s4s5s6s7s8s9stsjsqsks",
             type: "card (4 missing: 9C 5D QD...)",
             events: 48,
-            bits: 220,
+            bits: 208,
             words: 18,
             strength: "extremely strong",
         },
@@ -2721,140 +2722,10 @@ page.open(url, function(status) {
             entropy: "ac2c3c4c5c6c7c8c  tcjcqckcad2d3d4d  6d  8d9d  jd  kdah2h3h  5h6h7h8h9hthjhqhkh  2s3s4s5s6s7s8s9stsjsqsks",
             type: "card",
             events: 45,
-            bits: 213,
+            bits: 195,
             words: 18,
             strength: "extremely strong",
         },
-        // Additional entropy from each card decreases as deck is depleted.
-        // Check the boundaries of this depletion
-        // See table at https://github.com/iancoleman/bip39/issues/33#issuecomment-262855862
-        // for following values of 'events, bits, words'
-        // 2 cards remaining = 21 words
-        {
-            entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqhkhas2s3s4s5s6s7s8s9stsjs",
-            type: "card (2 missing: QS KS)",
-            events: 50,
-            bits: 224,
-            words: 21,
-            strength: "extremely strong",
-        },
-        // 3 cards remaining = 18 words
-        {
-            entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqhkhas2s3s4s5s6s7s8s9sts",
-            type: "card (3 missing: JS QS KS)",
-            events: 49,
-            bits: 222, // table uses different rounding - 222.99604
-            words: 18,
-            strength: "extremely strong",
-        },
-        // 13 cards remaining = 18 words
-        {
-            entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqhkh",
-            type: "card",
-            events: 39,
-            bits: 193,
-            words: 18,
-            strength: "extremely strong",
-        },
-        // 14 cards remaining = 15 words
-        {
-            entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqh",
-            type: "card",
-            events: 38,
-            bits: 189,
-            words: 15,
-            strength: "very strong",
-        },
-        // 21 cards remaining = 15 words
-        {
-            entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h",
-            type: "card",
-            events: 31,
-            bits: 160,
-            words: 15,
-            strength: "very strong",
-        },
-        // 22 cards remaining = 12 words
-        {
-            entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h",
-            type: "card",
-            events: 30,
-            bits: 155,
-            words: 12,
-            strength: "strong",
-        },
-        // 27 cards remaining = 12 words
-        {
-            entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqd",
-            type: "card",
-            events: 25,
-            bits: 132,
-            words: 12,
-            strength: "strong",
-        },
-        // 28 cards remaining = 9 words
-        {
-            entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjd",
-            type: "card",
-            events: 24,
-            bits: 127,
-            words: 9,
-            strength: "weak",
-        },
-        // 34 cards remaining = 9 words
-        {
-            entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d",
-            type: "card",
-            events: 18,
-            bits: 97,
-            words: 9,
-            strength: "weak",
-        },
-        // 35 cards remaining = 6 words
-        {
-            entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d",
-            type: "card",
-            events: 17,
-            bits: 92,
-            words: 6,
-            strength: "very weak",
-        },
-        // 40 cards remaining = 6 words
-        {
-            entropy: "ac2c3c4c5c6c7c8c9ctcjcqc",
-            type: "card",
-            events: 12,
-            bits: 66,
-            words: 6,
-            strength: "very weak",
-        },
-        // 41 cards remaining = 3 words
-        {
-            entropy: "ac2c3c4c5c6c7c8c9ctcjc",
-            type: "card",
-            events: 11,
-            bits: 61,
-            words: 3,
-            strength: "extremely weak",
-        },
-        // 46 cards remaining = 3 words
-        {
-            entropy: "ac2c3c4c5c6c",
-            type: "card",
-            events: 6,
-            bits: 33,
-            words: 3,
-            strength: "extremely weak",
-        },
-        // 47 cards remaining = 0 words
-        {
-            entropy: "ac2c3c4c5c",
-            type: "card",
-            events: 5,
-            bits: 28,
-            words: 0,
-            strength: "extremely weak",
-        },
     ];
     // use entropy
     page.evaluate(function() {
@@ -2894,6 +2765,7 @@ page.open(url, function(status) {
             if (test.words == 0) {
                 if (mnemonic.length > 0) {
                     console.log("Mnemonic length for " + test.strength + " strength is not " + test.words);
+                    console.log("Entropy: " + test.entropy);
                     console.log("Mnemonic: " + mnemonic);
                     fail();
                 }
@@ -2901,6 +2773,7 @@ page.open(url, function(status) {
             else {
                 if (mnemonic.split(" ").length != test.words) {
                     console.log("Mnemonic length for " + test.strength + " strength is not " + test.words);
+                    console.log("Entropy: " + test.entropy);
                     console.log("Mnemonic: " + mnemonic);
                     fail();
                 }
@@ -3107,18 +2980,6 @@ page.open(url, function(status) {
             var newPhrase = page.evaluate(function() {
                 return $(".phrase").val();
             });
-            // check raw entropy is in use, ie the first bits should remain the same
-            var startLength = 20;
-            var originalPhraseStart = originalPhrase.substring(0,startLength);
-            var newPhraseStart = newPhrase.substring(0,startLength);
-            if (newPhraseStart != originalPhraseStart) {
-                console.log("Changing last 12 cards changed first portion of mnemonic");
-                console.log("Original:");
-                console.log(originalPhrase);
-                console.log("New:");
-                console.log(newPhrase);
-                fail();
-            }
             // check the phrase has changed
             if (newPhrase == originalPhrase) {
                 console.log("Changing last 12 cards does not change mnemonic");