Hack Proofing Your Network-6

[mic64]

Chapter 6
165
Summary
Solutions Fast Track
Frequently Asked Questions
166 Chapter 6 • Cryptography
Introduction
Cryptography is everywhere these days, from hashed passwords to encrypted
mail, to Internet Protocol Security (IPSec) virtual private networks (VPNs) and
even encrypted filesystems. Security is the reason why people opt to encrypt
data, and if you want your data to remain secure you’d best know a bit about
how cryptography works.This chapter certainly can’t teach you how to become a
professional cryptographer—that takes years of study and practice—but you will
learn how most of the cryptography you will come in contact with functions
(without all the complicated math, of course).
We’ll examine some of the history of cryptography and then look closely at a
few of the most common algorithms, including Advanced Encryption Standard
(AES), the recently announced new cryptography standard for the U.S. government.
We’ll learn how key exchanges and public key cryptography came into
play, and how to use them. I’ll show you how almost all cryptography is at least
theoretically vulnerable to brute force attacks.
Naturally, once we’ve covered the background we’ll look at how cryptography
can be broken, from cracking passwords to man-in-the-middle-type
attacks.We’ll also look at how other attacks based on poor implementation of
strong cryptography can reduce your security level to zero. Finally, we’ll examine
how weak attempts to hide information using outdated cryptography can easily
be broken.
Understanding Cryptography Concepts
What does the word crypto mean? It has its origins in the Greek word kruptos,
which means hidden.Thus, the objective of cryptography is to hide information
so that only the intended recipient(s) can “unhide” it. In crypto terms, the hiding
of information is called encryption, and when the information is unhidden, it is
called decryption.A cipher is used to accomplish the encryption and decryption.
Merriam-Webster’s Collegiate Dictionary defines cipher as “a method of transforming
a text in order to conceal its meaning.”The information that is being
hidden is called plaintext; once it has been encrypted, it is called ciphertext.The
ciphertext is transported, secure from prying eyes, to the intended recipient(s),
where it is decrypted back into plaintext.
www.syngress.com
www.syngress.com
History
According to Fred Cohen, the history of cryptography has been documented
back to over 4000 years ago, where it was first allegedly used in Egypt. Julius
Caesar even used his own cryptography called Caesar’s Cipher. Basically, Caesar’s
Cipher rotated the letters of the alphabet to the right by three. For example, S
moves to V and E moves to H. By today’s standards the Caesar Cipher is
extremely simplistic, but it served Julius just fine in his day. If you are interested
in knowing more about the history of cryptography, the following site is a great
place to start: www.all.net/books/ip/Chap2-1.html.
In fact, ROT13 (rotate 13), which is similar to Caesar’s Cipher, is still in use
today. It is not used to keep secrets from people, but more to avoid offending
people when sending jokes, spoiling the answers to puzzles, and things along
those lines. If such things occur when someone decodes the message, then the
responsibility lies on them and not the sender. For example, Mr. G. may find the
following example offensive to him if he was to decode it, but as it is shown it
offends no one:V guvax Jvaqbjf fhpxf…
ROT13 is simple enough to work out with pencil and paper. Just write the
alphabet in two rows; the second row offset by 13 letters:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
NOPQRSTUVWXYZABCDEFGHIJKLM
Encryption Key Types
Cryptography uses two types of keys: symmetric and asymmetric. Symmetric keys
have been around the longest; they utilize a single key for both the encryption
and decryption of the ciphertext.This type of key is called a secret key, because
you must keep it secret. Otherwise, anyone in possession of the key can decrypt
messages that have been encrypted with it.The algorithms used in symmetric key
encryption have, for the most part, been around for many years and are well
known, so the only thing that is secret is the key being used. Indeed, all of the
really useful algorithms in use today are completely open to the public.
A couple of problems immediately come to mind when you are using symmetric
key encryption as the sole means of cryptography. First, how do you
ensure that the sender and receiver each have the same key? Usually this requires
the use of a courier service or some other trusted means of key transport.
Second, a problem exists if the recipient does not have the same key to decrypt
Cryptography • Chapter 6 167
168 Chapter 6 • Cryptography
the ciphertext from the sender. For example, take a situation where the symmetric
key for a piece of crypto hardware is changed at 0400 every morning at
both ends of a circuit.What happens if one end forgets to change the key
(whether it is done with a strip tape, patch blocks, or some other method) at the
appropriate time and sends ciphertext using the old key to another site that has
properly changed to the new key? The end receiving the transmission will not be
able to decrypt the ciphertext, since it is using the wrong key.This can create
major problems in a time of crisis, especially if the old key has been destroyed.
This is an overly simple example, but it should provide a good idea of what can
go wrong if the sender and receiver do not use the same secret key.
Asymmetric cryptography is relatively new in the history of cryptography,
and it is probably more recognizable to you under the synonymous term public
key cryptography.Asymmetric algorithms use two different keys, one for encryption
and one for decryption—a public key and a private key, respectively.Whitfield
Diffie and Martin Hellman first publicly released public key cryptography in
www.syngress.com
Assessing Algorithmic Strength
Algorithmic security can only be proven by its resistance to attack. Since
many more attacks are attempted on algorithms which are open to the
public, the longer an algorithm has been open to the public, the more
attempts to circumvent or break it have occurred. Weak algorithms are
broken rather quickly, usually in a matter of days or months, whereas
stronger algorithms may be used for decades. However, the openness of
the algorithm is an important factor. It’s much more difficult to break an
algorithm (whether weak or strong) when its complexities are completely
unknown. Thus when you use an open algorithm, you can rest
assured in its strength. This is opposed to a proprietary algorithm,
which, if weak, may eventually be broken even if the algorithm itself is
not completely understood by the cryptographer. Obviously, one should
limit the trust placed in proprietary algorithms to limit long-term liability.
Such scrutiny is the reason the inner details of many of the
patented algorithms in use today (such as RC6 from RSA Laboratories)
are publicly available.
Tools & Traps…
Cryptography • Chapter 6 169
1976 as a method of exchanging keys in a secret key system.Their algorithm,
called the Diffie-Hellman (DH) algorithm, is examined later in the chapter. Even
though it is commonly reported that public key cryptography was first invented
by the duo, some reports state that the British Secret Service actually invented it
a few years prior to the release by Diffie and Hellman. It is alleged, however, that
the British Secret Service never actually did anything with their algorithm after
they developed it. More information on the subject can be found at the following
location: www.wired.com/wired/archive/7.04/crypto_pr.html
Some time after Diffie and Hellman, Phil Zimmermann made public key
encryption popular when he released Pretty Good Privacy (PGP) v1.0 for DOS
in August 1991. Support for multiple platforms including UNIX and Amiga were
added in 1994 with the v2.3 release.Over time, PGP has been enhanced and
released by multiple entities, including ViaCrypt and PGP Inc., which is now part
of Network Associates. Both commercial versions and free versions (for noncommercial
use) are available. For those readers in the United States and Canada,
you can retrieve the free version from http://web.mit.edu/network/pgp.html.
The commercial version can be purchased from Network Associates at
www.pgp.com.
Learning about Standard
Cryptographic Algorithms
Just why are there so many algorithms anyway? Why doesn’t the world just standardize
on one algorithm? Given the large number of algorithms found in the
field today, these are valid questions with no simple answers. At the most basic
level, it’s a classic case of tradeoffs between security, speed, and ease of implementation.
Here security indicates the likelihood of an algorithm to stand up to current
and future attacks, speed refers to the processing power and time required to
encrypt and decrypt a message, and ease of implementation refers to an algorithm’s
predisposition (if any) to hardware or software usage. Each algorithm has different
strengths and drawbacks, and none of them is ideal in every way. In this chapter,
we will look at the five most common algorithms that you will encounter: Data
Encryption Standard (DES), AES [Rijndael], International Data Encryption
Algorithm (IDEA), Diffie-Hellman, and Rivest, Shamir, Adleman (RSA). Be
aware, though, that there are dozens more active in the field.
www.syngress.com
170 Chapter 6 • Cryptography
Understanding Symmetric Algorithms
In this section, we will examine several of the most common symmetric algorithms
in use: DES, its successor AES, and the European standard, IDEA. Keep in
mind that the strength of symmetric algorithms lies primarily in the size of the
keys used in the algorithm, as well as the number of cycles each algorithm
employs. All symmetric algorithms are also theoretically vulnerable to brute force
attacks, which are exhaustive searches of all possible keys. However, brute force
attacks are often infeasible.We will discuss them in detail later in the chapter.
DES
Among the oldest and most famous encryption algorithms is the Data Encryption
Standard, which was developed by IBM and was the U.S. government standard
from 1976 until about 2001. DES was based significantly on the Lucifer algorithm
invented by Horst Feistel, which never saw widespread use. Essentially, DES uses a
single 64-bit key—56 bits of data and 8 bits of parity—and operates on data in
64-bit chunks.This key is broken into 16 separate 48-bit subkeys, one for each
round, which are called Feistel cycles. Figure 6.1 gives a schematic of how the DES
encryption algorithm operates.
Each round consists of a substitution phase, wherein the data is substituted
with pieces of the key, and a permutation phase, wherein the substituted data is
scrambled (re-ordered). Substitution operations, sometimes referred to as confusion
operations, are said to occur within S-boxes. Similarly, permutation operations,
sometimes called diffusion operations, are said to occur in P-boxes. Both of
these operations occur in the “F Module” of the diagram.The security of DES
lies mainly in the fact that since the substitution operations are non-linear, so the
resulting ciphertext in no way resembles the original message.Thus, languagebased
analysis techniques (discussed later in this chapter) used against the ciphertext
reveal nothing.The permutation operations add another layer of security by
scrambling the already partially encrypted message.
Every five years from 1976 until 2001, the National Institute of Standards and
Technology (NIST) reaffirmed DES as the encryption standard for the U.S. government.
However, by the 1990s the aging algorithm had begun to show signs
that it was nearing its end of life. New techniques that identified a shortcut
method of attacking the DES cipher, such as differential cryptanalysis, were proposed
as early as 1990, though it was still computationally unfeasible to do so.
www.syngress.com
Cryptography • Chapter 6 171
SECURITY ALERT
How can symmetric algorithms such as DES be made more secure?
Theoretically, there are two ways: either the key length needs to be
increased, or the number of rounds in the encryption process needs to
be increased. Both of these solutions tend to increase the processing
power required to encrypt and decrypt data and slow down the encryption/
decryption speed because of the increased number of mathematical
operations required. Examples of modified DES include 3-DES (a.k.a.
Triple DES) and DESX. Triple DES uses three separate 56-bit DES keys as a
single 168-bit key, though sometimes keys 1 and 3 are identical, yielding
112-bit security. DESX adds an additional 64-bits of key data. Both 3-DES
and DESX are intended to strengthen DES against brute force attacks.
www.syngress.com
Figure 6.1 Diagram of the DES Encryption Algorithm
Preliminary Permutation
56-Bit Data Input
8-bit Parity Input
Incoming Data Stream
(Cleartext)
010011001101011
XOR
F
Module
64-Bits
Subkey N 48-Bits
Repeat for N
Iterations
Final Permutation
56-Bit Data Output
Outgoing Data Stream
(Ciphertext)
111010110100101
KN
172 Chapter 6 • Cryptography
Significant design flaws such as the short 56-bit key length also affected the
longevity of the DES cipher. Shorter keys are more vulnerable to brute force
attacks. Although Whitfield Diffie and Martin Hellman were the first to criticize
this short key length, even going so far as to declare in 1979 that DES would
be useless within 10 years, DES was not publicly broken by a brute force attack
until 1997.
The first successful brute force attack against DES took a large network of
machines over 4 months to accomplish. Less than a year later, in 1998, the
Electronic Frontier Foundation (EFF) cracked DES in less than three days using a
computer specially designed for cracking DES.This computer, code-named
“Deep Crack,” cost less than $250,000 to design and build.The record for
cracking DES stands at just over 22 hours and is held by Distributed.net, which
employed a massively parallel network of thousands of systems (including Deep
Crack). Add to this the fact that Bruce Schneier has theorized that a machine
capable of breaking DES in about six minutes could be built for a mere $10 million.
Clearly, NIST needed to phase out DES in favor of a new algorithm.
AES (Rijndael)
In 1997, as the fall of DES loomed ominously closer, NIST announced the search
for the Advanced Encryption Standard, the successor to DES. Once the search
began, most of the big-name cryptography players submitted their own AES candidates.
Among the requirements of AES candidates were:
 AES would be a private key symmetric block cipher (similar to DES).
 AES needed to be stronger and faster then 3-DES.
 AES required a life expectancy of at least 20-30 years.
 AES would support key sizes of 128-bits, 192-bits, and 256-bits.
 AES would be available to all—royalty free, non-proprietary and
