It may be time to rotate some keys. The venerable PuTTY was updated to 0.81 this week, and the major fix was a change to how ecdsa-sha2-nistp521 signatures are generated. The problem was reported on the oss-security mailing list, and it’s quite serious, though thankfully with a somewhat narrow coverage.
The PuTTY page on the vulnerability has the full details. To understand what’s going on, we need to briefly cover ECDSA, nonces, and elliptic curve crypto. All cryptography depends on one-way functions. In the case of RSA, it’s multiplying large primes together. The multiplication is easy, but given just the final result, it’s extremely difficult to find the two factors. DSA uses a similar problem, the discrete logarithm problem: raising a number to a given exponent, then doing modulo division.
Yet another cryptography primitive is the elliptic curve, which uses point multiplication as the one-way function. I’ve described it as a mathematical pinball, bouncing around inside the curve. It’s reasonably easy to compute the final point, but essentially impossible to trace the path back to the origin. Formally this is the Elliptic Curve Discrete Logarithm Problem, and it’s not considered to be quantum-resistant, either.
One of the complete schemes is ECDSA, which combines the DSA scheme with Elliptic Curves. Part of this calculation uses a nonce, denoted “k”, a number that is only used once. In ECDSA, k must be kept secret, and any repetition of different messages with the same nonce can lead to rapid exposure of the secret key.
And now we get to PuTTY, which was written for Windows back before that OS had any good cryptographic randomness routines. As we’ve already mentioned, re-use of k, the nonce, is disastrous for DSA. So, PuTTY did something clever, and took the private key and the contents of the message to be signed, hashed those values together using SHA-512, then used modulo division to reduce the bit-length to what was needed for the given k value. The problem is the 521-bit ECDSA, which takes a 521-bit k. That’s even shorter than the output of a SHA-512, so the resulting k value always started with nine 0 bits. Continue reading “This Week In Security: Putty Keys, Libarchive, And Palo Alto”