Not Playing Randomly: The Sony PS3 and Bitcoin Crypto Hacks

Watch those random number generators

What is the most costly hack to fix? Ransomware? Malware? Nope! Many experts think it is a failure of the trust infrastructure, and where the private keys of an organisation are leaked. This can then compromise all the things that are signed by those keys, including for documents and executables.

Imagine the case where Microsoft’s private keys were hacked, and where we could then not trust any piece of software (or hardware) that was signed by those keys. Intruders could create their own software (or hardware) and then sign it with a valid key. There would have to be large-scale revocation of software and hardware, and virtually everything which was associated with Microsoft’s private keys would have to be re-installed.

An intruder could thus recreate software which is properly signed by the trusted private key. Often these private keys are stolen by an insider in the company, but there are cases where sloppy coding has opened up the keys to the world. This happened in the case of ECDSA, and where developers did not check the random numbers they were generating.

In 2010, the hacker group fail0Overflow demonstrated that they could break the security methods of the Sony PS3. They achieved recreating Sony’s private key, and then break the signatures on the hypervisor and on the signed executables.

The core problem related to a lack of randomisation in the generation of a randomisation factor used within the signing processing (ECDSA). They did this by reversing the public key of the signature to give the private key. In fact, there was no actual randomisation involved and the seed value stays the same for each signing.

The signature values (R,S) use a random value of k to make sure that the values will differ for the same private key and the same message. Unfortunately, the Sony developers did not randomise it.

With ECDSA, we select a large prime number (p), and two parameters for the elliptic curve (a and b). Next, we select a prime number (n) which will be used to limit the values between 0 and n-1. Initially, we pick a point on the elliptic curve (G) and then calculate:

Y=x×G

The parameters of p, a, b, G, n and Y become public, and the private part is x (the private key) and the public key is Y. Next, we sign each document with a randomly generated value (k) and take a hash of the message (M):

r= (k×G)ₓ (mod n)s=k^{-1}·(M+Y· r) (mod n)

Note that ₓ identifies the x-co-ordinate.

The signature pair for the message is then (r,s):

Here is a sample run with the message of “hello” [here]:

import base64
Message: Hello
Hash (SHA-256): 185f8db32271fe25f561a6fc938b2e264306ec304eda518007d1764826381969
========Elliptic Curve details =============
N: 115792089237316195423570985008687907852837564279074904382605163141518161494337
G: (55066263022277343669578718895168534326250603453777594175500187360389116729240L,32670510020758816978083085130507043184471273380659243275938904335757337482424L)
========Create key pair =============
Private key: 115462636237614876875532093846366555919962524271433202626872074909427754724953
Public key: (25410763550731255280497221638170553105115478974003181854208881959963456550877L,76708110603767164532865056399633211194981188240494034058424171476748201070283L)
=======Signature generation (r,s) ==============
r=99266894966434570109926643066236781888227666184021363871992748804513599222619
s=58305626674803904522466103052053287325426747829332963563753649570076470177884
=======Signature verification (v==r) ==============
V=99266894966434570109926643066236781888227666184021363871992748804513599222619
Verified: True

We can then verify the signature with:

a) Calculating the hash of the message (M).

(b) Calculate w =s^{−1} (mod n), u1=M·w (mod n), u2=r·w (mod n)

( c) computing the point (x1, y1) on the curve:=u1×G+u2×Y

(d) We then check that r≡x1 ( mod n). If true, the signature has been validated.

Unfortunately, Sony did not generate a value of k for each signature, and always used 4 as the value of k. If we use the same value of k for two different documents, Eve can find the private key, and thus produce counterfeit signatures.

r= (k×G)x (mod n)s=k^{-1}·(M−X·r) (mod n)r′= (k×G)x (mod n)s′=K−1·(M′−X·r′) (mod n)s′-s = k^{-1} (M — M′)

and, as we know the two messages, we can determine k. From this, we can then compute the private key (x).

If we know M (message), r, s and k (the random value used), we can determine the private key (x) from:

x = (H(M) + k r) /s (mod p)

And if we know M, r, s and the private key (x) we can determine the random value (k) used:

k = (sx-H(M)) /r (mod p)

Another shock happened in 2012 with a Bitcoin hack, and which, again, broke ECDSA with a random number generator flaw. In Bitcoin, if Alice (A) sends bitcoins to Bob (B), a digital signature of the previous transaction is created with Alice’s private key. Bob’s public key is then added to the transaction. The verification of the transaction is then defined taking the public key from the previous transaction and checking the signature.

The flaw was first identified by Nils Schneider in 2013 [2] who found that the following r value appeared more than 50 times:

D47CE4C025C35EC440BC81D99834A624875161A26BF56EF7FDC0F5D52F843AD1

and was identified as being used by the same user in two transactions (and thus with the same private key). This meant that the same random number was being used. In the hack [1] there were two inputs and one output:

transaction: 9ec4bc49e828d924af1d1029cacf709431abbde46d59554b62input 1: 30440220d47ce4c025c35ec440bc81d99834a624875161a26bf56ef7fdc0f5d52f843ad1022044e1ff…input 2: 30440220d47ce4c025c35ec440bc81d99834a624875161a26bf56ef7fdc0f5d52f843ad102209a5f1c…

It can be noticed that the starting bytes of the inputs were the same, and that these identify the signature (r, s):

r1: d47ce4c025c35ec440bc81d99834a624875161a26bf56ef…r2: d47ce4c025c35ec440bc81d99834a624875161a26bf56ef…s1: 44e1ff2dfd8102cf7a47c21d5c9fd5701610d04953c68365…s2: 9a5f1c75e461d7ceb1cf3cab9013eb2dc85b6d0da8c3c6e..

We can see that the two signature values (r1 and r2) were the same. This happened because on a Java bug in the Java SecureRandom class on Android, and where it did not generate safe random numbers. The following two transactions, for example, have the same r value:

https://blockchain.info/tx/b6350f4339a59faf09bfc2a4086c2261598f46f257517ce53785145c964799bc
https://blockchain.info/tx/38fbb8a3ff718dd7c8006feb6aa9ed6add1772522781b0db95abb350a859220b

Then, on 28 Dec 2013, Nadia Heninger reported that 59 BTC had been stolen due to this bug [1HKywxiL4JziqXrzLKhmB6a74ma6kxbSDj]:

The gains of the hacks were finally transferred around August 2017.

Well, we add a random value into the mix of the signature in ECDSA, and this will change the signature. Unfortunately, if the random number is not generated correctly, it can considerably weaken the signature and thus reveal the private key. An improved method is EdDSA ( Edwards-curve Digital Signature Algorithm), and is used to create digital signature using an enhancement of the Schnorr signature with Twisted Edwards curves [here]. Its core strength is that its security is not based on the generation of a strong random number.

Repeat after me …

“I will always use random numbers of my signatures” …

“I will always use random numbers of my signatures” …

“I will always use random numbers of my signatures” …

[1] ECDSA — Application and Implementation Failures, Markus Schmid, UC SANTA BARBARA, CS 290G, FALL 2015.

[2] Nils Schneider: Recovering Bitcoin private keys using weak signatures from the blockchain, Blog entry, 28 January 2013, http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles…

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store