How to get a job with 250 lines of code

Recently, I stumbled upon a cryptographic challenge posed by a company called “Trustpilot”. The problem was available at http://followthewhiterabbit.trustpilot.com/challenge2.html. For completeness I post a screenshot here:

challenge

Let that sink for a little while. Generously, the key has only six unknowns, each of them admitting 17 possibilities. So in total there are 6^{17} = 24137569 aka a little less than 25 million possible keys. This is not an extremely huge number, in fact we can attack the problem by brute force, i.e. try each and every possible key.

As a preparatory step one should de-base64 the data given. One gets

IV = {0x0e,0x40,0x5b,0x72,0x64,0x28,0xd5,0x01,0xfe,0x79,0xdd,0x70,0x4f,0x20,0x72,0x9c}
CIPHER = {0xca,0x9b,0x72,0xa0,0x37,0x55,0x05,0xd4,0x2d,0x1a,0x18,0x28,0x78,0xfa,0x69,0x60,0x79,0xd6,0xca,0xe8,0x06,0x9b,0x2d,0x23,0xf3,0x5b,0x1f,0xdf,0x30,0x5e,0x51,0x71,0x0e,0xfc,0xb6,0x11,0xc3,0xed,0x97,0x99,0x56,0xb4,0xfe,0xfe,0x98,0x89,0x2c,0xbd,0x2a,0x3f,0x20,0x32,0x7f,0xe0,0x36,0xed,0x88,0xed,0xd3,0xe6,0x7e,0x04,0x84,0x1c,0xf5,0x03,0x26,0x93,0x69,0x88,0xe5,0xa6,0x99,0x6d,0x7f,0x8f,0x0f,0xcf,0xb7,0x6f,0x40,0xad,0xee,0x6d,0xba,0x65,0xa6,0x9d,0xf9,0x1a,0xcd,0xc0,0x1b,0xdb,0x7c,0x5e,0xec,0x1e,0x2b,0xb8,0xf6,0x55,0xc5,0x41,0x21,0x7e,0x7f,0xc8,0xad,0x93,0xcd,0x65,0xda,0xf8,0x71,0x03,0x6b,0x1c,0xd8,0x04,0xbf,0x6b,0x6c,0xf2,0x05,0x45,0xb8,0xe0,0x54,0xfa,0x9e,0xfd,0xd9,0x43,0xf2,0xf3,0xf9,0x84,0x22,0x15,0xb9,0x10,0x2a,0x69,0xc4,0x62,0x1b,0xed,0x8a,0xe9,0x83,0x8c,0x3b,0x21,0x83,0x5e,0x16,0xd5,0xf9,0x77,0xd5,0xb8,0x5b,0x5b,0x76,0x7b,0xee,0x8f,0x71,0xd7,0x23,0x90,0x12,0xb8,0x6b,0xcc,0xb5,0x72,0x31,0x2d,0xb9,0x0d,0x3b,0x46,0x93,0xc2,0x84,0xeb,0xcb,0x71,0x2c,0xe5,0x07,0xf0,0x60,0xed,0x42,0xa7,0xb7,0x3a,0x2b,0x46,0xc9,0xfe,0xcb,0xf7,0x7b,0xda,0xa0,0xf6,0x43,0x14,0x73,0x71,0x78,0x1b,0xca,0x70,0x8d,0x6a,0x51,0x7b,0xcd,0xa4,0xfa,0xa4,0x49,0xf0,0x28,0x1e,0x22,0xd3,0x97,0xd3,0x43,0x0e,0xa7,0x07,0xb4,0x94,0xd7,0x0d,0xbf,0x12,0xf0,0x86,0x95,0xf8,0xb2,0x47,0x62,0x1a,0xd3,0xc9,0x80,0xd0,0x68,0xa4,0xa9,0xe8,0x18,0x03,0xac,0x46,0xfc,0x40,0x06,0xb3,0x76,0x49,0xd1,0xa4,0x14,0x1a,0xdd,0x18,0x67,0x3d,0x0f,0xee,0xe0,0x6c,0x40,0xa7,0x66,0x0a,0x0e,0xe3,0xcf,0x31,0x0c,0x1f,0x21,0x99,0x0c,0xd1,0x93,0x8f,0x41,0x76,0x74,0xe1,0x47,0x2d,0x23,0x93,0x4f,0x6f,0xc6,0x19,0x28,0x6d,0xf1,0xe0,0xff,0x01,0xee,0xee,0xff,0x19,0xc9,0x8f,0x46,0xc6,0x80,0x02,0x8c,0xb4,0xdb,0x6d,0x18,0x59,0x4d,0xca,0xf2,0xa9,0xb7,0x6b,0xc3,0x0d,0x3d,0xce,0xad,0xf9,0x3a,0x26,0x4f,0xeb,0x0f,0x80,0x88,0xcf,0xa3,0xbf,0x4e,0x7b,0x74,0x36,0x42,0x4b,0xb9,0xc1,0xed,0x23,0x2b,0xc1,0x60,0x6b,0x50,0x47,0x8f,0xa6,0x85,0xb7,0xd4,0x10,0xb9,0x1c,0xcd,0xe0,0xd2,0xc5,0x35,0xc6,0x0c,0xb6,0xa2,0x53,0x77,0x5e,0xea,0xd3,0xda,0x6b,0x4f,0xef,0x8f,0x38,0xb3,0xa1,0x46,0xcd,0x15,0xd7,0xe4,0x22,0x5c,0xbf,0x1d,0x62,0x0d,0x74,0x7a,0x0e,0xf3,0x71}

