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&ampg [, 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: 01/01/96

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!