Upgrade to Pro — share decks privately, control downloads, hide ads and more …

New Cryptography

New Cryptography

George Tankersley, Filippo Valsorda (with Jack Grigg, Ben Kreuter)

Cryptography is usually associated with encrypting and signing messages, but since the 1990s, the field developed new tools that bring completely new capabilities: from PAKE protocols that make bruteforcing passwords impossible, to zero-knowledge proofs enabling blind credentials. This talk will take a look at all those things modern cryptography can do beyond the old encryption and signatures.

HOPE XII
July 20, 2018

George Tankersley

July 20, 2018
Tweet

More Decks by George Tankersley

Other Decks in Technology

Transcript

  1. New Cryptography: The Most Dangerous Game George Tankersley (@gtank__) Filippo

    Valsorda (@FiloSottile) https://hivemill.com/collections/smbc/products/smbc-the-most-dangerous-game-shirt
  2. Crypto 2.0 Builds on Crypto 1.0 (Berry Schoenmakers). If Crypto

    1.0 defends against outside attackers, 2.0 defends against malicious insiders. Much weirder. Mostly much newer. Not necessarily safe yet.
  3. Diffie-Hellman refresher Client Server pick x pick y gx mod

    p —→ ←— gy mod p use gxy mod p use gyx mod p
  4. Example of PAKE: EKE2 Client Server pick x pick y

    Encrypt password (gx mod p) —→ ←— Encrypt password (gy mod p) use gxy mod p use gyx mod p Can’t bruteforce Encrypt password (gx mod p)! (Requires special g and p.)
  5. PAKE Agree on a key when both sides share a

    password. No bruteforce opportunity for an attacker. Can use weak passwords! Examples: • Magic Wormhole • Pond • WPA3 Many types, use SPAKE2-EE.
  6. Blind Signatures (RSA) Public (N, e) and private d N

    = p*q and d = 1/e mod (N) Generate a signature S by S = Md mod N Verify it by checking that Se == M mod N (Md)e = M(1/e)*e = M1 = M mod N
  7. Blind Signatures (RSA) Public (N, e) and private d N

    = p*q and d = 1/e mod (N) Generate a signature S by S = Md mod N Verify it by checking that Se == M mod N (Md)e = M(1/e)*e = M1 = M mod N N is the modulus, product of two primes,
  8. Blind Signatures (RSA) Public (N, e) and private d N

    = p*q and d = 1/e mod (N) Generate a signature S by S = Md mod N Verify it by checking that Se == M mod N (Md)e = M(1/e)*e = M1 = M mod N N is the modulus, product of two primes,
  9. Blind Signatures (RSA) Public (N, e) and private d N

    = p*q and d = 1/e mod (N) Generate a signature S by S = Md mod N Verify it by checking that Se == M mod N (Md)e = M(1/e)*e = M1 = M mod N N is the modulus, product of two primes, e is the public exponent, d is its inverse,
  10. Blind Signatures (RSA) Public (N, e) and private d N

    = p*q and d = 1/e mod (N) Generate a signature S by S = Md mod N Verify it by checking that Se == M mod N (Md)e = M(1/e)*e = M1 = M mod N N is the modulus, product of two primes, e is the public exponent, d is its inverse,
  11. Blind Signatures (RSA) Public (N, e) and private d N

    = p*q and d = 1/e mod (N) Generate a signature S by S = Md mod N Verify it by checking that Se == M mod N (Md)e = M(1/e)*e = M1 = M mod N N is the modulus, product of two primes, e is the public exponent, d is its inverse, is magic, do not let it sense fear
  12. Blind Signatures (RSA) M is (~handwave~) just a number! The

    signatures still work if you do number things to it. So we’ll blind a signature by multiplying it with another big random number, so the signer never sees the real message. Generate a blinding factor re Blind the message: M blind = (re)M mod N S blind = (M blind )d mod N
  13. How can that possibly work? Generate a blinding factor re

    Blind the message: M blind = (re)M mod N S blind = (M blind )d mod N r also has an inverse, 1/r To unblind a signature: S = (S blind ) * (1/r) mod N = (M blind )d * (1/r) = (reM)d * (1/r) = (M)d(re)d * (1/r) = Md * red * (1/r) = Md mod N
  14. How can that possibly work? The signer has only ever

    seen Mr But we have a valid, unblind S! To unblind a signature: S = (S blind ) * (1/r) mod N = (M blind )d * (1/r) = (reM)d * (1/r) = (M)d(re)d * (1/r) = Md * red * (1/r) = Md mod N
  15. Why? Blind signatures allow you to receive tokens from an

    issuer and redeem them later without revealing who you are. The blind and unblind messages are unlinkable. This enables
  16. Zero-knowledge proofs must have: • Completeness ◦ If the prover

    is telling the truth, they will eventually convince the verifier. • Soundness ◦ A prover can only convince a verifier if they are actually telling the truth. • Zero-knowledgeness (yes, I know) ◦ Verifier doesn’t learn anything about the prover’s information. [Goldwasser, Micali, Rackoff 1985]
  17. Writing Circuits a 0 := boolean value a 1 :=

    boolean value … a 6 := boolean value a 7 := boolean value a 0 * (1 - a 0 ) = 0 a 1 * (1 - a 1 ) = 0 … a 6 * (1 - a 6 ) = 0 a 7 * (1 - a 7 ) = 0 a := byte value 1 * (20 a 0 + 21 a 1 + … + 26 a 7 + 27 a 7 - a) = 0 Now constrain those numbers to satisfy other equations, like elliptic curves or SHA-256
  18. Implementations! • Proving systems ◦ libsnark - C++ ◦ bellman

    - Rust • Medium-level libraries / DSLs ◦ jsnark - Java ◦ Snarky - OCaml ◦ ZoKrates - Ethereum Papers, links, examples: https://zkp.science
  19. ZKP Hide the information you are proving MPC Run complex

    computations on information you don’t know
  20. Defining Security Real Protocol A B C Ideal World A'

    B' C' Security: {A, B, C} indistinguishable from {A', B', C'}
  21. Defining Security A' B' C' Sim Secure if Sim can

    produce output with the same distribution as the original party A (resp. B, C)
  22. Strategy • First create protocol that protects privacy as long

    as all parties send valid (as prescribed by the protocol) messages at each step. • Then add logic to enforce sending valid messages. − Use ZK proofs to preserve privacy and force honest behavior
  23. Input Sharing • Alice chooses random r_i, r_j, … for

    each of her input bits and sends these to Bob. Alice keeps a_i XOR r_i as her shares. • Bob chooses random s_i, s_j, … for his bits and sends (b_i+s_i), … to Alice, keeping s_i as his shares. • Note that XORing shares gives true wire values!
  24. Computing an AND with OT • For two inputs a

    and b, Alice has (a+r) and (b+s), and Bob has r and s. • Bob can select w and keep ouput share rs+w; he can compute four possible: (a+r)s + (b+s)r + w = as+rs+br+rs+w = as+br+w • Alice can compute: (a+r)(b+s) = ab+as+br+rs = ab+(as+br)+rs • So Alice just needs to learn as+br+w to compute a share of the output, ab+rs+w
  25. Computing an AND with OT • Bob computes as+br+w but

    there are four possibilities – only Alice knows which is the right one • Alice should not learn any of the other possibilities • So use a 1-of-4 OT!
  26. Computing an AND with OT • Bob will keep rs+w

    as his share; Alice will get as+br+w and will compute her new share • We have XOR shares of the output – so we can use this as the input for another AND gate!
  27. Building a Circuit • Use this process to connect lots

    of ANDs • XORs can just be computed locally, no interactions needed (just XOR the shares) • Any circuit can be expressed with just ANDs and XORs
  28. More than Two Parties • Send XOR shares of each

    input bit to each other party • Act as OT sender for parties with smaller ID, OT receiver for parties with larger ID. • Still uses 1-of-4 OT • XOR all received share “pieces” to get output wire shares.
  29. Putting it all Together • This is the GMW protocol

    • Only one party needs to be honest for security to be maintained − If more than half are honest, small adaptation allows computation can be completed even if some parties drop out • Not very practical – only proves that a protocol exists for any function
  30. Remember We are cryptographers, not your cryptographers! George Tankersley (@gtank__)

    Filippo Valsorda (@FiloSottile) Benjamin Kreuter Jack Grigg (@str4d)