So the text is encrypted with AES-256? In an earlier post from last year, I presented an implementation of exactly that algorithm in Mathematica. Due to performance issues, I took the opportunity to port the Mathematica code to C++. Now the next thing one has to think about is the block mode of operation. Since they have given us an initialization vector (IV), it is unlikely that they used ECB. I decided to assume that CBC was the mode. Also see my follow-up post on the “AES in Mathematica” topic, where the difference between ECB and CBC is explained. When I do the brute force thing, I only focused on the decryption of the first block, i.e.

{0xca,0x9b,0x72,0xa0,0x37,0x55,0x05,0xd4,0x2d,0x1a,0x18,0x28,0x78,0xfa,0x69,0x60}.

In CBC on simply runs it through the block-decryption machinery and XORs the result with the IV.

Next, one needs to decide which of the 25 million decryption tries is the correct one. In a first attempt I tried to filter out those outcomes which had only printable ASCII characters (and additionally things like newlines, tabulators, bell sound 😉 etc.). Actually that didn’t work (there were some candidates though), so spent quite some time trying to find bugs in my implementation, trying different block modes, interpreting bogus output as an insane form of 13375p34k. Finally, I simply decided to redirect every decryption try into a file, which was a little less than 400 MB in the end. I opened the file in a hex editor and searched for strings like “you did it”, “good job” and finally “congratulations”. As a matter of fact it was “hidden” as “Congra×u¡aûionsé” containing “non-English” characters, which explained the failure of my first attempt. So I re-run my program to obtain the key under the condition that the decrypted string starts with “Congra”. Well I already “knew” the key from the position of the string “Congra×u¡aûionsé” in my big file. The total key reads in decimal representation

{0x05,0x11,0x14,0x11,0x01,0x07,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00}.

Question to my readers: Is there a special meaning related to the sequence [5,11,14,11,1,7]? Is that another matrix reference? I honestly don’t know.

OK, now that one has the key, one can go ahead and decrypt the rest of the message (which was in CBC as suspected). Here’s what it looks like:

Congra×u¡aûionsé You found the decryption key. Are you the One?! ;-)
You're curious and you're up for a challenge! So we like you already.
If you'd like to work with us at Trustpilot then email us the code you wrote to find the decryption key together with your resume.
The email is: thereisnospoon@trustpilot.com
We'll get in touch with you shortly.

Best regards
The developers at Trustpilot????????????????

All right, it remains to give the code that was responsible for the win:

#include <iostream>
#include <iomanip>
#include <cstring>

using namespace std;

static const unsigned char D_sbox[256] = {82, 9, 106, 213, 48, 54, 165, 56, 191, 64, 163, 158, 129, 243, 215, 251, 124, 227, 57, 130, 155, 47, 255, 135, 52, 142, 67, 68, 196, 222, 233, 203, 84, 123, 148, 50, 166, 194, 35, 61, 238, 76, 149, 11, 66, 250, 195, 78, 8, 46, 161, 102, 40, 217, 36, 178, 118, 91, 162, 73, 109, 139, 209, 37, 114, 248, 246, 100, 134, 104, 152, 22, 212, 164, 92, 204, 93, 101, 182, 146, 108, 112, 72, 80, 253, 237, 185, 218, 94, 21, 70, 87, 167, 141, 157, 132, 144, 216, 171, 0, 140, 188, 211, 10, 247, 228, 88, 5, 184, 179, 69, 6, 208, 44, 30, 143, 202, 63, 15, 2, 193, 175, 189, 3, 1, 19, 138, 107, 58, 145, 17, 65, 79, 103, 220, 234, 151, 242, 207, 206, 240, 180, 230, 115, 150, 172, 116, 34, 231, 173, 53, 133, 226, 249, 55, 232, 28, 117, 223, 110, 71, 241, 26, 113, 29, 41, 197, 137, 111, 183, 98, 14, 170, 24, 190, 27, 252, 86, 62, 75, 198, 210, 121, 32, 154, 219, 192, 254, 120, 205, 90, 244, 31, 221, 168, 51, 136, 7, 199, 49, 177, 18, 16, 89, 39, 128, 236, 95, 96, 81, 127, 169, 25, 181, 74, 13, 45, 229, 122, 159, 147, 201, 156, 239, 160, 224, 59, 77, 174, 42, 245, 176, 200, 235, 187, 60, 131, 83, 153, 97, 23, 43, 4, 126, 186, 119, 214, 38, 225, 105, 20, 99, 85, 33, 12, 125};

