The PS-3 Private Key Break

At the December 2010 Chaos Communication Congress in Berlin, a group calling itself ''fail0verflow'' announced it had succeeded in bypassing a number of Sony PlayStation 3 restrictive measures. These included the recovery of the private key Sony uses to sign code. Sony was using a technology called public key cryptography to insure that only programs it approved could run on the PS3. Public key cryptography uses one key, which is kept private, to create a mathematical puzzle that is very hard to solve, but which can be unlocked using a different key that can safely be made public. These puzzles can then be used to create electronic signatures that can be verified by any computer that has the public key. Absent unforeseen mathematical breakthroughs, if the public key algorithm is implemented correctly and the private key is kept secret, no one can forge such a signature.

The PS3 private key recovery was made possible by an improper implementation of the public key cryptography system Sony employed, Elliptic Curve Digital Signature Algorithm or ECDSA. ECDSA requires a secret random number to be generated for each signature. Those secret numbers must be different for each signature. If two signatures are found that used the same secret number, even if that number itself is not known, the private key can be recovered by simple algebra. Sony reportedly used the same secret number for all its signatures. As a result, anyone with the now-public private key can sign code it a way that is indistinguishable from a signature issued by Sony.

This flaw was not in any of the PS3 software or the IBM Cell processor that's at the heart of the PS3. It was a mistake in the program used to sign software approved to run on the PS3. That program presumably runs only on some highly guarded server at a facility controlled by Sony. The signing program could have been fixed by adding one line of code, a call to a strong random number generator, like /dev/random, to generate a new random number for each signature.  You may have to go back to the US and UK's Venona exploit in the Cold War to find an example of a large organization (the USSR in that case) screwing up what should have been an unbreakable system.

The lesson from this fiasco is that in cryptography details are crucial. Cryptographic software must be intensively reviewed by experts, not programers who recently read a book or took a course on the subject. The best solution may be open source implementations that have been available for public scrutiny for many years, and even then, an expert review of the final software is still essential. And all user of ECDSA and similar algorithms should review their signing software to insure it does not contain the same bug. This barn may contain more than one horse, so its's worth checking the door.

Here is a YouTube link to the complete presentation: http://www.youtube.com/watch?v=hcbaeKA2moE