1
Security Protocols
曹天杰
Tianjie Cao
tjcao@cumt.edu.cn
College of Computer Science and
Technology,China University of Mining and Technology,
Xuzhou,China
中国矿业大学计算机科学与技术学院
2003.6.9
2
secret splitting
Problem,
? You are the CEO of Coca-Cola,You are
responsible for bringing a refreshing taste to
zillions of people all over the world,but want to
keep the recipe secret from Pepsi’s industrial
spies,
? You could tell your most trusted employees
– they could defect to the opposition
– they could fall to rubber hose cryptanalysis
? How can we split a secret among two parties
where each piece by itself is useless?
3
secret splitting
Algorithm,
Assume Trent wishes to protect the message m,
Trent generates a random bit string r,the same
length m,
Trent computes m ? r = s
Trent gives Alice r
Trent gives Bob s
? Each of the pieces is called a shadow,
? To reconstruct m,Alice and Bob XOR their
shadows together,
? If r is truly random,the system is perfectly
secure (OTP),
? To extend the scheme to n people,generate n
random bit strings e.g,m ? r ? s ? t = u
4
secret sharing
Problem,
? You are responsible for a small third world
country’s nuclear weapons program,
? You want to ensure that no single lunatic can
launch a missile,
? You want to ensure that no two lunatics can
collude to launch a missile,
? You want at least three of five officers to be
lunatics before a missile can be launched,
? We call this a (3,5) threshold scheme,
5
Threshold Scheme
? N users and a threshold d
? Any group of d or more users can jointly
obtain the secret
? Any group of d-1 or less users can not
jointly obtain any information about the
secret
? Assume we have a dealer here who has the
secret
6
(N,1) - (N,N) scheme
? (N,1),Make N copies of the secret and give
each user a copy
? (N,N),Let s be the secret,let M be a large
number
Let s1,s2,…,sN be N random numbers such
that s1+ s2+…+ sN = s mod M
Assign si to the ith user
7
Adi Shamir (N,d)-Scheme
? Pick a prime p
? and a random polynomial
f (x) = ad-1xd-1 + ad-2xd-2 +…+ a0 mod p
a0 = f (0) = s
? User i receive si = f (i) mod p
? Any d users can interpolate to obtain f and
hence s
? Any d-1 users can not obtain any information
about s
8
Vandermonde System
? Vandermonde System is full rank and hence
has a unique solution
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
d
i
i
i
d
d
dd
d
d
s
s
s
a
a
a
ii
ii
ii
??????
2
1
1
1
0
1
1
22
1
11
.,,1
.,,1
.,,1
9
bit commitment
Problem,
? Alice wants to sell Bob information regarding
police informants within his Mafia empire,
? Alice doesn’t trust Bob enough to tell him the
rats without getting paid first (they might
suddenly disappear),
? Bob thinks that the deal is a police setup,and
won’t give her the money until she commits to
names,
10
bit commitment
Commitment,
? Bob → Alice,random r
? Alice → Bob,{r|m}k
Revelation,
? Alice → Bob,k
? Bob decrypts the message and verifies r
Discussion,
? The random value r is used for freshness and to stop Alice
from finding two messages where {m}k1 == {m’}k2
– i.e,forcing Alice to commit
? Bob does not know k until revelation so cannot brute
force the message space
11
bit commitment with hash functions
Commitment,
? Alice,generates random r1,r2
? Alice → Bob,r1 and x = h(r1,r2,m) [x is called a blob]
Revelation,
? Alice → Bob,r1,r2,m
? Bob hashes (r1,r2,m) and compares it to x
Discussion,
? Bob does not have to send any messages
– Alice sends a message to commit and a message to reveal
? Alice cannot find r3 such that h(r1,r3,m) == h(r1,r2,m)
? The value r2 is kept secret so Bob can’t brute force the
message space,
12
fair coin flipping
Problem,
? Alice and Bob are arguing on the Internet over
who will be white in a game of online chess,
? They agree to flip a coin to resolve the situation,
? Alice doesn’t trust Bob to flip the coin,
? Bob doesn’t trust Alice to flip the coin,
? How can we flip a coin fairly?
13
fair coin flipping
Solution,
? Alice commits to a random bit b using a bit
commitment scheme and sends the blob y
= f(b) to Bob,
? Bob tries to guess the bit,
? If Bob guesses correctly then Bob wins the
toss,
? If Bob guesses incorrectly then Alice wins
the toss,
14
Coin Flipping Using One-Way Functions
? (1) Alice chooses a random number,x,She
computes y = f(x),where f(x) is the one-way
function,
? (2) Alice sends y to Bob,
? (3) Bob guesses whether x is even or odd
and sends his guess to Alice,
? (4) If Bob’s guess is correct,the result of the
coin flip is heads,If Bob’s guess is incorrect,
the result of the coin flip is tails,Alice
announces the result of the coin flip and
sends x to Bob,
? (5) Bob confirms that y = f(x),
15
fair coin flipping using public key crypto
? Requires that the algorithm commutes
– e.g,RSA with identical moduli
DA(EB(EA(m))) = EB(m)
Algorithm,
? Alice and Bob generate public/private key pairs,
? Alice generates two random numbers rT,rH
? Alice → Bob,m1 = EA(“heads”,rH),m2 = EA(“tails”,rT)
? Bob selects one message x at random,
? Bob → Alice,EB(EA(x))
? Alice → Bob,DA(EB(EA(x))) = EB(x)
? Bob → Alice,x
16
fair coin flipping using public key crypto
? Alice verifies that x is one of the two random strings,
? Alice and Bob reveal to each other their keypairs to ensure
that neither cheated,
Discussion,
? The algorithm is self-enforcing,Either party can detect
cheating by the other without a TTP,
? Note,Bob learns of the result of the coin flip before Alice,
Although he can’t change it,he may delay the result on
purpose to take advantage of the situation
– Otherwise known as Bob flipping the coin into a well,
? Coin flipping has use in session key generation as neither
party can influence the result of each flip (i.e,bit)
– e.g,in Diffie-Hellman one party selects an exponent after the first,
17
mental poker
Problem,
? Alice and Bob want to play poker over email,
? Alice doesn’t trust Bob,
? Bob doesn’t trust Alice,
? How can Alice and Bob be deal hands fairly?
18
mental poker
Solution,
? Alice and Bob use a commutative public key cryptosystem
DA(EB(EA(m))) = EB(m)
? Alice encrypts 52 messages m1 = (“Ace of Spades”,r1) …
using her public key,
? Alice sends the blobs to Bob,
? Bob picks 5 of these at random,encrypts with his public key
and sends them back to Alice,
? Alice decrypts the messages with her public key and sends
back to Bob,
? Bob decrypts the messages to determine his hand,
? At the end of the game,Alice and Bob reveal their key pairs
to ensure neither cheats,
19
attacks against poker schemes
? Since some cryptographic algorithms are not truly
random processes,they tend to leak small amounts
of information,
? In RSA,for example,if the binary representation of
the card is a quadratic residue,then the encryption
of the card is also a quadratic residue,
? Remember that x is a quadratic residue (QR) if y2 ≡ x
(mod p) has a solution,
? This could be used by a malicious dealer to,mark”
some cards (e.g,the Aces),
20
oblivious transfer
Problem,
? Bob is trying to factor a 500-bit number,n,
? Alice wants to sell Bob a 100-bit factor for $100
(at a reasonable $1/bit)
? Bob only has $50 and offers to buy half the bits
- but only if Alice proves that the number is a
factor of n,
? How can the deal be done given Alice cannot
convince her number is a factor of n without
telling it to Bob?
21
oblivious transfer
Algorithm,
? Alice generates two public/private key pairs EA1,DA1 and
EA2,DA2
? Alice → Bob,EA1,EA2
? Bob generates a symmetric cypher key,k
? Bob picks one of Alice’s public keys randomly and encrypts k
? Bob → Alice,{k}EX
? Alice decrypts the key twice DA1{k}EX DA2{k}EX resulting in k
and garbage DY{k}EX (Alice does not know which is the real
key),
? Alice sends Bob two messages,one real and one fake {“here
are the bits”} {“sucker!!!”},each encrypted with one of these
keys,
? Bob decrypts both with k,One message will make sense to
him,
? Bob now has one of the messages,Alice has no idea which one,
? After the protocol is complete,Alice must reveal both private
keys to so Bob knows she didn’t cheat,
22
oblivious transfer
Discussion,
? Alice still needs to convince Bob that the message is a
factor of n,She does that using a zero-knowledge proof
(remember,a way of Alice telling Bob that she knows x
without revealing any information about x),
? Obvious transfer is a way Alice can send a bit to Bob in
such a way that Bob receives the bit with probability 0.5
and Alice does not know if it is received or not,(i.e.,I
have one secret and you get it with probability 0.5”),
? This can be extended to,I have two secrets and you get
one”,I have n secrets and you get one”,etc,
? Obvious transfer is not used alone,It is used as a building
block in other protocols,
23
oblivious transfer- Michael Rabin
In this protocol,Alice has a 50 percent chance
of sending Bob two primes,p,and q,
? (1) Alice sends Bob the product of the two primes,
n = pq,
? (2) Bob chooses a random x less than n,such that
x is relatively prime to n,He sends Alice,
? a = x2 mod n
? (3) Alice,knowing p and q,computes the four
roots of a,x,n - x,y,and n - y,She chooses one of
these roots at random and sends it to Bob,
? (4) If Bob receives y or n - y,he can compute the
greatest common divisor of x + y and n,which is
either p or q,Then,of course,n/p = q,If Bob
receives x or n - x,he can’t compute anything,
24
subliminal channels
Problem,
? Alice and Bob have been arrested for conspiracy
to factor large numbers by the government,
? Alice has been sent to a woman’s jail,Bob to a
men’s correctional facility,
? The warden,Walter,is willing to let them
communicate on the condition that messages
are not encrypted,
? How can Alice and Bob communicate secretly
given might Walter attempt to deceive both of
them by planting false messages?
25
subliminal channels
? Alice and Bob set up a subliminal channel in their message
(otherwise known as a covert communications channel),
? On the simplest level,Alice and Bob could use
steganography aka stego (information hiding),Note stego
is not crypto (although you can combine the two),
? Examples of this channel might be,
– A ‘0’ is sent if the number of words in a sentence is even,
– A ‘1’ is sent if the number of words in a sentence is odd,
? One might send an image in an email where the low order
bit of each pixel is actually a message,
– the low order bit is below any human perceptual change in
quality
26
subliminal channels ? Loki
– Daemon9,Alhambra (phrack/the guild)
– Bidirectional covert UNIX shell client using the data field in ICMP
type 0 (Echo Reply) and type 8 (Echo Request) packets,
? Daemonshell-UDP
– ICMP Echo Reply only (more stealthy)
? ICMP Backdoor
– Reusable tunnel library
– Messages fragmented to look more like ping packets (multiples of 64
bytes)
? Rwwwshell
– Backdoor emits requests as HTTP Response packets
– Output from commands return from the slave as cgi script HTTP
GETs
? B0CK
– IGMP multicast messages used as transport
? AckCmd
– TCP ACK packets for request (port 80),TCP RESET packets for
response (high port)
27
zero knowledge proofs
Problem,
? Peggy wants to prove to Victor she knows some piece of
information without revealing it,
? Proofs take the form of interactive protocols
– Victor asks Peggy a question
– If Peggy knows the answer she will always get it correct
– Otherwise there is a small chance she can guess correctly
– Repeat asking questions until Victor is convinced
? Already seen ZKPs have applications in authentication
by challenge-response (e.g,proof of identity)
28
ali baba’s cave
? Quisquater & Guillou [1989]
? Illustration of ZKPs
? Peggy claims she knows the password to
open trapdoor but doesn’t want to tell it to
Victor
Algorithm,
– Victor stands at outside cave
– Peggy goes into random branch of cave
– Victor enters cave and calls for Peggy to
either come from one branch (left or
right)
– If Peggy knows password she can come
out correct side every time
– Repeat enough times until Victor is sure
Peggy knows it
L R
Victor
Peggy
29
zero-knowledge proofs
? Cut and choose protocol
– Alice cuts something in half
– Bob picks which half he wants
– Alice takes the remaining half
? Properties of ZKPs
– Victor cannot learn anything from the protocol
– Peggy cannot cheat Victor
– Victor cannot cheat Peggy
– Victor cannot pretend to be Peggy to any third party
30
attacks on zkps of identity
? The Mafia fraud
– Alice is eating at Fat Tony’s Mafia Diner
– Fast Eddie is shopping at Bob’s jewelery store
– Alice starts the ZKP identity protocol with Fat Tony
– Fat Tony radios Fast Eddie who starts a ZKP identity protocol with
Bob
– Fat Tony and Fast Eddie as a communications channel
– Alice ends up being ripped off by the mafia
? The Terrorist fraud
– Carlos the terrorist wants to enter the country
– Bob is scheming to help Carlos enter the country
– Carlos is challenged at the border by Alice with a ZKP of identity
– Carlos radios Bob and gets him to enter the ZKP identity protocol
– Alice thinks Carlos is Bob and lets him in
31
Graph Isomorphism
? Assume that Peggy knows the isomorphism between the two graphs,G1
and G2,The following protocol will convince Victor of Peggy’s knowledge,
? (1) Peggy randomly permutes G1 to produce another graph,H,that is
isomorphic to G1,Because Peggy knows the isomorphism between H
and G1,she also knows the isomorphism between H and G2,
? (2) Peggy sends H to Victor,
? (3) Victor asks Peggy either to,
? (a) prove that H and G1 are isomorphic,or
? (b) prove that H and G2 are isomorphic,
? (4) Peggy complies,She either,
? (a) proves that H and G1 are isomorphic,without proving that H
and G2 are isomorphic,or
? (b) proves that H and G2 are isomorphic,without proving that H
and G1 are isomorphic,
? (5) Peggy and Victor repeat steps (1) through (4) n times,
32
Feige-Fiat-Shamir
? Before issuing any private keys,the arbitrator
chooses a random modulus,n,which is the product
of two large primes,
? To generate Peggy’s public and private keys,a
trusted arbitrator chooses a number,v,where v is a
quadratic residue mod n,In other words,choose v
such that x2 ≡ v (mod n) has a solution and v-1 mod n
exists,This v is Peggy’s public key,Then calculate
the smallest s for which s ≡ sqrt (v-1) (mod n),This is
Peggy’s private key,
33
Feige-Fiat-Shamir
? (1) Peggy picks a random r,where r is less then n,She
then computes x = r2 mod n,and sends x to Victor,
? (2) Victor sends Peggy a random bit,b,
? (3) If b = 0,then Peggy sends Victor r,If b = 1,then Peggy
sends Victor y = r * s mod n,
? (4) If b = 0,Victor verifies that x = r2 mod n,proving that
Peggy knows sqrt (x),If b = 1,Victor verifies that x = y2 * v
mod n,proving that Peggy knows sqrt (v-1),
? This is a single round of the protocol,
? Peggy and Victor repeat this protocol t times,until
Victor is convinced that Peggy knows s,
34
dining cryptographer’s problem
Problem,
Three cryptographers are sitting down to dinner at their
favourite three-star restaurant,Their waiter informs them
that arrangements have been made with the maitre d'hotel
for the bill to be paid anonymously,One of the
cryptographers might be paying for the dinner,or it might
have been NSA,The three cryptographers respect each
other's right to make an anonymous payment,but they
wonder if NSA is actually paying,
- David Chaum (1988),
35
dining cryptographer’s problem
Algorithm,
? Each cryptographer flips an unbiased coin (in secret)
? Each shows the result to the person on the right
? Each cryptographer states whether the two coins he can
see are the same or different
? If one of the cryptographers is the payer he says the
opposite of what he sees
? An odd number of differences means that a
cryptographer has paid,otherwise the NSA paid
? The algorithm is extensible to any number of diners
Security Protocols
曹天杰
Tianjie Cao
tjcao@cumt.edu.cn
College of Computer Science and
Technology,China University of Mining and Technology,
Xuzhou,China
中国矿业大学计算机科学与技术学院
2003.6.9
2
secret splitting
Problem,
? You are the CEO of Coca-Cola,You are
responsible for bringing a refreshing taste to
zillions of people all over the world,but want to
keep the recipe secret from Pepsi’s industrial
spies,
? You could tell your most trusted employees
– they could defect to the opposition
– they could fall to rubber hose cryptanalysis
? How can we split a secret among two parties
where each piece by itself is useless?
3
secret splitting
Algorithm,
Assume Trent wishes to protect the message m,
Trent generates a random bit string r,the same
length m,
Trent computes m ? r = s
Trent gives Alice r
Trent gives Bob s
? Each of the pieces is called a shadow,
? To reconstruct m,Alice and Bob XOR their
shadows together,
? If r is truly random,the system is perfectly
secure (OTP),
? To extend the scheme to n people,generate n
random bit strings e.g,m ? r ? s ? t = u
4
secret sharing
Problem,
? You are responsible for a small third world
country’s nuclear weapons program,
? You want to ensure that no single lunatic can
launch a missile,
? You want to ensure that no two lunatics can
collude to launch a missile,
? You want at least three of five officers to be
lunatics before a missile can be launched,
? We call this a (3,5) threshold scheme,
5
Threshold Scheme
? N users and a threshold d
? Any group of d or more users can jointly
obtain the secret
? Any group of d-1 or less users can not
jointly obtain any information about the
secret
? Assume we have a dealer here who has the
secret
6
(N,1) - (N,N) scheme
? (N,1),Make N copies of the secret and give
each user a copy
? (N,N),Let s be the secret,let M be a large
number
Let s1,s2,…,sN be N random numbers such
that s1+ s2+…+ sN = s mod M
Assign si to the ith user
7
Adi Shamir (N,d)-Scheme
? Pick a prime p
? and a random polynomial
f (x) = ad-1xd-1 + ad-2xd-2 +…+ a0 mod p
a0 = f (0) = s
? User i receive si = f (i) mod p
? Any d users can interpolate to obtain f and
hence s
? Any d-1 users can not obtain any information
about s
8
Vandermonde System
? Vandermonde System is full rank and hence
has a unique solution
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
d
i
i
i
d
d
dd
d
d
s
s
s
a
a
a
ii
ii
ii
??????
2
1
1
1
0
1
1
22
1
11
.,,1
.,,1
.,,1
9
bit commitment
Problem,
? Alice wants to sell Bob information regarding
police informants within his Mafia empire,
? Alice doesn’t trust Bob enough to tell him the
rats without getting paid first (they might
suddenly disappear),
? Bob thinks that the deal is a police setup,and
won’t give her the money until she commits to
names,
10
bit commitment
Commitment,
? Bob → Alice,random r
? Alice → Bob,{r|m}k
Revelation,
? Alice → Bob,k
? Bob decrypts the message and verifies r
Discussion,
? The random value r is used for freshness and to stop Alice
from finding two messages where {m}k1 == {m’}k2
– i.e,forcing Alice to commit
? Bob does not know k until revelation so cannot brute
force the message space
11
bit commitment with hash functions
Commitment,
? Alice,generates random r1,r2
? Alice → Bob,r1 and x = h(r1,r2,m) [x is called a blob]
Revelation,
? Alice → Bob,r1,r2,m
? Bob hashes (r1,r2,m) and compares it to x
Discussion,
? Bob does not have to send any messages
– Alice sends a message to commit and a message to reveal
? Alice cannot find r3 such that h(r1,r3,m) == h(r1,r2,m)
? The value r2 is kept secret so Bob can’t brute force the
message space,
12
fair coin flipping
Problem,
? Alice and Bob are arguing on the Internet over
who will be white in a game of online chess,
? They agree to flip a coin to resolve the situation,
? Alice doesn’t trust Bob to flip the coin,
? Bob doesn’t trust Alice to flip the coin,
? How can we flip a coin fairly?
13
fair coin flipping
Solution,
? Alice commits to a random bit b using a bit
commitment scheme and sends the blob y
= f(b) to Bob,
? Bob tries to guess the bit,
? If Bob guesses correctly then Bob wins the
toss,
? If Bob guesses incorrectly then Alice wins
the toss,
14
Coin Flipping Using One-Way Functions
? (1) Alice chooses a random number,x,She
computes y = f(x),where f(x) is the one-way
function,
? (2) Alice sends y to Bob,
? (3) Bob guesses whether x is even or odd
and sends his guess to Alice,
? (4) If Bob’s guess is correct,the result of the
coin flip is heads,If Bob’s guess is incorrect,
the result of the coin flip is tails,Alice
announces the result of the coin flip and
sends x to Bob,
? (5) Bob confirms that y = f(x),
15
fair coin flipping using public key crypto
? Requires that the algorithm commutes
– e.g,RSA with identical moduli
DA(EB(EA(m))) = EB(m)
Algorithm,
? Alice and Bob generate public/private key pairs,
? Alice generates two random numbers rT,rH
? Alice → Bob,m1 = EA(“heads”,rH),m2 = EA(“tails”,rT)
? Bob selects one message x at random,
? Bob → Alice,EB(EA(x))
? Alice → Bob,DA(EB(EA(x))) = EB(x)
? Bob → Alice,x
16
fair coin flipping using public key crypto
? Alice verifies that x is one of the two random strings,
? Alice and Bob reveal to each other their keypairs to ensure
that neither cheated,
Discussion,
? The algorithm is self-enforcing,Either party can detect
cheating by the other without a TTP,
? Note,Bob learns of the result of the coin flip before Alice,
Although he can’t change it,he may delay the result on
purpose to take advantage of the situation
– Otherwise known as Bob flipping the coin into a well,
? Coin flipping has use in session key generation as neither
party can influence the result of each flip (i.e,bit)
– e.g,in Diffie-Hellman one party selects an exponent after the first,
17
mental poker
Problem,
? Alice and Bob want to play poker over email,
? Alice doesn’t trust Bob,
? Bob doesn’t trust Alice,
? How can Alice and Bob be deal hands fairly?
18
mental poker
Solution,
? Alice and Bob use a commutative public key cryptosystem
DA(EB(EA(m))) = EB(m)
? Alice encrypts 52 messages m1 = (“Ace of Spades”,r1) …
using her public key,
? Alice sends the blobs to Bob,
? Bob picks 5 of these at random,encrypts with his public key
and sends them back to Alice,
? Alice decrypts the messages with her public key and sends
back to Bob,
? Bob decrypts the messages to determine his hand,
? At the end of the game,Alice and Bob reveal their key pairs
to ensure neither cheats,
19
attacks against poker schemes
? Since some cryptographic algorithms are not truly
random processes,they tend to leak small amounts
of information,
? In RSA,for example,if the binary representation of
the card is a quadratic residue,then the encryption
of the card is also a quadratic residue,
? Remember that x is a quadratic residue (QR) if y2 ≡ x
(mod p) has a solution,
? This could be used by a malicious dealer to,mark”
some cards (e.g,the Aces),
20
oblivious transfer
Problem,
? Bob is trying to factor a 500-bit number,n,
? Alice wants to sell Bob a 100-bit factor for $100
(at a reasonable $1/bit)
? Bob only has $50 and offers to buy half the bits
- but only if Alice proves that the number is a
factor of n,
? How can the deal be done given Alice cannot
convince her number is a factor of n without
telling it to Bob?
21
oblivious transfer
Algorithm,
? Alice generates two public/private key pairs EA1,DA1 and
EA2,DA2
? Alice → Bob,EA1,EA2
? Bob generates a symmetric cypher key,k
? Bob picks one of Alice’s public keys randomly and encrypts k
? Bob → Alice,{k}EX
? Alice decrypts the key twice DA1{k}EX DA2{k}EX resulting in k
and garbage DY{k}EX (Alice does not know which is the real
key),
? Alice sends Bob two messages,one real and one fake {“here
are the bits”} {“sucker!!!”},each encrypted with one of these
keys,
? Bob decrypts both with k,One message will make sense to
him,
? Bob now has one of the messages,Alice has no idea which one,
? After the protocol is complete,Alice must reveal both private
keys to so Bob knows she didn’t cheat,
22
oblivious transfer
Discussion,
? Alice still needs to convince Bob that the message is a
factor of n,She does that using a zero-knowledge proof
(remember,a way of Alice telling Bob that she knows x
without revealing any information about x),
? Obvious transfer is a way Alice can send a bit to Bob in
such a way that Bob receives the bit with probability 0.5
and Alice does not know if it is received or not,(i.e.,I
have one secret and you get it with probability 0.5”),
? This can be extended to,I have two secrets and you get
one”,I have n secrets and you get one”,etc,
? Obvious transfer is not used alone,It is used as a building
block in other protocols,
23
oblivious transfer- Michael Rabin
In this protocol,Alice has a 50 percent chance
of sending Bob two primes,p,and q,
? (1) Alice sends Bob the product of the two primes,
n = pq,
? (2) Bob chooses a random x less than n,such that
x is relatively prime to n,He sends Alice,
? a = x2 mod n
? (3) Alice,knowing p and q,computes the four
roots of a,x,n - x,y,and n - y,She chooses one of
these roots at random and sends it to Bob,
? (4) If Bob receives y or n - y,he can compute the
greatest common divisor of x + y and n,which is
either p or q,Then,of course,n/p = q,If Bob
receives x or n - x,he can’t compute anything,
24
subliminal channels
Problem,
? Alice and Bob have been arrested for conspiracy
to factor large numbers by the government,
? Alice has been sent to a woman’s jail,Bob to a
men’s correctional facility,
? The warden,Walter,is willing to let them
communicate on the condition that messages
are not encrypted,
? How can Alice and Bob communicate secretly
given might Walter attempt to deceive both of
them by planting false messages?
25
subliminal channels
? Alice and Bob set up a subliminal channel in their message
(otherwise known as a covert communications channel),
? On the simplest level,Alice and Bob could use
steganography aka stego (information hiding),Note stego
is not crypto (although you can combine the two),
? Examples of this channel might be,
– A ‘0’ is sent if the number of words in a sentence is even,
– A ‘1’ is sent if the number of words in a sentence is odd,
? One might send an image in an email where the low order
bit of each pixel is actually a message,
– the low order bit is below any human perceptual change in
quality
26
subliminal channels ? Loki
– Daemon9,Alhambra (phrack/the guild)
– Bidirectional covert UNIX shell client using the data field in ICMP
type 0 (Echo Reply) and type 8 (Echo Request) packets,
? Daemonshell-UDP
– ICMP Echo Reply only (more stealthy)
? ICMP Backdoor
– Reusable tunnel library
– Messages fragmented to look more like ping packets (multiples of 64
bytes)
? Rwwwshell
– Backdoor emits requests as HTTP Response packets
– Output from commands return from the slave as cgi script HTTP
GETs
? B0CK
– IGMP multicast messages used as transport
? AckCmd
– TCP ACK packets for request (port 80),TCP RESET packets for
response (high port)
27
zero knowledge proofs
Problem,
? Peggy wants to prove to Victor she knows some piece of
information without revealing it,
? Proofs take the form of interactive protocols
– Victor asks Peggy a question
– If Peggy knows the answer she will always get it correct
– Otherwise there is a small chance she can guess correctly
– Repeat asking questions until Victor is convinced
? Already seen ZKPs have applications in authentication
by challenge-response (e.g,proof of identity)
28
ali baba’s cave
? Quisquater & Guillou [1989]
? Illustration of ZKPs
? Peggy claims she knows the password to
open trapdoor but doesn’t want to tell it to
Victor
Algorithm,
– Victor stands at outside cave
– Peggy goes into random branch of cave
– Victor enters cave and calls for Peggy to
either come from one branch (left or
right)
– If Peggy knows password she can come
out correct side every time
– Repeat enough times until Victor is sure
Peggy knows it
L R
Victor
Peggy
29
zero-knowledge proofs
? Cut and choose protocol
– Alice cuts something in half
– Bob picks which half he wants
– Alice takes the remaining half
? Properties of ZKPs
– Victor cannot learn anything from the protocol
– Peggy cannot cheat Victor
– Victor cannot cheat Peggy
– Victor cannot pretend to be Peggy to any third party
30
attacks on zkps of identity
? The Mafia fraud
– Alice is eating at Fat Tony’s Mafia Diner
– Fast Eddie is shopping at Bob’s jewelery store
– Alice starts the ZKP identity protocol with Fat Tony
– Fat Tony radios Fast Eddie who starts a ZKP identity protocol with
Bob
– Fat Tony and Fast Eddie as a communications channel
– Alice ends up being ripped off by the mafia
? The Terrorist fraud
– Carlos the terrorist wants to enter the country
– Bob is scheming to help Carlos enter the country
– Carlos is challenged at the border by Alice with a ZKP of identity
– Carlos radios Bob and gets him to enter the ZKP identity protocol
– Alice thinks Carlos is Bob and lets him in
31
Graph Isomorphism
? Assume that Peggy knows the isomorphism between the two graphs,G1
and G2,The following protocol will convince Victor of Peggy’s knowledge,
? (1) Peggy randomly permutes G1 to produce another graph,H,that is
isomorphic to G1,Because Peggy knows the isomorphism between H
and G1,she also knows the isomorphism between H and G2,
? (2) Peggy sends H to Victor,
? (3) Victor asks Peggy either to,
? (a) prove that H and G1 are isomorphic,or
? (b) prove that H and G2 are isomorphic,
? (4) Peggy complies,She either,
? (a) proves that H and G1 are isomorphic,without proving that H
and G2 are isomorphic,or
? (b) proves that H and G2 are isomorphic,without proving that H
and G1 are isomorphic,
? (5) Peggy and Victor repeat steps (1) through (4) n times,
32
Feige-Fiat-Shamir
? Before issuing any private keys,the arbitrator
chooses a random modulus,n,which is the product
of two large primes,
? To generate Peggy’s public and private keys,a
trusted arbitrator chooses a number,v,where v is a
quadratic residue mod n,In other words,choose v
such that x2 ≡ v (mod n) has a solution and v-1 mod n
exists,This v is Peggy’s public key,Then calculate
the smallest s for which s ≡ sqrt (v-1) (mod n),This is
Peggy’s private key,
33
Feige-Fiat-Shamir
? (1) Peggy picks a random r,where r is less then n,She
then computes x = r2 mod n,and sends x to Victor,
? (2) Victor sends Peggy a random bit,b,
? (3) If b = 0,then Peggy sends Victor r,If b = 1,then Peggy
sends Victor y = r * s mod n,
? (4) If b = 0,Victor verifies that x = r2 mod n,proving that
Peggy knows sqrt (x),If b = 1,Victor verifies that x = y2 * v
mod n,proving that Peggy knows sqrt (v-1),
? This is a single round of the protocol,
? Peggy and Victor repeat this protocol t times,until
Victor is convinced that Peggy knows s,
34
dining cryptographer’s problem
Problem,
Three cryptographers are sitting down to dinner at their
favourite three-star restaurant,Their waiter informs them
that arrangements have been made with the maitre d'hotel
for the bill to be paid anonymously,One of the
cryptographers might be paying for the dinner,or it might
have been NSA,The three cryptographers respect each
other's right to make an anonymous payment,but they
wonder if NSA is actually paying,
- David Chaum (1988),
35
dining cryptographer’s problem
Algorithm,
? Each cryptographer flips an unbiased coin (in secret)
? Each shows the result to the person on the right
? Each cryptographer states whether the two coins he can
see are the same or different
? If one of the cryptographers is the payer he says the
opposite of what he sees
? An odd number of differences means that a
cryptographer has paid,otherwise the NSA paid
? The algorithm is extensible to any number of diners
