<<

. 6
( 29)



>>

CTF:




Page 117 of 666
Applied Cryptography: Second Edition - Bruce Schneier



I,Ek(I,v),d
(10) If a voter wants to change his vote (possible, in some elections) from v to v˜, he sends
the CTF:
I,Ek(I,v˜),d

A different voting protocol uses blind signatures instead of ANDOS, but is essentially the same [585].
Steps (1) through (3) are preliminary to the actual voting. Their purpose is to find out and publicize
the total number of actual voters. Although some of them probably will not participate, it reduces the
ability of the CTF to add fraudulent votes.

In step (4), it is possible for two voters to get the same identification number. This possibility can be
minimized by having far more possible identification numbers than actual voters. If two voters submit
votes with the same identification tag, the CTF generates a new identification number, I™, chooses one
of the two votes, and publishes:

I™,Ek(I,v)

The owner of that vote recognizes it and sends in a second vote, by repeating step (5), with the new
identification number.

Step (6) gives each voter the capability to check that the CTF received his vote accurately. If his vote
is miscounted, he can prove his case in step (9). Assuming a voter™s vote is correct in step (6), the
message he sends in step (9) constitutes a proof that his vote is miscounted.

One problem with the protocol is that a corrupt CTF could allocate the votes of people who respond
in step (2) but who do not actually vote. Another problem is the complexity of the ANDOS protocol.
The authors recommend dividing a large population of voters into smaller populations, such as
election districts.

Another, more serious problem is that the CTF can neglect to count a vote. This problem cannot be
resolved: Alice claims that the CTF intentionally neglected to count her vote, but the CTF claims that
the voter never voted.

Voting without a Central Tabulating Facility

The following protocol does away with the CTF entirely; the voters watch each other. Designed by
Michael Merritt [452, 1076, 453], it is so unwieldy that it cannot be implemented practically for more
than a handful of people, but it is useful to learn from nevertheless.


Alice, Bob, Carol, and Dave are voting yes or no (0 or 1) on a particular issue. Assume each voter has
a public and private key. Also assume that everyone knows everyone else™s public keys.

(1) Each voter chooses his vote and does the following:
(a) He attaches a random string to his vote.
(b) He encrypts the result of step (a) with Dave™s public key.
(c) He encrypts the result of step (b) with Carol™s public key.
(d) He encrypts the result of step (c) with Bob™s public key.
(e) He encrypts the result of step (d) with Alice™s public key.
(f) He attaches a new random string to the result of step (e) and encrypts it with
Dave™s public key. He records the value of the random string.
(g) He attaches a new random string to the result of step (f) and encrypts it with



Page 118 of 666
Applied Cryptography: Second Edition - Bruce Schneier



Carol™s public key. He records the value of the random string.
(h) He attaches a new random string to the result of step (g) and encrypts it with
Bob™s public key. He records the value of the random string.
(i) He attaches a new random string to the result of step (h) and encrypts it with
Alice™s public key. He records the value of the random string.
If E is the encryption function, R i is a random string, and V is the vote, his message looks
like:
EA(R5,EB(R4,EC(R3,ED(R2,EA(E B(EC(ED(V,R1))))))))

Each voter saves the intermediate results at each point in the calculation. These results
will be used later in the protocol to confirm that his vote is among those being counted.
(2) Each voter sends his message to Alice.
(3) Alice decrypts all of the votes with her private key and then removes all of the random
strings at that level.
(4) Alice scrambles the order of all the votes and sends the result to Bob.
Each vote now looks like this:
EB(R4,EC(R3,ED(R2,EA(EB(EC(ED(V,R1)))))))
(5) Bob decrypts all of the votes with his private key, checks to see that his vote is among
the set of votes, removes all the random strings at that level, scrambles all the votes, and then
sends the result to Carol.
Each vote now looks like this:
EC(R3,ED (R2,EA(EB(EC(ED(V,R1))))))
(6) Carol decrypts all of the votes with her private key, checks to see that her vote is
among the set of votes, removes all the random strings at that level, scrambles all the votes, and
then sends the result to Dave.
Each vote now looks like this:
ED(R2,EA(EB(EC(ED(V,R1)))))
(7) Dave decrypts all of the votes with his private key, checks to see that his vote is among
the set of votes, removes all the random strings at that level, scrambles all the votes, and sends
them to Alice.
Each vote now looks like this:
EA(EB(EC(ED(V,R1))))
(8) Alice decrypts all the votes with her private key, checks to see that her vote is among
the set of votes, signs all the votes, and then sends the result to Bob, Carol, and Dave.
Each vote now looks like this:
SA(EB(EC(ED(V,R1))))
(9) Bob verifies and deletes Alice™s signatures. He decrypts all the votes with his private
key, checks to see that his vote is among the set of votes, signs all the votes, and then sends the
result to Alice, Carol, and Dave.
Each vote now looks like this:
SB(EC(ED(V,R1)))
(10) Carol verifies and deletes Bob™s signatures. She decrypts all the votes with her
private key, checks to see that her vote is among the set of votes, signs all the votes, and then
sends the result to Alice, Bob, and Dave.
Each vote now looks like this:
SC(ED(V,R1))
(11) Dave verifies and deletes Carol™s signatures. He decrypts all the votes with his
private key, checks to see that his vote is among the set of votes, signs all the votes, and then
sends the result to Alice, Bob, and Carol.
Each vote now looks like this:




Page 119 of 666
Applied Cryptography: Second Edition - Bruce Schneier



SD(V,R1)
(12) All verify and delete Dave™s signature. They check to make sure that their vote is
among the set of votes (by looking for their random string among the votes).
(13) Everyone removes the random strings from each vote and tallies the votes.

Not only does this protocol work, it is also self-adjudicating. Alice, Bob, Carol, and Dave will
immediately know if someone tries to cheat. No CTF or CLA is required. To see how this works, let™s
try to cheat.

If someone tries to stuff the ballot, Alice will detect the attempt in step (3) when she receives more
votes than people. If Alice tries to stuff the ballot, Bob will notice in step (4).

More devious is to substitute one vote for another. Since the votes are encrypted with various public
keys, anyone can create as many valid votes as needed. The decryption protocol has two rounds:
round one consists of steps (3) through (7), and round two consists of steps (8) through (11). Vote
substitution is detected differently in the different rounds.

If someone substitutes one vote for another in round two, his actions are discovered immediately. At
every step the votes are signed and sent to all the voters. If one (or more) of the voters noticed that his
vote is no longer in the set of votes, he immediately stops the protocol. Because the votes are signed at
every step, and because everyone can backtrack through the second round of the protocol, it is easy to
detect who substituted the votes.

Substituting one vote for another during round one of the protocol is more subtle. Alice can™t do it in
step (3), because Bob, Carol, or Dave will detect it in step (5), (6), or (7). Bob could try in step (5). If he
replaces Carol™s or Dave™s vote (remember, he doesn™t know which vote corresponds to which voter),
Carol or Dave will notice in step (6) or (7). They wouldn™t know who tampered with their vote
(although it would have had to be someone who had already handled the votes), but they would know
that their vote was tampered with. If Bob is lucky and picks Alice™s vote to replace, she won™t notice
until the second round. Then, she will notice her vote missing in step (8). Still, she would not know
who tampered with her vote. In the first round, the votes are shuffled from one step to the other and
unsigned; it is impossible for anyone to backtrack through the protocol to determine who tampered
with the votes.


Another form of cheating is to try to figure out who voted for whom. Because of the scrambling in the
first round, it is impossible for someone to backtrack through the protocol and link votes with voters.
The removal of the random strings during the first round is also crucial to preserving anonymity. If
they are not removed, the scrambling of the votes could be reversed by re-encrypting the emerging
votes with the scrambler™s public key. As the protocol stands, the confidentiality of the votes is secure.

Even more strongly, because of the initial random string, R1, even identical votes are encrypted
differently at every step of the protocol. No one knows the outcome of the vote until step (11).

What are the problems with this protocol? First, the protocol has an enormous amount of
computation. The example described had only four voters and it was complicated. This would never
work in a real election, with tens of thousands of voters. Second, Dave learns the results of the election
before anyone else does. While he still can™t affect the outcome, this gives him some power that the
others do not have. On the other hand, this is also true with centralized voting schemes.

