Overview. Beyond basic cryptography

Июль 22, 2022

Главная
Информатика
Overview. Beyond basic cryptography

Содержание

2. Chapter 6  Other Security Building Blocks Motivation for Secret Splitting A professor, Carol, encrypts her
3. Chapter 6  Other Security Building Blocks Secret Splitting Secret splitting makes it possible to divide
4. Chapter 6  Other Security Building Blocks Secret Splitting Using One-Time Pads M = “THEKEYISTHREE” Create
5. Chapter 6  Other Security Building Blocks Secret Split. with One-Time Pads Encrypt C1 with P2:
6. Chapter 6  Other Security Building Blocks Secret Sharing Secret sharing (also called a threshold scheme)
7. Chapter 6  Other Security Building Blocks Motivation for Blind Sig’s Dave owns a bank Carol
8. Chapter 6  Other Security Building Blocks Blind Signatures Blind signatures enable a user to digitally
9. Chapter 6  Other Security Building Blocks Blind Signatures (cont) Carol blinds the message: B =
10. Chapter 6  Other Security Building Blocks Blind Signatures (cont) Dave signs the blinded message as
11. Chapter 6  Other Security Building Blocks Blind Signatures (cont) Carol unblinds the signed blinded message
12. Chapter 6  Other Security Building Blocks Properties of Blind Signatures Validity – as with normal
13. Chapter 6  Other Security Building Blocks Unlinkability of Blind Signatures Suppose: Carol gives Dave two
14. Chapter 6  Other Security Building Blocks Example of Unlinkability Carol gives Dave two blinded documents
15. Chapter 6  Other Security Building Blocks Example of Unlinkability (cont) To link an unblinded document
16. Chapter 6  Other Security Building Blocks Motivation for Blind Signatures (cont) Why would Dave sign
17. Chapter 6  Other Security Building Blocks Digital Money Without Blind Sig’s Carol creates a message
18. Chapter 6  Other Security Building Blocks Digital Money With Blind Signatures Carol creates a message
19. Chapter 6  Other Security Building Blocks Digital Money With Blind Signatures (cont) Problem #1: double
20. Chapter 6  Other Security Building Blocks Digital Money With Blind Signatures (cont) Problem #2: fraud
21. Chapter 6  Other Security Building Blocks Digital Money With Blind Signatures (cont) Dave requires Carol
22. Chapter 6  Other Security Building Blocks Digital Money With Blind Signatures (cont) Dave chooses 99
23. Chapter 6  Other Security Building Blocks Digital Money With Blind Signatures (cont) For Carol to
24. Chapter 6  Other Security Building Blocks Motivation for Bit Commitment Might want to commit to
25. Chapter 6  Other Security Building Blocks Motivation for Bit Commitment (cont) Chuck and Bill’s virtual
26. Chapter 6  Other Security Building Blocks Bit Commitment Bit commitment allows someone to commit to
27. Chapter 6  Other Security Building Blocks Bit Commitment Using a Symmetric-Key Cryptosystem Commitment phase: Chuck
28. Chapter 6  Other Security Building Blocks Bit Commitment Using a Symmetric-Key Cryptosystem Commitment phase: Bill
29. Chapter 6  Other Security Building Blocks Bit Commitment Using a Symmetric-Key Cryptosystem Neither can cheat:
30. Chapter 6  Other Security Building Blocks Bit Commitment Using a One-Way Hash Function Commitment phase:
31. Chapter 6  Other Security Building Blocks Bit Commitment Using a One-Way Hash Function Neither can
32. Chapter 6  Other Security Building Blocks Cryptographic Protocols A protocol is an agreed-upon sequence of
33. Chapter 6  Other Security Building Blocks Key Exchange with Symmetric Cryptography Assume Alice and Bob
34. Chapter 6  Other Security Building Blocks Key Exchange with Symmetric Cryptography (cont) Agreeing on a
35. Chapter 6  Other Security Building Blocks Key Exchange with Symmetric Cryptography (cont) The key-exchange protocol:
36. Chapter 6  Other Security Building Blocks Key Exchange with Symmetric Cryptography (cont) Issues: Security depends
37. Chapter 6  Other Security Building Blocks Attacking the Protocol Alice and Bob set up a
38. Chapter 6  Other Security Building Blocks Attacking the Protocol (cont) A: => KDC (A,B); KDC:
39. Chapter 6  Other Security Building Blocks What Went Wrong? Alice and Bob need to be
40. Chapter 6  Other Security Building Blocks Using Timestamps to Establish Freshness A: => KDC (A,B);
41. Chapter 6  Other Security Building Blocks Using Nonces to Establish Freshness A nonce is a
42. Chapter 6  Other Security Building Blocks Key-Exchange with Public-Key Cryptography Alice learns Bob’s public key
43. Chapter 6  Other Security Building Blocks Attacking the Protocol Recall the man-in-the-middle attack If Mallory
44. Chapter 6  Other Security Building Blocks The Interlock Protocol Combating the man-in-the-middle attack: Alice and
45. Chapter 6  Other Security Building Blocks The Interlock Prot. (cont) Foiling the man-in-the-middle: Assume Mallory
46. Chapter 6  Other Security Building Blocks Authentication Authentication is the process of proving your identity
47. Chapter 6  Other Security Building Blocks One-way Authentication Using Symmetric-Key Cryptography Assume that Alice and
48. Chapter 6  Other Security Building Blocks One-way Authentication Using Symmetric-Key Cryptography Problem: an adversary, Mallory,
49. Chapter 6  Other Security Building Blocks One-way Authentication Using Public-Key Cryptography Alice sends a nonce
50. Chapter 6  Other Security Building Blocks One-way Authentication Using Public-Key Cryptography Another challenge-and-response authentication protocol:
51. Chapter 6  Other Security Building Blocks Authentication and Key-Exchange Protocols Combine authentication and key-exchange Assume
52. Chapter 6  Other Security Building Blocks Authentication and Key-Exchange Protocols Wide-Mouth Frog C: => S(C,Encrypt((D,KCD,TC),KCS));
53. Chapter 6  Other Security Building Blocks Authentication and Key-Exchange Protocols Yahalom C => D (C,NC);
54. Chapter 6  Other Security Building Blocks Authentication and Key-Exchange Protocols Denning and Sacco (public-key) Carla
55. Chapter 6  Other Security Building Blocks Authentication and Key-Exchange Protocols A weakness of the Denning
56. Chapter 6  Other Security Building Blocks Authentication and Key-Exchange Protocols Fixing the Denning and Sacco
57. Chapter 6  Other Security Building Blocks Motivation for Zero Knowledge Proofs Many challenge and response
58. Chapter 6  Other Security Building Blocks Zero-Knowledge Proofs Alice can perform a zero-knowledge proof so
59. Chapter 6  Other Security Building Blocks Zero-Knowledge Proofs (cont) Bob asks Alice up to n
60. Chapter 6  Other Security Building Blocks The Zero-Knowledge Cave A cave with a single entrance
61. Chapter 6  Other Security Building Blocks The Zero-Knowledge Cave (cont)
62. Chapter 6  Other Security Building Blocks The Zero-Knowledge Cave (cont) Alice can prove to Bob
63. Chapter 6  Other Security Building Blocks The Zero-Knowledge Cave There are four possiblities: (1) Alice
64. Chapter 6  Other Security Building Blocks The Zero-Knowledge Cave (cont) No matter how many times
65. Chapter 6  Other Security Building Blocks Mathematical Background - Graph Isomorphism A graph is a
66. Chapter 6  Other Security Building Blocks Graph Isomorphism Graphs (I) and (II) are isomorphic: (I)
67. Chapter 6  Other Security Building Blocks Graph Isomorphism (cont) Graphs (II) and (III) are isomorphic:
68. Chapter 6  Other Security Building Blocks Graph Isomorphism (cont) Graphs (I) and (III) must be
69. Chapter 6  Other Security Building Blocks Graph Isomorphism is a Hard Problem In general, determining
70. Chapter 6  Other Security Building Blocks A Zero-Knowledge Proof Using Graph Isomorphism Alice creates two
71. Chapter 6  Other Security Building Blocks Zero-Knowledge Proof Using Graph Isomorphism Alice randomly permutes G1
72. Chapter 6  Other Security Building Blocks Zero-Knowledge Proof Using Graph Isomorphism Alice and Bob repeat
73. Chapter 6  Other Security Building Blocks Zero-Knowledge Proof Using Graph Isomorphism Without knowing the isomorphism
74. Chapter 6  Other Security Building Blocks Zero-Knowledge Proof Using Graph Isomorphism Alice only sends one
75. Chapter 6  Other Security Building Blocks Zero-Knowledge Proof Using Graph Isomorphism If Alice is able
76. Chapter 6  Other Security Building Blocks Problem With Zero-Knowledge Proofs Remember the man-in-the-middle attack? Carol
78. Скачать презентацию