unpatented.
Within months NIST had a total of 15 different entries, 6 of which were
rejected almost immediately on grounds that they were considered incomplete.
By 1999, NIST had narrowed the candidates down to five finalists including
MARS, RC6, Rijndael, Serpent, and Twofish.
Selecting the winner took approximately another year, as each of the candidates
needed to be tested to determine how well they performed in a variety of
environments. After all, applications of AES would range anywhere from portable
www.syngress.com
Cryptography • Chapter 6 173
smart cards to standard 32-bit desktop computers to high-end optimized 64-bit
computers. Since all of the finalists were highly secure, the primary deciding factors
were speed and ease of implementation (which in this case meant memory
footprint).
Rijndael was ultimately announced as the winner in October of 2000
because of its high performance in both hardware and software implementations
and its small memory requirement.The Rijndael algorithm, developed by Belgian
cryptographers Dr. Joan Daemen and Dr.Vincent Rijmen, also seems resistant to
power- and timing-based attacks.
So how does AES/Rijndael work? Instead of using Feistel cycles in each
round like DES, it uses iterative rounds like IDEA (discussed in the next section).
Data is operated on in 128-bit chunks, which are grouped into four groups of
four bytes each.The number of rounds is also dependent on the key size, such
that 128-bit keys have 9 rounds, 192-bit keys have 11 rounds and 256-bit keys
require 13 rounds. Each round consists of a substitution step of one S-box per
data bit followed by a pseudo-permutation step in which bits are shuffled
between groups.Then each group is multiplied out in a matrix fashion and the
results are added to the subkey for that round.
How much faster is AES than 3-DES? It’s difficult to say, because implementation
speed varies widely depending on what type of processor is performing the
encryption and whether or not the encryption is being performed in software or
running on hardware specifically designed for encryption. However, in similar
implementations, AES is always faster than its 3-DES counterpart. One test performed
by Brian Gladman has shown that on a Pentium Pro 200 with optimized
code written in C, AES (Rijndael) can encrypt and decrypt at an average speed
of 70.2 Mbps, versus DES’s speed of only 28 Mbps.You can read his other results
at fp.gladman.plus.com/cryptography_technology/aes.
IDEA
The European counterpart to the DES algorithm is the IDEA algorithm, and its
existence proves that Americans certainly don’t have a monopoly on strong cryptography.
IDEA was first proposed under the name Proposed Encryption Standard
(PES) in 1990 by cryptographers James Massey and Xuejia Lai as part of a combined
research project between Ascom and the Swiss Federal Institute of
Technology. Before it saw widespread use PES was updated in 1991 to increase its
strength against differential cryptanalysis attacks and was renamed Improved PES
(IPES). Finally, the name was changed to International Data Encryption
Algorithm (IDEA) in 1992.
www.syngress.com
174 Chapter 6 • Cryptography
Not only is IDEA newer than DES, but IDEA is also considerably faster and
more secure. IDEA’s enhanced speed is due to the fact the each round consists of
much simpler operations than the Fiestel cycle in DES.These operations (XOR,
addition, and multiplication) are much simpler to implement in software than the
substitution and permutation operations of DES.
IDEA operates on 64-bit blocks with a 128-bit key, and the encryption/
decryption process uses 8 rounds with 6 16-bit subkeys per round.The IDEA
algorithm is patented both in the US and in Europe, but free non-commercial
use is permitted.
Understanding Asymmetric Algorithms
Recall that unlike symmetric algorithms, asymmetric algorithms require more
than one key, usually a public key and a private key (systems with more than two
keys are possible). Instead of relying on the techniques of substitution and transposition,
which symmetric key cryptography uses, asymmetric algorithms rely on
the use of massively large integer mathematics problems. Many of these problems
are simple to do in one direction but difficult to do in the opposite direction. For
example, it’s easy to multiply two numbers together, but it’s more difficult to
factor them back into the original numbers, especially if the integers you are
using contain hundreds of digits.Thus, in general, the security of asymmetric
algorithms is dependent not upon the feasibility of brute force attacks, but the
feasibility of performing difficult mathematical inverse operations and advances in
mathematical theory that may propose new “shortcut” techniques. In this section,
we’ll take a look at RSA and Diffie-Hellman, the two most popular asymmetric
algorithms in use today.
Diffie-Hellman
In 1976, after voicing their disapproval of DES and the difficulty in handling
secret keys,Whitfield Diffie and Martin Hellman published the Diffie-Hellman
algorithm for key exchange.This was the first published use of public key cryptography,
and arguably one of the cryptography field’s greatest advances ever.
Because of the inherent slowness of asymmetric cryptography, the Diffie-Hellman
algorithm was not intended for use as a general encryption scheme—rather, its
purpose was to transmit a private key for DES (or some similar symmetric algorithm)
across an insecure medium. In most cases, Diffie-Hellman is not used for
encrypting a complete message because it is 10 to 1000 times slower than DES,
depending on implementation.
www.syngress.com
Cryptography • Chapter 6 175
Prior to publication of the Diffie-Hellman algorithm, it was quite painful to
share encrypted information with others because of the inherent key storage and
transmission problems (as discussed later in this chapter). Most wire transmissions
were insecure, since a message could travel between dozens of systems before
reaching the intended recipient and any number of snoops along the way could
uncover the key.With the Diffie-Hellman algorithm, the DES secret key (sent
along with a DES-encrypted payload message) could be encrypted via Diffie-
Hellman by one party and decrypted only by the intended recipient.
In practice, this is how a key exchange using Diffie-Hellman works:
 The two parties agree on two numbers; one is a large prime number, the