The third problem is that Alice can copy anyone else™s vote, even though she does not know what it is
beforehand. To see why this could be a problem, consider a three-person election between Alice, Bob,



Page 120 of 666
Applied Cryptography: Second Edition - Bruce Schneier



and Eve. Eve doesn™t care about the result of the election, but she wants to know how Alice voted. So
she copies Alice™s vote, and the result of the election is guaranteed to be equal to Alice™s vote.

Other Voting Schemes

Many complex secure election protocols have been proposed. They come in two basic flavors. There
are mixing protocols, like “Voting without a Central Tabulating Facility, ” where everyone™s vote gets
mixed up so that no one can associate a vote with a voter.

There are also divided protocols, where individual votes are divided up among different tabulating
facilities such that no single one of them can cheat the voters [360, 359, 118, 115]. These protocols only
protect the privacy of voters to the extent that different “parts” of the government (or whoever is
administering the voting) do not conspire against the voter. (This idea of breaking a central authority
into different parts, who are only trusted when together, comes from [316].)

One divided protocol is [1371]. The basic idea is that each voter breaks his vote into several shares.
For example, if the vote were “yes” or “no, ” a 1 could indicate “yes” and a 0 could indicate “no”; the
voter would then generate several numbers whose sum was either 0 or 1. These shares are sent to
tabulating facilities, one to each, and are also encrypted and posted. Each center tallies the shares it
receives (there are protocols to verify that the tally is correct) and the final vote is the sum of all the
tallies. There are also protocols to ensure that each voter™s shares add up to 0 or 1.

Another protocol, by David Chaum [322], ensures that voters who attempt to disrupt the election can
be traced. However, the election must then be restarted without the interfering voter; this approach is
not practical for large-scale elections.

Another, more complex, voting protocol that solves some of these problems can be found in [770, 771].
There is even a voting protocol that uses multiple-key ciphers [219]. Yet another voting protocol,
which claims to be practical for large-scale elections, is in [585]. And [347] allows voters to abstain.

Voting protocols work, but they make it easier to buy and sell votes. The incentives become
considerably stronger as the buyer can be sure that the seller votes as promised. Some protocols are
designed to be receipt-free, so that it is impossible for a voter to prove to someone else that he voted in
a certain way [117, 1170, 1372].

6.2 Secure Multiparty Computation

Secure multiparty computation is a protocol in which a group of people can get together and compute
any function of many variables in a special way. Each participant in the group provides one or more
variables. The result of the function is known to everyone in the group, but no one learns anything
about the inputs of any other members other than what is obvious from the output of the function.
Here are some examples:

Protocol #1

How can a group of people calculate their average salary without anyone learning the salary of
anyone else?

(1) Alice adds a secret random number to her salary, encrypts the result with Bob™s
public key, and sends it to Bob.
(2) Bob decrypts Alice™s result with his private key. He adds his salary to what he
received from Alice, encrypts the result with Carol™s public key, and sends it to Carol.




Page 121 of 666
Applied Cryptography: Second Edition - Bruce Schneier



(3) Carol decrypts Bob™s result with her private key. She adds her salary to what she
received from Bob, encrypts the result with Dave™s public key, and sends it to Dave.
(4) Dave decrypts Carol™s result with his private key. He adds his salary to what he
received from Carol, encrypts the result with Alice™s public key, and sends it to Alice.
(5) Alice decrypts Dave™s result with her private key. She subtracts the random number
from step (1) to recover the sum of everyone™s salaries.
(6) Alice divides the result by the number of people (four, in this case) and announces the
result.

This protocol assumes that everyone is honest; they may be curious, but they follow the protocol. If
any participant lies about his salary, the average will be wrong. A more serious problem is that Alice
can misrepresent the result to everyone. She can subtract any number she likes in step (5), and no one
would be the wiser. Alice could be prevented from doing this by requiring her to commit to her
random number using any of the bit-commitment schemes from Section 4.9, but when she revealed
her random number at the end of the protocol Bob could learn her salary.

Protocol #2

Alice and Bob are at a restaurant together, having an argument over who is older. They don™t,
however, want to tell the other their age. They could each whisper their age into the ear of a trusted
neutral party (the waiter, for example), who could compare the numbers in his head and announce
the result to both Alice and Bob.

The above protocol has two problems. One, your average waiter doesn™t have the computational
ability to handle situations more complex than determining which of two numbers is greater. And
two, if Alice and Bob were really concerned about the secrecy of their information, they would be
forced to drown the waiter in a bowl of vichyssoise, lest he tell the wine steward.

Public-key cryptography offers a far less violent solution. There is a protocol by which Alice, who
knows a value a, and Bob, who knows a value b, can together determine if a < b, so that Alice gets no
additional information about b and Bob gets no additional information about a. And, both Alice and
Bob are convinced of the validity of the computation. Since the cryptographic algorithm used is an
essential part of the protocol, details can be found in Section 23.14.


Of course, this protocol doesn™t protect against active cheaters. There™s nothing to stop Alice (or Bob,
for that matter) from lying about her age. If Bob were a computer program that blindly executed the
protocol, Alice could learn his age (is the age of a computer program the length of time since it was
written or the length of time since it started running?) by repeatedly executing the protocol. Alice
might give her age as 60. After learning that she is older, she could execute the protocol again with her
age as 30. After learning that Bob is older, she could execute the protocol again with her age as 45,
and so on, until Alice discovers Bob™s age to any degree of accuracy she wishes.

Assuming that the participants don™t actively cheat, it is easy to extend this protocol to multiple
participants. Any number of people can find out the order of their ages by a sequence of honest
applications of the protocol; and no participant can learn the age of another.

Protocol #3

Alice likes to do kinky things with teddy bears. Bob has erotic fantasies about marble tables. Both are
pretty embarrassed by their particular fetish, but would love to find a mate who shared in
their...um...lifestyle.




Page 122 of 666
Applied Cryptography: Second Edition - Bruce Schneier




Here at the Secure Multiparty Computation Dating Service, we™ve designed a protocol for people like
them. We™ve numbered an astonishing list of fetishes, from “aardvarks” to “zoot suits.” Discreetly
separated by a modem link, Alice and Bob can participate in a secure multiparty protocol. Together,
they can determine whether they share the same fetish. If they do, they might look forward to a
lifetime of bliss together. If they don™t, they can part company secure in the knowledge that their
particular fetish remains confidential. No one, not even the Secure Multiparty Computation Dating
Service, will ever know.

Here™s how it works:

(1) Using a one-way function, Alice hashes her fetish into a seven-digit string.
(2) Alice uses the seven-digit string as a telephone number, calls the number, and leaves a
message for Bob. If no one answers or the number is not in service, Alice applies a one-way
function to the telephone number until she finds someone who can play along with the protocol.
(3) Alice tells Bob how many times she had to apply the one-way hash function to her
fetish.
(4) Bob hashes his fetish the same number of times that Alice did. He also uses the seven-
digit string as a telephone number, and asks the person at the other end whether there were any
messages for him.

Note that Bob has a chosen-plaintext attack. He can hash common fetishes and call the resulting
telephone numbers, looking for messages for him. This protocol only really works if there are enough
possible plaintext messages for this to be impractical.

There™s also a mathematical protocol, one similar to Protocol #2. Alice knows a, Bob knows b, and
together they will determine whether a = b, such that Bob does not learn anything additional about a
and Alice does not learn anything additional about b. Details are in Section 23.14.

Protocol #4

This is another problem for secure multiparty computation [1373]: A council of seven meets regularly
to cast secret ballots on certain issues. (All right, they rule the world”don™t tell anyone I told you.)
All council members can vote yes or no. In addition, two parties have the option of casting “super
votes”: S-yes and S-no. They do not have to cast super votes; they can cast regular votes if they prefer.
If no one casts any super votes, then the majority of votes decides the issue. In the case of a single or
two equivalent super votes, all regular votes are ignored. In the case of two contradicting super votes,
the majority of regular votes decides. We want a protocol that securely performs this style of voting.

Two examples should illustrate the voting process. Assume there are five regular voters, N1 through
N5, and two super voters: S1 and S2. Here™s the vote on issue #1:

S1 S2 N1 N2 N3 N4 N5
S-yes no no no no yes yes