Слайд 2

Chapter 6  Other Security Building Blocks
Motivation for Secret Splitting
A professor,

Carol, encrypts her grade file with a symmetric-key cryptosystem
Good: only Carol can read grades (privacy)
Good: only Carol can modify grades (integrity)
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

Слайд 3

Chapter 6  Other Security Building Blocks
Secret Splitting
Secret splitting makes it

possible to divide a message into n pieces called shadows, such that:
Combining less than n shadows yields nothing
Combining all n shadows yields the message
Carol can split her key into n shadows and give one to n different people she trusts:
Good: if Carol becomes incapacitated all n people can get together and recover the grade file
Good: Unlikely that all n people would betray Carol’s trust

Слайд 4

Chapter 6  Other Security Building Blocks
Secret Splitting Using One-Time Pads
M

= “THEKEYISTHREE”
Create four shadows:
Generate n-1 one-time pads (as long as M):
P1 = PDJEUVNSKTUEG
P2 = NBEXUYYKPAQJZ
P3 = ICMKELDAOFGMC
Encrypt M with P1:
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)
…

Слайд 5

Chapter 6  Other Security Building Blocks
Secret Split. with One-Time Pads
Encrypt

C1 with P2:
C2 = XNTNUTXWUCDTL
Encrypt C2 with P3:
C3 = GQGYZFBXJIKGO
P1, P2, P3, and C3 are the four shadows
Good: all four shadows are required to reconstruct M:
Use P3 to decrypt C3 yielding C2
Use P2 to decrypt C2 yielding C1
Use P1 to decrypt C1 yielding M
Bad: What happens if Carol and one of the shadow holders become incapacitated?

Слайд 6

Chapter 6  Other Security Building Blocks
Secret Sharing
Secret sharing (also called

a threshold scheme) makes it possible to divide a message into n shadows, such that:
Combining less than k shadows yields nothing
Combining any k (or more) yields the message
Example:
Carol uses a (3-8)-threshold scheme to divide her key into eight shadows (any three required to recover M)
Give three to Alice, one to Bob, two to Dave, and one each to Elvis and Fred
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

Слайд 7

Chapter 6  Other Security Building Blocks
Motivation for Blind Sig’s
Dave owns

a bank
Carol has an account at Dave’s bank
Carol wants to withdraw some digital money
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
Blind signatures allow Dave to create digital money that is both valid and anonymous

Слайд 8

Chapter 6  Other Security Building Blocks
Blind Signatures
Blind signatures enable a

user to digitally sign a document without seeing its contents
Assume Dave’s RSA public/private keys are:
Public: e = 413, n = 629
Private: d = 53
Before giving a message, m, to Dave for his signature, Carol can blind it
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

Слайд 9

