src/js/entropy.js

   1 /*
   2  * Detects entropy from a string.
   3  *
   4  * Formats include:
   5  * binary [0-1]
   6  * base 6 [0-5]
   7  * dice 6 [1-6]
   8  * decimal [0-9]
   9  * hexadecimal [0-9A-F]
  10  * card [A2-9TJQK][CDHS]
  11  *
  12  * Automatically uses lowest entropy to avoid issues such as interpretting 0101
  13  * as hexadecimal which would be 16 bits when really it's only 4 bits of binary
  14  * entropy.
  15  */
  16
  17 window.Entropy = new (function() {
  18
  19     var TWO = new libs.BigInteger.BigInteger(2);
  20
  21     // matchers returns an array of the matched events for each type of entropy.
  22     // eg
  23     // matchers.binary("010") returns ["0", "1", "0"]
  24     // matchers.binary("a10") returns ["1", "0"]
  25     // matchers.hex("a10") returns ["a", "1", "0"]
  26     var matchers = {
  27         binary: function(str) {
  28             return str.match(/[0-1]/gi) || [];
  29         },
  30         base6: function(str) {
  31             return str.match(/[0-5]/gi) || [];
  32         },
  33         dice: function(str) {
  34             return str.match(/[1-6]/gi) || []; // ie dice numbers
  35         },
  36         base10: function(str) {
  37             return str.match(/[0-9]/gi) || [];
  38         },
  39         hex: function(str) {
  40             return str.match(/[0-9A-F]/gi) || [];
  41         },
  42         card: function(str) {
  43             // Format is NumberSuit, eg
  44             // AH ace of hearts
  45             // 8C eight of clubs
  46             // TD ten of diamonds
  47             // JS jack of spades
  48             // QH queen of hearts
  49             // KC king of clubs
  50             return str.match(/([A2-9TJQK][CDHS])/gi) || [];
  51         }
  52     }
  53
  54     // Convert array of cards from ["ac", "4d", "ks"]
  55     // to numbers between 0 and 51 [0, 16, 51]
  56     function convertCardsToInts(cards) {
  57         var ints = [];
  58         var values = "a23456789tjqk";
  59         var suits = "cdhs";
  60         for (var i=0; i<cards.length; i++) {
  61             var card = cards[i].toLowerCase();
  62             var value = card[0];
  63             var suit = card[1];
  64             var asInt = 13 * suits.indexOf(suit) + values.indexOf(value);
  65             ints.push(asInt);
  66         }
  67         return ints;
  68     }
  69
  70     this.fromString = function(rawEntropyStr, baseStr) {
  71         // Find type of entropy being used (binary, hex, dice etc)
  72         var base = getBase(rawEntropyStr, baseStr);
  73         // Convert dice to base6 entropy (ie 1-6 to 0-5)
  74         // This is done by changing all 6s to 0s
  75         if (base.str == "dice") {
  76             var newParts = [];
  77             var newInts = [];
  78             for (var i=0; i<base.parts.length; i++) {
  79                 var c = base.parts[i];
  80                 if ("12345".indexOf(c) > -1) {
  81                     newParts[i] = base.parts[i];
  82                     newInts[i] = base.ints[i];
  83                 }
  84                 else {
  85                     newParts[i] = "0";
  86                     newInts[i] = 0;
  87                 }
  88             }
  89             base.str = "base 6 (dice)";
  90             base.ints = newInts;
  91             base.parts = newParts;
  92             base.matcher = matchers.base6;
  93         }
  94         // Detect empty entropy
  95         if (base.parts.length == 0) {
  96             return {
  97                 binaryStr: "",
  98                 cleanStr: "",
  99                 cleanHtml: "",
 100                 base: base,
 101             };
 102         }
 103         // Convert base.ints to BigInteger.
 104         // Due to using unusual bases, eg cards of base52, this is not as simple as
 105         // using BigInteger.parse()
 106         var entropyInt = libs.BigInteger.BigInteger.ZERO;
 107         for (var i=base.ints.length-1; i>=0; i--) {
 108             var thisInt = libs.BigInteger.BigInteger.parse(base.ints[i]);
 109             var power = (base.ints.length - 1) - i;
 110             var additionalEntropy = libs.BigInteger.BigInteger.parse(base.asInt).pow(power).multiply(thisInt);
 111             entropyInt = entropyInt.add(additionalEntropy);
 112         }
 113         // Convert entropy to binary
 114         var entropyBin = entropyInt.toString(2);
 115         // If the first integer is small, it must be padded with zeros.
 116         // Otherwise the chance of the first bit being 1 is 100%, which is
 117         // obviously incorrect.
 118         // This is not perfect for non-2^n bases.
 119         var expectedBits = Math.floor(base.parts.length * Math.log2(base.asInt));
 120         while (entropyBin.length < expectedBits) {
 121             entropyBin = "0" + entropyBin;
 122         }
 123         // Calculate the number of bits per event
 124         var bitsPerEvent = Math.log2(base.asInt);
 125         // Cards binary must be handled differently, since they're not replaced
 126         if (base.asInt == 52) {
 127             var cardEntropy = processCardEntropy(base.parts);
 128             entropyBin = cardEntropy.binaryStr;
 129             bitsPerEvent = cardEntropy.bitsPerEvent;
 130         }
 131         // Supply a 'filtered' entropy string for display purposes
 132         var entropyClean = base.parts.join("");
 133         var entropyHtml = base.parts.join("");
 134         if (base.asInt == 52) {
 135             entropyClean = base.parts.join(" ").toUpperCase();
 136             entropyClean = entropyClean.replace(/C/g, "\u2663");
 137             entropyClean = entropyClean.replace(/D/g, "\u2666");
 138             entropyClean = entropyClean.replace(/H/g, "\u2665");
 139             entropyClean = entropyClean.replace(/S/g, "\u2660");
 140             entropyHtml = base.parts.join(" ").toUpperCase();
 141             entropyHtml = entropyHtml.replace(/C/g, "<span class='card-suit club'>\u2663</span>");
 142             entropyHtml = entropyHtml.replace(/D/g, "<span class='card-suit diamond'>\u2666</span>");
 143             entropyHtml = entropyHtml.replace(/H/g, "<span class='card-suit heart'>\u2665</span>");
 144             entropyHtml = entropyHtml.replace(/S/g, "<span class='card-suit spade'>\u2660</span>");
 145         }
 146         // Return the result
 147         var e = {
 148             binaryStr: entropyBin,
 149             cleanStr: entropyClean,
 150             cleanHtml: entropyHtml,
 151             bitsPerEvent: bitsPerEvent,
 152             base: base,
 153         }
 154         return e;
 155     }
 156
 157     function getSortedDeck() {
 158         var s = [];
 159         var suits = "CDHS";
 160         var values = "A23456789TJQK";
 161         for (var i=0; i<suits.length; i++) {
 162             for (var j=0; j<values.length; j++) {
 163                 s.push(values[j]+suits[i]);
 164             }
 165         }
 166         return s;
 167     }
 168
 169     function getBase(str, baseStr) {
 170         // Need to get the lowest base for the supplied entropy.
 171         // This prevents interpreting, say, dice rolls as hexadecimal.
 172         var binaryMatches = matchers.binary(str);
 173         var hexMatches = matchers.hex(str);
 174         var autodetect = baseStr === undefined;
 175         // Find the lowest base that can be used, whilst ignoring any irrelevant chars
 176         if ((binaryMatches.length == hexMatches.length && hexMatches.length > 0 && autodetect) || baseStr === "binary") {
 177             var ints = binaryMatches.map(function(i) { return parseInt(i, 2) });
 178             return {
 179                 ints: ints,
 180                 parts: binaryMatches,
 181                 matcher: matchers.binary,
 182                 asInt: 2,
 183                 str: "binary",
 184             }
 185         }
 186         var cardMatches = matchers.card(str);
 187         if ((cardMatches.length >= hexMatches.length / 2 && autodetect) || baseStr === "card") {
 188             var ints = convertCardsToInts(cardMatches);
 189             return {
 190                 ints: ints,
 191                 parts: cardMatches,
 192                 matcher: matchers.card,
 193                 asInt: 52,
 194                 str: "card",
 195             }
 196         }
 197         var diceMatches = matchers.dice(str);
 198         if ((diceMatches.length == hexMatches.length && hexMatches.length > 0 && autodetect) || baseStr === "dice") {
 199             var ints = diceMatches.map(function(i) { return parseInt(i) });
 200             return {
 201                 ints: ints,
 202                 parts: diceMatches,
 203                 matcher: matchers.dice,
 204                 asInt: 6,
 205                 str: "dice",
 206             }
 207         }
 208         var base6Matches = matchers.base6(str);
 209         if ((base6Matches.length == hexMatches.length && hexMatches.length > 0 && autodetect) || baseStr === "base 6") {
 210             var ints = base6Matches.map(function(i) { return parseInt(i) });
 211             return {
 212                 ints: ints,
 213                 parts: base6Matches,
 214                 matcher: matchers.base6,
 215                 asInt: 6,
 216                 str: "base 6",
 217             }
 218         }
 219         var base10Matches = matchers.base10(str);
 220         if ((base10Matches.length == hexMatches.length && hexMatches.length > 0 && autodetect) || baseStr === "base 10") {
 221             var ints = base10Matches.map(function(i) { return parseInt(i) });
 222             return {
 223                 ints: ints,
 224                 parts: base10Matches,
 225                 matcher: matchers.base10,
 226                 asInt: 10,
 227                 str: "base 10",
 228             }
 229         }
 230         var ints = hexMatches.map(function(i) { return parseInt(i, 16) });
 231         return {
 232             ints: ints,
 233             parts: hexMatches,
 234             matcher: matchers.hex,
 235             asInt: 16,
 236             str: "hexadecimal",
 237         }
 238     }
 239
 240     // Assume cards are NOT replaced.
 241     // Additional entropy decreases as more cards are used. This means
 242     // total possible entropy is measured using n!, not base^n.
 243     // eg the second last card can be only one of two, not one of fifty two
 244     // so the added entropy for that card is only one bit at most
 245     function processCardEntropy(cards) {
 246         // Track how many instances of each card have been used, and thus
 247         // how many decks are in use.
 248         var cardCounts = {};
 249         var numberOfDecks = 0;
 250         // Work out number of decks by max(duplicates)
 251         for (var i=0; i<cards.length; i++) {
 252             // Get the card that was drawn
 253             var cardLower = cards[i];
 254             var card = cardLower.toUpperCase();
 255             // Initialize the count for this card if needed
 256             if (!(card in cardCounts)) {
 257                 cardCounts[card] = 0;
 258             }
 259             cardCounts[card] += 1;
 260             // See if this is max(duplicates)
 261             if (cardCounts[card] > numberOfDecks) {
 262                 numberOfDecks = cardCounts[card];
 263             }
 264         }
 265         // Work out the total number of bits for this many decks
 266         // See http://crypto.stackexchange.com/q/41886
 267         var gainedBits = 0;
 268         // Equivalent of Math.log2(factorial(52*numberOfDecks))
 269         // which becomes infinity for numberOfDecks > 4
 270         for (var i=1; i<=52*numberOfDecks; i++) {
 271             gainedBits = gainedBits + Math.log2(i);
 272         }
 273         var lostBits = 52 * Math.log2(factorial(numberOfDecks));
 274         var maxBits = gainedBits - lostBits;
 275         // Convert the drawn cards to a binary representation.
 276         // The exact technique for doing this is unclear.
 277         // See
 278         // http://crypto.stackexchange.com/a/41896
 279         // "I even doubt that this is well defined (only the average entropy
 280         // is, I believe)."
 281         // See
 282         // https://github.com/iancoleman/bip39/issues/33#issuecomment-263021856
 283         // "The binary representation can be the first log(permutations,2) bits
 284         // of the sha-2 hash of the normalized deck string."
 285         //
 286         // In this specific implementation, the first N bits of the hash of the
 287         // normalized cards string is being used. Uppercase, no spaces; eg
 288         // sha256("AH8DQSTC2H")
 289         var totalCards = numberOfDecks * 52;
 290         var percentUsed = cards.length / totalCards;
 291         // Calculate the average number of bits of entropy for the number of
 292         // cards drawn.
 293         var numberOfBits = Math.floor(maxBits * percentUsed);
 294         // Create a normalized string of the selected cards
 295         var normalizedCards = cards.join("").toUpperCase();
 296         // Convert to binary using the SHA256 hash of the normalized cards.
 297         // If the number of bits is more than 256, multiple hashes
 298         // are used until the required number of bits is reached.
 299         var entropyBin = "";
 300         var iterations = 0;
 301         while (entropyBin.length < numberOfBits) {
 302             var hashedCards = sjcl.hash.sha256.hash(normalizedCards + ":" + iterations);
 303             var hashHex = sjcl.codec.hex.fromBits(hashedCards);
 304             for (var i=0; i<hashHex.length; i++) {
 305                 var decimal = parseInt(hashHex[i], 16);
 306                 var binary = decimal.toString(2);
 307                 while (binary.length < 4) {
 308                     binary = "0" + binary;
 309                 }
 310                 entropyBin = entropyBin + binary;
 311             }
 312             iterations = iterations + 1;
 313         }
 314         // Truncate to the appropriate number of bits.
 315         entropyBin = entropyBin.substring(0, numberOfBits);
 316         // Get the number of bits per event
 317         bitsPerEvent = maxBits / totalCards;
 318         return {
 319             binaryStr: entropyBin,
 320             bitsPerEvent: bitsPerEvent,
 321         }
 322     }
 323
 324     // Polyfill for Math.log2
 325     // See https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/log2#Polyfill
 326     Math.log2 = Math.log2 || function(x) {
 327         // The polyfill isn't good enough because of the poor accuracy of
 328         // Math.LOG2E
 329         // log2(8) gave 2.9999999999999996 which when floored causes issues.
 330         // So instead use the BigInteger library to get it right.
 331         return libs.BigInteger.BigInteger.log(x) / libs.BigInteger.BigInteger.log(2);
 332     };
 333
 334     // Depends on BigInteger
 335     function factorial(n) {
 336         if (n == 0) {
 337             return 1;
 338         }
 339         f = libs.BigInteger.BigInteger.ONE;
 340         for (var i=1; i<=n; i++) {
 341             f = f.multiply(new libs.BigInteger.BigInteger(i));
 342         }
 343         return f;
 344     }
 345
 346 })();