Small subgroup attack

As explained in Real-World Cryptography

A small subgroup attack sends public keys from small subgroups to expose information about a victim's private key through the resulting shared secrets.

A small subgroup attack targets a Diffie–Hellman key exchange with malicious public keys. Each key comes from a small subgroup, forcing the shared secret into a few predictable values and gradually revealing bits of the victim’s private key. section 5.4

The −1 public key

An attacker sends −1, the generator of a subgroup of size 2. Raising it to the victim’s private key produces 1 when that key is even and −1 when it is odd. Repeating the process can leak the private key incrementally. section 5.4

Reduce the attack surface by choosing groups carefully:

• Use standards that specify safe-prime moduli of the form p = 2q + 1, where q is also prime. section 5.4
• Safe-prime groups have only subgroups of order 2 and q, leaving too few small subgroups for this attack. section 5.4

Figure 5.15 A small subgroup attack impacts DH groups that have many subgroups. By choosing generators of small subgroups as public keys, an attacker can leak bits of someone’s private key little by little.

Visualize how malicious small-subgroup generators turn DH public keys into gradual private-key leakage. section 5.4

How Real-World Cryptography covers it

How deep it goes

Works through subgroup orders and a parity example, then stops short of implementation-level defenses.

Examples

Uses −1 as a malicious public key and distinguishes even from odd private keys through the shared secret.

What it assumes

Assumes Diffie–Hellman key exchange, private keys, public keys, shared secrets, and subgroup terminology.

What you can do after

Operate Diffie–Hellman more safely by following standards and selecting safe-prime groups.

How it connects

Connects Diffie–Hellman, subgroups, safe primes, Lagrange’s theorem, and shared secrets.

liveBookmanning.com

Read Real-World Cryptography on liveBook Get the book at manning.com

Related concepts

• safe primeaddressed by · A safe prime is a prime number p such that p = 2q + 1 for another prime number q.
• public key validationaddressed by · Public key validation is the process of checking that a received public key is a valid element of the intended cryptographic group.

This explainer was generated by Manning's knowledge graph from the text of Real-World Cryptography. The section links point to the parts of the book it draws on.