other is an integer smaller than the prime.They can do this in the open
and it doesn’t affect security.
 Each of the two parties separately generates another number, which they
keep secret.This number is equivalent to a private key.A calculation is
made involving the private key and the previous two public numbers.
The result is sent to the other party.This result is effectively a public key.
 The two parties exchange their public keys.They then privately perform
a calculation involving their own private key and the other party’s public
key.The resulting number is the session key. Each party will arrive at the
same number.
 The session key can be used as a secret key for another cipher, such as
DES. No third party monitoring the exchange can arrive at the same
session key without knowing one of the private keys.
The most difficult part of the Diffie-Hellman key exchange to understand is
that there are actually two separate and independent encryption cycles happening.
As far as Diffie-Hellman is concerned, only a small message is being
transferred between the sender and the recipient. It just so happens that this small
message is the secret key needed to unlock the larger message.
Diffie-Hellman’s greatest strength is that anyone can know either or both of
the sender and recipient’s public keys without compromising the security of the
message. Both the public and private keys are actually just very large integers.The
Diffie-Hellman algorithm takes advantage of complex mathematical functions
known as discrete logarithms, which are easy to perform forwards but extremely
difficult to find inverses for. Even though the patent on Diffie-Hellman has been
expired for several years now, the algorithm is still in wide use, most notably in
www.syngress.com
176 Chapter 6 • Cryptography
the IPSec protocol. IPSec uses the Diffie-Hellman algorithm in conjunction with
RSA authentication to exchange a session key that is used for encrypting all
traffic that crosses the IPSec tunnel.
RSA
In the year following the Diffie-Hellman proposal, Ron Rivest, Adi Shamir, and
Leonard Adleman proposed another public key encryption system.Their proposal
is now known as the RSA algorithm, named for the last initials of the
researchers. RSA shares many similarities with the Diffie-Hellman algorithm in
that RSA is also based on multiplying and factoring large integers. However,
RSA is significantly faster than Diffie-Hellman, leading to a split in the asymmetric
cryptography field that refers to Diffie-Hellman and similar algorithms as
Public Key Distribution Systems (PKDS) and RSA and similar algorithms as
Public Key Encryption (PKE). PKDS systems are used as session-key exchange
mechanisms, while PKE systems are generally considered fast enough to encrypt
reasonably small messages. However, PKE systems like RSA are not considered
fast enough to encrypt large amounts of data like entire filesystems or high-speed
communications lines.
NOTE
RSA, Diffie-Hellman and other asymmetric algorithms use much larger
keys than their symmetric counterparts. Common key sizes include 1024-
bits and 2048-bits, and the keys need to be this large because factoring,
while still a difficult operation, is much easier to perform than the
exhaustive key search approach used with symmetric algorithms. The relative
slowness of public key encryption systems is also due in part to
these larger key sizes. Since most computers can only handle 32-bits of
precision, different “tricks” are required to emulate the 1024-bit and
2048-bit integers. However, the additional processing time is somewhat
justified, since for security purposes 2048-bit keys are considered to be
secure “forever”—barring any exponential breakthroughs in mathematical
factoring algorithms, of course.
Because of the former patent restrictions on RSA, the algorithm saw only
limited deployment, primarily only from products by RSA Security, until the
mid-1990s. Now you are likely to encounter many programs making extensive
use of RSA, such as PGP and Secure Shell (SSH).The RSA algorithm has been
www.syngress.com
Cryptography • Chapter 6 177
in the public domain since RSA Security placed it there two weeks before the
patent expired in September 2000.Thus the RSA algorithm is now freely available
for use by anyone, for any purpose.
Understanding Brute Force
Just how secure are encrypted files and passwords anyway? Consider that there
are two ways to break an encryption algorithm—brute force and various cryptanalysis
shortcuts. Cryptanalysis shortcuts vary from algorithm to algorithm, or
may even be non-existent for some algorithms, and they are always difficult to
find and exploit. Conversely, brute force is always available and easy to try. Brute
force techniques involve exhaustively searching the given keyspace by trying
every possible key or password combination until the right one is found.
Brute Force Basics
As an example, consider the basic three-digit combination bicycle lock where
each digit is turned to select a number between zero and nine. Given enough
time and assuming that the combination doesn’t change during the attempts, just
rolling through every possible combination in sequence can easily open this lock.
The total number of possible combinations (keys) is 103 or 1000, and let’s say the
frequency, or number of combinations a thief can attempt during a time period,
is 30 per minute.Thus, the thief should be able to open the bike lock in a maximum
of 1000/(30 per min) or about 33 minutes. Keep in mind that with each
new combination attempted, the number of remaining possible combinations
(keyspace) decreases and the chance of guessing the correct combination (deciphering
the key) on the next attempt increases.
Brute force always works because the keyspace, no matter how large, is always
finite. So the way to resist brute force attacks is to choose a keysize large enough
that it becomes too time-consuming for the attacker to use brute force techniques.
In the bike lock example, three digits of keyspace gives the attacker a
maximum amount of time of 33 minutes required to steal the bicycle, so the thief
may be tempted to try a brute force attack. Suppose a bike lock with a five-digit
combination is used. Now there are 100,000 possible combinations, which would
take about 55.5 hours for the thief check by brute force. Clearly, most thieves
would move on and look for something easier to steal.
When applied to symmetric algorithms such as DES, brute force techniques
work very similarly to the bike lock example. In fact, this happens to be exactly
www.syngress.com
178 Chapter 6 • Cryptography
the way DES was broken by the EFF’s “Deep Crack.” Since the DES key is
known to be 56 bits long, every possible combination of keys between a string of
56 zeros and a string of 56 ones is tested until the appropriate key is discovered.
As for the distributed attempts to break DES, the five-digit bike lock analogy
needs to be slightly changed. Distributed brute force attempts are analogous to
having multiple thieves, each with an exact replica of the bike lock. Each of these
replicas has the exact same combination as the original bike lock, and the thieves
work on the combination in parallel. Suppose there are 50 thieves working
together to guess the combination. Each thief tries a different set of 2,000 combinations
such that no two thieves are working on the same combination set (subkeyspace).
Now instead of testing 30 combinations per minute, the thieves are
testing 1500 combinations per minute, and all possible combinations will be
checked in about 67 minutes. Recall that it took the single thief 55 hours to steal
the bike, but now 50 thieves working together can steal the bike in just over an
hour. Distributed computing applications working under the same fundamentals
are what allowed Distributed.net to crack DES in less than 24 hours.
Applying brute force techniques to RSA and other public key encryption
systems is not quite as simple. Since the RSA algorithm is broken by factoring, if
the keys being used are sufficiently small (far, far smaller than any program using
RSA would allow), it is conceivable that a person could crack the RSA algorithm
using pencil and paper. However, for larger keys, the time required to perform
the factoring becomes excessive. Factoring does not lend itself to
distributed attacks as well, either.A distributed factoring attack would require
much more coordination between participants than simple exhaustive keyspace
coordination.There are projects, such as the www-factoring project
(www.npac.syr.edu/factoring.html), that endeavor to do just this. Currently, the
www-factoring project is attempting to factor a 130-digit number. In comparison,
512-bit keys are about 155 digits in size.
Using Brute Force to Obtain Passwords
Brute force is a method commonly used to obtain passwords, especially if the
encrypted password list is available.While the exact number of characters in a
password is usually unknown, most passwords can be estimated to be between 4
and 16 characters. Since only about 100 different values can be used for each
character of the password, there are only about 1004 to 10016 likely password
combinations.Though massively large, the number of possible password combinations
is finite and is therefore vulnerable to brute force attack.
www.syngress.com
Cryptography • Chapter 6 179
Before specific methods for applying brute force can be discussed, a brief
explanation of password encryption is required. Most modern operating systems
use some form of password hashing to mask the exact password. Because passwords
are never stored on the server in cleartext form, the password authentication
system becomes much more secure. Even if someone unauthorized
somehow obtains the password list, he will not be able to make immediate use of
it, hopefully giving system administrators time to change all of the relevant passwords
before any real damage is caused.
Passwords are generally stored in what is called hashed format.When a password
is entered on the system it passes through a one-way hashing function, such as
Message Digest 5 (MD5), and the output is recorded. Hashing functions are oneway
encryption only, and once data has been hashed, it cannot be restored.A
server doesn’t need to know what your password is. It needs to know that you
know what it is.When you attempt to authenticate, the password you provided is
passed through the hashing function and the output is compared to the stored
hash value. If these values match, then you are authenticated. Otherwise, the login
attempt fails, and is (hopefully) logged by the system.
Brute force attempts to discover passwords usually involve stealing a copy of
the username and hashed password listing and then methodically encrypting possible
passwords using the same hashing function. If a match is found, then the
password is considered cracked. Some variations of brute force techniques involve
simply passing possible passwords directly to the system via remote login
attempts. However, these variations are rarely seen anymore due to account
lockout features and the fact that they can be easily spotted and traced by system
administrators.They also tend to be extremely slow.
Appropriate password selection minimizes—but cannot completely eliminate—
a password’s ability to be cracked. Simple passwords, such as any individual word
in a language, make the weakest passwords because they can be cracked with an
elementary dictionary attack. In this type of attack, long lists of words of a particular
language called dictionary files are searched for a match to the encrypted password.
More complex passwords that include letters, numbers and symbols require
a different brute force technique that includes all printable characters and generally
take an order of magnitude longer to run.
Some of the more common tools used to perform brute force password
attacks include L0phtcrack for Windows passwords, and Crack and John the
Ripper for UNIX passwords. Not only do hackers use these tools but security
professionals also find them useful in auditing passwords. If it takes a security professional
N days to crack a password, then that is approximately how long it will
www.syngress.com
180 Chapter 6 • Cryptography
take an attacker to do the same. Each of these tools will be discussed briefly, but
be aware that written permission should always be obtained from the system
administrator before using these programs against a system.
L0phtcrack
L0phtCrack is a Windows NT password-auditing tool from the L0pht that came
onto the scene in 1997. It provides several different mechanisms for retrieving the
passwords from the hashes, but is used primarily for its brute force capabilities.
The character sets chosen dictate the amount of time and processing power necessary
to search the entire keyspace.Obviously, the larger the character set
chosen, the longer it will take to complete the attack. However, dictionary based
attacks, which use only common words against the password database are normally
quite fast and often effective in catching the poorest passwords.Table 6.1
lists the time required for L0phtcrack 2.5 to crack passwords based on the character
set selected.
Table 6.1 L0phtcrack 2.5 Brute Force Crack Time Using a Quad Xeon 400
MHz Processor
Test: Brute Force Crack
Machine: Quad Xeon 400 MHz
Character Set Time
Alpha-Numeric 5.5 Hours
Alpha-Numeric-Some Symbols 45 Hours
Alpha-Numeric-All Symbols 480 Hours
Used with permission of the L0pht
L0pht Heavy Industries, the developers of L0phtcrack, have since sold the
rights to the software to @stake Security. Since the sale,@stake has released a
program called LC3, which is intended to be L0phtcrack’s successor. LC3
includes major improvements over L0phtcrack 2.5, such as distributed cracking
and a simplified sniffing attachment that allows password hashes to be sniffed over
Ethernet. Additionally, LC3 includes a password-cracking wizard to help the less
knowledgeable audit their system passwords. Figure 6.2 shows LC3 displaying the
output of a dictionary attack against some sample user passwords.
LC3 reflects a number of usability advances since the older L0phtcrack 2.5
program, and the redesigned user interface is certainly one of them. Both
www.syngress.com
Cryptography • Chapter 6 181
L0phtCrack and LC3 are commercial software packages. However, a 15-day trial
can be obtained at www.atstake.com/research/lc3/download.html.
Crack
The oldest and most widely used UNIX password cracking utility is simply called
Crack. Alec Muffett is the author of Crack, which he calls a password-guessing
program for UNIX systems. It runs only on UNIX systems against UNIX passwords,
and is for the most part a dictionary-based program. However, in the latest
release available (v5.0a from 1996), Alec has bundled Crack7, a brute force password
cracker that can be used if a dictionary-based attack fails. One of the most
interesting aspects of this combination is that Crack can test for common variants
that people use when they think they are picking more secure passwords. For
example, instead of “password,” someone may choose “pa55word.” Crack has
user-configurable permutation rules that will catch these variants. More information
on Alec Muffett and Crack is available at www.users.dircon.co.uk/~crypto.
www.syngress.com
Figure 6.2 Output of a Simple Dictionary-Based Attack
182 Chapter 6 • Cryptography
John the Ripper
John the Ripper is another password-cracking program, but it differs from Crack
in that it is available in UNIX, DOS, and Win32 editions. Crack is great for older
systems using crypt(), but John the Ripper is better for newer systems using MD5
and similar password formats. John the Ripper is used primarily for UNIX passwords,
but there are add-ons available to break other types of passwords, such as
Windows NT LanManager (LANMAN) hashes and Netscape Lightweight
Directory Access Protocol (LDAP) server passwords. John the Ripper supports
brute force attacks in incremental mode. Because of John the Ripper’s architecture,
one of its most useful features is its ability to save its status automatically during
the cracking process, which allows for aborted cracking attempts to be restarted
even on a different system. John the Ripper is part of the OpenWall project and
is available from www.openwall.com/john.
A sample screenshot of John the Ripper is shown in Figure 6.3. In this
example, a sample section of a password file in OpenBSD format is cracked using
John the Ripper. Shown below the password file snippet is the actual output of
John the Ripper as it runs.You can see that each cracked password is displayed on
the console. Be aware that the time shown to crack all four passwords is barely over
a minute only because I placed the actual passwords at the top of the “password.lst”
listing, which John uses as its dictionary. Real attempts to crack passwords would
take much longer.After John has cracked a password file, you can have John display
the password file in unshadowed format using the show option.
www.syngress.com
Figure 6.3 Sample Screenshot of John the Ripper
Cryptography • Chapter 6 183
Knowing When Real Algorithms
Are Being Used Improperly
While theoretically, given enough time, almost any encryption standard can be
cracked with brute force, it certainly isn’t the most desirable method to use when
“theoretically enough time” is longer than the age of the universe.Thus, any
shortcut method that a hacker can use to break your encryption will be much
more desirable to him than brute force methods.
None of the encryption algorithms discussed in this chapter have any serious
flaws associated with the algorithms themselves, but sometimes the way the algorithm
is implemented can create vulnerabilities. Shortcut methods for breaking
encryption usually result from a vendor’s faulty implementation of a strong
encryption algorithm, or lousy configuration from the user. In this section, we’ll
discuss several incidents of improperly used encryption that are likely to be
encountered in the field.
Bad Key Exchanges
Because there isn’t any authentication built into the Diffie-Hellman algorithm,
implementations that use Diffie-Hellman-type key exchanges without some sort
of authentication are vulnerable to man-in-the-middle (MITM) attacks.The most
notable example of this type of behavior is the SSH-1 protocol. Since the protocol
itself does not authenticate the client or the server, it’s possible for someone
to cleverly eavesdrop on the communications.This deficiency was one of the
main reasons that the SSH-2 protocol was completely redeveloped from SSH-1.
The SSH-2 protocol authenticates both the client and the server, and warns of or
prevents any possible MITM attacks, depending on configuration, so long as the
client and server have communicated at least once. However, even SSH-2 is vulnerable
to MITM attacks prior to the first key exchange between the client and
the server.
As an example of a MITM-type attack, consider that someone called Al is
performing a standard Diffie-Hellman key exchange with Charlie for the very
first time, while Beth is in a position such that all traffic between Al and Charlie
passes through her network segment. Assuming Beth doesn’t interfere with the
key exchange, she will not be able to read any of the messages passed between Al
and Charlie, because she will be unable to decrypt them. However, suppose that
Beth intercepts the transmissions of Al and Charlie’s public keys and she responds
to them using her own public key. Al will think that Beth’s public key is actually
www.syngress.com
184 Chapter 6 • Cryptography
Charlie’s public key and Charlie will think that Beth’s public key is actually Al’s
public key.
When Al transmits a message to Charlie, he will encrypt it using Beth’s public
key. Beth will intercept the message and decrypt it using her private key. Once
Beth has read the message, she encrypts it again using Charlie’s public key and
transmits the message on to Charlie. She may even modify the message contents
if she so desires. Charlie then receives Beth’s modified message, believing it to
come from Al. He replies to Al and encrypts the message using Beth’s public key.
Beth again intercepts the message, decrypts it with her private key, and modifies
it.Then she encrypts the new message with Al’s public key and sends it on to Al,
who receives it and believes it to be from Charlie.
Clearly, this type of communication is undesirable because a third party not
only has access to confidential information, but she can also modify it at will. In
this type of attack, no encryption is broken because Beth does not know either
Al or Charlie’s private keys, so the Diffie-Hellman algorithm isn’t really at fault.
Beware of the key exchange mechanism used by any public key encryption
system. If the key exchange protocol does not authenticate at least one and
preferably both sides of the connection, it may be vulnerable to MITM-type
attacks. Authentication systems generally use some form of digital certificates
(usually X.509), such as those available from Thawte or VeriSign.
Hashing Pieces Separately
Older Windows-based clients store passwords in a format known as LanManager
(LANMAN) hashes, which is a horribly insecure authentication scheme.
However, since this chapter is about cryptography, we will limit the discussion of
LANMAN authentication to the broken cryptography used for password storage.
As with UNIX password storage systems, LANMAN passwords are never
stored on a system in cleartext format—they are always stored in a hash format.
The problem is that the hashed format is implemented in such a way that even
though DES is used to encrypt the password, the password can still be broken
with relative ease. Each LANMAN password can contain up to 14 characters, and
all passwords less than 14 characters are padded to bring the total password length
up to 14 characters. During encryption the password is split into a pair of sevencharacter
passwords, and each of these seven-character passwords is encrypted
with DES.The final password hash consists of the two concatenated DESencrypted
password halves.
www.syngress.com
Cryptography • Chapter 6 185
Since DES is known to be a reasonably secure algorithm, why is this implementation
flawed? Shouldn’t DES be uncrackable without significant effort? Not
exactly. Recall that there are roughly 100 different characters that can be used in
a password. Using the maximum possible password length of 14 characters, there
should be about 10014 or 1.0x1028 possible password combinations. LANMAN
passwords are further simplified because there is no distinction between upperand
lowercase letters—all letters appears as uppercase. Furthermore, if the password
is less than eight characters, then the second half of the password hash is
always identical and never even needs to be cracked. If only letters are used (no
numbers or punctuation), then there can only be 267 (roughly eight billion) password
combinations.While this may still seem like a large number of passwords to
attack via brute force, remember that these are only theoretical maximums and
that since most user passwords are quite weak, dictionary-based attacks will
uncover them quickly.The bottom line here is that dictionary-based attacks on a
pair of seven-character passwords (or even just one) are much faster than those on
single 14-character passwords.
Suppose that strong passwords that use two or more symbols and numbers are
used with the LANMAN hashing routine.The problem is that most users tend to
just tack on the extra characters at the end of the password. For example, if a user
uses his birthplace along with a string of numbers and symbols, such as “MONTANA45%,”
the password is still insecure. LANMAN will break this password
into the strings “MONTANA” and “45%.”The former will probably be caught
quickly in a dictionary-based attack, and the latter will be discovered quickly in
a brute force attack because it is only three characters. For newer businessoriented
Microsoft operating systems such as Windows NT and Windows 2000,
LANMAN hashing can and should be disabled in the registry if possible, though
this will make it impossible for Win9x clients to authenticate to those machines.
Using a Short Password to Generate a Long Key
Password quality is a subject that we have already briefly touched upon in our
discussion of brute force techniques.With the advent of PKE encryption schemes
such as PGP, most public and private keys are generated using passwords or
passphrases, leaving the password generation steps vulnerable to brute force
attacks. If a password is selected that is not of significant length, that password can
be brute force attacked in an attempt to generate the same keys as the user.Thus
PKE systems such as RSA have a chance to be broken by brute force, not
because of any deficiency in the algorithm itself, but because of deficiencies in
www.syngress.com
186 Chapter 6 • Cryptography
the key generation process.The best way to protect against these types of roundabout
attacks is to use strong passwords when generating any sort of encryption
key. Strong passwords include the use of upper- and lowercase letters, numbers,
and symbols, preferably throughout the password. Eight characters is generally
considered the minimum length for a strong password, but given the severity of
choosing a poor password for key generation, I recommend you use at least
twelve characters for these instances.
High quality passwords are often said to have high entropy, which is a semi-
finite measurement that attempts to quantify the relative quality of a password.
Longer passwords typically have more entropy than shorter passwords, and the
more random each character of the password is, the more entropy in the password.
For example, the password “albatross” (about 30 bits of entropy) might be
reasonably long in length, but has less entropy than a totally random password of
the same length such as “g8%=MQ+p” (about 48 bits of entropy). Since the
former might appear in a list of common names for bird species, while the latter
would never appear in a published list, obviously the latter is a stronger and
therefore more desirable password.The moral of the story here is that strong
encryption such as 168-bit 3-DES can be broken easily if the secret key has only
a few bits of entropy.
Improperly Stored Private or Secret Keys
Let’s say you have only chosen to use the strong cryptography algorithms, you
have verified that there are not any flaws in the vendors’ implementations, and
you have generated your keys with great care. How secure is your data now? It is
still only as secure as your private or secret key.These keys must be safeguarded at
all costs, or you may as well not even use encryption.
Since keys are simply strings of data, they are usually stored in a file somewhere
in your system’s hard disk. For example, private keys for SSH-1 are stored
in the identity file located in the .ssh directory under a user’s home directory. If
the filesystem permissions on this file allow others to access the file, then this private
key is compromised. Once others have your private or secret key, reading
your encrypted communications becomes trivial. (Note that the SSH identity file
is used for authentication, not encryption; but you get the idea.)
However, in some vendor implementations, your keys could be disclosed to
others because the keys are not stored securely in RAM. As you are aware, any
information processed by a computer, including your secret or private key, is
located in the computer’s RAM at some point. If the operating system’s kernel
www.syngress.com
Cryptography • Chapter 6 187
does not store these keys in a protected area of its memory, they could conceivably
become available to someone who dumps a copy of the system’s RAM to a
file for analysis.These memory dumps are called core dumps in UNIX, and they
are commonly created during a denial of service (DoS) attack.Thus a successful
hacker could generate a core dump on your system and extract your key from
the memory image. In a similar attack, a DoS attack could cause excess memory
usage on the part of the victim, forcing the key to be swapped to disk as part of
virtual memory. Fortunately, most vendors are aware of this type of exploit by
now, and it is becoming less and less common since encryption keys are now
being stored in protected areas of memory.
www.syngress.com
Netscape’s Original SSL Implementation:
How Not to Choose Random Numbers
As we have tried to point out in this section, sometimes it does not
matter if you are using an algorithm that is known to be secure. If your
algorithm is being applied incorrectly, there will be security holes. An
excellent example of a security hole resulting from misapplied cryptography
is Netscape’s poor choice of random number seeds used in the
Secure Sockets Layer (SSL) encryption of its version 1.1 browser. You no
doubt note that this security flaw is several years old and thus of limited
importance today. However, below the surface we’ll see that this particular
bug is an almost classic example of one of the ways in which vendors
implement broken cryptography, and as such it continues to remain
relevant to this day. We will limit this discussion to the vulnerability in
the UNIX version of Netscape’s SSL implementation as discovered by Ian
Goldberg and David Wagner, although the PC and Macintosh versions
were similarly vulnerable.
Before I can explain the exact nature of this security hole we will
need to cover some background information, such as SSL technology
and random numbers. SSL is a certificate-based authentication and
encryption scheme developed by Netscape during the fledgling days of
e-commerce. It was intended to secure communications such as credit
card transactions from eavesdropping by would-be thieves. Because of
U.S. export restrictions, the stronger and virtually impervious 128-bit
(key) version of the technology was not in widespread use. In fact, even
Tools & Traps…
Continued
188 Chapter 6 • Cryptography
Understanding Amateur
Cryptography Attempts
If your data is not being protected by one of the more modern, computationally
secure algorithms that we’ve already discussed in this chapter, or some similar
variant, then your data is probably not secure. In this section, we’re going to discover
how simple methods of enciphering data can be broken using rudimentary
cryptanalysis.
www.syngress.com
domestically, most of Netscape’s users were running the anemic 40-bit
international version of the software.
Most key generation, including SSL key generation, requires some
form of randomness as a factor of the key generation process. Arbitrarily
coming up with random numbers is much harder than it sounds, especially
for machines. So we usually end up using pseudo-random numbers
that are devised from mostly random events, such as the time
elapsed between each keystroke you type or the movement of your
mouse across the screen.
For the UNIX version of its version 1.1 browser, Netscape used a
conglomeration of values, such as the current time, the process ID (PID)
number of the Netscape process and its parent’s process ID number.
Suppose the attacker had access to the same machine as the Netscape
user simultaneously, which is the norm in UNIX-based multi-user architectures.
It would be trivial for the attacker to generate a process listing
to discover Netscape’s PID and its parent’s PID. If the attacker had the
ability to capture TCP/IP packets coming into the machine, he could use
the timestamps on these packets to make a reasonable guess as to the
exact time the SSL certificate was generated. Once this information was
gathered, the attacker could narrow down the keyspace to about 106
combinations, which is then brute force attacked with ease at near realtime
speeds. Upon successfully discovering Netscape’s SSL certificate
seed generation values, he can generate an identical certificate for himself
and either eavesdrop or hijack the existing session.
Clearly, this was a serious security flaw that Netscape would need
to address in its later versions, and it did, providing patches for the 1.x
series of browsers and developing a new and substantially different
random number generator for its 2.x series of browsers. You can read
more details about this particular security flaw in the archives of Dr.
Dobbs’ Journal at www.ddj.com/documents/s=965/ddj9601h.
Cryptography • Chapter 6 189
Classifying the Ciphertext
Even a poorly encrypted message often looks indecipherable at first glance, but
you can sometimes figure out what the message is by looking beyond just the
stream of printed characters. Often, the same information that you can “read
between the lines” on a cleartext message still exists in an enciphered message.
For the mechanisms discussed below, all the “secrecy” is contained in the
algorithm, not in a separate key. Our challenge for these is to figure out the algorithm
used. So for most of them, that means that we will run a password or some
text through the algorithm, which will often be available to us in the form of a
program or other black box device. By controlling the inputs and examining the
outputs, we hope to determine the algorithm.This will enable us to later take an
arbitrary output and determine what the input was.
NOTE
The techniques described in this section are largely ineffective on modern
algorithms such as DES and its successors. What few techniques do exist
to gain information from modern ciphertext are quite complicated and
only work under special conditions.
Frequency Analysis
The first and most powerful method you can employ to crack simple ciphertext
is frequency analysis, which is based on the idea that certain letters are used more
often than others. For example, I can barely write a single word in this sentence
that doesn’t include the letter e. How can letter frequency be of use? You can
create a letter frequency table for your ciphertext, assuming the message is of suf-
ficient length, and compare that table to one charting the English language (there
are many available).That would give you some clues about which characters in
the ciphertext might match up with cleartext letters.
The astute reader will discover that some letters appear with almost identical
frequency. How then can you determine which letter is which? You can either
evaluate how the letters appear in context, or you can consult other frequency
tables that note the appearance of multiple letter combinations such as sh, ph, ie
and the.
www.syngress.com
190 Chapter 6 • Cryptography
Crypto of this type is just a little more complicated than the Caesar Cipher
mentioned at the beginning of the chapter.This was state-of-the-art hundreds of
years ago. Now problems of this type are used in daily papers for commuter
entertainment, under the titles of “Cryptogram,”“CryptoQuote,” or similar. Still,
some people will use this method as a token effort to hide things.This type of
mechanism, or ones just slightly more complex, show up in new worms and
viruses all the time.
Ciphertext Relative Length Analysis
Sometimes the ciphertext can provide you with clues to the cleartext even if you
don’t know how the ciphertext was encrypted. For example, suppose that you
have an unknown algorithm that encrypts passwords such that you have available
the original password and a ciphertext version of that password. If the length or
size of each is the same, then you can infer that the algorithm produces output in
a 1:1 ratio to the input.You may even be able to input individual characters to
obtain the ciphertext translation for each character. If nothing else, you at least
know how many characters to specify for an unknown password if you attempt
to break it using a brute force method.
If you know that the length of a message in ciphertext is identical to the
length of a message in cleartext, you can leverage this information to pick out
pieces of the ciphertext for which you can make guesses about the cleartext. For
example, during WWII while the Allies were trying to break the German Enigma
codes, they used a method similar to the above because they knew the phrase
“Heil Hitler” probably appeared somewhere near the end of each transmission.
Similar Plaintext Analysis
A related method you might use to crack an unknown algorithm is to compare
changes in the ciphertext output with changes in the cleartext input. Of course,
this method requires that you have access to the algorithm to selectively encode
your carefully chosen cleartext. For example, try encoding the strings
“AAAAAA,”“AAAAAB” and “BAAAAA” and note the difference in the ciphertext
output. For monoalphabetic ciphers, you might expect to see the first few
characters remain the same in both outputs for the first two, with only the last
portion changing. If so, then it’s almost trivial to construct a full translation table
for the entire algorithm that maps cleartext input to ciphertext output and vice
versa. Once the translation table is complete, you could write an inverse function
that deciphers the ciphertext back to plaintext without difficulty.
www.syngress.com
Cryptography • Chapter 6 191
What happens if the cipher is a polyalphabetic cipher, where more than one
character changes in the ciphertext for single character changes in cleartext? Well,
that becomes a bit trickier to decipher, depending on the number of changes to
the ciphertext.You might be able to combine this analysis technique with brute
force to uncover the inner workings of the algorithm, or you might not.
Monoalphabetic Ciphers
A monoalphabetic cipher is any cipher in which each character of the alphabet
is replaced by another character in a one-to-one ratio. Both the Caesar Cipher
and ROT13, mentioned earlier in the chapter, are classic examples of monoalphabetic
ciphers. Some monoalphabetic ciphers scramble the alphabet instead
of shifting the letters, so that instead of having an alphabet of ABCDEFGHIJKLMNOPQRSTUVWXYZ,
the cipher alphabet order might be MLNKBJVHCGXFZDSAPQOWIEURYT.
The new scrambled alphabet is used to
encipher the message such that M=A, L=B…T=Z. Using this method, the
cleartext message “SECRET” becomes “OBNQBW.”
You will rarely find these types of ciphers in use today outside of word games
because they can be easily broken by an exhaustive search of possible alphabet
combinations and they are also quite vulnerable to the language analysis methods
we described. Monoalphabetic ciphers are absolutely vulnerable to frequency
analysis because even though the letters are substituted, the ultimate frequency
appearance of each letter will roughly correspond to the known frequency characteristics
of the language.
Other Ways to Hide Information
Sometimes vendors follow the old “security through obscurity” approach, and
instead of using strong cryptography to prevent unauthorized disclosure of certain
information, they just try to hide the information using a commonly known
reversible algorithm like UUEncode or Base64, or a combination of two simple
methods. In these cases, all you need to do to recover the cleartext is to pass the
ciphertext back through the same engine.Vendors may also use XOR encoding
against a certain key, but you won’t necessarily need the key to decode the message.
Let’s look at some of the most common of these algorithms in use.
XOR
While many of the more complex and secure encryption algorithms use XOR
as an intermediate step, you will often find data obscured by a simple XOR
www.syngress.com
192 Chapter 6 • Cryptography
operation. XOR is short for exclusive or, which identifies a certain type of binary
operation with a truth table as shown in Table 6.2. As each bit from A is combined
with B, the result is “0” only if the bits in A and B are identical. Otherwise,
the result is 1.
Table 6.2 XOR Truth Table
A B A XOR B
0 0 0
0 1 1
1 0 1
1 1 0
Let’s look at a very simple XOR operation and how you can undo it. In our
simple example, we will use a single character key (“a”) to obscure a single character
message (“b”) to form a result that we’ll call “ciphertext” (see Table 6.3).
Table 6.3 XOR of “a” and “b”
Item Binary Value
a 01100001
b 01100010
ciphertext 00000011
Suppose that you don’t know what the value of “a” actually is, you only
know the value of “b” and the resulting “ciphertext.”You want to recover the key
so that you can find out the cleartext value of another encrypted message,
“cipher2,” which is 00011010.You could perform an XOR with “b” and the
“ciphertext” to recover the key “a,” as shown in Table 6.4.
Table 6.4 XOR of “ciphertext” and “b”
Item Binary Value
ciphertext 00000011
b 01100010
a 01100001
www.syngress.com
Cryptography • Chapter 6 193
Once the key is recovered, you can use it to decode “cipher2” into the character
“z” (see Table 6.5).
Table 6.5 XOR of “cipher2” and “a”
Item Binary Value
cipher2 00011010
a 01100001
z 01111010
Of course, this example is somewhat oversimplified. In the real world, you are
most likely to encounter keys that are multiple characters instead of just a single
character, and the XOR operation may occur a number of times in series to
obscure the message. In this type of instance, you can use a null value to obtain
the key—that is, the message will be constructed such that it contains only 0s.
Abstract 1 and 0 manipulation like this can be difficult to understand if you
are not used to dealing with binary numbers and values.Therefore, I’ll provide
you with some sample code and output of a simple program that uses a series of
3 XOR operations on various permutations of a key to obscure a particular message.
This short Perl program uses the freely available IIIkey module for the backend
XOR encryption routines.You will need to download IIIkey from
www3.marketrends.net/encrypt/ to use this program.
#!/usr/bin/perl
# Encodes/Decodes a form of XOR text
# Requires the IIIkey module
# Written specifically for HPYN 2nd Ed.
# by FWL 01.07.02
# Use the IIIkey module for the backend
# IIIkey is available from http://www3.marketrends.net/encrypt/
use IIIkey;
# Simple input validation
sub validate() {
if (scalar(@ARGV) < 3) {
print "Error: You did not specify input correctly!\n";
www.syngress.com
194 Chapter 6 • Cryptography
print "To encode data use ./xor.pl e \"Key\" \"String to
Encode\"\n";
print "To decode data use ./xor.pl d \"Key\" \"String to
Decode\"\n";
exit;
}
}
validate();
$tmp=new IIIkey;
$key=$ARGV[1];
$intext=$ARGV[2];
if ($ARGV[0] eq "e") { # encode text
$outtext=$tmp->crypt($intext, $key);
print "Encoded $intext to $outtext";
} elsif ($ARGV[0] eq "d") { # decode text
$outtext=$tmp->decrypt($intext, $key);
print "Decoded $intext to $outtext";
} else { # No encode/decode information given!
print "To encode or decode? That is the question.";
exit;
}
Here’s some sample output:
$ ./xor.pl e "my key" "secret message"
Encoded secret message to 8505352480^0758144+510906534
$ ./xor.pl d "my key" "8505352480^0758144+510906534"
Decoded 8505352480^0758144+510906534 to secret message
www.syngress.com
Cryptography • Chapter 6 195
UUEncode
UUEncode is a commonly used algorithm for converting binary data into a textbased
equivalent for transport via e-mail. As you probably know, most e-mail systems
cannot directly process binary attachments to e-mail messages. So when you
attach a binary file (such as a JPEG image) to an e-mail message, your e-mail
client takes care of converting the binary attachment to a text equivalent, probably
through an encoding engine like UUEncode.The attachment is converted
from binary format into a stream of printable characters, which can be processed
by the mail system. Once received, the attachment is processed using the inverse
of the encoding algorithm (UUDecode), resulting in conversion back to the
original binary file.
Sometimes vendors may use the UUEncode engine to encode ordinary
printable text in order to obscure the message.When this happens, all you need
to do to is pass the encoded text through a UUDecode program to discern the
message. Command-line UUEncode/UUDecode clients are available for just
about every operating system ever created.
Base64
Base64 is also commonly used to encode e-mail attachments similar to
UUEncode, under Multipurpose Internet Mail Extensions (MIME) extensions.
However, you are also likely to come across passwords and other interesting information
hidden behind a Base64 conversion. Most notably, many Web servers that
implement HTTP-based basic authentication store password data in Base64
format. If your attacker can get access to the Base64 encoded username and password
set, he or she can decode them in seconds, no brute force required. One of
the telltale signs that a Base64 encode has occurred is the appearance of one or
two equal signs ( = ) at the end of the string, which is often used to pad data.
Look at some sample code for converting between Base64 data and cleartext.
This code snippet should run on any system that has Perl5 or better with the
MIME::Base64 module from CPAN (www.cpan.org).We have also given you a
couple of usage samples.
#!/usr/bin/perl
# Filename: base64.pl
# Encodes/Decodes Base-64 text
# Requires the MIME::Base64 module
# Written specifically for HPYN 2nd Ed.
www.syngress.com
196 Chapter 6 • Cryptography
# by FWL 01.07.02
# Use the MIME module for encoding/decoding Base-64 strings
use MIME::Base64;
# Simple input validation
sub validate() {
if (scalar(@ARGV) < 2) {
print "Error: You did not specify input correctly!\n";
print "To encode data use ./base64.pl e \"String to Encode\"\n";
print "To decode data use ./base64.pl d \"String to Decode\"\n";
exit;
}
}
validate();
$intext=$ARGV[1];
if ($ARGV[0] eq "e") { # encode text
$outtext=encode_base64($intext);
print "Encoded $intext to $outtext";
} elsif ($ARGV[0] eq "d") { # decode text
$outtext=decode_base64($intext);
print "Decoded $intext to $outtext";
} else { # No encode/decode information given!
print "To encode or decode? That is the question.";
exit;
}
Here’s some sample output:
$ ./base64.pl e "Secret Password"
Encoded Secret Password to U2VjcmV0IFBhc3N3b3Jk
www.syngress.com
Cryptography • Chapter 6 197
$ ./base64.pl d "U2VjcmV0IFBhc3N3b3Jk"
Decoded U2VjcmV0IFBhc3N3b3Jk to Secret Password
Compression
Sometimes you may find that compression has been weakly used to conceal
information from you. In days past, some game developers would compress the
size of their save game files not only to reduce space, but also to limit your
attempts to modify it with a save game editor.The most commonly used algorithms
for this were SQSH (Squish or Squash) and LHA.The algorithms themselves
were somewhat inherited from console games of the 1980s, where they
were used to compress the ROM images in the cartridges. As a rule, when you
encounter text that you cannot seem to decipher via standard methods, you may
want to check to see if the information has been compressed using one of the
plethora of compression algorithms available today.
www.syngress.com
Consumer-Oriented Crypto—
The SDMI Hacking Challenge
Sometimes organizations decide to use cryptography that isn’t necessarily
amateur, but shouldn’t really be considered professional grade
either. For example, the Secure Digital Music Initiative (SDMI) is trying to
develop a watermarking scheme for digital music that carries an extraencoded
signal that prevents the music from being played or copied in
an unauthorized manner. In developing its watermarking scheme, the
SDMI proposed six watermarking schemes to the hacking community
and offered up a $10,000 prize to whoever could break the watermarking
technology, producing a song without any watermark from a
sample song with a watermark. Only samples of the watermarked songs
were made available; the SDMI did not release any details about how
the watermarking schemes themselves worked. A before-and-after
sample of a different song was provided for each of the watermarking
schemes, so that differences could be noted.
Two of the six watermarking schemes were dropped shortly after
the contest began, and the remaining four were ultimately broken
Notes from the Underground…
Continued
198 Chapter 6 • Cryptography
www.syngress.com
within weeks by a team of academic researchers led by Princeton
Professor Edward W. Felten. Felten and his associates chose not to
accept the $10,000 bounty, opting instead to publicly publish the results
of their research. It seems there was a small loophole in the agreement
that was presented to challengers before they would be given the files.
It said that they had to agree to keep all information secret in order to
collect the $10,000. It didn’t say anything about what would happen if
the challenger wasn’t interested in the money. Shortly thereafter, the
seemingly upset SDMI threatened a lawsuit under the provisions of the
Digital Millennium Copyright Act (DMCA) that prevented the sharing of
knowledge that could be used to circumvent copyright protection
schemes. Ultimately the SDMI chose not to pursue the matter, and Felten
and his associates presented their findings at the 10th USENIX Security
Symposium. Felten’s conclusion, which is generally shared by the security
community at large, was that any attempts at watermarking-type
encryption would ultimately be broken. Also of interest is the fact that
Felten’s team identified that no special knowledge in computer science
was needed to break the watermarking schemes; only a general knowledge
of signal processing was required.
You might view this story as yet another example of a vendor
attempting to employ what they proclaim to be “highly secure proprietary
algorithms,” but it is also an example of the continuing evolution
of cryptography and its applications in new ways. Even if these new
applications of cryptography don’t lend themselves well to the use of
conventional algorithms, you would be wise to remain skeptical of
newly proposed unproven algorithms, especially when these algorithms
are kept secret.
Cryptography • Chapter 6 199
Summary
This chapter looked into the meaning of cryptography and some of its origins,
including the Caesar Cipher. More modern branches of cryptography are symmetric
and asymmetric cryptography, which are also known as secret key and public
key cryptography, respectively.
The most common symmetric algorithms in use today include DES,AES, and
IDEA. Since DES is showing its age, we looked at how NIST managed the
development of AES as a replacement, and how Rijndael was selected from five
finalists to become the AES algorithm. From the European perspective, we saw
how IDEA came to be developed in the early 1990s and examined its advantages
over DES.
The early development of asymmetric cryptography was begun in the mid-
1970s by Diffie and Hellman, who developed the Diffie-Hellman key exchange
algorithm as a means of securely exchanging information over a public network.
After Diffie-Hellman, the RSA algorithm was developed, heralding a new era of
public key cryptography systems such as PGP. Fundamental differences between
public key and symmetric cryptography include public key cryptography’s
reliance on the factoring problem for extremely large integers.
Brute force is an effective method of breaking most forms of cryptography,
provided you have the time to wait for keyspace exhaustion, which could take
anywhere from several minutes to billions of years. Cracking passwords is the
most widely used application of brute force; programs such as L0phtcrack and
John the Ripper are used exclusively for this purpose.
Even secure algorithms can be implemented insecurely, or in ways not
intended by the algorithm’s developers. Man-in-the-middle attacks could cripple
the security of a Diffie-Hellman key exchange, and even DES-encrypted
LANMAN password hashes can be broken quite easily. Using easily broken passwords
or passphrases as secret keys in symmetric algorithms can have unpleasant
effects, and improperly stored private and secret keys can negate the security provided
by encryption altogether.
Information is sometimes concealed using weak or reversible algorithms.We
saw in this chapter how weak ciphers are subject to frequency analysis attacks
that use language characteristics to decipher the message. Related attacks include
relative length analysis and similar plaintext analysis.We saw how vendors sometimes
conceal information using XOR and Base64 encoding and looked at some
sample code for each of these types of reversible ciphers.We also saw how, on
occasion, information is compressed as a means of obscuring it.
www.syngress.com
200 Chapter 6 • Cryptography
Solutions Fast Track
Understanding Cryptography Concepts
Unencrypted text is referred to as cleartext, while encrypyted text is
called ciphertext.
The two main categories of cryptography are symmetric key and
asymmetric key cryptography. Symmetric key cryptography uses a single
secret key, while asymmetric key cryptography uses a pair of public and
private keys.
Public key cryptography was first devised as a means of exchanging a
secret key securely by Diffie and Hellman.
Learning about Standard Cryptographic Algorithms
The reason why so many cryptographic algorithms are available for your
use is that each algorithm has its own relative speed, security and ease of
use.You need to know enough about the most common algorithms to
choose one that is appropriate to the situation to which it will be
applied.
Data Encryption Standard (DES) is the oldest and most widely known
modern encryption method around. However, it is nearing the end of its
useful life span, so you should avoid using it in new implementations or
for information you want to keep highly secure.
Advanced Encryption Standard (AES) was designed as a secure
replacement for DES, and you can use several different keysizes with it.
Be aware that asymmetric cryptography uses entirely different principles
than symmetric cryptography.Where symmetric cryptography combines
a single key with the message for a number of cycles, asymmetric
cryptography relies on numbers that are too large to be factored.
The two most widely used asymmetric algorithms are Diffie-Hellman
and RSA.
www.syngress.com
Cryptography • Chapter 6 201
Understanding Brute Force
Brute force is the one single attack that will always succeed against
symmetric cryptography, given enough time.You want to ensure that
“enough time” becomes a number of years or decades or more.
An individual machine performing a brute force attack is slow. If you
can string together a number of machines in parallel, your brute force
attack will be much faster.
Brute force attacks are most often used for cracking passwords.
Knowing When Real Algorithms
Are Being Used Improperly
Understand the concept of the man-in-the-middle attack against a
Diffie-Hellman key exchange.
LANMAN password hashing should be disabled, if possible, because its
implementation allows it to be broken quite easily.
Key storage should always be of the utmost importance to you because if
your secret or private key is compromised, all data protected by those
keys is also compromised.
Understanding Amateur Cryptography Attempts
You can crack almost any weak cryptography attempts (like XOR) with
minimal effort.
Frequency analysis is a powerful tool to use against reasonably lengthy
messages that aren’t guarded by modern cryptography algorithms.
Sometimes vendors will attempt to conceal information using weak
cryptography (like Base64) or compression.
www.syngress.com
202 Chapter 6 • Cryptography
Q: Are there any cryptography techniques which are 100 percent secure?
A: Yes. Only the One Time Pad (OTP) algorithm is absolutely unbreakable if
implemented correctly.The OTP algorithm is actually a Vernam cipher,
which was developed by AT&T way back in 1917.The Vernam cipher
belongs to a family of ciphers called stream ciphers, since they encrypt data in
continuous stream format instead of the chunk-by-chunk method of block
ciphers.There are two problems with using the OTP, however:You must have
a source of truly random data, and the source must be bit-for-bit as long as
the message to be encoded.You also have to transmit both the message and
the key (separately), the key must remain secret, and the key can never be
reused to encode another message. If an eavesdropper intercepts two messages
encoded with the same key, then it is trivial for the eavesdropper to recover
the key and decrypt both messages.The reason OTP ciphers are not used
more commonly is the difficulty in collecting truly random numbers for the
key (as mentioned in one of the sidebars for this chapter) and the difficulty of
the secure distribution of the key.
Q: How long is DES expected to remain in use?
A: Given the vast number of DES-based systems, I expect we’ll continue to see
DES active for another five or ten years, especially in areas where security is
not a high priority. For some applications, DES is considered a “good enough”
technology since the average hacker doesn’t have the resources available (for
now) to break the encryption scheme efficiently. I predict that DES will still
find a use as a casual eavesdropping deterrent, at least until the widespread
adoption of IPv6. DES is also far faster than 3-DES, and as such it is more
suitable to older-style VPN gear that may not be forward-compatible with the
new AES standard. In rare cases where legacy connections are required, the
government is still allowing new deployment of DES-based systems.
www.syngress.com
Frequently Asked Questions
The following Frequently Asked Questions, answered by the authors of this book,
are designed to both measure your understanding of the concepts presented in
this chapter and to assist you with real-life implementation of these concepts. To
have your questions about this chapter answered by the author, browse to
www.syngress.com/solutions and click on the “Ask the Author” form.
Cryptography • Chapter 6 203
Q: After the 9/11 attacks I’m concerned about terrorists using cryptography, and
I’ve heard people advocate that the government should have a back door
access to all forms of encryption.Why would this be a bad idea?
A: Allowing back-door access for anyone causes massive headaches for users of
encryption. First and foremost, these back door keys are likely to be stored all
in one place, making that storage facility the prime target for hackers.When
the storage facility is compromised, and I have no doubt that it would be (the
only question is how soon), everyone’s data can effectively be considered
compromised.We’d also need to establish a new bureaucracy that would be
responsible for handing out the back door access, probably in a manner similar
to the way in which wiretaps are currently doled out.We would also
require some sort of watchdog group that certifies the deployment group as
responsible. Additionally, all of our encryption schemes would need to be
redesigned to allow backdoor access, probably in some form of “public key +
trusted key” format. Implementation of these new encryption routines would
take months to develop and years to deploy. New cracking schemes would
almost certainly focus on breaking the algorithm through the “trusted key”
access, leaving the overall security of these routines questionable at best.
Q: Why was CSS, the encryption technology used to protect DVDs from unauthorized
copying, able to be broken so easily?
A: Basically,DVD copy protection was broken so easily because one entity, Xing
Technologies, left their key lying around in the open, which as we saw in this
chapter is a cardinal sin.The data encoded on a DVD-Video disc is encrypted
using an algorithm called the Content Scrambling System (CSS) which can be
unlocked using a 40-bit key. Using Xing’s 40-bit key, hackers were able to brute
force and guess at the keys for over 170 other licensees at a rapid pace.That
way, since the genie was out of the bottle, so to speak, for so many vendors, the
encryption for the entire format was basically broken.With so many keys to
choose from, others in the underground had no difficulty in leveraging these
keys to develop the DeCSS program, which allows data copied off of the DVD
to be saved to another media in an unencrypted format. Ultimately, the CSS
scheme was doomed to failure.You can’t put a key inside millions of DVD
players, distribute them, and not expect someone to eventually pull it out.