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.
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:
((x) **(pub=11)) **(priv) = x
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.
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: