Cryptographic Protocols II

Van Nguyen – HUT

Hanoi – 2010
Agenda

Cryptographic Key Exchange:

Protocols: basic Diffie-Hellman
concepts protocol

Zero-Knowledge
Blind Signatures
Protocols

Information Security by Van K Nguyen

Sep 2009 Hanoi University of Technology 2
 Whittfield Diffie and Martin Hellman are called the inventors of
Public Key Cryptography. Diffie-Hellman Key Exchange is the first
Public Key Algorithm published in 1976.

DIFFIE-HELLMAN KEY
EXCHANGE
Information Security by Van K Nguyen
Sep 2009 Hanoi University of Technology 3
What is Diffie-Hellman?

 A Public Key Algorithm

 Only for Key Exchange
 Does NOT Encrypt or Decrypt
 Based on Discrete Logarithms
 Widely used in Security Protocols and
Commercial Products
 Williamson of Britain’s CESG claims to have
discovered it several years prior to 1976

4
Discrete Logarithms

 What is a logarithm?
 log10100 = 2 because 102 = 100
 In general if logmb = a then ma = b
 Where m is called the base of the logarithm
 A discrete logarithm can be defined for
integers only
 In fact we can define discrete logarithms
mod p also where p is any prime number

5
Discrete Logarithm Problem

 The security of the Diffie-Hellman algorithm

depends on the difficulty of solving the
discrete logarithm problem (DLP) in the
multiplicative group of a finite field

6
Sets, Groups and Fields

 A set is any collection of objects called the

elements of the set
 Examples of sets: R, Z, Q
 If we can define an operation on the elements
of the set and certain rules are followed then
we get other mathematical structures called
groups and fields

7
Groups
 A group is a set G with a custom-defined binary
operation + such that:
 The group is closed under +, i.e., for a, b  G:
 a+bG
 The Associative Law holds i.e., for any a, b, c  G:
 a + (b + c) = (a + b) + c
 There exists an identity element 0, such that
 a+0=a
 For each a  G there exists an inverse element –a
such that
 a + (-a) = 0
 If for all a, b  G: a + b = b + a then the group is
called an Abelian or commutative group
 If a group G has a finite number of elements it is
called a finite group
8
More About Group Operations

 + does not necessarily mean normal

arithmetic addition
 + just indicates a binary operation which can
be custom defined
 The group operation could be denoted as •
 The group notation with + is called the
additive notation and the group notation with
• is called the multiplicative notation

9
Fields
 A field is a set F with two custom-defined binary
operations + and • such that:
 The Field is closed under + and •, i.e., for a, b  F:
 a + b  F and a • b  F
 The Associative Law holds i.e., for any a, b, c  F:
 a + (b + c) = (a + b) + c and a • (b • c) = (a • b) • c
 There exist identity elements 0 and 1, such that
 a + 0 = a and a • 1 = a
 For each a  F there exist inverse elements –a and a-
1
such that
 a + (-a) = 0 and a • a-1 = 1
 If a field F has a finite number of elements it is
called a finite field

10
 Examples of Groups
 Groups
 Set of real numbers R under +
 Set of real numbers R under *
 Set of integers Z under +
 Set of integers Z under *?
 Set of integers modulo a prime number p under +
 Set of integers modulo a prime number p under *
 Set of 3 X 3 matrices under + meaning matrix addition
 Set of 3 X 3 matrices under * meaning matrix
multiplication?
 Fields
 Set of real numbers R under + and *
 Set of integers Z under + and *
 Set of integers modulo a prime number p under + and *

11
 Generator of Group
 If for a  G, all members of the group can be
written in terms of a by applying the group
operation * on a a number of times then a is
called a generator of the group G
 Examples
 2 is a generator of Z*11
 2 and 3 are generator of Z*19
m 1 2 3 4 5 6 7 8 9 10

2m mod 11 2 4 8 5 10 9 7 3 6 1

m 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

