Back to Table of Contents

Ayal Ryger's submission (Ayal gives thanks to John Ohno):

Agrippa self-destructs by writing the value 255 onto the first 40000 bytes of its file on disk (not the copy already loaded into RAM), even before it displays anything. [*Editor's Note:* See Brian's submission which shows that the original plan was to write 1's (255) into the binary, but was later altered to print a fake genetic sequence. Below, Ayal also recognizes that the shipping design was to insert fake genetic code.] The program is much much bigger than 40000 bytes, but obviously, it is irrecoverably damaged. It's unclear what would happen if it fails to overwrite itself. Ideally, it should abort, refusing to show the poem, but allowing the user to retry later. Did the floppy have any copy protection to prevent the user from retrying by those means?

The truly interesting find is how the poem is obfuscated to begin with. Someone familiar with a debugger (Apple's was MacsBug) could rip it from RAM. But everyone else was out of luck.

Despite all of the mentions of (NIST/NSA) DES (and no other ciphers), Agrippa's obfuscater is actually a variant of RSA.

The RSA modulus is only 12 bit, so even in 1992, the private key could be cracked by brute force in 1 second on a PC. The private key would allow someone to insert new text, without changing the public key (or the program). I.e. the private key is not needed to *decode* the text; it would allow someone to *impersonate* Gibson writing new text.

Using smarter math, the private key can also be computed on paper: it is 3491.

See http://en.wikipedia.org/wiki/Chinese_Remainder_Theorem
and http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

For each 3-byte block, the same function is applied. Therefore, an instance of repeated plaintext with the same block alignment will have corresponding repeated ciphertext.

There are many candidates. E.g. "of ", "to ", "in ".

A block (3 chars) is split into 2 12-bit halves. Each half is RSA-like encrypted, using exponent

e=11 and modulus m=4097 = 17*241. -1 **11 == -1. 0 **11 ==0

So consider 0 to be 4096, which otherwise would not occur in 12bit numbers.

Note that 11 is its own inverse mod 15: (11*11 mod 15 ==1)

Each byte then has its bits reordered.

The 1st and 3rd byte use the same bit order.

The obfuscated text was then escaped (adds backslashes before any special characters such as backslash or double-quot) and pasted into the Lisp source file!

Then Ayal followed up with more information about brute forcing the modulus:

Regarding cracking RSA, I'm only doing what any good course in Discrete Math might have on its exam, (to be computed with pencil & paper).

There are 2 levels of brute force:

- try all exponents "priv" to find one such that
((x) **(pub=11)) **(priv) = x

- (smarter) Factor the modulus by trying to divide
by each integer less than square root of modulus.
- Then compute Euler's phi function.
- Then compute 11's multiplicative inverse
- modulo the phi.

And again, with more information about the non-crypto aspects of Agrippa:

Below is some analysis which does not relate to the crypto. It is similar to the maps that were published prior to the contest, but is much more complete.

disk blocks (512 bytes)

0 - 48 : HFS metadata (a few bytes change when Agrippa is run, probably just to update the timestamp on the file) 49 - 1406: data fork of Agrippa; has 38 bytes of junk (!) after the (logical) end of file, presumably added by HFS. 1407 - 1703: resource fork of Agrippa 1704 : gzip'd (yes, gzip) FS metadata. clearly a corruption from OSX. 1705 - 1706 : filled with zeroes 1707 - 1711 : vestiges of old (unused) Agrippa resource fork 1712 : vestiges of old (unused) Agrippa 68k code. 1713 - 2877 : filled with 0xf6 -- a common pattern when formatting floppy disks. 2878 : HFS metadata (disk label?) 2879 : 0xf6 format pattern again. 2880 END OF DISK

data fork (offsets in bytes)

0 - 40000 : the faxed Lisp code for Agrippa put zeroes here, as its self-destruct. The later, actual disk did not. 0 - 466791 : mainly M68k code 466792 - 680167 : data, no M68k code 680168 - 686167 : The disk (not Lisp) version of Agrippa's self-destruct, puts a "genetic sequence" bytes here: 1503 A's 1448 C's 1516 G's 1525 T's. 686168-695258 : data, mostly 32bit, with clear patterns.

**"Genetic" data**

When divided into 3-letter groups (as is meaningful for RNA / DNA), all 64 possible combinations exist. The counts fit a bell curve, but with some anomalies (that might just be a bad random number generator). Without specific knowledge of genetics, I can't rule out that they're real.

After the contest closed Ayal provided some historical context:

- The programmer appears to be affiliated with Bolt, Beranek, & Newman, which would explain why Agrippa uses Lisp. Fax headers & other evidence are weak. BBN is close in every way to MIT. Both were big Lisp users, and were major creators of the Internet. [
*Editor's note:*While this supposition is not conclusive, an archived letter from the programmer suggests that he or she was working at BBN, but possibly for a short duration.] - A table-driven implementation of both the RSA and the bit-permutations steps can be >100 times as fast as the original.
- The closest comparable cryptography in consumer electronics was the Atari 7800 encryption algorithm in 1986. This ran on a tiny machine compared to a Macintosh, and its design is secure even today!
- It's possible to crash Agrippa, causing Lisp to pop up debugging & editing windows! It's not clear if any variables are accessible though. Source code is not accessible in this manner.
- Bytes are probably displayed using the MacRoman character set, which is quite different from modern Latin1/Windows1252 or Unicode. It happens that the poem is all ASCII, so this is not observable.

Ayal provided a Javascript implementation, which can be run in the web browser.