Similar presentations:

# Overview. Beyond basic cryptography

## 1. Overview

Beyond basic cryptography:o Secret splitting - divide a message into n pieces, such

that all n pieces must be combined to recover the

message

o Blind signatures – produce an unlinkable digital signature

o Bit commitment allows a user to commit to a prediction

without revealing it

o Cryptographic protocols make use of cryptography to

accomplish some task securely

Authentication

Key-exchange

o Zero-knowledge proofs allows a person to prove that he

knows a secret without revealing it

Chapter 6 Other Security Building Blocks

1

## 2. Motivation for Secret Splitting

A professor, Carol, encrypts her grade filewith a symmetric-key cryptosystem

o Good: only Carol can read grades (privacy)

o Good: only Carol can modify grades (integrity)

o Bad: if Carol becomes incapacitated nobody else

can recover the grades

Carol needs some kind of a mechanism that

will allow someone other than her to

decrypt the grade file in case of an

emergency

Chapter 6 Other Security Building Blocks

2

## 3. Secret Splitting

Secret splitting makes it possible to dividea message into n pieces called shadows,

such that:

o Combining less than n shadows yields nothing

o Combining all n shadows yields the message

Carol can split her key into n shadows and

give one to n different people she trusts:

o Good: if Carol becomes incapacitated all n

people can get together and recover the grade

file

o Good: Unlikely that all n people would betray

Carol’s trust

Chapter 6 Other Security Building Blocks

3

## 4. Secret Splitting Using One-Time Pads

M = “THEKEYISTHREE”Create four shadows:

Generate n-1 one-time pads (as long as M):

o P1 = PDJEUVNSKTUEG

o P2 = NBEXUYYKPAQJZ

o P3 = ICMKELDAOFGMC

Encrypt M with P1:

o C1 = JLOPZUYLEBMJL

T (20) + P (16) mod 26 = J (10)

H (8) + D (4) mod 26 = L (12)

E(5) + J (10) mod 26 = O (15)

…

Chapter 6 Other Security Building Blocks

4

## 5. Secret Split. with One-Time Pads

Encrypt C1 with P2:o C2 = XNTNUTXWUCDTL

Encrypt C2 with P3:

o C3 = GQGYZFBXJIKGO

P1, P2, P3, and C3 are the four shadows

Good: all four shadows are required to reconstruct

M:

o Use P3 to decrypt C3 yielding C2

o Use P2 to decrypt C2 yielding C1

o Use P1 to decrypt C1 yielding M

Bad: What happens if Carol and one of the shadow

holders become incapacitated?

Chapter 6 Other Security Building Blocks

5

## 6. Secret Sharing

Secret sharing (also called a threshold scheme) makes itpossible to divide a message into n shadows, such that:

o Combining less than k shadows yields nothing

o Combining any k (or more) yields the message

Example:

o Carol uses a (3-8)-threshold scheme to divide her key into eight

shadows (any three required to recover M)

o Give three to Alice, one to Bob, two to Dave, and one each to Elvis

and Fred

o Carol’s key can be recovered by:

Alice (3)

Dave (2) and Bob (1)

Bob (1), Elvis (1), and Fred (1)

Etc.

Good: Need some, not all, shadows to recover the key

Chapter 6 Other Security Building Blocks

6

## 7. Motivation for Blind Sig’s

Dave owns a bankCarol has an account at Dave’s bank

Carol wants to withdraw some digital money

Carol would like for the digital money to be:

o Valid – it should be accepted as payment by merchants

(perhaps after some verification procedure)

o Anonymous – Dave should not be able to determine where

Carol spends her money

Blind signatures allow Dave to create digital money

that is both valid and anonymous

Chapter 6 Other Security Building Blocks

7

## 8. Blind Signatures

Blind signatures enable a user to digitally sign adocument without seeing its contents

Assume Dave’s RSA public/private keys are:

o Public: e = 413, n = 629

o Private: d = 53

Before giving a message, m, to Dave for his

signature, Carol can blind it

o Choose a random blinding factor, b

1 < b < n-1

b is relatively prime to n

Example (using small numbers): m = 250 and b = 5

Chapter 6 Other Security Building Blocks

8

## 9. Blind Signatures (cont)

Carol blinds the message:B = (m (be)) mod n

B = (250 (5413)) mod 629

B = 172

Carol gives the blinded message, B, to Dave

Dave cannot read the blinded message

because he does not know the blinding

factor

o If n is large, exhaustive search for b is

unfeasible

Chapter 6 Other Security Building Blocks

9

## 10. Blind Signatures (cont)

Davesigns the blinded message as he

would any other message:

S’ = Bd mod n

S’ = 17253 mod 629

S’ = 168

Dave

sends the signed blinded

message, S’, to Carol

Chapter 6 Other Security Building Blocks

10

