]>
Commit | Line | Data |
---|---|---|
6606c50f IC |
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] | |
0fdcf2eb | 10 | * card [A2-9TJQK][CDHS] |
6606c50f IC |
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 | ||
c6624d51 IC |
17 | window.Entropy = new (function() { |
18 | ||
22f87669 | 19 | var TWO = new libs.BigInteger.BigInteger(2); |
886f06ee | 20 | |
6606c50f IC |
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"] | |
c6624d51 | 26 | var matchers = { |
6606c50f IC |
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 | }, | |
adc8ce12 IC |
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; | |
c6624d51 IC |
68 | } |
69 | ||
516c16d7 | 70 | this.fromString = function(rawEntropyStr, baseStr) { |
c6624d51 | 71 | // Find type of entropy being used (binary, hex, dice etc) |
516c16d7 | 72 | var base = getBase(rawEntropyStr, baseStr); |
c6624d51 | 73 | // Convert dice to base6 entropy (ie 1-6 to 0-5) |
425b75a9 | 74 | // This is done by changing all 6s to 0s |
c6624d51 | 75 | if (base.str == "dice") { |
a3d78b7d | 76 | var newParts = []; |
0d0f07f9 | 77 | var newInts = []; |
a3d78b7d IC |
78 | for (var i=0; i<base.parts.length; i++) { |
79 | var c = base.parts[i]; | |
425b75a9 | 80 | if ("12345".indexOf(c) > -1) { |
a3d78b7d | 81 | newParts[i] = base.parts[i]; |
0d0f07f9 | 82 | newInts[i] = base.ints[i]; |
c6624d51 IC |
83 | } |
84 | else { | |
a3d78b7d | 85 | newParts[i] = "0"; |
0d0f07f9 | 86 | newInts[i] = 0; |
c6624d51 IC |
87 | } |
88 | } | |
c6624d51 | 89 | base.str = "base 6 (dice)"; |
0d0f07f9 | 90 | base.ints = newInts; |
a3d78b7d | 91 | base.parts = newParts; |
c6624d51 IC |
92 | base.matcher = matchers.base6; |
93 | } | |
c6624d51 | 94 | // Detect empty entropy |
6606c50f | 95 | if (base.parts.length == 0) { |
c6624d51 IC |
96 | return { |
97 | binaryStr: "", | |
c6624d51 | 98 | cleanStr: "", |
b54c1218 | 99 | cleanHtml: "", |
c6624d51 IC |
100 | base: base, |
101 | }; | |
102 | } | |
adc8ce12 IC |
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() | |
22f87669 | 106 | var entropyInt = libs.BigInteger.BigInteger.ZERO; |
adc8ce12 | 107 | for (var i=base.ints.length-1; i>=0; i--) { |
22f87669 | 108 | var thisInt = libs.BigInteger.BigInteger.parse(base.ints[i]); |
adc8ce12 | 109 | var power = (base.ints.length - 1) - i; |
22f87669 | 110 | var additionalEntropy = libs.BigInteger.BigInteger.parse(base.asInt).pow(power).multiply(thisInt); |
adc8ce12 | 111 | entropyInt = entropyInt.add(additionalEntropy); |
c6624d51 | 112 | } |
1cf1bbaf IC |
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 | } | |
94959756 IC |
123 | // Calculate the number of bits per event |
124 | var bitsPerEvent = Math.log2(base.asInt); | |
87ad2c6e | 125 | // Cards binary must be handled differently, since they're not replaced |
6422c1cd | 126 | if (base.asInt == 52) { |
94959756 IC |
127 | var cardEntropy = processCardEntropy(base.parts); |
128 | entropyBin = cardEntropy.binaryStr; | |
129 | bitsPerEvent = cardEntropy.bitsPerEvent; | |
6422c1cd | 130 | } |
1cf1bbaf | 131 | // Supply a 'filtered' entropy string for display purposes |
adc8ce12 | 132 | var entropyClean = base.parts.join(""); |
b54c1218 | 133 | var entropyHtml = base.parts.join(""); |
c193ff67 IC |
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"); | |
b54c1218 IC |
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>"); | |
c193ff67 | 145 | } |
0fdcf2eb | 146 | // Return the result |
c6624d51 IC |
147 | var e = { |
148 | binaryStr: entropyBin, | |
c6624d51 | 149 | cleanStr: entropyClean, |
b54c1218 | 150 | cleanHtml: entropyHtml, |
94959756 | 151 | bitsPerEvent: bitsPerEvent, |
c6624d51 IC |
152 | base: base, |
153 | } | |
154 | return e; | |
155 | } | |
156 | ||
886f06ee IC |
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 | ||
516c16d7 | 169 | function getBase(str, baseStr) { |
c6624d51 IC |
170 | // Need to get the lowest base for the supplied entropy. |
171 | // This prevents interpreting, say, dice rolls as hexadecimal. | |
6606c50f IC |
172 | var binaryMatches = matchers.binary(str); |
173 | var hexMatches = matchers.hex(str); | |
516c16d7 | 174 | var autodetect = baseStr === undefined; |
c6624d51 | 175 | // Find the lowest base that can be used, whilst ignoring any irrelevant chars |
516c16d7 | 176 | if ((binaryMatches.length == hexMatches.length && hexMatches.length > 0 && autodetect) || baseStr === "binary") { |
adc8ce12 | 177 | var ints = binaryMatches.map(function(i) { return parseInt(i, 2) }); |
c6624d51 | 178 | return { |
adc8ce12 | 179 | ints: ints, |
6606c50f | 180 | parts: binaryMatches, |
c6624d51 IC |
181 | matcher: matchers.binary, |
182 | asInt: 2, | |
183 | str: "binary", | |
184 | } | |
185 | } | |
adc8ce12 | 186 | var cardMatches = matchers.card(str); |
516c16d7 | 187 | if ((cardMatches.length >= hexMatches.length / 2 && autodetect) || baseStr === "card") { |
adc8ce12 IC |
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 | } | |
6606c50f | 197 | var diceMatches = matchers.dice(str); |
516c16d7 | 198 | if ((diceMatches.length == hexMatches.length && hexMatches.length > 0 && autodetect) || baseStr === "dice") { |
adc8ce12 | 199 | var ints = diceMatches.map(function(i) { return parseInt(i) }); |
c6624d51 | 200 | return { |
adc8ce12 | 201 | ints: ints, |
6606c50f | 202 | parts: diceMatches, |
c6624d51 IC |
203 | matcher: matchers.dice, |
204 | asInt: 6, | |
205 | str: "dice", | |
206 | } | |
207 | } | |
6606c50f | 208 | var base6Matches = matchers.base6(str); |
516c16d7 | 209 | if ((base6Matches.length == hexMatches.length && hexMatches.length > 0 && autodetect) || baseStr === "base 6") { |
adc8ce12 | 210 | var ints = base6Matches.map(function(i) { return parseInt(i) }); |
c6624d51 | 211 | return { |
adc8ce12 | 212 | ints: ints, |
6606c50f | 213 | parts: base6Matches, |
c6624d51 IC |
214 | matcher: matchers.base6, |
215 | asInt: 6, | |
216 | str: "base 6", | |
217 | } | |
218 | } | |
6606c50f | 219 | var base10Matches = matchers.base10(str); |
516c16d7 | 220 | if ((base10Matches.length == hexMatches.length && hexMatches.length > 0 && autodetect) || baseStr === "base 10") { |
adc8ce12 | 221 | var ints = base10Matches.map(function(i) { return parseInt(i) }); |
c6624d51 | 222 | return { |
adc8ce12 | 223 | ints: ints, |
6606c50f | 224 | parts: base10Matches, |
c6624d51 IC |
225 | matcher: matchers.base10, |
226 | asInt: 10, | |
227 | str: "base 10", | |
228 | } | |
229 | } | |
adc8ce12 | 230 | var ints = hexMatches.map(function(i) { return parseInt(i, 16) }); |
c6624d51 | 231 | return { |
adc8ce12 | 232 | ints: ints, |
6606c50f | 233 | parts: hexMatches, |
c6624d51 IC |
234 | matcher: matchers.hex, |
235 | asInt: 16, | |
236 | str: "hexadecimal", | |
237 | } | |
238 | } | |
239 | ||
87ad2c6e IC |
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 | |
94959756 | 245 | function processCardEntropy(cards) { |
87ad2c6e IC |
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 | |
fc7c248f IC |
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 | } | |
87ad2c6e IC |
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. | |
9d33c892 | 297 | // If the number of bits is more than 256, multiple hashes |
87ad2c6e IC |
298 | // are used until the required number of bits is reached. |
299 | var entropyBin = ""; | |
300 | var iterations = 0; | |
301 | while (entropyBin.length < numberOfBits) { | |
9d33c892 | 302 | var hashedCards = sjcl.hash.sha256.hash(normalizedCards + ":" + iterations); |
87ad2c6e IC |
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); | |
94959756 IC |
316 | // Get the number of bits per event |
317 | bitsPerEvent = maxBits / totalCards; | |
318 | return { | |
319 | binaryStr: entropyBin, | |
320 | bitsPerEvent: bitsPerEvent, | |
321 | } | |
87ad2c6e IC |
322 | } |
323 | ||
c6624d51 IC |
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) { | |
adc8ce12 IC |
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. | |
22f87669 | 331 | return libs.BigInteger.BigInteger.log(x) / libs.BigInteger.BigInteger.log(2); |
c6624d51 IC |
332 | }; |
333 | ||
6422c1cd IC |
334 | // Depends on BigInteger |
335 | function factorial(n) { | |
336 | if (n == 0) { | |
337 | return 1; | |
338 | } | |
22f87669 | 339 | f = libs.BigInteger.BigInteger.ONE; |
6422c1cd | 340 | for (var i=1; i<=n; i++) { |
22f87669 | 341 | f = f.multiply(new libs.BigInteger.BigInteger(i)); |
6422c1cd IC |
342 | } |
343 | return f; | |
344 | } | |
345 | ||
c6624d51 | 346 | })(); |