Not Playing Randomly: The Sony PS3 and Bitcoin Crypto Hacks
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 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 reinstalled.
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.
Sony PS3 hack
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]:
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: TrueWe 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)
Bitcoin hack
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 by 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: 9ec4bc49e828d924af1d1029cacf709431abbde46d59554b62
input 1: 30440220d47ce4c025c35ec440bc81d99834a624875161a26bf
56ef7fdc0f5d52f843ad1022044e1ff…
input 2: 30440220d47ce4c025c35ec440bc81d99834a624875161a26bf
56ef7fdc0f5d52f843ad102209a5f1c…
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 of a Java bug in the Java SecureRandom class on Android, 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.
A solution
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 a 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.
Conclusions
Always use random numbers for ECDSA signatures.
References
[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.