In this instance the only vote that matters is S1 ™s, and the result is “yes.”

Here is the vote on issue #2:

S1 S2 N1 N2 N3 N4 N5
S-yes S-no no no no yes yes




Page 123 of 666
Applied Cryptography: Second Edition - Bruce Schneier




Here the two super votes cancel and the majority of regular “no” votes decide the issue.

If it isn™t important to hide the knowledge of whether the super vote or the regular vote was the
deciding vote, this is an easy application of a secure voting protocol. Hiding that knowledge requires a
more complicated secure multiparty computation protocol.

This kind of voting could occur in real life. It could be part of a corporation™s organizational
structure, where certain people have more power than others, or it could be part of the United
Nations™s procedures, where certain nations have more power than others.

Multiparty Unconditionally Secure Protocols

This is just a simple case of a general theorem: Any function of n inputs can be computed by a set of n
players in a way that will let all learn the value of the function, but any set of less than n/2 players will
not get any additional information that does not follow from their own inputs and the value of the
output information. For details, see [136, 334, 1288, 621].

Secure Circuit Evaluation

Alice has her input, a. Bob has his input, b. Together they wish to compute some general function, f
(a,b), such that Alice learns nothing about Bob™s input and Bob learns nothing about Alice™s input.
The general problem of secure multiparty computation is also called secure circuit evaluation. Here,
Alice and Bob can create an arbitrary Boolean circuit. This circuit accepts inputs from Alice and
from Bob and produces an output. Secure circuit evaluation is a protocol that accomplishes three
things:

1. Alice can enter her input without Bob™s being able to learn it.
2. Bob can enter his input without Alice™s being able to learn it.
3. Both Alice and Bob can calculate the output, with both parties being sure the output is
correct and that neither party has tampered with it.

Details on secure circuit evaluation can be found in [831].


6.3 Anonymous Message Broadcast

You can™t go out to dinner with a bunch of cryptographers without raising a ruckus. In [321], David
Chaum introduced the Dining Cryptographers Problem:

Three cryptographers are sitting down to dinner at their favorite three-star restaurant.
Their waiter informs them that arrangements have been made with the ma®tre d˜hôtel for
the bill to be paid anonymously. One of the cryptographers might be paying for the
dinner, or it might have been the NSA. The three cryptographers respect each other™s
right to make an anonymous payment, but they wonder if the NSA is paying.

How do the cryptographers, named Alice, Bob, and Carol, determine if one of them is paying for
dinner, while at the same time preserving the anonymity of the payer?

Chaum goes on to solve the problem:

Each cryptographer flips an unbiased coin behind his menu, between him and the



Page 124 of 666
Applied Cryptography: Second Edition - Bruce Schneier



cryptographer to his right, so that only the two of them can see the outcome. Each
cryptographer then states aloud whether the two coins he can see”the one he flipped and
the one his left-hand neighbor flipped”fell on the same side or on different sides. If one of
the cryptographers is the payer, he states the opposite of what he sees. An odd number of
differences uttered at the table indicates that a cryptographer is paying; an even number
of differences indicates that NSA is paying (assuming that the dinner was paid for only
once). Yet, if a cryptographer is paying, neither of the other two learns anything from the
utterances about which cryptographer it is.

To see that this works, imagine Alice trying to figure out which other cryptographer paid for dinner
(assuming that neither she nor the NSA paid). If she sees two different coins, then either both of the
other cryptographers, Bob and Carol, said, “same” or both said, “different.” (Remember, an odd
number of cryptographers saying “different” indicates that one of them paid.) If both said, “different,
” then the payer is the cryptographer closest to the coin that is the same as the hidden coin (the one
that Bob and Carol flipped). If both said, “same, ” then the payer is the cryptographer closest to the
coin that is different from the hidden coin. However, if Alice sees two coins that are the same, then
either Bob said, “same” and Carol said, “different, ” or Bob said, “different” and Carol said, “same.”
If the hidden coin is the same as the two coins she sees, then the cryptographer who said, “different”
is the payer. If the hidden coin is different from the two coins she sees, then the cryptographer who
said, “same” is the payer. In all of these cases, Alice needs to know the result of the coin flipped
between Bob and Carol to determine which of them paid.

This protocol can be generalized to any number of cryptographers; they all sit in a ring and flip coins
among them. Even two cryptographers can perform the protocol. Of course, they know who paid, but
someone watching the protocol could tell only if one of the two paid or if the NSA paid; they could not
tell which cryptographer paid.

The applications of this protocol go far beyond sitting around the dinner table. This is an example of
unconditional sender and recipient untraceability. A group of users on a network can use this
protocol to send anonymous messages.

(1) The users arrange themselves into a circle.
(2) At regular intervals, adjacent pairs of users flip coins between them, using some fair
coin flip protocol secure from eavesdroppers.
(3) After every flip, each user announces either “same” or “different.”

If Alice wishes to broadcast a message, she simply starts inverting her statement in those rounds
corresponding to a 1 in the binary representation of her message. For example, if her message were
“1001, ” she would invert her statement, tell the truth, tell the truth, and then invert her statement.
Assuming the result of her flips were “different, ” “same, ” “same, ” “same, ” she would say “same, ”
“same, ” “same, ” “different.”

If Alice notices that the overall outcome of the protocol doesn™t match the message she is trying to
send, she knows that someone else is trying to send a message at the same time. She then stops sending
the message and waits some random number of rounds before trying again. The exact parameters
have to be worked out based on the amount of message traffic on this network, but the idea should be
clear.

To make things even more interesting, these messages can be encrypted in another user™s public keys.
Then, when everyone receives the message (a real implementation of this should add some kind of
standard message-beginning and message-ending strings), only the intended recipient can decrypt and
read it. No one else knows who sent it. No one else knows who could read it. Traffic analysis, which
traces and compiles patterns of people™s communications even though the messages themselves may



Page 125 of 666
Applied Cryptography: Second Edition - Bruce Schneier



be encrypted, is useless.

An alternative to flipping coins between adjacent parties would be for them to keep a common file of
random bits. Maybe they could keep them on a CD-ROM, or one member of the pair could generate a
pile of them and send them to the other party (encrypted, of course). Alternatively, they could agree
on a cryptographically secure pseudo-random-number generator between them, and they could each
generate the same string of pseudo-random bits for the protocol.

One problem with this protocol is that while a malicious participant cannot read any messages, he can
disrupt the system unobserved by lying in step (3). There is a modification to the previous protocol
that detects disruption [1578, 1242]; the problem is called “The Dining Cryptographers in the Disco.”

6.4 Digital Cash

Cash is a problem. It™s annoying to carry, it spreads germs, and people can steal it from you. Checks
and credit cards have reduced the amount of physical cash flowing through society, but the complete
elimination of cash is virtually impossible. It™ll never happen; drug dealers and politicians would
never stand for it. Checks and credit cards have an audit trail; you can™t hide to whom you gave
money.

On the other hand, checks and credit cards allow people to invade your privacy to a degree never
before imagined. You might never stand for the police following you your entire life, but the police
can watch your financial transactions. They can see where you buy your gas, where you buy your
food, who you call on the telephone”all without leaving their computer terminals. People need a way
to protect their anonymity in order to protect their privacy.


Happily, there is a complicated protocol that allows for authenticated but untraceable messages.
Lobbyist Alice can transfer digital cash to Congresscritter Bob so that newspaper reporter Eve does
not know Alice™s identity. Bob can then deposit that electronic money into his bank account, even
though the bank has no idea who Alice is. But if Alice tries to buy cocaine with the same piece of
digital cash she used to bribe Bob, she will be detected by the bank. And if Bob tries to deposit the
same piece of digital cash into two different accounts, he will be detected”but Alice will remain
anonymous. Sometimes this is called anonymous digital cash to differentiate it from digital money
with an audit trail, such as credit cards.

A great social need exists for this kind of thing. With the growing use of the Internet for commercial
transactions, there is more call for network-based privacy and anonymity in business. (There are good
reasons people are reluctant to send their credit card numbers over the Internet.) On the other hand,
banks and governments seem unwilling to give up the control that the current banking system™s audit
trail provides. They™ll have to, though. All it will take for digital cash to catch on is for some
trustworthy institution to be willing to convert the digits to real money.

