jim@randvax.UUCP (Jim Gillogly) (04/07/88)
Earlier this week an encryption program was posted to alt.sources by Karl Denninger with a challenge cryptogram. He described the algorithm as follows: > The cipher is a substitution cipher executed by the 'XOR' > instruction, with an interesting twist. > > Picture a key and plaintext, as thus: > > Key > a b c d e f g h i j > Plain> z x y c d s f g h t > > The cipher proceeds down the line, from left to right, XORing the > bytes one by one. This would be trivially easy to break, except for > one feature: > A checksum is kept of the bytes processed before and after . XOR; when this checksum reaches a value the entire KEY > string is XORd with the checksum value; the checksum value > is then normalized to reflect the remainder from the > 'preset' value. > ... > For text, though, > there is a small window in the very front of the file in which it might be > possible to perform pattern-analysis to produce the password. To forestall > these attempts, 768 bytes of randomly-generated garbage are prepended to the > file before encryption takes place, and are removed on decryption. These > random bytes serve only to provide a 'seed' for the encryption function to > prevent pattern analysis. ... The program accepts keys of up to 80 characters, and he recommends using sentences. This is basically a block periodic system with 256 keys (the original key and all possible XOR's of it with a single byte). It has a number of weaknesses, though, including these three fatal ones: (1) A bug in the program (the famous && instead of & C trick) limits it to 2 keys: the "checksum" XOR'ed with the key turns out to be either 1 or 0 (usually 1). (2) The period (i.e. key length) can be determined using the Index of Coincidence or Kasiski methods (preferably I.C., which needs less text). (I didn't bother using this one.) (3) Too many characters are encrypted with the key before it's changed to the next value. Even with all three of these fixed I wouldn't trust my diary to it. I used "crib-dragging" to break it: assume various probable words in the plaintext, then move them along the ciphertext XORing them with the ciphertext and all 256 possible "checksums"... all 2 possible checksums in this case, because of bug (1); however, the time to run this is negligible and fixing the bug wouldn't help that much. Since he specified that the challenge cryptogram was in English and that sentences were a reasonable idea for the key, I tried various words like " the " and " that ", and printed out all the result strings that had letters, spaces, commas and periods (in reverse order, since each block is encrypted back-to-front). Dragging " the " through the text gives about 200 letter+punctuation strings, including the likely-looking " all " and " for ", which we then assume are pieces of the key. Dragging " The " yields "u.For", which looks like the end of the key and its beginning. Next I tried "denninger", "Denninger", and "Karl", none of which looked promising; "Karl" looked promising, but with capitals in the wrong places, so I tried " karl " and got two more good ones: "all yo", "you do". There was some overlap here, so I tried decrypting the ciphertext with the key "For all you do", expecting that bits of the text would be decrypted with this key, since there are only two variations of the key. Running "strings" on the result gave a few more pieces of plaintext, including "Microsoft", "Microport", "dn't expect", " mailed ", "ended only", "n't want t", and "icroport, Inc.". By this time (or earlier) there was enough key to suggest that an apostrophe ought to be included in legal key-letters, and it all falls out. The key is (as you've figured out) "For all you do, this Bud's for you." and the plaintext is below. One moral is that one doesn't get good security by simply trying things - Doug Gwyn and others have pointed out several times that one should really get advice from people who break these things... as Karl did by posting it. Jim Gillogly {hplabs,ihnp4}!sdcrdcf!randvax!jim jim@rand-unix.arpa ---------------------------------------------------------------------------- Sun Apr 3 22:52:26 CDT 1988 Congratulations! You have managed to decrypt the secret message in the shar distribution. We really didn't expect anyone to come up with this, but since you have done so you have a chance at a small reward. Contact MCS, Inc. by email or voice phone during business hours at (312) 566-8910, or via email at (...ihnp4!ddsw1!karl). If you are the FIRST person who reports to us with an exact copy of this file (either printed or emailed to the above address) you will receive $25.00 Included in this file are some summary statistics about our system over the last few days and a letter which was mailed to some interested perns a week or so back; these are intended only to build the size of the file to a reasonable level. Wouldn't want to make it too easy on you out there, would we? ----- Begin filler ----- 84450 page cache hits 13830 page cache misses 0 procs swapped in 0 procs swapped out 13830 filesystem page reads 13 swap area page reads 33 swap area page writes 728 pages reclaimed from free list 158201 pages shared due to copy-on-write fork 9 pages shared due to cache hits 67770 shared pages copied 2825211 page faults 275629 cpu context switches 1804298 (non clock) device interrupts 329206 traps 11052572 system calls UID PID PPID C STIME TTY TIME COMMAND karl 14976 14932 0 22:39:08 02 0:13 /usr/bin/vi /prv/karl/.article sysadm 6932 42 9 18:35:23 01 9:18 systat karl 14932 43 0 22:38:50 02 0:01 -ksh karl 15350 13741 49 22:52:22 03 0:03 vi winner karl 15431 15350 69 22:55:13 03 0:00 ps -adf And a random Text inclusion! Hi there! All of you have requested information on our autobaud 'getty' replacement package. Here's the currnet info, as we have it: o It augments Microport's getty, and does not entirely replace it. You use this one on your dialin lines. o The version Bill Vajk uses has been superseded, with improved capabilities. o It is available at no charge as a premium with the purchase of the following products: o AKCS (our bbs software/Microport, 3b1/3b2 & SCO Xenix V) o TAD (Sco Xenix V only) o Any Microport UNIX or SCO Xenix full system (ie: Dev Sys + Runtime or complete) Separately, the cost is $50.00. It comes with a short description of operation and instructions (really, it installs in 2 minutes :-) If we can be of help don't hesitate to holler! * (SCO Xenix is a trademark of the Santa Cruz Operation & Microsoft) (Microport UNIX is a trademark of AT&T Bell labs & Microport, Inc.) -- Jim Gillogly {hplabs,ihnp4}!sdcrdcf!randvax!jim jim@rand-unix.arpa