## 11. Blind Signatures (cont)

Carol unblinds the signed blinded message bymultiplying it by b’s multiplicative inverse modulo n

In our example, b = 5, so b-1 = 126 since

(126 5) mod 629 = 1

Carol computes:

S = (S’ b-1) mod n

S = (168 126) mod 629

S = 411

Note that the resulting digital signature, S = 411,

is identical to the one that would be produced by

Dave signing m = 250 with his private key!

Chapter 6 Other Security Building Blocks

11

## 12. Properties of Blind Signatures

Validity – as with normal digital signatures:o Anyone can use Dave’s public key to verify his

signature on the document is valid

o Dave’s signature still cannot be forged or

moved to another document, and Dave cannot

repudiate his signature

Unlinkability – unlike normal digital

signatures:

o Dave cannot subsequently link the unblinded

signed document to the blind document that he

signed

Chapter 6 Other Security Building Blocks

12

## 13. Unlinkability of Blind Signatures

Suppose:o Carol gives Dave two blinded documents to sign

o Dave signs them, returns them to Carol, and

keeps copies of the two blind documents

o Carol unblinds them and gives Dave copies of

the two unblinded documents bearing his

signature

Then:

o Dave will not be able to determine which

unblinded document corresponds to which

blinded document

Chapter 6 Other Security Building Blocks

13

## 14. Example of Unlinkability

Carol gives Dave two blinded documents to signo B1 = 542, B2 = 492

Dave signs them, returns them to Carol, and keeps copies of

the two blind documents

Carol unblinds them and gives Dave copies of the two

unblinded documents bearing his signature

o S1 = 217, S2 = 121

Dave can verify his signature and learn the contents of the

documents he signed:

o m1 = 217413 mod 629 = 200, m2 = 121413 mod 629 = 100

Dave cannot link an unblinded document to the corresponding

blind document:

o B1 = m1 and B2 = m2?

o B1 = m2 and B2 = m1?

Chapter 6 Other Security Building Blocks

14

## 15. Example of Unlinkability (cont)

To link an unblinded document to the corresponding blinddocument

o B1 (542) = m1 (200) and B2 (492) = m2 (100), or

o B1 (542) = m2 (100) and B2 (492) = m1 (200)

Dave must determine the blinding factor used to blind each

document

Dave can use exhaustive search to find the blinding factors:

o b1 = 409 since (100 × 409413) mod 629 = 542

o b2 = 557 since (200 × 557413) mod 629 = 492

Dave knows that the first blind document he signed, B1, was

m2 and the second blind document was m1

For large values of n, exhaustive search is not feasible and

therefore the signatures are unlinkable

Chapter 6 Other Security Building Blocks

15

## 16. Motivation for Blind Signatures (cont)

Why would Dave sign a blind document that hecould not read and create an unlinkable signature?

Recall:

o Dave owns a bank

o Carol has an account at Dave’s bank

o Carol wants to withdraw some digital money

o Carol would like for the digital money to be:

Valid – it should be accepted as payment by merchants

(perhaps after some verification procedure)

Anonymous – Dave should not be able to determine where

Carol spends her money

o Blind signatures allow Dave to create digital money that

is both valid and anonymous

Chapter 6 Other Security Building Blocks

16

## 17. Digital Money Without Blind Sig’s

Carol creates a message containing a serial number and avalue

o Serial number = 603482, Value = $10

Dave signs the message and deducts $10 from Carol’s

account

Carol uses the signed message to pay a merchant

o The merchant uses Dave’s public key to verify his signature

The merchant redeems the money with Dave for $10

Good: Carol’s digital money is valid

Bad: Carol’s digital money is not anonymous

o Dave could keep a record each serial number and to whom it was

issued

o When a merchant redeems digital money Dave could determine

to whom that money was issued

Chapter 6 Other Security Building Blocks

17

## 18. Digital Money With Blind Signatures

Carol creates a message containing a serial number and avalue

o Serial number = 603482, Value = $10

Carol blinds the message before giving it to Dave to sign

Dave does not know the blinding factor so he cannot see the

contents of the message (e.g. the serial number)

Dave signs the message and deducts $10 from Carol’s

account

Carol unblinds the message uses the signed message to pay a

merchant

o The merchant uses Dave’s public key to verify his signature

The merchant redeems the money with Dave for $10

Good: Carol’s digital money is valid

Good: Carol’s digital money is anonymous

Chapter 6 Other Security Building Blocks

18

## 19. Digital Money With Blind Signatures (cont)

Problem #1: double spendingo Carol uses her digital money to pay one merchant

The merchant uses Dave’s public key to verify it is valid

o Carol uses the same piece of digital money to pay another

merchant

The merchant uses Dave’s public key to verify it is valid

o Twenty dollars worth of digital money has cost Carol $10

Solution: merchant must check with Dave and

