Call Now: (800) 537-1660
 Home    Why?     Free Solver   Testimonials    FAQs    Product    Contact

May 18th

May 18th

# Zero-knowledge Proofs and Authentication

## Review

• Secret-sharing
– How does a (n,t) threshold secret sharing scheme work?
Zero -knowledge proof

## How to prove knowledge of square root (I)

• Finding square root mod N=pq is as hard as factoring
• A knows b s.t. b^2 =y mod pq, & wishes to prove to B
that she knows such b.
• A → B: s =: r^2 mod pq (A picks random r)
• B flips coin
• B → A: coin flip
–A → B: t =: r mod pq
– B verifies t^2 ≡ s mod pq
• If tails
–A → B: t =: rb mod pq
– B verifies t^2 ≡ sy mod pq
• What if A didn’t know the square root?
• What did B learn after the proof?

## How to prove knowledge of square root (II)

• What if A could predict B ’s coin flip?
• What if A reuses random number r in different
rounds?
• How is B convinced that A does know the square
root?
– Knowledge extractor
• Why is B not learning anything about the square
root?
– Simulator argument (out of scope)

• Hw1 statistics:
Mean: 34.6
Standard deviation: 10.8
1st quartile: 29.0
2nd quartile (median): 34.0
3rd quartile: 44.0
Maximum: 54.0

## Authentication

• Alice and Bob love each other, but they live far apart
• We’ve learned how they can encrypt their messages
• How can they make sure they are talking to each other?
• This is the question of authentication

## Types of authentication

• End user → End user (Alice & Bob)
• End user → Local computer (login)
• End user → Remote computer (web site login )
• Computer → Computer (DRM)
• Local computer → End user (fake ATM check)
• Remote computer → End user (phishing check)

## Basic Security Protocols

• Entity authentication protocols
– Prove identity to each other
• Key establishment/agreement/ distribution protocols
– Establish a trusted session key between two principals
– Usually used to set up trusted communication channel
providing secrecy and authenticity
• Other protocols: secure e-commerce, e-voting, time
synchronization, etc.
• We use our basic crypto graphic primitives to design
higher-level security properties

## Protocol De sign Basics

• Protocols involve principals, e.g., hosts, users, services,
processes
• Secret information, e.g., symmetric keys, private keys
• Authentic information, e.g., public keys
• Basic cryptographic primitives: public-key crypto, block cipher,
stream cipher, hash function, MAC, digital signatures , zeroknowledge
proofs
• Trusted entities
• Proofs of freshness, e.g., nonces and timestamps
– NONCE = Number used only ONCE
– Two types of nonces
» Counter: unique (non-repeating) but predictable, may use a time stamp for
this purpose
» Random number: unique and unpredictable

## “Ideal” Protocol Wish List

• Efficient protocol
• As little trust as necessary
• As few as sumptions as necessary
– Idealized encryption???
– Synchronized clocks?
– Synchronized sequence numbers?
– Randomly selected nonces and IVs?
– Security of crypto primitives?
– Authenticity or secrecy of keys?
• Little client/server state

## Protocol Analysis

• Analyze high level security properties
– Secrecy
– Authentication
– Atomicity
– Non-repudiation
• Assume cryptographic primitives secure
– Signature: secure against existential forgery
– Public key/Private key encryption:
• Security protocols are notoriously hard to get right

## Active Attacker

• An active attacker may
– Eavesdrop on previous protocol runs, even
on protocol runs by other principals, replay
messages at a later time
– Inject messages into the network, e.g.,
fabricated from pieces of previous messages
– Alter or delete a principal’s messages
– Initiate multiple parallel protocol sessions
– Run dictionary attack on passwords
– Run exhaustive attack on low-entropy nonce

## Intruder Model

Intruder can
Intercept , drop, generate messages, full control of network
• Collude with malicious parties

## Example: Needham-Schroeder Protocol

• KS , KC are public keys of S and C respectively
• Goal:
– Mutual authentication: C→S, S→C
– Shared secret: Nc , Ns

## F law in Needham -Schroeder

Flaw (discovered 18 years after publication):
• Authentication: C→E, S→C
• Secrecy: E knows Nc , Ns
• How to fix it?
– The second message should be

 Prev Next

Home    Why Algebra Buster?    Guarantee    Testimonials    Ordering    FAQ    About Us
What's new?    Resources    Animated demo    Algebra lessons    Bibliography of     textbooks