From 87ad2c6e4c7987320d8ce147fe9310b702c5deea Mon Sep 17 00:00:00 2001 From: Ian Coleman Date: Wed, 30 Nov 2016 15:30:19 +1100 Subject: [PATCH] Card entropy has improved conversion to binary See http://crypto.stackexchange.com/q/41886 and https://github.com/iancoleman/bip39/issues/33#issuecomment-263021856 --- src/js/entropy.js | 169 +++++++++++++++++------------------- tests.js | 215 ++++++++-------------------------------------- 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 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 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 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"); -- 2.41.0