Cryptographic
Vulnerabilities inThreshold Wallets

Omer Shlomovits
1Outline
This talk is focused on the pitfalls of using threshold ECDSA in building newgeneration of SW wallets.

Yay, Threshold Wallet!

What can go wrong?

I don’t care. I want it!
!2

A Wallet• Client software used as a gateway and means of interaction with ablockchain• Among other responsibilities, the Client software must play a critical
cryptographic role of generating digital signatures!3

Threshold Signatures(t,n)-threshold signature scheme distributes signing power to n parties
such that any group of at least t parties can generate a signature!4

Threshold Signatures(t,n)-threshold signature scheme distributes signing power to n parties
such that any group of at least t parties can generate a signature(2,3) - Keygen

xs,Qxc,Qxi,Q!5

Threshold Signatures(t,n)-threshold signature scheme distributes signing power to n parties
such that any group of at least t parties can generate a signature(2,3) - Signing

xc,Q, tx
xs,Q

xi,Q, tx

!6

Threshold ECDSA
https://github.com/KZen-networks/multi-party-ecdsa

Assumptions

KeyGen

Sign

[L17]

ECDSA, Paillier

Seconds

milliseconds[GG18]ECDSA, Strong RSA

milliseconds

milliseconds[DKLS18]

ECDSA

milliseconds

milliseconds[LNR18]ECDSA, DDH

Seconds

milliseconds!7Threshold ECDSA
https://github.com/KZen-networks/multi-party-ecdsa

Assumptions

KeyGen

Sign

[L17]

ECDSA, Paillier

Seconds

milliseconds[GG18]ECDSA, Strong RSA

milliseconds

milliseconds[DKLS18]

ECDSA

milliseconds

milliseconds[LNR18]ECDSA, DDH

Seconds

milliseconds• Annoyingly they all came out at the same time so none contains acomparison to the others!8Threshold ECDSA
https://github.com/KZen-networks/multi-party-ecdsa

Assumptions

KeyGenSign[L17]

ECDSA, Paillier

Seconds

milliseconds[GG18]ECDSA, Strong RSA

milliseconds

milliseconds[DKLS18]

ECDSA

milliseconds

milliseconds[LNR18]ECDSA, DDH

Seconds

milliseconds• Annoyingly they all came out at the same time so none contains acomparison to the others• Does efficient threshold signing ➡ efficient threshold wallet ?
!9Threshold Wallet
Described by the following tuple of 5 algorithms• Distributed key generation (DKG)• Distributed Signing• Secret Share Recovery• Deterministic Child Address Derivation• Rotation

Ref: https://github.com/KZen-networks/gotham-city!10

ThresholdSig > MultiSig?
A MultiSig is an Emulation of ThresholdSig• Access policy privacy• Secret refreshment• Low cost
• Max number of parties• Other differences:• Number of rounds• Chain support!11

Threshold Wallet System• Distributed network layer• Who are the n parties?
• Do all parties have to run a full node?
• Can we obtain privacy between signing parties?
• Can we translate BIP32 to multi-party ?
• Single key system and multi-party KMS cannot co-exist!12FocusThreshold Wallet System

Threshold Signatures

Implementation!13

FocusThreshold Wallet System

Threshold Signatures

Implementation• We take [L17] as a study case:• easier to explain• old enough to be implemented by several projects!14

ECDSA• EC public parameters : q,G• Choose Random k• Compute R = k • G• Compute r = rx mod q where R = (rx,ry)• Compute s = k-1 • (H(m)+ r • x) mod q
where x is the private key• Output (r,s)!15

Lindell 2P-KeyGen!16

Lindell 2P-Signing!17

2P-Keygen [L17]Q1 = x1 • G
Party1Q1Q2 = x2 • G
Party2Q2
Q = Q1 +Q2

Q = Q1 +Q2

Ence(x1)

The protocol promises: (1) Privacy, (2) Correctness!18

2P-Signing [L17]
Signing message m: m’ = Hash(m)R 1 = k1 • G
Party1R1

R 2 = k2 • G
Party2R2
R = k1 • R

R = k2 • R1

s’s = Decd(s’)/k1s’ =Ence(m’ / k2) ⊞Ence(x1)⊙Ence(x2 •r / k2)

