Back to Table of Contents
Jeremy Cooper took second place with the following submission:The text in the binary is encrypted with a hand-made algorithm that is a combination of 12-bit RSA and several bit-wise permutations. The decryption algorithm is:
Example: x = 99, y = 97, z = 116
Input position Output position -------------- --------------- 0 1 1 4 2 7 3 2 4 5 5 0 6 3 7 6Call this permuted result "py".
Example: 97 in 8-bit binary is 01100001 This permutes to 00001011, which is 11 in decimal.
Example: Since py = 00001011 and x = 01100001, the result would be 1011 concatenated with 01100001: 101101100001, which is 2913 in decimal.
public modulus (n) = 4097 public exponent (e) = 11That is to say, compute (w ** 11) mod 4097. Call the result "t1".
Example: 2913 to the eleventh power is 128157884794082129828859612711416527137. 128157884794082129828859612711416527137 divided by 4097 leaves a remainder of 3949.
Example: Since py = 00001011 and z = 01110100 (116 decimal), the result would be 01110100 concatenated with 0000: 011101000000, which is 1856 in decimal.
Example: 1856 to the eleventh power is 900238724867078044750327477390278656. 900238724867078044750327477390278656 divided by 4097 leaves a remainder of 500.
Example: t1 = 3949, or 111101101101 in binary. Its eight least- significant bits are 01101101, or 107 in decimal.
Example: t1 = 3949, or 111101101101 in binary. It needs no padding to reach twelve bits. t2 = 500, or 111110100 in binary. t2's four least-significant bits are therefore 0100. Concatenating 0100 with t1's four most significant bits, 1111, gives us 01001111, or 79 in decimal.
Example: t2 = 500, or 111110100. It needs three zeroes of padding, to make it a twelve-bit number. When padded it becomes 000111110100. Its eight most-significant bits are therefore 00011111, or 31 in decimal.
Input position Output position -------------- --------------- 0 2 1 7 2 4 3 1 4 6 5 3 6 0 7 5Call the results "o", "p", and "q", respectively.
Example: u = 01101011 -> 10001111 (143 decimal) s = 01001111 -> 10010111 (151 decimal) r = 00011111 -> 11010110 (214 decimal)
Example: [ This example, which started with the ciphertext composed of the ASCII string "cat" is not a good example. It decrypts to nonsense. ]
That's it!
Jeremy then used the same description with actual ciphertext:
Ok, here's the solution using the first six bytes of the ciphertext from the application. They are:
C1 67 BB 7C 6F 35
Then, using the algorithm:
Example: x = C1 (hex) = 193 (decimal), y = 67 (hex) = 103 (decimal), z = BB (hex) = 187 (decimal)
Input position Output position -------------- --------------- 0 1 1 4 2 7 3 2 4 5 5 0 6 3 7 6Call this permuted result "py".
Example: 103 in 8-bit binary is 01100111 This permutes to 10011011, which is 155 in decimal.
Example: Since py = 10011011 and x = 11000001, the result would be 1011 concatenated with 11000001: 101111000001, which is 3009 in decimal.
public modulus (n) = 4097 public exponent (e) = 11That is to say, compute (w ** 11) mod 4097. Call the result "t1".
Example: 3009 to the eleventh power is 183081332709971685898032400292321292609. 183081332709971685898032400292321292609 divided by 4097 leaves a remainder of 136.
Example: Since py = 10011011 and z = 10111011 (187 decimal), the result would be 10111011 concatenated with 1001: 101110111001, which is 3001 in decimal.
Example: 3001 to the eleventh power is 177797622648287046910292734455495033001. 177797622648287046910292734455495033001 divided by 4097 leaves a remainder of 2055.
Example: t1 = 136, or 10001000 in binary. Its eight least- significant bits are 10001000, or, again, 136 in decimal.
Example: t1 = 136, or 10001000 in binary. It needs four bits of padding to reach twelve bits in size: 000010001000. t2 = 2055, or 100000000111 in binary. Its four least-significant bits are 0111. Concatenating 0111 with t1's four most significant bits, 0000, gives us 01110000, or 112 in decimal.
Example: t2 = 2055, or 100000000111. It needs no padding to make it a twelve-bit number. Its eight most-significant bits are therefore 10000000, or 128 in decimal.
Input position Output position -------------- --------------- 0 2 1 7 2 4 3 1 4 6 5 3 6 0 7 5Call the results "o", "p", and "q", respectively.
Example: u = 10001000 -> 00100010 (34 decimal) s = 01110000 -> 01001001 (73 decimal) r = 10000000 -> 00100000 (32 decimal)
o = 00100010 = 22 (hex) = '"' (Double quote) p = 01001001 = 49 (hex) = 'I' q = 00100000 = 20 (hex) = ' ' (Space)So for block 1 we get the characters: '"I '
7C 6F 35
x = 7C y = 6F z = 35 (hex)
py = PERMUTE(6F) -> 9F
w = F7C = 3964 (decimal)
t1 = (3964 ** 11) mod 4097 = 432 = 1B0 (hex)
v = 359 (hex) = 859 (decimal)
t2 = (857 ** 11) mode 4097 = 3533 = DCD (hex)
u = B0 (hex)
s = D1 (hex)
r = DC (hex)
o = PERMUTE(B0) -> 68 (hex) = 104 (decimal) p = PERMUTE(D1) -> 65 (hex) = 101 (decimal) q = PERMITE(DC) -> 73 (hex) = 115 (decimal)
68 65 73 -> hes
Putting both blocks together we get:
"I hes
Which are the first characters of the poem:
"I hesitated before untying the bow ...
Then Jeremy implemented the decryption algorithm in Python. His implementation looks a little more "modern" than Robert's (since it doesn't use the Lisp function names), but they both evaluate to the exact same result.
Jeremy then provided the encryption routine in Python,reconstructed through reverse engineering:
Just for fun, here's the "encryption" code. I say "just for fun" meaningfully because Agrippa actually does not contain the code in this script. Instead, this is the script that the original software developer would have to have run to produce the ciphertext. He or she would have then inserted the ciphertext into the application and compiled it.
Jeremy provided more context by answering some of the original questions posed in the challenge:
So now that I've demonstrated the algorithm, I want to answer a few of the questions presented in the challenge:
Q. Does Agrippa really use encryption?
A.Yes, but only if by "use encryption" you mean that Agrippa uses an already encrypted ciphertext. When Agrippa runs it actually decrypts a pre-programmed ciphertext. In this stricter sense Agrippa does not use any encryption at all.
Q. How does the encryption function?
A. The Agrippa program contains an encrypted version of the Agrippa poem which it decrypts and then displays on the screen for a few minutes. The decryption routine resides within the program and uses a customized block cipher built out of two common cipher building blocks: bit-wise permutations and the RSA modular exponentiation cipher.
The cipher takes a three byte input block and transforms it into a three byte output block. It begins by performing a simple bit-wise permutation on the middle byte of the block and then splits the block into two twelve-bit blocks.
These two twelve-bit blocks are each handed to an RSA decryption routine. The resulting plaintext blocks from the RSA decryption are then split back into three eight-bit bytes again.
Finally, the cipher performs a permutation on all three bytes and returns them as output. [See below for a graphical depiction of this process]
Q. What is the encryption key?
A. Because the encryption is non-standard and it is the only instance of its kind, it is difficult to separate the algorithm from any keys that may have been used to configure it. Nonetheless, it does contain an recognizable RSA element. Its "public" key has the parameters:
public modulus (n) = 4097 (0x1001) public exponent (e) = 11
Since this key is very small, we can easily calculate its private counterpart:
prime factor 1 (p) = 241 prime factor 2 (q) = 17 private exponent (d) = 3491
Likewise, if we treat the permutation elements as configurable items, then their "keys" would be:
Permutation A = ( 1, 4, 7, 2, 5, 0, 3, 6 ) Permutation B = ( 2, 7, 4, 1, 6, 3, 0, 5 )
It is worth noting that the permutation indexes in both tables are formed from a generator in an additive group (mod 8).
And answering some further questions about his process, Jeremy had this to say:
Q. What analysis did you do to get the permutation functions?
A. I performed static and dynamic analysis of the binary code. After performing that analysis I also was able to locate the permutation functions inside the fax images of the "source code".
The functions, which are located on page 3 of the source code, are named "un-do-it" and "un-do-too-it". They correspond to the "Permutation_B" and "Permutation_A" functions, respectively, in my Python source code.
They also correspond to steps "j." and "b.", respectively, in my first message.
Q. Where did you get the ciphertext?
A. The ciphertext is available in the program memory image once the program has finished decompressing itself at start-up. Using dynamic analysis (debugger), you can observe the ciphertext by starting the application, waiting a very short while (about one second) and then issuing a break condition in your debugger. Upon entering the debugger you can observe the ciphertext memory at address 0x1058e0.
A partial, lossy version of it is also available on page 5. You can compare the "printable" characters in the source code to those in the ciphertext I have provided. (Since only the tail end of the ciphertext is visible in the source code, compare them by walking backwards).
A note about decompression:
Jeremy also provided a graphical depiction of the decryption in action:
This picture describes shows how the algorithm works on a single block, down to the bit level.
This picture shows the algorithm operating on the first two blocks of ciphertext from the real data.
[Editor's Note: Compare Jeremy's depiction of the decryption algorithm with Nikita's. They evaluate the same, but Jeremy's displays the intermediate step at each level, whereas Nikita's combines the permutations into a single step.