DP Tool Club 17/CD_ASCQ_17_101194.iso/vrac/sfs110.zip/SFS2.DOC

Text File | 1994-08-01 | 144KB | 2,475 lines

The Care and Feeding of Passwords
---------------------------------

With the inherent strength of an encryption system like the one used by SFS,
the password used for encryption is becoming more the focus of attack than the
encryption system itself.  The reason for this is that trying to guess an
encryption password is far simpler than trying to break the encryption system.

SFS allows keys of up to 100 characters in length.  These keys can contain
letters, numbers, spaces, punctuation, and most control and extended characters
except backspace (which is used for editing), escape (which is used to abort
the password entry), and carriage return or newline, which are used to signify
the end of the password.  This fact should be made use of to the fullest, with
preferred passwords being entire phrases rather than individual words (in fact
since very few words are longer than the SFS absolute minimum password length
of 10 characters, the complete set of these words can be checked in moments).
There exist programs designed to allow high-speed password cracking of standard
encryption algorithms which can, in a matter of hours (sometimes minutes, even
seconds in the case of very weak algorithms), attempt to use the contents of a
number of very large and complete dictionaries as sample passwords[1].  For
example one recent study of passwords used on Unix systems[2] found 25% of all
passwords simply by using sophisticated guessing techniques.  Of the 25% total,
nearly 21% (or around 3,000 passwords) were found within the first week using
only the spare processing power of a few low-end workstations.  368 were found
within the first few minutes.  On an average system with 50 users, the first
password could be found in under 2 minutes, with 5-15 passwords being found by
the end of the first day[3].

Virtually all passwords composed of single words can be broken with ease in
this manner, even in the case of encryption methods like the one which is used
by SFS, which has been specially designed to be resistant to this form of
attack (doing a test of all possible 10-letter passwords assuming a worst-case
situation in which the password contains lowercase letters only, can be
accomplished in 450,000 years on a fast workstation (DEC Alpha) if the attacker
knows the contents of the encrypted volume in advance - or about 4 1/2 years on
a network of 100,000 of these machines).  Of course no attacker would use this
approach, as few people will use every possible combination of 10 letter
passwords.  By using an intelligent dictionary-based cracking program, this
time can be reduced to only a few months.  Complete programs which perform this
task and libraries for incorporation into other software are already widely
available[4].  This problem is especially apparent if the encryption algorithm
used is very weak - the encryption used by the popular Pkzip archiver, for
example, can usually be broken in this manner in a few seconds on a cheap
personal computer using the standard wordlist supplied with all Unix
systems[5].

Simple modifications to passwords should not be trusted.  Capitalizing some
letters, spelling the words backwards, adding one or two digits to the end, and
so on, present only a slightly more difficult challenge to the average
password-cracker than plain unadorned passwords.  Any phrase which could be
present in any kind of list (song lyrics, movie scripts, books, plays, poetry,
famous sayings, and so on) should not be used - again, these can be easily and
automatically checked by computers.  Using foreign languages offers no extra
security, since it means an attacker merely has to switch to using
foreign-language dictionaries (or phrase lists, song lyrics, and so on).
Relying on an attacker not knowing that a foreign language is being used ("If I
use Swahili they'll never think of checking for it" - the so-called "Security
through obscurity" technique) offers no extra security, since the few extra
days or months it will take to check every known language are only a minor
inconvenience.

Probably the most difficult passwords to crack are ones comprising unusual
phrases or sentences, since instead of searching a small body of text like the
contents of a dictionary, book, or phrase list, the cracker must search a much
larger corpus of data, namely all possible phrases in the language being used.
Needless to say, the use of common phrases should be avoided, since these will
be an obvious target for crackers.

Some sample bad passwords might be:

    misconception               Found in a standard dictionary
    noitpecnocsim               Reversed standard dictionary word
    miskonseption               Simple misspelling of a standard word
    m1skon53pshun               Not-so-simple misspelling of a standard word
    MiScONcepTiON               Standard word with strange capitalization
    misconception1234           Standard word with simple numeric code appended
    3016886726                  Simple numeric code, probably a US phone number
    YKYBHTLWYS                  Simple mnemonic

In general coming up with a secure single-word password is virtually impossible
unless you have a very good memory for things like unique 20-digit numbers.

Some sample bad passphrases might be:

    What has it got in its
     pocketses?                 Found in a common book
    Ph'n-glui mgl'w naf'h
      Cthulhu R'yleh w'gah      Found in a somewhat less common book
    For yesterday the word of
      Caesar might have stood   Found in a theatrical work
    modify the characteristics
      of a directory            Found in a technical manual
    T'was brillig, and the
      slithy toves              Found in a book of poetry
    I've travelled roads that
      lead to wonder            Found in a list of music lyrics
    azetylenoszilliert in
      phaenomenaler kugelform   Found in an obscure foreign journal
    Arl be back                 Found in several films
    I don't recall              Associated with a famous person (although
                                it does make a good answer to the question
                                "What's the password?" during an
                                interrogation)

Needless to say, a passphrase should never be written down or recorded in any
other way, or communicated to anyone else.

