Real World Crypto 2021 - Session 4: Signatures
RWC2021 · Real World Crypto
Session video
Akira Takahashi (Aarhuis Uni) / LadderLeak: Breaking ECDSA With Less Than One Bit Of Nonce Leakage / paper video slides
ECDSA nonce is extremely sensitive, <1bit leakage per signature is exploitable using attacks based on HNP
HNP - Hidden Number Problem (Dan Boneh / Venkatesan in 1996)
HNP is at the heart of many recent real-world vulns in ECDSA/DH
Nonce leakage can be attacked via Lattice attacks or Fourier analysis (first done by Bleichenbacher, see https://blog.cr.yp.to/20191024-eddsa.html)
Ladder leakage: timing leakage from Montgomery ladder
(attacks in the talk can also be applied to Schnorr signatures)
Tim Ruffing (Blockstream) / MuSig2: Simple Two-Round Schnorr Multi-Signatures / paper video slides
Key idea in MuSig2: Every signer uses a random linear combination of multiple pre-nonces as a nonce.
- signatures look like ordinary Schnorr sigs, are compact and permit fast verification
- practical/simple 2-round signing protocol where first round can be precomputed without the message, making eventual signing almost non-interactive
- see paper for a funny story alluded to in the talk
Multisigs: n signers get together to create a single signature (n-of-n ie. all of n must be present, not threshold which is t-of-n where t < n and where only t need to be present).
Work motivated by Bitcoin where multi-sigs ease shared ownership. Bitcoin is moving from ECDSA to Schnorr.
Schnorr signatures used in Bitcoin on-chain:
- used instead of ECDSA because Schnorr facilitates more advanced signing protocols, e.g. multi-sig, threshold-sig, blind-sig)
- on-chain is better for consensus because off-chain protocols are not visible to verifiers
- Schnorr PK is created non-interactively; Schnorr sigs are verified interactively
Multi-sig require >1 PKs to be aggregated. The signers also contribute to the nonce.
Emil Lundberg (Yubico, Surrey Centre for CyberSecurity, Wire) / Asynchronous Remote Key Generation: An Analysis of Yubico’s Proposal for W3C WebAuthn / paper video slides
Introduces new crypto primitive: ARKG (Asynchronous remote key generation), proposed by Yubico, and implemented in WebAuthn guide
WebAuthn (2019) is W3C proposal of an API for accessing public key credentials. Backed by various types of hardware token (aka authenticators):
- key properties: two pubkeys generated by the same authenticator are not linkable, this is good for privacy/anonymity
- authenticator attestation: authenticator devices can prove their make/model, which is desirable for certain finance or government applications
You’re a bit screwed if you lose your device, so common pattern is to have a backup device kept at home: however for every service you use device to auth to, you need to register both primary and backup devices. This is inconvenient, error-prone and backups are easily lost.
Yubico’s proposal is that primary and back-up authenticator devices are paired together. You keep backup stored safe at home, and only work using the primary device. if it becomes necessary to use back-up device, it then becomes the new primary device. Later when you recover the old primary it becomes the new backup through another pairing. This process is modeled using AKRG.
The async aspect is that the primary device generates public keys fo rthe backup device, then if primary is lost, the backup device can later generate the corresponding private keys.