For this problem, the MMA invented a new symmetric cipher algorithm. The word "smart" in the title is a deliberate misnomer: there probably were some smart people using this kind of cipher 50 years ago, but anyone using this kind of cryptography post-Feistel is probably not very smart.
Unfortunately, reports of actual commercial products turning out to be no smarter than this "smart cipher system" are all too common:
http://www.google.com/search?q=%22The%20Doghouse:%22%20site:www.schneier.com
The contestants were given a random-looking 45-byte ciphertext, and were required to decrypt it. They were told that the plaintext started with "MMA{" and ended with "}". The MMA hosted a web form that contestants could use to encrypt any number of chosen plaintexts.
When I started looking at the problem, tobaljackson told me he had determined that the ciphertext is the same length as the plaintext, and that changing one byte of plaintext usually changes two bytes of ciphertext, and that neither of the ciphertext changes would be at the same location as the plaintext change. So the problem was already about halfway solved, before I started on it.
We know that some kind of shuffling is being done, so let's try changing every column of the plaintext, one column at a time. "View Source" reveals that the plaintext is submitted with the name "s", and that the ciphertext comes back in a single line that happens to be the only line that contains "h1". So maybe we can query the service using just bash and wget and grep, like this:
$ wget -O - http://bow.chal.mmactf.link/%7Escs/crypt6.cgi\?s={\
000000000000000000000000000000000000000000000,\
000000000000000000000000000000000000000000001,\
000000000000000000000000000000000000000000011,\
000000000000000000000000000000000000000000111,\
000000000000000000000000000000000000000001111,\
000000000000000000000000000000000000000011111,\
000000000000000000000000000000000000000111111,\
000000000000000000000000000000000000001111111,\
000000000000000000000000000000000000011111111,\
000000000000000000000000000000000000111111111,\
000000000000000000000000000000000001111111111,\
000000000000000000000000000000000011111111111,\
000000000000000000000000000000000111111111111,\
000000000000000000000000000000001111111111111,\
000000000000000000000000000000011111111111111,\
000000000000000000000000000000111111111111111,\
000000000000000000000000000001111111111111111,\
000000000000000000000000000011111111111111111,\
000000000000000000000000000111111111111111111,\
000000000000000000000000001111111111111111111,\
000000000000000000000000011111111111111111111,\
000000000000000000000000111111111111111111111,\
000000000000000000000001111111111111111111111,\
000000000000000000000011111111111111111111111,\
000000000000000000000111111111111111111111111,\
000000000000000000001111111111111111111111111,\
000000000000000000011111111111111111111111111,\
000000000000000000111111111111111111111111111,\
000000000000000001111111111111111111111111111,\
000000000000000011111111111111111111111111111,\
000000000000000111111111111111111111111111111,\
000000000000001111111111111111111111111111111,\
000000000000011111111111111111111111111111111,\
000000000000111111111111111111111111111111111,\
000000000001111111111111111111111111111111111,\
000000000011111111111111111111111111111111111,\
000000000111111111111111111111111111111111111,\
000000001111111111111111111111111111111111111,\
000000011111111111111111111111111111111111111,\
000000111111111111111111111111111111111111111,\
000001111111111111111111111111111111111111111,\
000011111111111111111111111111111111111111111,\
000111111111111111111111111111111111111111111,\
001111111111111111111111111111111111111111111,\
011111111111111111111111111111111111111111111,\
111111111111111111111111111111111111111111111}\
| grep h1 > raw-46x45.txt
It worked! After using emacs to clean up the output and get it into a more convenient format, we get this:
? (defconstant 46x45 (let ((*read-base* 16)) (read-from-string
"((30 06 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30)
(30 06 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 31)
(30 06 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 31 30 62)
(30 06 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 31 30 62 30 62)
(30 06 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 31 30 62 30 62 30 62)
(30 06 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 31 30 62 30 62 30 62 30 62)
(30 06 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 31 30 62 30 62 30 62 30 62 30 62)
(30 06 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 31 30 62 30 62 30 62 30 62 30 62 30 62)
(30 06 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 31 30 62 30 62 30 62 30 62 30 62 30 62 30 62)
(30 06 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 31 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62)
(30 06 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 31 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62)
(30 06 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 31 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62)
(30 06 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 31 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62)
(30 06 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 31 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62)
(30 06 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 31 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62)
(30 06 30 30 30 30 30 30 30 30 30 30 30 30 30 30 31 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62)
(30 06 30 30 30 30 30 30 30 30 30 30 30 30 31 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62)
(30 06 30 30 30 30 30 30 30 30 30 30 31 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62)
(30 06 30 30 30 30 30 30 30 30 31 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62)
(30 06 30 30 30 30 30 30 31 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62)
(30 06 30 30 30 30 31 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62)
(30 06 30 30 31 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62)
(30 06 31 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62)
(31 06 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62)
(62 06 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 31 62 30 62 30 62 30 62 30 62 30 62)
(62 06 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 31 62 30 62 30 62 30 62 30 62 30 62 62 62 30 62 30 62 30 62 30 62 30 62)
(62 06 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 62 62 30 62 30 62 30 62 30 62 30 62 62 62 30 62 30 62 30 62 31 62 30 62)
(62 06 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 31 62 62 62 30 62 30 62 30 62 30 62 30 62 62 62 30 62 30 62 30 62 62 62 30 62)
(62 06 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 62 62 62 62 30 62 30 62 30 62 30 62 31 62 62 62 30 62 30 62 30 62 62 62 30 62)
(62 06 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 31 62 62 62 62 62 30 62 30 62 30 62 30 62 62 62 62 62 30 62 30 62 30 62 62 62 30 62)
(62 06 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 62 62 62 62 62 62 30 62 30 62 30 62 30 62 62 62 62 62 30 62 31 62 30 62 62 62 30 62)
(62 06 62 30 62 30 62 30 62 30 62 30 62 30 62 31 62 62 62 62 62 62 62 30 62 30 62 30 62 30 62 62 62 62 62 30 62 62 62 30 62 62 62 30 62)
(62 06 62 30 62 30 62 30 62 30 62 30 62 30 62 62 62 62 62 62 62 62 62 30 62 30 62 30 62 31 62 62 62 62 62 30 62 62 62 30 62 62 62 30 62)
(62 06 62 30 62 30 62 30 62 30 62 30 62 31 62 62 62 62 62 62 62 62 62 30 62 30 62 30 62 62 62 62 62 62 62 30 62 62 62 30 62 62 62 30 62)
(62 06 62 30 62 30 62 30 62 30 62 30 62 62 62 62 62 62 62 62 62 62 62 30 62 30 62 30 62 62 62 62 62 62 62 30 62 62 62 30 62 62 62 31 62)
(62 06 62 30 62 30 62 30 62 30 62 31 62 62 62 62 62 62 62 62 62 62 62 30 62 30 62 30 62 62 62 62 62 62 62 30 62 62 62 30 62 62 62 62 62)
(62 06 62 30 62 30 62 30 62 30 62 62 62 62 62 62 62 62 62 62 62 62 62 30 62 30 62 31 62 62 62 62 62 62 62 30 62 62 62 30 62 62 62 62 62)
(62 06 62 30 62 30 62 30 62 31 62 62 62 62 62 62 62 62 62 62 62 62 62 30 62 30 62 62 62 62 62 62 62 62 62 30 62 62 62 30 62 62 62 62 62)
(62 06 62 30 62 30 62 30 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 30 62 30 62 62 62 62 62 62 62 62 62 31 62 62 62 30 62 62 62 62 62)
(62 06 62 30 62 30 62 31 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 30 62 30 62 62 62 62 62 62 62 62 62 62 62 62 62 30 62 62 62 62 62)
(62 06 62 30 62 30 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 30 62 31 62 62 62 62 62 62 62 62 62 62 62 62 62 30 62 62 62 62 62)
(62 06 62 30 62 31 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 30 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 30 62 62 62 62 62)
(62 06 62 30 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 30 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 31 62 62 62 62 62)
(62 06 62 31 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 30 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62)
(62 06 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 31 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62)
(62 26 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62))")))
46X45
As you can see, we start out with a lot of 30s, and when we change a plaintext 0 to a 1, one of the 30s changes to a 31. Then, in the next cycle, when the preceding plaintext 0 changes to a 1, the ciphertext that just changed to a 31 changes to a 62. This means that each byte in the ciphertext is affected by two consecutive bytes of plaintext. The whole table makes sense if we assume these meanings: 30 means a 0 after a 0; 31 means a 1 after a 0; 62 means a 1 after a 1; 06 means an initial 0; 26 means an initial 1.
To map the shuffling algorithm, we just need to find the ciphertext column that corresponds to the leftmost 1 in the plaintext. This will always be the only ciphertext column that contains a 31 or a 26:
? (defun find-encrypted-leftmost-1 (row)
(or (position #x31 row) (position #x26 row)))
FIND-ENCRYPTED-LEFTMOST-1
Now that we know the meaning of 06 and 26 and 30 and 31 and 62, let's find the meanings of all the other ciphertext bytes. Here's a query that will probe every combination of any character in "0123456789abcdef" preceded by any character in "0123456789abcdef{":
$ wget -O - http://bow.chal.mmactf.link/%7Escs/crypt6.cgi\?s={\
000102030405060708090a0b0c0d0e0f,\
101112131415161718191a1b1c1d1e1f,\
202122232425262728292a2b2c2d2e2f,\
303132333435363738393a3b3c3d3e3f,\
404142434445464748494a4b4c4d4e4f,\
505152535455565758595a5b5c5d5e5f,\
606162636465666768696a6b6c6d6e6f,\
707172737475767778797a7b7c7d7e7f,\
808182838485868788898a8b8c8d8e8f,\
909192939495969798999a9b9c9d9e9f,\
a0a1a2a3a4a5a6a7a8a9aaabacadaeaf,\
b0b1b2b3b4b5b6b7b8b9babbbcbdbebf,\
c0c1c2c3c4c5c6c7c8c9cacbcccdcecf,\
d0d1d2d3d4d5d6d7d8d9dadbdcdddedf,\
e0e1e2e3e4e5e6e7e8e9eaebecedeeef,\
f0f1f2f3f4f5f6f7f8f9fafbfcfdfeff,\
%7b0%7b1%7b2%7b3%7b4%7b5%7b6%7b7%7b8%7b9%7ba%7bb%7bc%7bd%7be%7bf}\
| grep h1 > raw-17x32.txt
After cleaning up the output, we get this:
? (defconstant 17x32 (let ((*read-base* 16)) (read-from-string
"((37 18 30 38 31 30 32 39 33 60 34 61 35 60 36 62 06 c0 60 63 81 81 06 64 30 03 03 65 c0 06 0c 66)
(6e 98 60 70 62 31 64 72 66 62 68 c2 6a 62 6c c4 26 c4 62 c6 89 89 26 c8 31 13 13 ca c4 26 4c cc)
(dc 19 c0 e0 c4 32 c8 e4 cc 64 d0 85 d4 64 d8 89 46 c8 64 8d 91 91 46 91 32 23 23 95 c8 46 8c 99)
(b9 99 81 c1 89 33 91 c9 99 66 a1 0b a9 66 b1 13 66 cc 66 1b 99 99 66 23 33 33 33 2b cc 66 cc 33)
(73 1a 03 83 13 34 23 93 33 68 43 16 53 68 63 26 86 d0 68 36 a1 a1 86 46 34 43 43 56 d0 86 0d 66)
(e6 9a 06 07 26 35 46 27 66 6a 86 2c a6 6a c6 4c a6 d4 6a 6c a9 a9 a6 8c 35 53 53 ac d4 a6 4d cc)
(cd 1b 0c 0e 4c 36 8c 4e cc 6c 0d 58 4d 6c 8d 98 c6 d8 6c d8 b1 b1 c6 19 36 63 63 59 d8 c6 8d 99)
(9b 9b 18 1c 98 37 19 9c 99 6e 1a b0 9a 6e 1b 31 e6 dc 6e b1 b9 b9 e6 32 37 73 73 b2 dc e6 cd 33)
(37 1c 30 38 31 38 32 39 33 70 34 61 35 70 36 62 07 e0 70 63 c1 c1 07 64 38 83 83 65 e0 07 0e 66)
(6e 9c 60 70 62 39 64 72 66 72 68 c2 6a 72 6c c4 27 e4 72 c6 c9 c9 27 c8 39 93 93 ca e4 27 4e cc)
(6e b0 60 70 62 61 64 72 66 c2 68 c2 6a c2 6c c4 2c 85 c2 c6 0b 0b 2c c8 61 16 16 ca 85 2c 58 cc)
(dc 31 c0 e0 c4 62 c8 e4 cc c4 d0 85 d4 c4 d8 89 4c 89 c4 8d 13 13 4c 91 62 26 26 95 89 4c 98 99)
(b9 b1 81 c1 89 63 91 c9 99 c6 a1 0b a9 c6 b1 13 6c 8d c6 1b 1b 1b 6c 23 63 36 36 2b 8d 6c d8 33)
(73 32 03 83 13 64 23 93 33 c8 43 16 53 c8 63 26 8c 91 c8 36 23 23 8c 46 64 46 46 56 91 8c 19 66)
(e6 b2 06 07 26 65 46 27 66 ca 86 2c a6 ca c6 4c ac 95 ca 6c 2b 2b ac 8c 65 56 56 ac 95 ac 59 cc)
(cd 33 0c 0e 4c 66 8c 4e cc cc 0d 58 4d cc 8d 98 cc 99 cc d8 33 33 cc 19 66 66 66 59 99 cc 99 99)
(b9 bd 81 c1 89 7b 91 c9 99 f6 a1 0b a9 f6 b1 13 6f ed f6 1b db db 6f 23 7b b7 b7 2b ed 6f de 33))")))
17X32
In the plaintext string "f0f1f2f3f4f5f6f7f8f9fafbfcfdfeff", we don't care about the encryption of any of the fs except the last one; the others are only there to affect the encryption of the following character. So we'll want a way to remove every other byte:
? (defun remove-evens (l)
"Removes the 0th, 2nd, 4th, etc. elements from a list."
(mapcan #'(lambda (b x) (if b (list x))) '#1=(nil t . #1#) l))
REMOVE-EVENS
We can't immediately do anything useful with the 17x32 table above, because it's shuffled. We'll have to defeat the 32-byte shuffle the same way we defeated the 45-byte shuffle. Here's the query:
$ wget -O - http://bow.chal.mmactf.link/%7Escs/crypt6.cgi\?s={\
00000000000000000000000000000000,\
00000000000000000000000000000001,\
00000000000000000000000000000011,\
00000000000000000000000000000111,\
00000000000000000000000000001111,\
00000000000000000000000000011111,\
00000000000000000000000000111111,\
00000000000000000000000001111111,\
00000000000000000000000011111111,\
00000000000000000000000111111111,\
00000000000000000000001111111111,\
00000000000000000000011111111111,\
00000000000000000000111111111111,\
00000000000000000001111111111111,\
00000000000000000011111111111111,\
00000000000000000111111111111111,\
00000000000000001111111111111111,\
00000000000000011111111111111111,\
00000000000000111111111111111111,\
00000000000001111111111111111111,\
00000000000011111111111111111111,\
00000000000111111111111111111111,\
00000000001111111111111111111111,\
00000000011111111111111111111111,\
00000000111111111111111111111111,\
00000001111111111111111111111111,\
00000011111111111111111111111111,\
00000111111111111111111111111111,\
00001111111111111111111111111111,\
00011111111111111111111111111111,\
00111111111111111111111111111111,\
01111111111111111111111111111111,\
11111111111111111111111111111111}\
| grep h1 > raw-33x32.txt
And here's the result:
? (defconstant 33x32 (let ((*read-base* 16)) (read-from-string
"((30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 06 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30)
(30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 06 30 30 30 30 30 30 30 30 30 30 30 30 30 30 31)
(30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 06 30 30 30 30 30 30 30 30 30 30 30 30 31 30 62)
(30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 06 30 30 30 30 30 30 30 30 30 30 31 30 62 30 62)
(30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 06 30 30 30 30 30 30 30 30 31 30 62 30 62 30 62)
(30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 06 30 30 30 30 30 30 31 30 62 30 62 30 62 30 62)
(30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 06 30 30 30 30 31 30 62 30 62 30 62 30 62 30 62)
(30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 06 30 30 31 30 62 30 62 30 62 30 62 30 62 30 62)
(30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 06 31 30 62 30 62 30 62 30 62 30 62 30 62 30 62)
(30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 31 06 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62)
(30 30 30 30 30 30 30 30 30 30 30 30 30 31 30 62 06 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62)
(30 30 30 30 30 30 30 30 30 30 30 31 30 62 30 62 06 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62)
(30 30 30 30 30 30 30 30 30 31 30 62 30 62 30 62 06 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62)
(30 30 30 30 30 30 30 31 30 62 30 62 30 62 30 62 06 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62)
(30 30 30 30 30 31 30 62 30 62 30 62 30 62 30 62 06 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62)
(30 30 30 31 30 62 30 62 30 62 30 62 30 62 30 62 06 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62)
(30 31 30 62 30 62 30 62 30 62 30 62 30 62 30 62 06 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62)
(31 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 06 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62)
(62 62 30 62 30 62 30 62 30 62 30 62 30 62 30 62 06 62 30 62 30 62 30 62 30 62 30 62 30 62 31 62)
(62 62 30 62 30 62 30 62 30 62 30 62 30 62 31 62 06 62 30 62 30 62 30 62 30 62 30 62 30 62 62 62)
(62 62 30 62 30 62 30 62 30 62 30 62 30 62 62 62 06 62 30 62 30 62 31 62 30 62 30 62 30 62 62 62)
(62 62 30 62 30 62 30 62 30 62 30 62 31 62 62 62 06 62 30 62 30 62 62 62 30 62 30 62 30 62 62 62)
(62 62 30 62 30 62 30 62 30 62 30 62 62 62 62 62 06 62 30 62 30 62 62 62 30 62 31 62 30 62 62 62)
(62 62 30 62 30 62 30 62 30 62 31 62 62 62 62 62 06 62 30 62 30 62 62 62 30 62 62 62 30 62 62 62)
(62 62 30 62 30 62 30 62 30 62 62 62 62 62 62 62 06 62 30 62 31 62 62 62 30 62 62 62 30 62 62 62)
(62 62 30 62 30 62 30 62 31 62 62 62 62 62 62 62 06 62 30 62 62 62 62 62 30 62 62 62 30 62 62 62)
(62 62 30 62 30 62 30 62 62 62 62 62 62 62 62 62 06 62 30 62 62 62 62 62 30 62 62 62 31 62 62 62)
(62 62 30 62 30 62 31 62 62 62 62 62 62 62 62 62 06 62 30 62 62 62 62 62 30 62 62 62 62 62 62 62)
(62 62 30 62 30 62 62 62 62 62 62 62 62 62 62 62 06 62 31 62 62 62 62 62 30 62 62 62 62 62 62 62)
(62 62 30 62 31 62 62 62 62 62 62 62 62 62 62 62 06 62 62 62 62 62 62 62 30 62 62 62 62 62 62 62)
(62 62 30 62 62 62 62 62 62 62 62 62 62 62 62 62 06 62 62 62 62 62 62 62 31 62 62 62 62 62 62 62)
(62 62 31 62 62 62 62 62 62 62 62 62 62 62 62 62 06 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62)
(62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 26 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62))")))
33X32
Now we can unshuffle the 17x32 table, and remove the unwanted columns, and get a nice 17x16 S-box:
? (defconstant s-box
(let ((columns (mapcar #'find-encrypted-leftmost-1
(remove-evens (reverse 33x32)))))
(mapcar #'(lambda (row)
(mapcar #'(lambda (column) (nth column row)) columns))
17x32)))
S-BOX
? (format t "~{~&~{~2,'0x~^ ~}~}" s-box)
30 31 32 33 34 35 36 37 38 39 61 62 63 64 65 66
60 62 64 66 68 6A 6C 6E 70 72 C2 C4 C6 C8 CA CC
C0 C4 C8 CC D0 D4 D8 DC E0 E4 85 89 8D 91 95 99
81 89 91 99 A1 A9 B1 B9 C1 C9 0B 13 1B 23 2B 33
03 13 23 33 43 53 63 73 83 93 16 26 36 46 56 66
06 26 46 66 86 A6 C6 E6 07 27 2C 4C 6C 8C AC CC
0C 4C 8C CC 0D 4D 8D CD 0E 4E 58 98 D8 19 59 99
18 98 19 99 1A 9A 1B 9B 1C 9C B0 31 B1 32 B2 33
30 31 32 33 34 35 36 37 38 39 61 62 63 64 65 66
60 62 64 66 68 6A 6C 6E 70 72 C2 C4 C6 C8 CA CC
60 62 64 66 68 6A 6C 6E 70 72 C2 C4 C6 C8 CA CC
C0 C4 C8 CC D0 D4 D8 DC E0 E4 85 89 8D 91 95 99
81 89 91 99 A1 A9 B1 B9 C1 C9 0B 13 1B 23 2B 33
03 13 23 33 43 53 63 73 83 93 16 26 36 46 56 66
06 26 46 66 86 A6 C6 E6 07 27 2C 4C 6C 8C AC CC
0C 4C 8C CC 0D 4D 8D CD 0E 4E 58 98 D8 19 59 99
81 89 91 99 A1 A9 B1 B9 C1 C9 0B 13 1B 23 2B 33
NIL
There are obvious patterns in that table, suggesting that it was probably generated by a simple algorithm, which we probably could deduce if we thought about it hard enough. But we don't need to, because we already have the table!
To use that table manually, imagine that the columns are labeled 0 1 2 3 4 5 6 7 8 9 a b c d e f, and imagine that the rows are labeled 0 1 2 3 4 5 6 7 8 9 a b c d e f {. Find the row that corresponds to the previous plaintext character, and search in that row for the ciphertext byte. The (imaginary) label of the column where you found the current ciphertext byte is the current plaintext character. The 30 and 31 at the upper left, and the 62 below the 31, match the meanings that we already determined from the 46x45 table above.
Let's automate that manual lookup procedure:
? (defun decrypt-byte (prev-plaintext cur-ciphertext)
(let ((row (nth (or (digit-char-p prev-plaintext 16)
(progn (assert (char= prev-plaintext #\{)) 16))
s-box)))
(char-downcase (digit-char (position cur-ciphertext row) 16))))
DECRYPT-BYTE
All that's left is to paste in the ciphertext from the problem page, unshuffle it according to the 46x45 table, and decrypt the unshuffled ciphertext bytes one at a time, except the "MMA{" and "}" that we already know:
? (defconstant ciphertext (let ((*read-base* 16)) (read-from-string
"(62 a9 6c 28 0e 33 31 c6 68 cd 66 66 59 46 cc 53 0c 98 31 65 c6 35 c9 a9 60 4e 37 b0 33 46 0d 60 46 26 66 33 cc e6 a9 f6 6c 07 2b 23 af)")))
CIPHERTEXT
? (do ((in (mapcar #'find-encrypted-leftmost-1 (subseq (reverse 46x45) 4 44))
(rest in))
(out '(#\{)
(cons (decrypt-byte (first out) (nth (first in) ciphertext)) out)))
((endp in) (format nil "MMA~{~a~}}" (reverse out))))
"MMA{f9cf7a3ddd5710e85116814fef01c907f4df35ce}"
This writeup is long, but it's mostly data dumps and exposition. The actual solution of the problem is just the three big wget commands, a minute or two of manual data editing, and 20 lines of Common Lisp code to do the data reduction.
Feedback welcomed.