Footnote [1]: A large collection of dictionaries suitable for this kind of
              attack can be found on black.ox.ac.uk in the `wordlists'
              directory.  These dictionaries contain, among other things, 2MB
              of Dutch words, 2MB of German words, 600KB of Italian words,
              600KB of Norwegian words, 200KB of Swedish words, 3.3MB of
              Finnish words, 1MB of Japanese words, 1.1MB of Polish words,
              700KB of assorted names, and a very large collection of assorted
              wordlists covering technical terms, jargon, the Koran, the works
              of Lewis Carrol, characters, actors, and titles from movies,
              plays, and television, Monty Python, Star Trek, US politics, US
              postal areas, the CIA world fact book, the contents of several
              large standard dictionaries and thesaurii, and common terms from
              Australian, Chinese, Danish, Dutch, English, French, German,
              Italian, Japanese, Latin, Norwegian, Polish, Russian, Spanish,
              Swedish, Yiddish, computers, literature, places, religion, and
              scientific terms.

              The black.ox.ac.uk site also contains, in the directory
              /src/security, the file cracklib25.tar.Z, a word dictionary of
              around 10MB, stored as a 6.4MB compressed tar file.

              A large dictionary of English words which also contains
              abbreviations, hyphenations, and misspelled words, is available
              from wocket.vantage.gte.com (131.131.98.182) in the
              /pub/standard_dictionary directory as dic-0594.tar, an
              uncompressed 16.1MB file, dic-0594.tar.Z, a compressed 7.6MB
              file, dic-0594.tar.gz, a Gzip'ed 5.9MB file, and dic-0594.zip, a
              Zipped 5.8MB file.  This contains around 1,520,000 entries.  In
              combination with a Markov model for the English language built
              from commonly-available texts, this wordlist provides a powerful
              tool for attacking even full passphrases.

              A Unix password dictionary is available from ftp.spc.edu as
              .unix/password-dictionary.txt.

              Grady Ward <[e-mail]> has collected very large
              collections of words, phrases, and other items suitable for
              dictionary attacks on cryptosystems.  Even the NSA has used his
              lists in their work.

Footnote [2]: Daniel Klein, "Foiling the Cracker: A Survey of, and Improvements
              to, Password Security", Software Engineering Institute, Carnegie
              Mellon University.

Footnote [3]: An improved implementation is approximately 3 times faster on an
              entry-level 386 system, 4 times faster on an entry-level 486
              system, and up to 10 times faster on a more powerful workstation
              such as a Sparcstation 10 or DEC 5000/260, meaning that the first
              password would be found in just over 10 seconds on such a
              machine.

Footnote [4]: One such program is "crack", currently at version 4.1 and
              available from black.ox.ac.uk in the directory /src/security as
              crack41.tar.Z.

Footnote [5]: Actual cryptanalysis of the algorithm, rather than just trying
              passwords, takes a little longer, usually on the order of a few
              minutes with a low-end workstation.


Other Software
--------------

There are a small number of other programs available which claim to provide
disk security of the kind provided by SFS.  However by and large these tend to
use badly or incorrectly implemented algorithms, or algorithms which are known
to offer very little security.  One such example is Norton's Diskreet, which
encrypts disks using either a fast proprietary cipher or the US Data Encryption
Standard (DES).  The fast proprietary cipher is very simple to break (it can be
done with pencil and paper), and offers protection only against a casual
browser.  Certainly anyone with any programming or puzzle-solving skills won't
be stopped for long by a system as simple as this.

The more secure DES algorithm is also available in Diskreet, but there are
quite a number of implementation errors which greatly reduce the security it
should provide.  Although accepting a password of up to 40 characters, it then
converts this to uppercase-only characters and then reduces the total size to 8
characters of which only a small portion are used for the encryption itself.
This leads to a huge reduction in the number of possible encryption keys, so
that not only are there a finite (and rather small) total number of possible
passwords, there are also a large number of equivalent keys, any of which will
decrypt a file (for example a file encrypted with the key 'xxxxxx' can be
decrypted with 'xxxxxx', 'xxxxyy', 'yyyyxx', and a large collection of other
keys, too many to list here).

These fatal flaws mean that a fast dictionary-based attack can be used to check
virtually all possible passwords in a matter of hours in a standard PC.  In
addition the CBC (cipher block chaining) encryption mode used employs a known,
fixed initialisation vector (IV) and restarts the chaining every 512 bytes,
which means that patterns in the encrypted data are not hidden by the
encryption.  Using these two implementation errors, a program can be
constructed which will examine a Diskreet-encrypted disk and produce the
password used to encrypt it (or at least one of the many, many passwords
capable of decrypting it) within moments.  In fact, for any data it encrypts,
Diskreet writes a number of constant, fixed data blocks (one of which contains
the name of the programmer who wrote the code, many others are simply runs of
zero bytes) which can be used as the basis of an attack on the encryption.
Even worse, the very weak proprietary scheme used by Diskreet gives away the
encryption key used so that if any two pieces of data are encrypted with the
same password, one with the proprietary scheme and the other with Diskreet's
DES implementation, the proprietary-encrypted data will reveal the encryption
key used for the DES-encrypted data.

These problems are in fact explicitly warned against in any of the documents
covering DES and its modes of operation, such as ISO Standards 10116 and
10126-2, US Government FIPS Publication 81, or basic texts like Denning's
"Cryptography and Data Security".  It appears that the authors of Diskreet
never bothered to read any of the standard texts on encryption to make sure
they were doing things right, or never really tested the finished version.  In
addition the Diskreet encryption code is taken from a code library provided by
another company rather than the people who sell Diskreet, with implementation
problems in both the encryption code and the rest of Diskreet.

The DES routines used in Da Vinci, a popular groupware product, are similarly
poorly implemented.  Not only is an 8-character password used directly as the
DES key, but the DES encryption method used is the electronic codebook (ECB)
mode, whose use is warned against in even the most basic cryptography texts
and, in a milder form, in various international encryption standards.  For
example, Annex A.1 of ISO 10116:1991 states "The ECB mode is in general not
recommended".  ISO 10126-2:1991 doesn't even mention ECB as being useful for
message encryption.  The combination of Da Vinci's very regular file structure
(which provides an attacker with a large amount of known data in very file),
the weak ECB encryption mode, and the extremely limited password range, makes a
precomputed dictionary attack (which involves a single lookup in a pre-set
table of plaintext-ciphertext pairs) very easy (even easier, in fact, than the
previously-discussed attack on Unix system passwords).  In fact, as ECB mode
has no pattern hiding ability whatsoever, all that is necessary is to encrypt a
common pattern (such as a string of spaces) with all possible dictionary
password values, and sort and store the result in a table.  Any password in the
dictionary can then be broken just as fast as the value can be read out of the
table.

PC Tools is another example of a software package which offers highly insecure
encryption.  The DES implementation used in this package has had the number of
rounds reduced from the normal 16 to a mere 2, making it trivial to break on
any cheap personal computer.  This very weak implementation is distributed
despite a wide body of research which documents just how insecure 2-round DES
really is[1].

Even a correctly-implemented and applied DES encryption system offers only
marginal security against a determined attacker.  It has long been rumoured
that certain government agencies and large corporations (and, no doubt,
criminal organizations) possessed specialized hardware which allowed them to
break the DES encryption.  However only in August of 1993 have complete
constructional details for such a device been published.  This device, for
which the budget version can be built for around $100,000, can find a DES key
in 3.5 hours for the somewhat more ambitious $1 million version (the budget
version takes 1 1/2 days to perform the same task). The speed of this device
scales linearly with cost, so that the time taken can be reduced to minutes or
even seconds if enough money is invested.  This is a one-off cost, and once a
DES-breaking machine of this type is built it can sit there day and night
churning out a new DES key every few minutes, hours, or days (depending on the
budget of the attacker).

In the 1980's, the East German company Robotron manufactured hundreds of
thousands of DES chips for the former Soviet Union.  This means one of two
things: Either the Soviet Union used the chips to build a DES cracker, or they
used DES to encrypt their own communications, which means that the US built
one.

The only way around the problem of fast DES crackers is to run DES more than
once over the data to be encrypted, using so-called triple DES (using DES twice
is as easy to attack as single DES, so in practice three iterations must be
used).  DES is inherently slow.  Triple DES is twice as slow[2].  A hard drive
which performs like a large-capacity floppy drive may give users a sense of
security, but won't do much for their patience.

The continued use of DES, mainly in the US, has been due more to a lack of any
replacement than to an ongoing belief in its security.  The National Bureau of
Standards (now National Institute of Standards and Technology) has only
relucatantly re-certified DES for further use every five years.  Interestingly
enough, the Australian government, which recently developed its own replacement
for DES called SENECA, now rates DES as being "inappropriate for protecting
government and privacy information" (this includes things like taxation
information and social security and other personal data).  Now that an
alternative is available, the Australian government seems unwilling to even
certify DES for information given under an "in confidence" classification,
which is a relatively low security rating.

Finally, the add-on "encryption" capabilities offered by general software
packages are usually laughable.  Various programs exist which will
automatically break the "encryption" offered by software such as Arc, Arj,
Lotus 123, Lotus Symphony, Microsoft Excel, Microsoft Word, Paradox, Pkzip 1.x,
the "improved encryption" in Pkzip 2.x, Quattro Pro, Unix crypt(1), Wordperfect
5.x and ealier, the "improved" encryption in Wordperfect 6.x, and many
others[3][4].  Indeed, these systems are often so simple to break that at least
one package which does so adds several delay loops simply to make it look as if
there were actually some work involved in the process. Although the manuals for
these programs make claims such as "If you forget the password, there is
absolutely no way to retrieve the document", the "encryption" used can often be
broken with such time-honoured tools as a piece of paper, a pencil, and a small
amount of thought.  Some programs which offer "password protection security"
don't even try to perform any encryption, but simply do a password check to
allow access to the data.  Two examples of this are Stacker and Fastback, both
of which can either have their code patched or have a few bytes of data changed
to ignore any password check before granting access to data.

Footnote [1]: A 2-round version is in fact so weak that most attackers never
              bother with it.  Biham and Shamirs "Differential Cryptanalysis of
              the Data Encryption Standard" only starts at 4 rounds, for which
              16 encrypted data blocks are needed for a chosen-plaintext
              attack.  A non-differential, ciphertext-only attack on a 3-round
              version requires 20 encrypted data blocks.  A known-plaintext
              attack requires "several" encrypted data blocks.  A 2-round
              version will be significantly weaker than the 3-round version.
              It has been reported that a university lecturer once gave his
              students 2-round DES to break as a homework exercise.

Footnote [2]: There are some clever tricks which can be used to make a triple
              DES implementation only twice as slow as single DES, rather than
              three times as slow as would be expected.

Footnote [3]: A package which will break many of these schemes is sold by
              Access Data, 125 South 1025 East, Lindon, Utah 84042, ph.
              1-800-658-5199 or 1-801-785-0363, fax [phone].  They
              provide a free demonstration disk which will decrypt files that
              have a password of 10 characters or less.  Access Data also have
              a UK distributor based in London called Key Exchange, ph.
              071-498-9005.

Footnote [4]: A number of programs (too many to list here) which will break the
              encryption of all manner of software packages are freely
              available via the internet.  For example, a WordPerfect
              encryption cracker is available from garbo.uwasa.fi in the
              directory /pc/util as wppass2.zip.

Footnote [5]: Why are you reading this footnote?  Nowhere in the text is there
              a [5] referring you to this note.  Go back to the start, and
              don't read this footnote again!


Data Security
-------------

This section presents an overview of a range of security problems which are, in
general, outside the reach of SFS.  These include relatively simple problems
such as not-quite-deleted files and general computer security, through to
sophisticated electronic monitoring and surveillance of a location in order to
recover confidential data or encryption keys.  The coverage is by no means
complete, and anyone seriously concerned about the possibility of such an
attack should consult a qualified security expert for further advice.  It
should be remembered when seeking advice that an attacker will use any
available means of compromising the security of data, and will attack areas
other than those in which the strongest defense mechanisms have been installed.
All possible means of attack should be considered, since strengthening one area
may merely make another area more appealing to an opponent.


Information Leakage

There are several ways in which information can leak from an encrypted SFS
volume onto other media.  The simplest kind is in the form of temporary files
maintained by application software and operating systems, which are usually
stored in a specific location and which, when recovered, may contain file
fragments or entire files from an encrypted volume.  This is true not only for
the traditional word processors, spreadsheets, editors, graphics packages, and
so on which create temporary files on disk in which to save data, but also for
operating systems such as OS/2, Windows NT, and Unix, which reserve a special
area of a disk to store data which is swapped in and out of memory when more
room is needed.

This information is usually deleted by the application after use, so that the
user isn't even aware that it exists.  Unfortunately "deletion" generally
consists of setting a flag which indicates that the file has been deleted,
rather than overwriting the data in any secure way.  Any information which is
"deleted" in this manner can be trivially recovered using a wide variety of
tools[1].  In the case of a swap file there is no explicit deletion as the swap
area is invisible to the user anyway. In a lightly-loaded system, data may
linger in a swap area for a considerable amount of time.

The only real solution to this is to redirect all temporary files and swap
files either to an encrypted volume or to a RAM disk whose contents will be
lost when power is removed.  Most programs allow this redirection, either as
part of the program configuration options or by setting the TMP or TEMP
environment variables to point to the encrypted volume or RAM disk.

Unfortunately moving the swap area and temporary files to an encrypted volume
results in a slowdown in speed as all data must now be encrypted.  One of the
basic premises behind swapping data to disk is that very fast disk access is
available.  By slowing down the speed of swapping, the overall speed of the
system (once swapping becomes necessary) is reduced.  However once a system
starts swapping there is a significant slowdown anyway (with or without
encryption), so the decision as to whether the swap file should be encrypted or
not is left to the individual user.

The other major form of information leakage with encrypted volumes is when
backing up encrypted data.  Currently there is no generally available secure
backup software (the few applications which offer "security" features are
ridiculously easy to circumvent), so that all data stored on an encrypted
volume will be backed up in unencrypted form.  Like the decision on where to
store temporary data and swap files, this is a tradeoff between security and
convenience.  If it were possible to back up an encrypted volume in its
encrypted form, the entire volume would have to be backed up as one solid block
every time a backup was made.  This could mean a daily five-hundred-megabyte
backup instead of only the half megabyte which has changed recently.
Incremental backups would be impossible.  Backing up or restoring individual
files would be impossible.  Any data loss or errors in the middle of a large
encrypted block could be catastrophic (in fact the encryption method used in
SFS has been carefully selected to ensure that even a single encrypted data bit
changed by an attacker will be noticeable when the data is decrypted[2]).

Since SFS volumes in their encrypted form are usually invisible to the
operating system anyway, the only way in which an encrypted volume can be
backed up is by accessing it through the SFS driver, which means the data is
stored in its unencrypted form.  This has the advantage of allowing standard
backup software and schedules to be used, and the disadvantage of making the
unencrypted data available to anyone who has access to the backups.  User
discretion is advised.

If it is absolutely essential that backups be encrypted, and the time (and
storage space) is available to back up an entire encrypted volume, then the
Rawdisk 1.1 driver, available as ftp.uni-duisburg.de:/pub/pc/misc/rawdsk11.zip,
may be used to make the entire encrypted SFS volume appear as a file on a DOS
drive which can be backed up using standard DOS backup software.  The
instructions which come with Rawdisk give details on setting the driver up to
allow non-DOS volumes to be backed up as standard DOS drives.  The SFS volume
will appear as a single enormous file RAWDISK.DAT which entirely fills the DOS
volume.

Footnote [1]: For example, more recent versions of MSDOS and DRDOS come with an
              "undelete" program which will perform this task.

Footnote [2]: This is not a serious limitation, since it will only affect
              deliberate changes in the data.  Any accidental corruption due to
              disk errors will result in the drive hardware reporting the whole
              sector the data is on as being unreadable.  If the data is
              deliberately changed, the sector will be readable without errors,
              but won't be able to be decrypted.


Eavesdropping

The simplest form of eavesdropping consists of directly overwiewing the system
on which confidential data is being processed.  The easiest defence is to
ensure that no direct line-of-sight path exists from devices such as computer
monitors and printers to any location from which an eavesdropper can view the
equipment in question.  Copying of documents and the contents of computer
monitors is generally possible at up to around 100 metres (300 feet) with
relatively unsophisticated equipment, but is technically possible at greater
distances.  The possibility of monitoring from locations such as
office-corridor windows and nearby rooms should also be considered.  This
problem is particularly acute in open-plan offices and homes.

The next simplest form of eavesdropping is remote eavesdropping, which does not
require access to the building but uses techniques for information collection
at a distance.  The techniques used include taking advantage of open windows or
other noise conveying ducts such as air conditioning and chimneys, using
long-range directional microphones, and using equipment capable of sensing
vibrations from surfaces such as windows which are modulated by sound from the
room they enclose.  By recording the sound of keystrokes when a password or
sensitive data is entered, an attacker can later recreate the password or data,
given either access to the keyboard itself or enough recorded keystrokes to
reconstruct the individual key sound patterns.  Similar attacks are possible
with some output devices such as impact printers.

Another form of eavesdropping involves the exploitation of existing equipment
such as telephones and intercoms for audio monitoring purposes.  In general any
device which handles audio signals and which can allow speech or other sounds
to be transmitted from the place of interest, which can be modified to perform
this task, or which can be used as a host to conceal a monitoring device and
provide power and possibly microphone and transmission capabilites to it (such
as, for example, a radio) can be the target for an attacker.  These devices can
include closed-circuit television systems (which can allow direct overviewing
of confidential information displayed on monitors and printers), office
communication systems such as public address systems, telephones, and intercoms
(which can either be used directly or modified to transmit sound from the
location to be monitored), radios and televisions (which can be easily adapted
to act as transmitters and which already contain power supplies, speakers (to
act as microphones), and antennae), and general electrical and electronic
equipment which can harbour a range of electronic eavesdropping devices and
feed them with their own power.

Another eavesdropping possibility is the recovery of information from hardcopy
and printing equipment.  The simplest form of this consists of searching
through discarded printouts and other rubbish for information.  Even shredding
a document offers only moderate protection against a determined enough
attacker, especially if a low-cost shredder which may perform an inadequate job
of shredding the paper is employed.  The recovery of text from the one-pass
ribbon used in high-quality impact printers is relatively simple.  Recovery of
text from multipass ribbons is also possible, albeit with somewhat more
difficulty.  The last few pages printed on a laser printer can also be
recovered from the drum used to transfer the image onto the paper.

Possibly the ultimate form of eavesdropping currently available, usually
referred to as TEMPEST (or occasionally van Eck) monitoring, consists of
monitoring the signals generated by all electrically-powered equipment.  These
signals can be radiated in the same way as standard radio and television
transmissions, or conducted along wiring or other metal work.  Some of these
signals will be related to information being processed by the equipment, and
can be easily intercepted (even at a significant distance) and used to
reconstruct the information in question.  For example, the radiation from a
typical VDU can be used to recover data with only a receiver at up to 25m (75
feet), with a TV antenna at up to 40m (120 feet), with an antenna and
amplification equipment at up to 80m (240 feet), and at even greater distances
with the use of more specialised equipment[1].  Information can also be
transmitted back through the power lines used to drive the equipment in
question, with transmission distances of up to 100m (300 feet) being possible.

TEMPEST monitoring is usually relatively expensive in resources, difficult to
mount, and unpredictable in outcome.  It is most likely to be carried out where
other methods of eavesdropping are impractical and where general security
measures are effective in stopping monitoring.  However, once in place, the
amount of information available through this form of eavesdropping is immense.
In general it allows the almost complete recovery of all data being processed
by a certain device such as a monitor or printer, almost undetectably, and over
a long period of time.  Protection against TEMPEST monitoring is difficult and
expensive, and is best left to computer security experts[2][3].

However, some simple measures are still possible, such as paying attention to
the orientation of VDU's (most of the signal radiated from a VDU is towards the
sides, with very little being emitted to the front and rear), chosing equipment
which already meets standards for low emissions (for example in the US the
"quietest" standard for computers and peripherals is know as the FCC Class B
standard), using well-shielded cable for all systems interconnections
(unshielded cable such as ribbon cable acts as an antenna for broadcasting
computer signals), using high-quality power line filters which block signals
into the high radio frequency range, and other methods generally used to reduce
or eliminate EMI (electromagnetic interference) from electronic equipment.

Footnote [1]: These figures are taken from "Schutzmassnahmen Gegen
              Kompromittierende Elektromagnetische Emissionen von
              Bildschirmsichtgeraeten", Erhard Moeller and Lutz Bernstein,
              Labor fuer Nachrichtentechnik, Fachhochschule Aachen.

Footnote [2]: TEMPEST informatiom and shielding measures for protection against
              TEMPEST monitoring are specified in standards like "Tempest
              Fundamentals", NSA-82-89, NACSIM 5000, National Security Agency,
              February 1, 1982, "Tempest Countermeasures for Facilities Within
              the United States", National COMSEC Instruction, NACSI 5004,
              January 1984, "Tempest Countermeasures for Facilities Outside the
              United States", National COMSEC Instruction, NACSI 5005, January
              1985, and MIL-STD 285 and 461B.  Unfortunately these
              specifications have been classified by the organisations who are
              most likely to make use of TEMPEST eavesdropping, and are not
              available to the public.

Footnote [3]: A computer centre in Moscow had all its windows shielded with
              reflective aluminium film, which was supposed to provide enough
              protection to stop most forms of TEMPEST eavesdropping.  The
              technique seems to have worked, because a KGB monitoring van
              parked outside apparently didn't notice the fact that the
              equipment had been diverted to printing out Strugatsky's novels.


Trojan Horses

It may be possible for an attacker to replace the SFS software with a copy
which seems to be identical but which has major weaknesses in it which make an
attack much easier, for example by using only a few characters of the password
to encrypt the disk.  The least likely target is mksfs, since changing the way
this operates would require a similar change to mountsfs and the SFS driver
which would be easily detectable by comparing them with and independant,
original copy.  Since a changed mksfs would require the long-term use of a
similarly changed mountsfs and driver, the changes of detection are greatly
increased.

A much more subtle attack involves changing mountsfs.  By substituting a
version which saves the user's password or encryption key to an unused portion
of the disk and then replaces itself with an unmodified, original copy, an
attacker can return at their leisure and read the password or key off the disk,
with the user none the wiser that their encryption key has been compromised.
The SFS driver may be modified to do this as well, although the task is slighly
more difficult than changing mountsfs.

Detecting this type of attack is very difficult, since although it is possible
to use security software which detects changes, this itself might be modified
to give a false reading.  Software which checks the checking software may in
turn be modified, and so on ad infinitum.  In general someone who is determined
enough can plant an undetectable trojan[1], although precautions like using
modification-detection programs, keeping physically separate copies of the SFS
software, and occasionally checking the installed versions against other,
original copies, may help reduce the risk somewhat.  The eventual creation of a
hardware SFS encryption card will reduce the risk further, although it is still
possible for an attacker to substitute their own fake encryption card.

Another possibility is the creation of a program unrelated to SFS which
monitors the BIOS character write routines for the printing of the password
prompt, or video RAM for the appearance of the prompt, or the BIOS keyboard
handler, or any number of other possibilities, and then reads the password as
it is typed in[2].  This is a generic attack against all types of encryption
software, and doesn't rely on a compromised copy of the software itself.

The stealth features in SFS are one way of making this kind of monitoring much
more difficult, and are explained in more detail in the section "Security
Analysis" below.  However the only really failsafe way to defeat this kind of
attack is to use custom hardware which performs its task before any user
software has time to run, such as the hardware SFS version currently under
development.

Footnote [1]: An attacker could employ, for example, what David Farber has
              described as "supplemental functionality in the keyboard driver".

Footnote [2]: One program which performs this task is Phantom 2, available from
              wuarchive.wustl.edu in the directory /pub/msdos/keyboard as
              ptm228.zip, or from P2 Enterprises, P.O. Box 25, Ben Lomond,
              California 95005-0025.  This program not only allows the
              recording of all keystrokes but provides timing information down
              to fractions of a second, allowing for detailed typing pattern
              analysis by an attacker.

              Another keystroke recorder is Encore, also available from
              wuarchive.wustl.edu in the directory /pub/msdos/keyboard as
              encore.zip.


Dangers of Encryption

The use of very secure encryption is not without its downsides.  Making the
data completely inaccessible to anyone but the holder of the correct password
can be hazardous if the data being protected consists of essential information
such as the business records for a company which are needed in its day-to-day
operation.  If the holder of the encryption password is killed in an accident
(or even just rendered unconscious for a time), the potential complete loss of
all business records is a serious concern.

Another problem is the question of who the holder of the password(s) should be.
If the system administrator at a particular site routinely encrypts all the
data held there for security purposes, then later access to the entire
encrypted dataset is dependant on the administrator, who may forget the
password, or die suddenly, or move on to another job and have little incentive
to inform their previous employer of the encryption password (for example if
they were fired from the previous job).  Although there are (as yet) no known
cases of this happening, it could occur that the ex-administrator has forgotten
the password used at his previous place of employment and might require a
small, five-figure consideration to help jog his memory.  The difficulty in
prosecuting such a case would be rather high, as proving that the encryption
system wasn't really installed in good faith by the well-intentioned
administrator to protect the company data and that the password wasn't
genuinely forgotten would be well nigh impossible.


Politics
--------

Many governments throughout the world have an unofficial policy on cryptography
which is to reserve all knowledge and use of encryption to the government in
general and the elite in particular.  This means that encryption is to be used
firstly (in the form of restrictions on its use) for intelligence-gathering,
and secondly for protecting the secret communications of the government.
The government therefore uses encryption to protect its own dealings, but
denies its citizens the right to use it to protect their own privacy, and
denies companies the right to use it to protect their business data.  Only a
very small number of countries have laws guaranteeing citizens' rights to use
encryption[1].

This policy is enforced in many ways.  In the US it is mainly through the use
of the ITAR, the International Traffic in Arms Regulations, a law which was
passed without public debate during the second world war.  This defines all
encryption material (hardware and software) as "munitions", subject to special
governmental control.  France also classifies encryption devices as
munitions[2].  These "munitions" in fact have no violent use beyond perhaps
beating someone to death with a box of disks.  Their only possible use is to
protect personal privacy and the privacy of business data.

In limiting the use (and export) of encryption technology[3], the US (and many
other countries which follow the lead of the US) are not only denying their
citizens the means to ensure the privacy of personal information stored on
computer, they are also placing businesses at risk.  With no easy way to
protect their data, companies are losing billions of dollars a year to
industrial espionage which even a simple measure like SFS would help to reduce.
Some real-life examples of what the lack of secure encryption can do are:

    - The head of the French DGSE (Direction Generale de la Securite
      Exterieure) secret service has publicly boasted that his organisation,
      through industrial espionage, helped French companies acquire over a
      billion dollars worth of business deals from foreign competitors
      [4][5][6].

    - The book "Friendly Spies" by Peter Schweitzer, published by Atlantic
      Monthly Press, gives many accounts about covert intelligence operations
      directed against US corporations by cold war allies, with foreign
      governments conspiring with foreign companies to steal US technology and
      economic secrets[7].

    - A US company was being consistently underbid by a Japanese competitor
      which was intercepting their electronic traffic.  When they started
      encrypting their messages, the underbidding stopped.  A few days later
      they were requested by the US government to stop using encryption in
      their traffic[8].

    - A New Zealand computer dealer acquired 90 used disks which turned out to
      contain sensitive financial records from a large bank.  The evening after
      he turned them over to the bank (for a $15,000 cash "finders fee") he was
      killed in a road accident.  The finders fee was never recovered[9].

      Despite this major security problem, the bank wouldn't learn from their
      mistakes.  A few weeks later a large-capacity networked disk drive
      originally used by them was supplied to another company as a supposedly
      "new" replacement for a drive which had died.  This drive was found to
      contain the complete financial records from one of their branches.  Not
      wanting to be scraped off the side of the road one night, the system
      manager decided to erase the contents of the drive[10].

      It isn't known how many more of their confidential financial records this
      bank has handed out to the public over the years.

    - The New Zealand Securities Commission accidentally left a number of
      sensitive files on the hard drive of one of a group of machines which was
      later sold at auction for $100.  These files were stored without any
      security measures, and related to Securities Commission and Serious Fraud
      Office investigations.  At last report, the files had still not been
      recovered[11].

    - The book "By Way of Deception" by Victor Ostrovsky and Claire Hoy,
      published by St. Martins Press, New York, in 1990 (ISBN 0-312-05613-3),
      reports in Appendix I that Mossad's computer services routinely monitor
      VISA, AMEX, and Diner's Club transactions, as well as police computer
      traffic.

In the latter case the lack of encryption not only had the potential to cause
serious financial harm to the bank involved but resulted in the death of the
main player.  The use of a program like SFS would have made the contents of the
disks unreadable to anyone but the bank.

In 1991 the US Justice Department tried to introduce legislation that would
require all US digital communications systems to be reengineered (at enormous
cost) to support monitoring of message traffic by the FBI.  This measure was
never passed into law.  The next year the FBI tried to introduce a similar
measure, but could find no-one willing to back the bill.  In 1993, yet another
attmempt was made, which is currently being fought by an unusual coalition of
civil libertarians, computer users and companies, and communications providers.
A poll carried out by Time/CNN in March 1994 indicated that 2/3 of Americans
were opposed to the legislation[12].

In April 1993, the US government announced a piece of hardware called the
Clipper Chip.  They proposed that this device, whose details are classified and
which contains self-destruct mechanisms which are activated if attempts are
made to examine it too closely, be built into all telephones.  Each chip has a
special serial number which identifies all communications carried out with that
phone.  At the beginning of each transmission, telephones equipped with a
Clipper Chip negotiate a connection which involves sending identifying
information across the phone network, and setting up a common key to use for
encrypting the conversation.

Built into this setup is a special back door which allows the government, and
anyone who works for the government, and anyone who has a friend who works for
the government, and anyone with enough money or force to bribe or coerce the
aforementioned people, to monitor the conversation[13].  The job is made much
easier by the extra identification information which the Clipper Chip attaches
to the data stream.  The Clipper Chip allows monitoring on a scale even George
Orwell couldn't have imagined when he wrote his novel "1984"[14].  The Time/CNN
poll mentioned above found that 80% of Americans were opposed to the Clipper
Chip[12].

A somewhat less blatant attempt to bypass communications privacy is gradually
appearing in the rest of the world.  The GSM digital telephone system uses a
special encryption algorithm called A5X which is a modified form of a stronger
system called A5.  A5X exists solely as a deliberately crippled A5, and is
relatively easy to bypass for electronic monitoring purposes.  Although the
details of A5 are classified "for national security purposes"[15], various
sources have commented that even the original unmodified A5 probably provides
only limited security against a determined attack, and the actual
implementation exhibits some fundamental flaws (such as a 3-hour key rollover)
which can greatly aid an attacker[16][17].

It is against this worrying background that SFS was created.  Right from the
start, the idea behind SFS was to provide the strongest possible cryptographic
security.  No compromises were made, there are no back doors or weaknesses
designed into the system, nor will there ever be the deliberate crippling of
the system or undermining of its integrity which some organizations would like.
The algorithms and methods used in SFS have been selected specifically for
their acknowledged strength and general acceptance by the worldwide
cryptographic community, and conform to a wide variety of national and
international standards for secure encryption.  As new algorithms and
cryptographic processes appear, SFS will be updated to always provide the best
possible security available.

Footnote [1]: One of these is Japan.  Article 21 of the Japanese Consitution
              states:  "Freedom of assembly and association as well as speech,
              press, and all other forms of expression are guaranteed.  No
              censorship shall be maintained, nor shall the secrecy of any
              means of communication be violated".

Footnote [2]: The "decret du 18 avril 1939" defines 8 categories of arms and
              munitions from the most dangerous (1st category) to the least
              dangerous (8th category).  The "decret 73-364 du 12 mars 1973"
              specifies that encryption equipment belongs to the second
              category.  Any usage of such equipment requires authorization
              from the Prime Minister.  The "decret 86-250 du 18 fev 1986"
              extends the definition of encryption equipment to include
              software.  It specifies that each request for authorization for
              business or private usage of the equipment must be sent to the
              Minister of Telecommunications.  The request must include a
              complete and detailed description of the "cryptologic process",
              and if this is materially possible, of two copies of the
              envisaged equipment (see also Footnote 6).  The "loi 90-1170 du
              29 decembre 1990" states that export or use of encryption
              equipment must be previously declared when used only for
              authentication, and previously authorized by the Prime Minister
              in all other cases, with penalties of fines of up to 500 000F and
              three months in jail.  Import of encryption equipment (but not
              encrypted data) is prohibited by the "decret du 18 avril 1939",
              article 11.  However the "loi du 29 dec 1990" only restricts use
              or export, not import, of encryption equipment.  There are no
              restrictions on the import of encrypted data.

              However these laws appear not to be enforced, with encryption
              software being freely imported, exported, available, and used in
              France.

Footnote [3]: The reasoning behind this, as stated by the Permanent Select
              Committee on Intelligence in its commentary of 16 June 1994 on
              the HR.3937 Omnibus Export Administration Act is that "the
              intelligence community's cryptologic success depends in part on
              controlling the use of encryption [...] controlling the
              dissemination of sophisticated encryption has been and will
              continue to be critical to those successes [of the US
              intelligence community] and US national security interests".

Footnote [4]  This was reported by cryptographer Martin Hellman at the 1993 RSA
              Data Security conference on 14-15 January 1993.

Footnote [5]  Some quotes from FBI Director Louis Freeh from a talk given to
              the Executives' Club of Chicago on 17 March 1994:

              "A nation's power is increasingly measured by economic prosperity
               at home and competitiveness abroad.  And in some ways, the
               United States is a sitting duck for countries and individuals
               who want to take a short cut to power".

               [At least 20 nations are] "actively engaged in economic
               espionage".

              "This kind of information [cost and price structure, research and
               development results, marketing plans, bids and customer lists]
               can be intercepted from fax and satellite communications.  It
               can be monitored from cellular and microwave telephone links.
               It can be retrieved from inadequately protected computer
               systems".

Footnote [6]: "Powerful computers scan telephone, fax, and computer data
               traffic for information from certain sources, to certain
               destinations, or containing certain keywords, and store any
               interesting communications for later analysys.  The fear that
               such monitoring stations will, after the end of the cold war, be
               used for industrial espionage, has been expressed by DP managers
               and tacitly confirmed by US security agencies" - Markt und
               Technik, 18/94, page 49.

Footnote [7]: "France and Germany and many other countries require US companies
               to `register' the encryption key for reasons of national
               security.  All of the American transmissions are monitored and
               the data is passed on to the local competitors.  Companies like
               IBM finally began to routinely transmit false information to
               their French subsidiary just to thwart the French Secret Service
               and by transitive property of economic nationalism, French
               computer companies" - RISKS-Forum Digest, 22 February 1993,
               Volume 14, Issue 34