Chapter 6  Other Security Building Blocks
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
If n is large, exhaustive search for b is unfeasible

Слайд 10

Chapter 6  Other Security Building Blocks
Blind Signatures (cont)
Dave signs 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

Слайд 11

Chapter 6  Other Security Building Blocks
Blind Signatures (cont)
Carol unblinds the

signed blinded message by multiplying 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!

Слайд 12

Chapter 6  Other Security Building Blocks
Properties of Blind Signatures
Validity –

as with normal digital signatures:
Anyone can use Dave’s public key to verify his signature on the document is valid
Dave’s signature still cannot be forged or moved to another document, and Dave cannot repudiate his signature
Unlinkability – unlike normal digital signatures:
Dave cannot subsequently link the unblinded signed document to the blind document that he signed

Слайд 13

Chapter 6  Other Security Building Blocks
Unlinkability of Blind Signatures
Suppose:
Carol gives

Dave two blinded documents to sign
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
Then:
Dave will not be able to determine which unblinded document corresponds to which blinded document

Слайд 14

Chapter 6  Other Security Building Blocks
Example of Unlinkability
Carol gives Dave

two blinded documents to sign
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
S1 = 217, S2 = 121
Dave can verify his signature and learn the contents of the documents he signed:
m1 = 217413 mod 629 = 200, m2 = 121413 mod 629 = 100
Dave cannot link an unblinded document to the corresponding blind document:
B1 = m1 and B2 = m2?
B1 = m2 and B2 = m1?

Слайд 15

Chapter 6  Other Security Building Blocks
Example of Unlinkability (cont)
To link

an unblinded document to the corresponding blind document
B1 (542) = m1 (200) and B2 (492) = m2 (100), or
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:
b1 = 409 since (100 × 409413) mod 629 = 542
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

Слайд 16

Chapter 6  Other Security Building Blocks
Motivation for Blind Signatures (cont)
Why

would Dave sign a blind document that he could not read and create an unlinkable signature?
Recall:
Dave owns a bank
Carol has an account at Dave’s bank
Carol wants to withdraw some digital money
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
Blind signatures allow Dave to create digital money that is both valid and anonymous

Слайд 17

Chapter 6  Other Security Building Blocks
Digital Money Without Blind Sig’s
Carol

creates a message containing a serial number and a value
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
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
Dave could keep a record each serial number and to whom it was issued
When a merchant redeems digital money Dave could determine to whom that money was issued

Слайд 18

Chapter 6  Other Security Building Blocks
Digital Money With Blind Signatures
Carol

creates a message containing a serial number and a value
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
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

Слайд 19

Chapter 6  Other Security Building Blocks
Digital Money With Blind Signatures

(cont)

Problem #1: double spending
Carol uses her digital money to pay one merchant
The merchant uses Dave’s public key to verify it is valid
Carol uses the same piece of digital money to pay another merchant
The merchant uses Dave’s public key to verify it is valid
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

Слайд 20

Chapter 6  Other Security Building Blocks
Digital Money With Blind Signatures

(cont)

Problem #2: fraud
Carol creates a message worth $1000
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
Dave signs the message and deducts $10 from Carol’s account
$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)

Слайд 21

Chapter 6  Other Security Building Blocks
Digital Money With Blind Signatures

(cont)

Dave requires Carol to create and submit 100 messages:
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)

Слайд 22

Chapter 6  Other Security Building Blocks
Digital Money With Blind Signatures

(cont)

Dave chooses 99 of the 100 messages at random to 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

Слайд 23

Chapter 6  Other Security Building Blocks
Digital Money With Blind Signatures

(cont)

For Carol to get $1,000 worth of digital money for $10 she would have to:
Create 99 messages containing the value $10
Create one message containing the value $1,000
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

Слайд 24

Chapter 6  Other Security Building Blocks
Motivation for Bit Commitment
Might want

to commit to a prediction without revealing it
Chuck and Bill’s virtual coin flips – Scenario #1
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
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

Слайд 25

Chapter 6  Other Security Building Blocks
Motivation for Bit Commitment (cont)
Chuck

and Bill’s virtual coin flips – Scenario #3
Chuck chooses a value, writes it on a piece of paper, seals it in an envelope, and hands the envelope to Bill
Bill announces his guess
Bill opens the envelope and both learn whether Bill was right
Good: neither can cheat
Fairness requirements:
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

Слайд 26

Chapter 6  Other Security Building Blocks
Bit Commitment
Bit commitment allows someone

to commit to a prediction without revealing it
Bit commitment has two phases:
Commitment phase: one party commits to a prediction in such a way that it cannot be subsequently changed
Verification phase: the second party learns the first party’s prediction
Cheating is impossible if:
The prediction cannot be changed after the commitment phase
The prediction is not revealed until the verification phase

Слайд 27

Chapter 6  Other Security Building Blocks
Bit Commitment Using a Symmetric-Key

Cryptosystem

Commitment phase:
Chuck chooses a random key, k, and encrypts his prediction
M = Encrypt(p,k)
Chuck gives a copy of M to Bill
Problem: easy for Chuck to change prediction by finding M such that:
Decrypt(M, k1) = 0, and
Decrypt(M, k2) = 1
Solution:
Bill send a random string of bits, R, to Chuck
Chuck concatenates his prediction to R and then encrypts:
M = Encrypt(“Rp”, k)

Слайд 28

Chapter 6  Other Security Building Blocks
Bit Commitment Using a Symmetric-Key

Cryptosystem

Commitment phase:
Bill send a random string of bits, R, to Chuck
Chuck concatenates his prediction to R and then encrypts:
M = Encrypt(“Rp”, k)
Chuck gives a copy of M to Bill
Verification phase:
Chuck sends k to Bill
Bill decrypts M, checks R, and learns p:
Decrypt (M, k)

Слайд 29