2m mod 19 2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10 1
3m mod 19 3 9 8 5 15 7 2 6 18 16 10 11 14 4 12 17 13 1
12
Primitive Roots
 If an = x then a is called the n-th root of x
 For any prime number p, if we have a number a
such that powers of a mod p generate all the
numbers between 1 to p-1 then a is called a
Primitive Root of p.
 In terms of the Group terminology a is the generator
element of the multiplicative group of the finite field
formed by mod p
 Then for any integer b and a primitive root a of prime
number p we can find a unique exponent i such that
b = ai mod p
 The exponent i is referred to as the discrete
logarithm or index, of b for the base a.
13
14
15
Diffie-Hellman Algorithm

 Five Parts
1. Global Public Elements
2. User A Key Generation
3. User B Key Generation
4. Generation of Secret Key by User A
5. Generation of Secret Key by User B

16
Global Public Elements

 q Prime number
   < q and  is a primitive root
of q
 The global public elements are also
sometimes called the domain parameters

17
User A Key Generation

 Select private XA XA < q

 Calculate public YA YA =  XA mod q

18
User B Key Generation

 Select private XB XB < q

 Calculate public YB YB =  XB mod q

19
Generation of Secret Key by User A

 K = (YB)XA mod q

20
Generation of Secret Key by User B

 K = (YA)XB mod q

21
Diffie-Hellman Key Exchange

22
Diffie-Hellman Example

 q = 97
 =5
 XA = 36
 XB = 58
 YA = 536 = 50 mod 97
 YB = 558 = 44 mod 97
 K = (YB)XA mod q = 4436 mod 97 = 75 mod 97
 K = (YA)XB mod q = 5058 mod 97 = 75 mod 97
23
Why Diffie-Hellman is Secure?

 Opponent has q, , YA and YB

 To get XA or XB the opponent is forced to take
a discrete logarithm
 The security of the Diffie-Hellman Key
Exchange lies in the fact that, while it is
relatively easy to calculate exponentials
modulo a prime, it is very difficult to calculate
discrete logarithms. For large primes, the
latter task is considered infeasible.
24
Homework: Man-in-the-middle-
attack
 Find out yourself (maybe from the Internet)
how this attack can be implemented
successfully against Diffie-Hellman protocol
 Suggest a way to prevent against this attack

Information Security by Van K Nguyen

Sep 2009 Hanoi University of Technology 25
 ZERO-KNOWLEDGE
PROTOCOLS
Information Security by Van K Nguyen
Sep 2009 Hanoi University of Technology 26
The Cave of the Forty Thieves
The Cave of the Forty Thieves
Properties of Zero-Knowledge Proofs

 Completeness – A prover who knows the

secret information can prove it with
probability 1.
 Soundness – The probability that a prover
who does not know the secret information
can get away with it can be made arbitrarily
small.
Identification
 Alice is identified by some secret she alone is
known to possess - e.g. a password
 Problems
 The authenticator must be trusted
 If secret sniffed or given to untrusted party, can
impersonate
 Use zero knowledge!
Fiat-Shamir Identification

One time setup:

 Trusted center published modulus n=pq, but

keeps p and q secret

 Alice selects a secret prime s comprime to n,

computes v=s2 mod n, and registers v with

the trusted center as its public key
Fiat-Shamir Identification

Protocol messages:
A  B: x = r2 mod n
B  A: e from {0, 1}
A  B: y = rse mod n
Fiat-Shamir Identification

Protocol messages:
If e=0, then the
A  B: x = r2 mod n
response y=r is
independent of secret

B  A: e from {0, 1}
s

A  B: y = rse mod n
Fiat-Shamir Identification

Protocol messages:
A  B: x = r2 mod n
B  A: e from {0, 1}
A  B: y = rse mod n
If e=1, then information pairs (x, y) can
be simulated by choosing y randomly,
and setting x=y2 /v mod n
Bit Commitments and Zero-
Knowledge
 Bit commitments are used in zero-knowledge
proofs to encode the secret information.
 For example, zero-knowledge proofs based
on graph colorations exist. In this case, bit
commitment schemes are used to encode the
colors.
 Complex zero-knowledge proofs with large