Footnote [8]: Private communications from one of the people involved.

Footnote [9]: This event received nationwide TV, radio, and newspaper coverage
              at the time.  For example, any New Zealand paper published on 7
              September 1992 should provide more information.

Footnote [10]: Private communications from the system manager involved.

Footnote [11]: This event received nationwide TV, radio, and newspaper coverage
               at the time.  Most New Zealand papers published on 13 August
               1994 contain coverage of the story.

Footnote [12]: "In a Time/CNN poll of 1,000 Americans conducted last week by
                Yankelovich Partners, two thirds said it was more important to
                protect the privacy of phone calls than to preserve the ability
                of police to conduct wiretaps.  When informed about the Clipper
                Chip, 80% said they opposed it" - Philip Elmer-Dewitt, "Who
                Should Keep the Keys", TIME, 14 March 1994.

Footnote [13]: In June 1994, an AT&T researcher discovered a means of bypassing
               this monitoring using about 28 minutes of computation time on
               easily-available mass-market Tessera cards.  By precomputing the
               values or employing many such devices running in parallel, the
               time can be reduced to virtually nothing.  This attack also
               opened up a number of other interesting possibilities for
               generally bypassing many of the perceived undesirable "features"
               of Clipper.

Footnote [14]: It has been claimed that the Clipper proposal is an example of
               the government servicing the people in the sense of the term
               used in the sentence "The farmer got a bull to service his
               cows".

Footnote [15]: In June 1994, the statement that A5 was too strong to disclose
               was suddenly changed so that it now became too weak to disclose,
               and that discussing the details might harm export sales.  This
               is an interesting contrast to the position taken in 1993 that
               sales to the Middle East might end up providing A5-capable
               equipment to the likes of Saddam Hussein.  Apparently there was
               a major debate among the NATO signal agencies in the 1980's over
               whether the GSM encryption should be strong or weak, with the
               weak encryption side eventually winning.

Footnote [16]: It has been reported that GCHQ, the UK intelligence agency which
               requested the A5X changes, regards as "strong encryption" (and
               therefore not suitable for use by the public) anything which
               can't be broken in real time.

