The Signature Nonce That Never Changed

Hard

· Backend

Incident

SEV-1

BUG-SIGN-K

Priority: Critical (key compromise) · reported by crypto review

Time to fix: 35 min

Failing checks on the shipped build

  • two signatures never share a nonce

    same r means the same k - the private key falls out: expected a truthy value but got false

How to work this incident

  1. Read the report: write down the expected behaviour and the actual one in a sentence each.
  2. Reproduce it: run the visible tests and find the failing check that matches the report.
  3. Read the logs and the failing checks for the first value that is wrong — the earliest wrong value is nearer the cause than the loudest error.
  4. Follow the request through the handler, the validation and the service it calls; find the first step whose output disagrees with the report.
  5. Fix the cause rather than the symptom, run the visible tests again, and submit against the hidden ones — then write the root cause down.

Inspired by

Sony PS3 · 2010

Modelled on the PlayStation 3 signing-key disclosure presented by the fail0verflow group in December 2010. ECDSA requires a fresh, secret random number (the nonce k) for every signature. Sony's signing used the same k for every signature, and two signatures made with the same nonce are enough to compute the private key with simple algebra — which is what happened to the key Sony used to sign PS3 software.

signer.py signs with a DSA-style scheme over a toy group (group.py; the numbers are tiny so tests run instantly, the structure is the real one). It draws its nonce once, when the signer is created.

Fix Signer so every signature uses a fresh nonce from the injected RNG.

Code map

group = bug_require("./group.py")


class Signer:
    def __init__(self, private_key, rng):
        self.private_key = private_key
        self.rng = rng
        self.nonce = self._draw_nonce()

    def _draw_nonce(self):
        k = self.rng.below(group.Q)
        while k == 0:
            k = self.rng.below(group.Q)
        return k

    def sign(self, message):
        k = self.nonce
        r = pow(group.G, k, group.P) % group.Q
        s = (pow(k, -1, group.Q) * (group.digest(message) + self.private_key * r)) % group.Q
        return (r, s)

Sign in to edit the file, run the tests and submit a fix

A free account — no card, no trial clock. You come straight back here.

The Signature Nonce That Never Changed — Python Bug Hunt

Modelled on the PlayStation 3 signing-key disclosure presented by the fail0verflow group in December 2010.

  • Language: Python
  • Layer: Backend
  • Difficulty: Hard
  • Concepts: Security, Randomness
  • Modelled on: Sony PS3 · 2010
  • Visible tests: a signature verifies; two signatures never share a nonce
  • Reward: 50 XP for a complete fix

Incident

  • Severity: SEV-1 (priority: Critical (key compromise))
  • Ticket: BUG-SIGN-K
  • Reported by: crypto review
  • Time to fix: 35 minutes, the target for a hard incident

Failing checks on the shipped build

  • two signatures never share a nonce — same r means the same k - the private key falls out: expected a truthy value but got false

How to work this incident

  1. Read the report: write down the expected behaviour and the actual one in a sentence each.
  2. Reproduce it: run the visible tests and find the failing check that matches the report.
  3. Read the logs and the failing checks for the first value that is wrong — the earliest wrong value is nearer the cause than the loudest error.
  4. Follow the request through the handler, the validation and the service it calls; find the first step whose output disagrees with the report.
  5. Fix the cause rather than the symptom, run the visible tests again, and submit against the hidden ones — then write the root cause down.

Briefing

Modelled on the PlayStation 3 signing-key disclosure presented by the fail0verflow group in December 2010. ECDSA requires a fresh, secret random number (the nonce k) for every signature. Sony's signing used the same k for every signature, and two signatures made with the same nonce are enough to compute the private key with simple algebra — which is what happened to the key Sony used to sign PS3 software.

signer.py signs with a DSA-style scheme over a toy group (group.py; the numbers are tiny so tests run instantly, the structure is the real one). It draws its nonce once, when the signer is created.

Fix Signer so every signature uses a fresh nonce from the injected RNG.

Bug report

BUG-SIGN-K · Priority: Critical (key compromise) · Reported by: crypto review

Signer(private_key, rng).sign(message) returns (r, s):

  • each call draws a NEW nonce k = rng.below(group.Q); nothing is drawn when the signer is created
  • k == 0 is not a valid nonce: draw again
  • r = pow(G, k, P) % Q and s = k^-1 (digest(message) + private_key r) % Q; if r == 0 or s == 0, draw again
  • every signature must verify with group.verify(public_key, message, sig)

Consequences the tests check: n signatures consume n nonces (when none are rejected), and two signatures never share an r.

Observed: every signature from the release signer carries the same r.

Logs

[signer] sign pkg=update-3.41 r=0x2c1 s=0x0f3
[signer] sign pkg=update-3.50 r=0x2c1 s=0x1a7
[audit] 2 signatures share r — private key recoverable

The code as shipped

src/signing/signer.py (editable)

group = bug_require("./group.py")


class Signer:
    def __init__(self, private_key, rng):
        self.private_key = private_key
        self.rng = rng
        self.nonce = self._draw_nonce()

    def _draw_nonce(self):
        k = self.rng.below(group.Q)
        while k == 0:
            k = self.rng.below(group.Q)
        return k

    def sign(self, message):
        k = self.nonce
        r = pow(group.G, k, group.P) % group.Q
        s = (pow(k, -1, group.Q) * (group.digest(message) + self.private_key * r)) % group.Q
        return (r, s)

Read-only context: src/signing/group.py, src/signing/rng.py.

Open the hunt to start the incident clock, edit the files, run the visible tests and submit against the hidden ones, then write the root cause down. More Python bug hunts.