numbers of intermediate steps that must be
verified also use bit commitment schemes.
Bit Commitments

 “Flipping a coin down a well”

 “Flipping a coin by telephone”
 A value of 0 or 1 is committed to by the
prover by encrypting it with a one-way
function, creating a “blob”. The verifier can
then “unwrap” this blob when it becomes
necessary by revealing the key.
Bit Commitment Properties

 Concealing – The verifier cannot determine

the value of the bit from the blob.
 Binding – The prover cannot open the blob as
both a zero and a one.
Bit Commitments: An Example
 Let n = pq, where p and q are prime. Let m be a
quadratic nonresidue modulo n. The values m and n are
public, and the values p and q are known only to Peggy.
 Peggy commits to the bit b by choosing a random x and
sending Vic the blob mbx2.
 When the time comes for Vic to check the value of the
bit, Peggy simply reveals the values b and x.
 Since no known polynomial-time algorithm exists for
solving the quadratic residues problem modulo a
composite n whose factors are unknown, hence this
scheme is computationally concealing.
 On the other hand, it is perfectly binding, since if it
wasn’t, m would have to be a quadratic residue, a
contradiction.
“fake” ZKP
 Consider this simple protocol
1. If the prover claims to be A, the verifier chooses a
random message M, and sends the ciphertext C =
PA(M) to the prover.
2. The prover decrypts C using SA and sends the result
M’ to the verifier.
3. The verifier accepts the identity of the prover if and
only if M’ = M.
 At first sight, it may seem OK:
 V already knows M
 But WRONG! What if the verifier is an adversary?
Information Security by Van K Nguyen
Sep 2009 Hanoi University of Technology 39
Fixed protocol
1. If P claims to be A, V chooses a random
message M, and sends C = PA (M) to P
2. P decrypts C using SA and sends V a
commitment to the result commitpk(r,M’)
3. V  P: M.
4. P checks if M = M’. If not he stops the protocol.
Otherwise he opens the commitment PV: r,M
5. V accepts the identity of the prover if and only if
M’ = M and the pair r,M’ correctly opens the
commitment
Information Security by Van K Nguyen
Sep 2009 Hanoi University of Technology 40
Another Example of ZKP
 Peggy the prover would like to show Vic the verifier that
an element b is a member of the subgroup of Zn*
generated by a, where a has order l. (i.e., does ak = b
for some k such that 0 ≤ k ≤ l?)
 Peggy chooses a random j, 0 ≤ j ≤ l – 1, and sends Vic
aj.
 Vic chooses a random i = 0 or 1, and sends it to Peggy.
 Peggy computes j + ik mod l, and sends it to Vic.
 Vic checks that aj + ik = ajaik = ajbi.
 They then repeat the above steps log2n times.
 If Vic’s final computation checks out in each round, he
accepts the proof.
Complexity Theory

 The last proof works because the problem of

solving discrete logarithms is NP-complete
(or is believed to be, at any rate).
 It has been shown that all problems in NP
have a zero-knowledge proof associated with
them.
Computational Assumptions

 A zero-knowledge proof assumes the prover

possesses unlimited computational power.
 It is more practical in some cases to assume
that the prover’s computational abilities are
bounded. In this case, we have a zero-
knowledge argument.
Proof vs. Argument

Zero-Knowledge Argument:
Proof:
 Unconditional completeness

 Computational
Unconditional soundness
soundness
 Perfect
Computational
zero-knowledge
zero-knowledge
 Computationally
Unconditionally binding
bindingblobs
blobs
 Unconditionally
Computationallyconcealing
concealingblobs
blobs
Applications

 Zero-knowledge proofs can be applied where

secret knowledge too sensitive to reveal
needs to be verified
 Key authentication
 PIN numbers
 Smart cards
Limitations
 A zero-knowledge proof is
only as good as the secret
it is trying to conceal
 Zero-knowledge proofs of
identities in particular are
problematic
 The Grandmaster Problem
 The Mafia Problem
 etc.