Footnote [17]: UK cryptographer Ross Anderson has charecterised A5 as being
               "not much good".  A simple brute-force attack which searches all
               2^40 key combinations will break the system in about a week on a
               standard PC, with much faster attacks being possible using
               either better algorithms, custom hardware, or both.
               Interestingly, the low upper limit on the number of possible
               keys would also seem to meet the US government requirements for
               weak exportable encryption.

               Attacks faster than the basic brute-force one are also possible,
               and one such attack was to be presented by Dr Simon Shepherd at
               an IEE colloquium in London on 3rd June 1994.  However the talk
               was canceled at the last minute by GCHQ.


An Introduction to Encryption Systems
-------------------------------------

For space reasons the following introduction to encryption systems is very
brief.  Anyone requiring more in-depth coverage is urged to consult the texts
mentioned in the references at the end of this document.

Encryption algorithms (ciphers) are generally one of two types, block ciphers
and stream ciphers.  A block cipher takes a block of plaintext and converts the
entire block into ciphertext.  A stream cipher takes a single bit or byte of
plaintext at a time and converts it into ciphertext.  There also exist means of
converting block ciphers to stream ciphers, and vice versa.  Usually a stream
cipher is preferred, as it doesn't require data to be quantised to the block
size of the cipher in use.  Unfortunately, stream ciphers, although more
convenient, are usually harder to get right than block ciphers.  Many practical
stream ciphers are in fact simply block ciphers pretending to be stream
ciphers.

Virtually all good conventional-key ciphers are so-called product ciphers, in
which several (relatively) weak transformations such as substitution,
transposition, modular addition/multiplication, and linear transformation are
iterated over a piece of data, gaining more and more strength with each
iteration (usually referred to as a round).  These types of ciphers have been
extensively studied and are reasonably well understood.  The following table
compares the main parameters of several product ciphers.  Lucifer is the
immediate precursor to the US Data Encryption Standard (DES).  Loki is a
proposed alternative to DES.  FEAL is a fast block cipher designed in Japan.
IDEA is a relatively new Swiss block cipher which has been proposed as a
successor to DES and which has (so far) proven more resistant to attack then
DES.  MDC/SHS is a cipher based on the SHS one-way hash function (more on this
later).

   +-----------+------------+----------+-----------+---------------+
   |  Cipher   | Block size | Key size | Number of | Complexity of |
   |           |            |  (bits)  |   rounds  |  Best Attack  |
   +-----------+------------+----------+-----------+---------------+
   |  Lucifer  |    128     |    128   |     16    |     2^21      |
   |    DES    |     64     |     56   |     16    |     2^43      |
   |  Loki91   |     64     |     64   |     16    |     2^48      |
   |  FEAL-8   |     64     |    128   |      8    |    10,000     |
   |   IDEA    |     64     |    128   |      8    |     2^128     |
   |  MDC/SHS  |    160     |    512   |     80    |     2^512     |
   +-----------+------------+----------+-----------+---------------+

The complexity of the best known attack is the number of operations necessary
to allow the cipher to be broken.  Note how the block size, key size, and
number of rounds don't necessarily give a good indication of how secure the
algorithm itself is.  Lucifer, although it has twice the block size and over
twice the key size of DES, is rather simple to break (the key size of DES is
discussed later on in the section on insecurities).  DES is the result of
several years of work on improvements to Lucifer.  FEAL has been continually
changed every year or so when the previous version was broken.  Due to this,
current versions are treated with some scepticism.  Both IDEA and MDC have so
far resisted all forms of attack, although recently a class of weak keys have
been discovered in IDEA (and a simple change in the algorithm will eliminate
these weak keys).  Note that in the case of the last two algorithms the given
complexity is for a brute-force attack (explained below), which is the most
pessimistic kind possible.  There may be much better attacks available,
although if anyone knows of any they're not saying anything.  Of the algorithms
listed above, DES has been attacked the hardest, and IDEA and MDC the least,
which may go some way toward explaining the fact that brute force is the best
known attack.

There are a large number of modes of operation in which these block ciphers can
be used.  The simplest is the electronic codebook (ECB) mode, in which the data
to be encrypted is broken up into seperate subblocks which correspond to the
size of the block cipher being used, and each subblock is encrypted
individually.  Unfortunately ECB has a number of weaknesses (some of which are
outlined below), and should never be used in a well-designed cryptosystem.
Using P[] to denote a plaintext block, C[] to denote a ciphertext block, e() to
denote encryption, d() to denote decryption, and ^ for the exclusive-or
operation, ECB mode encryption can be given as:

    C[ n ] = e( P[ n ] )

with decryption being:

    P[ n ] = d( C[ n ] )

A better encryption mode is cipher block chaining (CBC), in which the first
data subblock is exclusive-ored with an initialization vector (IV) and then
encrypted.  The resulting ciphertext is exclusive-ored with the next data
subblock, and the result encrypted.  This process is repeated until all the
data has been encrypted.  Because the ciphertext form of each subblock is a
function of the IV and all preceding subblocks, many of the problems inherent
in the ECB encryption mode are avoided.  CBC-mode encryption is:

    C[ 1 ] = e( P[ 1 ] ^ IV )
    C[ n ] = e( P[ n ] ^ C[ n-1 ] )

and decryption is:

    P[ 1 ] = d( C[ 1 ] ) ^ IV
    P[ n ] = d( C[ n ] ) ^ C[ n-1 ]

Another encryption mode is cipher feedback (CFB), in which the IV is encrypted
and then exclusive-ored with the first data subblock to provide the ciphertext.
The resulting ciphertext is then encrypted and exclusive-ored with the next
data subblock to provide the next ciphertext block.  This process is repeated
until all the data has been encrypted.  Because the ciphertext form of each
subblock is a function of the IV and all preceding subblocks (as is also the
case for CBC-mode encryption), many of the problems inherent in the ECB
encryption mode are avoided.  CFB-mode encryption is:

    C[ 1 ] = P[ 1 ] ^ e( IV )
    C[ n ] = P[ n ] ^ e( C[ n-1 ] )

and decryption is:

    P[ 1 ] = C[ 1 ] ^ e( IV )
    P[ n ] = C[ n ] ^ e( C[ n-1 ] )

There are several other modes of operation which are not covered here.  More
details can be found in the texts given in the references.

One point worth noting is that by using a different IV for each message in CBC
and CFB mode, the ciphertext will be different each time, even if the same
piece of data is encrypted with the same key.  This can't be done in ECB mode,
and is one of its many weaknesses.

There are several standard types of attack which can be performed on a
cryptosystem.  The most restricted of these is a ciphertext-only attack, in
which the contents of the message are unknown.  This kind of attack virtually
never occurs, as there is always some regularity or known data in the message
which can be exploited by an attacker.

This leads to the next kind of attack, the known-plaintext attack.  In this
case some (or all) of the plaintext of the message is known.  This type of
attack is fairly easy to mount, since most data consists of well-known,
fixed-format messages containing standard headers, a fixed layout, or data
conforming to a certain probability distribution such as ASCII text.

Finally, in a chosen-plaintext attack the attacker is able to select plaintext
and obtain the corresponding ciphertext.  This attack is also moderately easy
to mount, since it simply involves fooling the victim into transmitting a
message or encrypting a piece of data chosen by the attacker.  This kind of
attack was used to help break the Japanese "Purple" cipher during WWII by
including in a news release a certain piece of information which it was known
the Japanese would encrypt and transmit to their superiors.

However attacks of this kind are usually entirely unnecessary.  Too many
cryptosystems in everyday use today are very easy to break, either because the
algorithms themselves are weak, because the implementations are incorrect, or
because the way they are used is incorrect.  Often amateurs think they can
design secure systems, and are not aware of what an expert cryptanalyst could
do.  Sometimes there is insufficient motivation for anybody to invest the work
needed to produce a secure system.  Many implementations contain flaws which
aren't immediately obvious to a non-expert.  Some of the possible problems
include:

- Use of easily-searched keyspaces.  Some algorithms depend for their security
  on the fact that a search of all possible encryption keys (a so-called brute
  force attack) would take too long to be practical.  Or at least, it took too
  long to be practical when the algorithm was designed.  The Unix password
  encryption algorithm is a prime example of this.  The DES key space is
  another example.  Recent research has indicated that the DES was not in fact
  weakened by having only 56 bits of key material (as has often been claimed),
  since the inherent strength of the algorithm itself only provides this many
  bits of security (that is, that increasing the key size would have no effect
  since other attacks which don't involve knowing the key can be used to break
  the encryption in far less than 2^56 operations).  The encryption used in the
  Pkzip archiver can usually be broken automatically in less time than it takes
  to type the password in for authorized access to the data since, although it
  allows longer keys than DES, it makes the check for valid decryption keys
  exceedingly easy for an attacker.

- Use of insecure algorithms designed by amateurs.  This covers the algorithms
  used in the majority of commercial database, spreadsheet, and wordprocessing
  programs such as Lotus 123, Lotus Symphony, Microsoft Excel, Microsoft Word,
  Paradox, Quattro Pro, WordPerfect, and many others.  These systems are so
  simple to break that the author of at least one package which does so added
  several delay loops to his code simply to make it look as if there was
  actually some work involved.