Digital cash protocols are very complex. We™ll build up to one, a step at a time. For more formal
details, read [318, 339, 325, 335, 340]. Realize that this is just one digital cash protocol; there are
others.

Protocol #1

The first few protocols are physical analogies of cryptographic protocols. This first protocol is a
simplified physical protocol for anonymous money orders:




Page 126 of 666
Applied Cryptography: Second Edition - Bruce Schneier




(1) Alice prepares 100 anonymous money orders for $1000 each.
(2) Alice puts one each, and a piece of carbon paper, into 100 different envelopes. She
gives them all to the bank.
(3) The bank opens 99 envelopes and confirms that each is a money order for $1000.
(4) The bank signs the one remaining unopened envelope. The signature goes through the
carbon paper to the money order. The bank hands the unopened envelope back to Alice, and
deducts $1000 from her account.
(5) Alice opens the envelope and spends the money order with a merchant.
(6) The merchant checks for the bank™s signature to make sure the money order is
legitimate.
(7) The merchant takes the money order to the bank.
(8) The bank verifies its signature and credits $1000 to the merchant™s account.

This protocol works. The bank never sees the money order it signed, so when the merchant brings it
to the bank, the bank has no idea that it was Alice™s. The bank is convinced that it is valid, though,
because of the signature. The bank is confident that the unopened money order is for $1000 (and not
for $100, 000 or $100, 000, 000) because of the cut-and-choose protocol (see Section 5.1). It verifies the
other 99 envelopes, so Alice has only a 1 percent chance of cheating the bank. Of course, the bank will
make the penalty for cheating great enough so that it isn™t worth that chance. If the bank refuses to
sign the last check (if Alice is caught cheating) without penalizing Alice, she will continue to try until
she gets lucky. Prison terms are a better deterrent.

Protocol #2

The previous protocol prevents Alice from writing a money order for more than she claims to, but it
doesn™t prevent Alice from photocopying the money order and spending it twice. This is called the
double spending problem; to solve it, we need a complication:

(1) Alice prepares 100 anonymous money orders for $1000 each. On each money order
she includes a different random uniqueness string, one long enough to make the chance of
another person also using it negligible.
(2) Alice puts one each, and a piece of carbon paper, into 100 different envelopes. She
gives them all to the bank.
(3) The bank opens 99 envelopes and confirms that each is a money order for $1000.
(4) The bank signs the one remaining unopened envelope. The signature goes through the
carbon paper to the money order. The bank hands the unopened envelope back to Alice and
deducts $1000 from her account.
(5) Alice opens the envelope and spends the money order with a merchant.
(6) The merchant checks for the bank™s signature to make sure the money order is
legitimate.
(7) The merchant takes the money order to the bank.
(8) The bank verifies its signature and checks its database to make sure a money order
with the same uniqueness string has not been previously deposited. If it hasn™t, the bank credits
$1000 to the merchant™s account. The bank records the uniqueness string in a database.
(9) If it has been previously deposited, the bank doesn™t accept the money order.

Now, if Alice tries to spend a photocopy of the money order, or if the merchant tries to deposit a
photocopy of the money order, the bank will know about it.

Protocol #3

The previous protocol protects the bank from cheaters, but it doesn™t identify them. The bank doesn™t



Page 127 of 666
Applied Cryptography: Second Edition - Bruce Schneier



know if the person who bought the money order (the bank has no idea it™s Alice) tried to cheat the
merchant or if the merchant tried to cheat the bank. This protocol corrects that:

(1) Alice prepares 100 anonymous money orders for $1000 each. On each of the money
orders she includes a different random uniqueness string, one long enough to make the chance
of another person also using it negligible.
(2) Alice puts one each, and a piece of carbon paper, into 100 different envelopes. She
gives them all to the bank.
(3) The bank opens 99 envelopes and confirms that each is a money order for $1000 and
that all the random strings are different.
(4) The bank signs the one remaining unopened envelope. The signature goes through the
carbon paper to the money order. The bank hands the unopened envelope back to Alice and
deducts $1000 from her account.
(5) Alice opens the envelope and spends the money order with a merchant.
(6) The merchant checks for the bank™s signature to make sure the money order is
legitimate.
(7) The merchant asks Alice to write a random identity string on the money order.
(8) Alice complies.
(9) The merchant takes the money order to the bank.
(10) The bank verifies the signature and checks its database to make sure a money order
with the same uniqueness string has not been previously deposited. If it hasn™t, the bank credits
$1000 to the merchant™s account. The bank records the uniqueness string and the identity string
in a database.
(11) If the uniqueness string is in the database, the bank refuses to accept the money
order. Then, it compares the identity string on the money order with the one stored in the
database. If it is the same, the bank knows that the merchant photocopied the money order. If it
is different, the bank knows that the person who bought the money order photocopied it.


This protocol assumes that the merchant cannot change the identity string once Alice writes it on the
money order. The money order might have a series of little squares, which the merchant would
require Alice to fill in with either Xs or Os. The money order might be made out of paper that tears if
erased.

Since the interaction between the merchant and the bank takes place after Alice spends the money,
the merchant could be stuck with a bad money order. Practical implementations of this protocol
might require Alice to wait near the cash register during the merchant-bank interaction, much the
same way as credit-card purchases are handled today.

Alice could also frame the merchant. She could spend a copy of the money order a second time, giving
the same identity string in step (7). Unless the merchant keeps a database of money orders it already
received, he would be fooled. The next protocol eliminates that problem.

Protocol #4

If it turns out that the person who bought the money order tried to cheat the merchant, the bank
would want to know who that person was. To do that requires moving away from a physical analogy
and into the world of cryptography.

The technique of secret splitting can be used to hide Alice™s name in the digital money order.

(1) Alice prepares n anonymous money orders for a given amount.
Each of the money orders contains a different random uniqueness string, X, one long enough to



Page 128 of 666
Applied Cryptography: Second Edition - Bruce Schneier



make the chance of two being identical negligible.
On each money order, there are also n pairs of identity bit strings, I1, I2,..., In. (Yes, that™s n
different pairs on each check.) Each of these pairs is generated as follows: Alice creates a string
that gives her name, address, and any other piece of identifying information that the bank
wants to see. Then, she splits it into two pieces using the secret splitting protocol (see Section
3.6). Then, she commits to each piece using a bit-commitment protocol.
For example, I37 consists of two parts: I37L and I37R. Each part is a bit-committed packet that
Alice can be asked to open and whose proper opening can be instantly verified. Any pair (e.g.,
I37L and I37R, but not I37L and I38R), reveals Alice™s identity.
Each of the money orders looks like this:

Amount
Uniqueness String: X
Identity Strings: I1 = (I1L,I1R)
I2 = (I2L,I2R)
....
In = (InL, InR)


(2) Alice blinds all n money orders, using a blind signature protocol. She gives them all to
the bank.
(3) The bank asks Alice to unblind n - 1 of the money orders at random and confirms that
they are all well formed. The bank checks the amount, the uniqueness string, and asks Alice to
reveal all of the identity strings.
(4) If the bank is satisfied that Alice did not make any attempts to cheat, it signs the one
remaining blinded money order. The bank hands the blinded money order back to Alice and
deducts the amount from her account.
(5) Alice unblinds the money order and spends it with a merchant.
(6) The merchant verifies the bank™s signature to make sure the money order is
legitimate.
(7) The merchant asks Alice to randomly reveal either the left half or the right half of
each identity string on the money order. In effect, the merchant gives Alice a random n- bit
selector string, b1, b2,..., bn. Alice opens either the left or right half of Ii, depending on whether
bi is a 0 or a 1.
(8) Alice complies.
(9) The merchant takes the money order to the bank.
(10) The bank verifies the signature and checks its database to make sure a money order
with the same uniqueness string has not been previously deposited. If it hasn™t, the bank credits
the amount to the merchant™s account. The bank records the uniqueness string and all of the
identity information in a database.
(11) If the uniqueness string is in the database, the bank refuses to accept the money
order. Then, it compares the identity string on the money order with the one stored in the
database. If it is the same, the bank knows that the merchant copied the money order. If it is
different, the bank knows that the person who bought the money order photocopied it. Since the
second merchant who accepted the money order handed Alice a different selector string than
did the first merchant, the bank finds a bit position where one merchant had Alice open the left
half and the other merchant had Alice open the right half. The bank XORs the two halves
together to reveal Alice™s identity.