make sure the digital money has not already been

spent before accepting it

Chapter 6 Other Security Building Blocks

19

## 20. Digital Money With Blind Signatures (cont)

Problem #2: fraudo Carol creates a message worth $1000

o Carol blinds the message before giving it to Dave to sign

telling him it is worth $10

Dave does not know the blinding factor so he cannot see the

contents of the message

o Dave signs the message and deducts $10 from Carol’s

account

o $1,000 worth of digital money has cost Carol $10

Solution: Dave needs to be pretty sure of the

value of the digital money without actually seeing

it (and the serial number)

Chapter 6 Other Security Building Blocks

20

## 21. Digital Money With Blind Signatures (cont)

Dave requires Carol to create and submit 100messages:

m1 = “Serial number = 935076, Value = $10”

m2 = “Serial number = 104766, Value = $10”

...

m100 = “Serial number = 337147, Value = $10”

Carol chooses 100 different blinding factors, b1,

b2, …, b100

Carol uses the blinding factors to create 100

blinded messages

Carol gives all 100 blinded messages to Dave and

tells him their value ($10 each in this case)

Chapter 6 Other Security Building Blocks

21

## 22. Digital Money With Blind Signatures (cont)

Dave chooses 99 of the 100 messages at randomto challenge

Dave asks Carol for the corresponding blinding

factors

Dave unblinds each of the 99 messages and checks

to see that each is worth $10

If all checks succeed Dave signs the one blind

message he did not challenge and returns it to

Carol

Carol unblinds the message

Carol now has a valid, anonymous piece of digital

money from Dave

Chapter 6 Other Security Building Blocks

22

## 23. Digital Money With Blind Signatures (cont)

For Carol to get $1,000 worth of digitalmoney for $10 she would have to:

o Create 99 messages containing the value $10

o Create one message containing the value $1,000

o Hope that the $1,000 message is the one

message that Dave does not challenge

Carol’s chances of succeeding are one in

100

Dave can lower the odds of fraud by

requiring 1,000 or 1,000,000 messages to

be submitted

Chapter 6 Other Security Building Blocks

23

## 24. Motivation for Bit Commitment

Might want to commit to a prediction without revealing itChuck and Bill’s virtual coin flips – Scenario #1

o

o

o

o

Chuck thinks of a value, either ‘heads’ or ‘tails’

Bill announces his guess

Chuck tells Bill his value

Problem: Chuck can cheat Bill

Chuck has not committed to a value - he can change it after Bill

guesses

Chuck and Bill’s virtual coin flips – Scenario #2

o

o

o

o

Bill thinks of his guess

Chuck thinks of a value and announces it to Bill

Bill tells Chuck his guess

Problem: Bill can cheat Chuck

Chuck had to reveal his value in order to commit to it

Chapter 6 Other Security Building Blocks

24

## 25. Motivation for Bit Commitment (cont)

Chuck and Bill’s virtual coin flips – Scenario #3o Chuck chooses a value, writes it on a piece of paper, seals

it in an envelope, and hands the envelope to Bill

o Bill announces his guess

o Bill opens the envelope and both learn whether Bill was

right

o Good: neither can cheat

Fairness requirements:

o Chuck must commit to his value in such a way that:

Chuck cannot subsequently change the value

Bill does not learn Chuck’s value until after Bill has guessed

Chapter 6 Other Security Building Blocks

25

## 26. Bit Commitment

Bit commitment allows someone to commit to aprediction without revealing it

Bit commitment has two phases:

o Commitment phase: one party commits to a prediction in

such a way that it cannot be subsequently changed

o Verification phase: the second party learns the first

party’s prediction

Cheating is impossible if:

o The prediction cannot be changed after the commitment

phase

o The prediction is not revealed until the verification

phase

Chapter 6 Other Security Building Blocks

26

## 27. Bit Commitment Using a Symmetric-Key Cryptosystem

Commitment phase:o Chuck chooses a random key, k, and encrypts his

prediction

M = Encrypt(p,k)

o Chuck gives a copy of M to Bill

Problem: easy for Chuck to change prediction by

finding M such that:

o Decrypt(M, k1) = 0, and

o Decrypt(M, k2) = 1

Solution:

o Bill send a random string of bits, R, to Chuck

o Chuck concatenates his prediction to R and then

encrypts:

M = Encrypt(“Rp”, k)

Chapter 6 Other Security Building Blocks

27

## 28. Bit Commitment Using a Symmetric-Key Cryptosystem

Commitment phase:o Bill send a random string of bits, R, to Chuck

o Chuck concatenates his prediction to R and then

encrypts:

M = Encrypt(“Rp”, k)

o Chuck gives a copy of M to Bill

Verification phase:

o Chuck sends k to Bill

o Bill decrypts M, checks R, and learns p:

Decrypt (M, k)