- Use of insecure algorithms designed by experts.  An example is the standard
  Unix crypt command, which is an implementation of a rotor machine much like
  the German Enigma cipher which was broken during WWII.  There is a program
  called cbw (for `crypt breakers workbench') which can automatically decrypt
  data encrypted with crypt[1].  After the war, the US government even sold
  Enigma cipher machines to third-world governments without telling them that
  they knew how to break this form of encryption.

- Use of incorrectly-implemented algorithms.  Some encryption programs use the
  DES algorithm, which consists of a series of complicated and arbitrary-
  seeming bit transformations controlled by complex lookup tables.  These
  transformations and tables are very easy to get wrong.

  A well-known fact about the DES algorithm is that even the slightest
  deviation from the correct implementation significantly weakens the algorithm
  itself.  In other words any implementation which doesn't conform 100% to the
  standard may encrypt and decrypt data perfectly, but is in practice rather
  easier to break than the real thing.

  The US National Bureau of Standards (now the National Institute of Standards
  and Technology) provides a reference standard for DES encryption.  A
  disappointingly large number of commercial implementations fail this test.

- Use of badly-implemented algorithms.  This is another problem which besets
  many DES implementations.  DES can be used in several modes of operation,
  some of them better than others.  The simplest of these is the Electronic
  Codebook (ECB) mode, in which a block of data is broken up into seperate
  subblocks which correspond to the unit of data which DES can encrypt or
  decrypt in one operation, and each subblock is then encrypted seperately.

  There also exist other modes such as CBC in which one block of encrypted data
  is chained to the next (such that the ciphertext block n depends not only on
  the corresponding plaintext but also on all preceding ciphertext blocks
  0..n-1), and CFB, which is a means of converting a block cipher to a stream
  cipher with similar chaining properties.

  There are several forms of attack which can be used when an encrypted message
  consists of a large number of completely independant message blocks.  It is
  often possible to identify by inspection repeated blocks of data, which may
  correspond to patterns like long strings of spaces in text.  This can be used
  as the basis for a known-plaintext attack.

  ECB mode is also open to so-called message modification attacks.  Lets assume
  that Bob asks his bank to deposit $10,000 in account number 12-3456-789012-3.
  The bank encrypts the message `Deposit $10,000 in account number
  12-3456-789012-3' and sends it to its central office.  Encrypted in ECB mode
  this looks as follows:

    E( Deposit $10,000 in acct. number 12-3456-789012-3 )

  Bob intercepts this message, and records it.  The encrypted message looks as
  follows:

    H+2nx/GHEKgvldSbqGQHbrUfotYFtUk6gS4CpMIuH7e2MPZCe

  Later on in the day, he intercepts the following a message:

    H+2nx/GHEKgvldSbqGQHbrUfotYFtUk61Pts2LtOHa8oaNWpj

  Since each block of text is completely independant of any surrounding block,
  he can simply insert the blocks corresponding to his account number:

    ................................gS4CpMIuH7e2MPZCe

  in place of the existing blocks, and thus alter the encrypted data without
  any knowledge of the encryption key used.  Bob has since gone on to early
  retirement in his new Hawaiian villa.

  ECB mode, and the more secure modes such as CBC and CFB are described in
  several standards.  Some of these standards make a reference to the
  insecurity of ECB mode, and recommend the use of the stronger CBC or CFB
  modes.  Usually implementors stop reading at the section on ECB, with the
  result being that many commercial packages which use DES and which do manage
  to get it correct end up using it in ECB mode.

- Protocol errors.  Even if a more secure encryption mode such as CBC or CFB
  mode is used, there can still be problems.  If a standard message format
  (such as the one shown above) is used, modification is still possible, except
  that now instead of changing individual parts of a message the entire message
  must be altered, since each piece of data is dependant on all previous parts.
  This can be avoided by prepending a random initialisation vector (IV) to each
  message, which propagates through the message itself to generate a completely
  different ciphertext each time the same message is encrypted.  The use of the
  salt in Unix password encryption is an example of an IV, although the range
  of only 4096 values is too small to provide real security.

In some ways, cryptography is like pharmaceuticals.  Its integrity is
important.  Bad penicillin looks just the same as good penicillin.  Determining
whether most software is correct or not is simple - just look at the output.
However the ciphertext produced by a weak encryption algorithm looks no
different from the ciphertext produced by a strong algorithm.... until an
opponent starts using your supposedly secure data against you, or you find your
money transfers are ending up in an account somewhere in Switzerland, or
financing Hawaiian villas.

Footnote [1]: Available from black.ox.ac.uk in the directory /src/security as
              cbw.tar.Z.


Security Analysis
-----------------

This section attempts to analyse some of the possible failure modes of SFS and
indicate which strategies have been used to minimise problems.


Incorrect Encryption Algorithm Implementations

When implementing something as complex as most encryption algorithms, it is
very simple to make a minor mistake which greatly weakens the implementation.
It is a well-known fact that making even the smallest change to the DES
algorithm reduces its strength considerably.  There is a body of test data
available as US National Bureau of Standards (NBS) special publication 500-20
which can be used to validate DES implementations.  Unfortunately the
programmers who produce many commercial DES implementations either don't know
it exists or have never bothered using it to verify their code (see the section
"Other Software" above), leading to the distribution of programs which perform
some sort of encryption which is probably quite close to DES but which
nevertheless has none of the security of the real DES.

In order to avoid this problem, the SHS code used in SFS has a self-test
feature which can be used to test conformance with the data given in Federal
Information Processing Standards (FIPS) publication 180 and ANSI X9.30 part 2,
which are the specifications for the SHS algorithm[1].  This self-test can be
invoked in the mksfs program by giving it the option `-t' for `test':

    mksfs -t

mountsfs and the SFS driver itself use exactly the same code, so testing it in
mksfs is enough to ensure correctness of the other two programs.  The following
tests can take a minute or so to run to completion.

The self-test, when run, produces the following output:

  Running SHS test 1 ... passed, result=0164B8A914CD2A5E74C4F7FF082C4D97F1EDF880
  Running SHS test 2 ... passed, result=D2516EE1ACFA5BAF33DFC1C471E438449EF134C8
  Running SHS test 3 ... passed, result=3232AFFA48628A26653B5AAA44541FD90D690603

The test values can be compared for correctness with the values given in
Appendix 1 of the FIPS publication.  If any of the tests fail, mksfs will exit
with an error message.  Otherwise it will perform a speed test and display a
message along the lines of:

  Testing speed for 10MB data... done.  Time = 31 seconds, 323 kbytes/second

  All SHS tests passed

Note that the speed given in this test is only vaguely representative of the
actual speed, as the test code used slows the implementation down somewhat.  In
practice the overall speed should be higher than the figure given, while the
actual disk encryption speed will be lower due to the extra overhead of disk
reading and writing.

Footnote [1]: The FIPS 180 publication is available from the National Technical
              Information Service, Springfield, Virginia 22161, for $22.50 + $3
              shipping and handling within the US.  NTIS will take telephone
              orders on [phone] (8:30 AM to 5:30 PM Eastern Time),
              fax [phone].  For assistance, call [phone].


Weak passwords

Despite the best efforts of security specialists to educate users about the
need to chose good keys, people persist in using very weak passwords to protect
critical data.  SFS attempts to ameliorate this problem by forcing a minimum
key length of 10 characters and making a few simple checks for insecure
passwords such as single words (since the number of words of length 10 or more
characters is rather small, it would allow a very fast dictionary check on all
possible values).  The checking is only rudimentary, but in combination with
the minimum password length should succeed in weeding out most weak passwords.

Another possible option is to force a key to contain at least one punctuation
character, or at least one digit as some Unix systems do.  Unfortunately this
tends to lead people to simply append a single punctuation character or a fixed
digit to the end of an existing key, with little increase in security.

More password issues are discussed in the section "The Care and Feeding of
Passwords" above.


Data left in program memory by SFS programs

Various SFS utilities make use of critical keying information which can be used
to access an SFS volume.  Great care has been taken to ensure that all critical
information stored by these programs is erased from memory at the earliest
possible moment.  All encryption-related information is stored in static
buffers which are accessed through pointers passed to various routines, and is
overwritten as soon as it is no longer needed.  All programs take great care to
acquire keying information from the user at the last possible moment, and
destroy this information as soon as either the disk volume has been encrypted
or the keying information has been passed to the SFS driver.  In addition, they
install default exit handlers on startup which systematically erase all data
areas used by the program, both for normal exits and for error or
special-condition exits such as the user interrupting the programs execution.


Data left in program memory by the SFS driver

The SFS driver, in order to transparently encrypt and decrypt a volume, must
at all times store the keying information needed to encrypt and decrypt the
volume.  It is essential that this information be destroyed as soon as the
encrypted volume is unmounted.  SFS does this by erasing all encryption-related
information held by the driver as soon as it receives an unmount command.  In
addition, the driver's use of a unique disk key for each disk ensures that even
if a complete running SFS system is captured by an opponent, only the keys for
the volumes currently mounted will be compromised, even if several volumes are
encrypted with the same user password (see the section "Controlled Disclosure
of Encrypted Information" below for more details on this).


Data left in system buffers by mksfs

mksfs must, when encrypting a volume, read and write data via standard system
disk routines.  This data, consisting of raw disk sectors in either plaintext
or encrypted form, can linger inside system buffers and operating system or
hard disk caches for some time afterwards.  However since none of the
information is critical (the plaintext was available anyway moments before
mksfs was run, and at worst knowledge of the plaintext form of a disk sector
leads to a known plaintext attack, which is possible anyway with the highly
regular disk layout used by most operating systems), and since accessing any of
this information in order to erase it is highly nontrivial, this is not
regarded as a weakness.


Data left in system buffers by mountsfs

As part of its normal operation, mountsfs must pass certain keying information
to the SFS driver through a DOS system call.  DOS itself does not copy the
information, but simply passes a pointer to it to the SFS driver.  After the
driver has been initialised, mountsfs destroys the information as outlined
above.  This is the only time any keying information is passed outside the
control of mountsfs, and the value is only passed by reference.


Data left in system buffers by the SFS driver

Like mksfs, the SFS driver reads and writes data via standard system disk
routines.  This data, consisting of raw disk sectors in either plaintext or
encrypted form, can linger inside system buffers and operating system or hard
disk caches for some time afterwards.  Once the encrypted volume is unmounted,
it is essential that any plaintext information still held in system buffers be
destroyed.

In order to accomplish this, mountsfs, when issuing an unmount command,
performs two actions intended to destroy any buffered information.  First, it
issues a cache flush command followed by a cache reset command to any DOS drive
cacheing software it recognizes, such as older versions of Microsoft's
SmartDrive (with IOCTL commands), newer versions of SmartDrive (version 4.0 and
up), the PCTools 5.x cache, Central Point Software's PC-Cache 6.0 and up, the
more recent PC-Cache 8.x, Norton Utilities' NCache-F, NCache-S, and the newer
NCache 6.0 and up, the Super PC-Kwik cache 3.0 and up, and Qualitas' QCache 4.0
and up.  Some other cacheing software can be detected but doesn't support
external cache flushing.  This step is handled by mountsfs rather than the
driver due to the rather complex nature of the procedures necessary to handle
the large variety of cacheing software, and the fact that most cacheing
software can't be accessed from a device drvier.

After this the SFS driver itself issues a disk reset command which has the
effect of flushing all buffered and cached data scheduled to be written to a
disk, and of marking those cache and buffer entries as being available for
immediate use.  In addition to the explicit flushing performed by the mountsfs
program, many cacheing programs will recognise this as a signal to flush their
internal buffers (quite apart from the automatic flushing performed by the
operating system and the drive controller).

Any subsequent disk accesses will therefore overwrite any data still held in
the cache and system buffers.  While this does not provide a complete guarantee
that the data has gone (some software disk caches will only support a cache
flush, not a complete cache reset), it is the best which can be achieved
without using highly hardware and system-specific code.


SFS volumes left mounted

It is possible that an SFS volume may be unintentionally left mounted on an
unattended system, allowing free access to both the in-memory keying
information and the encrypted volume.  In order to lessen this problem
somewhat, a fast-unmount hotkey has been incorporated into the SFS driver which
allows an unmount command to be issued instantly from the keyboard (see the
sections "Mounting an SFS Volume" and "Advanced SFS Driver Options" above).
The ease of use of this command (a single keystroke) is intended to encourage
the unmounting of encrypted volumes as soon as they are no longer needed,
rather than whenever the system is next powered down.

As an extra precaution, the driver's use of a unique disk key for each disk
ensures that even if a complete running SFS system with encrypted volumes still
mounted is captured by an opponent, only the keys for the volumes currently
mounted will be compromised, even if several volumes are encrypted with the
same user password (see the section "Controlled Disclosure of Encrypted
Information" below for more details on this).

Finally, a facility for an automatic timed unmount of volumes left mounted is
provided, so that volumes mistakenly left mounted while the system is
unattended may be automatically unmounted after a given period of time.  This
ensures that, when the inevitable distractions occur, encrypted volumes are
safely unmounted at some point rather than being left indefinitely accessible
to anyone with access to the system.


Controlled disclosure of encrypted information

To date there are no known laws which can be used to enforce disclosure of
encrypted information, a field which is usually covered by safeguards against
self-incrimination.  However there have been moves in both the US and the UK to
pass legislation which would compromise the integrity of encrypted information,
or which would remove protection against self-incrimination.  In either case
this would allow agencies to compel users of cryptographic software to reveal
the very information they are trying to protect, often without the users even
being aware that their privacy is being compromised.

The approach taken in the US, in the form of the Clipper initiative, is to have
all encryption keys held by the government.  If disclosure of the information
is required, the key is retrieved from storage and used to decrypt the
information.  A side effect of this is that any data which has ever been
encrypted with the key, and any data which will ever be encrypted in the
future, has now been rendered unsafe.  This system is best viewed as
uncontrolled disclosure.

SFS includes a built-in mechanism for controlled disclosure so that, if
disclosure is ever required by law, only the information for which access is
authorized may be revealed.  All other encrypted data remains as secure as it
was previously.

This is achieved by encrypting each disk volume with a unique disk key which is
completely unrelated to the users passphrase.  When the passphrase is entered,
it is transformed by iterating a one-way hash function over it several hundred
times to create an intermediate key which is used to decrypt the disk key
itself.  The disk volume is then en/decrypted with the disk key rather than the
unmodified encryption key supplied by the user.  There is no correlation
between the user/intermediate key and the disk key

If disclosure of the encrypted information is required, the disk key can be
revealed without compromising the security of the user key (since it is
unrelated to the user key), or the integrity of any other data encrypted with
the user key (since the disk key is unique for each disk volume, so that
knowledge of a particular disk key allows only the one volume it corresponds to
to be decrypted).

The controlled disclosure option is handled by the two mountsfs options `-d'
and `-c'.  The `-d' option will disclose the unique key for a given disk
volume, and the `-c' option will accept this key instead of the usual password.
For example to disclose the disk key for the SFS volume "Data", the command
would be:

  mountsfs -d vol=data

mountsfs will then ask for the password in the usual manner and prompt:

  You are about to disclose the encryption key for this SFS volume.
  Are you sure you want to do this [y/n]

At this point a response of 'Y' will continue and a response of 'N' will exit
the program without disclosing the disk key.  A response of 'Y' will print the
disk key in the following format:

  Disk key is

      2D 96 B1 06 6D E8 30 21 D5 DB 1B CC 3E 0E C7 CF D6 D1 0C 97 75 DC
      06 74 BC 2F E6 A0 3C 56 80 5F 0D 30 DA 54 D3 0D 28 F3 14 DE 79 67
      6E 1A 75 DC 33 87 86 29 BA A5 B1 64 5B 79 67 8C 8A 1B D1 27 5B 79
      73 6B 45 7B DA 54 43 6C C1 AB 06 67 7E 94 86 F2 50 22 09 8D 21 D5
      E7 3A 80 5F 0D 30 DA 54 D3 0D 28 FF 6D E8 30 21 33 87 86 29 C0 ED
      4A 22 96 B1 06 6D E8 30 21 D5 1C 2D E6 A0 3C 56 DA 54 43 6C 56 80

This is the unique key needed to access the particular encrypted volume.

To use this key instead of the usual one with mountsfs, the command would be:

  mountsfs -c vol=data

mountsfs will then ask for this disk key instead of the usual password:

  Please enter 264-digit disk key, [ESC] to exit:

At this point the disk key should be entered.  mountsfs will automatically
format the data as it is entered to conform to the above layout.  The ESC key
can be used at any point to exit the process.

Once the key has been entered, the program will perform a validity check on the
key.  If this test fails, mountsfs will display the message:

  Error: Incorrect disk key entered

and exit.  Otherwise it will mount the volume as usual.  Since each volume has
its own unique disk key, revealing the key for one volume gives access to that
volume and no others.  Even if 20 volumes are all encrypted with the same user
password, only one volume can be accessed using a given disk key.


Password Lifetimes and Scope

An SFS password which is used over a long period of time makes a very tempting
target for an attacker.  The longer a particular password is used, the greater
the chance that it has been compromised.  A password used for a year has a far
greater chance of being compromised than one used for a day.  If a password is
used for a long period of time, the temptation for an attacker to spend the
effort necessary to break it is far greater than if the password is only a
short-term one.

The scope of a password is also important.  If a password is used to encrypt a
single drive containing business correspondence, it's compromise is only mildly
serious.  If it is employed to protect dozens of disk volumes or a large file
server holding considerable amounts of confidential information, the compromise
of the password could be devastating.  Again, the temptation to attack the
master password for an entire file server is far greater than for the password
protecting data contained on a single floppy disk.

SFS attacks this problem in two ways.  First, it uses unique disk keys to
protect each SFS volume.  The disk key is a 1024-bit cryptographically strong
random key generated from nondeterministic values acquired from system
hardware, system software, and user input (see the subsection "Generating
Random Numbers" below).  The data on each disk volume is encrypted using this
unique disk key, which is stored in encrypted form in the SFS volume header
(this works somewhat like session keys in PEM or PGP, except that a
conventional-key algorithm is used instead of a public-key one).  To access the
disk, the encrypted disk key is first decrypted with the user password, and the
disk key itself is used to access the disk.  This denies an attacker any known
plaintext to work with (as the plaintext consists of the random disk key).  To
check whether a given password is valid, an attacker must use it to decrypt the
disk key, rekey the encryption system with the decrypted disk key, and try to
decrypt the disk data.  Only then will they know whether their password guess
was correct or not.  This moves the target of an attack from a (possibly
simple) user password to a 1024-bit random disk key[1].

The other way in which SFS tries to ameliorate the problem of password
lifetimes and scope is by making the changing of a password a very simple
operation.  Since the only thing which needs to be changed when a password
change is made is the encryption on the disk key, the entire password change
operation can be made in a matter of seconds, rather than the many minutes it
would take to decrypt and re-encrypt an entire disk.  It is hoped that the ease
with which passwords can be changed will encourage the frequent changing of
passwords by users.

Footnote [1]: SFS may not use the entire 1024 bits - the exact usage depends on
              the encryption algorithm being used.


Trojan Horses

The general problem of trojan horses is discussed in the section "Data
Security" above.  In general, by planting a program in the target machine which
monitors the password as it is entered or the data as it is read from or
written to disk, an attacker can spare themselves the effort of attacking the
encryption system itself.  In an attempt to remove the threat of password
interception, SFS takes direct control of the keyboard and various other pieces
of system hardware which may be used to help intercept keyboard access, making
it significantly more difficult for any monitoring software to detect passwords
as they are entered.  If any keystroke recording or monitoring routines are
running, the SFS password entry process is entirely invisible to them.  This
feature has been tested by a computer security firm who examined SFS, and found
it was the only program they had encountered (including one rated as secure for
military use) which withstood this form of attack.

Similarly, the fast disk access modes used by SFS can be used to bypass any
monitoring software, as SFS takes direct control of the drive controller
hardware rather than using the easily-intercepted BIOS or DOS disk access
routines.

Although these measures can still be worked around by an attacker, the methods
required are by no means trivial and will probably be highly system-dependant,
making a general encryption-defeating trojan horse difficult to achieve.


Design Details
--------------

This section goes into a few of the more obscure details not covered in the
section on security analysis, such as the encryption algorithm used by SFS, the
generation of random numbers, the handling of initialization vectors (IV's),
and a brief overview on the deletion of sensitive information retained in
memory after a program has terminated (this is covered in more detail in the
section "Security Analysis" above).


The Encryption Algorithm used in SFS

Great care must be taken when choosing an encryption algorithm for use in
security software.  For example, the standard Unix crypt(1) command is based on
a software implementation of a rotor machine encryption device of the kind
which was broken by mathematicians using pencil and paper (and, later on, some
of the first electronic computers) in the late 1930's[1].  Indeed, there exists
a program called `crypt breaker's workbench' which allows the automated
breaking of data encrypted using the crypt(1) command[2].  The insecurity of
various other programs has been mentioned elsewhere.  It is therefore
imperative that a reliable encryption system, based on world-wide security
standards, and easily verifiable by consulting these standards, be used.

When a block cipher is used as a stream cipher by running it in CFB (cipher
feedback) mode, there is no need for the cipher's block transformation to be a
reversible one as it is only ever run in one direction (generally
encrypt-only).  Therefore the use of a reversible cipher such as DES or IDEA is
unnecessary, and any secure one-way block transformation can be substituted.
This fact allows the use of one-way hash functions, which have much larger
block sizes (128 or more bits) and key spaces (512 or more bits) than most
reversible block ciphers in use today.

The transformation involved in a one-way hash function takes an initial hash
value H and a data block D, and hashes it to create a new hash value H':

    hash( H, D ) -> H'

or, more specifically, in the function used in SFS:

    H + hash( D ) -> H'

This operation is explained in more detail in FIPS Publication 180 and ANSI
X9.30 part 2, which define the Secure Hash Standard.  By using H as the data
block to be encrypted and D as the key, we can make the output value H'
dependant on a user-supplied key. That is, when H is the plaintext, D is the
encryption key, and H' is the ciphertext:

     plaintext H
         |
         v
    +---------+
    |   SHS   |<- key D
    +---------+
         |
         v
    ciphertext H'

If we regard it as a block cipher, the above becomes:

    H' = SHS( H )

which is actually:

    C  =   e( P )

Since we can only ever "encrypt" using a one-way hash function, we need to run
the "cipher" in cipher feedback mode, which doesn't require a reversible
encryption algorithm.

By the properties of the hash function, it is computationally infeasible to
either recover the key D or to control the transformation H -> H' (in other
words given a value for H' we cannot predict the H which generated it, and
given control over the value H we cannot generate an arbitrary H' from it).

The MDC encryption algorithm is a general encryption system which will take any
one-way hash function and turn it into a stream cipher running in CFB mode. The
recommended one-way hash function for MDC is the Secure Hash Standard as
specified in Federal Information Processing Standards (FIPS) Publication 180
and ANSI X9.30 part 2.  SHS is used as the block transformation in a block
cipher run in CFB mode as detailed in AS 2805.5.2 section 8 and ISO 10116:1991
section 6, with the two parameters (the size of the feedback and plaintext
variables) j and k both being set to the SHS block size of 160 bits.  The
properties of this mode of operation are given in Appendix A3 of AS 2805.5.2
and Annex A.3 of ISO 10116:1991.  The CFB mode of operation is also detailed in
a number of other standards such as FIPS Publication 81 and USSR Government
Standard GOST 28147-89, Section 4.  The use of an initialization vector (IV) is
as given in ISO 10126-2:1991 section 4.2, except that the size of the IV is
increased to 160 bits from the 48 or 64 bits value given in the standard. This
is again detailed in a number of other standards such as GOST 28147-89 Section
3.1.2. The derivation of the IV is given in the section "Encryption
Considerations" below.

The key setup for the MDC encryption algorithm is performed by running the
cipher over the encryption key (in effect encrypting the key with MDC using
itself as the key) and using the encrypted value as the new encryption key.
This procedure is then repeated a number of times to make a "brute-force"
decryption attack more difficult, as per the recommendation in the Public-Key
Cryptography Standard (PKCS), part 1.  This reduces any input key, even one
which contains regular data patterns, to a block of white noise equal in size
to the MDC key data.

The exact key scheduling process for MDC is as follows:

 Initialization:

 - The SHS hash value H is set to the key IV[3].
 - The SHS data block D is set to all zeroes.
 - The key data of length 2048 bits is set to a 16-bit big-endian value
   containing the length of the user key in bytes, followed by up to 2032 bits
   of user key.

   SHS hash value H = key IV;
   SHS data block D = zeroes;
   key_data [0:15] = length of user key in bytes;
   key_data [16:2047] = user key, zero-padded;

 Key schedule:

 - The following process is iterated a number of times:

   - The 2048-bit key data block is encrypted using MDC.
   - Enough of the encrypted key data is copied from the start of the key data
     block into the SHS data block D to fill it.

   for i = 1 to 200 do
       encrypted_key = encrypt( key_data );
       D = encrypted_key;

During the repeated encryptions, the IV is never reset.  This means that the IV
from the end of the n-1 th data block is re-injected into the start of the n th
data block.  After 200 iterations, the "randomness" present in the key has been
diffused throughout the entire key data block.

Although the full length of the key data block is 2048 bits, the SHS algorithm
only uses 512 bits of this (corresponding to the SHS data block D) per
iteration.  The remaining 1536 bits take part in the computation (by being
carried along via the IV) but are not used directly.  By current estimates
there are around 2^256 atoms in the universe.  Compiling a table of all 2^512
possible keys which would be necessary for a brute-force attack on MDC would
therefore be a considerable challenge to an attacker, requiring, at least, the
creation of another 512 * 2^256 universes to hold all the keys.  Even allowing
for the current best-case estimate of a creation time of 7 days per universe,
the mere creation of storage space for all the keys would take an unimaginably
large amount of time.

The SFS key schedule operation has been deliberately designed to slow down
special hardware implementations, since the encryption algorithm is rekeyed
after each iteration.  Normal high-speed password-cracking hardware would (for
example, with DES) have 16 separate key schedules in a circular buffer, each
being applied to a different stage of a 16-stage pipeline (one stage per DES
round) allowing a new result to be obtained in every clock cycle once the
pipeline is filled.  In MDC the key data is reused multiple times during the 80
rounds of SHS, requiring 80 separate key schedules for the same performance as
the 16 DES ones.  However since the algorithm is rekeyed after every iteration
for a total of 200 iterations, this process must either be repeated 200 times
(for a corresponding slowdown factor of 200), or the full pipeline must be
extended to 16,000 stages to allow the one-result-per-cycle performance which
the 16-stage DES pipeline can deliver (assuming the rekeying operation can be
performed in a single cycle).  Changing the iteration count to a higher value
will further slow down this process.

The number of iterations of key encryption is controlled by the user, and is
generally done some hundreds of times.  The setup process in SFS has been tuned
to take approximately half a second on a workstation rated at around 15 MIPS
(corresponding to 200 iterations of the encryption process), making a
brute-force password attack very time-consuming.  Note that the key IV is
injected at the earliest possible moment in the key schedule rather than at the
very end, making the use of a precomputed data attack impossible.  The standard
method of injecting the encryption IV at the end of the key schedule process
offers very little protection against an attack using precomputed data, as it
is still possible to precompute the key schedules and simply drop in the
encryption IV at the last possible moment.

Footnote [1]: This is covered in a number of books, for example Welchman's "The
              Hut Six Story: Breaking the Enigma Codes", New York, McGraw-Hill
              1982, and Kahns "Seizing the Enigma", Boston, Houghton-Mifflin
              1991.

Footnote [2]: Available from black.ox.ac.uk in the directory /src/security as
              cbw.tar.Z.

Footnote [3]: Some sources would refer to this value as a `salt'.  The term
              `key IV' is used here as this is probably a more accurate
              description of its function.


Generating Random Numbers

One thing which cryptosystems consume in large quantities are random numbers.
Not just any old random value, but cryptographically strong random numbers.  A
cryptographically strong random value is one which cannot be predicted by an
attacker (if the attacker can predict the values which are used to set up
encryption keys, then they can make a guess at the encryption key itself).
This automatically rules out all software means of generating random values,
and means specialised hardware must be used.

Very few PC's are currently equipped with this type of hardware.  However SFS
requires 1024 random bits for each encrypted disk, in the form of the disk key
(see the section "Password Lifetimes and Scope" above).  SFS therefore uses a
number of sources of random numbers, both ones present in the hardware of the
PC and one external source:

  - Various hardware timers which are read occasionally when the program is
    running (generally after operations which are long and complex and will be
    heavily affected by external influences such as interrupts, video, screen,
    and disk I/O, and other factors.

  - The contents and status information of the keyboard buffer

  - Disk driver controller and status information

  - Mouse data and information

  - Video controller registers and status information

[ - The clock skew between two hardware clocks available on the PC.  Due to
    background system activity such as interrupt servicing, disk activity, and
    variable-length instruction execution times, these clocks run out-of-phase.
    SFS uses this phase difference as a source of random numbers.  NB: Not
    implemented yet].

  - The timing of keystrokes when the password is entered.  SFS reads the
    high-speed 1.19 MHz hardware timer after each keystroke and uses the timer
    values as a source of random numbers.  This timer is used both to measure
    keystroke latency when the password is entered and read at random times
    during program execution.  Trials have shown that this 16-bit counter
    yields around 8 bits of random information (the exact information content
    is difficult to gauge as background interrupts, video updates, disk
    operations, protected-mode supervisor software, and other factors greatly
    affect any accesses to this counter, but an estimate of 8 bits is probably
    close enough[1]).

  - The timing of disk access latency for random disk reads.  The exact
    operation is as follows:

        Read a timer-based random disk sector
        Add its contents (8 bits)
        Read the high-speed 1.19 MHz hardware timer (13 bits)
        Use the two values for the next random sector

    This is repeated as often as required (in the case of SFS this is 10
    times).  Assuming a (currently rather optimistic) maximum of 5ms to acquire
    a sector this provides about 13 bits of randomness per disk operation.  The
    number of factors which influence this value is rather high, and includes
    among other things the time it takes the BIOS to process the request, the
    time it takes the controller to process the request, time to seek to the
    track on the disk, time to read the data (or, if disk cacheing is used,
    time for the occasional cache hit), time to send it to the PC, time to
    switch in and out of protected mode when putting it in the cache, and of
    course the constant 3-degree background radiation of other interrupts and
    system activity happening at the same time.  If a solid-state disk were
    being used, the hardware latency would be significantly reduced, but
    currently virtually no 386-class PC's have solid-state disks (they're
    reserved for palmtops and the like), so this isn't a major concern.

An estimate of the number of random bits available from each source is as
follows:

    Keystroke latency, 8 bits per key      80 bits for minimum 10-char key
    Second password entry for encryption   80 bits for minimum 10-char key
    Disk access latency, 13 bits per read 130 bits for 10 reads
    Disk sector data, 8 bits               80 bits for 10 reads
    System clocks and timers                3 bits
    Video controller information            4 bits
    Keyboard buffer information             4 bits
    Disk status information                 4 bits
    General system status                   4 bits
    Random high-speed timer reads         120 bits for 15 reads
                                          --------
    Total                                 509 bits

These figures are very conservative estimates only, and are based on timing
experiments with typed-in passwords and a careful scrutiny of the PC's hardware
and system status data.  For example, although the time to access a disk sector
for a particular drive may be 10ms or more, the actual variation on that 10ms
may only be +/- 2ms.  The figures given above were taken by averaging the
variation in times for large numbers of tests.  In practice (especially with
longer passwords) the number of random bits is increased somewhat (for example
with a 30-character password the total may be as high as 829 bits of random
information).  However even the minimal estimate of 509 bits is adequate for
the 512-bit key required by MDC.

Each quantum of semi-random information is exclusive-ored into a 1024-bit
buffer which is initially set to all zeroes.  Once 1024 bits of buffer have
been filled, the data is encrypted with MDC to distribute the information, and
the first 512 bits of the 1024-bit buffer is used as the key for the next MDC
encyrption pass.  Then more data is added until, again, 1024 bits of buffer
have been filled, whereupon the data is again mixed by encrypting it with MDC.
This process is repeated several times, with the amount of "randomness" in the
buffer increasing with each iteration.

Before being used, this data is encrypted 10 times over with MDC to ensure a
complete diffusion of randomness.  Since the IV for the encryption is reused
for the next pass through the buffer, any information from the end of the
buffer is thus reinjected at the start of the buffer on the next encryption
pass.

Although this method of generating random numbers is not perfect, it seems to
be the best available using the existing hardware.  General estimates of the
exact amount of truly random information which can be acquired in this manner
are in the vicinity of several hundred bits.  Proposed attacks all make the
assumption that an attacker is in possession of what amounts to a complete
hardware trace of events on the machine in question.  Allowing for a reasonable
amount of physical system security, it can be assumed that the random data used
in SFS is unpredictable enough to provide an adequate amount of security
against all but the most determined attacker.

Footnote [1]: If an opponent can obtain several hours of keystroke timings and
              can come up with a good model including serial correlations, they
              may be able to reduce the likely inputs to the random number
              accumulator to a somewhat smaller value, or at least bias their
              guesses to fall within the range of likely values.


Encryption Considerations

When a block cipher is converted to handle units of data larger than its
intrinsic block size, a number of weaknesses can be introduced, depending on
the mode of operation which is chosen for the block cipher.  For example, if
two identical ciphertext blocks are present in different locations in a file,
this may be used to determine the plaintext.  If we can find two identical
blocks of ciphertext when cipher block chaining (CBC) is used, then we know
that:

    P[ i ] = d( C[ i ] ) ^ C[ i-1 ]
    P[ j ] = d( C[ j ] ) ^ C[ j-1 ]

where C is the ciphertext, P is the plaintext, and e() and d() are encryption
and decryption respectively.  Now if C[ i ] = C[ j ], then d( C[ i ] ) =
d( C[ j ] ), which cancel out when xor'd so that:

    P[ i ] ^ C[ i-1 ] = P[ j ] ^ C[ j-1 ]

or:

     P[ j ] = P[ i ] ^ C[ i-1 ] ^ C[ j-1 ]

Knowing C[ i ] and C[ j ] we can determine P[ i ] and P[ j ], and knowing
either P[ i ] or P[ j ] we can determine the other.

Something similar holds when cipher feedback (CFB) mode is used, except that
now the decryption operation is:

    P[ i ] = e( C[ i-1 ] ) ^ C[ i ]
    P[ j ] = e( C[ j-1 ] ) ^ C[ j ]

Now if C[ i ] = C[ j ] then e( C[ i ] ) = e( C[ j ] ) (recall that in CFB mode
the block cipher is only ever used for encryption), so that they again cancel
out, so:

    P[ i ] ^ e( C[ i-1 ] ) = P[ j ] ^ e( C[ j-1 ] )

or:

    P[ i ] = P[ j ] ^ e( C[ i-1 ] ) ^ e( C[ j-1 ] )

In general this problem is of little consequence since the probability of
finding two equal blocks of ciphertext when using a 160-bit block cipher on a
dataset of any practical size is negligible.  More esoteric modes of operation
such as plaintext feedback (PFB) and ones whose acronyms have more letters than
Welsh place names tend to have their own special problems and aren't considered
here.

The problem does become serious, however, in the case of sector-level
encryption, where the initialization vector cannot be varied.  Although the IV
may be unique for each sector, it remains constant unless special measures such
as reserving extra storage for sector IV's which are updated with each sector
write are taken.  If a sector is read from disk, a small change made to part of
it (for example changing a word in a text file), and the sector written out to
disk again, several unchanged ciphertext/plaintext pairs will be present,
allowing the above attack to be applied.  However, there are cases in which
this can be a problem.  For example, running a program such as a disk
defragmenter will rewrite a large number of sectors while leaving the IV
unchanged, allowing an opponent access to large quantities of XOR'd plaintext
blocks simply by recording the disk contents before and after the
defragmentation process.  Normally this problem would be avoided by using a
different IV for each encrypted message, but most disk systems don't have the
room to store an entire sectors worth of data as well as the IV needed to
en/decrypt it.

An additional disadvantage of the CFB encryption mode is that the data in the
last block of a dataset may be altered by an attacker to give different
plaintext without it affecting the rest of the block, since the altered
ciphertext in the last block never enters the feedback loop.  This type of
attack requires that an opponent possess at least two copies of the ciphertext,
and that they differ only in the contents of the last block.  In this case the
last ciphertext block from one copy can be subsituted for the last ciphertext
block in the other copy, allowing a subtle form of message modification attack.
In fact in combination with the previously mentioned weakness of CFB, an
attacker can determine the XOR of the plaintexts in the last block and
substitute an arbitrary piece of "encrypted" plaintext to replace the existing
data.

There are several approaches to tackling this problem.  The most simplistic one
is to permute the plaintext in a key-dependant manner before encryption and
after decryption.  This solution is unsatisfactory as it simply shuffles the
data around without necessarily affecting any particular plaintext or
ciphertext block.  The desired goal of a change in any part of the plaintext
affecting the entire dataset is not achieved.

A better solution is to encrypt data twice, once from front to back and then
from back to front[1].  The front-to-back pass propagates any dependencies to
the back of the dataset, and the back-to-front pass propagates dependencies
back to the front again.  In this way a single change in any part of the
plaintext affects the entire dataset.  The disadvantage of this approach is
that it at least halves the speed of the encryption, as all data must be
encrypted twice. If the encryption is done in software, this may create an
unacceptable loss of throughput.  Even with hardware assistance there is a
noticeable slowdown, as no hardware implementations easily support backwards
encryption, requiring the data to be reversed in software before the second
pass is possible.

The best solution is probably to use a word-wise scrambler polynomial like the
one used in SHA.  With a block of plaintext P this is:

    P[ i ] ^= P[ i-K1 ] ^ P[ i-K2 ]

with suitable values for the constants K1 and K2.  If K2 is chosen to be 5 (the
SHA block size in words) then the initial values of the 5 words (which can be
thought of as as P[ -5 ]...P[ -1 ]) are simply the sectorIV.  The value of K1
is arbitrary, SFS uses a value of 4.

This technique is used by first setting the initial values of the 5 words to
the sectorIV.  The scrambler function is then run over the entire data block,
propagating all dependencies to the last 5 words in the block.  These last 5
words are then used as the IV for the CFB encryption of the entire block.  In
this way the encryption IV depends on all the bits in the block, and the
scrambling does a moderately good job of breaking up statistical patterns in
the plaintext.  No information is lost, so no randomness in the sectorIV is
misplaced.

This also provides resistance to the selective-modification attack which allows
an attacker to change selected bits in the last block of a CFB-encrypted
dataset without damage.  By destroying the IV used in the CFB encryption, the
first block is completely corrupted, which is unlikely to go unnoticed.

To decrypt a dataset encrypted in this manner, the first 5 words of ciphertext
are shifted into the feedback path, and the remainder of the dataset is
decrypted in the standard manner.  The last 5 decrypted words are then used as
the IV to decrypt the first encrypted block.  Finally, the scrambler is run
over the recovered plaintext to undo the changes made during the encryption
scrambling.

The overall en/decryption process used by SFS, in the case of 512-byte sectors
and 32-bit words (so that each sector contains 128 words), is:

    Encryption:

        using sectorIV[ 0 ]...sectorIV[ 4 ] as the scrambler IV
            scramble data[ 0 ]...data[ 127 ]
        using data[ 127-5 ]...data[ 127-1 ] as the encryption IV
            encrypt data[ 0 ]...data[ 127 ]

    Decryption:

        using data[ 0 ]...data[ 4 ] as the encryption IV
            decrypt data[ 5 ]...data[ 127 ]
        using data[ 127-5 ]...data[ 127-1 ] as the encryption IV
            decrypt data[ 0 ]...data[ 4 ]
        using sectorIV[ 0 ]...sectorIV[ 4 ] as the scrambler IV
            scramble data[ 0 ]...data[ 127 ]

where the scrambling operation is:

        data[ i ] ^= data[ i-4 ] ^ data[ i-5 ]

as outlined above.  Note that the i-4 and i-5 th values referred to here are
the original, scrambled values, not the descrambled values.  The easiest way to
implement this is to cache the last 5 scrambled values and cyclically overwrite
them as each word in the data buffer is processed.

Footnote [1]:  To be precise, you need some sort of feedback from the end of
               a block on the first encryption pass to the start of the block
               on the next encryption pass.  A block can be encrypted forwards
               twice as long as the IV is wrapped back to the start of the
               block for the second encryption pass.


A Discussion of the MDC Encryption Algorithm[1]

(A word on notation:  The notation {0,1}^k is used to mean the set of all bit
strings of length k, and {0,1}* means the set of all bit strings, including the
empty string.  Any message can be viewed as a bit string by means of a suitable
encoding).

The encryption method used by SFS is somewhat unusual, and in some respects is
similar to Merkle's "Meta Method" for obtaining cryptosystems[2].  The method
relies on the existence of secure one-way hash functions.  A hash function is a
function that takes as input an arbitrary number of bits and produces a
fixed-sized output called the "message digest".  In other words, hash functions
have the form

    h : {0,1}* --> {0,1}^k              for some fixed k,

and the hash of a message M is defined to be h( M ).  A secure one-way hash
function is a hash function with the following properties:

    1. For each message M, it is easy to compute h( M ).

    2. Given M, it is computationally infeasible to compute M' with
       h( M ) = h( M' ) (secure against forgery).

    3. It is computationally infeasible to compute M and M' with
       h( M ) = h( M' ) (secure against collisions).

For a good, but rather technical, discussion of hash functions, see
"Contemporary Cryptology. The Science of Information Integrity" edited by
Gustavus Simmons, IEEE Press, 1992 (ISBN 0-87942-277-7).

The terms "easy to compute" and "infeasible to compute" can be given more
precise definitions, but we'll settle for this informal terminology for now.
Roughly speaking, "easy to compute" means that it will take a tolerable amount
of time to compute the answer, even on a rather small machine; "infeasible to
compute" means that it should take eons to find out a particular result, even
when using millions of computers of the fastest conceivable technology in
parallel.

Examples of hash functions include the MD2, MD4, and MD5 hash functions,
developed by Ron Rivest of RSA Data Security, Inc., which have been (at least
in the case of MD4 and MD5) placed in the public domain, and the Secure Hash
Standard SHS, developed by NIST (with significant input from the NSA).  The
existence of secure one-way hash functions has not been proven, although there
exist some strong candidates, including MD5 and SHS.

The reference implementations of the above hashing functions include one
interesting aspect which makes it possible to use them as encryption functions.
Since the hashing of a very large amount of data in one sweep is not desirable
(because all the data would have to be in memory at the time of hashing), most
hashing algorithms allow data to be hashed incrementally.  This is made
possible by augmenting the definition of a hash function to include the state
of the last hashing operation.  In other words, a hash function now has the
form

    h : {0,1}^k x {0,1}* --> {0,1}^k,

where the first argument is the previous hash value, and the hash of a message
M = ( M1, M2, ..., Mn ) is defined to be

    h( h( ...( h( h0, M1 ), M2 ), ... ), Mn ).

(The value of all the h evaluations must not change if the message is broken up
into blocks of different lengths, but all of the previously mentioned hash
functions have that property).  Here, h0 is a fixed, known initial value that
is used in all hashing calculations.

This is not the way "real" hash functions behave, but it is close enough.  For
example, the MD5 hashing function has "initialization", "updating", and
"finalization" parts, where the finalization part appends the number of hashed
bytes to the message, hashes one final time, and returns the final hash value.
This means that the hashing "context" must include the number of bytes hashed
so far, without it being a part of the hash value.  The hash function can be
said to have "memory".

If we assume that h is a secure one-way hashing function, we can now use such
an h as a scrambling device.  For example, if we set E( M ) = h( h0, M ) for
every message M, M will not be recoverable from E( M ), because h is secure by
definition.  Another method would be to supply M to any standard MSDOS or UNIX
utility and use the resulting error message as the ciphertext (remembering that
a computer is a device for turning input into error messages).  However, there
are still two problems to be solved before we can use hash functions as
encryption functions:

    1. The scrambling process is not controlled by a key.

    2. The scrambling process is not invertible, so there is no way to
       decrypt the ciphertext.

Both problems can be solved by interchanging the roles of hash and data and by
using CFB mode in the encryption process.  In other words, let K be an
arbitrarily long key, let M = ( M1, ..., Mn ) be a message, broken up into
chunks of k bits, let IV be an initialization vector, and set

    C1 = M1 xor h( IV, K )
    Ci = Mi xor h( C( i-1 ), K )        for 1 < i <= n.

This is sent to the recipient, who easily recovers the plaintext by

    P1 = C1 xor h( IV, K )
    Pi = Ci xor h( C( i-1 ), K )                for 1 < i <= n,

since we have

    P1 = ( M1 xor h( IV, K ) ) xor h( IV, K )
       = M1 xor ( h( IV, K ) xor h( IV,K ) )    because xor is associative,
       = M1 xor 0,                              because x xor x = 0,
       = M1,                                    because x xor 0 = x,

and similarly for the Pi's.  This method of encryption also offers more
security than using ECB mode, assuming that this were possible with hash
functions, since the plaintext is diffused over the entire ciphertext,
destroying plaintext statistics, and thus foiling straightforward ciphertext
correlation attacks.

This method can clearly be used for any hash function which can hash
incrementally.  Thus, it is a "Meta Method" for turning hash functions into
encryption functions.  This is called the Message Digest Cipher (MDC) method of
encryption.  Specific instances of the method have the name of the hash
function added as a suffix.  For example, the MDC method applied to the MD5
hash function would be referred to as MDC/MD5.  SFS uses MDC/SHS.

Having analysed the inner workings of MDC, at least one theoretical attack on
the algorithm should be mentioned.  There are certain properties of hash
functions which may make them unsuitable for use as encryption algorithms.  For
example suppose knowledge of a 160-bit input/output pair to SHS leaks a
fraction of a bit of information about the data being hashed, maybe a quarter
of a bit.  This allows a search of 2^159.75 data blocks to find another data
block that causes the given input-output transformation, and thus finds a
second message which produces the same hash value.  This problem is not
significant when SHS is used as a cryptographic hash function, since it only
reduces the search space by 16% from the full 2^160 possibilities.  However
when SHS is used for encryption, it may be possible to accumulate these quarter
bits, so that after 2560 blocks (50K) of known plaintext, enough bits have been
accumulated to compute the encryption key.  This is because multiple
input/output pairs are available for a given data block, and each one puts more
constraints on the block until eventually you have the actual value can be
determined.

If a hash function is has the properties given above and no such information is
leaked, it can serve to create a strong encryption algorithm, but a serious
weakness in the encryption algorithm is not necessarily a serious weakness in
the hash function.  To date noone has ever demonstrated such a weakness, and
there are a number of similar "what if" arguments which can be used against
most encryption schemes.  For example if it were possible to build a quantum
computer then it could be used to break many of the most popular public-key
encryption schemes in use today.  The reason that these schemes aren't being
abandoned is that it is very unlikely that any computer of this form will be
built, and that if someone does manage it then the implications will be far
more serious than just the breaking of a number of encryption schemes.

Footnote [1]: Most of this analysis was contributed by Stephan Neuhaus,
              <[e-mail]>

Footnote [2]: This is discussed further in Ralph Merkle's paper "One Way Hash
              Functions and DES", Crypto '89 Proceedings, Springer-Verlag,
              1989 (volume 435 of the Lecture Notes in Computer Science
              series).


Deletion of SFS Volumes

Truly deleting data from magnetic media is very difficult.  The problem lies in
the fact that when data is written to the medium, the write head sets the
polarity of most, but not all, of the magnetic domains.  This is partially due
to the inability of the writing device to write in exactly the same location
each time, and partially due to the variations in media sensitivity and field
strength over time and among devices.

In general terms, when a one is written to disk, the media records a one, and
when a zero is written, the media records a zero.  However the actual effect is
closer to obtaining something like 0.95 when a zero is overwritten with a one,
and 1.05 when a one is overwritten with a one.  Normal disk circuitry is set up
so that both these values are read as ones, but using specialized circuitry it
is possible to work out what previous `layers' contained (in fact on some
systems it may be possible to recover previous data with a simple software
modification to the hardware control code).

This problem is further complicated by the fact that the heads might not pass
exactly over the same track position when data is rewritten, leaving a trace of
the old data still intact.  Current-generation drives reduce this problem
somewhat as track and linear densities have now become so high that the
traditional optical methods of extracting information from the disk platters
has become much more difficult, and in some cases impossible, as the linear bit
cell is below the optical diffraction limit for visible light.  While some data
patterns can still be discerned, recognizing others would be limited to some
subset of patterns.

Despite this small respite, when all the above factors are combined it turns
out that each track on a piece of media contains an image of everything ever
written to it, but that the contribution from each `layer' gets progressively
smaller the further back it was made.  Using techniques like low energy
electron scattering, ferrofluid with optical tracers, or related methods,
followed by the same signal-processing technology which is used to clean up
satellite images, low-level recorded speech, and other data, it is possible to
recover previous data with a remarkable degree of accuracy, to a level limited
only by the sensitivity of the equipment and the amount of expertise of the
organisation attempting the recovery.  Intelligence organisations have a *lot*
of expertise in this field.

The basic concept behind the overwriting scheme used by SFS is to flip each
magnetic domain on the disk back and forth as much as possible (this is the
basic idea behind degaussing - magnetic media are limited in their ability to
store high-frequency oscillations, so we try to flip the bits as rapidly as
possible).  This means that the disk head should be run at the highest possible
frequency, and the same pattern should not be written twice in a row.  If the
data was encoded directly, that would mean a an alternating pattern of ones and
zeroes.  However, disks always use a NRZI encoding scheme in which a 1 bit
signifies an inversion, making the desired pattern a series of one bits.  This
leads to a further complication as all disks use some form of run-length
limited (RLL) encoding, so that the adjacent ones won't be written.  This
encoding is used so that transitions aren't placed too closely together, or too
far apart, which would mean the drive would lose track of where it was in the
data.

The basic limitation on disks is the proximity of 1 bits.  Floppies (which are
a more primitive form of the technology used in hard disks) like to keep the 1
bits 4us apart.  However they can't be kept too far apart or the read clock
loses synchronisation.  This "too far" figure depends a lot on the technology
in the drive, it doesn't depend on the magnetic media much (unlike the "too
close" figure, which depends a lot on the media involved).  The first
single-density encoding wrote one user data bit, then one "1" clock bit, taking
a total of 8us.  This was called FM, since a 1 bit was encoded as two
transitions (1 wavelength) per 8 us, while a 0 bit was encoded as one
transition (1/2 wavelength).

Then it was discovered that it was possible to have two 0 bits between adjacent
1s.  The resulting encoding of 4 bits into 5 was called group code recording
(GCR) which was (0,2) RLL.  This allowed 4 user data bits to be written in
5 * 4us = 20 us, for an effective time per user bit of 5 us, which was a big
improvement over 8 us.

But GCR encoding was somewhat complex.  A different approach was taken in
modified FM (MFM), which suppressed the 1 clock bit except between adjacent
0's.  Thus, 0000 turned into 0(1)0(1)0(1)0 (where the ()s are the inserted
clock bits), 1111 turned into 1(0)1(0)1(0)1, and 1010 turned into
1(0)0(0)1(0)0.  The maximum time between 1 bits was now three 0 bits.  However,
there was at least one 0 bit, so it became possible to clock the bits at
2us/bit and not have more than one 1 bit every 4us.  This achieved one user bit
per 4 us, a result which was better than GCR and obtainable with simpler
circuitry.  As can be seen, the effective data rate depends on the bit rate
(which has been 4 us, 4 us and 2 us in these examples) and the encoding rate, a
measure of the encoding efficiency. The encoding rates have been 1/2, 4/5 and
1/2.

There is a (2,7) RLL code with rate 1/2, meaning that 1 user bit goes to 2
encoded bits (although the mapping involves multi-bit groups and is somewhat
complex), but there are always at least two 0 bits between 1 bits, so 1 bits
happen at most every 3 bit times.  This allows the clock to be reduced to
1.3333 us (this 2/1.33333 = 6/4 = 3/2 is the source of the added capacity gain
of RLL hard drive controllers over equivalent MFM controllers).  The time per
user bit is now 2.6666 = 2 2/3 us.

However, the faster clock is finicky.  It is also possible to use a (1,7) RLL
encoding.  Since this is (1,x), the clock rate is 2 us/bit, but the encoding
efficiency improves from 1/2 to 2/3.  This allows 2 effective user bits per 6
us, or 3 us per user bit.  For hard drives, it is easier to increase the clock
rate by an extra 9/8 than to fiddle with a clock 50% faster, so this is very
popular with more recent disk drives.

The three most common RLL codes are (1,3) RLL (usually known as MFM), (2,7) RLL
(the original "RLL" format), and (1,7) RLL (which is popular in newer drives).
The origins of these codes are explained in more details below.  Fortunately,
each of these three have commonly-used encoding tables.  A knowledge of these
tables can be used to design overwrite patterns with lots of transitions after
being encoded with whatever encoding technique the drive uses.

For MFM, the patterns to write to produce this are 0000 and 1111.  So a couple
of rounds of this should be included in the overwrite pattern. MFM drives are
the oldest, lowest-density drives around (this is especially true for the
very-low-density floppy drives).  As such, they're the easiest to recover data
from with modern equipment and we need to take the most care with them.

For (1,7) RLL, the patterns to write are 0011 and 1100, or 0x33 and 0xCC when
expressed as bytes.  To provide some security against bit misalignment, the
values 0x99 and 0x66 should be included as well (although drive manufacturers
like to keep things byte-aligned, so this sort of bit misalignment is unlikely
to happen).

For (2,7) RLL drives, three patterns are necessary, and the problem of byte
endianness question rears its head.  The previous two cases are not
significantly affected by shifting the bytes around, but this one is.
Fortunately, thanks to the strong influence of IBM mainframe drives, everything
seems to be uniformly big-endian within bytes (that is, the most significant
bit is written to the disk first).

For (2,7) RLL using the standard tables:

  10   -> 0100
  11   -> 1000
  000  -> 00100
  010  -> 100100
  011  -> 001000
  0010 -> 00100100
  0011 -> 00001000

the bit patterns 100100100..., 010010010... and 001001001... will encode into
the maximum-frequency encoded strings 010010010010... (0x49, 0x24, 0x92),
100100100100... (0x92, 0x49, 0x24), and 001001001001.... (0x24, 0x92, 0x49).
Writing all three of these patterns will cover all the bases.

For the latest crop of high-density drives which use methods like Partial-
Response Maximum-Likelihood (PRML) methods which may be roughly equated to the
trellis encoding done by V.32 modems in that it is effective but
computationally expensive, all we can do is write a variety of random patterns,
because the processing inside the drive is too complex to second-guess.
Fortunately, these drives push the limits of the magnetic media much more than
the old MFM drives ever did by encoding data with much smaller magnetic
domains, closer to the physical capacity of the magnetic media.  If these
drives require sophisticated signal processing just to read the most recently
written data, reading overwritten layers is also correspondingly more
difficult.  A good scrubbing with random data will do about as well as can be
expected.

To deal with all these types of drives in one overwrite pattern, SFS uses the
following sequence of 30 consecutive writes to erase data:

   1.  Random
   2.  0000..., MFM encoded to 01010101...
   3.  1111..., MFM encoded to 10101010...
   4.  Random
   5.  010010..., (2,7) RLL encoded to 100100100100...
   6.  100100..., (2,7) RLL encoded to 010010010010...
   7.  001001..., (2,7) RLL encoded to 001001001001...
   8.  Random
   9.  00110011..., (1,7) RLL encoded to 010101010101...
  10.  11001100..., (1,7) RLL encoded to 101010101010...
  11.  01100110..., (1,7) misaligned RLL encoded to 010101010101...
  12.  10011001..., (1,7) misaligned RLL encoded to 101010101010...
  13.  Random
  14.  1111..., MFM encoded to 10101010...
  15.  0000..., MFM encoded to 01010101...
  16.  Random
  17.  001001..., (2,7) RLL encoded to 001001001001...
  18.  100100..., (2,7) RLL encoded to 010010010010...
  19.  010010..., (2,7) RLL encoded to 100100100100...
  20.  Random
  21.  11001100..., (1,7) RLL encoded to 101010101010...
  22.  00110011..., (1,7) RLL encoded to 010101010101...
  23.  10011001..., (1,7) misaligned RLL encoded to 101010101010...
  24.  01100110..., (1,7) misaligned RLL encoded to 010101010101...
  25.  Random
  26.  0000..., MFM encoded to 01010101...
  27.  1111..., MFM encoded to 10101010...
  28.  Random
  29.  Random
  30.  Random

All patterns are repeated twice, once in each order, and MFM is repeated three
times, because MFM drives are generally the lowest density, and thus
particularly easy to examine.  If the device being written to supports cacheing
or buffering of data, SFS will attempt to disable the buffering of data to
ensure physical disk writes are performed (for example by setting the Force
Unit Access bit during SCSI-2 Group 1 write commands).

There is a commonly-held belief that there is a US government standard for
declassifying magnetic media which simply involves overwriting data on it three
times.  There are in fact a number of standards[1] which contain simple phrases
such as "Magnetic disks, drums, and other similar rigid storage devices shall
be sanitized by overwriting all storage locations with any character, then the
complement of the character (e.g., binary ones and binary zeros) alternately a
minimum of three times".  However this simple description is usually
reinterpreted by the appropriate government agencies to a level which often
makes physical destruction of the media and its replacement with new media
preferable to attempting any declassification by overwriting the data (the
(classified) standards for truly declassifying magnetic media probably involve
concentrated acid, furnaces, belt sanders, or any combination of the above[2]).

The use of such extreme measures is necessary not only because data recovery
from the actual tracks itself may (with some effort) be possible, but because
of factors like intelligent drives which keep so-called "alternative cylinders"
on a disk free to allow dynamic re-allocation of data to one of these tracks in
case a disk block develops errors.  The original block is no longer accessible
through any sort of normal access mechanism, and the data on it can't be
destroyed without going through some unusual contortions which tend to be
highly hardware-dependant.  Other complications include the use of journaling
filesystems which keep track of previous generations of data, and disk
compression software or hardware which will compress a simple repeated
overwrite pattern to nothing and leave the original data intact on the disk[3].
Therefore if "overwriting all storage locations" is interpreted to mean
"exposing the entire reading surface to a magnetic field having a strength at
the recording surface greater than the field intensity at which it was
recorded", the method does have merit.  Unfortunately it is virtually
impossible to get at all storage locations, and simple-minded methods such as
trying to write patterns to the storage allocated to a file in order to erase
it don't even come close to this target.  The overwrite method used by SFS does
come reasonably close by attempting to create a rapidly-fluctuating magnetic
field over all physically accessible sectors which make up a disk volume,
creating the same effect as a degaussing tool used to erase magnetic fields.

Another consideration which needs to be taken into account when trying to erase
data through software is that drives conforming to some of the higher-level
protocols such as the various SCSI standards are relatively free to interpret
commands sent to them in whichever way they choose (as long as they still
conform to the SCSI specification).  Thus some drives, if sent a FORMAT UNIT
command may return immediately without performing any action, may simply
perform a read test on the entire disk (the most common option), or may
actually write data to the disk[4][5].  This is rather common among newer
drives which can't directly be low-level formatted, unlike older ST-412 and
ST-506 MFM or RLL drives.  For example trying to format an IDE drive generally
has little effect - a low-level format generally isn't possible, and the
standard DOS `format' command simply writes a boot record, FAT, and root
directory, performs a quick scan for bad sectors, and exits.

Therefore if the data is very sensitive and is stored on floppy disk, it can
best be destroyed by removing the media from the disk liner and burning it.
Disks are relatively cheap, and can easily be replaced.  Permanently destroying
data on fixed disks is less simple, but the multiple-overwrite option used by
SFS at least makes it quite challenging (and expensive) to recover any
information.

Footnote [1]: Among others there is the Department of Defense standard DoD
              5200.28-M, Army standard AR 380-19, Navy standards OPNAVINST
              5510.1H and NAVSO P-5239-26, Air Force standard AFSSI-5020, and
              Department of Energy standard DOE 5637.1.

Footnote [2]: The UK Ministry of Defence grinds down disk platters and then
              supposedly stores the (still-classified) dust for a decade or
              more.  Rumours that they remove programmers brains for storage in
              order to erase the classified information they contain are
              probably unfounded.

Footnote [3]: From a posting to the usenet alt.security newsgroup on 1 August
              1994, article-ID <31c75s$[e-mail]>: "I got fired
              from my job and told to clean my desk, so I immediately went to
              my office and ran Norton WipeDisk on my hard drive, which
              contained much of the work I had done and also my contact list,
              letters, games, and so on.  Unfortunately, I had DoubleSpaced it
              and the files were easily recovered".

Footnote [4]: Again it may be possible to bypass this using highly hardware-
              specific methods.  For example Quantum SCSI drives manufactured a
              few years ago could be forced to write data to disk during a
              format by changing the sector filler byte before the format
              command was issued.

Footnote [5]: The SCSI-2 standard includes an initialization pattern (IP)
              option for the FORMAT UNIT command (Section 8.2.1.2), however it
              is not clear how well this is supported by existing drives.