Shamir Secret SharingZero-Knowledge ProtocolsAuthenticationFirewallsCS 161: Computer SecurityMidterm 1 ReviewPart 2October 4, 2006Marco Barreno CS 161, Fall 2006 Midterm 1 Review, Part 2 1/17Shamir Secret SharingMarco Barreno CS 161, Fall 2006 Midterm 1 Review, Part 2 2/17Sharing a secret◮Let’s say we want to hide a secret with t people such thatany q of them can reconstruct the secret but any q − 1cannot◮We can use a polynomial with random coefficients:f(x) = xq+ aq−1xq−1+ · · · + a1x + a0(modp)◮The secret is f(0) = a0, and the shares we distribute aref(1), f(2), ..., f(t) (the other coefficients are also keptsecret)◮Now any q people can solve the polynomial for a0but q − 1have no information◮Note: Could do something similar with real numbers, butintegers are easier so we use modular arithmeticMarco Barreno CS 161, Fall 2006 Midterm 1 Review, Part 2 3/17Secret sharing: simple example◮Let q = 3 and p = 11 (don’t confuse with the p, q of RSA):f(x) = x3+ a2x2+ a1x + a0(mod11)◮Let’s say the secret we want to hide is “5”, and werandomly choose coefficients a2= 3 and a1= 9◮For t = 6, we compute f(1) = 7, f(2) = 10, f(3) = 9,f(4) = 10, f(5) = 8, and f(6) = 9.◮Any three can now solve for coefficients:f(2) = 10 = 8 + 4a2+ 2a1+ a0(mod11)f(3) = 9 = 5 + 9a2+ 3a1+ a0(mod11)f(6) = 9 = 7 + 3a2+ 6a1+ a0(mod11)Marco Barreno CS 161, Fall 2006 Midterm 1 Review, Part 2 4/17Zero-Knowledge ProtocolsMarco Barreno CS 161, Fall 2006 Midterm 1 Review, Part 2 5/17Zero-knowledge proof of identity◮Goal 1: Alice knows that the person she’s talking to is Bob.◮Goal 2: Bob reveals no additional information to Alice.◮Assumptions:◮Alice knows Bob’s public key◮Taking square roots modulo n is "hard"◮Protocol (everything mod pq):◮Bob picks secret b, publishes b2as public key (persistent)◮Alice wants to check Bob’s identity, asks Bob to begin◮Bob picks random r (new each run), sends "commitment"r2to Alice◮Alice flips coin (or chooses); heads means reveal r (Aliceverifies r2), tails means reveal rb (Alice verifies r2b2)◮If Bob passes, Alice is 50% convinced of his identity◮Repeat arbitrarily many timesMarco Barreno CS 161, Fall 2006 Midterm 1 Review, Part 2 6/17How can Mallory pretend to be Bob?◮Doesn’t know b (because he can’t factor), but can gamethe system◮To know the "heads" answer, picks r like Bob would◮When Alice sends "heads", he sends r◮If Alice sends "tails", what can he do? nothing!◮To know the "tails" answer, picks t and computesr2= t2/b2to send to Alice◮When Alice sends "tails", he sends t◮Alice thinks he sent rb and checks by squaring it, but(rb)2= r2b2= (t2/b2)b2= t2so fake Bob has fooled Aliceon tails◮If Alice sends "heads", he can’t do anything because hedidn’t pick r and then square it, he just picked somethingthat he called r2, but he can’t take the square rootMarco Barreno CS 161, Fall 2006 Midterm 1 Review, Part 2 7/17Why doesn’t the protocol leak information to Alice?◮When she flips "heads", Bob just reveals a randomnumber, which Alice could have picked by herself◮When she flips "tails", Bob sends her rb, but this is alsorandom because multiplication induces a permutation, so arandom number times anything lands on a random valueMarco Barreno CS 161, Fall 2006 Midterm 1 Review, Part 2 8/17AuthenticationMarco Barreno CS 161, Fall 2006 Midterm 1 Review, Part 2 9/17Authentication◮Authentication is verifying an identity, or verifying theoriginator of a message◮Many types of authentication◮Person → person◮Person → local computer◮Remote computer → person◮etc.◮Difficult to get right and easy to screw up◮Most real attacks today are authentication attacks:phishing, “pretexting”, spyware password pop-ups, etc.Marco Barreno CS 161, Fall 2006 Midterm 1 Review, Part 2 10/17Needham-Schroeder◮Symmetric encryption with trusted server◮Each user shares symmetric key with server (A shares keya, B shares key b, etc.)◮A → S: {B}a◮S → A: {t, {A, t}b}a◮A → B: {A, t}b◮A ↔ B: { messages...}tMarco Barreno CS 161, Fall 2006 Midterm 1 Review, Part 2 11/17Problem and fix◮Replay attack:◮M → B: {A, t}b◮M → B: { something that shouldn’t be repeated }t◮Solution: nonces (unique value, such as a random numberor timestamp)◮Revised N-S: every message has timestamp, so attackercan’t replay◮Problems remain: requires real-time trusted third partyMarco Barreno CS 161, Fall 2006 Midterm 1 Review, Part 2 12/17FirewallsMarco Barreno CS 161, Fall 2006 Midterm 1 Review, Part 2 13/17Firewall overview◮Motivation: Every network service is a potential hole◮Block services in the network before they reach machines◮Enforces security policy: policy on which services shouldbe visible, which should be blocked, and how wedistinguish insiders from outsiders◮Default allow vs. default deny◮Default allow is easier on users and bothers them less◮Default deny is more secure in several ways: fails safe,catches unknown attacks, hedges against commonmistakesMarco Barreno CS 161, Fall 2006 Midterm 1 Review, Part 2 14/17Packet filters◮Checks each packet against series of rules◮Rules test IP, protocol, port, etc. to decide drop or allow◮The first matching rule decides the action◮Syntax: hactioni hprotoi haddri → haddri◮Each haddri is of the form hipi:hporti[/{in,out}]◮The * wildcard matches any value◮(in/out difference is which interface packet received on)Marco Barreno CS 161, Fall 2006 Midterm 1 Review, Part 2 15/17Firewall example◮allow tcp*:*/out → 1.2.3.4:25/in◮allow tcp*:*/in →*:*/out◮allow tcp*:*/out →*:*/in (if ACK is set)◮drop* *:*→*:*Marco Barreno CS 161, Fall 2006 Midterm 1 Review, Part 2 16/17More on firewalls◮Reference monitor◮Mediates all access to network◮Three requirements: Always invoked, tamper resistant,verifiable◮Application-level firewall can do more than packet filter◮Inspect and enforce application protocols◮Do more nuanced filtering◮Stateful firewall can do more◮Assemble TCP connections (not just look for ACK)◮Limit number of open requests, etc.◮VPNs extend perimeter over secure channel to remotemachine◮Good for working from home, bad if home computer getsvirusMarco Barreno CS 161, Fall 2006 Midterm 1 Review, Part 2
View Full Document
Unlocking...