Hannu A. Aronsson

Department of Computer Science

Helsinki University of Technology

*haa@cs.hut.fi*

- 1. Introduction
- 2. Zero-knowledge Protocol Basics
- 2.1 The parties in a Zero-knowledge protocol
- 2.2 Zero-knowledge terminology
- 2.3 Features of Zero/knowledge Protocols
- 2.4 Modes of Operation
- 2.5 Computational Requirements
- 3. Zero-knowledge Protocol Theory
- 3.1 Cryptographic Strength
- 3.2 Contingency plans for Protocol Failure?
- 3.3 Which Problems can be Used in Zero-knowledge Protocols?
- 4. The Zero-knowledge Protocols Themselves
- 4.1 Proof of Knowledge
- 4.2 Proof of Identity or Identification
- 4.3 Feige-Fiat-Shamir Proof of Identity
- 4.4 Guillou-Quisquater Proof of Identity
- 4.5 Schnorr's Mutual Authentication
- 4.6 Key Exchange
- 4.7 Digital Signatures
- 4.8 Theoretical Protocols
- 4.9 Esoteric Protocols
- 5. Zero-knowledge Protocols in Practice
- 5.1 Real Computational and Memory Requirements
- 5.2 Useful applications
- 5.3 Breaking Smart Cards, A Reality Check
- 5.4 Embedded Applications Need (Some) Security Too
- 6. Minimalistic Zero-knowledge Protocol
- 6.1 Principles
- 6.2 Implementation
- 6.3 Security Analysis
- 6.4 Conclusions
- References

There is quite a lot written about zero-knowledge protocols in theory, but not so much practical down-to-earth material is available even though zero-knowledge techniques have been used in many applications.

Some of the practical aspects of zero-knowledge protocols and related issues are discussed, in the mind-set of minimalistic practical environments. The hardware technology used in these environments is described, and resulting real-world practical problems are related to zero-knowledge protocols.

A very lightweight zero knowledge protocol is outlined and its possible uses and cryptographic strengths and weaknesses are analyzed.

Although Zero-knowledge protocols look a bit unusual, most usual cryptographic problems can be solved by using them, as well as with public key cryptography. For some applications, like key exchange (for later normal cheap and fast symmetric encryption on the communications link) or proving mutual identities, zero-knowledge protocols can in many occasions be a very good and suitable solution.

- Peggy the Prover
- Peggy has some information that she wants to prove to Victor, but she
doesn't want to tell the secret itself to Victor.
- Victor the Verifier
- Victor asks Peggy a series of questions, trying to find out if Peggy
really knows the secret or not. Victor does not learn anything of the
secret itself, even if he would cheat or not adhere to the
protocol.
- Eve the Eavesdropper
- Eve is listening to the conversation between Peggy and Victor. A good
zero-knowledge protocol also makes sure that any third-party will not
learn a thing about the secret, and will not even be able to replay it
for anyone else later to convince them.
- Maggie the Malice
- Maggie is listening to the protocol traffic and maliciously sending
extra messages and modifying or destroying messages. The protocol must
be tamper-resistant to this kind of activity.

*Accreditation* means the building of confidence in each
iteration of the protocol. If in one step of a zero-knowledge
protocol, the chance of an impostor being able to provide the answer
is 1 in 2, the chances of her passing an entire conversation are
2^-(number of accreditation rounds).

Often the prover will offer a *problem* (i.e. particular numeric
values for a generic hard-to-solve mathematical problem,
e.g. factoring extremely large numbers, which are products of large
primes) to the verifier, which will ask for one of the 2 or more
possible solutions. If the prover knows the real solution to the hard
mathematical problem, she is able to provide any of the solutions
asked for. If she doesn't know the real solution, she can not provide
all of the possible solutions, and if the verifier asks for one of the
other solutions, she is unable to provide it, and will be found
out.

* Cut-and-choose* protocols work in the way, that one failure
means the failure of the whole protocol (i.e. that the prover is not
legitimate), but you can keep working on the protocol as long as you
want, if the prover is legitimate. After you reach the level of
confidence you need without being cut off, the protocol is
successful.

