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 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) {
  71         // Find type of entropy being used (binary, hex, dice etc)
  72         var base = getBase(rawEntropyStr);
  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 = BigInteger.ZERO;
 107         for (var i=base.ints.length-1; i>=0; i--) {
 108             var thisInt = BigInteger.parse(base.ints[i]);
 109             var power = (base.ints.length - 1) - i;
 110             var additionalEntropy = 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         // Assume cards are NOT replaced.
 124         // Additional entropy decreases as more cards are used. This means
 125         // total possible entropy is measured using n!, not base^n.
 126         // eg the second last card can be only one of two, not one of fifty two
 127         // so the added entropy for that card is only one bit at most
 128         if (base.asInt == 52) {
 129             var totalDecks = Math.ceil(base.parts.length / 52);
 130             var totalCards = totalDecks * 52;
 131             var totalCombos = factorial(52).pow(totalDecks);
 132             var totalRemainingCards = totalCards - base.parts.length;
 133             var remainingDecks = Math.floor(totalRemainingCards / 52);
 134             var remainingCards = totalRemainingCards % 52;
 135             var remainingCombos = factorial(52).pow(remainingDecks).multiply(factorial(remainingCards));
 136             var currentCombos = totalCombos.divide(remainingCombos);
 137             var numberOfBits = Math.log2(currentCombos);
 138             var maxWithoutReplace = BigInteger.pow(2, numberOfBits);
 139             // Use a bunch of sorted decks to measure entropy from, populated
 140             // as needed.
 141             var sortedDecks = [];
 142             // Initialize the final entropy value for these cards
 143             var entropyInt = BigInteger.ZERO;
 144             // Track how many instances of each card have been used, and thus
 145             // how many decks are in use.
 146             var cardCounts = {};
 147             // Track the total bits of entropy that remain, which diminishes as
 148             // each card is drawn.
 149             var totalBitsLeft = numberOfBits;
 150             // Work out entropy contribution of each card drawn
 151             for (var i=0; i<base.parts.length; i++) {
 152                 // Get the card that was drawn
 153                 var cardLower = base.parts[i];
 154                 var card = cardLower.toUpperCase();
 155                 // Initialize the deck for this card if needed, to track how
 156                 // much entropy it adds.
 157                 if (!(card in cardCounts)) {
 158                     cardCounts[card] = 0;
 159                 }
 160                 // Get the deck this card is from
 161                 var deckIndex = cardCounts[card];
 162                 while (deckIndex > sortedDecks.length-1) {
 163                     sortedDecks.push(getSortedDeck());
 164                 }
 165                 // See how many bits this card contributes (depends on how many
 166                 // are left in the deck it's from)
 167                 var deckForCard = sortedDecks[deckIndex];
 168                 var cardsLeftInDeck = deckForCard.length;
 169                 var additionalBits = Math.log2(cardsLeftInDeck);
 170                 // Work out the min and max value for this card
 171                 var nextTotalBitsLeft = totalBitsLeft - additionalBits;
 172                 var minPossibleNewEntropy = TWO.pow(nextTotalBitsLeft).subtract(1);
 173                 var maxPossibleNewEntropy = TWO.pow(totalBitsLeft).subtract(1);
 174                 var diff = maxPossibleNewEntropy.subtract(minPossibleNewEntropy);
 175                 // BigInteger aggresively floors numbers which greatly affects
 176                 // the small numbers. In that case, use native Math library
 177                 var useBigInt = totalBitsLeft >= 32;
 178                 if (!useBigInt) {
 179                     minPossibleNewEntropy = Math.round(Math.pow(2, nextTotalBitsLeft)-1);
 180                     maxPossibleNewEntropy = Math.round(Math.pow(2, totalBitsLeft)-1);
 181                     diff = maxPossibleNewEntropy - minPossibleNewEntropy;
 182                 }
 183                 // Scale the value between possible min and max depending on
 184                 // this card value
 185                 var thisCardIndex = deckForCard.indexOf(card);
 186                 var toAdd = BigInteger.ZERO;
 187                 if (cardsLeftInDeck > 1) {
 188                     if (useBigInt) {
 189                         toAdd = diff.multiply(thisCardIndex)
 190                             .divide(deckForCard.length - 1)
 191                             .add(minPossibleNewEntropy);
 192                     }
 193                     else {
 194                         var ratio = thisCardIndex / (deckForCard.length -1);
 195                         var f = diff * ratio;
 196                         toAdd = new BigInteger(f).add(minPossibleNewEntropy);
 197                     }
 198                 }
 199                 // Add this card entropy to existing entropy
 200                 entropyInt = entropyInt.add(toAdd);
 201                 // Remove this card from the deck it comes from
 202                 deckForCard.splice(thisCardIndex,1);
 203                 // Ensure the next insance of this card uses the next deck
 204                 cardCounts[card] = cardCounts[card] + 1;
 205                 // Next card drawn has less total remaining bits to work with
 206                 totalBitsLeft = nextTotalBitsLeft;
 207             }
 208             // Convert to binary
 209             var entropyBin = entropyInt.toString(2);
 210             var numberOfBitsInt = Math.floor(numberOfBits);
 211             while (entropyBin.length < numberOfBitsInt) {
 212                 entropyBin = "0" + entropyBin;
 213             }
 214         }
 215         // Supply a 'filtered' entropy string for display purposes
 216         var entropyClean = base.parts.join("");
 217         var entropyHtml = base.parts.join("");
 218         if (base.asInt == 52) {
 219             entropyClean = base.parts.join(" ").toUpperCase();
 220             entropyClean = entropyClean.replace(/C/g, "\u2663");
 221             entropyClean = entropyClean.replace(/D/g, "\u2666");
 222             entropyClean = entropyClean.replace(/H/g, "\u2665");
 223             entropyClean = entropyClean.replace(/S/g, "\u2660");
 224             entropyHtml = base.parts.join(" ").toUpperCase();
 225             entropyHtml = entropyHtml.replace(/C/g, "<span class='card-suit club'>\u2663</span>");
 226             entropyHtml = entropyHtml.replace(/D/g, "<span class='card-suit diamond'>\u2666</span>");
 227             entropyHtml = entropyHtml.replace(/H/g, "<span class='card-suit heart'>\u2665</span>");
 228             entropyHtml = entropyHtml.replace(/S/g, "<span class='card-suit spade'>\u2660</span>");
 229         }
 230         // Return the result
 231         var e = {
 232             binaryStr: entropyBin,
 233             cleanStr: entropyClean,
 234             cleanHtml: entropyHtml,
 235             base: base,
 236         }
 237         return e;
 238     }
 239
 240     function getSortedDeck() {
 241         var s = [];
 242         var suits = "CDHS";
 243         var values = "A23456789TJQK";
 244         for (var i=0; i<suits.length; i++) {
 245             for (var j=0; j<values.length; j++) {
 246                 s.push(values[j]+suits[i]);
 247             }
 248         }
 249         return s;
 250     }
 251
 252     function getBase(str) {
 253         // Need to get the lowest base for the supplied entropy.
 254         // This prevents interpreting, say, dice rolls as hexadecimal.
 255         var binaryMatches = matchers.binary(str);
 256         var hexMatches = matchers.hex(str);
 257         // Find the lowest base that can be used, whilst ignoring any irrelevant chars
 258         if (binaryMatches.length == hexMatches.length && hexMatches.length > 0) {
 259             var ints = binaryMatches.map(function(i) { return parseInt(i, 2) });
 260             return {
 261                 ints: ints,
 262                 parts: binaryMatches,
 263                 matcher: matchers.binary,
 264                 asInt: 2,
 265                 str: "binary",
 266             }
 267         }
 268         var cardMatches = matchers.card(str);
 269         if (cardMatches.length >= hexMatches.length / 2) {
 270             var ints = convertCardsToInts(cardMatches);
 271             return {
 272                 ints: ints,
 273                 parts: cardMatches,
 274                 matcher: matchers.card,
 275                 asInt: 52,
 276                 str: "card",
 277             }
 278         }
 279         var diceMatches = matchers.dice(str);
 280         if (diceMatches.length == hexMatches.length && hexMatches.length > 0) {
 281             var ints = diceMatches.map(function(i) { return parseInt(i) });
 282             return {
 283                 ints: ints,
 284                 parts: diceMatches,
 285                 matcher: matchers.dice,
 286                 asInt: 6,
 287                 str: "dice",
 288             }
 289         }
 290         var base6Matches = matchers.base6(str);
 291         if (base6Matches.length == hexMatches.length && hexMatches.length > 0) {
 292             var ints = base6Matches.map(function(i) { return parseInt(i) });
 293             return {
 294                 ints: ints,
 295                 parts: base6Matches,
 296                 matcher: matchers.base6,
 297                 asInt: 6,
 298                 str: "base 6",
 299             }
 300         }
 301         var base10Matches = matchers.base10(str);
 302         if (base10Matches.length == hexMatches.length && hexMatches.length > 0) {
 303             var ints = base10Matches.map(function(i) { return parseInt(i) });
 304             return {
 305                 ints: ints,
 306                 parts: base10Matches,
 307                 matcher: matchers.base10,
 308                 asInt: 10,
 309                 str: "base 10",
 310             }
 311         }
 312         var ints = hexMatches.map(function(i) { return parseInt(i, 16) });
 313         return {
 314             ints: ints,
 315             parts: hexMatches,
 316             matcher: matchers.hex,
 317             asInt: 16,
 318             str: "hexadecimal",
 319         }
 320     }
 321
 322     // Polyfill for Math.log2
 323     // See https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/log2#Polyfill
 324     Math.log2 = Math.log2 || function(x) {
 325         // The polyfill isn't good enough because of the poor accuracy of
 326         // Math.LOG2E
 327         // log2(8) gave 2.9999999999999996 which when floored causes issues.
 328         // So instead use the BigInteger library to get it right.
 329         return BigInteger.log(x) / BigInteger.log(2);
 330     };
 331
 332     // Depends on BigInteger
 333     function factorial(n) {
 334         if (n == 0) {
 335             return 1;
 336         }
 337         f = BigInteger.ONE;
 338         for (var i=1; i<=n; i++) {
 339             f = f.multiply(new BigInteger(i));
 340         }
 341         return f;
 342     }
 343
 344 })();