This is quite an amazing protocol, so let™s look at it from various angles.

Can Alice cheat? Her digital money order is nothing more than a string of bits, so she can copy it.
Spending it the first time won™t be a problem; she™ll just complete the protocol and everything will go



Page 129 of 666
Applied Cryptography: Second Edition - Bruce Schneier



smoothly. The merchant will give her a random n-bit selector string in step (7) and Alice will open
either the left half or right half of each Ii in step (8). In step (10), the bank will record all of this data,
as well as the money order™s uniqueness string.

When she tries to use the same digital money order a second time, the merchant (either the same
merchant or a different merchant) will give her a different random selector string in step (7). Alice
must comply in step (8); not doing so will immediately alert the merchant that something is suspicious.
Now, when the merchant brings the money order to the bank in step (10), the bank would
immediately notice that a money order with the same uniqueness string was already deposited. The
bank then compares the opened halves of the identity strings. The odds that the two random selector
strings are the same is 1 in 2n; it isn™t likely to happen before the next ice age. Now, the bank finds a
pair with one half opened the first time and the other half opened the second time. It XORs the two
halves together, and out pops Alice™s name. The bank knows who tried to spend the money order
twice.

Note that this protocol doesn™t keep Alice from trying to cheat; it detects her cheating with almost
certainty. Alice can™t prevent her identity from being revealed if she cheats. She can™t change either
the uniqueness string or any of the identity strings, because then the bank™s signature will no longer
be valid. The merchant will immediately notice that in step (6).

Alice could try to sneak a bad money order past the bank, one on which the identity strings don™t
reveal her name; or better yet, one whose identity strings reveal someone else™s name. The odds of her
getting this ruse past the bank in step (3) are 1 in n . These aren™t impossible odds, but if you make the
penalty severe enough, Alice won™t try it. Or, you could increase the number of redundant money
orders that Alice makes in step (1).

Can the merchant cheat? His chances are even worse. He can™t deposit the money order twice; the
bank will notice the repeated use of the selector string. He can™t fake blaming Alice; only she can open
any of the identity strings.


Even collusion between Alice and the merchant can™t cheat the bank. As long as the bank signs the
money order with the uniqueness string, the bank is assured of only having to make good on the
money order once.

What about the bank? Can it figure out that the money order it accepted from the merchant was the
one it signed for Alice? Alice is protected by the blind signature protocol in steps (2) through (5). The
bank cannot make the connection, even if it keeps complete records of every transaction. Even more
strongly, there is no way for the bank and the merchant to get together to figure out who Alice is.
Alice can walk in the store and, completely anonymously, make her purchase.

Eve can cheat. If she can eavesdrop on the communication between Alice and the merchant, and if she
can get to the bank before the merchant does, she can deposit the digital cash first. The bank will
accept it and, even worse, when the merchant tries to deposit the cash he will be identified as a
cheater. If Eve steals and spends Alice™s cash before Alice can, then Alice will be identified as a
cheater. There™s no way to prevent this; it is a direct result of the anonynimity of the cash. Both Alice
and the merchant have to protect their bits as they would paper money.

This protocol lies somewhere between an arbitrated protocol and a self-enforcing protocol. Both Alice
and the merchant trust the bank to make good on the money orders, but Alice does not have to trust
the bank with knowledge of her purchases.




Page 130 of 666
Applied Cryptography: Second Edition - Bruce Schneier




Digital Cash and the Perfect Crime

Digital cash has its dark side, too. Sometimes people don™t want so much privacy. Watch Alice commit
the perfect crime [1575]:

(1) Alice kidnaps a baby.
(2) Alice prepares 10, 000 anonymous money orders for $1000 (or as many as she wants
for whatever denomination she wants).
(3) Alice blinds all 10, 000 money orders, using a blind signature protocol. She sends them
to the authorities with the threat to kill the baby unless the following instructions are met:
(a) Have a bank sign all 10, 000 money orders.
(b) Publish the results in a newspaper.
(4) The authorities comply.
(5) Alice buys a newspaper, unblinds the money orders, and starts spending them. There
is no way for the authorities to trace the money orders to her.
(6) Alice frees the baby.

Note that this situation is much worse than any involving physical tokens”cash, for example.
Without physical contact, the police have less opportunity to apprehend the kidnapper.

In general, though, digital cash isn™t a good deal for criminals. The problem is that the anonymity
only works one way: The spender is anonymous, but the merchant is not. Moreover, the merchant
cannot hide the fact that he received money. Digital cash will make it easy for the government to
determine how much money you made, but impossible to determine what you spent it on.

Practical Digital Cash

A Dutch company, DigiCash, owns most of the digital cash patents and has implemented digital cash
protocols in working products. Anyone interested should contact DigiCash BV, Kruislaan 419, 1098
VA Amsterdam, Netherlands.

Other Digital Cash Protocols

There are other digital cash protocols; see [707, 1554, 734, 1633, 973]. Some of them involve some
pretty complicated mathematics. Generally, the various digital cash protocols can be divided into
various categories. On-line systems require the merchant to communicate with the bank at every sale,
much like today™s credit-card protocols. If there is a problem, the bank doesn™t accept the cash and
Alice cannot cheat.

Off-line systems, like Protocol #4, require no communication between the merchant and the bank
until after the transaction between the merchant and the customer. These systems do not prevent
Alice from cheating, but instead detect her cheating. Protocol #4 detected her cheating by making
Alice™s identity known if she tried to cheat. Alice knows that this will happen, so she doesn™t cheat.

Another way is to create a special smart card (see Section 24.13) containing a tamperproof chip called
an observer [332, 341, 387]. The observer chip keeps a mini database of all the pieces of digital cash
spent by that smart card. If Alice attempts to copy some digital cash and spend it twice, the imbedded
observer chip would detect the attempt and would not allow the transaction. Since the observer chip is
tamperproof, Alice cannot erase the mini-database without permanently damaging the smart card.
The cash can wend its way through the economy; when it is finally deposited, the bank can examine
the cash and determine who, if anyone, cheated.




Page 131 of 666
Applied Cryptography: Second Edition - Bruce Schneier




Digital cash protocols can also be divided along another line. Electronic coins have a fixed value;
people using this system will need several coins in different denominations. Electronic checks can be
used for any amount up to a maximum value and then returned for a refund of the unspent portion.

Two excellent and completely different off-line electronic coin protocols are [225, 226, 227] and [563,
564, 565]. A system called NetCash, with weaker anonymity properties, has also been proposed [1048,
1049]. Another new system is [289].

In [1211], Tatsuaki Okamoto and Kazuo Ohta list six properties of an ideal digital cash system:

1. Independence. The security of the digital cash is not dependent on any physical
location. The cash can be transferred through computer networks.
2. Security. The digital cash cannot be copied and reused.
3. Privacy (Untraceability). The privacy of the user is protected; no one can trace the
relationship between the user and his purchases.
4. Off-line Payment. When a user pays for a purchase with electronic cash, the protocol
between the user and the merchant is executed off-line. That is, the shop does not need to be
linked to a host to process the user™s payment.
5. Transferability. The digital cash can be transferred to other users.
6. Divisibility. A piece of digital cash in a given amount can be subdivided into smaller
pieces of cash in smaller amounts. (Of course, everything has to total up properly in the end.)

The protocols previously discussed satisfy properties 1, 2, 3, and 4, but not 5 and 6. Some on-line
digital cash systems satisfy all properties except 4 [318, 413, 1243]. The first off-line digital cash
system that satisfies properties 1, 2, 3, and 4, similar to the one just discussed, was proposed in [339].
Okamoto and Ohta proposed a system that satisfies properties 1 through 5 [1209]; they also proposed
a system that satisfies properties 1 through 6 as well, but the data requirement for a single purchase is
approximately 200 megabytes. Another off-line divisible coin system is described in [522].

The digital cash scheme proposed in [1211], by the same authors, satisfies properties 1 through 6,
without the enormous data requirements. The total data transfer for a payment is about 20 kilobytes,
and the protocol can be completed in several seconds. The authors consider this the first ideal
untraceable electronic cash system.