- The verifier can not learn anything from the protocol
- The Verifier does not learn anything from the protocol, that he could
not learn all by himself, without the prover. This is the central
zero-knowledge concept, i.e. No knowledge (zero amount of knowledge)
is transferred.

Without this feature, the protocol would be called a minimum-disclosure protocol, i.e. zero-knowledge protocols require that absolutely no information can be leaked in any case. - The prover can not cheat the verifier
- If Peggy doesn't know the secret, she can only succeed with a great
amount of good luck. After several rounds of the protocol, the odds of
an impostor passing as legitimate can be made as low as necessary.

The protocols are also cut and choose, i.e. the first time the prover fails, Victor knows Peggy is not legitimate. So, with each round of the protocol, the certainty gets better and better.

The protocols can be made to work even if the odds of a guess passing are high, you just need more rounds in the protocol. - The verifier can't cheat the prover
- Victor can't get any information out of the protocol, even if he does
not follow the protocol. The only thing Victor can do is to convince
himself that Peggy knows the secret. The Prover will always reveal
only one solution of many to any one problem, never all of them which
would allow finding out the secret itself.
- The verifier can not pretend to be the prover to any third party
- Because no information can leak from Peggy to Victor, Victor can't try
to masquerade as Peggy to any outside third party. With some of these
protocols, a man-in-the-middle attack is possible, though, meaning
that someone can relay the traffic from the true Peggy and try to
convince another Victor that he, the perpetrator, is Peggy.

Also, if the verifier records the conversation between him and the prover, that recording can't be used to convince any third party. It looks the same as a faked conversation (e.g. where the verifier and prover agreed beforehand which requests the verifier will choose).

*Interactive*, where Peggy and Victor interactively go through
the protocol, building up the certainty piece by piece.

*Parallel*, where Peggy creates a number of problems and Victor
asks for a number of solutions at a time. This can be used to bring
down the number of interactive messages with a slow-response-time
connection.

*Off line*, where Peggy creates a number of problems, and then uses
a cryptographically strong one-way hash function on the data and the
set of problems to play the role of Victor, to select a random
solution wanted for each problem. She then appends these solutions to
the message. This mode can be used for *digital signatures* .

A typical implementation might require 20 30 modular multiplications (with full-length bit strings) that can be optimized to 10 20 with precalculation. This is much faster than RSA.

The memory requirements seem to be about equal - to have very high security with Zero-knowledge protocols, you will need very long keys and numbers, so in memory terms, the requirements may not be very different.

Zero-Knowledge mechanisms let you split the protocol into an iterative process of lighter transactions, instead of one heavy transaction.

It seems possible to create a protocol with (many) very light iterative rounds, minimizing the computation and memory requirements of the protocol at any one time. More on this as we go along.

They work as follows:

- Peggy goes into a random branch of the cave, which Victor
doesn't know standing outside the cave

- Victor comes into the cave, and calls out a random branch of
the cave (left or right), where Peggy should come out

- If Peggy knows the secret password, she can come out the right
way every time, opening and passing the secret door with the
password if necessary. If Peggy doesn't know the password, she
has a 50% chance of initially going into the wrong branch, and
as she is not able to pass the secret door, Victor can call her
bluff.

This example also demonstrates another feature of zero-knowledge protocols: Now Victor is convinced that Peggy knows the secret password, but he cannot convince anyone else himself, as he doesn't know the secret!

Let's say that Victor would videotape the operation. But that recording can't be used to convince anyone else, as it looks just the same as a faked videotape, where a mischievous verifier and the prover agreed in advance which passage the prover should come out each time.

So, Victor can't even convince others, just himself, about Peggy knowing the secret. Absolutely no information flowed to Victor in the protocol.

Victor shows Peggy a scrambled Rubik's cube and asks for a proof of her skill to solve it. Peggy shows Victor a new, scrambled Rubik's cube. Victor can then choose to ask either

- for Peggy to show how to move from the new scrambled position to
the original scrambled position, or

- for Peggy to show how to move from the new scrambled position to the solved position.

Knowing both parts of the solution means that you can solve the cube, i.e. you know the secret. This is why Peggy must always present a differently scrambled cube in each round, because if Victor gets both answers to a single problem, he gains the knowledge of how to solve the cube in that case.