Chapter 6  Other Security Building Blocks
Bit Commitment Using a Symmetric-Key

Cryptosystem

Neither can cheat:
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
The prediction is not revealed until the verification phase
Bill does not know the key Chuck chose and connot read M without it

Слайд 30

Chapter 6  Other Security Building Blocks
Bit Commitment Using a One-Way

Hash Function

Commitment phase:
Chuck creates two random strings of bits, R1 and R2
Chuck concatenates R1, R2, and his prediction, p, and sends the result through the one-way hash function, H:
h = H(R1R2p)
Chuck sends h and R1 to Bill
Verification phase:
Chuck sends R2 and p to Bill
Bill computes the hash:
h’ = H(R1R2p)
Bill verifies that h’ = h

Слайд 31

Chapter 6  Other Security Building Blocks
Bit Commitment Using a One-Way

Hash Function

Neither can cheat:
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
The prediction is not revealed until the verification phase
Since the hash function is one-way, Bill cannot deduce p from h and R1

Слайд 32

Chapter 6  Other Security Building Blocks
Cryptographic Protocols
A protocol is an

agreed-upon sequence of actions performed by two or more principals
Cryptographic protocols make use of cryptography to accomplish some task securely
Example:
How can Alice and Bob agree on a session key to protect a conversation?
Answer: use a key-exchange cryptographic protocol

Слайд 33

Chapter 6  Other Security Building Blocks
Key Exchange with Symmetric Cryptography
Assume

Alice and Bob each share a key with a Key Distribution Center (KDC)
KA is the key shared by Alice and the KDC
KB is the key shared by Bob and the KDC
To agree on a session key:
Alice contacts the KDC and requests a session key for Bob and her
The KDC generates a random session key, encrypts it with both KA and KB, and sends the results to Alice

Слайд 34

Chapter 6  Other Security Building Blocks
Key Exchange with Symmetric Cryptography

(cont)

Agreeing on a session key (cont):
Alice decrypts the part of the message encrypted with KA and learns the session key
Alice sends the part of the message encrypted with KB to Bob
Bob receives Alice’s message, decrypts it, and learns the session key
Alice and Bob communicate securely using the session key

Слайд 35

Chapter 6  Other Security Building Blocks
Key Exchange with Symmetric Cryptography

(cont)

The key-exchange protocol:
A: => KDC (A,B);
KDC: => A (E(KAB,KA), E(KAB,KB));
A: => B (E(KAB,KB));

Слайд 36

Chapter 6  Other Security Building Blocks
Key Exchange with Symmetric Cryptography

(cont)

Issues:
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
The use of a new session key for each conversation limits the chances/value of compromising a session key

Слайд 37

Chapter 6  Other Security Building Blocks
Attacking the Protocol
Alice and Bob

set up a secure session protected by KAB
An 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

Слайд 38

Chapter 6  Other Security Building Blocks
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

Слайд 39

Chapter 6  Other Security Building Blocks
What Went Wrong?
Alice and Bob

need to be able to distinguish between a current (or fresh) response from the KDC and an old one
Solutions:
Alice and Bob could keep track of all previously-used session keys and never accept an old session key
KDC could include freshness information in its messages
Timestamps
Nonces

Слайд 40

Chapter 6  Other Security Building Blocks
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

Слайд 41

Chapter 6  Other Security Building Blocks
Using Nonces to Establish Freshness
A

nonce is a randomly-generated value that:
Is never reused
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));

Слайд 42

Chapter 6  Other Security Building Blocks
Key-Exchange with Public-Key Cryptography
Alice learns

Bob’s public key (by either asking 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

Слайд 43

Chapter 6  Other Security Building Blocks
Attacking the Protocol
Recall the man-in-the-middle

attack
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

Слайд 44

Chapter 6  Other Security Building Blocks
The Interlock Protocol
Combating the man-in-the-middle

attack:
Alice and Bob exchange public keys
Alice encrypts her message using Bob’s public key. Alice sends half the encrypted message to Bob (e.g. every other bit)
Bob encrypts his message using Alice’s public key. Bob sends half the encrypted message to Alice (e.g. every other bit)
Alice sends the other half of her encrypted message to Bob. Bob puts the two halves together and decrypts them using his private key
Bob sends the other half of his encrypted message to Alice. Alice puts the two halves together and decrypts them using her private key

Слайд 45

Chapter 6  Other Security Building Blocks
The Interlock Prot. (cont)
Foiling the

man-in-the-middle:
Assume Mallory can trick Alice into using MPublic instead 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

Слайд 46

Chapter 6  Other Security Building Blocks
Authentication
Authentication is the process of

proving your identity to someone else
One-way
Two-way
Authentication protocols are often designed using a challenge and response mechanism
Authenticator creates a random challenge
Authenticatee proves identity by replying with the appropriate response

Слайд 47

Chapter 6  Other Security Building Blocks
One-way Authentication Using Symmetric-Key Cryptography
Assume

that Alice and Bob share a secret symmetric key, KAB
One-way authentication protocol:
Alice creates a nonce, NA, and sends it to Bob as a challenge
Bob encrypts Alice’s nonce with their secret key and returns the result, Encrypt(NA, KAB), to Alice
Alice can decrypt Bob’s response and verify that the result is her nonce
A: => B(NA);
B: => A(Encrypt(NA, KAB));

Слайд 48

Chapter 6  Other Security Building Blocks
One-way Authentication Using Symmetric-Key Cryptography
Problem:

an adversary, Mallory, might be able to impersonate Bob to Alice:
Alice sends challenge to Bob (intercepted by Mallory)
Mallory does not know KAB and thus cannot create the appropriate response
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));

Слайд 49

Chapter 6  Other Security Building Blocks
One-way Authentication Using Public-Key Cryptography
Alice

sends a nonce to Bob as a challenge
Bob 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

Слайд 50