Chapter 6 Other Security Building Blocks

28

## 29. Bit Commitment Using a Symmetric-Key Cryptosystem

Neither can cheat:o The prediction cannot be changed after the

commitment phase

A good cryptosystem will not allow Chuck to create an

M such that:

Decrypt(Rp1,k1) = M

Decrypt(Rp2,k2) = M

o The prediction is not revealed until the

verification phase

Bill does not know the key Chuck chose and connot

read M without it

Chapter 6 Other Security Building Blocks

29

## 30. Bit Commitment Using a One-Way Hash Function

Commitment phase:o Chuck creates two random strings of bits, R1 and R2

o Chuck concatenates R1, R2, and his prediction, p, and

sends the result through the one-way hash function, H:

h = H(R1R2p)

o Chuck sends h and R1 to Bill

Verification phase:

o Chuck sends R2 and p to Bill

o Bill computes the hash:

h’ = H(R1R2p)

o Bill verifies that h’ = h

Chapter 6 Other Security Building Blocks

30

## 31. Bit Commitment Using a One-Way Hash Function

Neither can cheat:o The prediction cannot be changed after the

commitment phase

A good one-way hash function will not allow Chuck to

create an R1, R2, and p such that there is a collision:

H(R1R2p1) = h

H(R1R3p2) = h

o The prediction is not revealed until the

verification phase

Since the hash function is one-way, Bill cannot deduce

p from h and R1

Chapter 6 Other Security Building Blocks

31

## 32. Cryptographic Protocols

A protocol is an agreed-upon sequence ofactions performed by two or more

principals

Cryptographic protocols make use of

cryptography to accomplish some task

securely

Example:

o How can Alice and Bob agree on a session key to

protect a conversation?

o Answer: use a key-exchange cryptographic

protocol

Chapter 6 Other Security Building Blocks

32

## 33. Key Exchange with Symmetric Cryptography

Assume Alice and Bob each share a keywith a Key Distribution Center (KDC)

o KA is the key shared by Alice and the KDC

o KB is the key shared by Bob and the KDC

To agree on a session key:

o Alice contacts the KDC and requests a session

key for Bob and her

o The KDC generates a random session key,

encrypts it with both KA and KB, and sends the

results to Alice

Chapter 6 Other Security Building Blocks

33

## 34. Key Exchange with Symmetric Cryptography (cont)

Agreeing on a session key (cont):o Alice decrypts the part of the message

encrypted with KA and learns the session key

o Alice sends the part of the message encrypted

with KB to Bob

o Bob receives Alice’s message, decrypts it, and

learns the session key

o Alice and Bob communicate securely using the

session key

Chapter 6 Other Security Building Blocks

34

## 35. Key Exchange with Symmetric Cryptography (cont)

Thekey-exchange protocol:

A: => KDC (A,B);

KDC: => A (E(KAB,KA), E(KAB,KB));

A: => B (E(KAB,KB));

Chapter 6 Other Security Building Blocks

35

## 36. Key Exchange with Symmetric Cryptography (cont)

Issues:o Security depends on secrecy of KA and KB

KDC must be secure and trusted by both Alice and

Bob

KA and KB should be used sparingly

o The use of a new session key for each

conversation limits the chances/value of

compromising a session key

Chapter 6 Other Security Building Blocks

36

## 37. Attacking the Protocol

Alice and Bob set up a secure session protected by KABAn intruder, Mallory, watches them do this and stores the

KDC’s message to Alice and all the subsequent messages

between Alice Bob encrypted with KAB

Mallory cryptanalyzes the session between Alice and Bob and

eventually recovers KAB

The next time Alice and Bob want to talk Mallory intercepts

the KDC’s reply and replays the old message containing KAB

Alice and Bob conduct a “secure” conversation which is

protected by KAB which is known to Mallory

Chapter 6 Other Security Building Blocks

37

## 38. Attacking the Protocol (cont)

A: => KDC (A,B);KDC: => A (E(KAB,KA), E(KAB,KB));

A: => B (E(KAB,KB));

// Alice and Bob encrypt their messages using KAB

// Mallory recovers KAB by analyzing Alice and Bob’s session

A: => KDC (A,B);

KDC: => A (E(KAB’,KA), E(KAB’,KB));

// Mallory intercepts the above message and replaces it

M: => A (E(KAB,KA), E(KAB,KB));

A: => B (E(KAB,KB));

// Mallory reads all traffic session between Alice and Bob

Chapter 6 Other Security Building Blocks

38

## 39. What Went Wrong?

Alice and Bob need to be able todistinguish between a current (or fresh)

response from the KDC and an old one

Solutions:

o Alice and Bob could keep track of all previously-

used session keys and never accept an old

session key

o KDC could include freshness information in its

messages

Timestamps

Nonces

Chapter 6 Other Security Building Blocks