static const unsigned char   sbox[256] = {99, 124, 119, 123, 242, 107, 111, 197, 48, 1, 103, 43, 254, 215, 171, 118, 202, 130, 201, 125, 250, 89, 71, 240, 173, 212, 162, 175, 156, 164, 114, 192, 183, 253, 147, 38, 54, 63, 247, 204, 52, 165, 229, 241, 113, 216, 49, 21, 4, 199, 35, 195, 24, 150, 5, 154, 7, 18, 128, 226, 235, 39, 178, 117, 9, 131, 44, 26, 27, 110, 90, 160, 82, 59, 214, 179, 41, 227, 47, 132, 83, 209, 0, 237, 32, 252, 177, 91, 106, 203, 190, 57, 74, 76, 88, 207, 208, 239, 170, 251, 67, 77, 51, 133, 69, 249, 2, 127, 80, 60, 159, 168, 81, 163, 64, 143, 146, 157, 56, 245, 188, 182, 218, 33, 16, 255, 243, 210, 205, 12, 19, 236, 95, 151, 68, 23, 196, 167, 126, 61, 100, 93, 25, 115, 96, 129, 79, 220, 34, 42, 144, 136, 70, 238, 184, 20, 222, 94, 11, 219, 224, 50, 58, 10, 73, 6, 36, 92, 194, 211, 172, 98, 145, 149, 228, 121, 231, 200, 55, 109, 141, 213, 78, 169, 108, 86, 244, 234, 101, 122, 174, 8, 186, 120, 37, 46, 28, 166, 180, 198, 232, 221, 116, 31, 75, 189, 139, 138, 112, 62, 181, 102, 72, 3, 246, 14, 97, 53, 87, 185, 134, 193, 29, 158, 225, 248, 152, 17, 105, 217, 142, 148, 155, 30, 135, 233, 206, 85, 40, 223, 140, 161, 137, 13, 191, 230, 66, 104, 65, 153, 45, 15, 176, 84, 187, 22};

static const unsigned char  rcontab[7] = {1, 2, 4, 8, 16, 32, 64};