The textbook protocols work with relatively theoretical mathematics, and looking from a practical perspective it's not always so clear how they can be applied in real life applications.

Like other cryptographic protocols, zero-knowledge protocols base themselves on the usual crypto math, e.g. modulo calculation, discrete mathematics, extremely large numbers (hundreds or thousands of bits), etc.

- The problem of solving discrete logarithms for large numbers
(hundreds of bits)

- The problem of knowing if a number is a square mod
*n*or not, if you don't know the factors of n

- The problem of factoring large numbers that are products of two or more large (hundreds of bits) primes

Other, but only theoretically interesting, impractical problems are used in the theoretical protocols.

Surprisingly, I haven't seen a designed-in feature in any cryptosystem to handle the case of the cryptographic bottom of the system falling out, e.g. a planned course of action in the system for that case.

A lot of your data may need secure retention for many years. Some people say that NSA is 10 years ahead of others in cryptography and cryptanalysis; think about what everybody may be able to do in 10 years?

We don't know if these problems will be broken ever. To play safe with the ever-increasing computation power, you should at least choose keys that are long enough in your time perspective.

In this paper, though, we look at the practical application of quite short keys (minimizing memory requirements) and try to supplement the weak security of that approach with time limits and other practical techniques.

If one-way functions exist, any problem in NP has a zero-knowledge proof. The existence of one-way functions is the weakest assumption for strong encryption's existence [2].

The digital signature protocols rely on the quality and randomness of one-way hash functions.

The Ali Baba's Cave -example is an non-computer example of a zero-knowledge proof of knowledge. One problem that is often used in zero-knowledge proof-of-knowledge protocols is the knowledge of a discrete logarithm of some large number.

She could set-up a two-room game, inviting the top two players to play with her. She would place each one in a separate room, and then play exactly the move the other chess master did to the other and vice versa. Both masters would think they're playing against Alice, even if they're really playing against each other. She would at least appear to be a strong player if not winning. She doesn't even have to know the rules of the game, chess.

This man-in-the-middle attack can be used against some of the Zero-knowledge proof of identity protocols. One counterattack to the man-in-the-middle attack is imposing time limits for the replies, in the hope that there is not enough time for the man in the middle to relay the communications.

The so-called *Mafia fraud* does the same, intercepting
electronic payment messages to cheat a person proving his identity
when paying at a cheap restaurant into "proving" his identity
elsewhere to buy e.g. expensive jewels for the criminals.

There is also the potential problem of *multiple identities* , if
the system does not guarantee that each person has only one
identity. Alice could create several identities, and commit crimes
using some identity only once, which could never be traced back to
her.

Also, it might be possible to rent or *sell identities*,
i.e. Alice could sell her private key to someone else, who could then
masquerade as her. This works, because what is being actually proved
is that you know some piece of information (a bunch of bits), not
really who you are. This is also a more generic problem.

A simplified version of this protocol works as follows (we present the full protocol here to give a taste of what most of these protocols look like. The rest will be handled in a more overviewing fashion):

- Precalculation: An arbitrator generates a random modulus
*n*(512-1024 bits) which is the product of two large primes.The arbitrator generates a public and private key pair for Peggy, by choosing a number,*v*, which is a quadratic residue mod n (i.e.*x^2 = v mod n*has a solution, and*v^-1 mod n*exists). This number,*v*, is the public key. The private key is then the smallest*s*for which*s = sqrt(1/v) mod n*. - The identification protocol proceeds then as follows: Peggy
picks a random number
*r*where*r<n*. She then computes*x = r^2 mod n*and sends it to Victor.

- Victor sends Peggy a random bit,
*b.* - If the bit is 0, Peggy sends Victor
*r*. If the bit is 1, she sends*y = r * s mod n*. - If the bit was 0, Victor verifies that
*x = r^2 mod n,*proving that Peggy knows*sqrt(x).*If the bit was 1, he verifies that*x = y^2 * v mod n,*proving that Peggy knows*sqrt(x/v).*

Victor can't try to masquerade as Peggy to another verifier, as the bit Victor randomly sent to Peggy earlier has only a 50% chance of being the same as the second verifier will ask for.