Chapter 6  Other Security Building Blocks
One-way Authentication Using Public-Key Cryptography
Another

challenge-and-response authentication protocol:
Alice performs a computation based on some random numbers (chosen by Alice) and her private key and sends the result to Bob
Bob sends Alice a random number (chosen by Bob)
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
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

Слайд 51

Chapter 6  Other Security Building Blocks
Authentication and Key-Exchange Protocols
Combine authentication

and key-exchange
Assume Carla and Diane are on opposite ends of a network and want to talk securely
Want to agree on a new session key securely
Want to each be sure that they are talking to the other and not an intruder
Wide-Mouth Frog
Assumes a trusted third-party, Sam, who shares a secret keys, KC and KD, respectively, with Carla and Diane

Слайд 52

Chapter 6  Other Security Building Blocks
Authentication and Key-Exchange Protocols
Wide-Mouth Frog

C: => S(C,Encrypt((D,KCD,TC),KCS));
S: => D(Encrypt((C, KCD, TS), KDS));
Observations:
Reliance on synchronized clocks to generate timestamps
Depends on a third-party that both participants trust
Initiator is trusted to generate good session keys

Слайд 53

Chapter 6  Other Security Building Blocks
Authentication and Key-Exchange Protocols
Yahalom
C =>

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

Слайд 54

Chapter 6  Other Security Building Blocks
Authentication and Key-Exchange Protocols
Denning and

Sacco (public-key)
Carla sends a message to Sam including her name and Diane’s name
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));
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));

Слайд 55

Chapter 6  Other Security Building Blocks
Authentication and Key-Exchange Protocols
A weakness

of the Denning and Sacco protocol
Harry can trick Diane into thinking that she is communicating with Carla when she is really communicating with Harry
Harry establishes a session key, KCH, with Carla
C: => H(Encrypt(Encrypt((KCH,TC),CPrivate),HPublic));
Harry decrypts Carla’s message and learns KCH
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));
Diane will decrypt the message, check the signature and timestamp, and believe that she is talking to Carla with KCH as the session key

Слайд 56

Chapter 6  Other Security Building Blocks
Authentication and Key-Exchange Protocols
Fixing the

Denning and Sacco protocol:
Add the other party’s name to the key exchange message:
C: => D(Encrypt(Encrypt((D,KCD,TC),CPrivate),DPublic));

Слайд 57

Chapter 6  Other Security Building Blocks
Motivation for Zero Knowledge Proofs
Many

challenge and response authentication protocols
Prove identity by demonstrating knowledge of a certain piece of information (e.g. a password)
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:
Requires Alice to disclose S to Bob
Bob may subsequently be able to impersonate Alice

Слайд 58

Chapter 6  Other Security Building Blocks
Zero-Knowledge Proofs
Alice can perform a

zero-knowledge proof so that:
Bob can verify that Alice knows the secret
Bob does not gain any information about the secret
Overview:
Bob will ask Alice a series of questions
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
If Alice answers many questions in row correctly chances are good that she knows the secret
None of the questions or answers give Bob any information about Alice’s secret

Слайд 59

Chapter 6  Other Security Building Blocks
Zero-Knowledge Proofs (cont)
Bob asks Alice

up to n questions
If Alice ever answers incorrectly, Bob stops and knows Alice does not know S
If Alice always answers correctly, she probably knows S
How many questions should Bob ask?
n = 1
Efficient but chance of getting fooled
Alice’s odds of guessing right once are 1 in 2
n = 10
Less efficient, less chance of getting fooled
Alice’s odds of guessing right ten times are 1 in 210 (~1,000)
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)

Слайд 60

Chapter 6  Other Security Building Blocks
The Zero-Knowledge Cave
A cave with

a single entrance
The entry passage forks into left and right passages
The two passages eventually meet each other
A door has been built where they join
The only way to open the door is to say the “magic words”

Слайд 61

Chapter 6  Other Security Building Blocks
The Zero-Knowledge Cave (cont)

Слайд 62

Chapter 6  Other Security Building Blocks
The Zero-Knowledge Cave (cont)
Alice can

prove to Bob that she knows the magic words
Alice need not reveal the magic words to Bob:
Alice and Bob stand at the entrance to the cave
Alice walks all the way into the cave until she is standing at the door
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
Bob chooses at random to ask Alice to come out of either the passage to Bob’s right or the one to his left
Alice exits from the appropriate passage (using the magic words if necessary)

Слайд 63

Chapter 6  Other Security Building Blocks
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

Слайд 64

Chapter 6  Other Security Building Blocks
The Zero-Knowledge Cave (cont)
No matter

how many times this protocol is run Bob learns 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

Слайд 65

Chapter 6  Other Security Building Blocks
Mathematical Background - Graph Isomorphism
A

graph is a set of verteces and the edges that connect them:
If two graphs are identical except for the names given to verteces they are called isomorphic

Слайд 66

Chapter 6  Other Security Building Blocks
Graph Isomorphism
Graphs (I) and (II)

are isomorphic:

(I)

(II)

I II
A G
B C
C H
D I
E E
F A
G D
H F
I B

Слайд 67

Chapter 6  Other Security Building Blocks
Graph Isomorphism (cont)
Graphs (II) and

(III) are isomorphic:
Are graphs (I) and (III) isomorphic?

II III
A I
B F
C B
D E
E D
F H
G C
H A
I G

Слайд 68

Chapter 6  Other Security Building Blocks
Graph Isomorphism (cont)
Graphs (I) and

(III) must be isomorphic because graph isomorphism is transitive
Can find the isomorphism by mapping from (I) to (II) to (III):

I II
A G
B C
C H
D I
E E
F A
G D
H F
I B

II III
A I
B F
C B
D E
E D
F H
G C
H A
I G

I III
A C
B B
C A
D G
E D
F I
G E
H H
I F

Слайд 69