static const unsigned char galois_rainbow_table[15][256] = {
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255},
{0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,90,92,94,96,98,100,102,104,106,108,110,112,114,116,118,120,122,124,126,128,130,132,134,136,138,140,142,144,146,148,150,152,154,156,158,160,162,164,166,168,170,172,174,176,178,180,182,184,186,188,190,192,194,196,198,200,202,204,206,208,210,212,214,216,218,220,222,224,226,228,230,232,234,236,238,240,242,244,246,248,250,252,254,27,25,31,29,19,17,23,21,11,9,15,13,3,1,7,5,59,57,63,61,51,49,55,53,43,41,47,45,35,33,39,37,91,89,95,93,83,81,87,85,75,73,79,77,67,65,71,69,123,121,127,125,115,113,119,117,107,105,111,109,99,97,103,101,155,153,159,157,147,145,151,149,139,137,143,141,131,129,135,133,187,185,191,189,179,177,183,181,171,169,175,173,163,161,167,165,219,217,223,221,211,209,215,213,203,201,207,205,195,193,199,197,251,249,255,253,243,241,247,245,235,233,239,237,227,225,231,229},
{0,3,6,5,12,15,10,9,24,27,30,29,20,23,18,17,48,51,54,53,60,63,58,57,40,43,46,45,36,39,34,33,96,99,102,101,108,111,106,105,120,123,126,125,116,119,114,113,80,83,86,85,92,95,90,89,72,75,78,77,68,71,66,65,192,195,198,197,204,207,202,201,216,219,222,221,212,215,210,209,240,243,246,245,252,255,250,249,232,235,238,237,228,231,226,225,160,163,166,165,172,175,170,169,184,187,190,189,180,183,178,177,144,147,150,149,156,159,154,153,136,139,142,141,132,135,130,129,155,152,157,158,151,148,145,146,131,128,133,134,143,140,137,138,171,168,173,174,167,164,161,162,179,176,181,182,191,188,185,186,251,248,253,254,247,244,241,242,227,224,229,230,239,236,233,234,203,200,205,206,199,196,193,194,211,208,213,214,223,220,217,218,91,88,93,94,87,84,81,82,67,64,69,70,79,76,73,74,107,104,109,110,103,100,97,98,115,112,117,118,127,124,121,122,59,56,61,62,55,52,49,50,35,32,37,38,47,44,41,42,11,8,13,14,7,4,1,2,19,16,21,22,31,28,25,26},
{0,4,8,12,16,20,24,28,32,36,40,44,48,52,56,60,64,68,72,76,80,84,88,92,96,100,104,108,112,116,120,124,128,132,136,140,144,148,152,156,160,164,168,172,176,180,184,188,192,196,200,204,208,212,216,220,224,228,232,236,240,244,248,252,27,31,19,23,11,15,3,7,59,63,51,55,43,47,35,39,91,95,83,87,75,79,67,71,123,127,115,119,107,111,99,103,155,159,147,151,139,143,131,135,187,191,179,183,171,175,163,167,219,223,211,215,203,207,195,199,251,255,243,247,235,239,227,231,54,50,62,58,38,34,46,42,22,18,30,26,6,2,14,10,118,114,126,122,102,98,110,106,86,82,94,90,70,66,78,74,182,178,190,186,166,162,174,170,150,146,158,154,134,130,142,138,246,242,254,250,230,226,238,234,214,210,222,218,198,194,206,202,45,41,37,33,61,57,53,49,13,9,5,1,29,25,21,17,109,105,101,97,125,121,117,113,77,73,69,65,93,89,85,81,173,169,165,161,189,185,181,177,141,137,133,129,157,153,149,145,237,233,229,225,253,249,245,241,205,201,197,193,221,217,213,209},
{0,5,10,15,20,17,30,27,40,45,34,39,60,57,54,51,80,85,90,95,68,65,78,75,120,125,114,119,108,105,102,99,160,165,170,175,180,177,190,187,136,141,130,135,156,153,150,147,240,245,250,255,228,225,238,235,216,221,210,215,204,201,198,195,91,94,81,84,79,74,69,64,115,118,121,124,103,98,109,104,11,14,1,4,31,26,21,16,35,38,41,44,55,50,61,56,251,254,241,244,239,234,229,224,211,214,217,220,199,194,205,200,171,174,161,164,191,186,181,176,131,134,137,140,151,146,157,152,182,179,188,185,162,167,168,173,158,155,148,145,138,143,128,133,230,227,236,233,242,247,248,253,206,203,196,193,218,223,208,213,22,19,28,25,2,7,8,13,62,59,52,49,42,47,32,37,70,67,76,73,82,87,88,93,110,107,100,97,122,127,112,117,237,232,231,226,249,252,243,246,197,192,207,202,209,212,219,222,189,184,183,178,169,172,163,166,149,144,159,154,129,132,139,142,77,72,71,66,89,92,83,86,101,96,111,106,113,116,123,126,29,24,23,18,9,12,3,6,53,48,63,58,33,36,43,46},
{0,6,12,10,24,30,20,18,48,54,60,58,40,46,36,34,96,102,108,106,120,126,116,114,80,86,92,90,72,78,68,66,192,198,204,202,216,222,212,210,240,246,252,250,232,238,228,226,160,166,172,170,184,190,180,178,144,150,156,154,136,142,132,130,155,157,151,145,131,133,143,137,171,173,167,161,179,181,191,185,251,253,247,241,227,229,239,233,203,205,199,193,211,213,223,217,91,93,87,81,67,69,79,73,107,109,103,97,115,117,127,121,59,61,55,49,35,37,47,41,11,13,7,1,19,21,31,25,45,43,33,39,53,51,57,63,29,27,17,23,5,3,9,15,77,75,65,71,85,83,89,95,125,123,113,119,101,99,105,111,237,235,225,231,245,243,249,255,221,219,209,215,197,195,201,207,141,139,129,135,149,147,153,159,189,187,177,183,165,163,169,175,182,176,186,188,174,168,162,164,134,128,138,140,158,152,146,148,214,208,218,220,206,200,194,196,230,224,234,236,254,248,242,244,118,112,122,124,110,104,98,100,70,64,74,76,94,88,82,84,22,16,26,28,14,8,2,4,38,32,42,44,62,56,50,52},
{0,7,14,9,28,27,18,21,56,63,54,49,36,35,42,45,112,119,126,121,108,107,98,101,72,79,70,65,84,83,90,93,224,231,238,233,252,251,242,245,216,223,214,209,196,195,202,205,144,151,158,153,140,139,130,133,168,175,166,161,180,179,186,189,219,220,213,210,199,192,201,206,227,228,237,234,255,248,241,246,171,172,165,162,183,176,185,190,147,148,157,154,143,136,129,134,59,60,53,50,39,32,41,46,3,4,13,10,31,24,17,22,75,76,69,66,87,80,89,94,115,116,125,122,111,104,97,102,173,170,163,164,177,182,191,184,149,146,155,156,137,142,135,128,221,218,211,212,193,198,207,200,229,226,235,236,249,254,247,240,77,74,67,68,81,86,95,88,117,114,123,124,105,110,103,96,61,58,51,52,33,38,47,40,5,2,11,12,25,30,23,16,118,113,120,127,106,109,100,99,78,73,64,71,82,85,92,91,6,1,8,15,26,29,20,19,62,57,48,55,34,37,44,43,150,145,152,159,138,141,132,131,174,169,160,167,178,181,188,187,230,225,232,239,250,253,244,243,222,217,208,215,194,197,204,203},
{0,8,16,24,32,40,48,56,64,72,80,88,96,104,112,120,128,136,144,152,160,168,176,184,192,200,208,216,224,232,240,248,27,19,11,3,59,51,43,35,91,83,75,67,123,115,107,99,155,147,139,131,187,179,171,163,219,211,203,195,251,243,235,227,54,62,38,46,22,30,6,14,118,126,102,110,86,94,70,78,182,190,166,174,150,158,134,142,246,254,230,238,214,222,198,206,45,37,61,53,13,5,29,21,109,101,125,117,77,69,93,85,173,165,189,181,141,133,157,149,237,229,253,245,205,197,221,213,108,100,124,116,76,68,92,84,44,36,60,52,12,4,28,20,236,228,252,244,204,196,220,212,172,164,188,180,140,132,156,148,119,127,103,111,87,95,71,79,55,63,39,47,23,31,7,15,247,255,231,239,215,223,199,207,183,191,167,175,151,159,135,143,90,82,74,66,122,114,106,98,26,18,10,2,58,50,42,34,218,210,202,194,250,242,234,226,154,146,138,130,186,178,170,162,65,73,81,89,97,105,113,121,1,9,17,25,33,41,49,57,193,201,209,217,225,233,241,249,129,137,145,153,161,169,177,185},
{0,9,18,27,36,45,54,63,72,65,90,83,108,101,126,119,144,153,130,139,180,189,166,175,216,209,202,195,252,245,238,231,59,50,41,32,31,22,13,4,115,122,97,104,87,94,69,76,171,162,185,176,143,134,157,148,227,234,241,248,199,206,213,220,118,127,100,109,82,91,64,73,62,55,44,37,26,19,8,1,230,239,244,253,194,203,208,217,174,167,188,181,138,131,152,145,77,68,95,86,105,96,123,114,5,12,23,30,33,40,51,58,221,212,207,198,249,240,235,226,149,156,135,142,177,184,163,170,236,229,254,247,200,193,218,211,164,173,182,191,128,137,146,155,124,117,110,103,88,81,74,67,52,61,38,47,16,25,2,11,215,222,197,204,243,250,225,232,159,150,141,132,187,178,169,160,71,78,85,92,99,106,113,120,15,6,29,20,43,34,57,48,154,147,136,129,190,183,172,165,210,219,192,201,246,255,228,237,10,3,24,17,46,39,60,53,66,75,80,89,102,111,116,125,161,168,179,186,133,140,151,158,233,224,251,242,205,196,223,214,49,56,35,42,21,28,7,14,121,112,107,98,93,84,79,70},
{0,10,20,30,40,34,60,54,80,90,68,78,120,114,108,102,160,170,180,190,136,130,156,150,240,250,228,238,216,210,204,198,91,81,79,69,115,121,103,109,11,1,31,21,35,41,55,61,251,241,239,229,211,217,199,205,171,161,191,181,131,137,151,157,182,188,162,168,158,148,138,128,230,236,242,248,206,196,218,208,22,28,2,8,62,52,42,32,70,76,82,88,110,100,122,112,237,231,249,243,197,207,209,219,189,183,169,163,149,159,129,139,77,71,89,83,101,111,113,123,29,23,9,3,53,63,33,43,119,125,99,105,95,85,75,65,39,45,51,57,15,5,27,17,215,221,195,201,255,245,235,225,135,141,147,153,175,165,187,177,44,38,56,50,4,14,16,26,124,118,104,98,84,94,64,74,140,134,152,146,164,174,176,186,220,214,200,194,244,254,224,234,193,203,213,223,233,227,253,247,145,155,133,143,185,179,173,167,97,107,117,127,73,67,93,87,49,59,37,47,25,19,13,7,154,144,142,132,178,184,166,172,202,192,222,212,226,232,246,252,58,48,46,36,18,24,6,12,106,96,126,116,66,72,86,92},
{0,11,22,29,44,39,58,49,88,83,78,69,116,127,98,105,176,187,166,173,156,151,138,129,232,227,254,245,196,207,210,217,123,112,109,102,87,92,65,74,35,40,53,62,15,4,25,18,203,192,221,214,231,236,241,250,147,152,133,142,191,180,169,162,246,253,224,235,218,209,204,199,174,165,184,179,130,137,148,159,70,77,80,91,106,97,124,119,30,21,8,3,50,57,36,47,141,134,155,144,161,170,183,188,213,222,195,200,249,242,239,228,61,54,43,32,17,26,7,12,101,110,115,120,73,66,95,84,247,252,225,234,219,208,205,198,175,164,185,178,131,136,149,158,71,76,81,90,107,96,125,118,31,20,9,2,51,56,37,46,140,135,154,145,160,171,182,189,212,223,194,201,248,243,238,229,60,55,42,33,16,27,6,13,100,111,114,121,72,67,94,85,1,10,23,28,45,38,59,48,89,82,79,68,117,126,99,104,177,186,167,172,157,150,139,128,233,226,255,244,197,206,211,216,122,113,108,103,86,93,64,75,34,41,52,63,14,5,24,19,202,193,220,215,230,237,240,251,146,153,132,143,190,181,168,163},
{0,12,24,20,48,60,40,36,96,108,120,116,80,92,72,68,192,204,216,212,240,252,232,228,160,172,184,180,144,156,136,132,155,151,131,143,171,167,179,191,251,247,227,239,203,199,211,223,91,87,67,79,107,103,115,127,59,55,35,47,11,7,19,31,45,33,53,57,29,17,5,9,77,65,85,89,125,113,101,105,237,225,245,249,221,209,197,201,141,129,149,153,189,177,165,169,182,186,174,162,134,138,158,146,214,218,206,194,230,234,254,242,118,122,110,98,70,74,94,82,22,26,14,2,38,42,62,50,90,86,66,78,106,102,114,126,58,54,34,46,10,6,18,30,154,150,130,142,170,166,178,190,250,246,226,238,202,198,210,222,193,205,217,213,241,253,233,229,161,173,185,181,145,157,137,133,1,13,25,21,49,61,41,37,97,109,121,117,81,93,73,69,119,123,111,99,71,75,95,83,23,27,15,3,39,43,63,51,183,187,175,163,135,139,159,147,215,219,207,195,231,235,255,243,236,224,244,248,220,208,196,200,140,128,148,152,188,176,164,168,44,32,52,56,28,16,4,8,76,64,84,88,124,112,100,104},
{0,13,26,23,52,57,46,35,104,101,114,127,92,81,70,75,208,221,202,199,228,233,254,243,184,181,162,175,140,129,150,155,187,182,161,172,143,130,149,152,211,222,201,196,231,234,253,240,107,102,113,124,95,82,69,72,3,14,25,20,55,58,45,32,109,96,119,122,89,84,67,78,5,8,31,18,49,60,43,38,189,176,167,170,137,132,147,158,213,216,207,194,225,236,251,246,214,219,204,193,226,239,248,245,190,179,164,169,138,135,144,157,6,11,28,17,50,63,40,37,110,99,116,121,90,87,64,77,218,215,192,205,238,227,244,249,178,191,168,165,134,139,156,145,10,7,16,29,62,51,36,41,98,111,120,117,86,91,76,65,97,108,123,118,85,88,79,66,9,4,19,30,61,48,39,42,177,188,171,166,133,136,159,146,217,212,195,206,237,224,247,250,183,186,173,160,131,142,153,148,223,210,197,200,235,230,241,252,103,106,125,112,83,94,73,68,15,2,21,24,59,54,33,44,12,1,22,27,56,53,34,47,100,105,126,115,80,93,74,71,220,209,198,203,232,229,242,255,180,185,174,163,128,141,154,151},
{0,14,28,18,56,54,36,42,112,126,108,98,72,70,84,90,224,238,252,242,216,214,196,202,144,158,140,130,168,166,180,186,219,213,199,201,227,237,255,241,171,165,183,185,147,157,143,129,59,53,39,41,3,13,31,17,75,69,87,89,115,125,111,97,173,163,177,191,149,155,137,135,221,211,193,207,229,235,249,247,77,67,81,95,117,123,105,103,61,51,33,47,5,11,25,23,118,120,106,100,78,64,82,92,6,8,26,20,62,48,34,44,150,152,138,132,174,160,178,188,230,232,250,244,222,208,194,204,65,79,93,83,121,119,101,107,49,63,45,35,9,7,21,27,161,175,189,179,153,151,133,139,209,223,205,195,233,231,245,251,154,148,134,136,162,172,190,176,234,228,246,248,210,220,206,192,122,116,102,104,66,76,94,80,10,4,22,24,50,60,46,32,236,226,240,254,212,218,200,198,156,146,128,142,164,170,184,182,12,2,16,30,52,58,40,38,124,114,96,110,68,74,88,86,55,57,43,37,15,1,19,29,71,73,91,85,127,113,99,109,215,217,203,197,239,225,243,253,167,169,187,181,159,145,131,141}
};