39

## 40. Using Timestamps to Establish Freshness

A: => KDC (A,B);KDC: => A (E((KAB,TKDC),KA), E((KAB,TKDC),KB));

A: => B (E((KAB,TKDC),KB));

Where TKDC is a timestamp from the KDC’s

clock and:

Alice and Bob’s clocks are both synchronized with

the KDC’s

Alice and Bob both check the KDC’s message to

make sure it was generated recently

Chapter 6 Other Security Building Blocks

40

## 41. Using Nonces to Establish Freshness

A nonce is a randomly-generated valuethat:

o Is never reused

o Can be used to prove the freshness of a

message

A: => KDC (A,B,NA);

B: => KDC (A,B, NB);

KDC: => A (E((KAB,NA),KA));

KDC: => B (E((KAB,NB),KB));

Chapter 6 Other Security Building Blocks

41

## 42. Key-Exchange with Public-Key Cryptography

Alice learns Bob’s public key (by eitherasking Bob or some third party)

Alice generates a random session key, KAB

Alice encrypts the session key with Bob’s

public key

Alice sends Encrypt(KAB,BPublic) to Bob

Bob receives Alice’s message and decrypts

it with his private key

Alice and Bob encrypt their subsequent

communications with KAB

Chapter 6 Other Security Building Blocks

42

## 43. Attacking the Protocol

Recall the man-in-the-middle attacko If Mallory can trick Alice into thinking that

MPublic is Bob’s public key

Mallory can decrypt Alice’s first message to Bob

Encrypt(KAB,MPublic)

Mallory learns the proposed session key KAB

Mallory can send Bob: Encrypt(KAB,BPublic)

Alice and Bob will encrypt their subsequent

communications with KAB thinking that it is secure

This is a very serious problem because it’s

often difficult to be sure you know

somebody’s public key

Chapter 6 Other Security Building Blocks

43

## 44. The Interlock Protocol

Combating the man-in-the-middle attack:o Alice and Bob exchange public keys

o Alice encrypts her message using Bob’s public key. Alice

sends half the encrypted message to Bob (e.g. every

other bit)

o Bob encrypts his message using Alice’s public key. Bob

sends half the encrypted message to Alice (e.g. every

other bit)

o Alice sends the other half of her encrypted message to

Bob. Bob puts the two halves together and decrypts them

using his private key

o Bob sends the other half of his encrypted message to

Alice. Alice puts the two halves together and decrypts

them using her private key

Chapter 6 Other Security Building Blocks

44

## 45. The Interlock Prot. (cont)

Foiling the man-in-the-middle:o Assume Mallory can trick Alice into using MPublic instead

o

o

o

o

o

of BPublic

When Mallory receives the first half of Alice’s message

she won’t be able to decrypt it and re-encrypt it with

BPublic

Mallory must invent a completely new message, encrypt it

and send half of it to Bob

When the second half of Alice’s message arrives, Mallory

can put the two halves together, decrypt, and learn what

Alice’s original message was

However, Mallory has already committed to the first half

of the message and it is too late to change

Therefore, Bob will not get the message Alice sent, and

Alice and Bob will probably be able to figure out that

there is an intruder between them

Chapter 6 Other Security Building Blocks

45

## 46. Authentication

Authentication is the process of provingyour identity to someone else

o One-way

o Two-way

Authentication protocols are often

designed using a challenge and response

mechanism

o Authenticator creates a random challenge

o Authenticatee proves identity by replying with

the appropriate response

Chapter 6 Other Security Building Blocks

46

## 47. One-way Authentication Using Symmetric-Key Cryptography

Assume that Alice and Bob share a secretsymmetric key, KAB

One-way authentication protocol:

o Alice creates a nonce, NA, and sends it to Bob as a

challenge

o Bob encrypts Alice’s nonce with their secret key and

returns the result, Encrypt(NA, KAB), to Alice

o Alice can decrypt Bob’s response and verify that the

result is her nonce

A: => B(NA);

B: => A(Encrypt(NA, KAB));

Chapter 6 Other Security Building Blocks

47

## 48. One-way Authentication Using Symmetric-Key Cryptography

Problem: an adversary, Mallory, might be able toimpersonate Bob to Alice:

o Alice sends challenge to Bob (intercepted by Mallory)

o Mallory does not know KAB and thus cannot create the

appropriate response

o Mallory may be able to trick Bob (or Alice) into creating

the appropriate response for her:

A: => M(NA);

M: => B(NN);

B: => M(Encrypt(NA, KAB));

M: => A(Encrypt(NA, KAB));

Chapter 6 Other Security Building Blocks

48

## 49. One-way Authentication Using Public-Key Cryptography

Alice sends a nonce to Bob as a challengeBob replies by encrypting the nonce with his

private key

Alice decrypts the response using Bob’s public key

