Chapter 10
Using Algorithms
Think
of security—data security, communications security, information
security,
whatever—as a chain. The security of the entire system is only as
strong
as the weakest link. Everything has to be secure: cryptographic
algorithms,
protocols, key management, and more. If your algorithms are great
but
your random-number generator stinks, any smart cryptanalyst is going to
attack
your system through the random-number generation. If you patch that
hole
but forget to securely erase a memory location that contains the key, a
cryptanalyst
will break your system via that route. If you do everything right
and
accidentally e-mail a copy of your secure files to The Wall Street Journal,
you
might as well not have bothered.
It’s
not fair. As the designer of a secure system, you have to think of every
possible
means of attack and protect against them all, but a cryptanalyst only
has to
find one hole in your security and exploit it.
Cryptography
is only a part of security, and often a very small part. It is the
mathematics
of making a system secure, which is different from actually
making
a system secure. Cryptography has its “size queens”: people who
spend
so much time arguing about how long a key should be that they forget
about
everything else. If the secret police want to know what is on your
computer,
it is far easier for them to break into your house and install a camera
that
can record what is on your computer screen than it is for them to
cryptanalze
your hard drive.
Additionally,
the traditional view of computer cryptography as “spy versus
spy”
technology is becoming increasingly inappropriate. Over 99 percent of
the
cryptography used in the world is not protecting military secrets; it’s in
applications
such as bank cards, pay-TV, road tolls, office building and
computer
access tokens, lottery terminals, and prepayment electricity meters
[43,44].
In these applications, the role of cryptography is to make petty crime
slightly
more difficult; the paradigm of the well-funded adversary with a rabbit
warren
of cryptanalysts and roomsful of computers just doesn’t apply.
Most of
those applications have used lousy cryptography, but successful
attacks
against them had nothing to do with cryptanalysis. They involved
crooked
employees, clever sting operations, stupid implementations,
integration
blunders, and random idiocies. (I strongly recommend Ross
Anderson’s
paper, “Why Cryptosytems Fail” [44]; it should be required
reading
for anyone involved in this field.) Even the NSA has admitted that
most
security failures in its area of interest are due to failures in
implementation,
and not failures in algorithms or protocols [1119]. In these
instances
it didn’t matter how good the cryptography was; the successful
attacks
bypassed it completely.
10.1 Choosing an Algorithm
When it
comes to evaluating and choosing algorithms, people have several
alternatives:
— They
can choose a published algorithm, based on the belief that a
published
algorithm has been scrutinized by many cryptographers; if no
one has
broken the algorithm yet, then it must be pretty good.
— They
can trust a manufacturer, based on the belief that a well-known
manufacturer
has a reputation to uphold and is unlikely to risk that
reputation
by selling equipment or programs with inferior algorithms.
— They
can trust a private consultant, based on the belief that an
impartial
consultant is best equipped to make a reliable evaluation of
different
algorithms.
— They
can trust the government, based on the belief that the
government
is trustworthy and wouldn’t steer its citizens wrong.
— They
can write their own algorithms, based on the belief that their
cryptographic
ability is second-to-none and that they should trust
nobody
but themselves.
Any of
these alternatives is problematic, but the first seems to be the most
sensible.
Putting your trust in a single manufacturer, consultant, or government
is
asking for trouble. Most people who call themselves security consultants
(even
those from big-name firms) usually don’t know anything about
encryption.
Most security product manufacturers are no better. The NSA has
some of
the world’s best cryptographers working for it, but they’re not telling
all
they know. They have their own interests to further which are not congruent
with
those of their citizens. And even if you’re a genius, writing your own
algorithm
and then using it without any peer review is just plain foolish.
The
algorithms in this book are public. Most have appeared in the open
literature
and many have been cryptanalyzed by experts in the field. I list all
published
results, both positive and negative. I don’t have access to the
cryptanalysis
done by any of the myriad military security organizations in the
world
(which are probably better than the academic institutions—they’ve been
doing
it longer and are better funded), so it is possible that these algorithms are
easier
to break than it appears. Even so, it is far more likely that they are more
secure
than an algorithm designed and implemented in secret in some
corporate
basement.
The
hole in all this reasoning is that we don’t know the abilities of the various
military
cryptanalysis organizations.
What
algorithms can the NSA break? For the majority of us, there’s really no
way of
knowing. If you are arrested with a DES-encrypted computer hard
drive,
the FBI is unlikely to introduce the decrypted plaintext at your trial; the
fact
that they can break an algorithm is often a bigger secret than any
information
that is recovered. During WWII, the Allies were forbidden from
using
decrypted German Ultra traffic unless they could have plausibly gotten
the
information elsewhere. The only way to get the NSA to admit to the ability
to
break a given algorithm is to encrypt something so valuable that its public
dissemination
is worth the admission. Or, better yet, create a really funny joke
and
send it via encrypted e-mail to shady characters in shadowy countries.
NSA
employees are people, too; I doubt even they can keep a good joke secret.
A good
working assumption is that the NSA can read any message that it
chooses,
but that it cannot read all messages that it chooses. The NSA is
limited
by resources, and has to pick and choose among its various targets.
Another
good assumption is that they prefer breaking knuckles to breaking
codes;
this preference is so strong that they will only resort to breaking codes
when
they wish to preserve the secret that they have read the message.
In any
case, the best most of us can do is to choose among public algorithms
that
have withstood a reasonable amount of public scrutiny and cryptanalysis.
Previous
Table of Contents Next
Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms
& Conditions, Copyright
© 1996-2000 EarthWeb Inc.
All rights reserved. Reproduction whole or in part in any form or medium
without express written permission of EarthWeb is
prohibited. Read EarthWeb's privacy statement.
Brief Full
Advanced
Search
Search Tips
To access the contents, click the chapter and section titles.
Applied
Cryptography, Second Edition: Protocols, Algorthms, and Source
Code in
C (cloth)
(Publisher:
John Wiley & Sons, Inc.)
Author(s):
Bruce Schneier
ISBN:
0471128457
Publication
Date: 01/01/96
Search this book:
Previous
Table of Contents Next
Algorithms
for Export
Algorithms
for export out of the United States must be approved by the U.S.
government
(actually, by the NSA—see Section 25.1). It is widely believed
that
these export-approved algorithms can be broken by the NSA. Although no
one has
admitted this on the record, these are some of the things the NSA is
rumored
to privately suggest to companies wishing to export their
cryptographic
products:
— Leak a
key bit once in a while, embedded in the ciphertext.
— “Dumb
down” the effective key to something in the 30-bit range.
For
example, while the algorithm might accept a 100-bit key, most of
those
keys might be equivalent.
— Use a
fixed IV, or encrypt a fixed header at the beginning of each
encrypted
message. This facilitates a known-plaintext attack.
— Generate
a few random bytes, encrypt them with the key, and then
put
both the plaintext and the ciphertext of those random bytes at the
beginning
of the encrypted message. This also facilitates a
known-plaintext
attack.
NSA
gets a copy of the source code, but the algorithm’s details remain secret
from
everyone else. Certainly no one advertises any of these deliberate
weaknesses,
but beware if you buy a U.S. encryption product that has been
approved
for export.
10.2 Public-Key Cryptography versus Symmetric
Cryptography
Which
is better, public-key cryptography or symmetric cryptography? This
question
doesn’t make any sense, but has been debated since public-key
Go!
Keyword
-----------
Go!
cryptography
was invented. The debate assumes that the two types of
cryptography
can be compared on an equal footing. They can’t.
Needham
and Schroeder [1159] pointed out that the number and length of
messages
are far greater with public-key algorithms than with symmetric
algorithms.
Their conclusion was that the symmetric algorithm was more
efficient
than the public-key algorithm. While true, this analysis overlooks the
significant
security benefits of public-key cryptography.
Whitfield
Diffie writes [492,494]:
In
viewing public-key cryptography as a new form of
cryptosystem
rather than a new form of key management, I set the
stage
for criticism on grounds of both security and performance.
Opponents
were quick to point out that the RSA system ran about
one-thousandth
as fast as DES and required keys about ten times
as
large. Although it had been obvious from the beginning that the
use of
public key systems could be limited to exchanging keys for
conventional
[symmetric] cryptography, it was not immediately
clear
that this was necessary. In this context, the proposal to build
hybrid systems
[879] was hailed as a discovery in its own right.
Public-key
cryptography and symmetric cryptography are different sorts of
animals;
they solve different sorts of problems. Symmetric cryptography is
best
for encrypting data. It is orders of magnitude faster and is not susceptible
to chosen-ciphertext
attacks. Public-key cryptography can do things that
symmetric
cryptography can’t; it is best for key management and a myriad of
protocols
discussed in Part I.
Other
primitives were discussed in Part I: one-way hash functions, message
authentication
codes, and so on. Table 10.1 lists different types of algorithms
and
their properties [804].
10.3 Encrypting Communications Channels
This is
the classic Alice and Bob problem: Alice wants to send Bob a secure
message.
What does she do? She encrypts the message.
In
theory, this encryption can take place at any layer in the OSI (Open Systems
Interconnect)
communications model. (See the OSI security architecture
standard
for more information [305].) In practice, it takes place either at the
lowest
layers (one and two) or at higher layers. If it takes place at the lowest
layers,
it is called link-by-link encryption; everything going through a
particular
data link is encrypted. If it takes place at higher layers, it is called
end-to-end
encryption; the data are encrypted selectively and stay
encrypted
until
they are decrypted by the intended final recipient. Each approach has its
own
benefits and drawbacks.
Table
10.1
Classes
of Algorithms
Algorithm
Confidentiality Authentication Integrity
Key
Management
Symmetric
encryption
algorithms
Yes No
No Yes
Public-key
encryption
algorithms
Yes No
No Yes
Digital
signature
algorithms
No Yes
Yes No
Key-agreement
algorithms
Yes
Optional No Yes
One-way
hash
functions
No No
Yes No
Message
authentication
codes
No Yes
Yes No
Link-by-Link
Encryption
The
easiest place to add encryption is at the physical layer (see Figure 10.1).
This is
called link-by-link encryption. The interfaces to the physical layer are
generally
standardized and it is easy to connect hardware encryption devices at
this
point. These devices encrypt all data passing through them, including data,
routing
information, and protocol information. They can be used on any type
of
digital communication link. On the other hand, any intelligent switching or
storing
nodes between the sender and the receiver need to decrypt the data
stream
before processing it.
This
type of encryption is very effective. Because everything is encrypted, a
cryptanalyst
can get no information about the structure of the information. He
has no
idea who is talking to whom, how long the messages they are sending
are,
what times of day they communicate, and so on. This is called traffic-flow
security: the
enemy is not only denied access to the information, but also
access
to the knowledge of where and how much information is flowing.
Security
does not depend on any traffic management techniques. Key
management
is also simple; only the two endpoints of the line need a common
key,
and they can change their key independently from the rest of the network.
Figure
10.1 Link encryption.
Previous
Table of Contents Next
Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms
& Conditions, Copyright
© 1996-2000 EarthWeb Inc.
All rights reserved. Reproduction whole or in part in any form or medium
without express written permission of EarthWeb is
prohibited. Read EarthWeb's privacy statement.
Brief Full
Advanced
Search
Search Tips
To access the contents, click the chapter and section titles.
Applied
Cryptography, Second Edition: Protocols, Algorthms, and Source
Code in
C (cloth)
(Publisher:
John Wiley & Sons, Inc.)
Author(s):
Bruce Schneier
ISBN:
0471128457
Publication
Date: 01/01/96
Search this book:
Previous
Table of Contents Next
Imagine
a synchronous communications line, encrypted using 1-bit CFB. After
initialization,
the line can run indefinitely, recovering automatically from bit or
synchronization
errors. The line encrypts whenever messages are sent from
one end
to the other; otherwise it just encrypts and decrypts random data. Eve
has no
idea when messages are being sent and when they are not; she has no
idea
when messages begin and end. All she sees is an endless stream of
random-looking
bits.
If the
communications line is asynchronous, the same 1-bit CFB mode can be
used.
The difference is that the adversary can get information about the rate of
transmission.
If this information must be concealed, make some provision for
passing
dummy messages during idle times.
The
biggest problem with encryption at the physical layer is that each physical
link in
the network needs to be encrypted: Leaving any link unencrypted
jeopardizes
the security of the entire network. If the network is large, the cost
may
quickly become prohibitive for this kind of encryption.
Additionally,
every node in the network must be protected, since it processes
unencrypted
data. If all the network’s users trust one another, and all nodes are
in
secure locations, this may be tolerable. But this is unlikely. Even in a single
corporation,
information might have to be kept secret within a department. If
the
network accidentally misroutes information, anyone can read it. Table 10.2
summarizes
the pros and cons of link-by-link encryption.
End-to-End
Encryption
Another
approach is to put encryption equipment between the network layer
and the
transport layer. The encryption device must understand the data
according
to the protocols up to layer three and encrypt only the transport data
units,
which are then recombined with the unencrypted routing information
Go!
Keyword
-----------
Go!
and
sent to lower layers for transmission.
This
approach avoids the encryption/decryption problem at the physical layer.
By
providing end-to-end encryption, the data remains encrypted until it
reaches
its final destination (see Figure 10.2). The primary problem with
end-to-end
encryption is that the routing information for the data is not
encrypted;
a good cryptanalyst can learn much from who is talking to whom,
at what
times and for how long, without ever knowing the contents of those
conversations.
Key management is also more difficult, since individual users
must
make sure they have common keys.
Table
10.2
Link-by-Link
Encryption: Advantages and Disadvantages
Advantages:
Easier
operation, since it can be made transparent to the user. That is,
everything
is encrypted before being sent over the link.
Only
one set of keys per link is required.
Provides
traffic-flow security, since any routing information is
encrypted.
Encryption
is online.
Disadvantages:
Data is
exposed in the intermediate nodes.
Figure
10.2 End-to-end encryption.
Building
end-to-end encryption equipment is difficult. Each particular
communications
system has its own protocols. Sometimes the interfaces
between
the levels are not well-defined, making the task even more difficult.
If
encryption takes place at a high layer of the communications architecture,
like
the applications layer or the presentation layer, then it can be independent
of the
type of communication network used. It is still end-to-end encryption,
but the
encryption implementation does not have to bother about line codes,
synchronization
between modems, physical interfaces, and so forth. In the
early
days of electromechanical cryptography, encryption and decryption took
place
entirely offline; this is only one step removed from that.
Encryption
at these high layers interacts with the user software. This software
is
different for different computer architectures, and so the encryption must be
optimized
for different computer systems. Encryption can occur in the
software
itself or in specialized hardware. In the latter case, the computer will
send
the data to the specialized hardware for encryption before sending it to
lower
layers of the communication architecture for transmission. This process
requires
some intelligence and is not suitable for dumb terminals.
Additionally,
there may be compatibility problems with different types of
computers.
The
major disadvantage of end-to-end encryption is that it allows traffic
analysis.
Traffic analysis is the analysis of encrypted messages: where they
come
from, where they go to, how long they are, when they are sent, how
frequent
or infrequent they are, whether they coincide with outside events like
meetings,
and more. A lot of good information is buried in that data, and a
cryptanalyst
will want to get his hands on it. Table 10.3 presents the positive
and
negative aspects of end-to-end encryption.
Combining
the Two
Table
10.4, primarily from [1244], compares link-by-link and end-to-end
encryption.
Combining the two, while most expensive, is the most effective
way of
securing a network. Encryption of each physical link makes any
analysis
of the routing information impossible, while end-to-end encryption
reduces
the threat of unencrypted data at the various nodes in the network. Key
management
for the two schemes can be completely separate: The network
managers
can take care of encryption at the physical level, while the individual
users
have responsibility for end-to-end encryption.
Table
10.3
End-to-End
Encryption: Advantages and Disadvantages
Advantages:
Higher
secrecy level.
Disadvantages:
Requires
a more complex key-management system.
Traffic
analysis is possible, since routing information is not
encrypted.
Encryption
is offline.
10.4 Encrypting Data for Storage
Encrypting
data for storage and later retrieval can also be thought of in the
Alice
and Bob model. Alice is still sending a message to Bob, but in this case
“Bob”
is Alice at some future time. However, the problem is fundamentally
different.
In
communications channels, messages in transit have no intrinsic value. If
Bob
doesn’t receive a particular message, Alice can always resend it. This is
not
true for data encrypted for storage. If Alice can’t decrypt her message, she
can’t
go back in time and re-encrypt it. She has lost it forever. This means that
encryption
applications for data storage should have some mechanisms to
prevent
unrecoverable errors from creeping into the ciphertext.
The
encryption key has the same value as the message, only it is smaller. In
effect,
cryptography converts large secrets into smaller ones. Being smaller,
they
can be easily lost. Key management procedures should assume that the
same
keys will be used again and again, and that data may sit on a disk for
years
before being decrypted.
Furthermore,
the keys will be around for a long time. A key used on a
communications
link should, ideally, exist only for the length of the
communication.
A key used for data storage might be needed for years, and
hence
must be stored securely for years.
Other
problems particular to encrypting computer data for storage were listed
in
[357]:
— The
data may also exist in plaintext form, either on another disk, in
another
computer, or on paper. There is much more opportunity for a
cryptanalyst
to perform a known-plaintext attack.
— In
database applications, pieces of data may be smaller than the
block
size of most algorithms. This will cause the ciphertext to be
considerably
larger than the plaintext.
— The
speed of I/O devices demands fast encryption and decryption,
and
will probably require encryption hardware. In some applications,
special
high-speed algorithms may be required.
— Safe,
long-term storage for keys is required.
— Key
management is much more complicated, since different people
need
access to different files, different portions of the same file, and so
forth.
Previous
Table of Contents Next
Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms
& Conditions, Copyright
© 1996-2000 EarthWeb Inc.
All rights reserved. Reproduction whole or in part in any form or medium
without express written permission of EarthWeb is
prohibited. Read EarthWeb's privacy statement.
Brief Full
Advanced
Search
Search Tips
To access the contents, click the chapter and section titles.
Applied
Cryptography, Second Edition: Protocols, Algorthms, and Source
Code in
C (cloth)
(Publisher:
John Wiley & Sons, Inc.)
Author(s):
Bruce Schneier
ISBN:
0471128457
Publication
Date: 01/01/96
Search this book:
Previous
Table of Contents Next
Table
10.4
Comparing
Link-by-Link and End-to-End Encryption
Link-by-link
encryption End-to-end encryption
Security
within Hosts
Message
exposed in sending host Message encrypted in sending host
Message
exposed in intermediate
nodes
Message
encrypted inintermediate
nodes
Role of
User
Applied
by sending host Applied by sending process
Invisible
to user User applies encryption
Host
maintains encryption User must find algorithm
One
facility for all users User selects encryption
Can be
done in hardware More easily done in software
All or
no messages encrypted User chooses to encrypt or not, for
each
message
Implementation
Concerns
Requires
one key per host pair Requires one key per user pair
Requires
encryption hardware or
software
at each host
Requires
encryption hardware or
software
at each node
Provides
node authentication Provides user authentication
If the
encrypted files are not structured as records and fields, such as text files,
retrieval
is easier: The entire file is decrypted before use. If the encrypted files
are
database files, this solution is problematic. Decrypting the entire database
to
access a single record is inefficient, but encrypting records independently
Go!
Keyword
-----------
Go!
might
be susceptible to a block-replay kind of attack.
In
addition, you must make sure the unencrypted file is erased after encryption
(see
Section 10.9). For further details and insights, consult [425,569].
Dereferencing
Keys
When
encrypting a large hard drive, you have two options. You can encrypt all
the
data using a single key. This gives a cryptanalyst a large amount of
ciphertext
to analyze and makes it impossible to allow multiple users to see
only
parts of the drive. Or, you can encrypt each file with a different key,
forcing
users to memorize a different key for each file.
The
solution is to encrypt each file with a separate key, and to encrypt the keys
with
another key known by the users. Each user only has to remember that one
key.
Different users can have different subsets of the file-encryption keys
encrypted
with their key. And there can even be a master key under which
every
file-encryption key is encrypted. This is even more secure because the
file-encryption
keys are random and less susceptible to a dictionary attack.
Driver-Level
vs. File-Level Encryption
There
are two ways to encrypt a hard drive: at the file level and at the driver
level.
Encryption at the file level means that every file is encrypted separately.
To use
a file that’s been encrypted, you must first decrypt the file, then use it,
and
then re-encrypt it.
Driver-level
encryption maintains a logical drive on the user’s machine that
has all
data on it encrypted. If done well, this can provide security that, beyond
choosing
good passwords, requires little worry on the part of the user. The
driver
must be considerably more complex than a simple file-encryption
program,
however, because it must deal with the issues of being an installed
device
driver, allocation of new sectors to files, recycling of old sectors from
files,
random-access read and update requests for any data on the logical disk,
and so
on.
Typically,
the driver prompts the user for a password before starting up. This
is used
to generate the master decryption key, which may then be used to
decrypt
actual decryption keys used on different data.
Providing
Random Access to an Encrypted Drive
Most
systems expect to be able to access individual disk sectors randomly.
This
adds some complication for using many stream ciphers and block ciphers
in any
chaining mode. Several solutions are possible.
Use the
sector address to generate a unique IV for each sector being encrypted
or
decrypted. The drawback is that each sector will always be encrypted with
the
same IV. Make sure this is not a security problem.
For the
master key, generate a pseudo-random block as large as one sector.
(You
can do this by running an algorithm in OFB mode, for example.) To
encrypt
any sector, first XOR in this pseudo-random block, then encrypt
normally
with a block cipher in ECB mode. This is called ECB+OFB (see
Section
15.4).
Since
CBC and CFB are error-recovering modes, you can use all but the first
block
or two in the sector to generate the IV for that sector. For example, the
IV for
sector 3001 may be the hash of the all but the first 128 bits of the
sector’s
data. After generating the IV, encrypt normally in CBC mode. To
decrypt
the sector, you use the second 64-bit block of the sector as an IV, and
decrypt
the remainder of the sector. Then, using the decrypted data, you
regenerate
the IV and decrypt the first 128 bits.
You can
use a block cipher with a large enough block size that it can encrypt
the
whole sector at once. Crab (see Section 14.6) is an example.
10.5 Hardware Encryption versus Software
Encryption
Hardware
Until
very recently, all encryption products were in the form of specialized
hardware.
These encryption/decryption boxes plugged into a communications
line
and encrypted all the data going across that line. Although software
encryption
is becoming more prevalent today, hardware is still the
embodiment
of choice for military and serious commercial applications. The
NSA,
for example, only authorizes encryption in hardware. There are several
reasons
why this is so.
Previous
Table of Contents Next
Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms
& Conditions, Copyright
© 1996-2000 EarthWeb Inc.
All rights reserved. Reproduction whole or in part in any form or medium
without express written permission of EarthWeb is
prohibited. Read EarthWeb's privacy statement.
Brief Full
Advanced
Search
Search Tips
To access the contents, click the chapter and section titles.
Applied
Cryptography, Second Edition: Protocols, Algorthms, and Source
Code in
C (cloth)
(Publisher:
John Wiley & Sons, Inc.)
Author(s):
Bruce Schneier
ISBN:
0471128457
Publication
Date: 01/01/96
Search this book:
Previous
Table of Contents Next
Table
10.5
Comparing
File-Level and Driver-Level Encryption
File-Level
Encryption Driver-Level Encryption
Benefits:
Ease of
implementation and use.
Flexible.
Relatively
small performance penalty.
Users
can move files between different
machines
without problems.
Users
can back files up without problems.
Temporary
files, work files, and
so
forth can be kept on the secure
drive.
It’s
harder to forget to re-encrypt
something
on this kind of system.
Security
Issues:
Potential
leakage through
security-unconscious
programs. (Program
may
write file to disk for temporary
storage,
for example.)
Bad
implementations may always
re-encrypt
with same key for same
password.
Lots of
things can go wrong with
a
device-driver or
memory-resident
program.
Bad
implementations will allow
chosen-plaintext,
or even
chosen-ciphertext
attacks.
If
whole system is master-keyed
under
one password, loss of that
password
means that the attacker
gets
everything.
A more
limited set of ciphers can
reasonably
be used for this kind of
application.
For example, OFB
stream
ciphers would not work.
Usability
Problems:
Go!
Keyword
-----------
Go!
User
has to figure out what to do.
There
may be different passwords for
different
files.
Manual
encryption of selected files is the
only
access control.
There
will be a performance
penalty.
The
driver may interact in weird
ways
with Windows, OS/2 DOS
emulation,
device drivers, and so
on.
The
first is speed. As we will see in Part III, encryption algorithms consist of
many
complicated operations on plaintext bits. These are not the sorts of
operations
that are built into your run-of-the-mill computer. The two most
common
encryption algorithms, DES and RSA, run inefficiently on
general-purpose
processors. While some cryptographers have tried to make
their
algorithms more suitable for software implementation, specialized
hardware
will always win a speed race.
Additionally,
encryption is often a computation-intensive task. Tying up the
computer’s
primary processor for this is inefficient. Moving encryption to
another
chip, even if that chip is just another processor, makes the whole
system
faster.
The
second reason is security. An encryption algorithm running on a
generalized
computer has no physical protection. Mallory can go in with
various
debugging tools and surreptitiously modify the algorithm without
anyone
ever realizing it. Hardware encryption devices can be securely
encapsulated
to prevent this. Tamperproof boxes can prevent someone from
modifying
a hardware encryption device. Special-purpose VLSI chips can be
coated
with a chemical such that any attempt to access their interior will result
in the
destruction of the chip’s logic. The U.S. government’s Clipper and
Capstone
chips (see Sections 24.16 and 24.17) are designed to be tamperproof.
The
chips can be designed so that it is impossible for Mallory to read the
unencrypted
key.
IBM
developed a cryptographic system for encrypting data and
communications
on mainframe computers [515,1027]. It includes
tamper-resistant
modules to hold keys. This system is discussed in Section
24.1.
Electromagnetic
radiation can sometimes reveal what is going on inside a
piece
of electronic equipment. Dedicated encryption boxes can be shielded, so
that
they leak no compromising information. General-purpose computers can
be
shielded as well, but it is a far more complex problem. The U.S. military
calls
this TEMPEST; it’s a subject well beyond the scope of this book.
The final
reason for the prevalence of hardware is the ease of installation. Most
encryption
applications don’t involve general-purpose computers. People may
wish to
encrypt their telephone conversations, facsimile transmissions, or data
links.
It is cheaper to put special-purpose encryption hardware in the
telephones,
facsimile machines, and modems than it is to put in a
microprocessor
and software.
Even
when the encrypted data comes from a computer, it is easier to install a
dedicated
hardware encryption device than it is to modify the computer’s
system
software. Encryption should be invisible; it should not hamper the user.
The
only way to do this in software is to write encryption deep into the
operating
system. This isn’t easy. On the other hand, even a computer
neophyte
can plug an encryption box between his computer and his external
modem.
The
three basic kinds of encryption hardware on the market today are:
self-contained
encryption modules (that perform functions such as password
verification
and key management for banks), dedicated encryption boxes for
communications
links, and boards that plug into personal computers.
Some
encryption boxes are designed for certain types of communications
links,
such as T-1 encryption boxes that are designed not to encrypt
synchronization
bits. There are different boxes for synchronous and
asynchronous
communications lines. Newer boxes tend to accept higher bit
rates
and are more versatile.
Even
so, many of these devices have some incompatibilities. Buyers should be
aware of
this and be well-versed in their particular needs, lest they find
themselves
the owners of encryption equipment unable to perform the task at
hand.
Pay attention to restrictions in hardware type, operating system,
applications
software, network, and so forth.
PC-board
encryptors usually encrypt everything written to the hard disk and
can be
configured to encrypt everything sent to the floppy disk and serial port
as
well. These boards are not shielded against electromagnetic radiation or
physical
interference, since there would be no benefit in protecting the boards
if the
computer remained unaffected.
More
companies are starting to put encryption hardware into their
communications
equipment. Secure telephones, facsimile machines, and
modems
are all available.
Internal
key management for these devices is generally secure, although there
are as
many different schemes as there are equipment vendors. Some schemes
are
more suited for one situation than another, and buyers should know what
kind of
key management is incorporated into the encryption box and what they
are
expected to provide themselves.
Software
Any
encryption algorithm can be implemented in software. The disadvantages
are in
speed, cost, and ease of modification (or manipulation). The advantages
are in
flexibility and portability, ease of use, and ease of upgrade. The
algorithms
written in C at the end of this book can be implemented, with little
modification,
on any computer. They can be inexpensively copied and
installed
on many machines. They can be incorporated into larger applications,
such as
communications programs or word processors.
Previous
Table of Contents Next
Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms
& Conditions, Copyright
© 1996-2000 EarthWeb Inc.
All rights reserved. Reproduction whole or in part in any form or medium
without express written permission of EarthWeb is
prohibited. Read EarthWeb's privacy statement.
Brief Full
Advanced
Search
Search Tips
To access the contents, click the chapter and section titles.
Applied
Cryptography, Second Edition: Protocols, Algorthms, and Source
Code in
C (cloth)
(Publisher:
John Wiley & Sons, Inc.)
Author(s):
Bruce Schneier
ISBN:
0471128457
Publication
Date: 01/01/96
Search this book:
Previous
Table of Contents Next
Software
encryption programs are popular and are available for all major
operating
systems. These are meant to protect individual files; the user
generally
has to manually encrypt and decrypt specific files. It is important
that
the key management scheme be secure: The keys should not be stored on
disk
anywhere (or even written to a place in memory from where the processor
swaps
out to disk). Keys and unencrypted files should be erased after
encryption.
Many programs are sloppy in this regard, and a user has to choose
carefully.
Of
course, Mallory can always replace the software encryption algorithm with
something
lousy. But for most users, that isn’t a problem. If Mallory can break
into
our office and modify our encryption program, he can also put a hidden
camera
on the wall, a wiretap on the telephone, and a TEMPEST detector
down
the street. If Mallory is that much more powerful than the user, the user
has
lost the game before it starts.
10.6 Compression, Encoding, and Encryption
Using a
data compression algorithm together with an encryption algorithm
makes
sense for two reasons:
Cryptanalysis
relies on exploiting redundancies in the plaintext;
compressing
a file before encryption reduces these redundancies.
Encryption
is time-consuming; compressing a file before encryption
speeds
up the entire process.
The
important thing to remember is to compress before encryption. If the
encryption
algorithm is any good, the ciphertext will not be compressible; it
will
look like random data. (This makes a reasonable test of an encryption
algorithm;
if the ciphertext can be compressed, then the algorithm probably
isn’t
very good.)
Go!
Keyword
-----------
Go!
If you
are going to add any type of transmission encoding or error detection
and
recovery, remember to add that after encryption. If there is noise in the
communications
path, decryption’s error-extension properties will only make
that
noise worse. Figure 10.3 summarizes these steps.
10.7 Detecting Encryption
How
does Eve detect an encrypted file? Eve is in the spy business, so this is an
important
question. Imagine that she’s eavesdropping on a network where
messages
are flying in all directions at high speeds; she has to pick out the
interesting
ones. Encrypted files are certainly interesting, but how does she
know
they are encrypted?
Generally,
she relies on the fact that most popular encryption programs have
well-defined
headers. Electronic-mail messages encrypted with either PEM or
PGP
(see Sections 24.10 and 24.12) are easy to identify for that reason.
Other
file encryptors just produce a ciphertext file of seemingly random bits.
How can
she distinguish it from any other file of seemingly random bits?
There
is no sure way, but Eve can try a number of things:
— Examine
the file. ASCII text is easy to spot. Other file formats, such
as
TIFF, TeX, C, Postscript, G3 facsimile, or Microsoft Excel, have
standard
identifying characteristics. Executable code is detectable, as
well.
UNIX files often have “magic numbers” that can be detected.
Figure
10.3 Encryption with compression and error control.
— Try to
uncompress the file, using the major compression algorithms.
If the
file is compressed (and not encrypted), this should yield the original file.
— Try to
compress the file. If the file is ciphertext (and the algorithm is
good),
then the probability that the file can be appreciably compressed by a
general-purpose
compression routine is small. (By appreciably, I mean more
than 1
or 2 percent.) If it is something else (a binary image or a binary data
file,
for example) it probably can be compressed.
Any
file that cannot be compressed and is not already compressed is probably
ciphertext.
(Of course, it is possible to specifically make ciphertext that is
compressible.)
Identifying the algorithm is a whole lot harder. If the algorithm
is
good, you can’t. If the algorithm has some slight biases, it might be possible
to
recognize those biases in the file. However, the biases have to be pretty
significant
or the file has to be pretty big in order for this to work.
10.8 Hiding Ciphertext in Ciphertext
Alice
and Bob have been sending encrypted messages to each other for the
past
year. Eve has been collecting them all, but she cannot decrypt any of
them.
Finally, the secret police tire of all this unreadable ciphertext and arrest
the
pair. “Give us your encryption keys,” they demand. Alice and Bob refuse,
but
then they notice the thumbscrews. What can they do?
Wouldn’t
it be nice to be able to encrypt a file such that there are two possible
decryptions,
each with a different key. Alice could encrypt a real message to
Bob in
one of the keys and some innocuous message in the other key. If Alice
were
caught, she could surrender the key to the innocuous message and keep
the
real key secret.
The
easiest way to do this is with one-time pads. Let P be the plaintext, D
the
dummy
plaintext, C the ciphertext, K the real key, and K’ the
dummy key.
Alice
encrypts P:
P • K =
C
Alice
and Bob share K, so Bob can decrypt C:
C • K =
P
If the
secret police ever force them to surrender their key, they don’t surrender
K, but
instead surrender:
K’ = C •
D
The
police then recover the dummy plaintext:
C • K’
= D
Previous
Table of Contents Next
Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms
& Conditions, Copyright
© 1996-2000 EarthWeb Inc.
All rights reserved. Reproduction whole or in part in any form or medium
without express written permission of EarthWeb is
prohibited. Read EarthWeb's privacy statement.
Brief Full
Advanced
Search
Search Tips
To access the contents, click the chapter and section titles.
Applied
Cryptography, Second Edition: Protocols, Algorthms, and Source
Code in
C (cloth)
(Publisher:
John Wiley & Sons, Inc.)
Author(s):
Bruce Schneier
ISBN:
0471128457
Publication
Date: 01/01/96
Search this book:
Previous
Table of Contents Next
Since
these are one-time pads and K is completely random, there is no way to
prove
that K’ was not the real key. To make matters more convincing, Alice
and Bob
should concoct some mildly incriminating dummy messages to take
the
place of the really incriminating real messages. A pair of Israeli spies once
did
this.
Alice
could take P and encrypt it with her favorite algorithm and key K to
get
C. Then
she takes C and XORs it with some piece of mundane
plaintext—Pride
and Prejudice for example, to get K’. She stores both C and
the XOR
on her hard disk. Now, when the secret police interrogate her, she
can
explain that she is an amateur cryptographer and that K’ is a merely
one-time
pad for C. The secret police might suspect something, but unless they
know K
they cannot prove that Alice’s explanation isn’t valid.
Another
method is to encrypt P with a symmetric algorithm and K, and D
with
K’.
Intertwine bits (or bytes) of the ciphertext to make the final ciphertexts. If
the
secret police demand the key, Alice gives them K’ and says that the
alternating
bits (or bytes) are random noise designed to frustrate cryptanalysis.
The
trouble is the explanation is so implausible that the secret police will
probably
not believe her (especially considering it is suggested in this book).
A
better way is for Alice to create a dummy message, D, such that the
concatenation
of P and D, compressed, is about the same size as D. Call
this
concatenation
P’. Alice then encrypts P’ with whatever algorithm she and Bob
share
to get C. Then she sends C to Bob. Bob decrypts C to get P’,
and then P
and D.
Then they both compute C • D = K’. This K’ becomes the dummy
one-time
pad they use in case the secret police break their doors down. Alice
has to
transmit D so that hers and Bob’s alibis match.
Another
method is for Alice to take an innocuous message and run it through
some
error-correcting code. Then she can introduce errors that correspond to
the
secret encrypted message. On the receiving end, Bob can extract the errors
Go!
Keyword
-----------
Go!
to
reconstruct the secret message and decrypt it. He can also use the
error-correcting
code to recover the innocuous message. Alice and Bob might
be hard
pressed to explain to the secret police why they consistently get a 30
percent
bit-error rate on an otherwise noise-free computer network, but in
some
circumstances this scheme can work.
Finally,
Alice and Bob can use the subliminal channels in their digital
signature
algorithms (see Sections 4.2 and 23.3). This is undetectable, works
great,
but has the drawback of only allowing 20 or so characters of subliminal
text to
be sent per signed innocuous message. It really isn’t good for much
more
than sending keys.
10.9 Destroying Information
When
you delete a file on most computers, the file isn’t really deleted. The
only
thing deleted is an entry in the disk’s index file, telling the machine that
the
file is there. Many software vendors have made a fortune selling
file-recovery
software that recovers files after they have been deleted.
And
there’s yet another worry: Virtual memory means your computer can read
and
write memory to disk any time. Even if you don’t save it, you never know
when a
sensitive document you are working on is shipped off to disk. This
means
that even if you never save your plaintext data, your computer might do
it for
you. And driver-level compression programs like Stacker and
DoubleSpace
can make it even harder to predict how and where information is
stored
on a disk.
To erase
a file so that file-recovery software cannot read it, you have to
physically
write over all of the file’s bits on the disk. According to the
National
Computer Security Center [1148]:
Overwriting
is a process by which unclassified data are written to
storage
locations that previously held sensitive data.... To purge
the...storage
media, the DoD requires overwriting with a pattern,
then
its complement, and finally with another pattern; e.g.,
overwrite
first with 0011 0101, followed by 1100 1010, then 1001
0111.
The number of times an overwrite must be accomplished
depends
on the storage media, sometimes on its sensitivity, and
sometimes
on different DoD component requirements. In any
case, a
purge is not complete until a final overwrite is made using
unclassified
data.
You may
have to erase files or you may have to erase entire drives. You
should
also erase all unused space on your hard disk.
Most
commercial programs that claim to implement the DoD standard
overwrite
three times: first with all ones, then with all zeros, and finally with a
repeating
one-zero pattern. Given my general level of paranoia, I recommend
overwriting
a deleted file seven times: the first time with all ones, the second
time
with all zeros, and five times with a cryptographically secure
pseudo-random
sequence. Recent developments at the National Institute of
Standards
and Technology with electron-tunneling microscopes suggest even
that
might not be enough. Honestly, if your data is sufficiently valuable,
assume
that it is impossible to erase data completely off magnetic media. Burn
or
shred the media; it’s cheaper to buy media new than to lose your secrets.
Previous
Table of Contents Next
Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms
& Conditions, Copyright
© 1996-2000 EarthWeb Inc.
All rights reserved. Reproduction whole or in part in any form or medium
without express written permission of EarthWeb is
prohibited. Read EarthWeb's privacy statement.
Brief Full
Advanced
Search
Search Tips
To access the contents, click the chapter and section titles.
Applied
Cryptography, Second Edition: Protocols, Algorthms, and Source
Code in
C (cloth)
(Publisher:
John Wiley & Sons, Inc.)
Author(s):
Bruce Schneier
ISBN:
0471128457
Publication
Date: 01/01/96
Search this book:
Previous
Table of Contents Next
Part III
Cryptographic Algorithms
Chapter 11
Mathematical Background
11.1 Information Theory
Modern
information theory was first published in 1948 by Claude Elmwood
Shannon
[1431, 1432]. (His papers have been reprinted by the IEEE Press
[1433].)
For a good mathematical treatment of the topic, consult [593]. In this
section,
I will just sketch some important ideas.
Entropy
and Uncertainty
Information
theory defines the amount of information in a message as the
minimum
number of bits needed to encode all possible meanings of that
message,
assuming all messages are equally likely. For example, the
day-of-the-week
field in a database contains no more than 3 bits of
information,
because the information can be encoded with 3 bits:
000 = Sunday
001 = Monday
010 = Tuesday
011 = Wednesday
100 = Thursday
101 = Friday
Go!
Keyword
-----------
Go!
110 = Saturday
111 is unused
If this
information were represented by corresponding ASCII character strings,
it would
take up more memory space but would not contain any more
information.
Similarly, the “sex” field of a database contains only 1 bit of
information,
even though it might be stored as one of two 6-byte ASCII
strings:
“MALE” or “FEMALE.”
Formally,
the amount of information in a message M is measured by the
entropy
of a message, denoted by H(M). The entropy of a message
indicating
sex is
1 bit; the entropy of a message indicating the day of the week is slightly
less
than 3 bits. In general, the entropy of a message measured in bits is log2 n,
in
which n is the number of possible meanings. This assumes that each
meaning
is equally likely.
The
entropy of a message also measures its uncertainty. This is the number
of
plaintext
bits needed to be recovered when the message is scrambled in
ciphertext
in order to learn the plaintext. For example, if the ciphertext block
“QHP*5M”
is either “MALE” or “FEMALE, ” then the uncertainty of the
message
is 1. A cryptanalyst has to learn only one well-chosen bit to recover
the message.
Rate of
a Language
For a
given language, the rate of the language is
r = H(M)/N
in
which N is the length of the message. The rate of normal English takes
various
values between 1.0 bits/letter and 1.5 bits/letter, for large values of N.
Shannon,
in [1434], said that the entropy depends on the length of the text.
Specifically
he indicated a rate of 2.3 bits/letter for 8-letter chunks, but the rate
drops
to between 1.3 and 1.5 for 16-letter chunks. Thomas Cover used a
gambling
estimating technique and found an entropy of 1.3 bits/character
[386].
(I’ll use 1.3 in this book.) The absolute rate of a language is the
maximum
number of bits that can be coded in each character, assuming each
character
sequence is equally likely. If there are L characters in a language, the
absolute
rate is:
R = log2 L
This is
the maximum entropy of the individual characters.
For
English, with 26 letters, the absolute rate is log2 26, or
about 4.7 bits/letter.
It
should come as no surprise to anyone that the actual rate of English is much
less
than the absolute rate; natural language is highly redundant.
The redundancy
of a language, denoted D, is defined by:
D = R
- r
Given
that the rate of English is 1.3, the redundancy is 3.4 bits/letter. This
means
that each English character carries 3.4 bits of redundant information.
An
ASCII message that is nothing more than printed English has 1.3 bits of
information
per byte of message. This means it has 6.7 bits of redundant
information,
giving it an overall redundancy of 0.84 bits of information per bit
of
ASCII text, and an entropy of 0.16 bits of information per bit of ASCII text.
The
same message in BAUDOT, at 5 bits per character, has a redundancy of
0.74
bits per bit and an entropy of 0.26 bits per bit. Spacing, punctuation,
numbers,
and formatting modify these results.
Security
of a Cryptosystem
Shannon
defined a precise mathematical model of what it means for a
cryptosystem
to be secure. The goal of a cryptanalyst is to determine the key
K, the
plaintext P, or both. However, he may be satisfied with some
probabilistic
information about P: whether it is digitized audio, German text,
spreadsheet
data, or something else.
In most
real-world cryptanalysis, the cryptanalyst has some probabilistic
information
about P before he even starts. He probably knows the language of
the
plaintext. This language has a certain redundancy associated with it. If it is
a
message to Bob, it probably begins with “Dear Bob.” Certainly “Dear Bob”
is more
probable than “e8T&g [, m.” The purpose of cryptanalysis is to
modify
the probabilities associated with each possible plaintext. Eventually
one
plaintext will emerge from the pile of possible plaintexts as certain (or at
least,
very probable).
There
is such a thing as a cryptosystem that achieves perfect secrecy: a
cryptosystem
in which the ciphertext yields no possible information about the
plaintext
(except possibly its length). Shannon theorized that it is only possible
if the
number of possible keys is at least as large as the number of possible
messages.
In other words, the key must be at least as long as the message
itself,
and no key can be reused. In still other words, the one-time pad (see
Section
1.5) is the only cryptosystem that achieves perfect secrecy.
Perfect
secrecy aside, the ciphertext unavoidably yields some information
about
the corresponding plaintext. A good cryptographic algorithm keeps this
information
to a minimum; a good cryptanalyst exploits this information to
determine
the plaintext.
Cryptanalysts
use the natural redundancy of language to reduce the number of
possible
plaintexts. The more redundant the language, the easier it is to
cryptanalyze.
This is the reason that many real-world cryptographic
implementations
use a compression program to reduce the size of the text
before
encrypting it. Compression reduces the redundancy of a message as
well as
the work required to encrypt and decrypt.
The
entropy of a cryptosystem is a measure of the size of the keyspace, K. It
is
approximated
by the base two logarithm of the number of keys:
H(K)
= log2 K
A
cryptosystem with a 64-bit key has an entropy of 64 bits; a cryptosystem
with a
56-bit key has an entropy of 56 bits. In general, the greater the entropy,
the
harder it is to break a cryptosystem.
Previous
Table of Contents Next
Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms
& Conditions, Copyright
© 1996-2000 EarthWeb Inc.
All rights reserved. Reproduction whole or in part in any form or medium
without express written permission of EarthWeb is
prohibited. Read EarthWeb's privacy statement.
Brief Full
Advanced
Search
Search Tips
To access the contents, click the chapter and section titles.
Applied
Cryptography, Second Edition: Protocols, Algorthms, and Source
Code in
C (cloth)
(Publisher:
John Wiley & Sons, Inc.)
Author(s):
Bruce Schneier
ISBN:
0471128457
Publication
Date: 01/01/96
Search this book:
Previous
Table of Contents Next
Unicity
Distance
For a
message of length n, the number of different keys that will decipher a
ciphertext
message to some intelligible plaintext in the same language as the
original
plaintext (such as an English text string) is given by the following
formula
[712,95]:
2H(K)-
nD - 1
Shannon
[1432] defined the unicity distance, U, also called the unicity
point,
as an
approximation of the amount of ciphertext such that the sum of the real
information
(entropy) in the corresponding plaintext plus the entropy of the
encryption
key equals the number of ciphertext bits used. He then went on to
show
that ciphertexts longer than this distance are reasonably certain to have
only
one meaningful decryption. Ciphertexts significantly shorter than this are
likely
to have multiple, equally valid decryptions and therefore gain security
from
the opponent’s difficulty in choosing the correct one.
For
most symmetric cryptosystems, the unicity distance is defined as the
entropy
of the cryptosystem divided by the redundancy of the language.
U = H(K)/D
Unicity
distance does not make deterministic predictions, but gives
probabilistic
results. Unicity distance estimates the minimum amount of
ciphertext
for which it is likely that there is only a single intelligible plaintext
decryption
when a brute-force attack is attempted. Generally, the longer the
unicity
distance, the better the cryptosystem. For DES, with a 56-bit key, and
an
ASCII English message, the unicity distance is about 8.2 ASCII characters
or 66
bits. Table 11.1 gives the unicity distances for varying key lengths. The
unicity
distances for some classical cryptosystems are found in [445].
Unicity
distance is not a measure of how much ciphertext is required for
Go!
Keyword
-----------
Go!
cryptanalysis,
but how much ciphertext is required for there to be only one
reasonable
solution for cryptanalysis. A cryptosystem may be computationally
infeasible
to break even if it is theoretically possible to break it with a small
amount
of ciphertext. (The largely esoteric theory of relativized cryptography
is
relevant here [230, 231, 232, 233, 234, 235].) The unicity distance is
inversely
proportional to the redundancy. As redundancy approaches zero,
even a
trivial cipher can be unbreakable with a ciphertext-only attack.
Shannon
defined a cryptosystem whose unicity distance is infinite as one that
has ideal
secrecy. Note that an ideal cryptosystem is not necessarily a perfect
cryptosystem,
although a perfect cryptosystem would necessarily be an ideal
cryptosystem.
If a cryptosystem has ideal secrecy, even successful
cryptanalysis
will leave some uncertainty about whether the recovered
plaintext
is the real plaintext.
Information
Theory in Practice
While
these concepts have great theoretical value, actual cryptanalysis seldom
proceeds
along these lines. Unicity distance guarantees insecurity if it’s too
small
but does not guarantee security if it’s high. Few practical algorithms are
absolutely
impervious to analysis; all manner of characteristics might serve as
entering
wedges to crack some encrypted messages. However, similar
information
theory considerations are occasionally useful, for example, to
determine
a recommended key change interval for a particular algorithm.
Cryptanalysts
also employ a variety of statistical and information theory tests
to help
guide the analysis in the most promising directions. Unfortunately,
most
literature on applying information theory to cryptanalysis remains
classified,
including the seminal 1940 work of Alan Turing.
Table
11.1
Unicity
Distances of ASCII Text Encrypted
with
Algorithms with Varying Key Lengths
Key
Length (in bits) Unicity Distance (in
characters)
40 5.9
56 8.2
64 9.4
80 11.8
128
18.8
256
37.6
Confusion
and Diffusion
The two
basic techniques for obscuring the redundancies in a plaintext
message
are, according to Shannon, confusion and diffusion [1432].
Confusion
obscures the relationship between the plaintext and the ciphertext.
This
frustrates attempts to study the ciphertext looking for redundancies and
statistical
patterns. The easiest way to do this is through substitution. A simple
substitution
cipher, like the Caesar Cipher, is one in which every identical
letter
of plaintext is substituted for a single letter of ciphertext. Modern
substitution
ciphers are more complex: A long block of plaintext is substituted
for a
different block of ciphertext, and the mechanics of the substitution
change
with each bit in the plaintext or key. This type of substitution is not
necessarily
enough; the German Enigma is a complex substitution algorithm
that
was broken during World War II.
Diffusion
dissipates the redundancy of the plaintext by spreading it out over
the
ciphertext. A cryptanalyst looking for those redundancies will have a
harder
time finding them. The simplest way to cause diffusion is through
transposition
(also called permutation). A simple transposition cipher, like
columnar
transposition, simply rearranges the letters of the plaintext. Modern
ciphers
do this type of permutation, but they also employ other forms of
diffusion
that can diffuse parts of the message throughout the entire message.
Stream
ciphers rely on confusion alone, although some feedback schemes add
diffusion.
Block algorithms use both confusion and diffusion. As a general
rule,
diffusion alone is easily cracked (although double transposition ciphers
hold up
better than many other pencil-and-paper systems).
11.2 Complexity Theory
Complexity
theory provides a methodology for analyzing the computational
complexity
of different cryptographic techniques and algorithms. It compares
cryptographic
algorithms and techniques and determines their security.
Information
theory tells us that all cryptographic algorithms (except one-time
pads)
can be broken. Complexity theory tells us whether they can be broken
before
the heat death of the universe.
Previous
Table of Contents Next
Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms
& Conditions, Copyright
© 1996-2000 EarthWeb Inc.
All rights reserved. Reproduction whole or in part in any form or medium
without express written permission of EarthWeb is
prohibited. Read EarthWeb's privacy statement.
Brief Full
Advanced
Search
Search Tips
To access the contents, click the chapter and section titles.
Applied
Cryptography, Second Edition: Protocols, Algorthms, and Source
Code in
C (cloth)
(Publisher:
John Wiley & Sons, Inc.)
Author(s):
Bruce Schneier
ISBN:
0471128457
Publication
Date: 01/01/96
Search this book:
Previous
Table of Contents Next
Complexity
of Algorithms
An
algorithm’s complexity is determined by the computational power needed
to
execute it. The computational complexity of an algorithm is often measured
by two
variables: T (for time complexity) and S (for space
complexity, or
memory
requirement). Both T and S are commonly expressed as functions of
n, where
n is the size of the input. (There are other measures of complexity:
the
number of random bits, the communications bandwidth, the amount of
data,
and so on.)
Generally,
the computational complexity of an algorithm is expressed in what
is
called “big O” notation: the order of magnitude of the computational
complexity.
It’s just the term of the complexity function which grows the
fastest
as n gets larger; all lower-order terms are ignored. For example, if the
time
complexity of a given algorithm is 4n2 + 7n
+ 12, then the computational
complexity
is on the order of n2, expressed O(n2).
Measuring
time complexity this way is system-independent. You don’t have to
know
the exact timings of various instructions or the number of bits used to
represent
different variables or even the speed of the processor. One computer
might
be 50 percent faster than another and a third might have a data path
twice
as wide, but the order-of-magnitude complexity of an algorithm remains
the
same. This isn’t cheating; when you’re dealing with algorithms as complex
as the
ones presented here, the other stuff is negligible (is a constant factor)
compared
to the order-of-magnitude complexity.
This
notation allows you to see how the input size affects the time and space
requirements.
For example, if T = O(n), then doubling the input size doubles
the
running time of the algorithm. If T = O(2n), then
adding one bit to the input
size
doubles the running time of the algorithm (within a constant factor).
Go!
Keyword
-----------
Go!
Generally,
algorithms are classified according to their time or space
complexities.
An algorithm is constant if its complexity is independent of n:
O(1).
An algorithm is linear, if its time complexity is O(n).
Algorithms can
also be
quadratic, cubic, and so on. All these algorithms are polynomial;
their
complexity is O(nm), when m is
a constant. The class of algorithms that
have a
polynomial time complexity are called polynomial-time algorithms.
Algorithms
whose complexities are O(t f(n)),
where t is a constant greater than 1
and f
(n) is some polynomial function of n, are called exponential.
The subset
of
exponential algorithms whose complexities are O(c f(n)),
where c is a
constant
and f (n) is more than constant but less than linear, is called
superpolynomial.
Ideally,
a cryptographer would like to be able to say that the best algorithm to
break
this encryption algorithm is of exponential-time complexity. In practice,
the
strongest statements that can be made, given the current state of the art of
computational
complexity theory, are of the form “all known cracking
algorithms
for this cryptosystem are of superpolynomial-time complexity.”
That
is, the cracking algorithms that we know are of superpolynomial-time
complexity,
but it is not yet possible to prove that no polynomial-time cracking
algorithm
could ever be discovered. Advances in computational complexity
may
some day make it possible to design algorithms for which the existence of
polynomial-time
cracking algorithms can be ruled out with mathematical
certainty.
As n
grows, the time complexity of an algorithm can make an enormous
difference
in whether the algorithm is practical. Table 11.2 shows the running
times
for different algorithm classes in which n equals one million. The table
ignores
constants, but also shows why ignoring constants is reasonable.
Table
11.2
Running
Times of Different Classes of Algorithms
Class
Complexity
# of
Operations
for n
= 106
Time at
106 O/S
Constant
O(1) 1 1 µsec.
Linear
O(n) 106 1 sec.
Quadratic
O(n2) 1012 11.6
days
Cubic
O(n3) 1018 32, 000
yrs.
Exponential
O(2n) 10301,030 10301,006 times
the age of
the
universe
Assuming
that the unit of “time” for our computer is a microsecond, the
computer
can complete a constant algorithm in a microsecond, a linear
algorithm
in a second, and a quadratic algorithm in 11.6 days. It would take
32, 000
years to complete a cubic algorithm; not terribly practical, but a
computer
built to withstand the next ice age would deliver a solution
eventually.
Performing the exponential algorithm is futile, no matter how well
you
extrapolate computing power, parallel processing, or contact with
superintelligent
aliens.
Look at
the problem of a brute-force attack against an encryption algorithm.
The
time complexity of this attack is proportional to the number of possible
keys,
which is an exponential function of the key length. If n is the length
of
the
key, then the complexity of a brute-force attack is O(2n).
Section 12.3
discusses
the controversy surrounding a 56-bit key for DES instead of a
112-bit
key. The complexity of a brute-force attack against a 56-bit key is 256;
against
a 112-bit key the complexity is 2112. The former is possible; the latter
isn’t.
Previous
Table of Contents Next
Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms
& Conditions, Copyright
© 1996-2000 EarthWeb Inc.
All rights reserved. Reproduction whole or in part in any form or medium
without express written permission of EarthWeb is
prohibited. Read EarthWeb's privacy statement.
Brief Full
Advanced
Search
Search Tips
To access the contents, click the chapter and section titles.
Applied
Cryptography, Second Edition: Protocols, Algorthms, and Source
Code in
C (cloth)
(Publisher:
John Wiley & Sons, Inc.)
Author(s):
Bruce Schneier
ISBN:
0471128457
Publication
Date: 01/01/96
Search this book:
Previous
Table of Contents Next
Complexity
of Problems
Complexity
theory also classifies the inherent complexity of problems, not just
the
complexity of particular algorithms used to solve problems. (Excellent
introductions
to this topic are [600, 211, 1226]; see also [1096, 27, 739].) The
theory
looks at the minimum time and space required to solve the hardest
instance
of a problem on a theoretical computer known as a Turing machine .
A
Turing machine is a finite-state machine with an infinite read-write memory
tape.
It turns out that a Turing machine is a realistic model of computation.
Problems
that can be solved with polynomial-time algorithms are called
tractable,
because they can usually be solved in a reasonable amount of time
for
reasonable-sized inputs. (The exact definition of “reasonable” depends on
the
circumstance.) Problems that cannot be solved in polynomial time are
called intractable,
because calculating their solution quickly becomes
infeasible.
Intractable problems are sometimes just called hard. Problems that
can
only be solved with algorithms that are superpolynomial are
computationally
intractable, even for relatively small values of n.
It gets
worse. Alan Turing proved that some problems are undecidable . It is
impossible
to devise any algorithm to solve them, regardless of the algorithm’s
time
complexity.
Problems
can be divided into complexity classes, which depend on the
complexity
of their solutions. Figure 11.1 shows the more important
complexity
classes and their presumed relationships. (Unfortunately, not much
about this
material has been proved mathematically.)
On the
bottom, the class P consists of all problems that can be solved in
polynomial
time. The class NP consists of all problems that can be solved in
polynomial
time only on a nondeterministic Turing machine: a variant of a
Go!
Keyword
-----------
Go!
normal
Turing machine that can make guesses. The machine guesses the
solution
to the problem—either by making “lucky guesses” or by trying all
guesses
in parallel—and checks its guess in polynomial time.
NP ’s relevance
to cryptography is this: Many symmetric algorithms and all
public-key
algorithms can be cracked in nondeterministic polynomial time.
Given a
ciphertext C, the cryptanalyst simply guesses a plaintext, X, and
a key,
k, and
in polynomial time runs the encryption algorithm on inputs X and k and
checks
whether the result is equal to C. This is important theoretically,
because
it puts
an upper bound on the complexity of cryptanalysis for these algorithms.
In
practice, of course, it is a deterministic polynomial-time algorithm that the
cryptanalyst
seeks. Furthermore, this argument is not applicable to all classes
of
ciphers; in particular, it is not applicable to one-time pads—for any C,
there
are
many X, k pairs that yield C when run through the encryption
algorithm,
but
most of these X s are nonsense, not legitimate plaintexts.
Figure
11.1 Complexity classes.
The
class NP includes the class P, because any problem solvable in
polynomial
time on a deterministic Turing machine is also solvable in
polynomial
time on a nondeterministic Turing machine; the guessing stage can
simply
be omitted.
If all NP
problems are solvable in polynomial time on a deterministic machine,
then P
= NP. Although it seems obvious that some NP problems are
much
harder
than others (a brute-force attack against an encryption algorithm versus
encrypting
a random block of plaintext), it has never been proven that P ` NP
(or
that P = NP). However, most people working in complexity theory
believe
that
they are unequal.
Stranger
still, specific problems in NP can be proven to be as difficult as any
problem
in the class. Steven Cook [365] proved that the Satisfiability problem
(given
a propositional Boolean formula, is there a way to assign truth values to
the
variables that makes the formula true?) is NP-complete . This means
that,
if
Satisfiability is solvable in polynomial time, then P = NP.
Conversely, if any
problem
in NP can be proven not to have a deterministic polynomial-time
algorithm,
the proof will show that Satisfiability does not have a deterministic
polynomial-time
algorithm either. No problem is harder than Satisfiability in
NP.
Since
Cook’s seminal paper was published, a huge number of problems have
been
shown to be equivalent to Satisfiability; hundreds are listed in [600], and
some
examples follow. By equivalent, I mean that these problems are also
NP-complete; they
are in NP and also as hard as any problem in NP . If their
solvability
in deterministic polynomial time were resolved, the P versus NP
question
would be solved. The question of whether P = NP is the central
unsolved
question of computational complexity theory, and no one expects it
to be
solved anytime soon. If someone showed that P = NP, then most of
this
book
would be irrelevant: As previously explained, many classes of ciphers are
trivially
breakable in nondeterministic polynomial time. If P = NP, they
are
breakable
by feasible, deterministic algorithms.
Further
out in the complexity hierarchy is PSPACE . Problems in PSPACE
can be
solved in polynomial space, but not necessarily polynomial time.
PSPACE includes
NP, but some problems in PSPACE are thought to be
harder
than NP. Of course, this isn’t proven either. There is a class of
problems,
the so-called PSPACE-complete problems, with the property that,
if any
one of them is in NP then PSPACE = NP and if any one of
them is in P
then PSPACE
= P .
And
finally, there is the class of problems called EXPTIME . These problems
are
solvable in exponential time. The EXPTIME-complete problems can
actually
be proven not to be solvable in deterministic polynomial time. It has
been
shown that P does not equal EXPTIME .
Previous
Table of Contents Next
Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms
& Conditions, Copyright
© 1996-2000 EarthWeb Inc.
All rights reserved. Reproduction whole or in part in any form or medium
without express written permission of EarthWeb is
prohibited. Read EarthWeb's privacy statement.
Brief Full
Advanced
Search
Search Tips
To access the contents, click the chapter and section titles.
Applied
Cryptography, Second Edition: Protocols, Algorthms, and Source
Code in
C (cloth)
(Publisher:
John Wiley & Sons, Inc.)
Author(s):
Bruce Schneier
ISBN:
0471128457
Publication
Date:
Search this book:
Previous
Table of Contents Next
NP-Complete
Problems
Michael
Garey and David Johnson compiled a list of over 300 NP-complete
problems [600]. Here are
just a few of them:
— Traveling Salesman Problem. A traveling
salesman has to visit n
different cities using only one tank of gas (there
is a maximum distance
he can travel). Is there a route that allows him to
visit each city exactly
once on that single tank of gas? (This is a generalization
of the
Hamiltonian
Cycle problem—see Section 5.1.)
—
Three-Way Marriage Problem. In a room are n men, n women, and n
clergymen (priests, rabbis, whatever). There is
also a list of acceptable
marriages, which consists of one man, one woman,
and one clergyman
willing to officiate. Given this list of possible
triples, is it possible to
arrange n marriages such that everyone is
either marrying one person or
officiating at one marriage?
—
Three-Satisfiability. There is a list of n logical
statements, each with
three variables. For example: if (x and y)
then z, (x and w) or (not z), if
((not u
and not x) or (z and (u or not x))) then (not z
and u) or x), and so
on. Is there a truth assignment for all the variables
that satisfies all the
statements? (This is a special case of the Satisfiability problem
previously mentioned.)
Go!
Keyword
-----------
Go!