void sBox(unsigned char * dest, int len) {
    for(int i = 0; i < len; i++)
        dest[i] = sbox[dest[i]];
}

void D_sBox(unsigned char * dest, int len) {
    for(int i = 0; i < len; i++)
        dest[i] = D_sbox[dest[i]];
}

void D_shiftRows(unsigned char state[16]) {
    unsigned char newstate[16];

    newstate[0]  = state[0];
    newstate[1]  = state[13];
    newstate[2]  = state[10];
    newstate[3]  = state[7];
    newstate[4]  = state[4];
    newstate[5]  = state[1];
    newstate[6]  = state[14];
    newstate[7]  = state[11];
    newstate[8]  = state[8];
    newstate[9]  = state[5];
    newstate[10] = state[2];
    newstate[11] = state[15];
    newstate[12] = state[12];
    newstate[13] = state[9];
    newstate[14] = state[6];
    newstate[15] = state[3];

    memcpy(state,newstate,16);
}

void bitXor4(unsigned char dest[4], unsigned const char src[4]) {
    for(int i = 0; i < 4; i++)
        dest[i] ^= src[i];
}

void bitXor4(unsigned char dest[4], unsigned const char op1[4], unsigned const char op2[4]) {
    for(int i = 0; i < 4; i++)
        dest[i] = op1[i]^op2[i];
}

