31:T76e, ## 1.1 Convert hex to base64 Input: `49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d` Output: `SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t` ### (a) Parse Hexidecimal (base16) encoding Each byte is 2 characters, 0-9a-f (100% length penalty in terms of bytes, i.e. 1 raw byte = 2 characters/2 encoded bytes). Javascript functions: - `x.toString(16)` to convert an integer into a base 16 string - `parseInt("ff", 16)` to convert characters to an int. Note: `parseInt` loses precision above 14 characters / 7 bytes, (e.g. `parseInt(x, 16).toString(16)` will put 0's past the first 14 characters). - You can also use `BigInt("0x" + hex)` to get a valid representation, but it's not particularly useful. ### (b) Encode to Base64 Each 3 bytes is 4 characters, 0-9a-zA-Z/+ (33% length penalty) Javascript Functions - [atob](https://developer.mozilla.org/en-US/docs/Web/API/atob) converts "ascii" to "binary". - Ascii means base64 encoded characters, since the 64 characters are valid ASCII (not a great name since there are more than 64 valid ASCII characters). Pretty awful name based on an old [unix command](https://www.unix.com/man-page/minix/1/btoa/), more detail in the [spec](https://html.spec.whatwg.org/multipage/webappapis.html#dom-btoa-dev) - "binary" refers to a "binary string". It's bytes, but represented as a string still for some reason rather than an array. - [btoa](https://developer.mozilla.org/en-US/docs/Web/API/btoa) converts "binary" to "ascii". - Note: these are browser functions, and don't work in Node. - Also here are some functions for going from a byte string to an array and back. Note: `atob` (i.e. decoding) has some behavior I found surprising. That is, it will drop some bits if it's not a round multiple of 6 bits: https://infra.spec.whatwg.org/#forgiving-base6432:T622,lib = { const hexAlphabet = "0123456789abcdef"; const toByteStr = (a) => String.fromCharCode(...a); const fromByteStr = (s) => s.split("").map(c => c.charCodeAt(0)); const toHex1 = (x) => { let hex = x.toString(16); if (hex.length == 1) { hex = "0" + hex;} return hex }; return { toByteStr, fromByteStr, atoi: (a) => a.charCodeAt(0), itoa: (i) => String.fromCharCode(i), toHex1, toHex: (s) => s.map(toHex1).join(""), fromHex: (s) => { if ((s.length % 2) !== 0) { throw 'hex string must have length divisible by 2'; } let ints = []; for (let i = 0; i < s.length; i += 2) { let c1 = s[i]; let c2 = s[i+1]; let b = hexAlphabet.indexOf(c2) + (hexAlphabet.indexOf(c1) << 4); ints.push(b); } return ints; }, tob64: (arr) => btoa(toByteStr(arr)), fromb64: (s) => fromByteStr(atob(s)), fromBinArr: (x) => { let result = 0; for (let i = 0; i < 8; i += 1) { result |= x[7 - i] << i } return result; }, toBinArr: (c) => { if (c > 255) { throw 'must be 8 bit byte'; } let result = []; result[7] = (c & 1) > 0 ? 1 : 0; result[6] = (c & 2) > 0 ? 1 : 0; result[5] = (c & 4) > 0 ? 1 : 0; result[4] = (c & 8) > 0 ? 1 : 0; result[3] = (c & 16) > 0 ? 1 : 0; result[2] = (c & 32) > 0 ? 1 : 0; result[1] = (c & 64) > 0 ? 1 : 0; result[0] = (c & 128) > 0 ? 1 : 0; return result; } } }33:[{"id":"0ec03c4f9aa48390bd355c7ee6965b65b10aeb97bdda1c3c8f3d10720dc8684d8829e2e0fae8a34430a52ca5d4d9aa7c8329ed1412e507c3137530dbf524c50f","href":"https://static.observableusercontent.com/files/0ec03c4f9aa48390bd355c7ee6965b65b10aeb97bdda1c3c8f3d10720dc8684d8829e2e0fae8a34430a52ca5d4d9aa7c8329ed1412e507c3137530dbf524c50f","name":"mobydick.txt","type":"text/plain","lastModified":1664949052146.38,"size":592042},{"id":"655fce9f639f2a4c2b9154d4a09789ab0a99e25272b32694198db3c5254176068a46a10eb7a2defd20b70b12107fd6d99351d7df09d83ff24224ed91507ec96c","href":"https://static.observableusercontent.com/files/655fce9f639f2a4c2b9154d4a09789ab0a99e25272b32694198db3c5254176068a46a10eb7a2defd20b70b12107fd6d99351d7df09d83ff24224ed91507ec96c","name":"4.txt","type":"text/plain","lastModified":1664965458363.455,"size":19944}] 2f:{"title":"Cryptopals 1.1 through 1.4","cells":[{"id":6,"value":"# Cryptopals 1.1 through 1.4\n\nThis notebook covers exercises 1.1 through 1.4 of https://cryptopals.com","pinned":false,"hidden":false,"mode":"md"},{"id":410,"value":"$31","pinned":false,"hidden":false,"mode":"md"},{"id":382,"value":"{ // Demonstrate what a \"byte string\" is in Javascript\n const toByteStr = (a) => String.fromCharCode(...a);\n const fromByteStr = (s) => s.split(\"\").map(c => c.charCodeAt(0));\n\n let foo = [255, 255, 255];\n return [\n toByteStr(foo),\n fromByteStr(toByteStr(foo)),\n ]\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":334,"value":"// showing the 0 filling on parseInt after character 14. 4 zero's are added when we use a 20 char string\n[c1_1.input.slice(0,20), parseInt(c1_1.input.slice(0,20), 16).toString(16)] ","pinned":true,"hidden":false,"mode":"ojs"},{"id":17,"value":"c1_1 = {\n return {\n input: '49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d',\n output: 'SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t',\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":20,"value":"lib.fromHex(c1_1.input)","pinned":true,"hidden":false,"mode":"ojs"},{"id":22,"value":"lib.tob64(lib.fromHex(c1_1.input))","pinned":true,"hidden":false,"mode":"ojs"},{"id":12,"value":"lib.tob64(lib.fromHex(c1_1.input)) == c1_1.output","pinned":true,"hidden":false,"mode":"ojs"},{"id":64,"value":"## 1.2\n\nXOR these:\n\n`1c0111001f010100061a024b53535009181c`\n\n`686974207468652062756c6c277320657965`\n\nand get:\n\n`746865206b696420646f6e277420706c6179`\n","pinned":false,"hidden":false,"mode":"md"},{"id":73,"value":"c1_2 = {\n return {\n input1: '1c0111001f010100061a024b53535009181c',\n input2: '686974207468652062756c6c277320657965',\n output: '746865206b696420646f6e277420706c6179',\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":76,"value":"o1_2 = {\n const a1 = lib.fromHex(c1_2.input1);\n const a2 = lib.fromHex(c1_2.input2);\n\n return lib.toHex(a1.map((c, i) => c ^ a2[i]));\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":85,"value":"o1_2 === c1_2.output","pinned":true,"hidden":false,"mode":"ojs"},{"id":87,"value":"## 1.3 Single-byte XOR cipher\n\nInput: `1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736`\n\nThere's some string in there.","pinned":false,"hidden":false,"mode":"md"},{"id":94,"value":"c1_3 = {return {input: '1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736'}}","pinned":false,"hidden":false,"mode":"ojs"},{"id":185,"value":"singleXor = (arr, k) => arr.map(c => lib.itoa(c^k)).join(\"\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":128,"value":"### Brute Force","pinned":false,"hidden":false,"mode":"md"},{"id":130,"value":"brute_force = {\n let arr = lib.fromHex(c1_3.input);\n let results = [];\n for (let i = 0; i < 255; i += 1) {\n results.push(arr.map(c => lib.itoa(c^i)).join(\"\"))\n }\n\n return results\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":412,"value":"// By inspection\nbrute_force[88]","pinned":true,"hidden":false,"mode":"ojs"},{"id":137,"value":"### Character Frequencies","pinned":false,"hidden":false,"mode":"md"},{"id":97,"value":"makeFreqs = (s) => s.reduce((acc, c) => {\n acc[c] = (acc[c] || 0) + 1;\n return acc\n}, {}) ","pinned":false,"hidden":false,"mode":"ojs"},{"id":113,"value":"c1_3_infreq = makeFreqs(lib.fromHex(c1_3.input))","pinned":false,"hidden":false,"mode":"ojs"},{"id":91,"value":"mobydick_freqs = {\n const full_text = await FileAttachment(\"mobydick.txt\").text();\n\n //return full_text;\n return makeFreqs(full_text.split(\"\"));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":144,"value":"most_common_input = {\n let entries = Object.keys(c1_3_infreq).map(k => [c1_3_infreq[k], k]);\n\n return parseInt(entries.sort((a, b)=> b[0] - a[0])[0][1]);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":165,"value":"most_common_mb = {\n let entries = Object.keys(mobydick_freqs).map(k => [mobydick_freqs[k], k]);\n\n //return entries.sort()[entries.length - 1][1];\n\n return entries.sort((a, b) => b[0] - a[0])[0][1];\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":179,"value":"suspectKey1 = most_common_input ^ lib.atoi(most_common_mb)","pinned":true,"hidden":false,"mode":"ojs"},{"id":188,"value":"c1_3_result = singleXor(lib.fromHex(c1_3.input), suspectKey1)","pinned":true,"hidden":false,"mode":"ojs"},{"id":206,"value":"sortedFreq = Object.keys(mobydick_freqs).map(k => {return {'freq': mobydick_freqs[k], char: (k === \" \") ? \"\" : k}}).sort((a, b)=> b.freq - a.freq)","pinned":true,"hidden":false,"mode":"ojs"},{"id":446,"value":"sortFreqs = (fs) => Object.keys(fs).map(k => {return {'freq': fs[k], char: (k === \" \") ? \"\" : k}}).sort((a, b)=> b.freq - a.freq)","pinned":true,"hidden":false,"mode":"ojs"},{"id":313,"value":"sortedFreq[96]","pinned":true,"hidden":false,"mode":"ojs"},{"id":223,"value":"truncatedFreqs = sortedFreq.slice(0, 50)","pinned":true,"hidden":false,"mode":"ojs"},{"id":210,"value":"Plot.plot({ \n //x: { domain: Object.keys(sortedFreq) },\n marks: [\n Plot.barY(truncatedFreqs, {\n \n x: d => truncatedFreqs.indexOf(d),\n y: \"freq\" }),\n Plot.text(truncatedFreqs, {\n x: d => truncatedFreqs.indexOf(d),\n text: \"char\",\n dy: -10,\n y: \"freq\" })\n ],\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":230,"value":"inFreq = Object.keys(c1_3_infreq).map(k => {return {'freq': c1_3_infreq[k], char: (k === \" \") ? \"\" : k}}).sort((a, b)=> b.freq - a.freq)","pinned":true,"hidden":false,"mode":"ojs"},{"id":232,"value":"Plot.plot({ \n //x: { domain: Object.keys(sortedFreq) },\n marks: [\n Plot.barY(inFreq, {\n \n x: d => inFreq.indexOf(d),\n y: \"freq\" }),\n Plot.text(inFreq, {\n x: d => inFreq.indexOf(d),\n text: \"char\",\n dy: -10,\n y: \"freq\" }),\n\n ],\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":246,"value":"rFreq = {\n const freq1 = makeFreqs(c1_3_result.split(\"\"))\n \n return Object.keys(freq1).map(k => {return {'freq': freq1[k], char: (k === \" \") ? \"\" : k}}).sort((a, b)=> b.freq - a.freq)\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":251,"value":"Plot.plot({ \n //x: { domain: Object.keys(sortedFreq) },\n marks: [\n Plot.barY(rFreq, {\n \n x: d => rFreq.indexOf(d),\n y: \"freq\" }),\n Plot.text(rFreq, {\n x: d => rFreq.indexOf(d),\n text: \"char\",\n dy: -10,\n y: \"freq\" }),\n\n ],\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":256,"value":"## Chi Square test\n\n* https://en.wikipedia.org/wiki/Chi-squared_test\n* http://boris.ryabko.net/jspi.pdf\n\n","pinned":true,"hidden":false,"mode":"md"},{"id":265,"value":"makeRelative = (f) => {\n const total = Object.values(f).reduce((v, acc) => acc + v, 0);\n\n const rel = {};\n Object.keys(f).map((k) => rel[k] = f[k]/total);\n\n return rel;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":268,"value":"mbd_rel = makeRelative(mobydick_freqs);","pinned":true,"hidden":false,"mode":"ojs"},{"id":260,"value":"chiSqScore = (pf, bf) => {\n\n const scores = Object.keys(pf).map(k => {\n if (k === \"'\") {\n return Math.pow(pf[k] - bf['‘'], 2)/bf['‘'];\n } else if (bf[k] === undefined) {\n // This means the character doesn't ever occur in the base set\n // (e.g. Moby Dick never has this character). If you're being strict,\n // you should immediately reject this, but since we're being relative\n // we use the least common character in moby dick to represent the frequency of that character.\n //console.log(`bad k ${k}`);\n\n return Math.pow(pf[k] - bf['£'], 2)/bf['£'];\n\n return NaN;\n }\n return Math.pow(pf[k] - bf[k], 2)/bf[k];\n });\n\n //return scores;\n return scores.reduce((c, a) => a + c, 0)\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":301,"value":"{\n const s = brute_force[88];\n const f1 = makeFreqs(s.split(\"\"));\n\n return {key: 88, s: s, score: chiSqScore(\n makeRelative(f1),\n mbd_rel\n )}\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":281,"value":"makeRelative(makeFreqs(brute_force[5].split(\"\")))","pinned":true,"hidden":false,"mode":"ojs"},{"id":270,"value":"{\n\n const mbd_rel = makeRelative(mobydick_freqs);\n const rs = brute_force.map((s, i) => {\n const f1 = makeFreqs(s.split(\"\"));\n\n return {key: i, s: s, score: chiSqScore(\n makeRelative(f1),\n mbd_rel\n )}\n });\n\n return rs.filter(x => x.score >0).sort((a, b) => a.score - b.score)\n\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":429,"value":"## 1.4: Detect single character XOR\n\nThere's an attached file 4.txt that has 60 lines in it.\n\nMy thought is that I could take the most common character (i.e. ``) try to get a key based on that, then check which has the lowest Chi Square with my Moby Dick text.","pinned":false,"hidden":false,"mode":"md"},{"id":434,"value":"c1_4 = {\n const texts = (await FileAttachment(\"4.txt\").text()).split(\"\\n\");\n const bytes = texts.map(lib.fromHex);\n\n return {texts, bytes};\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":439,"value":"getSpaceChiSquare = (arr, i) => {\n // Get frequency of bytes in cipher text\n const rawFreqs = makeFreqs(arr);\n const relFreqs = makeRelative(rawFreqs);\n const freqs = sortFreqs(relFreqs);\n const mostCommon = freqs[0];\n\n // Assume that character is \" \", so xor it with space to get our\n // top key candidate\n const key = lib.atoi(\" \") ^ parseInt(mostCommon.char);\n const r = singleXor(arr, key);\n\n\n // Now get the frequencies of our decrypted text\n const cFreqs = makeRelative(makeFreqs(r.split(\"\")));\n\n // Get the Chi Square to indicate to let us sort on how\n // likely this is English text (low Chi square -> more likely its English)\n const score = chiSqScore(cFreqs, mbd_rel)\n\n return {i, hex: lib.toHex(arr), score, r, key};\n};","pinned":true,"hidden":false,"mode":"ojs"},{"id":463,"value":"c1_4.bytes.map(getSpaceChiSquare).sort((a, b) => a.score - b.score)[0]","pinned":true,"hidden":false,"mode":"ojs"},{"id":502,"value":"findBestChiKey = (arr) => {\n // Get frequency of bytes in cipher text\n const rawFreqs = makeFreqs(arr);\n const relFreqs = makeRelative(rawFreqs);\n const freqs = sortFreqs(relFreqs);\n // const mostCommon = freqs[0];\n\n const sols = [];\n\n for (let k = 0; k < 255; k += 1) {\n const r = singleXor(arr, k);\n // Now get the frequencies of our decrypted text\n const cFreqs = makeRelative(makeFreqs(r.split(\"\")));\n // Get the Chi Square to indicate to let us sort on how\n // likely this is English text (low Chi square -> more likely its English)\n const score = chiSqScore(cFreqs, mbd_rel);\n\n sols.push({k, hex: lib.toHex(arr), score, r});\n }\n\n return sols.sort((a, b) => a.score - b.score);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":505,"value":"findBestChiKey(c1_4.bytes[170])","pinned":true,"hidden":false,"mode":"ojs"},{"id":330,"value":"## Library implementation","pinned":false,"hidden":false,"mode":"md"},{"id":338,"value":"lib.fromHex(\"ffeeaagg\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":342,"value":"parseInt(\"ff\", 16) ","pinned":true,"hidden":false,"mode":"ojs"},{"id":0,"value":"$32","pinned":true,"hidden":false,"mode":"ojs"},{"id":493,"value":"","pinned":false,"hidden":false,"mode":"html"}],"files":"$W33","stdlib":"1","titling":"auto"}