aboutsummaryrefslogtreecommitdiff
path: root/src/js
diff options
context:
space:
mode:
Diffstat (limited to 'src/js')
-rw-r--r--src/js/entropy.js345
-rw-r--r--src/js/index.js8
2 files changed, 164 insertions, 189 deletions
diff --git a/src/js/entropy.js b/src/js/entropy.js
index 62b2711..3b62e10 100644
--- a/src/js/entropy.js
+++ b/src/js/entropy.js
@@ -16,7 +16,136 @@
16 16
17window.Entropy = new (function() { 17window.Entropy = new (function() {
18 18
19 var TWO = new libs.BigInteger.BigInteger(2); 19 let eventBits = {
20
21 "binary": {
22 "0": "0",
23 "1": "1",
24 },
25
26 // log2(6) = 2.58496 bits per roll, with bias
27 // 4 rolls give 2 bits each
28 // 2 rolls give 1 bit each
29 // Average (4*2 + 2*1) / 6 = 1.66 bits per roll without bias
30 "base 6": {
31 "0": "00",
32 "1": "01",
33 "2": "10",
34 "3": "11",
35 "4": "0",
36 "5": "1",
37 },
38
39 // log2(6) = 2.58496 bits per roll, with bias
40 // 4 rolls give 2 bits each
41 // 2 rolls give 1 bit each
42 // Average (4*2 + 2*1) / 6 = 1.66 bits per roll without bias
43 "base 6 (dice)": {
44 "0": "00", // equivalent to 0 in base 6
45 "1": "01",
46 "2": "10",
47 "3": "11",
48 "4": "0",
49 "5": "1",
50 },
51
52 // log2(10) = 3.321928 bits per digit, with bias
53 // 8 digits give 3 bits each
54 // 2 digits give 1 bit each
55 // Average (8*3 + 2*1) / 10 = 2.6 bits per digit without bias
56 "base 10": {
57 "0": "000",
58 "1": "001",
59 "2": "010",
60 "3": "011",
61 "4": "100",
62 "5": "101",
63 "6": "110",
64 "7": "111",
65 "8": "0",
66 "9": "1",
67 },
68
69 "hexadecimal": {
70 "0": "0000",
71 "1": "0001",
72 "2": "0010",
73 "3": "0011",
74 "4": "0100",
75 "5": "0101",
76 "6": "0110",
77 "7": "0111",
78 "8": "1000",
79 "9": "1001",
80 "a": "1010",
81 "b": "1011",
82 "c": "1100",
83 "d": "1101",
84 "e": "1110",
85 "f": "1111",
86 },
87
88 // log2(52) = 5.7004 bits per card, with bias
89 // 32 cards give 5 bits each
90 // 16 cards give 4 bits each
91 // 4 cards give 2 bits each
92 // Average (32*5 + 16*4 + 4*2) / 52 = 4.46 bits per card without bias
93 "card": {
94 "ac": "00000",
95 "2c": "00001",
96 "3c": "00010",
97 "4c": "00011",
98 "5c": "00100",
99 "6c": "00101",
100 "7c": "00110",
101 "8c": "00111",
102 "9c": "01000",
103 "tc": "01001",
104 "jc": "01010",
105 "qc": "01011",
106 "kc": "01100",
107 "ad": "01101",
108 "2d": "01110",
109 "3d": "01111",
110 "4d": "10000",
111 "5d": "10001",
112 "6d": "10010",
113 "7d": "10011",
114 "8d": "10100",
115 "9d": "10101",
116 "td": "10110",
117 "jd": "10111",
118 "qd": "11000",
119 "kd": "11001",
120 "ah": "11010",
121 "2h": "11011",
122 "3h": "11100",
123 "4h": "11101",
124 "5h": "11110",
125 "6h": "11111",
126 "7h": "0000",
127 "8h": "0001",
128 "9h": "0010",
129 "th": "0011",
130 "jh": "0100",
131 "qh": "0101",
132 "kh": "0110",
133 "as": "0111",
134 "2s": "1000",
135 "3s": "1001",
136 "4s": "1010",
137 "5s": "1011",
138 "6s": "1100",
139 "7s": "1101",
140 "8s": "1110",
141 "9s": "1111",
142 "ts": "00",
143 "js": "01",
144 "qs": "10",
145 "ks": "11",
146 },
147
148 }
20 149
21 // matchers returns an array of the matched events for each type of entropy. 150 // matchers returns an array of the matched events for each type of entropy.
22 // eg 151 // eg
@@ -51,48 +180,28 @@ window.Entropy = new (function() {
51 } 180 }
52 } 181 }
53 182
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) { 183 this.fromString = function(rawEntropyStr, baseStr) {
71 // Find type of entropy being used (binary, hex, dice etc) 184 // Find type of entropy being used (binary, hex, dice etc)
72 var base = getBase(rawEntropyStr, baseStr); 185 var base = getBase(rawEntropyStr, baseStr);
73 // Convert dice to base6 entropy (ie 1-6 to 0-5) 186 // Convert dice to base6 entropy (ie 1-6 to 0-5)
74 // This is done by changing all 6s to 0s 187 // This is done by changing all 6s to 0s
75 if (base.str == "dice") { 188 if (base.str == "dice") {
76 var newParts = []; 189 var newEvents = [];
77 var newInts = []; 190 for (var i=0; i<base.events.length; i++) {
78 for (var i=0; i<base.parts.length; i++) { 191 var c = base.events[i];
79 var c = base.parts[i];
80 if ("12345".indexOf(c) > -1) { 192 if ("12345".indexOf(c) > -1) {
81 newParts[i] = base.parts[i]; 193 newEvents[i] = base.events[i];
82 newInts[i] = base.ints[i];
83 } 194 }
84 else { 195 else {
85 newParts[i] = "0"; 196 newEvents[i] = "0";
86 newInts[i] = 0;
87 } 197 }
88 } 198 }
89 base.str = "base 6 (dice)"; 199 base.str = "base 6 (dice)";
90 base.ints = newInts; 200 base.events = newEvents;
91 base.parts = newParts;
92 base.matcher = matchers.base6; 201 base.matcher = matchers.base6;
93 } 202 }
94 // Detect empty entropy 203 // Detect empty entropy
95 if (base.parts.length == 0) { 204 if (base.events.length == 0) {
96 return { 205 return {
97 binaryStr: "", 206 binaryStr: "",
98 cleanStr: "", 207 cleanStr: "",
@@ -100,44 +209,23 @@ window.Entropy = new (function() {
100 base: base, 209 base: base,
101 }; 210 };
102 } 211 }
103 // Convert base.ints to BigInteger. 212 // Convert entropy events to binary
104 // Due to using unusual bases, eg cards of base52, this is not as simple as 213 var entropyBin = base.events.map(function(e) {
105 // using BigInteger.parse() 214 return eventBits[base.str][e.toLowerCase()];
106 var entropyInt = libs.BigInteger.BigInteger.ZERO; 215 }).join("");
107 for (var i=base.ints.length-1; i>=0; i--) { 216 // Get average bits per event
108 var thisInt = libs.BigInteger.BigInteger.parse(base.ints[i]); 217 // which may be adjusted for bias if log2(base) is fractional
109 var power = (base.ints.length - 1) - i; 218 var bitsPerEvent = base.bitsPerEvent;
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 219 // Supply a 'filtered' entropy string for display purposes
132 var entropyClean = base.parts.join(""); 220 var entropyClean = base.events.join("");
133 var entropyHtml = base.parts.join(""); 221 var entropyHtml = base.events.join("");
134 if (base.asInt == 52) { 222 if (base.asInt == 52) {
135 entropyClean = base.parts.join(" ").toUpperCase(); 223 entropyClean = base.events.join(" ").toUpperCase();
136 entropyClean = entropyClean.replace(/C/g, "\u2663"); 224 entropyClean = entropyClean.replace(/C/g, "\u2663");
137 entropyClean = entropyClean.replace(/D/g, "\u2666"); 225 entropyClean = entropyClean.replace(/D/g, "\u2666");
138 entropyClean = entropyClean.replace(/H/g, "\u2665"); 226 entropyClean = entropyClean.replace(/H/g, "\u2665");
139 entropyClean = entropyClean.replace(/S/g, "\u2660"); 227 entropyClean = entropyClean.replace(/S/g, "\u2660");
140 entropyHtml = base.parts.join(" ").toUpperCase(); 228 entropyHtml = base.events.join(" ").toUpperCase();
141 entropyHtml = entropyHtml.replace(/C/g, "<span class='card-suit club'>\u2663</span>"); 229 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>"); 230 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>"); 231 entropyHtml = entropyHtml.replace(/H/g, "<span class='card-suit heart'>\u2665</span>");
@@ -154,18 +242,6 @@ window.Entropy = new (function() {
154 return e; 242 return e;
155 } 243 }
156 244
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) { 245 function getBase(str, baseStr) {
170 // Need to get the lowest base for the supplied entropy. 246 // Need to get the lowest base for the supplied entropy.
171 // This prevents interpreting, say, dice rolls as hexadecimal. 247 // This prevents interpreting, say, dice rolls as hexadecimal.
@@ -177,20 +253,21 @@ window.Entropy = new (function() {
177 var ints = binaryMatches.map(function(i) { return parseInt(i, 2) }); 253 var ints = binaryMatches.map(function(i) { return parseInt(i, 2) });
178 return { 254 return {
179 ints: ints, 255 ints: ints,
180 parts: binaryMatches, 256 events: binaryMatches,
181 matcher: matchers.binary, 257 matcher: matchers.binary,
182 asInt: 2, 258 asInt: 2,
259 bitsPerEvent: 1,
183 str: "binary", 260 str: "binary",
184 } 261 }
185 } 262 }
186 var cardMatches = matchers.card(str); 263 var cardMatches = matchers.card(str);
187 if ((cardMatches.length >= hexMatches.length / 2 && autodetect) || baseStr === "card") { 264 if ((cardMatches.length >= hexMatches.length / 2 && autodetect) || baseStr === "card") {
188 var ints = convertCardsToInts(cardMatches);
189 return { 265 return {
190 ints: ints, 266 ints: ints,
191 parts: cardMatches, 267 events: cardMatches,
192 matcher: matchers.card, 268 matcher: matchers.card,
193 asInt: 52, 269 asInt: 52,
270 bitsPerEvent: (32*5 + 16*4 + 4*2) / 52, // see cardBits
194 str: "card", 271 str: "card",
195 } 272 }
196 } 273 }
@@ -199,9 +276,10 @@ window.Entropy = new (function() {
199 var ints = diceMatches.map(function(i) { return parseInt(i) }); 276 var ints = diceMatches.map(function(i) { return parseInt(i) });
200 return { 277 return {
201 ints: ints, 278 ints: ints,
202 parts: diceMatches, 279 events: diceMatches,
203 matcher: matchers.dice, 280 matcher: matchers.dice,
204 asInt: 6, 281 asInt: 6,
282 bitsPerEvent: (4*2 + 2*1) / 6, // see diceBits
205 str: "dice", 283 str: "dice",
206 } 284 }
207 } 285 }
@@ -210,9 +288,10 @@ window.Entropy = new (function() {
210 var ints = base6Matches.map(function(i) { return parseInt(i) }); 288 var ints = base6Matches.map(function(i) { return parseInt(i) });
211 return { 289 return {
212 ints: ints, 290 ints: ints,
213 parts: base6Matches, 291 events: base6Matches,
214 matcher: matchers.base6, 292 matcher: matchers.base6,
215 asInt: 6, 293 asInt: 6,
294 bitsPerEvent: (4*2 + 2*1) / 6, // see diceBits
216 str: "base 6", 295 str: "base 6",
217 } 296 }
218 } 297 }
@@ -221,126 +300,22 @@ window.Entropy = new (function() {
221 var ints = base10Matches.map(function(i) { return parseInt(i) }); 300 var ints = base10Matches.map(function(i) { return parseInt(i) });
222 return { 301 return {
223 ints: ints, 302 ints: ints,
224 parts: base10Matches, 303 events: base10Matches,
225 matcher: matchers.base10, 304 matcher: matchers.base10,
226 asInt: 10, 305 asInt: 10,
306 bitsPerEvent: (8*3 + 2*1) / 10, // see b10Bits
227 str: "base 10", 307 str: "base 10",
228 } 308 }
229 } 309 }
230 var ints = hexMatches.map(function(i) { return parseInt(i, 16) }); 310 var ints = hexMatches.map(function(i) { return parseInt(i, 16) });
231 return { 311 return {
232 ints: ints, 312 ints: ints,
233 parts: hexMatches, 313 events: hexMatches,
234 matcher: matchers.hex, 314 matcher: matchers.hex,
235 asInt: 16, 315 asInt: 16,
316 bitsPerEvent: 4,
236 str: "hexadecimal", 317 str: "hexadecimal",
237 } 318 }
238 } 319 }
239 320
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})(); 321})();
diff --git a/src/js/index.js b/src/js/index.js
index 252eec1..b070006 100644
--- a/src/js/index.js
+++ b/src/js/index.js
@@ -1726,7 +1726,7 @@
1726 var numberOfBits = entropy.binaryStr.length; 1726 var numberOfBits = entropy.binaryStr.length;
1727 var timeToCrack = "unknown"; 1727 var timeToCrack = "unknown";
1728 try { 1728 try {
1729 var z = libs.zxcvbn(entropy.base.parts.join("")); 1729 var z = libs.zxcvbn(entropy.base.events.join(""));
1730 timeToCrack = z.crack_times_display.offline_fast_hashing_1e10_per_second; 1730 timeToCrack = z.crack_times_display.offline_fast_hashing_1e10_per_second;
1731 if (z.feedback.warning != "") { 1731 if (z.feedback.warning != "") {
1732 timeToCrack = timeToCrack + " - " + z.feedback.warning; 1732 timeToCrack = timeToCrack + " - " + z.feedback.warning;
@@ -1745,7 +1745,7 @@
1745 DOM.entropyFiltered.html(entropy.cleanHtml); 1745 DOM.entropyFiltered.html(entropy.cleanHtml);
1746 DOM.entropyType.text(entropyTypeStr); 1746 DOM.entropyType.text(entropyTypeStr);
1747 DOM.entropyCrackTime.text(timeToCrack); 1747 DOM.entropyCrackTime.text(timeToCrack);
1748 DOM.entropyEventCount.text(entropy.base.ints.length); 1748 DOM.entropyEventCount.text(entropy.base.events.length);
1749 DOM.entropyBits.text(numberOfBits); 1749 DOM.entropyBits.text(numberOfBits);
1750 DOM.entropyWordCount.text(wordCount); 1750 DOM.entropyWordCount.text(wordCount);
1751 DOM.entropyBinary.text(spacedBinaryStr); 1751 DOM.entropyBinary.text(spacedBinaryStr);
@@ -1770,8 +1770,8 @@
1770 // Detect duplicates 1770 // Detect duplicates
1771 var dupes = []; 1771 var dupes = [];
1772 var dupeTracker = {}; 1772 var dupeTracker = {};
1773 for (var i=0; i<entropy.base.parts.length; i++) { 1773 for (var i=0; i<entropy.base.events.length; i++) {
1774 var card = entropy.base.parts[i]; 1774 var card = entropy.base.events[i];
1775 var cardUpper = card.toUpperCase(); 1775 var cardUpper = card.toUpperCase();
1776 if (cardUpper in dupeTracker) { 1776 if (cardUpper in dupeTracker) {
1777 dupes.push(card); 1777 dupes.push(card);