and verify that the result is her nonce

A: => B(NA);

B: => A(Encrypt(NA, BPrivate));

Encrypting any message that someone sends as an

authentication challenge might not be a good idea

Chapter 6 Other Security Building Blocks

49

## 50. One-way Authentication Using Public-Key Cryptography

Another challenge-and-response authenticationprotocol:

o Alice performs a computation based on some random

numbers (chosen by Alice) and her private key and sends

the result to Bob

o Bob sends Alice a random number (chosen by Bob)

o Alice makes some computation based on her private key,

her random numbers, and the random number received

from Bob and sends the result to Bob

o Bob performs some computations on the various numbers

and Alice’s public key to verify that Alice knows her

private key

Advantage: Alice never encrypts a message chosen

by someone else

Chapter 6 Other Security Building Blocks

50

## 51. Authentication and Key-Exchange Protocols

Combine authentication and key-exchangeAssume Carla and Diane are on opposite ends of a

network and want to talk securely

o Want to agree on a new session key securely

o Want to each be sure that they are talking to the other

and not an intruder

Wide-Mouth Frog

o Assumes a trusted third-party, Sam, who shares a secret

keys, KC and KD, respectively, with Carla and Diane

Chapter 6 Other Security Building Blocks

51

## 52. Authentication and Key-Exchange Protocols

Wide-Mouth FrogC: => S(C,Encrypt((D,KCD,TC),KCS));

S: => D(Encrypt((C, KCD, TS), KDS));

Observations:

o Reliance on synchronized clocks to generate

timestamps

o Depends on a third-party that both participants

trust

o Initiator is trusted to generate good session keys

Chapter 6 Other Security Building Blocks

52

## 53. Authentication and Key-Exchange Protocols

YahalomC => D (C,NC);

D => S (D,Encrypt((C,NC,ND),KD));

S => C (Encrypt((D,KCD,NC,ND),KC),Encrypt((C,KCD),KD));

C => D (Encrypt((C,KCD),KD),Encrypt(ND,KCD));

Note: Diane is the first one to contact Sam

who only sends one message to Carla

Chapter 6 Other Security Building Blocks

53

## 54. Authentication and Key-Exchange Protocols

Denning and Sacco (public-key)o Carla sends a message to Sam including her name and Diane’s

name

o Sam replies with signed copies of both Carla and Diane’s

public key

C: => S(C,D);

S: =>

C(Encrypt((C,CPublic,TS),SPriavte),Encrypt((D,DPublic,TS),SPriavte));

C: =>

D(Encrypt((C,CPublic,TS),SPriavte),Encrypt((D,DPublic,TS),SPriavte));

o Carla generates the session key, KCD, and signed a message

containing it and a timestamp with her private key

C: => D(Encrypt(Encrypt((KCD,TC),CPrivate),DPublic));

Chapter 6 Other Security Building Blocks

54

## 55. Authentication and Key-Exchange Protocols

A weakness of the Denning and Sacco protocolo Harry can trick Diane into thinking that she is

communicating with Carla when she is really

communicating with Harry

o Harry establishes a session key, KCH, with Carla

C: => H(Encrypt(Encrypt((KCH,TC),CPrivate),HPublic));

o Harry decrypts Carla’s message and learns KCH

o Harry encrypts Carla’s signed message with Diane’s public

key, and sends the result to Diane claiming to be Carla

H: => D(Encrypt(Encrypt((KCH,TC),CPrivate),DPublic));

o Diane will decrypt the message, check the signature and

timestamp, and believe that she is talking to Carla with

KCH as the session key

Chapter 6 Other Security Building Blocks

55

## 56. Authentication and Key-Exchange Protocols

Fixingthe Denning and Sacco

protocol:

o Add the other party’s name to the key

exchange message:

C: =>

D(Encrypt(Encrypt((D,KCD,TC),CPrivate),DPublic));

Chapter 6 Other Security Building Blocks

56

## 57. Motivation for Zero Knowledge Proofs

Many challenge and response authenticationprotocols

o Prove identity by demonstrating knowledge of a certain

piece of information (e.g. a password)

o Bob authenticates Alice based on her knowledge of a

secret, S

Only Alice knows the secret, S

This person knows

Therefore, this person is Alice

Drawbacks:

o Requires Alice to disclose S to Bob

Bob may subsequently be able to impersonate Alice

Chapter 6 Other Security Building Blocks

57

## 58. Zero-Knowledge Proofs

Alice can perform a zero-knowledge proof so that:o Bob can verify that Alice knows the secret

o Bob does not gain any information about the secret

Overview:

o Bob will ask Alice a series of questions

o For each question:

If Alice knows the secret she will have a 100% chance of answering

correctly

If Alice does not know the secret she will have a 50% chance of

answering correctly

o If Alice answers many questions in row correctly chances are