Output: 𝞂 = (s, r), s.t. Verify(𝞂, Q, m’) = 1
The protocol promises: (1) Completeness (2) Consistency (3) Unforgeability!19

Paillier CryptoSystem
Paillier is additively homomorphic public key encryption scheme• Homomorphic addition of plaintexts: Decd(Ence(a) ⊞ Ence(b)) = a + b• Homomorphic multiplication by scalar: Decd(Ence(a)⊙k) = a•k!20

Paillier CryptoSystem
Paillier is additively homomorphic public key encryption scheme• Homomorphic addition of plaintexts: Decd(Ence(a) ⊞ Ence(b)) = a + b• Homomorphic multiplication by scalar: Decd(Ence(a)⊙k) = a•k• Zero-knowledge proofs (https://github.com/KZen-networks/zk-paillier):• Proof of correct key generation (d,e)• Range proof (r): c = Ence(a), a < r• Proof that two ciphertexts encrypts the same message : c1 =Ence (a), c2 = Ence (b), b == a12•…
!21

Getting Dirty• All examples were found in the wild
• Most of them in our multi-party-ECDSA code:• https://github.com/KZen-networks/multi-party-ecdsa• All other important issues were reported and fixed!22

DO NOT OPTIMIZE #1
P1P2com(Q1)Q2

Q1 = decom(Q1)

.
.
.

!23

DO NOT OPTIMIZE #1
P1com(Q1)P2

Q1 = decom(Q1)

Q2.
.
.

!24

#1 DO NOT OPTIMIZE
P1com(Q1)P2 P1

Q1 = decom(Q1)

Q1

Q2

Q2.
.
.

.
.
.

P2!25

#1 DO NOT OPTIMIZE
P1com(Q1)P2 P1

Q1 = decom(Q1)

Q1

Q2

Q2.
.
.

.
.
.

P2Rogue Key Attack (https://eprint.iacr.org/2018/068.pdf ): Q2 = Q - Q1!26

#2 DO NOT OPTIMIZE!27

#2 DO NOT OPTIMIZE
DLog PoKDLog PoKCorrect Paillier
Key GenerationPaillier-DLog
proof

!28

DO NOT OPTIMIZE #2Hey!
ZK proofs can be removed andcode still works!

!29

[ZK in MPC]
• Zero knowledge proofs hold 3 properties: Completeness, Soundness
and Zero-Knowledge• MPC (at least here) uses ZK as part of security proof to protect against
Malicious adversaries• This mean that removing/changing the ZK proof will break the security
proofBroken security proof does not always lead to immediate attack!30

#2 DO NOT OPTIMIZE• In KZen implementation of Lindell 2P-KeyGen we neglected LPDL. (toour defence we did integrate the Paillier range proof)!31

#3 ZK Confusion• Proof of correct Paillier Keypair:• RP = {(N, (p1,p2)), N = p1 • p2 and p1,p2 are primes}!32

#3 ZK Confusion• Proof of correct Paillier Keypair:• RP = {(N, (p1,p2)), N = p1 • p2 and p1,p2 are primes}• The author used zk proof from an old paper:• R’P = {(N,ɸ(N)), gcd((N,ɸ(N)) = 1}!33

#3 ZK Confusion• Proof of correct Paillier Keypair:• RP = {(N, (p1,p2)), N = p1 • p2 and p1,p2 are primes}• The author used zk proof from an old paper:• R’P = {(N,ɸ(N)), gcd((N,ɸ(N)) = 1}
• This two relation are not equivalent. i.e if N is a product of 3 distinct
primes of the same length!34

#3 ZK Confusion• Proof of correct Paillier Keypair:• RP = {(N, (p1,p2)), N = p1 • p2 and p1,p2 are primes}• The author used zk proof from an old paper:• R’P = {(N,ɸ(N)), gcd((N,ɸ(N)) = 1}
• This two relation are not equivalent. i.e if N is a product of 3 distinct
primes of the same length• This was fixed at a later version. Luckily, in this specific protocol R’P isenough!35

#4 ZK Confusion• Not to neglect other papers:• [GG18] KeyGen is using an unnecessary proof of knowledge ofDLog• [LNR18] zk Range proof protocol (6.2.5) is provided without a proof!36

#5 Work In Progress• 8 versions in a span of 18months• First version accepted toCrypto17’• +7 pages difference between
first and last versions• Unlike GitHub, there is nobuilt in way to track changes• In the last version there wasan update replacing zkpok of
DLog with zero knowledge ofDH relation to enableconcurrent signing!37

#6 Bad Ways toAchieve Efficiency• Zk proofs are to avoid malicious adversary but what if we use
multiple devices of the same user: well in that case we canassume that all parties are acting honest•!38

Good Ways to Achieve
Efficiency!39

Good Ways to Achieve
Efficiency• If a protocol is abstracting Zero Knowledge proofs, they can be
replaced with better version!40

Good Ways to Achieve
Efficiency• If a protocol is abstracting Zero Knowledge proofs, they can be
replaced with better version• Some protocols are presented as a chain of separate sub-protocols. Sometimes they can run in parallel instead of sequential.

!41

Good Ways to Achieve
Efficiency• If a protocol is abstracting Zero Knowledge proofs, they can bereplaced with better version• Some protocols are presented as a chain of separate sub-protocols. Sometimes they can run in parallel instead of sequential.

• Trading stronger security assumption for efficiency!42

#7 Breaking a Threshold
WalletBreaking 2P-Rotation

Call 2P-Sign and broken 2P-Rotation many times

Breaking 2P-KeyGen!43

2P-Rotation
Party1

Party2r

Coin flip

Q’1 = (x1 + r) • Gr
Q’2 = (x2 - r) • G

Q’ = Q

Q’ = Q

Ence’(x1 + r)

!44

2P-Rotation zk-Paillier• P1 Generates a new Paillier keypair (d’,e’ ) and encrypt (x1 + r) into
ckey_A = Ence’ (x1 + r)
• P2 homomorphically adds r to Ence(x1):ckey_B = Ence(x1) ⊞ r• P1 Proves in zero knowledge that ckey_A and ckey_B encrypts the samemessage x1 + r!45

2P-Rotation zk-Paillier• P1 Generates a new Paillier keypair (d’,e’ ) and encrypt (x1 + r) into
ckey_A = Ence’ (x1 + r)
• P2 homomorphically adds r to Ence(x1):ckey_B = Ence(x1) ⊞ r• P1 Proves in zero knowledge that ckey_A and ckey_B encrypts the samemessage x1 + r• Problem: chosen zk proof works only if prover do not know
factorization ➡ P1 can cheat ?
*Appendix A: https://www.iacr.org/archive/eurocrypt2000/1807/18070437-new.pdf!46

Breaking 2P-Keygen(*)Find way for P1 to rotate to any value

Rotate to unknown range such that if x2 issmaller than some known value 2p-Sign will bevalid, and invalid otherwise(*) Each “rotate”
should cancel thecoin flip r and add
a big number suchthat verificationsucceed if x2 did
not invoke modulo
operation onPaillier

Collect a constraint of the value of x2x2!47

#7 Mitigation• We suggested that if the purpose is to skip the entire 2P-Keygen

there is a general purpose for the zk proof (https://eprint.iacr.org/2016/583.pdf)• In Practice, Re-run of 2p-keygen it is:
We thank Omer Shlomovits, Li Lin and Claudio Orlandi for reporting avulnerability in our refresh procedure on February 10 2019. This has
been fixed in the open source in this update by rerunning the Paillier
ciphertext generation procedure used in key generation in every
refresh.

!48

But What If I MUST
have a threshold wallet!49But What If I MUST
have a threshold wallet• Understand what guarantees you get from the cryptography, what are thelimits and the risks• Map your security assumptions - try to minimise them as much as possible
in comparison to the entire system• Assume attacker has infinite resources and can do whatever she wants!50But What If I MUST
have a threshold wallet• Understand what guarantees you get from the cryptography, what are thelimits and the risks• Map your security assumptions - try to minimise them as much as possible
in comparison to the entire system• Assume attacker has infinite resources and can do whatever she wants
And more:• Hire a cryptographer• Education, adversarial thinking, specifically for devs
• Cryptographic audits• Battle test your code
• Programming language (e.g. Rust)• Formal Verification!51

Summary
This talk was focused on the pitfalls of using threshold ECDSA in building new
generation of SW wallets.

Yay, Threshold Wallet!

What can go wrong?

I don’t care. I want it!
!52

Questions?
When Schnorr?

https://t.me/kzen_researchhttps://github.com/KZen-networks!53