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:

  1. Break the ciphertext into chunks of three eight-bit bytes.
  2. For each chunk:
    1. Denote the three bytes in the chunk as "x", "y" and "z", assigning the first byte to x, the second to y, and the third to z. 
      Example: x = 99, y = 97, z = 116
    2. Permute the bits of y according to the following pattern: 
      Input position  Output position
--------------  ---------------
      0                1
      1                4
      2                7
      3                2
      4                5
      5                0
      6                3
      7                6
      Call this permuted result "py". 
      Example: 97 in 8-bit binary is 01100001
        This permutes to 00001011, which is 11 in decimal.
    3. Pack x and py into a twelve-bit number by concatenating the four least-significant bits of py with all eight bits of x. Call the result "w". 
      Example: Since py = 00001011 and x = 01100001, the result would be
        1011 concatenated with 01100001: 101101100001, which
        is 2913 in decimal.
    4. RSA decrypt w with the following public key: 
           public modulus  (n) = 4097
     public exponent (e) = 11
      That 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.
    5. Pack py and z into a twelve-bit number by concatenating all eight bits of z with the four most-significant bits of py. Call the result "v". 
      Example: Since py = 00001011 and z = 01110100 (116 decimal), the
        result would be 01110100 concatenated with 0000:
        011101000000, which is 1856 in decimal.
    6. RSA decrypt v with the public key above. Call the result "t2". 
      Example: 1856 to the eleventh power is
        900238724867078044750327477390278656.
        900238724867078044750327477390278656 divided by 4097
        leaves a remainder of 500.
    7. Take the eight least-significant bits of t1 and call them 'u'. 
      Example: t1 = 3949, or 111101101101 in binary. Its eight least-
            significant bits are 01101101, or 107 in decimal.
    8. Treat t1 as a twelve-bit number (that is, pad it with zeroes until it is twelve bits long). Concatenate the four least- significant bits of t2 with the four most-significant bits of the padded t1. Call the result "s". 
      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.
    9. Treat t2 as a twelve-bit number, padding as necessary. Take its eight most-significant bits and call them "r". 
      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.
    10. Permute the bits of u, s, and r according to the following pattern (where zero denotes the least significant bit and seven, the most): 
      Input position  Output position
--------------  ---------------
      0                2
      1                7
      2                4
      3                1
      4                6
      5                3
      6                0
      7                5
      Call the results "o", "p", and "q", respectively. 
      Example:  u = 01101011 -> 10001111 (143 decimal)
          s = 01001111 -> 10010111 (151 decimal)
          r = 00011111 -> 11010110 (214 decimal)
    11. Convert o, p and q to their ASCII equivalents and write them down, in that order. 
      Example: [ This example, which started with the ciphertext composed
          of the ASCII string "cat" is not a good example. It
          decrypts to nonsense. ]
  3. (Go to next chunk)

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:

  1. Break the ciphertext into chunks of three eight-bit bytes.
  2. For each chunk:
    1. Denote the three bytes in the chunk as "x", "y" and "z", assigning the first byte to x, the second to y, and the third to z. 
      Example: x = C1 (hex) = 193 (decimal),
        y = 67 (hex) = 103 (decimal),
        z = BB (hex) = 187 (decimal)
    2. Permute the bits of y according to the following pattern: 
      Input position  Output position
--------------  ---------------
     0                1
     1                4
     2                7
     3                2
     4                5
     5                0
     6                3
     7                6
      Call this permuted result "py". 
      Example: 103 in 8-bit binary is 01100111
        This permutes to 10011011, which is 155 in decimal.
    3. Pack x and py into a twelve-bit number by concatenating the four least-significant bits of py with all eight bits of x. Call the result "w". 
      Example: Since py = 10011011 and x = 11000001, the result would be
        1011 concatenated with 11000001: 101111000001, which
        is 3009 in decimal.
    4. RSA decrypt w with the following public key: 
      public modulus  (n) = 4097
public exponent (e) = 11
      That 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.
    5. Pack py and z into a twelve-bit number by concatenating all eight bits of z with the four most-significant bits of py. Call the result "v". 
      Example: Since py = 10011011 and z = 10111011 (187 decimal), the
        result would be 10111011 concatenated with 1001:
        101110111001, which is 3001 in decimal.
    6. RSA decrypt v with the public key above. Call the result "t2". 
      Example: 3001 to the eleventh power is
        177797622648287046910292734455495033001.
        177797622648287046910292734455495033001 divided by 4097
        leaves a remainder of 2055.
    7. Take the eight least-significant bits of t1 and call them 'u'. 
      Example: t1 = 136, or 10001000 in binary. Its eight least-
        significant bits are 10001000, or, again, 136 in decimal.
    8. Treat t1 as a twelve-bit number (that is, pad it with zeroes until it is twelve bits long). Concatenate the four least- significant bits of t2 with the four most-significant bits of the padded t1. Call the result "s". 
      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.
    9. Treat t2 as a twelve-bit number, padding as necessary. Take its eight most-significant bits and call them "r". 
      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.
    10. Permute the bits of u, s, and r according to the following pattern (where zero denotes the least significant bit and seven, the most): 
      Input position  Output position
--------------  ---------------
      0                2
      1                7
      2                4
      3                1
      4                6
      5                3
      6                0
      7                5
      Call the results "o", "p", and "q", respectively. 
      Example: u = 10001000 -> 00100010 (34 decimal)
        s = 01110000 -> 01001001 (73 decimal)
        r = 10000000 -> 00100000 (32 decimal)
    11. Convert o, p and q to their ASCII equivalents and write them down, in that order. 
      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 '
    == Block 2 ==
    1. Next three bytes: 
      7C 6F 35
    2.   
      x = 7C
y = 6F
z = 35 (hex)
    3.   
      py = PERMUTE(6F) -> 9F
    4. w = F7C = 3964 (decimal)
    5. t1 = (3964 ** 11) mod 4097 = 432 = 1B0 (hex)
    6. v = 359 (hex) = 859 (decimal)
    7. t2 = (857 ** 11) mode 4097 = 3533 = DCD (hex)
    8. u = B0 (hex)
    9. s = D1 (hex)
    10. r = DC (hex)
    11. o = PERMUTE(B0) -> 68 (hex) = 104 (decimal)
p = PERMUTE(D1) -> 65 (hex) = 101 (decimal)
q = PERMITE(DC) -> 73 (hex) = 115 (decimal)
    12. 68 65 73 -> hes
== PUTTING THE BLOCKS TOGETHER ==

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:

To save disk space, the program has been compressed by the LISP compiler. The start-up code in the application runs a decompression routine before handing control to the LISP interpreter. The compression routine was provided by the compiler automatically has nothing to do with the design of Agrippa itself, nor would it typically be considered "encryption/decryption", so I did not include a report of it in my analysis.

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.

Depiction of the decryption algorithm on a single block

This picture shows the algorithm operating on the first two blocks of ciphertext from the real data.

Depiction of the decryption algorithm on a single block using real text
[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.