Документация по криптоалгоритмам / DES / Cracking_DES / CH5 / readme

README FOR DES SEARCH ENGINE CONTROLLER SOFTWARE

April 23, 1998


Written 1998 by Cryptography Research (http://www.cryptography.com)
for the Electronic Frontier Foundation (EFF). Placed in the public
domain by Cryptography Research and EFF.

This is unsupported free software. Use and distribute at your own
risk. U.S. law may regulate the use and/or export of this program.
Foreign laws may also apply.



---------------------------------------------------------------------
Section 1: Compiling the Programs.

Compiling the programs should be easy. Using 32-bit Microsoft Visual
C++ for Windows compile as shown below. For Borland C++ or other
compilers, replace "cl" with the compiler name (e.g., bcc). On a 16-
bit DOS compiler with a large search array, the large memory model
(Borland's "-ml" flag) is required or the system will run out of
memory.

> cl search.c keyblock.c chipio.c des.c
> cl initsrch.c keyblock.c
> cl autoconf.c chipio.c
> cl testvec.c sim.c des.c



---------------------------------------------------------------------
Section 2: Auto-Configuring the Search Array.

The auto-configuration program is an important part of the DES
Cracker. Because there are a large number of chips in the system, it
is inevitable that a few fail. By automatically removing defective
units, it is not necessary to repair the system when failures do
occur.

The program "autoconf.exe" will automatically identify the
configuration of a search array. With the I/O port base address at
210 hex, simply run the program with the command:

> autoconf search.cfg -t

Note that the "-t" flag performs register testing (recommended if the
search system might contain defective chips that need to be avoided).
If the I/O port is at an address other than 210, specify the address.
The "-v" flag provides verbose output. For example:

> autoconf search.cfg 210 -t -v

When autoconf completes, it will print the total number of chips to
the screen and save the configuration information to the
configuration file. The configuration can be edited (e.g., with
grep) to remove defective units not caught with autoconf.

(Note that this first release does not implement search unit testing
code except for the register tests.)



---------------------------------------------------------------------
Section 3: Initializing a Search.

The search parameters have to be specified before a key can be found.
The program initsrch creates a "search context" file that contains
these search parameters and a list of the regions of keyspace that
remain to be searched.

The search parameters can either be entered into initsrch or
specified on the command line. To enter them manually, run initsrch
with no parameters:

> initsrch

The program will then prompt for the search context file. Press
enter for the default filename ("search.ctx").

Next, the program will prompt for a search mode. Five modes are
supported and are described in the following sections.

K - Known plaintext
E - ECB ASCII text
C - CBC ASCII text
B - Blaze challenge
M - Manual parameter specification


1. Known plaintext searching

This is the simplest (and most common) mode of operation. If a
complete DES plaintext/ciphertext pair is known, this mode can be
used to quickly search for the key. When prompted, enter the
plaintext in hexadecimal form (e.g., "123456789ABCDEF0") and press
enter. Next, enter the ciphertext, also in hexadecimal. The program
will then create a search context file and exit.


2. ECB ASCII text searching

If your target message is known to be ASCII text and was encrypted
using DES ECB mode, enter two different ciphertexts. The program
will create the search context file and exit. The program is
configured to include all letters ("a-z" and "A-Z"), numbers ("0-9"),
and common punctuation (ASCII zero, tab, linefeed carriage return,
space, and common punctuation (!"'(),-.^_). For other character
sets, use the manual parameter specification option.


3. CBC ASCII text searching

If your message is ASCII text and was encrypted using DES CBC mode,
this option lets you specify an initialization vector and two
ciphertext messages. The CBC mode ASCII option uses the same ASCII
text characters as ECB ASCII.


4. The Blaze challenge

Matt Blaze's DES challenge involves searching for a key such that a
repeated plaintext byte produces a repeated ciphertext byte. This
option will search for keys that meet the challenge. Simply specify
the desired repeated ciphertext byte.


5. Manual parameter specification

The manual parameter mode allows direct control over the search
parameters. The manual mode requires entering more data than the
other modes; it is often easier to pipe input from a script file,
e.g.:

> initsrch < search.scr

First, enter the plaintext vector. This is 64 hex digits long and
specifies the bytes that can appear in "valid" plaintexts. The most
significant bit of the left-hand digit specifies whether ASCII 255
can appear, and the least significant bit of the last digit specifies
whether ASCII zero can appear. For example, the plaintext vector for
the ASCII text modes is:

0000000000000000000000000000000007FFFFFFC7FFFFFE8FFF738700002601

Next, enter the initialization vector for the first DES, if any.
This will be XORed onto the first plaintext before its validity is
checked.

Next, enter the two ciphertexts (ciphertext 0 and ciphertext 1).
These may be the same or different.

Next, enter the plaintext byte mask. This sets bits that should be
ignored in the plaintext. For example, if the left-hand byte of the
plaintext is unknown or can have any value, the plaintext byte mask
would be set to 80 (hex).

Finally, enter the searchInfo byte. Bit 1 of this byte specifies
whether CBC mode should be used. If so, the first ciphertext will be
XORed onto candidate plaintexts produced by decrypting the second
ciphertext. Bit 2 of searchInfo specifies whether the extraXor
operation should be done. This operation XORs the right half of the
plaintext onto the left half before it is checked. (For the Blaze
challenge, the desired plaintext has a single byte repeated. The
extraXor operation will set the left half of the plaintext to zero if
the plaintext is good. The plaintextByteMask can then be set to 0x0F
to ignore the right half and the plaintextVector has only the bit for
ASCII zero set.)


5. The search context file

The search context file contains a header, the search parameters, and
2^24 bits corresponding to the unsearched key regions. The search
parameters are: plaintextVector (32 bytes), plaintextXorMask (8
bytes), ciphertext0 (8 bytes), ciphertext1 (8 bytes),
plaintextByteMask (1 byte), and searchInfo (1 byte). Each search
region includes 2^32 keys. The first bit (the MSB of the first key
region byte) corresponds to the keys 00000000000000 through
000000FFFFFFFF, in 56-bit notation. (To produce the 56-bit form of a
64-bit DES key, delete the eight parity bits.)



---------------------------------------------------------------------
Section 4: Running a Search.

The most common way to run a search is to type:

> search search.cfg search.ctx logfile -q

The "-q" flag requests quiet output, which prints less information to
the screen. The search.cfg file is produced by autoconf, and
search.ctx is produced by initsrch. The logfile will contain a list
of candidate keys encountered.

If a search is stopped partway through, work done in partially-
completed key regions is lost, but completed regions are noted in the
search context file. Note that a complete search will produce a
rather large amount of data in the logfile. If hard disk space is
limited, it may be desirable to stop the search occasionally (for
example, daily) to purge the logfile.



---------------------------------------------------------------------
Section 5: Porting to other platforms.

When porting to other platforms, some code changes or additions may
be required. The following may not be found on all systems:

stricmp: This is a case-insensitive strcmp found on many
compilers. If it isn't present, you can either use strcmp
(though commands will become case sensitive) or write one.

SEEK_SET: A constant (equal to zero) used to tell fseek()
to go to a fixed offset. Usually defined in stdio.h

kbhit(void): Returns true if a key has been pressed. (Used to
check for commands during searches.)

getch(void): Reads a keystroke from the keyboard.

inportb(unsigned portNum): Reads a byte from an I/O port. Used
only by chipio.c. On other platforms, inportb may need to
be emulated. (For Visual C++, inportb is implemented in
chipio.c as inline assembly language.)

outportb(int portNum, int value): Sends a byte to an I/O port.
Used only by chipio.c. On other platforms, outportb may
need to be emulated. (For Visual C++, outportb is
implemented in chipio.c as inline assembly language.)



---------------------------------------------------------------------
Section 6: Final comments

As this code goes to press, there was little opportunity for testing
and the code has not undergone any of the assurance, code review, or
testing processes we normally use. When working on the code, you
you may find a few bugs. Feedback, as always, is appreciated.

Paul Kocher, Josh Jaffe, and everyone else at Cryptography Research
would like to thank John Gilmore and the EFF for funding this unique
project, and AWT for their expert hardware work!