ńňđ. 6 |

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 |