|
nneonneo's second crypto challenge.
|
|
Here's a second crypto challenge, for anyone who is interested. Dunkyl is an amateur cryptographer looking for fame and fortune. He's recently come across a neat technique for doing encryption with 32-bit integers, and he thinks he can make it super-secure. Along the way, he managed to devise a very neat system! His system takes two integers as the key, and a file of data. It encrypts the data one integer at a time, using both keys. This gives his system 64-bit security, and he wants to sell it to the U.S. government as a system which only they can crack (since only the U.S. government would have the power to crack a 64-bit system!). Dunkyl's system also exhibits a really curious property that Dunkyl calls "antisymmetry": using the integers a,b as the key decrypts any message encrypted with b,a (in other words, to decrypt a message, one needs only swap the order of the key arguments). He claims that this property makes it ideal for implementing in hardware, since it requires very few digital logic gates, and the same circuit can be used for both encryption and decryption. He's quite confident that his scheme is secure against all but the most powerful of computer systems (which only the NSA could possibly have access to). Dunkyl challenges you to break his system! Of course it cannot be done, since Dunkyl's system is only breakable by the NSA. But you are welcome to try anyway ;) Here is the source code of Dunkyl's system, in C: /* Dunkyl's Encryption System. */
/* To decrypt, simply give the keys in reverse order. */
#include <stdio.h>
#define BUFFER_SIZE 256
int getmask(int key1, int key2) {
if(key1 > key2) return 0x5CAC5AC5;
return ~0x5CAC5AC5;
}
int blockfunc(int key, int data) {
int pk = key*data;
return (pk%251)<<24 | (pk%241)<<16 | (pk%239)<<8 | (pk%229);
}
int blockcrypt(int key, int data, int mask) {
return (blockfunc(key, data & mask) & ~mask) ^ data;
}
size_t crypt(int key1, int key2, char *buf, size_t len) {
int i;
int *intbuf = (int *)buf;
int mask = getmask(key1, key2);
if(len&3 != 0) {
/* Pad out to a multiple of four bytes. */
len += (4-(len&3));
}
for(i=0; i<(len>>2); i++, intbuf++) {
*intbuf = blockcrypt(key1, blockcrypt(key2, *intbuf, mask), ~mask);
}
return len;
}
int main(int argc, char **argv) {
if(argc != 3) {
printf("usage: %s key1 key2n", argv[0]);
return -1;
}
int key1 = *(int *)argv[1];
int key2 = *(int *)argv[2];
if(key1 == key2) {
printf("Keys must be different!n");
return -1;
}
char buf[BUFFER_SIZE];
size_t len;
while(len=fread(buf, 1, BUFFER_SIZE, stdin)) {
len = crypt(key1, key2, buf, len);
fwrite(buf, 1, len, stdout);
}
return 0;
}
and here's the encrypted file, hex encoded. F6 DF A5 9E B0 9E 8B 97 46 0D C8 2F 16 D7 20 8E C9 B2 6C 80 96 88 91 DF 6C CD BE 8F 51 D2 82 99 CB 9E 96 91 F0 9E 93 90 B8 DA 7B C7 E3 40 B1 56 BD 1E CD B2 F9 D8 0F 9E 9A D8 77 8F 72 CD 9E 05 B7 64 59 28 BA 97 9A DF DF 11 9A BB EB DA 3F D3 6C CD BE 8F 36 94 8C 18 5F 99 7B 9B 05 90 88 9A 48 C0 A9 87 5F 2E 86 1A AB D0 77 94 53 3B 98 18 96 9B 22 D7 EA 8B 90 90 81 7B DE 19 36 94 8C 18 EE B3 0B 5D 73 9E 91 DF 4C FC F1 A5 F7 AD 5C 53 DD 88 97 90 6B 22 5D 6D 5B D9 16 91 5B 5E 95 35 1E DF 97 90 96 A2 9E 9E D0 93 7F 93 AF 94 4A 82 F2 CC 7B C9 2F 10 8B 8C 31 DF BE 91 BE D5 07 9F 9C CE DB 8C 64 0C D5 1C 5F 2E 86 1A 25 B5 C0 BA CA C2 3E DD D6 8B 90 DF FD 28 50 41 46 0C C9 2E 77 95 32 C1 42 8F F7 D5 6A 3B 3E 07 75 95 61 94 20 DE 21 C7 FF 24 7E FC 38 DF 96 8C 55 8B 97 96 25 DA DB BF AA B0 FE A3 D6 87 65 C7 32 1F D0 85 5B 82 DB 3D 89 8C F3 C2 DF F2 21 6B B2 8C 8C 9A 25 C5 17 CA F6 9D 86 D1 85 84 8F AF 24 8B 97 8A EC 2E 8F 1F 6B 83 0A 09 75 BE CF DF 6E 9E 93 93 19 D1 68 CB 33 8A 8B DF 7F 9B CC B7 86 8B 97 DF C9 93 8B 9A 81 9A 9B D1 6D 64 9F 3C FB 45 02 7C 7C 97 90 8A 8B 41 9F 8B 1C DE 36 93 5D 3D 26 CE 35 96 91 9A 05 41 34 E8 0A 8C DF 96 04 8B 90 DF 6C CD BE 8F 51 D2 82 99 CB 9E 96 91 C4 87 73 98 63 4E 06 21 7C 97 90 8A 50 E2 7C 31 B1 8C 1E C1 10 D6 FF CF 05 86 DF 99 8F 0C CB 7E 80 91 8B 90 5F 2E 86 1A 81 8D 9C 33 F7 EC F0 0B FC DF B9 9A 0C 8D 9A 8C F8 DF 8B 97 30 8F 8E 11 D0 93 7F 93 3D AD 19 6E 7D 23 73 39 FF CE 9E 89 2F 9A 2C B5 C8 A5 1F F6 7E 85 46 FA 3F 9A 9E D3 DC 93 9F 8C 80 1C D0 98 22 96 A5 86 5C F5 3E D9 24 8B 97 8A EC 2E 8F 1F BD 81 89 AC A0 CA D3 CA 1D DF 97 96 84 DF 9A 86 BA 38 DF 12 EE 89 57 DD 7C DF 93 90 36 8B 97 96 06 06 09 03 55 8D 94 9A 3B 0C 78 72 A3 DE 7E 34 45 97 96 8C B4 82 1C CE C6 13 C1 5F 16 D2 9A C3 96 FF 97 1B DC 91 90 8B F0 9E 93 90 A2 D8 77 8B 6A 8C BE DB 02 C5 1B CE 7F 03 70 25 7E 85 46 FA 80 93 0B DE EB DA 3F D3 59 12 72 53 56 AD BE AB 55 B8 2C B7 6B A6 E0 C7 A6 5B 8D 16 45 93 9B DF EF 9E 8B 97 5C F5 3E D9 24 8B 97 8A EC 2E 8F 1F 57 9D 9A 9C A3 92 9A C4 73 9E 91 DF 0A 88 9E 94 E4 11 89 3A F8 D2 C0 0A 07 CC 24 83 FD 28 50 41 46 0C C9 2E 77 95 32 C1 75 8A BB CE 40 D7 28 82 EE 71 DC E8 30 B4 88 DE 02 14 9E B7 0E B7 D3 9A 04 C1 41 EC E3 9B DF 90 79 DF 8B 97 9D DF 8C 93 F3 D8 0B 92 F7 51 60 A9 45 DF BE 8C 7B 16 C1 7D 6C CD BE 8F F5 BE 9F FF E0 9E 8C 8B 49 83 9B 94 4A 7F D2 B6 CD DA 3F D3 38 C1 7B 9C B1 B3 C4 88 07 9B 9A D3 71 BE D3 39 CD DC 03 D3 EF 9E 8B 97 F3 85 3C D5 80 DA 77 93 2E 9A 89 55 FD 8F D1 DF A9 93 9E 8C E4 DF 88 96 EE 71 DC E8 30 B4 88 DE CF 43 6D DD 5B 60 65 5F A7 37 D0 AD 56 9A 57 F2 D6 9E 8C D3 9D 24 4B 47 F8 DF 8B 97 9C 8A DF 9E 5F 9E 96 91 FB 9B 8D 9E 40 DF 8B 97 CB C5 1D 9C 8D 96 B4 22 47 D6 00 DA 6B 99 90 7E AD DF DF A5 32 9D 1E DF 32 2E 6B C7 B1 9E F3 C2 3B 8C 88 9A 93 9A 9B C5 73 CD 36 8B 08 1D 6D D7 DF 32 CD B1 B7 96 91 9B 20 CF F5 D7 C8 DD A8 97 88 53 8E DE 3F 73 69 32 5F 2E 86 1A 61 8C 9E 96 E3 B6 71 E5 41 9B 36 97 71 A7 39 77 40 7E D6 B1 74 B3 48 38 6F 39 3D A0 C7 8D 9A 8C 7F C7 32 95 BE D5 07 9F 24 E5 18 68 57 41 FA 5F AA 2B 92 05 56 AD 1A 93 DC 91 90 8B 57 9D 9A 9C D8 9A 28 8E 98 B6 DF F3 F6 A9 BA BB E7 17 9A 91 71 D3 12 85 70 D9 3C 88 9F 80 16 C7 55 9A F9 87 97 10 C1 A9 DF 16 8C B3 AB 28 89 7F E1 CF 26 C1 E7 17 9A 91 F0 7B E6 5E A7 34 8E 30 D8 96 7E 08 A9 02 FF FC 3C 33 8E 10 07 CC 24 83 91 D5 07 9F 30 B5 9A DE 8E B4 C3 5E 73 12 CF B9 A5 BD DB 9D F3 5F 9A 33 9B F5 92 9A 0D DF B3 90 FC 9A DF 8B 17 0E B7 CC 35 DF 88 90 10 C1 B7 87 D1 DA 5B C1 E8 2F DF B3 D6 8B 90 DF EC 9A D1 DD AD DF DF A5 32 9D 1E DF 32 2E 6B C7 B1 9E F3 C2 3B 8C 88 9A 93 9A 9B C5 C8 DD A8 97 29 8B DF 8C 64 0C D5 1C 79 A6 7B DC 37 85 1B C8 67 88 72 9F 90 F0 E0 6C C6 9D 8D 96 07 B9 D6 B0 CF 5B D8 36 6B 51 A4 53 6A 32 65 47 E7 17 9A 91 20 CF F5 D7 62 D5 18 D6 FC 9A DF 8B 7B 9A 92 DF 00 73 8E A6 2A 31 8A D2 87 DF 8C 9E E1 64 9F 6A 1A 8A F3 98 08 36 C2 08 4D DF DD AB 86 94 9A DF B0 9E 8B 97 62 B9 CE 1B A9 87 07 D7 F0 81 3D 12 5B 98 BA D5 7D 83 B0 96 B3 99 DF 92 F1 9B DF 9C 9D 2C 9E A4 CD DC 03 D3 BE 93 90 91 EA DF 88 96 4A CD 57 9B DE 9A 92 D2 45 0E 96 3E 40 D7 28 82 9E 12 CD 9C 45 87 16 F0 1A AB DF 9E 59 5B C2 19 00 26 12 C9 8A 8A 91 8B 32 70 98 B5 57 92 49 C3 08 49 39 A2 96 9B 22 D7 A3 8B DF 9D 00 DF 9E 98 5E 9A 9A 9E 39 B6 7A F0 6A 32 65 47 5F 2E 86 1A BE EE E7 74 A5 37 D8 F3 51 9D B8 90 3C C3 16 85 0F 73 40 4C CA DA F3 CC 63 4E 06 21 2E 96 89 9A 8A 8A 91 8B 37 97 83 9B 06 8A FF CB 2E 96 89 9A 5F 2E 86 1A 3E DF 91 90 18 92 38 8D 9F 50 17 1F BE FF 9D 90 B6 AF 1E D7 BD 94 57 9F 86 91 9B DF DA 3F 98 DC C7 9D 9A 9E E8 BB D2 2E 0A DF 9D 9A A2 7A CB 30 08 7B 87 0B DA DD F5 DF 97 EE EF 8F B2 57 2A 19 3E 95 13 C6 C5 9B DF A5 32 9D 1E DF 32 2E 6B C7 10 6F B2 39 99 B6 DF 98 D5 C3 16 DB BF B4 DE 3F EE 37 DD F0 5B B6 DF 9E 3E DF 91 90 4C AC 57 C5 D2 88 8C 9B A6 20 49 4D 19 DF 99 90 EA F7 03 DB B7 68 80 63 6D 64 9F 3C 1A 8A F3 98 08 36 C2 08 E9 C9 1E C6 FC 16 88 9A FF F1 13 53 FD 28 50 41 46 0C C9 2E 5C D7 BA 83 71 BE D3 39 E4 8C 8F 9E A5 DA 64 13 F8 2F DE C5 C8 D7 27 9F 35 91 CF 2D 0E 83 E2 9C E1 9A DE 71 70 C9 33 86 F8 DF 8B 97 30 82 DD 3E FC C6 92 87 F8 DF 8B 97 A3 22 FE C0 02 66 31 2F 1B BA AC DE B9 AB 97 9A EF DF 9E 8D 3E C5 1B C6 CC 8B 8D 8A EB 2E C8 89 17 DF 90 99 64 9E C0 BC 1C 98 29 DA BB 3B 8D D0 7E 96 91 8F E4 9B 90 DF 18 52 9E EE 93 3F 92 B4 EE 89 9A DF 6C CD BA DB 85 80 16 8B 39 CA 96 9E B7 80 1A DF FE F0 37 04 3A 8B 8C D1 6D 64 9F 3C 6F 39 3D A0 8C 93 93 DF D2 99 DF 90 19 8D DF 99 2F 10 8B 8C FD 9A 8F 8C 93 8D 96 91 1C 9A 8B 97 70 D9 3C 88 D5 97 90 93 2E 90 2C 93 E7 73 C1 5C 94 98 97 DF C7 9D 9A 9A C5 A7 24 CB CC 3A 8A 0B FA 89 DB FE EE AD 57 D9 F3 DC A7 D3 3E AD CC 9D D0 7B 92 35 62 37 C8 70 55 8E E9 E8 0E B7 D3 9A 30 82 DD 3E A0 CA D3 CA 19 DF 9D 9A FD 5E DD 90 25 C5 17 CA 53 2D 9C 1E DF 32 CD B1 9E 3E DD 0D 1D CC 33 87 CB 90 91 98 89 19 8A 1A D1 E9 D0 86 69 D2 15 D5 50 94 BE D7 08 96 1C 97 ED 38 99 2A E5 CE A4 DC 5F 2E 86 1A 4E 11 FD 34 E1 4B F3 AE 2F 90 91 9C 88 29 91 97 9F BD 9F 8B 13 C5 F5 A8 04 92 29 D6 AC 88 1C DE 4A CD 57 9B 6D 1F 9C 8B 42 4D 75 E3 7E 85 46 FA C0 B0 DE 31 D0 93 7F 93 1D 8F B6 CA CE C1 57 D1 C8 F8 FC 2E C5 9E 86 DF F1 6E DE EB 6F 39 3D A0 C7 8D 9A 8C 55 DE DF B8 0F DF 8D 9E 7D 0E 25 09 D6 8B 90 DF 6C CD BE 8F 9A 4A 07 FD F4 36 DD DF B4 A8 97 86 F6 91 90 8B 69 08 0A 88 5F 96 94 9A 3B 88 12 9E AD 67 3B DB 26 6B 43 7F 61 13 2A B2 56 02 9D E1 F5 F3 BC 33 9B 56 8E 9E A3 3C C7 2E B8 DF 11 7C 84 A4 ED B0 F0 DF 9D 96 D6 BE 8E 60 B1 50 8D FE 7D 3D 6A EE 75 8A BB CE 77 C9 2B 56 80 8B 97 DF 6C CD BE 8F 3C 03 40 CD 4D 46 3B 97 5F 2E 86 1A F7 18 82 2D ED 9E 27 94 35 8F 28 58 C3 3F 8A 7D FD 28 50 41 46 0C C9 2E 75 95 32 D5 6D 64 9F 3C 1A 8A F3 98 08 36 C2 08 4E 1E C0 0C E0 D5 AC C9 C3 C5 DF DD A0 D5 EC 41 AF DA 77 8F AD B0 7E 01 71 BE D3 39 B9 D4 96 95 40 DF 8B 97 DE 90 6C C7 86 91 9B DF 36 91 DF 92 F0 E9 C5 B7 E0 FB D5 A6 0C 91 8C F5 32 DF 93 9E 94 98 97 DF 86 91 9B DF E3 BB 8B 0D 71 BE D3 39 9D 92 8A 92 CB 92 D9 E6 45 2E 86 0A 16 DF 9B 90 D7 16 DC 0F 2A 3E D6 0F 3C D5 90 88 84 D1 F5 DF 99 24 C4 6F 88 7F 9C 16 07 B9 D6 B0 47 9B 57 9C C9 D8 0B 9E B0 D8 7B C7 AF 9E 8A 98 C8 96 91 98 E6 E0 DD 66 B2 FE 0E C5 BB 9D 93 96 88 D8 77 83 DB 9F BE 87 E1 26 8F 39 F3 BE CF 29 ED 1F 9E 1B C8 91 7D D0 3F 23 59 4D B6 DF 92 86 60 B8 90 9B 59 DF BD 8A DD 5B C8 37 0E 0B 8D 1A 0A 84 AB CF 7C 97 90 8A C6 9D 8D 96 9F BD 9F 8B 80 95 16 DC 1D 5D AD D8 B8 3C 9A 40 B1 50 8D FE B7 64 59 28 5C F5 3E D9 24 8B 97 8A EC 2E 8F 1F 6B 22 5D 6D E6 97 16 D2 56 0C 25 CD 15 3B DD 1A 28 88 38 8D FD 2C C1 FE 45 9C 6D 84 6C E1 CC C3 D6 8B 90 DF 6C CD BE 8F 3C 03 40 CD 7F C7 32 95 07 3A 1F 38 72 D9 49 D7 ED A8 97 9E D5 7E 9E 37 C5 8A 93 9B DF B6 DF 97 E8 89 9A DF 7A 90 DF 98 D5 C3 16 DB DF BC CA 36 6A 60 61 E8 DF D5 92 96 53 39 1D 5D DC 80 05 8F 79 8A 8D 8D 6F EC 26 78 3F 9C 9A DF 3C 9E 39 67 85 17 9F 0B 86 94 9A DF 4F 0A C8 37 BF 5F 8E 89 DC DE 7B DD EE 90 92 DF DF BC CA 36 43 DD D2 DF 35 91 9B DF 46 0C C9 2E 5F 2E 86 1A 18 CD 23 8A 5A 81 92 93 C6 99 8D 90 3E DF 90 91 19 04 6E C4 B5 8B 97 9A 7C 61 76 6C 30 AE B0 05 29 9B DF 92 BE FF 9D 90 99 9B DF A5 32 9D 1E DF 32 2E 6B C7 10 6F B2 39 AF 9E 8A 98 C8 96 91 98 CC CB BE 94 8A 5F 9D 1C 27 C2 1C 8F F7 31 C5 8D 92 BF DF DB B7 64 59 28 5C F5 3E D9 24 8B 97 8A EC 2E 8F 1F 59 AD DD 2C F0 9E 93 90 B8 DA 7B C7 05 90 88 9A 48 C0 A9 87 6B 83 0A 09 3F 73 69 32 D6 8B 90 DF C2 B6 CC 7C 43 1C F0 D4 12 C5 DF DD 15 13 B2 4A 17 6F 55 FF B2 1C 8B 5F 3B A8 B8 C6 AD 9D 93 9A CB D5 27 9F 89 88 DD 30 35 CB 7B 9C 08 36 C2 08 7B 16 C1 7D 6C CD BE 8F 36 94 8C 18 5D 1D 67 73 86 8B 97 DF 18 52 9E EE 75 81 A3 A4 43 1C F0 D4 BD C7 3C C1 DF DC 03 DF 70 C9 33 86 6E DD B4 88 19 5F C6 0F EB C1 1A D2 7D E0 B5 2D The file he encrypted is a text file (an excerpt from a book), in which several words are uppercase. He also gives you the following pieces of information, which won't help you in the least: - Both integers in the key he used have all bytes in the range 0-127, i.e. ANDing the integers with 0x7f7f7f7f will not change their value. - The last few bytes in the file are 20 64 65 61 64 21 22 0A (' dead!"n'). Submission requirements: Submit, by PM to nneonneo, the uppercase words from the text. For "bonus marks", submit the encryption keys that he used. More information: The implementation assumes a little-endian system (e.g. x86, but not PowerPC). Here is example usage: $ echo -n 'Hello, World! Dunkyl is awesome!' > a.txt $ crypt abcd efgh < a.txt | hexdump 0000000 d2bd dfbf d3ef a8df 9522 871b 5f05 0ae8 0000010 5aa6 9419 3a81 ee12 0c2c 0d89 9819 c632 $ crypt abcd efgh < a.txt > a.dat $ crypt efgh abcd < a.dat Hello, World! Dunkyl is awesome! $ crypt abcd efgh < a.dat | hexdump 0000000 2d41 2040 8d9a f630 6a63 78e4 cced 0d4c 0000010 60a0 1db3 472c ddee d3bf 5136 e374 9bdc $ crypt 1234 5678 < a.dat | hexdump 0000000 3fa0 38c8 0df5 d563 7599 7ddd be32 0dbf 0000010 84c5 4bf6 87a4 05ed 8a4e b40b 6799 39cd This shows a 32-byte file being encrypted using the key (0x64636261,0x68676665), then being decrypted using the reverse key (0x68676665,0x64636261). It also shows that attempting to decrypt with an incorrect key (in this case, (0x34333231,0x38373635)) will fail. A hint, since it's been two months: 2DES (Google it). You don't have to bruteforce 2^56 keys if you're clever, only 2^29 (and any modern computer can do that in a few seconds). |