Anonymous Credit Cards

This protocol [988] uses several different banks to protect the identity of the customer. Each customer
has an account at two different banks. The first bank knows the person™s identity and is willing to
extend him credit. The second bank knows the customer only under a pseudonym (similar to a
numbered Swiss bank account).

The customer can withdraw funds from the second bank by proving that the account is his. However,
the bank does not know the person and is unwilling to extend him credit. The first bank knows the
customer and transfers funds to the second bank”without knowing the pseudonym. The customer
then spends these funds anonymously. At the end of the month, the second bank gives the first bank a
bill, which it trusts the bank to pay. The first bank passes the bill on to the customer, which it trusts
the customer to pay. When the customer pays, the first bank transfers additional funds to the second
bank. All transactions are handled through an intermediary, which acts sort of like an electronic
Federal Reserve: settling accounts among banks, logging messages, and creating an audit trail.

Exchanges between the customer, merchant, and various banks are outlined in [988]. Unless everyone
colludes against the customer, his anonymity is assured. However, this is not digital cash; it is easy for



Page 132 of 666
Applied Cryptography: Second Edition - Bruce Schneier



the bank to cheat. The protocol allows customers to keep the advantages of credit cards without
giving up their privacy.


Part II
Cryptographic Techniques
Chapter 7
Key Length
7.1 Symmetric Key Length

The security of a symmetric cryptosystem is a function of two things: the strength of the algorithm
and the length of the key. The former is more important, but the latter is easier to demonstrate.

Assume that the strength of the algorithm is perfect. This is extremely difficult to achieve in practice,
but easy enough for this example. By perfect, I mean that there is no better way to break the
cryptosystem other than trying every possible key in a brute-force attack.

To launch this attack, a cryptanalyst needs a small amount of ciphertext and the corresponding
plaintext; a brute-force attack is a known-plaintext attack. For a block cipher, the cryptanalyst would
need a block of ciphertext and corresponding plaintext: generally 64 bits. Getting this plaintext and
ciphertext is easier than you might imagine. A cryptanalyst might get a copy of a plaintext message by
some means and intercept the corresponding ciphertext. He may know something about the format of
the ciphertext: For example, it is a WordPerfect file, it has a standard electronic-mail message header,
it is a UNIX directory file, it is a TIFF image, or it is a standard record in a customer database. All of
these formats have some predefined bytes. The cryptanalyst doesn™t need much plaintext to launch
this attack.

Calculating the complexity of a brute-force attack is easy. If the key is 8 bits long, there are 28, or 256,
possible keys. Therefore, it will take 256 attempts to find the correct key, with a 50 percent chance of
finding the key after half of the attempts. If the key is 56 bits long, then there are 256 possible keys.
Assuming a supercomputer can try a million keys a second, it will take 2285 years to find the correct
key. If the key is 64 bits long, then it will take the same supercomputer about 585,000 years to find the
correct key among the 264 possible keys. If the key is 128 bits long, it will take 10 25 years. The
universe is only 1010 years old, so 1025 years is a long time. With a 2048-bit key, a million million-
attempts-per-second computers working in parallel will spend 10597 years finding the key. By that
time the universe will have long collapsed or expanded into nothingness.

Before you rush to invent a cryptosystem with an 8-kilobyte key, remember the other side to the
strength question: The algorithm must be so secure that there is no better way to break it than with a
brute-force attack. This is not as easy as it might seem. Cryptography is a subtle art. Cryptosystems
that look perfect are often extremely weak. Strong cryptosystems, with a couple of minor changes, can
become weak. The warning to the amateur cryptographer is to have a healthy, almost paranoid,
suspicion of any new algorithm. It is best to trust algorithms that professional cryptographers have
scrutinized for years without cracking them and to be suspicious of algorithm designers™ grandiose
claims of security.

Recall an important point from Section 1.1: The security of a cryptosystem should rest in the key, not
in the details of the algorithm. Assume that any cryptanalyst has access to all the details of your



Page 133 of 666
Applied Cryptography: Second Edition - Bruce Schneier



algorithm. Assume he has access to as much ciphertext as he wants and can mount an intensive
ciphertext-only attack. Assume that he can mount a plaintext attack with as much data as he needs.
Even assume that he can mount a chosen-plaintext attack. If your cryptosystem can remain secure,
even in the face of all that knowledge, then you™ve got something.

That warning aside, there is still plenty of room in cryptography to maneuver. In reality, this kind of
security isn™t really necessary in many situations. Most adversaries don™t have the knowledge and
computing resources of a major government, and even the ones who do probably aren™t that
interested in breaking your cryptosystem. If you™re plotting to overthrow a major government, stick
with the tried and true algorithms in the back of the book. The rest of you, have fun.

Time and Cost Estimates for Brute-Force Attack

Remember that a brute-force attack is typically a known-plaintext attack; it requires a small amount
of ciphertext and corresponding plaintext. If you assume that a brute-force attack is the most efficient
attack possible against an algorithm”a big assumption”then the key must be long enough to make
the attack infeasible. How long is that?

Two parameters determine the speed of a brute-force attack: the number of keys to be tested and the
speed of each test. Most symmetric algorithms accept any fixed-length bit pattern as the key. DES has
a 56-bit key; it has 256 possible keys. Some algorithms discussed in this book have a 64-bit key; these
have 264 possible keys. Others have a 128-bit key.

The speed at which each possible key can be tested is also a factor, but a less important one. For the
purposes of this analysis, I will assume that each different algorithm can be tested in the same amount
of time. The reality may be that one algorithm may be tested two, three, or even ten times faster than
another. But since we are looking for key lengths that are millions of times more difficult to crack
than would be feasible, small differences due to test speed are irrelevant.

Most of the debate in the cryptologic community about the efficiency of brute-force attacks has
centered on the DES algorithm. In 1977, Whitfield Diffie and Martin Hellman [497] postulated the
existence of a special-purpose DES-cracking machine. This machine consisted of a million chips, each
capable of testing a million keys per second. Such a machine could test 256 keys in 20 hours. If built to
attack an algorithm with a 64-bit key, it could test all 264 keys in 214 days.

A brute-force attack is tailor-made for parallel processors. Each processor can test a subset of the
keyspace. The processors do not have to communicate among themselves; the only communication
required at all is a single message signifying success. There are no shared memory requirements. It is
easy to design a machine with a million parallel processors, each working independent of the others.

More recently, Michael Wiener decided to design a brute-force cracking machine [1597,1598]. (He
designed the machine for DES, but the analysis holds for most any algorithm.) He designed
specialized chips, boards, and racks. He estimated prices. And he discovered that for $1 million,
someone could build a machine that could crack a 56-bit DES key in an average of 3.5 hours (results
guaranteed in 7 hours). And that the price/speed ratio is linear. Table 7.1 generalizes these numbers
to a variety of key lengths. Remember Moore™s Law: Computing power doubles approximately every
18 months. This means costs go down a factor of 10 every five years; what cost $1 million to build in
1995 will cost a mere $100,000 in the year 2000. Pipelined computers might do even better [724].

For 56-bit keys, these numbers are within the budgets of most large companies and many criminal
organizations. The military budgets of most industrialized nations can afford to break 64-bit keys.
Breaking an 80-bit key is still beyond the realm of possibility, but if current trends continue that will



Page 134 of 666
Applied Cryptography: Second Edition - Bruce Schneier



change in only 30 years.


Of course, it is ludicrous to estimate computing power 35 years in the future. Breakthroughs in some
science-fiction technology could make these numbers look like a joke. Conversely, physical limitations
unknown at the present time could make them unrealistically optimistic. In cryptography it is wise to
be pessimistic. Fielding an algorithm with an 80-bit key seems extremely short-sighted. Insist on at
least 112-bit keys.

Table 7.1
Average Time Estimates for a Hardware Brute-Force Attack in 1995
Length of Key in Bits
Cost 40 56 64 80 112 128