In this protocol, Peggy should never reuse an *r.* If she did,
Victor could send her the other random bit, and collect a set of both
responses. Then, if he had enough of these, he could try to
impersonate Peggy to an outsider.

This protocol can be implemented in a parallel fashion, making the public and private keys be a set of quadratic residues mod n, etc. Then you can do as many rounds in parallel as you have keys in the set, speeding up the protocol (but with larger memory requirements) and needing fewer messages.

This protocol requires that the prover have the following: A bit
string of credentials *J* (card ID, validity, bank account
number, ...) used as the public key, and application-specific pieces
of public information, an exponent *v* and a modulus *n* ,
which is the product of two secret primes. The private key *B*
is calculated so that *JB^v = 1 (mod n).*
The protocol goes as follows:

- Peggy sends Victor her credentials
*J*. She has to prove that the*J*are her credentials: She picks a random number*r*, so that*1 < r < n 1*. She sends*T = r^v (mod n)*to Victor. - Victor picks a random number
*d,*so that*0 < d < v 1,*which he sends to Peggy. - Peggy computes
*D = rB^d (mod n)*and sends it to Victor. - Victor computes
*T'=D^v * J^d (mod n).*If*T = T' (mod n)*, then the authentication succeeds.

Peggy can create a number of problems, use the one-way hash function as a virtual Victor (which will randomly request one or the other solution to each problem, if the hash function is cryptographically good) and provide those answers.

As input to the one-way hash function, the message and the problems presented to Victor are used. This way, neither the message or the problems can be changed without making the signature void. The output of a good crypto-grade one-way hash function is completely random and unpredictable, so Peggy can't try to tweak the inputs to the hash until she gets suitable values permitting forgery.

The receivers can calculate the hash function themselves, check that the correct solutions were provided and that the solutions were valid. If so, then the signature can be considered valid.

With the Guillou-Quisquater signature scheme you can do multiple
signatures easier than having everyone sign the document separately:
The basic idea is that both signers compute their own *J*
and *B* values, which are used together to build the signature.

Using this to build a zero-knowledge protocol, the prover's secret is the Hamiltonian cycle of a graph.

The prover gives the verifier a permuted version of the original graph, and the verifier can ask for either

- prove that the graph is a permutation of the original graph, or

- show the Hamiltonian path for the permuted graph.

This protocol is theoretical because of the requirement for the graph to be extremely large, and the large memory and message size requirements it has.

Applying these protocols to the real world can be challenging, especially given the constraints of embedded computing. The promise of lighter calculations than public key protocols makes studying this very interesting and potentially very useful.

Let's look at these topics in more detail.

So the computational requirements are still pretty heavy for small-scale applications. The theoretical protocols are clearly too heavy for many minimalistic embedded solutions. Anyway, the promise of a lighter-weight protocol for many common needs, is worth looking into.

If the application permits using conventional symmetric algorithms (e.g. DES), those are still greatly lighter to calculate. There are other security problems in using symmetrical cryptography in e.g. smart cards, which are discussed in more detail below.

If you can only replace one big and very expensive but definitive public key transaction with a series of big and expensive rounds of zero-knowledge transactions, it might not be worth the trouble.

Here is a summary of the requirements of different cryptographic protocol families and their calculation and memory requirements:

Protocol Family | Message Size | Protocol Iterations | Amount of Calculation | Memory Requirements |
---|---|---|---|---|

Zero-knowledge | large | many | large | large |

Public-key | large | one | very large | large |

Symmetric | small | one | small | small |

There is no clear choice for all applications. Especially in small environments, the available computing power and memory is often a limiting factor in the selection of cryptographic techniques.

You would think that it would be good if your electronic cash card, your medical information card, intelligent key and lock systems, etc had real security to protect the information on them, the access to them, and your identity.

Many embedded and most smart card systems could use some degree of real security.

Because of the lack of computing power and good algorithms, most satellite reception decryption cards only use very simple cryptographic techniques, such as feedback shift registers etc. Most of these systems have been broken and pirate cards (and pirated pirate cards) are quite widely distributed.

