From adc8ce127d4f8ea0d7e5ede6a82c2791d60ff4d2 Mon Sep 17 00:00:00 2001
From: Ian Coleman <coleman.ian@gmail.com>
Date: Mon, 7 Nov 2016 16:01:21 +1100
Subject: [PATCH] Cards can be used for entropy

Format is [A2-9TJQK][CDHS]
---
 src/js/entropy.js | 123 ++++++++++++++++--------
 src/js/index.js   |  21 +++--
 tests.js          | 231 +++++++++++++++++++++++++++++++++++-----------
 3 files changed, 278 insertions(+), 97 deletions(-)

diff --git a/src/js/entropy.js b/src/js/entropy.js
index 5b687d8..92300af 100644
--- a/src/js/entropy.js
+++ b/src/js/entropy.js
@@ -36,6 +36,32 @@ window.Entropy = new (function() {
         hex: function(str) {
             return str.match(/[0-9A-F]/gi) || [];
         },
+        card: function(str) {
+            // Format is NumberSuit, eg
+            // AH ace of hearts
+            // 8C eight of clubs
+            // TD ten of diamonds
+            // JS jack of spades
+            // QH queen of hearts
+            // KC king of clubs
+            return str.match(/([A2-9TJQK][CDHS])/gi) || [];
+        }
+    }
+
+    // Convert array of cards from ["ac", "4d", "ks"]
+    // to numbers between 0 and 51 [0, 16, 51]
+    function convertCardsToInts(cards) {
+        var ints = [];
+        var values = "a23456789tjqk";
+        var suits = "cdhs";
+        for (var i=0; i<cards.length; i++) {
+            var card = cards[i].toLowerCase();
+            var value = card[0];
+            var suit = card[1];
+            var asInt = 13 * suits.indexOf(suit) + values.indexOf(value);
+            ints.push(asInt);
+        }
+        return ints;
     }
 
     this.fromString = function(rawEntropyStr) {
@@ -62,61 +88,61 @@ window.Entropy = new (function() {
         if (base.parts.length == 0) {
             return {
                 binaryStr: "",
-                hexStr: "",
                 cleanStr: "",
                 base: base,
             };
         }
         // Pull leading zeros off
         var leadingZeros = [];
-        while (base.parts[0] == "0") {
+        while (base.ints[0] == "0") {
             leadingZeros.push("0");
-            base.parts.shift();
+            base.ints.shift();
         }
         // Convert leading zeros to binary equivalent
-        var numBinLeadingZeros = Math.ceil(Math.log2(base.asInt) * leadingZeros.length);
+        var numBinLeadingZeros = Math.floor(Math.log2(base.asInt) * leadingZeros.length);
         var binLeadingZeros = "";
         for (var i=0; i<numBinLeadingZeros; i++) {
             binLeadingZeros += "0";
         }
-        // Convert leading zeros to hex equivalent
-        var numHexLeadingZeros = Math.floor(numBinLeadingZeros / 4);
-        var hexLeadingZeros = "";
-        for (var i=0; i<numHexLeadingZeros; i++) {
-            hexLeadingZeros += "0";
-        }
         // Handle entropy of zero
-        if (base.parts.length == 0) {
+        if (base.ints.length == 0) {
             return {
                 binaryStr: binLeadingZeros,
-                hexStr: hexLeadingZeros || "0",
                 cleanStr: leadingZeros,
                 base: base,
             }
         }
-        // If using hex, should always be multiples of 4 bits, which can get
-        // out of sync if first number has leading 0 bits, eg 2 in hex is 0010
-        // which would show up as 10, thus missing 2 bits it should have.
-        if (base.asInt == 16) {
-            var firstDigit = parseInt(base.parts[0], 16);
-            if (firstDigit >= 4 && firstDigit < 8) {
-                binLeadingZeros += "0";
-            }
-            else if (firstDigit >= 2 && firstDigit < 4) {
-                binLeadingZeros += "00";
-            }
-            else if (firstDigit >= 1 && firstDigit < 2) {
-                binLeadingZeros += "000";
-            }
+        // If the first integer is small, it must be padded with zeros.
+        // Otherwise the chance of the first bit being 1 is 100%, which is
+        // obviously incorrect.
+        // This is not perfect for unusual bases, eg base 6 has 2.6 bits, so is
+        // slightly biased toward having leading zeros, but it's still better
+        // than ignoring it completely.
+        // TODO: revise this, it seems very fishy. For example, in base 10, there are
+        // 8 opportunities to start with 0 but only 2 to start with 1
+        var firstInt = base.ints[0];
+        var firstIntBits = Math.floor(Math.log2(firstInt))+1;
+        var maxFirstIntBits = Math.floor(Math.log2(base.asInt-1))+1;
+        var missingFirstIntBits = maxFirstIntBits - firstIntBits;
+        var firstIntLeadingZeros = "";
+        for (var i=0; i<missingFirstIntBits; i++) {
+            binLeadingZeros += "0";
+        }
+        // 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;
+        for (var i=base.ints.length-1; i>=0; i--) {
+            var thisInt = BigInteger.parse(base.ints[i]);
+            var power = (base.ints.length - 1) - i;
+            var additionalEntropy = BigInteger.parse(base.asInt).pow(power).multiply(thisInt);
+            entropyInt = entropyInt.add(additionalEntropy);
         }
-        // Convert entropy to different foramts
-        var entropyInt = BigInteger.parse(base.parts.join(""), base.asInt);
+        // Convert entropy to different formats
         var entropyBin = binLeadingZeros + entropyInt.toString(2);
-        var entropyHex = hexLeadingZeros + entropyInt.toString(16);
-        var entropyClean = leadingZeros.join("") + base.parts.join("");
+        var entropyClean = base.parts.join("");
         var e = {
             binaryStr: entropyBin,
-            hexStr: entropyHex,
             cleanStr: entropyClean,
             base: base,
         }
@@ -129,17 +155,32 @@ window.Entropy = new (function() {
         var binaryMatches = matchers.binary(str);
         var hexMatches = matchers.hex(str);
         // Find the lowest base that can be used, whilst ignoring any irrelevant chars
-        if (binaryMatches.length == hexMatches.length) {
+        if (binaryMatches.length == hexMatches.length && hexMatches.length > 0) {
+            var ints = binaryMatches.map(function(i) { return parseInt(i, 2) });
             return {
+                ints: ints,
                 parts: binaryMatches,
                 matcher: matchers.binary,
                 asInt: 2,
                 str: "binary",
             }
         }
+        var cardMatches = matchers.card(str);
+        if (cardMatches.length >= hexMatches.length / 2) {
+            var ints = convertCardsToInts(cardMatches);
+            return {
+                ints: ints,
+                parts: cardMatches,
+                matcher: matchers.card,
+                asInt: 52,
+                str: "card",
+            }
+        }
         var diceMatches = matchers.dice(str);
-        if (diceMatches.length == hexMatches.length) {
+        if (diceMatches.length == hexMatches.length && hexMatches.length > 0) {
+            var ints = diceMatches.map(function(i) { return parseInt(i) });
             return {
+                ints: ints,
                 parts: diceMatches,
                 matcher: matchers.dice,
                 asInt: 6,
@@ -147,8 +188,10 @@ window.Entropy = new (function() {
             }
         }
         var base6Matches = matchers.base6(str);
-        if (base6Matches.length == hexMatches.length) {
+        if (base6Matches.length == hexMatches.length && hexMatches.length > 0) {
+            var ints = base6Matches.map(function(i) { return parseInt(i) });
             return {
+                ints: ints,
                 parts: base6Matches,
                 matcher: matchers.base6,
                 asInt: 6,
@@ -156,15 +199,19 @@ window.Entropy = new (function() {
             }
         }
         var base10Matches = matchers.base10(str);
-        if (base10Matches.length == hexMatches.length) {
+        if (base10Matches.length == hexMatches.length && hexMatches.length > 0) {
+            var ints = base10Matches.map(function(i) { return parseInt(i) });
             return {
+                ints: ints,
                 parts: base10Matches,
                 matcher: matchers.base10,
                 asInt: 10,
                 str: "base 10",
             }
         }
+        var ints = hexMatches.map(function(i) { return parseInt(i, 16) });
         return {
+            ints: ints,
             parts: hexMatches,
             matcher: matchers.hex,
             asInt: 16,
@@ -175,7 +222,11 @@ window.Entropy = new (function() {
     // 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) {
-        return Math.log(x) * Math.LOG2E;
+        // The polyfill isn't good enough because of the poor accuracy of
+        // Math.LOG2E
+        // log2(8) gave 2.9999999999999996 which when floored causes issues.
+        // So instead use the BigInteger library to get it right.
+        return BigInteger.log(x) / BigInteger.log(2);
     };
 
 })();
diff --git a/src/js/index.js b/src/js/index.js
index 1cc77d3..a717a9e 100644
--- a/src/js/index.js
+++ b/src/js/index.js
@@ -738,33 +738,36 @@
         // Show entropy details
         var extraBits = 32 - (entropy.binaryStr.length % 32);
         var extraChars = Math.ceil(extraBits * Math.log(2) / Math.log(entropy.base.asInt));
+        var words = Math.floor(entropy.binaryStr.length / 32) * 3;
         var strength = "an extremely weak";
-        if (entropy.hexStr.length >= 8) {
+        if (words >= 3) {
             strength = "a very weak";
         }
-        if (entropy.hexStr.length >= 12) {
+        if (words >= 6) {
             strength = "a weak";
         }
-        if (entropy.hexStr.length >= 24) {
+        if (words >= 9) {
             strength = "a strong";
         }
-        if (entropy.hexStr.length >= 32) {
+        if (words >= 12) {
             strength = "a very strong";
         }
-        if (entropy.hexStr.length >= 40) {
+        if (words >= 15) {
             strength = "an extremely strong";
         }
-        if (entropy.hexStr.length >=48) {
+        if (words >= 18) {
             strength = "an even stronger"
         }
         var msg = "Have " + entropy.binaryStr.length + " bits of entropy, " + extraChars + " more " + entropy.base.str + " chars required to generate " + strength + " mnemonic: " + entropy.cleanStr;
         showEntropyError(msg);
         // Discard trailing entropy
-        var hexStr = entropy.hexStr.substring(0, Math.floor(entropy.hexStr.length / 8) * 8);
+        var bitsToUse = Math.floor(entropy.binaryStr.length / 32) * 32;
+        var binaryStr = entropy.binaryStr.substring(0, bitsToUse);
         // Convert entropy string to numeric array
         var entropyArr = [];
-        for (var i=0; i<hexStr.length / 2; i++) {
-            var entropyByte = parseInt(hexStr[i*2].concat(hexStr[i*2+1]), 16);
+        for (var i=0; i<binaryStr.length / 8; i++) {
+            var byteAsBits = binaryStr.substring(i*8, i*8+8);
+            var entropyByte = parseInt(byteAsBits, 2);
             entropyArr.push(entropyByte)
         }
         // Convert entropy array to mnemonic
diff --git a/tests.js b/tests.js
index 1841af6..8de6391 100644
--- a/tests.js
+++ b/tests.js
@@ -1997,85 +1997,212 @@ page.open(url, function(status) {
 // Entropy unit tests
 function() {
 page.open(url, function(status) {
-    var error = page.evaluate(function() {
+    var response = page.evaluate(function() {
         var e;
         // binary entropy is detected
-        e = Entropy.fromString("01010101");
-        if (e.base.str != "binary") {
-            return "Binary entropy not detected correctly";
+        try {
+            e = Entropy.fromString("01010101");
+            if (e.base.str != "binary") {
+                return "Binary entropy not detected correctly";
+            }
+        }
+        catch (e) {
+            return e.message;
         }
         // base6 entropy is detected
-        e = Entropy.fromString("012345012345");
-        if (e.base.str != "base 6") {
-            return "base6 entropy not detected correctly";
+        try {
+            e = Entropy.fromString("012345012345");
+            if (e.base.str != "base 6") {
+                return "base6 entropy not detected correctly";
+            }
+        }
+        catch (e) {
+            return e.message;
         }
         // dice entropy is detected
-        e = Entropy.fromString("123456123456");
-        if (e.base.str != "base 6 (dice)") {
-            return "dice entropy not detected correctly";
+        try {
+            e = Entropy.fromString("123456123456");
+            if (e.base.str != "base 6 (dice)") {
+                return "dice entropy not detected correctly";
+            }
+        }
+        catch (e) {
+            return e.message;
         }
         // base10 entropy is detected
-        e = Entropy.fromString("0123456789");
-        if (e.base.str != "base 10") {
-            return "base10 entropy not detected correctly";
+        try {
+            e = Entropy.fromString("0123456789");
+            if (e.base.str != "base 10") {
+                return "base10 entropy not detected correctly";
+            }
+        }
+        catch (e) {
+            return e.message;
         }
         // hex entropy is detected
-        e = Entropy.fromString("0123456789ABCDEF");
-        if (e.base.str != "hexadecimal") {
-            return "hexadecimal entropy not detected correctly";
+        try {
+            e = Entropy.fromString("0123456789ABCDEF");
+            if (e.base.str != "hexadecimal") {
+                return "hexadecimal entropy not detected correctly";
+            }
+        }
+        catch (e) {
+            return e.message;
+        }
+        // card entropy is detected
+        try {
+            e = Entropy.fromString("AC4DTHKS");
+            if (e.base.str != "card") {
+                return "card entropy not detected correctly";
+            }
+        }
+        catch (e) {
+            return e.message;
         }
         // entropy is case insensitive
-        e = Entropy.fromString("aBcDeF");
-        if (e.cleanStr != "aBcDeF") {
-            return "Entropy should not be case sensitive";
+        try {
+            e = Entropy.fromString("aBcDeF");
+            if (e.cleanStr != "aBcDeF") {
+                return "Entropy should not be case sensitive";
+            }
+        }
+        catch (e) {
+            return e.message;
         }
         // dice entropy is converted to base6
-        e = Entropy.fromString("123456");
-        if (e.cleanStr != "012345") {
-            return "Dice entropy is not automatically converted to base6";
+        try {
+            e = Entropy.fromString("123456");
+            if (e.cleanStr != "012345") {
+                return "Dice entropy is not automatically converted to base6";
+            }
+        }
+        catch (e) {
+            return e.message;
         }
         // dice entropy is preferred to base6 if ambiguous
-        e = Entropy.fromString("12345");
-        if (e.base.str != "base 6 (dice)") {
-            return "dice not used as default over base 6";
+        try {
+            e = Entropy.fromString("12345");
+            if (e.base.str != "base 6 (dice)") {
+                return "dice not used as default over base 6";
+            }
+        }
+        catch (e) {
+            return e.message;
         }
         // unused characters are ignored
-        e = Entropy.fromString("fghijkl");
-        if (e.cleanStr != "f") {
-            return "additional characters are not ignored";
+        try {
+            e = Entropy.fromString("fghijkl");
+            if (e.cleanStr != "f") {
+                return "additional characters are not ignored";
+            }
+        }
+        catch (e) {
+            return e.message;
         }
         // the lowest base is used by default
         // 7 could be decimal or hexadecimal, but should be detected as decimal
-        e = Entropy.fromString("7");
-        if (e.base.str != "base 10") {
-            return "lowest base is not used";
+        try {
+            e = Entropy.fromString("7");
+            if (e.base.str != "base 10") {
+                return "lowest base is not used";
+            }
         }
-        // Hexadecimal representation is returned
-        e = Entropy.fromString("1010");
-        if (e.hexStr != "A") {
-            return "Hexadecimal representation not returned";
+        catch (e) {
+            return e.message;
         }
         // Leading zeros are retained
-        e = Entropy.fromString("000A");
-        if (e.cleanStr != "000A") {
-            return "Leading zeros are not retained";
+        try {
+            e = Entropy.fromString("000A");
+            if (e.cleanStr != "000A") {
+                return "Leading zeros are not retained";
+            }
+        }
+        catch (e) {
+            return e.message;
         }
         // Leading zeros are correctly preserved for hex in binary string
-        e = Entropy.fromString("2A");
-        if (e.binaryStr != "00101010") {
-            return "Hex leading zeros are not correct in binary";
+        try {
+            e = Entropy.fromString("2A");
+            if (e.binaryStr != "00101010") {
+                return "Hex leading zeros are not correct in binary";
+            }
+        }
+        catch (e) {
+            return e.message;
+        }
+        // Leading zeros are correctly preserved for base 6 in binary string
+        try {
+            e = Entropy.fromString("2");
+            if (e.binaryStr != "010") {
+                return "Base 6 leading zeros are not correct in binary";
+            }
+        }
+        catch (e) {
+            return e.message;
         }
         // Keyboard mashing results in weak entropy
         // Despite being a long string, it's less than 30 bits of entropy
-        e = Entropy.fromString("aj;se ifj; ask,dfv js;ifj");
-        if (e.binaryStr.length >= 30) {
-            return "Keyboard mashing should produce weak entropy";
+        try {
+            e = Entropy.fromString("aj;se ifj; ask,dfv js;ifj");
+            if (e.binaryStr.length >= 30) {
+                return "Keyboard mashing should produce weak entropy";
+            }
         }
-        return false;
+        catch (e) {
+            return e.message;
+        }
+        // Card entropy is used if every pair could be a card
+        try {
+            e = Entropy.fromString("4c3c2c");
+            if (e.base.str != "card") {
+                return "Card entropy not used if all pairs are cards";
+            }
+        }
+        catch (e) {
+            return e.message;
+        }
+        // Card entropy uses base 52
+        // [ cards, binary ]
+        try {
+            var cards = [
+                [ "ac", "00000" ],
+                [ "acac", "00000000000" ],
+                [ "acac2c", "00000000000000001" ],
+                [ "acks", "00000110011" ],
+                [ "acacks", "00000000000110011" ],
+                [ "2c", "000001" ],
+                [ "3d", "001111" ],
+                [ "4h", "011101" ],
+                [ "5s", "101011" ],
+                [ "6c", "000101" ],
+                [ "7d", "010011" ],
+                [ "8h", "100001" ],
+                [ "9s", "101111" ],
+                [ "tc", "001001" ],
+                [ "jd", "010111" ],
+                [ "qh", "100101" ],
+                [ "ks", "110011" ],
+                [ "ks2c", "101001011101" ],
+                [ "KS2C", "101001011101" ],
+            ];
+            for (var i=0; i<cards.length; i++) {
+                var card = cards[i][0];
+                var result = cards[i][1];
+                e = Entropy.fromString(card);
+                console.log(e.binary + " " + result);
+                if (e.binaryStr !== result) {
+                    return "card entropy not parsed correctly: " + result + " != " + e.binaryStr;
+                }
+            }
+        }
+        catch (e) {
+            return e.message;
+        }
+        return "PASS";
     });
-    if (error) {
+    if (response != "PASS") {
         console.log("Entropy unit tests");
-        console.log(error);
+        console.log(response);
         fail();
     };
     next();
@@ -2339,10 +2466,10 @@ page.open(url, function(status) {
         [ "0", "1" ],
         [ "0000", "4" ],
         [ "6", "3" ],
-        [ "7", "3" ],
+        [ "7", "4" ],
         [ "8", "4" ],
         [ "F", "4" ],
-        [ "29", "5" ],
+        [ "29", "7" ],
         [ "0A", "8" ],
         [ "1A", "8" ], // hex is always multiple of 4 bits of entropy
         [ "2A", "8" ],
@@ -2350,9 +2477,9 @@ page.open(url, function(status) {
         [ "8A", "8" ],
         [ "FA", "8" ],
         [ "000A", "16" ],
-        [ "2220", "10" ],
-        [ "2221", "9" ], // uses dice, so entropy is actually 1110
-        [ "2227", "12" ],
+        [ "2220", "11" ],
+        [ "2221", "11" ], // uses dice, so entropy is actually 1110
+        [ "2227", "14" ],
         [ "222F", "16" ],
         [ "FFFF", "16" ],
     ]
-- 
2.41.0