1014 years 1019 years
$100 K 2 seconds 35 hours 1 year 70,000 years
1013 years 1018 years
$1 M .2 seconds 3.5 hours 37 days 7000 years
1012 years 1017 years
$10 M .02 seconds 21 minutes 4 days 700 years
1011 years 1016 years
$100 M 2 milliseconds 2 minutes 9 hours 70 years
1010 years 1015 years
$1 G .2 milliseconds 13 seconds 1 hour 7 years
109 years 1014 years
$10 G .02 milliseconds 1 second 5.4 minutes 245 days
108 years 1013 years
$100 G 2 microseconds .1 second 32 seconds 24 days
107 years 1012 years
$1 T .2 microseconds .01 second 3 seconds 2.4 days
106 years 1011 years
$10 T .02 microseconds 1 millisecond .3 second 6 hours


If an attacker wants to break a key badly enough, all he has to do is spend money. Consequently, it
seems prudent to try to estimate the minimum “value” of a key: How much value can be trusted to a
single key before it makes economic sense to try to break? To give an extreme example, if an
encrypted message is worth $1.39, then it wouldn™t make much financial sense to set a $10-million
cracker to the task of recovering the key. On the other hand, if the plaintext message is worth $100
million, then decrypting that single message would justify the cost of building the cracker. Also, the
value of some messages decreases rapidly with time.

Software Crackers

Without special-purpose hardware and massively parallel machines, brute-force attacks are
significantly harder. A software attack is about a thousand times slower than a hardware attack.

The real threat of a software-based brute-force attack is not that it is certain, but that it is “free.” It
costs nothing to set up a microcomputer to test possible keys whenever it is idle. If it finds the correct
key”great. If it doesn™t, then nothing is lost. It costs nothing to set up an entire microcomputer
network to do that. A recent experiment with DES used the collective idle time of 40 workstations to
test 234 keys in a single day [603]. At this speed, it will take four million days to test all keys, but if
enough people try attacks like this, then someone somewhere will get lucky. As was said in [603]:

The crux of the software threat is sheer bad luck. Imagine a university computer network
of 512 workstations, networked together. On some campuses this would be a medium-
sized network. They could even be spread around the world, coordinating their activity



Page 135 of 666
Applied Cryptography: Second Edition - Bruce Schneier



through electronic mail. Assume each workstation is capable of running [the algorithm] at
a rate of 15,000 encryptions per second.... Allowing for the overhead of testing and
changing keys, this comes down to...8192 tests per second per machine. To exhaust [a 56-
bit] keyspace with this setup would take 545 years (assuming the network was dedicated
to the task twenty-four hours per day). Notice, however, that the same calculations give
our hypothetical student hackers one chance in 200,000 of cracking a key in one day. Over
a long weekend their odds increase to one chance in sixty-six thousand. The faster their
hardware, or the more machines involved, the better their chance becomes. These are not
good odds for earning a living from horse racing, but they™re not the stuff of good press
releases either. They are much better odds than the Government gives on its lotteries, for
instance. “One-in-a-million”? “Couldn™t happen again in a thousand years”? It is no
longer possible to say such things honestly. Is this an acceptable ongoing risk?

Using an algorithm with a 64-bit key instead of a 56-bit key makes this attack 256 times more
difficult. With a 40-bit key, the picture is far more bleak. A network of 400 computers, each capable
of performing 32,000 encryptions per second, can complete a brute-force attack against a 40-bit key in
a single day. (In 1992, the RC2 and RC4 algorithms were approved for export with a 40-bit key”see
Section 13.8.)

A 128-bit key makes a brute-force attack ridiculous even to contemplate. Industry experts estimate
that by 1996 there will be 200 million computers in use worldwide. This estimate includes everything
from giant Cray mainframes to subnotebooks. If every one of those computers worked together on
this brute-force attack, and each computer performed a million encryptions per second every second,
it would still take a million times the age of the universe to recover the key.

Neural Networks

Neural nets aren™t terribly useful for cryptanalysis, primarily because of the shape of the solution
space. Neural nets work best with problems that have a continuity of solutions, some better than
others. This allows a neural net to learn, proposing better and better solutions as it does. Breaking an
algorithm provides for very little in the way of learning opportunities: You either recover the key or
you don™t. (At least this is true if the algorithm is any good.) Neural nets work well in structured
environments where there is something to learn, but not in the high-entropy, seemingly random world
of cryptography.


Viruses

The greatest difficulty in getting millions of computers to work on a brute-force attack is convincing
millions of computer owners to participate. You could ask politely, but that™s time-consuming and
they might say no. You could try breaking into their machines, but that™s even more time-consuming
and you might get arrested. You could also use a computer virus to spread the cracking program
more efficiently over as many computers as possible.

This is a particularly insidious idea, first presented in [1593]. The attacker writes and lets loose a
computer virus. This virus doesn™t reformat the hard drive or delete files; it works on a brute-force
cryptanalysis problem whenever the computer is idle. Various studies have shown that
microcomputers are idle between 70 percent and 90 percent of the time, so the virus shouldn™t have
any trouble finding time to work on its task. If it is otherwise benign, it might even escape notice while
it does its work.

Eventually, one machine will stumble on the correct key. At this point there are two ways of
proceeding. First, the virus could spawn a different virus. It wouldn™t do anything but reproduce and



Page 136 of 666
Applied Cryptography: Second Edition - Bruce Schneier



delete any copies of the cracking virus it finds but would contain the information about the correct
key. This new virus would simply propagate through the computer world until it lands on the
computer of the person who wrote the original virus.

A second, sneakier approach would be for the virus to display this message on the screen:

There is a serious bug in this computer.
Please call 1-800-123-4567 and read the
following 64-bit number to the operator:

xxxx xxxx xxxx xxxx

There is a $100 reward for the first
person to report this bug.

How efficient is this attack? Assume the typical infected computer tries a thousand keys per second.
This rate is far less than the computer™s maximum potential, because we assume it will be doing other
things occasionally. Also assume that the typical virus infects 10 million machines. This virus can
break a 56-bit key in 83 days and a 64-bit key in 58 years. You might have to bribe the antiviral
software makers, but that™s your problem. Any increase in computer speeds or the virus infection rate
would, of course, make this attack more efficient.

The Chinese Lottery

The Chinese Lottery is an eclectic, but possible, suggestion for a massively parallel cryptanalysis
machine [1278]. Imagine that a brute-force, million-test-per-second cracking chip was built into every
radio and television sold. Each chip is programmed to test a different set of keys automatically upon
receiving a plaintext/ciphertext pair over the airwaves. Every time the Chinese government wants to
break a key, it broadcasts the data. All the radios and televisions in the country start chugging away.
Eventually, the correct key will appear on someone™s display, somewhere in the country. The Chinese
government pays a prize to that person; this makes sure that the result is reported promptly and
properly, and also helps the sale of radios and televisions with the cracking chips.

If every man, woman, and child in China owns a radio or television, then the correct key to a 56-bit
algorithm will appear in 61 seconds. If only 1 in 10 Chinese owns a radio or television”closer to
reality”the correct key will appear in 10 minutes. The correct key for a 64-bit algorithm will appear
in 4.3 hours”43 hours if only 1 in 10 owns a radio or television.

Some modifications are required to make this attack practical. First, it would be easier to have each
chip try random keys instead of a unique set of keys. This would make the attack about 39 percent
slower”not much in light of the numbers we™re working with. Also, the Chinese Communist party
would have to mandate that every person listen to or watch a certain show at a certain time, just to
make sure that all of the radios and televisions are operating when the plaintext/ciphertext pair is
broadcast. Finally, everyone would have to be instructed to call a Central-Party-Whatever-It™s-Called
if a key ever shows up on their screen, and then to read off the string of numbers appearing there.

Table 7.2 shows the effectiveness of the Chinese Lottery for different countries and different key
lengths. China would clearly be in the best position to launch such an attack if they have to outfit
every man, woman, and child with their own television or radio. The United States has fewer people
but a lot more equipment per capita. The state of Wyoming could break a 56-bit key all by itself in
less than a day.

Biotechnology




Page 137 of 666
Applied Cryptography: Second Edition - Bruce Schneier




If biochips are possible, then it would be foolish not to use them as a distributed brute-force
cryptanalysis tool. Consider a hypothetical animal, unfortunately called a “DESosaur” [1278]. It
consists of biological cells capable of testing possible keys. The plaintext/ciphertext pair is broadcast
to the cells via some optical channel (these cells are transparent, you see). Solutions are carried to the
DESosaur™s speech organ via special cells that travel through the animal™s circulatory system.

