Real World Crypto 2021 - Session 4: Signatures


Prev | Up | Next

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

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.

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:

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):

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.