good that she knows the secret

o None of the questions or answers give Bob any information

about Alice’s secret

Chapter 6 Other Security Building Blocks

58

## 59. Zero-Knowledge Proofs (cont)

Bob asks Alice up to n questionso If Alice ever answers incorrectly, Bob stops and knows Alice

does not know S

o If Alice always answers correctly, she probably knows S

How many questions should Bob ask?

o n=1

Efficient but chance of getting fooled

Alice’s odds of guessing right once are 1 in 2

o n = 10

Less efficient, less chance of getting fooled

Alice’s odds of guessing right ten times are 1 in 210 (~1,000)

o n = 20

Much less efficient, little chance of getting fooled

Alice’s odds of guessing right twenty times are 1 in 220 (~1,000,000)

Chapter 6 Other Security Building Blocks

59

## 60. The Zero-Knowledge Cave

A cave with a single entranceThe entry passage forks into left and right

passages

The two passages eventually meet each

other

A door has been built where they join

o The only way to open the door is to say the

“magic words”

Chapter 6 Other Security Building Blocks

60

## 61. The Zero-Knowledge Cave (cont)

Chapter 6 Other Security Building Blocks61

## 62. The Zero-Knowledge Cave (cont)

Alice can prove to Bob that she knows the magicwords

Alice need not reveal the magic words to Bob:

o Alice and Bob stand at the entrance to the cave

o Alice walks all the way into the cave until she is standing

at the door

o Bob walks into the cave and to the fork

Bob does not know whether Alice chose to take the left or

the right passage to the door

o Bob chooses at random to ask Alice to come out of either

the passage to Bob’s right or the one to his left

o Alice exits from the appropriate passage (using the

magic words if necessary)

Chapter 6 Other Security Building Blocks

62

## 63. The Zero-Knowledge Cave

There are four possiblities:(1) Alice enters the left passage and Bob asks her to come out the

left

Alice does not need to pass through the door

(2) Alice enters the left passage and Bob asks her to come out the

right

Alice must say the magic words to pass through the door

(3) Alice enters the right passage and Bob asks her to come out the

left

Alice must say the magic words to pass through the door

(4) Alice enters the right passage and Bob asks her to come out the

right

Alice does not need to pass through the door

If Alice knows the magic words she can come out of the

proper passage 100% of the time

If Alice does not know the magic words she can come out of

the proper passage 50% of the time

Chapter 6 Other Security Building Blocks

63

## 64. The Zero-Knowledge Cave (cont)

No matter how many times this protocol is run Boblearns nothing about Alice’s secret

If Alice is able to complete 20 successful exits

from the cave then either:

(1) Bob’s requests were not random (Alice was able to

predict them)

(2) There was no barrier in the cave

(3) Alice guessed correctly 20 times in a row (~1 in

1,000,000)

(4) Alice knew the secret

So when performing a zero-knowledge proof, Bob

should try to make sure neither (1) nor (2) hold

Chapter 6 Other Security Building Blocks

64

## 65. Mathematical Background - Graph Isomorphism

A graph is a set of verteces and the edges that connectthem:

A

C

D

F

G

B

E

G

H

I

A

A

C

E

B

C

I

H

E

D

F

D

I

B

If Htwo graphs

are identicalF except

for the names Ggiven to

verteces

(I) they are called isomorphic

(II)

(III)

Chapter 6 Other Security Building Blocks

65

## 66. Graph Isomorphism

Graphs (I) and (II) are isomorphic:A

C

D

F

E

(I)

H

I

C

I

A

G

H

G

B

E

D

F

(II)

Chapter 6 Other Security Building Blocks

B

I

A

B

C

D

E

F

G

H

I

II

G

C

H

I

E

A

D

F

B

66

## 67. Graph Isomorphism (cont)

Graphs (II) and (III) are isomorphic:G

H

I

A

E

B

C

I

H

E

D

D

F

A

C

B

G

Are(II)

graphs (I) and (III) isomorphic?

(III)

Chapter 6 Other Security Building Blocks

F

II

A

B

C

D

E

F

G

H

I

III

I

F

B

E

D

H

C

A

G

67

## 68. Graph Isomorphism (cont)

Graphs (I) and (III) must be isomorphic because graphisomorphism is transitive

Can find the isomorphism by mapping from (I) to (II) to

(III):

I

A

B

C

D

E

F

G

H

I

II

G

C

H

I

E

A

D

F

B

II

A

B

C

D

E

F

G

H

I

Chapter 6 Other Security Building Blocks

III

I

F

B

E

D

H

C

A

G

I

A

B

C

D

E

F

G

H

I

III

C

B

A

G

D

I

E

H

F

68

## 69. Graph Isomorphism is a Hard Problem

In general, determining whether twographs are isomorphic is a difficult

problem:

o Best-known algorithm runs in time exponential