The typical dinosaur had about 1014 cells (excluding bacteria). If each of them can perform a million
encryptions per second (granted, this is a big if), breaking a 56-bit key would take seven ten-
thousandths of a second. Breaking a 64-bit key would take less than two tenths of a second. Breaking
a 128-bit key would still take 1011 years, though.

Table 7.2
Brute-Force Cracking Estimates for Chinese Lottery

Time to Break
# of
Country Population Televisions/Radios 56-bit 64-bit
China 1,190,431,000 257,000,000 280 seconds 20 hours
U.S. 260,714,000 739,000,000 97 seconds 6.9 hours
Iraq 19,890,000 4,730,000 4.2 hours 44 days
Israel 5,051,000 3,640,000 5.5 hours 58 days
Wyoming 470,000 1,330,000 15 hours 160 days
Winnemucca, NV 6,100 17,300 48 days 34 years
(All data is from the 1995 World Almanac and Book of Facts.)

Another biological approach is to use genetically engineered cryptanalytic algae that are capable of
performing brute-force attacks against cryptographic algorithms [1278]. These organisms would
make it possible to construct a distributed machine with more processors because they could cover a
larger area. The plaintext/ciphertext pair could be broadcast by satellite. If an organism found the
result, it could induce the nearby cells to change color to communicate the solution back to the
satellite.


Assume the typical algae cell is the size of a cube 10 microns on a side (this is probably a large
estimate), then 1015 of them can fill a cubic meter. Pump them into the ocean and cover 200 square
miles (518 square kilometers) of water to a meter deep (you figure out how to do it”I™m just the idea
man), and you™d have 1023 (over a hundred billion gallons) of them floating in the ocean. (For
comparison, the Exxon Valdez spilled 10 million gallons of oil.) If each of them can try a million keys
per second, they will recover the key for a 128-bit algorithm in just over 100 years. (The resulting
algae bloom is your problem.) Breakthroughs in algae processing speed, algae diameter, or even the
size puddle one could spread across the ocean, would reduce these numbers significantly.

Don™t even ask me about nanotechnology.

Thermodynamic Limitations

One of the consequences of the second law of thermodynamics is that a certain amount of energy is
necessary to represent information. To record a single bit by changing the state of a system requires



Page 138 of 666
Applied Cryptography: Second Edition - Bruce Schneier



an amount of energy no less than kT, where T is the absolute temperature of the system and k is the
Boltzman constant. (Stick with me; the physics lesson is almost over.)

Given that k =1.38*10-16 erg/°Kelvin, and that the ambient temperature of the universe is 3.2°K, an
ideal computer running at 3.2°K would consume 4.4*10-16 ergs every time it set or cleared a bit. To
run a computer any colder than the cosmic background radiation would require extra energy to run a
heat pump.

Now, the annual energy output of our sun is about 1.21*10 41 ergs. This is enough to power about
2.7*1056 single bit changes on our ideal computer; enough state changes to put a 187-bit counter
through all its values. If we built a Dyson sphere around the sun and captured all of its energy for 32
years, without any loss, we could power a computer to count up to 2192. Of course, it wouldn™t have
the energy left over to perform any useful calculations with this counter.

But that™s just one star, and a measly one at that. A typical supernova releases something like 1051
ergs. (About a hundred times as much energy would be released in the form of neutrinos, but let them
go for now.) If all of this energy could be channeled into a single orgy of computation, a 219-bit
counter could be cycled through all of its states.

These numbers have nothing to do with the technology of the devices; they are the maximums that
thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will
be infeasible until computers are built from something other than matter and occupy something other
than space.

7.2 Public-Key Key Length

One-way functions were discussed in Section 2.3. Multiplying two large primes is a one-way function;
it™s easy to multiply the numbers to get a product but hard to factor the product and recover the two
large primes (see Section 11.3). Public-key cryptography uses this idea to make a trap-door one-way
function. Actually, that™s a lie; factoring is conjectured to be a hard problem (see Section 11.4). As far
as anyone knows, it seems to be. Even if it is, no one can prove that hard problems are actually hard.
Most everyone assumes that factoring is hard, but it has never been mathematically proven one way
or the other.

This is worth dwelling on. It is easy to imagine that 50 years in the future we will all sit around,
reminiscing about the good old days when people used to think factoring was hard, cryptography was
based on factoring, and companies actually made money from this stuff. It is easy to imagine that
future developments in number theory will make factoring easier or that developments in complexity
theory will make factoring trivial. There™s no reason to believe this will happen”and most people
who know enough to have an opinion will tell you that it is unlikely”but there™s also no reason to
believe it won™t.

In any case, today™s dominant public-key encryption algorithms are based on the difficulty of
factoring large numbers that are the product of two large primes. (Other algorithms are based on
something called the Discrete Logarithm Problem, but for the moment assume the same discussion
applies.) These algorithms are also susceptible to a brute-force attack, but of a different type.
Breaking these algorithms does not involve trying every possible key; breaking these algorithms
involves trying to factor the large number (or taking discrete logarithms in a very large finite field”a
similar problem). If the number is too small, you have no security. If the number is large enough, you
have security against all the computing power in the world working from now until the sun goes
nova”given today™s understanding of the mathematics. Section 11.3 discusses factoring in more




Page 139 of 666
Applied Cryptography: Second Edition - Bruce Schneier



mathematical detail; here I will limit the discussion to how long it takes to factor numbers of various
lengths.

Factoring large numbers is hard. Unfortunately for algorithm designers, it is getting easier. Even
worse, it is getting easier faster than mathematicians expected. In 1976 Richard Guy wrote: “I shall be
surprised if anyone regularly factors numbers of size 1080 without special form during the present
century” [680]. In 1977 Ron Rivest said that factoring a 125-digit number would take 40 quadrillion
years [599]. In 1994 a 129-digit number was factored [66]. If there is any lesson in all this, it is that
making predictions is foolish.

Table 7.3 shows factoring records over the past dozen years. The fastest factoring algorithm during
the time was the quadratic sieve (see Section 11.3).

These numbers are pretty frightening. Today it is not uncommon to see 512-bit numbers used in
operational systems. Factoring them, and thereby completely compromising their security, is well in
the range of possibility: A weekend-long worm on the Internet could do it.

Computing power is generally measured in mips-years: a one-million-instruction-per-second (mips)
computer running for one year, or about 3*1013 instructions. By convention, a 1-mips machine is
equivalent to the DEC VAX 11/780. Hence, a mips-year is a VAX 11/780 running for a year, or the
equivalent. (A 100 MHz Pentium is about a 50 mips machine; a 1800-node Intel Paragon is about
50,000.)

The 1983 factorization of a 71-digit number required 0.1 mips-years; the 1994 factorization of a 129-
digit number required 5000. This dramatic increase in computing power resulted largely from the
introduction of distributed computing, using the idle time on a network of workstations. This trend
was started by Bob Silverman and fully developed by Arjen Lenstra and Mark Manasse. The 1983
factorization used 9.5 CPU hours on a single Cray X-MP; the 1994 factorization took 5000 mips-years
and used the idle time on 1600 computers around the world for about eight months. Modern factoring
methods lend themselves to this kind of distributed implementation.


The picture gets even worse. A new factoring algorithm has taken over from the quadratic sieve: the
general number field sieve. In 1989 mathematicians would have told you that the general number field
sieve would never be practical. In 1992 they would have told you that it was practical, but only faster
than the quadratic sieve for numbers greater than 130 to 150 digits or so. Today it is known to be
faster than the quadratic sieve for numbers well below 116 digits [472,635]. The general number field
sieve can factor a 512-bit number over 10 times faster than the quadratic sieve. The algorithm would
require less than a year to run on an 1800-node Intel Paragon. Table 7.4 gives the number of mips-
years required to factor numbers of different sizes, given current implementations of the general
number field sieve [1190].

Table 7.3
Factoring Using the Quadratic Sieve
# of decimal How many times harder to
Year digits factored factor a 512-bit number
1983 71 >20 million
1985 80 >2 million
1988 90 250,000
1989 100 30,000




Page 140 of 666
Applied Cryptography: Second Edition - Bruce Schneier



1993 120 500
1994 129 100

<<

. 6
( 29)



>>