Chapter 6  Other Security Building Blocks
Graph Isomorphism is a Hard

Problem

In general, determining whether two graphs are isomorphic is a difficult problem:
Best-known algorithm runs in time exponential to the number of verteces
As the number of verteces gets large, finding an answer is intractable
A claimed isomorphism between two graphs can be checked in polynomial time
As the number of verteces gets large, verifying an answer is tractable

Слайд 70

Chapter 6  Other Security Building Blocks
A Zero-Knowledge Proof Using Graph

Isomorphism

Alice creates two graphs, G1 and G2, which are isomorphic to each other:
Randomly create G1
Randomly permute the verteces of G1 to create G2
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

Слайд 71

Chapter 6  Other Security Building Blocks
Zero-Knowledge Proof Using Graph Isomorphism
Alice

randomly permutes G1 to produce another graph, H, which is isomorphic to both G1 and G2
Alice knows the isomorphism between G1 and G2
Alice knows the isomorphism between G1 and H
Alice knows the isomorphism between G2 and H (by transativity)
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

Слайд 72

Chapter 6  Other Security Building Blocks
Zero-Knowledge Proof Using Graph Isomorphism
Alice

and Bob repeat the following protocol until Bob is satisfied:
Alice randomly permutes G1 to produce another graph, H
Alice sends H to Bob
Bob asks Alice either to:
Prove that H and G1 are isomorphic, or
Prove that H and G2 are isomorphic
Alice complies (without providing the other isomorphism)
Bob verifies whether or not Alice’s answer is correct

Слайд 73

Chapter 6  Other Security Building Blocks
Zero-Knowledge Proof Using Graph Isomorphism
Without

knowing the isomorphism between G1 and G2 Alice cannot create a graph H for which she knows the isomorphism to both G1 and G2
Otherwise she would know the isomorphism between G1 and G2 by transitivity
In each round Alice’s must choose:
Permute G1 to produce a graph, H1, for which she knows the isomorphism to G1 (but not G2), or
Permute G2 to produce a graph, H2, for which she knows the isomorphism to G2 (but not G1)

Слайд 74

Chapter 6  Other Security Building Blocks
Zero-Knowledge Proof Using Graph Isomorphism
Alice

only sends one graph to Bob in each round
Four possibilities each round:
Alice sends H1 and Bob asks for (H1,G1): Alice will be able to answer
Alice sends H1 and Bob asks for (H1,G2): Alice will not be able to answer
Alice sends H2 and Bob asks for (H2,G1): Alice will not be able to answer
Alice sends H2 and Bob asks for (H2,G2): Alice will be able to answer
Results:
Alice has a 50% chance in each round of answering correctly whether or not she knows the isomorphism between G1 and G2
Each round Bob learns the isomorphism between a random graph and either G1 or G2

Слайд 75

Chapter 6  Other Security Building Blocks
Zero-Knowledge Proof Using Graph Isomorphism
If

Alice is able to answer correctly 20 times in a row:
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

Слайд 76

Chapter 6  Other Security Building Blocks
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)
Carol asks Alice to prove she knows the isomorphism
Alice generates a graph, H, and sends it to Carol
Carol contacts Bob and says she’s ready to start the proof; she sends H to Bob
Bob chooses either G1 or G2 and asks Carol for the isomorphism
Carol asks Alice the same question
Alice answers Carol
Carol repeats the answer to Bob
Results:
Carol will answer Bob correctly in every round
Bob will believe that Carol knows the isomorphism
Carol does not know the isomorphism

Overview. Beyond basic cryptography

Содержание

Chapter 6  Other Security Building Blocks Motivation for Secret SplittingA professor,

Chapter 6  Other Security Building Blocks Secret SplittingSecret splitting makes it

Chapter 6  Other Security Building Blocks Secret Splitting Using One-Time PadsM

Chapter 6  Other Security Building Blocks Secret Split. with One-Time PadsEncrypt