void bitXor16(unsigned char dest[16], unsigned const char src[16]) {
    for(int i = 0; i < 16; i++)
        dest[i] ^= src[i];
}

void bitXor16(unsigned char dest[16], unsigned const char op1[16],  unsigned const char op2[16]) {
    for(int i = 0; i < 16; i++)
        dest[i] = op1[i]^op2[i];
}

void D_mixColumn(unsigned char * state4) {
    unsigned char entry0 = galois_rainbow_table[14][state4[0]] ^ galois_rainbow_table[11][state4[1]] ^ galois_rainbow_table[13][state4[2]] ^ galois_rainbow_table[ 9][state4[3]];
    unsigned char entry1 = galois_rainbow_table[ 9][state4[0]] ^ galois_rainbow_table[14][state4[1]] ^ galois_rainbow_table[11][state4[2]] ^ galois_rainbow_table[13][state4[3]];
    unsigned char entry2 = galois_rainbow_table[13][state4[0]] ^ galois_rainbow_table[ 9][state4[1]] ^ galois_rainbow_table[14][state4[2]] ^ galois_rainbow_table[11][state4[3]];
    unsigned char entry3 = galois_rainbow_table[11][state4[0]] ^ galois_rainbow_table[13][state4[1]] ^ galois_rainbow_table[ 9][state4[2]] ^ galois_rainbow_table[14][state4[3]];

    state4[0] = entry0;
    state4[1] = entry1;
    state4[2] = entry2;
    state4[3] = entry3;
}

void D_mixColumns(unsigned char state[16]) {
    for(int i = 0; i < 16; i += 4)
        D_mixColumn(&(state[i]));
}

void rotateLeft(unsigned char state[4]) {
    unsigned char swap = state[0];
    for(int i = 0; i < 3; i++)
        state[i] = state[i+1]
    state[3] = swap;
}

void generateRoundKeys(unsigned char roundkeys[15][16], const unsigned char key[32]) {
    unsigned char keytable[4][60];
    for (int j = 0; j < 8; j++)
        for (int i = 0; i < 4; i++)
            keytable[i][j] = key[4*j+i];

    unsigned char t[4], t_left1[4], t_left8[4];

    for(int i = 8; i < 60; i++) {
        for(int j = 0; j < 4; j++)
            t_left1[j] = keytable[j][i-1]
        for(int j = 0; j < 4; j++)
            t_left8[j] = keytable[j][i-8]

        if( ( (i % 8) == 0) ) {
            rotateLeft(t_left1);
            sBox(t_left1, 4);
            t_left1[0] ^= rcontab[i/8-1];
        } else if( ( (i % 4) == 0) )
            sBox(t_left1, 4);

        bitXor4(t, t_left8, t_left1);

        for(int j = 0; j < 4; j++)
            keytable[j][i] = t[j]
    }
    for(int i = 0; i < 15; i++)
        for(int col = 0; col < 4; col++)
            for(int row = 0; row < 4; row++)
                roundkeys[i][4*col+row] = keytable[row][4*i+col];
}

