X-Git-Url: https://git.immae.eu/?p=perso%2FImmae%2FProjets%2FCryptomonnaies%2FBIP39.git;a=blobdiff_plain;f=src%2Fjs%2Fentropy.js;h=62b271125a4939ac8d2249cd9d1508cadf966ae9;hp=8a0c799f549ed4d2ef8b6b75e41592c0a0ef7f8f;hb=22f8766947313324c4acda2de4f170475d3c5ded;hpb=886f06ee6bbca2e6e05109dbd7e264bdea35238f diff --git a/src/js/entropy.js b/src/js/entropy.js index 8a0c799..62b2711 100644 --- a/src/js/entropy.js +++ b/src/js/entropy.js @@ -16,7 +16,7 @@ window.Entropy = new (function() { - var TWO = new BigInteger(2); + var TWO = new libs.BigInteger.BigInteger(2); // matchers returns an array of the matched events for each type of entropy. // eg @@ -67,9 +67,9 @@ window.Entropy = new (function() { return ints; } - this.fromString = function(rawEntropyStr) { + this.fromString = function(rawEntropyStr, baseStr) { // Find type of entropy being used (binary, hex, dice etc) - var base = getBase(rawEntropyStr); + var base = getBase(rawEntropyStr, baseStr); // Convert dice to base6 entropy (ie 1-6 to 0-5) // This is done by changing all 6s to 0s if (base.str == "dice") { @@ -103,11 +103,11 @@ window.Entropy = new (function() { // Convert base.ints to BigInteger. // Due to using unusual bases, eg cards of base52, this is not as simple as // using BigInteger.parse() - var entropyInt = BigInteger.ZERO; + var entropyInt = libs.BigInteger.BigInteger.ZERO; for (var i=base.ints.length-1; i>=0; i--) { - var thisInt = BigInteger.parse(base.ints[i]); + var thisInt = libs.BigInteger.BigInteger.parse(base.ints[i]); var power = (base.ints.length - 1) - i; - var additionalEntropy = BigInteger.parse(base.asInt).pow(power).multiply(thisInt); + var additionalEntropy = libs.BigInteger.BigInteger.parse(base.asInt).pow(power).multiply(thisInt); entropyInt = entropyInt.add(additionalEntropy); } // Convert entropy to binary @@ -120,97 +120,13 @@ 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 + // Calculate the number of bits per event + var bitsPerEvent = Math.log2(base.asInt); + // 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; - } + var cardEntropy = processCardEntropy(base.parts); + entropyBin = cardEntropy.binaryStr; + bitsPerEvent = cardEntropy.bitsPerEvent; } // Supply a 'filtered' entropy string for display purposes var entropyClean = base.parts.join(""); @@ -232,6 +148,7 @@ window.Entropy = new (function() { binaryStr: entropyBin, cleanStr: entropyClean, cleanHtml: entropyHtml, + bitsPerEvent: bitsPerEvent, base: base, } return e; @@ -249,13 +166,14 @@ window.Entropy = new (function() { return s; } - function getBase(str) { + function getBase(str, baseStr) { // Need to get the lowest base for the supplied entropy. // This prevents interpreting, say, dice rolls as hexadecimal. var binaryMatches = matchers.binary(str); var hexMatches = matchers.hex(str); + var autodetect = baseStr === undefined; // Find the lowest base that can be used, whilst ignoring any irrelevant chars - if (binaryMatches.length == hexMatches.length && hexMatches.length > 0) { + if ((binaryMatches.length == hexMatches.length && hexMatches.length > 0 && autodetect) || baseStr === "binary") { var ints = binaryMatches.map(function(i) { return parseInt(i, 2) }); return { ints: ints, @@ -266,7 +184,7 @@ window.Entropy = new (function() { } } var cardMatches = matchers.card(str); - if (cardMatches.length >= hexMatches.length / 2) { + if ((cardMatches.length >= hexMatches.length / 2 && autodetect) || baseStr === "card") { var ints = convertCardsToInts(cardMatches); return { ints: ints, @@ -277,7 +195,7 @@ window.Entropy = new (function() { } } var diceMatches = matchers.dice(str); - if (diceMatches.length == hexMatches.length && hexMatches.length > 0) { + if ((diceMatches.length == hexMatches.length && hexMatches.length > 0 && autodetect) || baseStr === "dice") { var ints = diceMatches.map(function(i) { return parseInt(i) }); return { ints: ints, @@ -288,7 +206,7 @@ window.Entropy = new (function() { } } var base6Matches = matchers.base6(str); - if (base6Matches.length == hexMatches.length && hexMatches.length > 0) { + if ((base6Matches.length == hexMatches.length && hexMatches.length > 0 && autodetect) || baseStr === "base 6") { var ints = base6Matches.map(function(i) { return parseInt(i) }); return { ints: ints, @@ -299,7 +217,7 @@ window.Entropy = new (function() { } } var base10Matches = matchers.base10(str); - if (base10Matches.length == hexMatches.length && hexMatches.length > 0) { + if ((base10Matches.length == hexMatches.length && hexMatches.length > 0 && autodetect) || baseStr === "base 10") { var ints = base10Matches.map(function(i) { return parseInt(i) }); return { ints: ints, @@ -319,6 +237,90 @@ 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 processCardEntropy(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 = 0; + // Equivalent of Math.log2(factorial(52*numberOfDecks)) + // which becomes infinity for numberOfDecks > 4 + for (var i=1; i<=52*numberOfDecks; i++) { + gainedBits = gainedBits + Math.log2(i); + } + 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 hashes + // 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 + ":" + iterations); + var hashHex = sjcl.codec.hex.fromBits(hashedCards); + for (var i=0; i