Some digital cash experiments rely on shared secrets or keys stored on the cards (e.g. a symmetric algorithm such as DES is used), which requires that the manufacture of the cards is tightly controlled and the system is still vulnerable to a serious reverse engineering attack.

Even some of the so-called security CPU's used in smart card applications can be read (both code i.e. algorithm, and data i.e. keys), sometimes with

- simple techniques (using nonstandard programming voltages to
clear code protection fuses or misusing the manufacturers
undocumented internal testing features), or with

- specialized, but still relatively cheap techniques (magnetic
scanning of currents throughout the working chip) or eventually
with

- expensive, but comprehensive techniques (acid washing the chip away layer at a time).

If a single smart card technology is used *widely* enough, the
incentive of breaking it can become very high. For example, if a
European Union -wide electronic cash card would be introduced, the
incentives for criminals and organized crime to break it would be very
large indeed.

Even with the so-called secure smart card technologies, you can't expect total physical security for your code (algorithm) or any data (keys) on the card.

This is especially bad news for systems based on symmetric cryptography techniques, as the single key used both for encryption and decryption could be recovered from any of the many cards in circulation. This is why smart card applications need public key or zero-knowledge protocols and solutions.

This is also a problem for the Clipper chip proposal from NSA. If the Clipper would become mandatory and other crypto would be banned (as planned), the incentive for breaking it would also become extremely high, and somebody would surely pop the Clipper chip system open (however much it would cost) and find out the supposedly secret algorithm and any embedded keys for analysis.

Most of the time these applications are also extremely cost limited: They use the cheapest, $1-$2 price scale embedded controllers, which don't have much memory or computing power.

We are not aiming to build a totally 100% secure system here. We should keep in mind the trade-off between cryptography, resources and the required level of security. In many embedded solutions it may be enough to provide a system safe enough, for the particular application, and given the attack scenarios.

For applications where you need total security (e.g., digital cash), the protocols you need are quite heavy and would require high-end embedded controllers or smart cards, and very complex public key or zero-knowledge protocols, which are outside the scope of this paper.

The computing power of these RISC pipelined controllers is around a maximum of 10 20 MIPS (instructions working on 8-bit data).

The working memory resources of chips in this family are from 24 to 256 bytes of RAM. Some models come with 64 bytes of EEPROM, which could be suitable for key and secret storage. The program memory capacity ranges from 512 instructions to 4096 instructions.

A typical widely-used model, the PIC 16C84, has a program memory of 1024 instructions, 36 bytes or scratchpad RAM, 64 bytes of EEPROM (nonvolatile) memory and a maximum performance of about 3 MIPS. This is our example target environment.

It's noteworthy to say here that the 16C84 chip has been found vulnerable. By using non-standard programming voltages, you can trick the chip into a mode that will allow you to clear the memory protection bit without clearing out all of the memory simultaneously (as would happen if it worked to its specification). As the 16C84 is a popular chip used in many applications, the vulnerability is rather serious, from the security viewpoint, as well as from the code copyright viewpoint.

Many other manufacturers also have comparable embedded controllers. These controllers sell a lot in the world. They are the kind of thing you can find in your computer mouse or microwave oven and other such little devices all around us.

In a cryptosystem, the level of security required is a balancing act between apparent threats. We only need to make the breaking of the system not worth the perpetrators time and resources. For "boring" embedded applications, this security level is not necessarily very high.

We shall analyze a protocol where

- use a very light round zero-knowledge -based protocol (so that
not much computing power is required at any given time), where
we

- require each round to complete within a very short time limit
(so that an outsider even with superior computing power doesn't
have time to break the algorithm by brute force), and

- make sure that a quick dictionary-based attack (i.e. precalculated tables) attack is not feasible for an outsider with superior memory resources.

If the iteration round is light enough, we can possibly iterate many times to establish the credentials for the connection. If the embedded controllers used in the system are pretty fast, the resources required for an outsider to break the protocol by brute force would become be high enough to prevent attacks.

The approach of limiting allowable response time is also used in some existing protocols to avoid man-in-the-middle attacks (e.g. the Chess grand master problem or the Mafia fraud).

A 64-bit system should be strong enough to thwart most brute force attacks (e.g. DES keys are 56 bits). A 32-bit system is already suspectible to attack, as current desktop computers can have gigabytes of memory space to use. 64-bit key-space should be pretty good.