void D_state(unsigned char state[16], const unsigned char roundkey[16]) {
    bitXor16(state, roundkey);
    D_mixColumns(state);
    D_shiftRows(state);
    D_sBox(state,16);
}

void D_AES_BLOCK(unsigned char message[16], const unsigned char ciphertext[16], const unsigned char roundkeys[15][16]) {
    unsigned char state[16];

    bitXor16(state, ciphertext, roundkeys[14]);
    D_shiftRows(state);
    D_sBox(state, 16);

    for(int i = 13; i > 0; i--)
        D_state(state, roundkeys[i])

    bitXor16(message, state, roundkeys[0]);
}

void D_AES_BLOCK(unsigned char message[16], const unsigned char ciphertext[16], const unsigned char key[32]) {
    unsigned char roundkeys[15][16];
    generateRoundKeys(roundkeys, key);
    D_AES_BLOCK(message, ciphertext, roundkeys);
}

void D_AES_CBC(const unsigned char * ciphertext, const int num_blocks, const unsigned char key[32], const unsigned char iv[16]) {
    unsigned char roundkeys[15][16];
    unsigned char decrypted_block[16];
    unsigned char* block_ptr      = ((unsigned char*) (ciphertext))+16;
    unsigned char* block_ptr_prev = (unsigned char*) (ciphertext);

    generateRoundKeys(roundkeys, key);

    D_AES_BLOCK(decrypted_block, ciphertext, roundkeys);
    for(int i = 0; i < 16; i++) {
        decrypted_block[i] ^= iv[i];
        cout<<decrypted_block[i];
    }

    for (int i = 1; i < num_blocks; i++) {
        D_AES_BLOCK(decrypted_block, block_ptr, roundkeys);
        for(int ch=0; ch < 16; ch++) {
            decrypted_block[ch] ^= block_ptr_prev[ch];
            cout<<decrypted_block[ch];
        }
        block_ptr += 16;
        block_ptr_prev += 16;
    }
}

bool checkTextSanity(const unsigned char text[16]) {
    return (text[0]=='C') && (text[1]=='o') && (text[2]=='n') && (text[3]=='g') && (text[4]=='r') && (text[5]=='a');
}

