Baby Sharks: Small-Subgroup Attacks to Disrupt Large Distributed Systems

The presentation discusses the vulnerability of decentralized random bitcoin and consensus protocols in distributed computing due to small order subgroups attacks.

• Decentralized random bitcoin uses BLS threshold signatures to generate verifiable randomness, but if the public key is tweaked, verification will fail and the chain may get stuck.
• Consensus protocols relying on cryptographic primitives like threshold BLS signatures may also fail to verify signatures, causing the protocol to not terminate correctly.
• The implementation stack of MPC includes math, cryptographic primitives, logic, and network, and the attack surface is the network.
• Elliptic curves are the discrete math used in MPC, and distributed key generation is a protocol vulnerable to small order subgroups attacks.
• Verifiable secret sharing and proof of knowledge are also vulnerable to these attacks.

The speaker mentions a previous talk they gave on targeting cryptocurrency wallets using the same implementation stack, but not needing to go as deep into the foundations.

Elliptic-curve cryptography is now a common choice by practitioners, implementing cryptographic primitives that require a group of large prime order. However, for some elliptic curves, the prime order group is a subgroup of a larger composite-order group. Two such examples are Curve25519 and the pairing friendly curve BLS12-381.Protocols that are implemented with these curves are susceptible to small subgroup attacks where a point from the composite-order group is used instead of the prime-order group. Such attacks were previously demonstrated in the wild for Curve25519, e.g. CryptoNote double spend vulnerability.In this talk, we focus on small subgroup attacks in implementations that are based on threshold cryptography: proactive secret sharing, distributed key generation, and threshold signatures. Such protocols involve interaction between distrusting parties, usually with a requirement to communicate elliptic curve points. Due to the overhead in complexity, we notice that implementers occasionally forget to "sanitize" inputs, .i.e. the received points. We look at applications such as consensus, distributed randomness beacon, cryptocurrency wallet, and proof-of-stake validator. We show how injecting small order subgroup elements can bypass the security for cryptographic primitives used in threshold cryptography such as verifiable secret sharing, sigma protocols, and digital signatures. We discuss the potential damage of our attacks on the mentioned applications and demonstrate it is possible with little effort to break "liveness" for some critical real world systems.