Chapter 6  Other Security Building Blocks Secret SharingSecret sharing (also called

Chapter 6  Other Security Building Blocks Motivation for Blind Sig’sDave owns

Chapter 6  Other Security Building Blocks Blind SignaturesBlind signatures enable a

Chapter 6  Other Security Building Blocks Blind Signatures (cont)Carol blinds the

Chapter 6  Other Security Building Blocks Blind Signatures (cont)Dave signs the

Chapter 6  Other Security Building Blocks Blind Signatures (cont)Carol unblinds the

Chapter 6  Other Security Building Blocks Properties of Blind SignaturesValidity –

Chapter 6  Other Security Building Blocks Unlinkability of Blind SignaturesSuppose:Carol gives

Chapter 6  Other Security Building Blocks Example of UnlinkabilityCarol gives Dave

Chapter 6  Other Security Building Blocks Example of Unlinkability (cont)To link

Chapter 6  Other Security Building Blocks Motivation for Blind Signatures (cont)Why

Chapter 6  Other Security Building Blocks Digital Money Without Blind Sig’sCarol

Chapter 6  Other Security Building Blocks Digital Money With Blind SignaturesCarol

Chapter 6  Other Security Building Blocks Digital Money With Blind Signatures

Chapter 6  Other Security Building Blocks Digital Money With Blind Signatures

Chapter 6  Other Security Building Blocks Digital Money With Blind Signatures

Chapter 6  Other Security Building Blocks Digital Money With Blind Signatures

Chapter 6  Other Security Building Blocks Digital Money With Blind Signatures

Chapter 6  Other Security Building Blocks Motivation for Bit CommitmentMight want

Chapter 6  Other Security Building Blocks Motivation for Bit Commitment (cont)Chuck

Chapter 6  Other Security Building Blocks Bit CommitmentBit commitment allows someone

Chapter 6  Other Security Building Blocks Bit Commitment Using a Symmetric-Key

Chapter 6  Other Security Building Blocks Bit Commitment Using a Symmetric-Key

Chapter 6  Other Security Building Blocks Bit Commitment Using a Symmetric-Key

Chapter 6  Other Security Building Blocks Bit Commitment Using a One-Way

Chapter 6  Other Security Building Blocks Bit Commitment Using a One-Way

Chapter 6  Other Security Building Blocks Cryptographic ProtocolsA protocol is an

Chapter 6  Other Security Building Blocks Key Exchange with Symmetric CryptographyAssume

Chapter 6  Other Security Building Blocks Key Exchange with Symmetric Cryptography

Chapter 6  Other Security Building Blocks Key Exchange with Symmetric Cryptography

Chapter 6  Other Security Building Blocks Key Exchange with Symmetric Cryptography

Chapter 6  Other Security Building Blocks Attacking the ProtocolAlice and Bob

Chapter 6  Other Security Building Blocks Attacking the Protocol (cont)A: =>

Chapter 6  Other Security Building Blocks What Went Wrong?Alice and Bob

Chapter 6  Other Security Building Blocks Using Timestamps to Establish FreshnessA:

Chapter 6  Other Security Building Blocks Using Nonces to Establish FreshnessA

Chapter 6  Other Security Building Blocks Key-Exchange with Public-Key CryptographyAlice learns

Chapter 6  Other Security Building Blocks Attacking the ProtocolRecall the man-in-the-middle

Chapter 6  Other Security Building Blocks The Interlock ProtocolCombating the man-in-the-middle

Chapter 6  Other Security Building Blocks The Interlock Prot. (cont)Foiling the

Chapter 6  Other Security Building Blocks AuthenticationAuthentication is the process of

Chapter 6  Other Security Building Blocks One-way Authentication Using Symmetric-Key CryptographyAssume

Chapter 6  Other Security Building Blocks One-way Authentication Using Symmetric-Key CryptographyProblem:

Chapter 6  Other Security Building Blocks One-way Authentication Using Public-Key CryptographyAlice

Chapter 6  Other Security Building Blocks One-way Authentication Using Public-Key CryptographyAnother

Chapter 6  Other Security Building Blocks Authentication and Key-Exchange ProtocolsCombine authentication

Chapter 6  Other Security Building Blocks Authentication and Key-Exchange ProtocolsWide-Mouth Frog

Chapter 6  Other Security Building Blocks Authentication and Key-Exchange ProtocolsYahalom C =>

Chapter 6  Other Security Building Blocks Authentication and Key-Exchange ProtocolsDenning and

Chapter 6  Other Security Building Blocks Authentication and Key-Exchange ProtocolsA weakness

Chapter 6  Other Security Building Blocks Authentication and Key-Exchange ProtocolsFixing the

Chapter 6  Other Security Building Blocks Motivation for Zero Knowledge ProofsMany

Chapter 6  Other Security Building Blocks Zero-Knowledge ProofsAlice can perform a

Chapter 6  Other Security Building Blocks Zero-Knowledge Proofs (cont)Bob asks Alice

Chapter 6  Other Security Building Blocks The Zero-Knowledge CaveA cave with

Chapter 6  Other Security Building Blocks The Zero-Knowledge Cave (cont)

Chapter 6  Other Security Building Blocks The Zero-Knowledge Cave (cont)Alice can

Chapter 6  Other Security Building Blocks The Zero-Knowledge CaveThere are four

Chapter 6  Other Security Building Blocks The Zero-Knowledge Cave (cont)No matter

Chapter 6  Other Security Building Blocks Mathematical Background - Graph IsomorphismA

Chapter 6  Other Security Building Blocks Graph IsomorphismGraphs (I) and (II)

Chapter 6  Other Security Building Blocks Graph Isomorphism (cont)Graphs (II) and

Chapter 6  Other Security Building Blocks Graph Isomorphism (cont)Graphs (I) and

Chapter 6  Other Security Building Blocks Graph Isomorphism is a Hard

Chapter 6  Other Security Building Blocks A Zero-Knowledge Proof Using Graph

Chapter 6  Other Security Building Blocks Zero-Knowledge Proof Using Graph IsomorphismAlice

Chapter 6  Other Security Building Blocks Zero-Knowledge Proof Using Graph IsomorphismAlice

Chapter 6  Other Security Building Blocks Zero-Knowledge Proof Using Graph IsomorphismWithout

Chapter 6  Other Security Building Blocks Zero-Knowledge Proof Using Graph IsomorphismAlice

Chapter 6  Other Security Building Blocks Zero-Knowledge Proof Using Graph IsomorphismIf

Chapter 6  Other Security Building Blocks
Motivation for Secret Splitting
A professor,

Chapter 6  Other Security Building Blocks
Secret Splitting
Secret splitting makes it

Chapter 6  Other Security Building Blocks
Secret Splitting Using One-Time Pads
M

Chapter 6  Other Security Building Blocks
Secret Split. with One-Time Pads
Encrypt

Chapter 6  Other Security Building Blocks
Secret Sharing
Secret sharing (also called

Chapter 6  Other Security Building Blocks
Motivation for Blind Sig’s
Dave owns

Chapter 6  Other Security Building Blocks
Blind Signatures
Blind signatures enable a

Chapter 6  Other Security Building Blocks
Blind Signatures (cont)
Carol blinds the

Chapter 6  Other Security Building Blocks
Blind Signatures (cont)
Dave signs the

Chapter 6  Other Security Building Blocks
Blind Signatures (cont)
Carol unblinds the

Chapter 6  Other Security Building Blocks
Properties of Blind Signatures
Validity –

Chapter 6  Other Security Building Blocks
Unlinkability of Blind Signatures
Suppose:
Carol gives

Chapter 6  Other Security Building Blocks
Example of Unlinkability
Carol gives Dave

Chapter 6  Other Security Building Blocks
Example of Unlinkability (cont)
To link

Chapter 6  Other Security Building Blocks
Motivation for Blind Signatures (cont)
Why

Chapter 6  Other Security Building Blocks
Digital Money Without Blind Sig’s
Carol

Chapter 6  Other Security Building Blocks
Digital Money With Blind Signatures
Carol

Chapter 6  Other Security Building Blocks
Digital Money With Blind Signatures

Chapter 6  Other Security Building Blocks
Digital Money With Blind Signatures

Chapter 6  Other Security Building Blocks
Digital Money With Blind Signatures

Chapter 6  Other Security Building Blocks
Digital Money With Blind Signatures

Chapter 6  Other Security Building Blocks
Digital Money With Blind Signatures

Chapter 6  Other Security Building Blocks
Motivation for Bit Commitment
Might want

Chapter 6  Other Security Building Blocks
Motivation for Bit Commitment (cont)
Chuck

Chapter 6  Other Security Building Blocks
Bit Commitment
Bit commitment allows someone

Chapter 6  Other Security Building Blocks
Bit Commitment Using a Symmetric-Key

Chapter 6  Other Security Building Blocks
Bit Commitment Using a Symmetric-Key

Chapter 6  Other Security Building Blocks
Bit Commitment Using a Symmetric-Key

Chapter 6  Other Security Building Blocks
Bit Commitment Using a One-Way

Chapter 6  Other Security Building Blocks
Bit Commitment Using a One-Way

Chapter 6  Other Security Building Blocks
Cryptographic Protocols
A protocol is an

Chapter 6  Other Security Building Blocks
Key Exchange with Symmetric Cryptography
Assume

Chapter 6  Other Security Building Blocks
Key Exchange with Symmetric Cryptography

Chapter 6  Other Security Building Blocks
Key Exchange with Symmetric Cryptography

Chapter 6  Other Security Building Blocks
Key Exchange with Symmetric Cryptography

Chapter 6  Other Security Building Blocks
Attacking the Protocol
Alice and Bob

Chapter 6  Other Security Building Blocks
Attacking the Protocol (cont)
A: =>

Chapter 6  Other Security Building Blocks
What Went Wrong?
Alice and Bob

Chapter 6  Other Security Building Blocks
Using Timestamps to Establish Freshness
A:

Chapter 6  Other Security Building Blocks
Using Nonces to Establish Freshness
A

Chapter 6  Other Security Building Blocks
Key-Exchange with Public-Key Cryptography
Alice learns

Chapter 6  Other Security Building Blocks
Attacking the Protocol
Recall the man-in-the-middle

Chapter 6  Other Security Building Blocks
The Interlock Protocol
Combating the man-in-the-middle

Chapter 6  Other Security Building Blocks
The Interlock Prot. (cont)
Foiling the

Chapter 6  Other Security Building Blocks
Authentication
Authentication is the process of

Chapter 6  Other Security Building Blocks
One-way Authentication Using Symmetric-Key Cryptography
Assume

Chapter 6  Other Security Building Blocks
One-way Authentication Using Symmetric-Key Cryptography
Problem:

Chapter 6  Other Security Building Blocks
One-way Authentication Using Public-Key Cryptography
Alice

Chapter 6  Other Security Building Blocks
One-way Authentication Using Public-Key Cryptography
Another

Chapter 6  Other Security Building Blocks
Authentication and Key-Exchange Protocols
Combine authentication

Chapter 6  Other Security Building Blocks
Authentication and Key-Exchange Protocols
Wide-Mouth Frog

Chapter 6  Other Security Building Blocks
Authentication and Key-Exchange Protocols
Yahalom
C =>

Chapter 6  Other Security Building Blocks
Authentication and Key-Exchange Protocols
Denning and

Chapter 6  Other Security Building Blocks
Authentication and Key-Exchange Protocols
A weakness

Chapter 6  Other Security Building Blocks
Authentication and Key-Exchange Protocols
Fixing the

Chapter 6  Other Security Building Blocks
Motivation for Zero Knowledge Proofs
Many

Chapter 6  Other Security Building Blocks
Zero-Knowledge Proofs
Alice can perform a

Chapter 6  Other Security Building Blocks
Zero-Knowledge Proofs (cont)
Bob asks Alice

Chapter 6  Other Security Building Blocks
The Zero-Knowledge Cave
A cave with

Chapter 6  Other Security Building Blocks
The Zero-Knowledge Cave (cont)

Chapter 6  Other Security Building Blocks
The Zero-Knowledge Cave (cont)
Alice can

Chapter 6  Other Security Building Blocks
The Zero-Knowledge Cave
There are four

Chapter 6  Other Security Building Blocks
The Zero-Knowledge Cave (cont)
No matter

Chapter 6  Other Security Building Blocks
Mathematical Background - Graph Isomorphism
A

Chapter 6  Other Security Building Blocks
Graph Isomorphism
Graphs (I) and (II)

Chapter 6  Other Security Building Blocks
Graph Isomorphism (cont)
Graphs (II) and

Chapter 6  Other Security Building Blocks
Graph Isomorphism (cont)
Graphs (I) and

Chapter 6  Other Security Building Blocks
Graph Isomorphism is a Hard

Chapter 6  Other Security Building Blocks
A Zero-Knowledge Proof Using Graph

Chapter 6  Other Security Building Blocks
Zero-Knowledge Proof Using Graph Isomorphism
Alice

Chapter 6  Other Security Building Blocks
Zero-Knowledge Proof Using Graph Isomorphism
Alice

Chapter 6  Other Security Building Blocks
Zero-Knowledge Proof Using Graph Isomorphism
Without

Chapter 6  Other Security Building Blocks
Zero-Knowledge Proof Using Graph Isomorphism
Alice

Chapter 6  Other Security Building Blocks
Zero-Knowledge Proof Using Graph Isomorphism
If