rs@uunet.UU.NET (Rich Salz) (06/21/87)
Submitted by: Robert W. Baldwin <BALDWIN@XX.LCS.MIT.EDU>
Mod.sources: Volume 10, Issue 11
Archive-name: cbw/Part11
#! /bin/sh
# This is a shell archive. Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file". To overwrite existing
# files, type "sh file -c". You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g.. If this archive is complete, you
# will see the following message at the end:
# "End of archive 11 (of 11)."
# Contents: cbw.doc
# Wrapped by rs@uunet on Wed Jun 17 18:17:34 1987
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f cbw.doc -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"cbw.doc\"
else
echo shar: Extracting \"cbw.doc\" \(51998 characters\)
sed "s/^X//" >cbw.doc <<'END_OF_cbw.doc'
X
X
X
X
X
X
X
X CRYPT BREAKERS WORKBENCH
X
X USERS MANUAL
X
X
X
X
X
X
X
X
X Robert W. Baldwin
X baldwin@xx.lcs.mit.edu
X mit-eddie!baldwin
X October, 1986
X
XOverview
X The Crypt Breakers' Workbench (CBW) is an interactive multi-window system
Xfor mounting a cipher-text only attack on a file encrypted by the Unix crypt
Xcommand. CBW is a workbench in the sense that it provides the user with an
Xintegrated set of tools that simplify the initial, middle and final portions of
Xthe decryption process. A user interacts with the workbench by choosing tools
Xand setting parameters. CBW carries out the work and displays the results. A
Xmoderately experienced user of CBW can easily decrypt both long and short
Xmessages when bigram statistics are known for the message space. The basic
Xcryptanalytic techniques used by CBW are described in a paper by Reeds and
XWeinberger that appeared in the October 1984 issue of the ATT Bell Laboratories
XTechnical Journal. This manual explains the capabilities and operating
Xprocedures of CBW.
X
X1. Introduction to the Workbench
X A workbench is a place where a craftsman can quickly and comfortably carry
Xout a wide range of tasks. The ease of performing tasks comes from the range
Xof tools present on the workbench and the experience of the craftsman. Each
Xtool has its strengths and limitations, but the craftsman can select the best
Xtool for the job at hand. The workbench is not a static thing. Often the
Xcraftsman builds a jig that is tailored to a particular problem. Some jigs are
Xlater discarded while others become permanent fixtures of the workbench. It is
Xin this sense of the term workbench that CBW is a workbench for breaking the
XUnix crypt cipher.
X
X CBW has evolved over the past two years, and it will continue to evolve as
Xthe process of decrypting Unix files becomes better understood. Already I can
Xthink of commands that I want to add to speed up the end-game of the decryption
Xprocess. It is being released in its current form to allow others to play with
Xit and add their own ideas.
X
X One goal of releasing CBW is to discourage people from using the Unix
Xcrypt command for sensitive information. Crypt was never intended to be a
Xhighly secure cipher. It's primary advantage has been its speed, which made it
Xsuitable for integration into a wide range of application programs. The CBW
Xprogram simply points out how easy the cipher is to break using the ideas
Xdescribed by Reeds and Weinberger in the October 1984 issue of the ATT Bell
XLabs Technical Journal. As those authors suggested, if you must use crypt, you
Xshould run compress on the file before encrypting it.
X
X2. Key Space Attack
X The basic metaphor of CBW is that the computer knows several message-space
Xsearching strategies, and the user decides which strategy to try next. The
Xprogram takes on the burden of carrying out the strategy, but it is up to the
Xuser to choose the strategy and to set the necessary parameters (e.g., how
Xclose a scoring statistic has to be to its expected value before the program
Xwill accept a guess). When a strategy completes, its results are displayed.
XAn important feature of the program is that the results are displayed in a
Xmanner that makes it easy for the user to decide what to do next. Further, it
Xeasy to carry out decisions such as accepting the outcome as is, accepting it
Xwith minor changes, or starting over with a different strategy or a different
Xparameter setting.
X
X To use CBW it is necessary to know a few facts about the underlying cipher
Xsystem, in this case the Unix crypt program. The primary fact to know is that
Xthe job of deciphering a file can be broken down into several smaller jobs.
XThe ciphertext being decoded can be divided into blocks of 256 characters, and
Xeach block can be decoded separately.
X
X Each block is encrypted using a relatively simple cipher system, but the
Xkey to this simple system changes at the end of each block. Effectively, each
Xblock is encrypted by a single rotor enigma system. The rotor has 256
Xpositions to handle full eight-bit bytes, and this leads to the number of
Xcharacters in each block. CBW represents the wiring for each block's rotor by
Xa permutation matrix.
X
X Once several blocks are decoded (or mostly decoded), it becomes possible
Xto determine how the key changes after each block. The key change is expressed
Xas a permutation matrix called Zee. Typically one needs to solve four or five
Xblocks (about 1000 characters), before it is possible to automatically compute
XZee and solve the rest of the file. For short messages there is no need to
Xcompute Zee.
X
X After the inter-block relationship has been determined, the program,
Xzeecode, can be used to decipher the whole file. The program zeecode looks at
Xthe save-file produced by CBW to get the information it needs to decode an
Xentire file.
X
X3. Files, Terminals and Shell Variables
X This documentation assumes that the code, source, and datafiles are kept
Xin a directory called /projects/Ecrypt, but these files could be placed
Xanywhere.
X
X The most important files are the program itself, and the files that
Xcontain the English language statistics. The program is called 'cbw'. The
Xstatistics files are 'mss.stats', 'mss-bigram.stats', and 'trigram.stats'. For
Xthe probable word guessing command there are files like 'common.words'.
X
X To make it easy for users to provide their own statistics files, cbw uses
Xthe shell variables LETTERSTATS, BIGRAMSTATS, and TRIGRAMSTATS to access these
Xfiles. The variable DICTIONARY identifies a file of words for the
Xlookup-pattern command (one word per line). These shell variables must be set
Xto the full pathnames for the desired files. The file stats.slice defines all
Xof these variables. Your .login file should contain a line like:
X
X source /projects/Ecrypt/stats.slice
X
X The main input to cbw is a ciphertext file, and the main output is a save
Xfile that specifies how the ciphertext can be decoded. The program 'zeecode'
Xuses CBW's save file to decode the ciphertext file. The ciphertext file for
Xcbw is assumed to have a name like 'fileroot.cipher'. The output of cbw is
Xstored in the file named 'fileroot.perm'. The '.perm' stands for permutation.
X
X
X
X3.1. Terminal compatibility
X CBW is designed to run on any display terminal. To run on a particular
Xterminal CBW must be able to generate graphic characters on that terminal and
Xbe able to recognize the escape sequences sent by that terminal's function keys
X(e.g., the arrow keys). CBW adapts to different terminals by examining shell
Xvariables (TERM, GRAPHICSMAP, and KEYMAP), the termcap entry, and compiled in
Xdefaults. It builds a keystroke map and a graphics symbol map which translate
Xbetween arbitrarily long sequences of ascii characters and the internal
Xrepresentation for keystroke commands and graphic symbols. The rest of this
Xdocument will describe the action of keys, but the reader should remember that
Xthe binding between commands and keys can be changed.
X
X You should be able to use CBW without understanding the details of
Xterminal handling, but for completeness, those details are presented in the
Xappendix. You will need to be sure that the shell variable TERM identifies the
Xkind of terminal you are using. You should also be able to find a shell script
Xthat will set up the graphics map for your terminal. List the files matching
X/projects/Ecrypt/*.slice, if there is one for your terminal (e.g.,
Xvt100.slice), execute it to initialize the necessary shell variables (e.g.,
Xsource /projects/Ecrypt/vt100.slice).
X
X In general an unrecognized keystroke generates a self-insert command.
XHowever, control characters other than newline and tab are reserved for default
Xkeystroke commands. To insert a control character, precede it by a C-Q. The
XC-Q command will create a self-insert command for the next ascii character
Xreceived from the terminal.
X
X The notation C-N will be used to represent pressing the N or n key while
Xthe control key is held down.
X
X4. Getting Started and Getting Out
X After setting up the shell variables described in the previous section,
Xyou can invoke the Crypt Breakers' Workbench from any directory by typing:
X
X /projects/Ecrypt/cbw fileroot
X
XWhere 'fileroot.cipher' is the name of the ciphertext file in the current
Xdirectory. You do not need to specify the full pathname of the cbw program if
X/project/Ecrypt is in your shell's search path.
X
X To exit the program move the cursor to the bottom window (using the arrow
Xkeys or C-N or C-X), then type 'q', a space, and a return. The 'q' signifies
Xthe quit command, the space causes command completion to be invoked (i.e.,
X'qui ' would work just as well), and the return key causes the command to be
Xexecuted. If you have changed the decryption window since you last saved your
Xwork, the program will ask if you really want to quit. Type 'y' if you want to
Xquit, or any other key to abort the quit command.
X
X5. Commands
X There are two types of commands: keystroke and user commands. Keystroke
Xcommands are interpreted by the window that currently contains the cursor. For
Xexample, the up-arrow key generally moves the cursor up by one line, but in the
Xdecryption-block window, it moves the cursor up two lines. An attempt has been
Xmade to keep the keystroke commands uniform and emacs-like. The keystroke
Xcommands will be explained for each window.
X
X The user commands can take arguments typed by the user. They are entered
Xinto the command line via a simple editor and executed when the user types a
Xreturn. The cursor must be in the user i/o window to type or execute user
Xcommands. The details of the editor are given in the section on the user i/o
Xwindow. Each user command is explained in section 7.
X
X-------------------------------------------------------------------------------
X
X Crypt Breakers' Workbench
XBlock - 0 Know 14 of 128 wires |Word Match
X |.n.y
X@Device[dover]......e[...........o.............A.........@....i. |Andy
X |envy
X......................... ...................................... |indy
X |only
X....... .................................................xt.r.a. |
X |
X..o.......s.........d.s.............e.........t....o.mu......on |
X |
X |
X |
XProbable word search -- Done |
X@Device[dover]..t...e[Font.timesroman..].....e.A..i.l....@Sectio |
Xn..n..................... .r...n......n.ly.....on.....h......... |
X....... .........;................ons.......e .c.... ....xt.r.a. |
X..o.......s.........d.s.............e.........t.. .o.mu..c...on |
X |
X `----------
X
XHelp : F3 enters guess, ^G undoes it.
XStatus : Command completed.
XCommand: pwords-from file: mss.words Max dev: 1.2 (try 1.0)
X
X-------------------------------------------------------------------------------
X
X Figure 5-1: Sample Screen
X
X6. Windows
X The screen is partitioned into seven windows as shown in figure 5-1.
XAssociated with each window is a keystroke command interpreter and private
Xstate information. By convention keys like up-arrow, C-D, and delete do
Xsimilar things in all the windows.
X
X There are some keystrokes that have the same effects in all windows, they
Xare:
X
XC-L Redraw the whole screen.
X
XC-X, F4 Jump to command input line.
X
XC-Q Quote. Insert the following character.
X
XC-Z Abort the current command, restore the terminal modes, suspend
X the program and return to the shell. If the program is
X restarted, the terminal will be initialized for CBW and the
X screen redrawn. The command that was active (if any) when the
X C-Z was received is aborted. Actually this command is invoked
X when CBW receives a SIGTSTP signal.
X
XC-C Restore the terminal modes and kill the CBW process. Actually
X this command is invoked when CBW receives a SIGINT signal.
X
X The following subsections describe the features of the windows starting at
Xthe top of the screen and working downwards.
X
X
X
X6.1. Banner window
X This window contains the program title. Default behavior for arrow keys.
X
X
X
X6.2. Decryption Block Label window
X This window contains a single line that describes the block displayed in
Xthe decryption block storage window. The block number is shown at the left end
Xof the line. The right hand side of this line displays how much is known about
Xthe decryption permutation for the current block. This value is expressed in
Xterms of the number of wires (2-cycles in the permutation) that are known. A
Xdecryption permutation that maps character A to B also maps B to A, so there
Xare only 128 wires even though there are 256 possible characters.
X
X
X
X6.3. Decryption Block Storage window
X Displays what is known about the plaintext corresponding to a single block
Xof 256 ciphertext characters. A dot character, which is different from a
Xperiod character, is shown when the plaintext character is unknown. Other
Xgraphic characters represent control characters like newline, tab, and
Xform-feed. If a character decrypts into a byte that has the high bit set
X(i.e., not an ascii character), it shows as a solid diamond.
X
X Most keystrokes are self-insert commands. When a character is inserted,
Xit replaces the character at the current position, and any deduced characters
Xare displayed and highlighted (by underlining). The other keystroke command
Xcharacters are:
X
XC-D, DEL Delete character forward, delete backward. This forces a
X permutation wiring to be removed. It can do unexpected things.
X Consider a permutation with A wired to B and P wired to
X Q. Adding a wire from B to P, then removing it with the DEL
X command does not restore the original AB and PQ wirings.
X
XC-G Undo. Backup the permutation to the state it had before the
X last contiguous sequence of keystrokes. Arrow commands
X terminate a contiguous sequence of keystrokes. In most cases,
X undo should be used instead of DEL or C-D.
X
XC-T Try-all. Display a list of the ascii characters that could be
X put in the current cursor position without conflicting with the
X existing permutation wirings. The list is sorted with the most
X likely character first (leftmost).
X
XC-L Redraws the whole screen. As a side effect this erases the
X list of characters produced by C-T.
X
XF1, C-R Move to the previous block of 256 characters.
X
XF2, C-S Advance to next block of 256 characters.
X
X
X
X6.4. Guess Block Label window
X Title for the Guess Block Storage window. Default arrow behavior.
XParameters for guessing commands are displayed in this window.
X
X
X
X6.5. Guess Block Storage window
X This window is multiplexed between different strategies for guessing that
Xa particular plaintext string is at some position in the block. The general
Xmeaning of the keystroke commands are:
X
XF2, C-S Goto next guess.
X
XF3, C-A Accept guess, merge it into the current decryption block. This
X does not automatically advance to the next guess.
X
XC-G Undo the merge of a guess. Actually this is identical to the
X undo in the decryption block storage window, so it will only
X undo the guess if you have not typed any commands to the
X decryption window.
X
X
X
X6.6. Word Lookup
X This window displays the list of words in a dictionary that match a
Xparticular pattern. The pattern is specified by the lookup-pattern command
X(see section 7.4). Only the first 20 or so matches are displayed. The
Xdictionary file defaults to /usr/dict/words, but the pathname can be set using
Xthe environment variable DICTIONARY. The dictionary file contains a sorted
Xlist of words separated by newline characters. Case is ignored.
X
X
X
X6.7. User I/O window
X This window consists of three lines: help, status, and command. The help
Xline changes as the cursor moves between windows. It reminds the user of the
Xcommands available in the current window. A more elaborate help facility has
Xnot been implemented. The status line is used to show error and completion
Xmessages. The cursor cannot be positioned over either the help or status
Xlines.
X
X The command line behaves like a line editor. The editing characters are:
X
XC-U Erase the whole line.
X
XC-F, C-B Move forward and backward one character.
X
XC-D, DEL Delete one character forward or backward.
X
XF2, C-S Next-Argument. It searches for the first "%" character in the
X command line, deletes it and leaves the cursor there. This is
X used with command templates.
X
XSpace Within the first word on the command line, a space character
X invokes command completion. A completed command string is a
X template command with argument slots (marked by %) and
X suggested argument values.
X
XReturn Execute command. The cursor can be anywhere within the command
X line.
X
X7. User Commands
X
X
X
X7.1. quit
X Exit the program. If any of the permutations have changed since they were
Xlast saved, the user is asked for confirmation.
X
X
X
X7.2. save-permutation
X Associated with each block of the ciphertext is a permutation that tells
Xhow to decode the known characters. This command saves those permutations.
XThere is a special permutation, called Zee, that relates the permutations of
Xsuccessive blocks. The save command also saves Zee.
X
X
X
X7.3. load-permutations
X Inverse of save. The ciphertext file is loaded automatically when CBW
Xstarts, but the permutation file must be loaded explicitly. This command is
Xused to load previously saved work. Warning: the load command will replace the
Xcurrent permutations without asking whether you want to save them first.
X
X
X
X7.4. lookup-pattern
X Searches a dictionary for words matching a pattern. The dictionary is
Xspecified by the shell variable DICTIONARY. The pattern is specified as an
Xargument to the command. Currently, the pattern consists of characters and
Xperiods (.). The period characters match any one character in a word from the
Xdictionary. This means that you have to know the length of the word you are
Xlooking for. The current dictionary does not contain suffixes, so you will
Xoften need to try a few patterns to find the desired word. There are many ways
Xto improve this command.
X
X
X
X7.5. bigram guessing
X This command uses a statistics based on letter pairs (bigrams) to
Xcarefully guess at the plaintext. This is the most useful command in CBW and
Xit represents a significant improvement on the techniques discussed in the
XReeds and Weinberger paper. This tool works by finding the best position for
Xguessing, and then trying all 128 ascii characters in that position. For each
Xof the 128 trials the deduced characters are scored and the trial with the best
Xscore is accepted if it meets the criteria set by the user. The process
Xrepeats for the next best position until no positions satisfy the user's cutoff
Xcriteria.
X
X The best position for guessing is the one that produces the most evidence.
XIt is the position that generates the largest number of deduced characters.
XPreference is given to positions that are deduced next to an already accepted
Xcharacter because bigram statistics can be used in these places. An
Xapproximation to the best position can be identified by examining the
Xciphertext. For the crypt cipher it is possible to identify all the characters
Xin the ciphertext that were the output of a particular terminal of the block
Xrotor. Each of the 128 trial plaintext characters for that position will
Xgenerate a wiring from that terminal to some other terminal. If the other
Xterminal is already used, the guess is rejected immediately. However, if the
Xrotor terminal is free, additional character positions may be deduced because
Xof the symmetric nature of the rotor (recall that if the rotor maps X to Y then
Xit also maps Y to X). Thus by examining the ciphertext CBW can set a lower
Xlimit on the number of characters that will be deduced by guessing in a
Xparticular position.
X
X The bigram command takes two arguments, a cut-off level and a minimum
Xprobability. The purpose of the cutoff level is to insure that a guess is only
Xaccepted if the probability of the guess being right is at least some factor
Xgreater than the probability that the guess is wrong. A cutoff level of 2.0
Xtells CBW to only accept guesses when the probability of the guess being right
Xis at least twice as great as the probability that the guess is wrong. Since
Xall 128 possible guesses are tried, the probability of a guess being wrong is
Xjust the sum of the probabilities that any other guess is correct.
X
X The probability that a guess is correct is based on a statistic that is
Xthe sum of the logarithm of the expected letter pair frequencies of deduced
Xcharacters appearing next to the deduced or accepted characters. The mean and
Xvariance of this statistic is a simple function of the number of characters
Xdeduced, so it is possible to approximate the probability density distribution
Xof the statistic with a gaussian distribution. The probability (actually
Xprobability density) that a guess is correct can be computed from the gaussian
Xdistribution based on the number of standard deviations that the observed value
Xof the statistics differs from its expected value.
X
X The minimum probability tells CBW to only accept the best guess if its
Xprobability is higher than some value. The minimum probability comes into play
Xwhen very few letter pairs are deduced. In those cases it is better to skip
Xguessing until additional characters have been deduced.
X
X This command can be used to automatically deduce about 100 of the 256
Xpossible positions within a block. It is by far the most useful command in the
Xworkbench. My usual strategy is to run the command three times on each block,
Xfirst with a cut-off of 1.5 and a minimum probability of 0.6, then with a
Xcut-off of 1.2 and a probability of 0.4, and finally with a cut-off of 1.0 and
Xa probability of 0.15.
X
X An essential aspect of this command is that it carefully selects the
Xpositions where it does guessing. After each guess it selects the position
Xthat will deduce the maximum number of letters and letter pairs. Without the
Xcareful searching, it is only slightly more effective than the equivalence
Xclass command (which is now obsolete).
X
X The method for computing the bigram probability is somewhat interesting.
XRather than having a 128 x 128 entry table, the program uses a 36 x 36 entry
Xtable with a character mapping table. For example, the character map treats
Xupper and lower case letters the same, and it treats all left brackets and
Xparenthesis the same. To compensate for the information lost by treating upper
Xand lower case letters as the same, the program bases its guess probabilities
Xon the product (actually products are taken by summing logs) of the monogram
Xand bigram probabilities for the deduced characters. Compensating for the lost
Xinformation lead to a 30% increase in the number of correctly guessed
Xcharacters.
X
X
X
X7.6. pwords
X Given a list of words that are likely to be found in the text, this
Xcommand tries each word in every possible starting position, and accepts a
Xguess if the score for the deduced characters is within a given number of
Xstandard deviations of its expected value. The list of words must be stored in
Xa file, one word per line, using standard C backslashing conventions for
Xcontrol characters (e.g., "\n" for newline).
X
X CBW used to have a command that accepted words from the keyboard, but I
Xfound that users are more thorough in selecting words if they have to
Xseparately edit a file. The result is a collection of reusable files that
Xbecomes a permanent part of your workbench. For example, I have files for mail
Xheaders, C programs, computer science articles, common short words, and various
Xtext formatters. Of course in the spirit of a workbench, if you do not like
Xthis limitation it is easy to add the desired command.
X
X
X
X7.7. auto-trigram guessing
X This command is obsolete. Use pword instead.
X
X
X
X7.8. knit-blocks
X This command is used to deduce the relationship between successive blocks
Xof the cipher. That relationship is stored in a permutation called Zee. Given
Xfour or more partially filled in blocks, the knit command can be used to deduce
Xinformation about Zee. You can then use the propagate command to transfer what
Xyou have solved in one block to any other block (see section 7.10). For the
Xtheory of knitting see the Reeds and Weinberger paper.
X
X The knitting processes is not deterministic unless you have completely
Xsolved four blocks or partially solved more than five blocks. When knitting
Xblocks k through n, the knit command displays block n+1 in the decryption
Xwindow and in the guess window it displays the characters that would be deduced
Xby each knitting guess. You can use the F3 (or C-A) key to accept a guess
Xand/or the F2 to advance to the next guess.
X
X The knit command is intolerant of incorrect decodings of a block. If you
Xare not sure of the plaintext value of a character (e.g., whether some position
Xcontains a space or a tab character), it is best to leave character undecoded.
XIf any character is incorrectly decoded, then the knit command will run for
Xhours. If the command runs for more than five minutes, abort it with C-Z. A
Xclever algorithm might avoid this mis-feature.
X
X The knit command displays how much of Zee is currently known.
X
X
X
X7.9. Clear-zee
X Sets the Zee permutation to a state where no information is known. This
Xis the only way to recover from a bad knitting.
X
X
X
X7.10. propagate using Zee
X If the Zee permutation is partially known, the propagate command can be
Xused to deduce unknown characters in one block from known characters in another
Xblock. Its arguments are any two block numbers. The blocks do not have to be
Xadjacent. The destination block will be displayed in the decryption window
Xwith the deduced characters highlighted.
X
X8. Known Bugs
X
X 1. Due to a simple memory allocation strategy, only the first fifteen
X or so blocks of a file can be examined.
X
X 2. CBW can only process full 256 character blocks, which means that it
X cannot be used to decode very short files.
X
X 3. Trigram stats are no longer used, so they should not be loaded.
X
X 4. Replacing the knit window without accepting the current guess (by
X say invoking the propagate command), causes the current knitting
X guess to be accepted. This bug comes from an oversight in my window
X package and is a bit of a pain to fix.
X
X 5. See the file TODO.txt for a list of suggested enhancements.
X
XAcknowledgments
X The author would like to thank Simson L. Garfinkel, Samuel M. Levitin,
XClifford Neuman, and Tim Shepard for the ideas and programs they contributed to
Xthis project. Paul Paloski provided extensive comments on the alpha test
Xversion of CBW, and John Gilmore enhanced it for portability.
X
XI. Graphics Map
X
X CBW uses non-ascii symbols to display non-printing characters such as
Xnewline and tab. Each kind of terminal supports a different set of graphics
Xcharacters (if any), and even if two terminals support the same graphic (e.g.,
Xmiddle horizontal bar) they usually represent it by different sequences of
Xascii characters. CBW handles these differences by using an explicit graphics
Xsymbol map. The map converts an internal symbol identifier into a string of
Xascii characters which cause the terminal to display the desired symbol.
X
X The graphics map can be set by the user via a shell environment variable.
XThe map is build in three steps. CBW first looks in the termcap entry for this
Xterminal for the definitions that describes how to enter and exit the
Xterminal's standout mode (inverse video) and graphics mode. There must be a
Xdefinition for standout mode, but the graphics mode fields can be missing.
XNext, a default graphics map is read from a compiled in string (see
Xterminal.h). The default map uses standout mode to represent symbols. For
Xexample, the newline and tab characters are drawn by displaying an 'n' and a
X't' in standout mode. A complete list of the defaults is given in table I-1.
X
X-------------------------------------------------------------------------------
X
XGRAPHIC USE
X\St Tab characters.
X\SX Non-Ascii character.
X\Sn Newline character.
X\Sr Return character.
X\Sf Form feed character.
X\SC Other control characters.
X\S Plaintext character unknown (standout space).
X\N^ Pseudo underline to highlight char above this one.
X\N| Vertical line segment.
X\N- Horizontal line segment.
X\N` Lower-left corner of box.
X
X
X Table I-1: Default graphic symbols
X
X-------------------------------------------------------------------------------
X
X The last step of building the graphics map is to read the shell variable
XGRAPHICSMAP (if it is defined). This variable is formatted like a /etc/termcap
Xentry. It is a sequence of definitions separated by whitespace (spaces, tabs,
Xor newlines) or colons. Each definition has a label and a value. The label is
Xa string terminated by an '=' character. The label associated with each symbol
Xis given in table I-2. The value is a sequence of characters terminated by a
Xcolon (or the end of the environment variable string). The first two
Xcharacters of the value string are special. The first character must be a
Xbackslash ('\'). The second character specifies the mode that the terminal
Xshould be in when the remainder of the value string is displayed. That
Xcharacter must be one of 'N', 'S', or 'G' for normal, standout, or graphic
Xmode. The combined mode of standout plus graphics cannot be represented (this
Xcould be fixed in terminal.c). The rest of the value characters can use the
Xstandard backslash conventions (\n, \r, \t, \f, \\, and \177) with the addition
Xthat \E will be translated into an escape character (\033).
X
X-------------------------------------------------------------------------------
X
XLABEL SYMBOL
Xtb Tab characters.
Xna Non-Ascii character.
Xlf Newline character.
Xcr Return character.
Xff Form feed character.
Xcc Other control characters.
Xuk Plaintext character unknown.
Xul Pseudo underline to highlight char above this one.
Xvb Vertical line segment (bar).
Xhb Horizontal line segment (bar).
Xll Lower-left corner of box.
X
X
X Table I-2: Symbol labels for graphic map
X
X-------------------------------------------------------------------------------
X
X The default map string and the h19 graphics map string are listed below to
Xillustrate the format.
XDefault Graphics Map String:
X
X #define DGRAPHICS "tb=\\St:na=\\SX: lf=\\Sn:cr=\\Sr:\
X ff=\\Sf:cc=\\SC:uk=\\S :::ul=\\N^:
X hb=\\N-:vb=\\N|:ll=\\N`:"
X
XH19 Graphics Map String:
X
X setenv GRAPHICSMAP 'tb=\Gh:lf=\Gk:cr=\Gg:na=\Gi:\
X ff=\G~:cc=\Gw:uk=\G^:ul=\Gz:\
X hb=\G'\`':vb=\Ga:ll=\Ge'
X
X To make up a new graphics map, you should first find out the range of
Xsymbols that your terminal can display. Just put your terminal in graphics
Xmode (see the 'as' and 'ae' definitions in the termcap for your terminal) and
Xsend it all the ascii character The file /projects/Ecrypt/graphics does this
Xfor terminal that use \EF and \EG to enter and exit graphics mode (vt100 and
Xh19).
X
XII. Key Map
X
X CBW uses a keymap to convert arbitrary sequences of ascii characters into
Xkeystroke commands. The information in the map comes from the shell
Xenvironment variable KEYMAP, the termcap entry for the user's terminal, and
Xfrom a compiled in string that specifies the default map (see terminal.h). The
Xshell variable overrides the information from the other sources.
X
X The termcap entry for the terminal should provide all the information
Xneeded by CBW. It should not be necessary to use the KEYMAP variable. The
Xtermcap entry can come from the environment variable TERMCAP, or from the file
X/etc/termcap based on the value of the variable TERM.
X
X The format of the key map environment variable string is the same as the
Xformat of the graphics map variable except that the first two character of the
Xvalue field are not treated specially. Each definition in the string binds a
Xkeystroke command to some sequence of ascii characters. Note that the same
Xcommand can be bound to two or more sequences. The label portion of the
Xdefinition identifies the command and the value portion gives the character
Xsequence. Table II-1 lists the label to use for each keystroke command. Many
Xof the default bindings come the termcap entry. In those cases, the label for
Xthe definition in the termcap entry is given. The command labels used in
XKEYMAP are different from the terminal capability labels used in TERMCAP.
X
X-------------------------------------------------------------------------------
X
XLABEL COMMAND
Xup Move cursor up.
Xdo Move cursor down.
Xle Move cursor left.
Xri Move cursor right.
Xre Redraw screen.
Xun Undo last guess accepted.
Xcl Clear command line.
Xws Word search (not fully implemented).
Xdf Delete current character and move forward.
Xdb Move left and delete that character.
Xpr Previous block or guess.
Xne Next block or guess.
Xac Accept guess.
Xex Execute command line or insert newline.
Xta Try all characters in this position.
Xjc Jump to command line.
X
X
X Table II-1: Command labels for key map
X
X-------------------------------------------------------------------------------
X
X Several termcap definitions are required by CBW and several others are
Xused if they are present. CBW will print a message and exit if one of the
Xrequired definitions is missing. Table II-2 list all the definitions used by
XCBW.
X
X-------------------------------------------------------------------------------
X
XLABEL USE
Xis Terminal initialization string.
Xce Erase to end of line.
Xcd Erase to end of screen.
Xcl Erase whole screen.
Xcm Cursor motion.
Xas Start graphics mode.
Xae End graphics mode.
Xso Start standout mode.
Xse End standout mode.
Xks Start send keypad escapes.
Xke End send keypad escapes.
Xk1 The f1 key.
Xk2 The f2 key.
Xk3 The f3 key.
Xk4 The f4 key.
Xku Up arrow.
Xkd Down arrow.
Xkl Left arrow.
Xkr Right arrow.
X
X
X Table II-2: TERMCAP definitions used by CBW
X
X-------------------------------------------------------------------------------
X
XIII. Command Summary
X
X
XKEYSTROKE COMMAND
X
XC-L Redraw the whole screen. As a side effect this erases the list
X of characters produced by C-T.
X
XC-X, F4 Jump to command input line.
X
XC-Q Quote. Insert the following character.
X
XC-Z Abort the current command, restore the terminal modes, suspend
X the program and return to the shell. If the program is
X restarted, the terminal will be initialized for CBW and the
X screen redrawn. The command that was active (if any) when the
X C-Z was received is aborted. Actually this command is invoked
X when CBW receives a SIGTSTP signal.
X
XC-C Restore the terminal modes and kill the CBW process. Actually
X this command is invoked when CBW receives a SIGINT signal.
X
XC-D, DEL Delete character forward, delete backward. This forces a
X permutation wiring to be removed. It can do unexpected things.
X Consider a permutation with A wired to B and P wired to
X Q. Adding a wire from B to P, then removing it with the DEL
X command does not restore the original AB and PQ wirings.
X
XC-G Undo. Backup the permutation to the state it had before the
X last contiguous sequence of keystrokes. Arrow commands
X terminate a sequence. In most cases, undo should be used
X instead of DEL or C-D. The cursor must be in either the guess
X block or the decryption block window.
X
XC-T Try-all. Display a list of the ascii characters that could be
X put in the current cursor position without conflicting with the
X existing permutation wirings. The list is sorted with the most
X likely character first (leftmost). The cursor must be in the
X decryption block window.
X
XF1, C-R Move to the previous block of 256 characters. Decryption block
X window only.
X
XF2, C-S Advance to next block of 256 characters. Decryption block
X window only.
X
XF2, C-S Goto next guess. Guess block window only.
X
XF3, C-A Accept guess, merge it into the current decryption block. This
X does not automatically advance to the next guess. Guess block
X window only.
X
XC-F, C-B Move forward and backward one character.
X
XC-D, DEL Delete one character forward or backward.
X
XF2, C-S Next-Argument. It searches for the first "%" character in the
X command line, deletes it and leaves the cursor there. This is
X used with command templates.
X
XSpace Within the first word on the command line, a space character
X invokes command completion. A completed command string is a
X template command with argument slots (marked by %) and
X suggested argument values.
X
XReturn Execute command. The cursor can be anywhere within the command
X line.
X
X
X
X-------------------------------------------------------------------------------
X
X USER COMMANDS
X
X
Xquit-program permanently
X
Xauto-trigram max_dev: % min_total_chars: % min_wire_chars: %
X
Xknitting using blocks from: % to: % Min show count: %
X
Xlookup-pattern: % in dictionary
X
Xequivalence-class guess, use accept level: % (try 2.0)
X
Xpwords-from file: % Max dev: % (try 1.0)
X
Xload-permutations
X
Xsave-permutations
X
Xclear-zee permutation
X
Xpropagate-info from: % to: % using Zee
X
Xbigram-guess level: % (2.0), min_prob: % (0.15)
X
XIV. Tutorial
X
X The following is a step by step sequence of commands to compile and
Xexercise the Crypt Breakers Workbench. It demonstrates how easily crypt files
Xcan be broken.
X
X 1. Edit stats.slice to set the name of the directory that contains the
X statistics files. Statistics for scribe documents are included with
X the source files.
X
X The stats.slice file also defines the location of the dictionary
X used by the lookup-pattern command. The default dictionary is
X /usr/dict/words. The dictionary is just a list of words, one per
X line. Case does not matter.
X
X 2. Execute 'source stats.slice' to initialize the necessary shell
X variables.
X
X 3. If there is a .slice file for your terminal type (e.g., vt100.slice,
X or h19.slice), execute source on that file. This initializes the
X graphics map and key map.
X
X 4. Print out cbw.doc, so you can read it after you have decided that
X you can't figure out how the program works.
X
X 5. Copy test3.perm and .cipher to foo.perm and foo.cipher. The .txt
X files contain the original plaintext.
X
X 6. Execute 'cbw foo'.
X
X 7. The cursor will on the command line. Use the arrow keys (or C-P,
X C-N, C-F, C-B) to move the cursor to the upper lefthand position of
X the decryption window. Try typing '@Device[Dover]'. Notice that
X most of the characters you type deduced other characters in the
X block.
X
X 8. The 'D' in 'Dover' is wrong. Using the arrow keys, position the
X cursor over the 'D' and type 'd'.
X
X 9. Advance to the position after the ']' and type C-T. A list of
X possible characters for this position will be displayed. The list
X is sorted with the most likely character on the left. Notice that
X many characters are not possible because they would deduce non-ascii
X characters elsewhere in the block, or they would conflict with
X previously accepted guesses.
X
X Try guessing tab, comma and linefeed for the character after the
X ']'. Use C-G to undo each guess. Delete and C-D do not restore the
X old state, they just erase the wiring that was deduced by a
X particular character.
X
X 10. Move the cursor down to the command line. You can use emacs cursor
X characters (C-N, C-P, C-F, C-B) or the arrow keys. Unfortunately,
X C-U does not work as in emacs. The C-X key or F4 will jump directly
X to the command line.
X
X 11. Type 'pw '. The space will cause command completion for the
X probable-word guessing command. Type F2 (or C-S) to advance to the
X first argument, and enter the file name 'mss.words'. That file
X contains a list of keywords used by the Scribe (Finalword) text
X formatter. Press F2 to advance to the second argument, which
X specifies a cut-off level for automatically accepting guesses. The
X level is the maximum number of standard deviations that the scoring
X function can be away from its expected value. Enter 1.2, and press
X return to invoke the command.
X
X 12. A partially filled in block will appear in the guessing window. To
X accept the result of this command, press F3 (or C-A).
X
X 13. Try the pword guess command again with a level of 3. To do this,
X just move to the command line, change the 1.2 to a 3, and press
X return. Again F3 accepts the guess. If some guesses look wrong
X (such as the 'F' on the second line under the '[Article]'), you can
X correct them using the editor in the decryption block window.
X
X 14. Advance to block 1 of the file by moving the cursor to the
X decryption window and pressing F2 (or C-S). F1 (or C-R) moves back
X one block, F2 moves ahead one block.
X
X 15. The second block is likely to be plain english with few scribe
X commands. Move to the command window, type C-U to erase the line
X and type 'bi ' to setup the bigram guessing command. Try an
X acceptance level of 1.0 and a minimum probability of 0.6. Type
X return to invoke the command.
X
X 16. After a short wait (~15 seconds), a partial block will appear.
X Accept the guess with the F3 key in the guessing window.
X
X 17. Try looking up a pattern in the dictionary. In the command window
X type 'look ', use F2 to advance to the pattern, and type in the
X pattern '....llit.', and press return. This will match against the
X word 'satellite' if it is in you site's dictionary.
X
X 18. One could go on like this, but let's skip ahead by loading in a
X previously saved state. Invoke the load command (it loads the file
X foo.perm, just as save dumps to foo.perm (making this command take a
X filename is a good implementation exercise)). Type C-U, 'load ',
X and return. Notice that all the work so far is replaced by the
X information in the .perm file. This can be considered a feature.
X
X 19. Use the F1 and F2 keys in the decryption window to view the blocks
X that have been solved. Notice that a fully solved block does not
X specify all the wirings of the block key (permutation). Typically
X only 105 of the 128 wires are used.
X
X 20. Lets try deducing the inter-block relationship (zee). Execute the
X clear-zee command.
X
X 21. Execute knit blocks 0 through 3 with a min show count of 20. This
X means that the program should only show you guesses that deduce 20
X or more wirings of the zee permutation. Press return to invoke this
X guessing strategy. The cursor will move to the guessing window.
X Press F2 to start the first round of guessing.
X
X The running time of the knit command is exponential in the number of
X blocks knitted, and it will run for a very long time if any of the
X blocks are decrypted incorrectly. This means that it is better to
X leave a position blank than to guess at it.
X
X 22. The program moves to block 4 and shows you the characters in block 4
X that would be deduced from block 3 given the deduced wirings of zee.
X If these look reasonable, press F3 to accept the guess, and press F2
X to try the next guess. To reject a guess, press F2 without pressing
X F3.
X
X 23. Now that part of zee is known, try propagating the settings of block
X 1 into block 0 using zee. The propagate command will do this. Also
X try propagating blocks 2, 3, and 4 to zero.
X
X Notice that the number of known wires can increase without deducing
X additional characters in the block.
X
X 24. There should be a command that propagates information between groups
X of blocks, but for now you must do this one block at a time. After
X propagating block 1 - 4 to block zero, and block zero to blocks 1 -
X 4, et cetera, try the knit command again.
X
X 25. Propagate block 4 to 5 to provide a framework to evaluate new
X guesses.
X
X 26. Knit block 0 through 4 with a minimum show level of 2. You may want
X to skip accepting guesses that do not deduce any characters. Repeat
X this process with a show level of 1.
X
X 27. The program should now know all 256 wirings of zee. Repeat the
X process of propagating information between blocks until all 128
X wires of the block zero are known.
X
X 28. Save your work with the save-permutations command (on the command
X line type 'sa ' and press return). This writes the file foo.perm.
X
X 29. Exit the program with the quit command.
X
X 30. Copy foo.perm to zeecode.perm.
X
X 31. Execute 'zeecode < foo.cipher | more '. This program reads CBW's
X save file to find the permutation for block zero and the Zee
X permutation that describes how the remaining block keys are
X generated. Using this information it decodes standard input and
X writes on standard output.
X
X 32. That's all.
X
X Table of Contents
XOverview 2
X1. Introduction to the Workbench 2
X2. Key Space Attack 2
X3. Files, Terminals and Shell Variables 2
X 3.1. Terminal compatibility 2
X4. Getting Started and Getting Out 2
X5. Commands 2
X6. Windows 4
X 6.1. Banner window 4
X 6.2. Decryption Block Label window 4
X 6.3. Decryption Block Storage window 4
X 6.4. Guess Block Label window 4
X 6.5. Guess Block Storage window 4
X 6.6. Word Lookup 4
X 6.7. User I/O window 4
X7. User Commands 4
X 7.1. quit 4
X 7.2. save-permutation 4
X 7.3. load-permutations 4
X 7.4. lookup-pattern 4
X 7.5. bigram guessing 4
X 7.6. pwords 5
X 7.7. auto-trigram guessing 5
X 7.8. knit-blocks 5
X 7.9. Clear-zee 5
X 7.10. propagate using Zee 5
X8. Known Bugs 5
XAcknowledgments 6
XI. Graphics Map 7
XII. Key Map 8
XIII. Command Summary 9
XIV. Tutorial 10
X
X List of Figures
XFigure 5-1: Sample Screen 3
X
X List of Tables
XTable I-1: Default graphic symbols 7
XTable I-2: Symbol labels for graphic map 7
XTable II-1: Command labels for key map 8
XTable II-2: TERMCAP definitions used by CBW 8
END_OF_cbw.doc
if test 51998 -ne `wc -c <cbw.doc`; then
echo shar: \"cbw.doc\" unpacked with wrong size!
fi
# end of overwriting check
fi
echo shar: End of archive 11 \(of 11\).
cp /dev/null ark11isdone
MISSING=""
for I in 1 2 3 4 5 6 7 8 9 10 11 ; do
if test ! -f ark${I}isdone ; then
MISSING="${MISSING} ${I}"
fi
done
if test "${MISSING}" = "" ; then
echo You have unpacked all 11 archives.
rm -f ark[1-9]isdone ark[1-9][0-9]isdone
else
echo You still need to unpack the following archives:
echo " " ${MISSING}
fi
## End of shell archive.
exit 0