to the number of verteces

As the number of verteces gets large, finding an

answer is intractable

o A claimed isomorphism between two graphs can

be checked in polynomial time

As the number of verteces gets large, verifying an

answer is tractable

Chapter 6 Other Security Building Blocks

69

## 70. A Zero-Knowledge Proof Using Graph Isomorphism

Alice creates two graphs, G1 and G2, whichare isomorphic to each other:

o Randomly create G1

o Randomly permute the verteces of G1 to create

G2

o Save the permutation of G1’s verteces used to

produce G2

It is the isomorphism between the two

Alice can use a zero-knowledge proof to

convince Bob that she knows the

isomorphism without revealing it

Chapter 6 Other Security Building Blocks

70

## 71. Zero-Knowledge Proof Using Graph Isomorphism

Alice randomly permutes G1 to produce anothergraph, H, which is isomorphic to both G1 and G2

o Alice knows the isomorphism between G1 and G2

o Alice knows the isomorphism between G1 and H

o Alice knows the isomorphism between G2 and H (by

transativity)

o For anybody who does not know the isomorphism between

G1 and G2:

Finding the isomorphism between G1 and G2 is “hard”

Finding the isomorphism between G1 and H is as hard as

finding the isomorphism between G1 and G2

Finding the isomorphism between G2 and H is as hard as

finding the isomorphism between G1 and G2

Chapter 6 Other Security Building Blocks

71

## 72. Zero-Knowledge Proof Using Graph Isomorphism

Alice and Bob repeat the following protocol untilBob is satisfied:

o Alice randomly permutes G1 to produce another graph, H

o Alice sends H to Bob

o Bob asks Alice either to:

Prove that H and G1 are isomorphic, or

Prove that H and G2 are isomorphic

o Alice complies (without providing the other isomorphism)

o Bob verifies whether or not Alice’s answer is correct

Chapter 6 Other Security Building Blocks

72

## 73. Zero-Knowledge Proof Using Graph Isomorphism

Without knowing the isomorphism between G1 andG2 Alice cannot create a graph H for which she

knows the isomorphism to both G1 and G2

o Otherwise she would know the isomorphism between G1

and G2 by transitivity

In each round Alice’s must choose:

o Permute G1 to produce a graph, H1, for which she knows

the isomorphism to G1 (but not G2), or

o Permute G2 to produce a graph, H2, for which she knows

the isomorphism to G2 (but not G1)

Chapter 6 Other Security Building Blocks

73

## 74. Zero-Knowledge Proof Using Graph Isomorphism

Alice only sends one graph to Bob in each roundFour possibilities each round:

o Alice sends

answer

o Alice sends

answer

o Alice sends

answer

o Alice sends

answer

H1 and Bob asks for (H1,G1): Alice will be able to

H1 and Bob asks for (H1,G2): Alice will not be able to

H2 and Bob asks for (H2,G1): Alice will not be able to

H2 and Bob asks for (H2,G2): Alice will be able to

Results:

o Alice has a 50% chance in each round of answering correctly

whether or not she knows the isomorphism between G1 and G2

o Each round Bob learns the isomorphism between a random graph

and either G1 or G2

Chapter 6 Other Security Building Blocks

74

## 75. Zero-Knowledge Proof Using Graph Isomorphism

If Alice is able to answer correctly 20times in a row:

(1) Bob’s requests were not random

–

Alice was able to predict them and generate H

accordingly

(2) Graph isomorphism is not a hard problem

(3) Alice guessed correctly 20 times in a row

(4) Alice knew the secret

Chapter 6 Other Security Building Blocks

75

## 76. Problem With Zero-Knowledge Proofs

Remember the man-in-the-middle attack?Carol is going to prove to Bob that she knows the isomorphism

between G1 and G2 (even though she doesn’t)

o Carol asks Alice to prove she knows the isomorphism

o Alice generates a graph, H, and sends it to Carol

o Carol contacts Bob and says she’s ready to start the proof; she sends H

to Bob

o Bob chooses either G1 or G2 and asks Carol for the isomorphism

o Carol asks Alice the same question

o Alice answers Carol

o Carol repeats the answer to Bob

Results:

o Carol will answer Bob correctly in every round

o Bob will believe that Carol knows the isomorphism

o Carol does not know the isomorphism

Chapter 6 Other Security Building Blocks

76

## 77. Summary

Beyond basic cryptography:o Secret splitting - divide a message into n pieces, such

that all n pieces must be combined to recover the

message

o Blind signatures – produce an unlinkable digital signature

o Bit commitment allows a user to commit to a prediction

without revealing it

o Cryptographic protocols make use of cryptography to

accomplish some task securely

Authentication

Key-exchange

o Zero-knowledge proofs allows a person to prove that he

knows a secret without revealing it

Chapter 6 Other Security Building Blocks

77