The Signature Nonce That Never Changed — Python Bug Hunt

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.