Zero Knowledge Protocols
Introduction
The concept behind zero knowledge protocols is introduced below:
Andy: Hey Chris, do you know anything about zero knowledge protocols??
Chris: Yes, of course I do, but it’s a secret.
Andy: Ok, prove it to me, without revealing any of this “secret” information.
Chris: Er…..
Zero knowledge protocols are the acts of implementing identification, key exchanges, and cryptographic operations, whilst ensuring that secret information is not revealed during the protocols. The secret information is also concealed from any eavesdroppers. As the secret is not revealed at any stage, the verifier cannot pretend to be you to a third party.
The computational requirements, technicalities, and applications are discussed later on.
As with other computer security topics, various “people” are involved in illustrating concepts. In zero knowledge terms we have Peggy the prover, Victor the verifier, Eve the eavesdropper, and Maggie the malice.
Peggy wishes to prove to Victor that she knows some information without revealing the actual information to him. Victor asks questions of Peggy to find out if she knows the information or not – he learns nothing about the actual information itself, even when he tries to cheat the protocol. Eve listens to the conversation between Peggy and Victor, but does not learn anything about the secret information. Maggie is listening to the traffic of the protocol and is sending new messages or altering messages.
The secret information in a zero knowledge protocol is normally a password, a private key, a mathematical solution to a problem, or some credentials which are required to be concealed. An obvious point here is that in normal username and password systems, where the user enters their username and password, the password is revealed to the verifier – in zero knowledge the password is kept concealed.
Zero knowledge protocols use a cut and choose method, which allows victor to increase this certainty that Peggy knows the secret information, while at the same time the certainty that she does not know the information is she fails at any of the rounds of verification. A round of verification, or accreditation as it known in zero knowledge, allows Peggy to add certainty. For example, if each round had two options for Peggy to choose from to solve a problem set by Victor, then the chances of Peggy guessing the right information each round is 2 ^ n (where n is the number of rounds). It is up to Victor to decide how many rounds it will take before he is confident that Peggy is legitimate.
Key concepts:
- Victor learns nothing from the protocol
- this is where the protocol derives it’s name “zero knowledge”, as zero knowledge is transferred between the prover and the verifier.
- Peggy cannot cheat Victor
- it requires enough rounds to ensure that the likelihood of Peggy succeeding is minimal if she doesn’t know the secret information – the more rounds, the more likely she is to fail, and a single failure means that she is instantly deemed not legitimate.
- Victor cannot cheat Peggy
- Victor can’t derive the secret from the solutions Peggy gives. Peggy only gives one solution to a problem.
- Victor can’t pretend to be a third party
- to pretend to be a third party Victor would have to know the secret information, which he doesn’t.
Zero knowledge can be done in three main ways:
Interactively – Peggy and Victor go through the protocol and establish a higher degree of legitimacy in every round.
Parallel – a number of problems and solutions are passed between Peggy and Victor at a time – good for a slow response time connection.
Off line – Peggy creates problems, and uses a one-way hash function on the data and problems to select a random solution to send to Victor for each problem. These solution are sent to Victor attached to a message.
Real World Analogy
To illustrate more clearly the concept of zero knowledge protocols, we will use the textbook analogy of Ali Baba’s cave.
The cave seems to lead to two dead ends, but in fact it has a secret door between positions C and D. This door will only be opened by a secret password. Victor wants to verify that Peggy knows the secret of the cave, and Peggy wishes to prove this without revealing the magic words.
- Victor locates himself at point A, while Peggy enters the cave to position C or D (her choice).
- Victor proceeds to point B and calls to Peggy to come out specifically from either the left passage or the right passage.
- Peggy comes out from the correct passage, using the secret door between C and D if she is required to do so.
- This process is repeated as many times as it takes Victor to believe that Peggy knows the secret – bearing in mind that the chances of Peggy being “lucky” and choosing the right passage each time is 2 ^ n (where n is the number of times Victor asks her to come out). After 33 times, there is more chance of Victor being struck by lightning than him wrongly assuming that Peggy is legitimate.
Suppose Victor wants to prove to a third party that Peggy knows the secret, so he sets up a video camera at point B. This records Peggy going in one passage and coming out from the correct passage each time. If he showed the recording to a third party, Carol, then Carol could not trust that Peggy and Victor had not previously decided a sequence of left and right passage exits, or indeed that Victor had not edited the video to make it appear that Peggy had come out of the correct exit at each stage. Therefore it is impossible for Victor to convince Carol of the proof’s validity.
Technical Overview
While the
analogy of the cave demonstrates the principals of zero-knowledge protocols,
the protocols themselves are a little more complicated. Generally zero
knowledge protocols use the solutions to NP-complete problems as the secret
information. The following steps show the basic structure of some of the more
popular protocols. We assume that Peggy has the solution to a hard(NP-complete) problem.
- An arbitrator gives Peggy a
random number. Peggy then uses her solution and the number to transform
her problem into another, isomorphic, problem. She then solves this using
her existing solution.
- Peggy ‘commits’ to this new
solution.
- Peggy sends Victor the
isomorphic problem.
- Victor then sends Peggy a
random bit:
If the bit is 1, Peggy must show Victor that
her problem and the new problem are isomorphic.
If the bit is 0, Peggy must give Victor the
solution to the new problem that she committed to, and show that this solves
the isomorphic problem.
An example: Hamiltonian
Cycles
This
example was first given by Manuel Blum. Blum also proved that any mathematical
problem can be converted into a graph such that solving the problem is as
difficult as finding the Hamiltonian cycle of the graph. Here, Peggy knows the
Hamiltonian cycle of a Graph A and wants to prove it to Victor.
- Peggy permutes the graph into
one that is isomorphic to it B. She encrypts this into B’ where each line
in B is an encrypted 1 or 0.
- Peggy sends B’ to Victor, who
then sends back a 1 or 0.
If it is a 1, Peggy must prove that B’ is an
encryption of an isomorphic graph to A. She does this by sending Victor the
permutations she used, and the decrypted version of B’(B).
This means that she hasn’t revealed a Hamiltonian cycle for either A or B.
If it is a 0, Peggy must send Victor a
Hamiltonian cycle for B. She does this by decrypting only the lines in B’ that
make the Hamiltonian cycle. In this way she does not reveal that A and B are
topologically the same.
- The above is repeated as many
times as is needed for Victor to be satisfied.
For a
sufficiently large graph, it would be computationally far too difficult for
Peggy to work out a Hamiltonian path for B if she had not permuted it herself
from A. Because of this, Victor can be satisfied that Peggy really does know a
Hamiltonian cycle for A.
There are
two broad classes of zero knowledge protocols: proof of knowledge, and proof of
identity. In proof of knowledge protocols, the knowledge is often a discrete
logarithm of a large number, perhaps the product of two large primes.
Feige Fiat Shamir
Protocol
This is the
most well known proof of identity protocol. The following steps describe a
simple version of this protocol.
- A neutral arbitrator generates
a random modulus n, that is the product of two
large prime numbers. n is usually between 512 and
1024 bits. The arbitrator generates a public-private key pair for Peggy.
The public key is a number v where v-1 mod n exists and there
is a solution for x to x2 = v mod n. The private key is the
smallest value that a number s can take where s = √(1/v)
mod n.
- Peggy picks a random number r
that is smaller than n. She sends Victor x where x = r2 mod n.
Victor sends Peggy back a random bit.
- If the bit is 0, Peggy sends
back r. Victor then verifies that x = r2 mod n. This means that
Peggy knows √x.
- If the bit is 1, Peggy sends
back r*s mod n. Victor then verifies that
x= y2*v mod n. This means that Peggy knows √(x/v)
If someone
tries to impersonate Peggy, they will be found out with a 50% probability
because they can only prepare for one of the values of the bit that Victor
sends back. Victor cannot pretend to be Peggy to another verifier because the
bit that the new verifier sends to Victor only has a 50% chance of being the
same as the bit that Victor sent to Peggy.
Peggy must
not reuse a value of r as Victor can collect the answer to both values of the
random bit he sends, and thus work out the secret. If he did this enough times
then Victor could impersonate Peggy.
There are
two other similar protocols that are used frequently. The first is the Guillou-Quisqater protocol (Also known as the GQ protocol).
This uses roughly three times the processing power of the Feige-Fiat-Shamir
protocol but cuts down the size of each transaction. The second is the Schnorr protocol, that can also be
used for digital signatures if Victor is replaced by a one-way hash function.
Other forms of protocol
Instead of
performing all the different rounds in a zero knowledge protocol serially, they
can be done in parallel. Peggy simply commits to n different solutions to n
isomorphic problems, Victor sends back n random bits and then Peggy acts
accordingly. This type of protocol has slightly different properties because
Victor can compute his n ‘random’ bits as a hash function of the solutions that
Peggy commits to. So far no-one has proved that this is still zero-knowledge in
general, but it has been proved in specific cases.
Building on
the ideas of a parallel protocol, non-interactive zero knowledge protocols have
been devised. This means that Peggy is proving her knowledge or identity not
just to Victor but to anyone who wishes to know. Peggy commits to solutions of
n problems, but then hashes them through a one-way hash function. She uses the
first n bits of the output from the hash function as her random bits and then
publishes her results based on these. In order for Peggy to cheat, she must be
able to predict the output of the hash function.
Potential threats to Proof
of Identity Protocols
Chess Grand Master Problem
Imagine
that I want to prove that I have the ability to play chess at the level of a
grand master. I can invite two great chess players separately and place them in
separate rooms. I then play black against one and white against the other. All
that I need to do is take the move that the first player makes and play it
myself against the other player, and vice versa. In this way, each player
thinks they are playing me when in fact they are playing each other, while at
best I can be seen to beat one of them or at worst appear to be a very
competent player.
In a
zero-knowledge protocol this can be avoided by requiring transactions to be
completed in a short time frame.
The Mafia Fraud
This
requires the collaboration of two parties within the protocol. Peggy goes into
Victor’s pound shop and uses her credit card to buy some cheap items. However,
Victor works for the Mafia, as does Maggie. Victor relays Peggy’s details to
Maggie, who uses them to purchase expensive items at some other shop.
Applications
When
designing any security system the designer has to think about some key areas.
These include:
- security needs
- application areas
- and the system capabilities
It can
sometime be a trade-off between the security needs and the system capability.
For instance a system that allows users to view private medical information may
need a higher performance system to deal with the increased security, whereas a
remote garage door opener will have a lower security and therefore will need a
less powerful system.
Below is a
summary of three current cryptographic protocols.
|
Protocol |
Message |
Protocol |
Amount of |
Memory |
|
Zero-knowledge |
large |
many |
large |
large |
|
Public-key |
large |
one |
very large |
large |
|
Symmetric |
small |
one |
small |
small |
Smartcards
These are
often mentioned as good application areas for zero knowledge protocols, as the
protocol is fairly light to computer, and smartcards have limited resources
available.
Unfortunately
the physical security on smartcards is known to be vulnerable. The technology
to read protected memory is surprisingly good, and is often relatively easy and
cheap to do.
Some
standard techniques include:
- using non-standard programming
voltages
- misusing the manufacturers
undocumented testing procedures
- magnetic scanning of currents
throughout the working chip
- acid washing the chip away, a
layer at a time
Smartcards
then become a worrying security issue for systems based on symmetric
cryptography techniques, as the keys used for encryption and decryption will be
the same for all cards, and if one is broken then they all will be.
So why not public key techniques? As smartcards have limited computing power,
public keys become less favourable, due to the slight increase in computational
power needed to process the protocol.
Crypto ‘95
Another
area that zero knowledge has been used is in a program called Crypto ’95. The
program was designed by T. Okamoto and was developed to help solve the problem
of anonymous electronic cash with the ability to conduct payments of exact
amounts. It was the first offline efficient, anonymous e-cash scheme, being
released, as the name suggests, in 1995. The zero knowledge protocol was used
for the creation of the anonymous ‘e-coin’.
Side note –
the protocol was actually fairly inefficient, and was therefore used only at
set-up, to make the system as a whole more efficient. This then limited the
anonymity offered by allowing the linking of coins withdrawn, rather than a
more desirable anonymity by offering the linking of a subset of coins
withdrawn.
Zero Knowledge Password
Problem
The ZKPP is
a subset of the zero knowledge protocol, and deals with the issue of proving
that you know a password to a system, without revealing it to anyone else. The
problem extends into providing session keys for secret communication between
interested parties. The problem was solved in the early 90’s, independently by
two groups of researchers.
Other Areas
It has also been proposed that the protocol could be used in watermark verification. The problem at the moment; that in the process of establishing piracy of your product, you generally reveal the watermark, which then weakens the defense on other copies with the same, or similar watermark.
In more commercial areas, the zero knowledge protocol has been used in VideoCrypt, an analogue decoding card for satellite TV.
References
[1] Applied Cryptography; B. Schneier; John Wiley & Sons; 1995
[2] Zero Knowledge Protocols and Small Systems; Hannu A Aronsson,;Department
of Computer Science,
[3] Handbook of Applied Cryptography; A
Menezes, P. Oorschot &
[4] History of Zero Knowledge Password Authentication; http://www.integritysciences.com/history.html
This handout is available online at http://www.ferrrisonline.co.uk/computersecurity/handout.htm