Every phase of the protocol must complete within a given time limit, just enough for the legitimate secret holder to calculate the reply, and transmit it. It is hoped that this time restriction will make man-in-the-middle and brute force attacks unfeasible.

A superior computing power intruder might realistically have 3 to 5 orders of magnitude more computing power than the legitimate system. Even if the brute-force calculation is fast, you will need to be able to break the problem within the given time limit, always. Making sure a brute force attack is unfeasible, it should be enough to make a brute-force attack take 10 or so orders of magnitude more computing power, i.e. a few bits worth of magnitude.

Victor must provide some random input for Peggy's problem, so that an impostor is not able to precalculate some set of problems and both solutions using his superior computing and memory resources.

As Peggy's problem is changed by the number given to her by Victor, she can't pre-build a set of problems and solutions to them.

The time limits set in the protocol should make this attack unfeasible.

This attack is possible on other protocols too, but because this protocol uses a relatively weak single round, the possibility of this attack succeeding might make it a real danger to the security of this protocol.

One economical solution might be to look at the applications of this protocol: Non-critical embedded systems, each with their own secrets. It may not be economical for someone to break the system, if the possible benefits are very small.

Breaking a 64-bit secret is still relatively formidable effort by brute force, so in the environment where this protocol would be used, it should be enough.

Note that some of the numbers used in zero-knowledge need to have some special features (e.g., being prime), the brute force attack on this system may be much easier than the brute force attack on a conventional symmetric cryptosystem with 64-bits of real random key.

For example, if you know that breaking the secrets would take several days on a very powerful computer (you could even try it yourself in advance on your own system), you could, anyway, use these protocols in a one-day event for access control smart cards, with almost total confidence. When the adversary breaks the code, the particular secret(s) is (are) not in use any more.

By balancing the security needs, applications and system capabilities it may still be possible to build systems with relatively good security, instead of no security as in most current systems.

It is evident from this study, that implementing real security does have quite large computational and memory requirements. So, in applications where good security is necessary, high-powered embedded controllers should be selected, so that they can work with the full-strength cryptographic protocols.

Another possible solution would be to use symmetric-key cryptography protocols (which have relatively small computational and memory requirements), with designed-in features for the eventual loss of key secrecy through reverse engineering.

Joining theoretically good cryptographic techniques and protocols with real world limitations of small systems is sometimes extremely hard. Most studies are based on the availability of enough computing power and memory.

When you try to apply these techniques in very small systems, you will have to make compromises. Knowing the strength of your protocols, keys and the hardware and being able to balance and apply the system to your actual needs will be even more important than in traditional cryptographic applications.

**[1]**- David Chaum.
*Security without identification*: Card computers to make big brother obsolete **[2]**- Ivan Bjerre Damgård.
*Zero-knowledge Protocols*, Århus University and CRYPTOMATHIC A/S. **[3]**- Bruce Schneier.
*Applied Cryptography*, Wiley & Sons, 1994, ISBN 0-471-59756-2, 1994. **[4]**- Quisquater & Guillou.
*Teaching Zero-knowledge protocols for your children* **[5]**- DigiCash, Inc. Zero Knowledge Interactive Proofs
**[6]**- DigiCash publications. a list of publications by D. Chaum
**[7]**- Tatu Ylönen. crypto page
**[8]**- Has DSS Been Hacked?
**[9]**- UCL Crypto Group.
- UCL Crypto Group home page
**[10]**- RSA Data Security, Inc. FAQ About Today's Cryptography
**[11]**- Gilles Brassard. A Bibliography of Quantum Cryptography
**[12]**- Erik Warren Selberg. How to Stop a Cheater: Secret Sharing with Dishonest Participation
**[13]**- Hadmut Danisch. The Exponential Security System TESS: An Identity-Based Cryptographic Protocol for Authenticated Key-Exchange.
**[14]**- Assorted Cypherpunks Topics
**[15]**- IBM Research. Digital Signatures Secure in the Strongest Sense Known
**[16]**- Security Papers
**[17]**- Rumor(tm) Database - cypherpunks