int main(int, char **) {
    cout<<"CHALLENGE ACCEPTED!\n\n";

    const unsigned char iv[16]     = {0x0e,0x40,0x5b,0x72,0x64,0x28,0xd5,0x01,0xfe,0x79,0xdd,0x70,0x4f,0x20,0x72,0x9c};
    const unsigned char block1[16] = {0xca,0x9b,0x72,0xa0,0x37,0x55,0x05,0xd4,0x2d,0x1a,0x18,0x28,0x78,0xfa,0x69,0x60};
    const unsigned char ciphertext[416] = {0xca,0x9b,0x72,0xa0,0x37,0x55,0x05,0xd4,0x2d,0x1a,0x18,0x28,0x78,0xfa,0x69,0x60,0x79,0xd6,0xca,0xe8,0x06,0x9b,0x2d,0x23,0xf3,0x5b,0x1f,0xdf,0x30,0x5e,0x51,0x71,0x0e,0xfc,0xb6,0x11,0xc3,0xed,0x97,0x99,0x56,0xb4,0xfe,0xfe,0x98,0x89,0x2c,0xbd,0x2a,0x3f,0x20,0x32,0x7f,0xe0,0x36,0xed,0x88,0xed,0xd3,0xe6,0x7e,0x04,0x84,0x1c,0xf5,0x03,0x26,0x93,0x69,0x88,0xe5,0xa6,0x99,0x6d,0x7f,0x8f,0x0f,0xcf,0xb7,0x6f,0x40,0xad,0xee,0x6d,0xba,0x65,0xa6,0x9d,0xf9,0x1a,0xcd,0xc0,0x1b,0xdb,0x7c,0x5e,0xec,0x1e,0x2b,0xb8,0xf6,0x55,0xc5,0x41,0x21,0x7e,0x7f,0xc8,0xad,0x93,0xcd,0x65,0xda,0xf8,0x71,0x03,0x6b,0x1c,0xd8,0x04,0xbf,0x6b,0x6c,0xf2,0x05,0x45,0xb8,0xe0,0x54,0xfa,0x9e,0xfd,0xd9,0x43,0xf2,0xf3,0xf9,0x84,0x22,0x15,0xb9,0x10,0x2a,0x69,0xc4,0x62,0x1b,0xed,0x8a,0xe9,0x83,0x8c,0x3b,0x21,0x83,0x5e,0x16,0xd5,0xf9,0x77,0xd5,0xb8,0x5b,0x5b,0x76,0x7b,0xee,0x8f,0x71,0xd7,0x23,0x90,0x12,0xb8,0x6b,0xcc,0xb5,0x72,0x31,0x2d,0xb9,0x0d,0x3b,0x46,0x93,0xc2,0x84,0xeb,0xcb,0x71,0x2c,0xe5,0x07,0xf0,0x60,0xed,0x42,0xa7,0xb7,0x3a,0x2b,0x46,0xc9,0xfe,0xcb,0xf7,0x7b,0xda,0xa0,0xf6,0x43,0x14,0x73,0x71,0x78,0x1b,0xca,0x70,0x8d,0x6a,0x51,0x7b,0xcd,0xa4,0xfa,0xa4,0x49,0xf0,0x28,0x1e,0x22,0xd3,0x97,0xd3,0x43,0x0e,0xa7,0x07,0xb4,0x94,0xd7,0x0d,0xbf,0x12,0xf0,0x86,0x95,0xf8,0xb2,0x47,0x62,0x1a,0xd3,0xc9,0x80,0xd0,0x68,0xa4,0xa9,0xe8,0x18,0x03,0xac,0x46,0xfc,0x40,0x06,0xb3,0x76,0x49,0xd1,0xa4,0x14,0x1a,0xdd,0x18,0x67,0x3d,0x0f,0xee,0xe0,0x6c,0x40,0xa7,0x66,0x0a,0x0e,0xe3,0xcf,0x31,0x0c,0x1f,0x21,0x99,0x0c,0xd1,0x93,0x8f,0x41,0x76,0x74,0xe1,0x47,0x2d,0x23,0x93,0x4f,0x6f,0xc6,0x19,0x28,0x6d,0xf1,0xe0,0xff,0x01,0xee,0xee,0xff,0x19,0xc9,0x8f,0x46,0xc6,0x80,0x02,0x8c,0xb4,0xdb,0x6d,0x18,0x59,0x4d,0xca,0xf2,0xa9,0xb7,0x6b,0xc3,0x0d,0x3d,0xce,0xad,0xf9,0x3a,0x26,0x4f,0xeb,0x0f,0x80,0x88,0xcf,0xa3,0xbf,0x4e,0x7b,0x74,0x36,0x42,0x4b,0xb9,0xc1,0xed,0x23,0x2b,0xc1,0x60,0x6b,0x50,0x47,0x8f,0xa6,0x85,0xb7,0xd4,0x10,0xb9,0x1c,0xcd,0xe0,0xd2,0xc5,0x35,0xc6,0x0c,0xb6,0xa2,0x53,0x77,0x5e,0xea,0xd3,0xda,0x6b,0x4f,0xef,0x8f,0x38,0xb3,0xa1,0x46,0xcd,0x15,0xd7,0xe4,0x22,0x5c,0xbf,0x1d,0x62,0x0d,0x74,0x7a,0x0e,0xf3,0x71};

    cout<<"IV:";
    for(int ch=0; ch < 16; ch++)
        cout<<dec<<(unsigned int)iv[ch]<<",";
    cout<<endl;
    cout<<"CIPHER:";
    for(int ch=0; ch < 416; ch++)
        cout<<dec<<(unsigned int)ciphertext[ch]<<",";
    cout<<endl<<endl;

    unsigned char key[32] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
    unsigned char decrypt1[16];
    for(int i1=0; i1 <= 16; i1++)//
        for(int i2=0; i2 <= 16; i2++)
            for(int i3=0; i3 <= 16; i3++)
                for(int i4=0; i4 <= 16; i4++)
                    for(int i5=0; i5 <= 16; i5++)
                        for(int i6=0; i6 <= 16; i6++) {
                            key[0] = (unsigned char) i1;
                            key[1] = (unsigned char) i2;
                            key[2] = (unsigned char) i3;
                            key[3] = (unsigned char) i4;
                            key[4] = (unsigned char) i5;
                            key[5] = (unsigned char) i6;

                            /*xor with IV after decryption. (corresponds to CBC, pCBC)*/
                            D_AES_BLOCK(decrypt1, block1, key);
                            for(int i = 0; i < 16; i++)
                                decrypt1[i] ^= iv[i];

                            if(checkTextSanity(decrypt1)) {
                                cout<<"CANDIDATE FOUND!\n";
                                for(int i=0; i < 16; i++)
                                    cout<<decrypt1[i];
                                cout<<" = ";
                                for(int i=0; i < 16; i++)
                                    cout<<(unsigned int)decrypt1[i]<<' ';

                                cout<<"\nKEY(hex):";
                                for(int i=0; i < 32; i++)
                                    cout<<hex<<(int)key[i]<<' ';
                                cout<<"\nKEY(dec):"<<dec<<i1<<' '<<i2<<' '<<i3<<' '<<i4<<' '<<i5<<' '<<i6<<endl<<endl;

                                cout<<"TRYING TO DECRYPT WHOLE MESSAGE:\n";
                                D_AES_CBC(ciphertext, 26, key, iv);
                                cout<<endl;
                                return 0;
                            }
                        }
    return 1;
}

250 lines of code for a presumably cool job? Well there is still a job-interview, your resume has to look good, bla, bla, bla. If I wasn’t too busy smoking weed and drinking scotch, I would definitely apply for the position. But the first hurdle was taken. With a home-brew implementation of AES. Speaking of which, you may have noticed that the Galois multiplications are now implemented by a simple lookup table, which is way faster than working directly with the definition. Incidentally, how long did it take to try every key in the first place? One and a half minutes on my 5 y/o cheapo laptop (I used g++ with -O3 optimization level, with profiling I got even faster results).

Advertisements

About goobypl5

pizza baker, autodidact, particle physicist
This entry was posted in Encryption, Programming, Security/Encryption and tagged , , , , , . Bookmark the permalink.

One Response to How to get a job with 250 lines of code

  1. Pingback: How to get a job with 70 lines of code | randomgooby

Share your thoughts

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s