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("");
}
}
+ // 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) {
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";
}
}
// [ 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];
entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqhkhas2s3s4s5s6s7s8s9stsjsqsks3d",
type: "card (full deck, 1 duplicate: 3d)",
events: 53,
- bits: 231,
+ bits: 254,
words: 21,
strength: "extremely strong",
},
entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqhkhas2s3s4s5s6s7s8s9stsjsqs3d4d",
type: "card (2 duplicates: 3d 4d, 1 missing: KS)",
events: 53,
- bits: 231,
+ bits: 254,
words: 21,
strength: "extremely strong",
},
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
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
entropy: "asAS",
type: "card (1 duplicate: AS)",
events: 2,
- bits: 12,
+ bits: 9,
words: 0,
strength: "extremely weak",
},
entropy: "ASas",
type: "card (1 duplicate: as)",
events: 2,
- bits: 12,
+ bits: 9,
words: 0,
strength: "extremely weak",
},
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",
},
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() {
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();
}
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();
}
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");
projects / perso / Immae / Projets / Cryptomonnaies / BIP39.git / commitdiff
