1 of 18

Secret Key Recovery

Allison, Michael, and Yuwen

Secret Key Recovery

2 of 18

Privacy = Secret keys

  • Secret keys are central to security in any setting
  • What happens if…
    • You lose the secret key associated with your public key in a PKI?
    • You lose the secret key associated with a messaging service (like Signal)?

​

  • You lose all your data (if it’s not backed up)
  • You lose all your friends
  • Your friends lose all trust in you
    • Identities must be re-verified by meeting up with them in person

​

2

Secret Key Recovery

3 of 18

Why it’s hard

  • Your secret key is essentially your cryptographic identity.

​

  • Problem: How do you verify your identity without a keypair?
  • Answer: A password.
    • Future work: Security questions / biometric authentication.

​

  • Problem: A single server can’t hold the password
  • Solution: Shard the secret key / password among multiple servers and use MPC to recover the key.

3

Secret Key Recovery

4 of 18

Threat Model

  • Alice shards her key into N shares.
  • No more than N-1 semi-honest servers can collude.
  • DOS attacks are not possible.
  • Guarantee: Alice can recover her secret key
    • An attacker who doesn’t know Alice’s password can’t recover her key

4

Secret Key Recovery

5 of 18

Protocol Overview: Registration

5

P*: iloveice!11!

ilovei

ce!11!

<SK1>, <P*1>

<SK2>, <P*2>

SK:

Secret Key Recovery

6 of 18

Protocol Overview: Recovery

Step 1: Guess password

6

P: iloveice!11!

ilovei

ce!11!

<P1>

<P2>

ce!11!

ilovei

Secret Key Recovery

7 of 18

Protocol Overview: Recovery

Step 2: Receive back MPC result and add locally

7

ilovei

ce!11!

ce!11!

ilovei

MPC Computation

Secret Key Recovery

8 of 18

Protocol Overview: Recovery

What if the password guess is incorrect?

8

ilovei

ce!11!

ce!!!!!

ilovei

MPC Computation

Secret Key Recovery

9 of 18

MPC (SPDZ) Review

Parties hold additive secret shares of inputs and can compute an arithmetic circuit together without revealing their shares

​

​

9

x1, y1

x2, y2

x1 + y1

x2 + y2

C x1

C x2

x + y

Cx

  • Addition and Scalar Multiplication: Compute locally and combine
  • Multiplication: Requires one secret-shared beaver triple per multiplication

Secret Key Recovery

10 of 18

Beaver Triples

  • (a, b, c) where a·b=c
  • Each party receives shares of a, b, c
  • Independent of parties’ inputs → can be generated separately
    • SPDZ: triples are generated by the parties in an offline preprocessing phase

10

Secret Key Recovery

11 of 18

Beaver Triple Server

  • Continuously generates and stores (a, b, c) where a·b=c
  • Shares of beaver triples are sent to servers that store key and passwords shards when they need to perform a MPC multiplication

​

11

  • Security concerns:
    • Beaver triple server provides wrong shares of triple: considered DOS which we assume does not happen
    • MITM attack when sending beaver triple shares: use TLS
    • Colluding: key-storing server who learns a whole beaver triple can learn entire inputs

Secret Key Recovery

12 of 18

Beaver Triple Server

12

a ← GF(p)

b ← GF(p)

c = a · b

(a1, b1, c1)

(a2, b2, c2)

ilovei

ce!11!

ce!11!

ilovei

MPC

Computation

Secret Key Recovery

13 of 18

MPC (2-party case)

Server 1

Server 2

Goal:

  • Returns SK if correct, garbage otherwise

13

Secret Key Recovery

14 of 18

MPC (2-party case)

14

Secret Key Recovery

15 of 18

D-D-D-D-Demo!

15

Secret Key Recovery

16 of 18

Future work

  • N participating servers instead of 2
  • Bigger fields
  • Performance evaluation
  • Oblivious Transfer / SHE >>>> Beaver Triple Server
  • Malicious security: Each node needs a public / private keypair
    • Integrate with other group’s work

16

Secret Key Recovery

17 of 18

questions?

17

Secret Key Recovery

18 of 18

MPC review - beaver triples - TODO

Math - [([R][actual PIN - PIN guess] + 1) (k)]

Huge diagrams

Current work - demo demo

Next steps - bigger curves, more bits

​

18

Secret Key Recovery