Rolling your own crypto is a bad idea — we should leave this to experts though even they get it wrong quite frequently.
In general, one can safely use standard crypto algorithms and ciphers provided you follow the requirements carefully. Many require cryptographically strong random numbers — if this property is not satisfied, attackers can exploit it.
One-time pad — the requirement is in the name itself
The most famous cipher is the one-time pad (OTP) which gives perfect secrecy (as proved by Shannon and others).
Pr[M = m | C = c ] = Pr[M = m]
That is, knowing the cipher text will not give you any additional info about the plain text that you didn’t already know.
However, you won’t get perfect secrecy if you reuse the pad — two-time pad! — as shown below.
As Dana Carvey might say: One-time pad: Good, Two-time pad: Bad!
Messages m1 and m2 are encrypted using the same pad (r).
c1 = (m1 ⊕ r)
c2 = (m2 ⊕ r)
c1 ⊕ c2 = m1 ⊕ m2
English text (and other languages) contains enough redundancy that given m1 ⊕ m2 of sufficient length, the adversary can recover both m1 and m2 in the clear.
During the second world war, the Soviet Union could not produce enough one-time pads. So, they used a number of one-time pads twice!
Stream Cipher — nonce reuse
OTP is not practical and so we use stream ciphers to get a sequence of random bits equal to the length of the message . One method is to use a block cipher like AES to generate the random stream. AES, like all block ciphers, is a random permutation: it takes a key and 16 bytes of input and returns 16 bytes. So, if the input to be encrypted is less than 17 bytes, you can use AES to encrypt zero, i.e. AES(key, 0), and xor it with the plain text.
c1 = (m1 ⊕ AES(key, 0))
If the input is more that 17 bytes but less than 33 bytes, we can xor the second 16 bytes or less of the message with output of encrypting ONE, i.e. (AES(key, 1)). Essentially AES is used to encrypt a counter. In a stream cipher (for the same reasons as in the OTP case), for a given encryption key, the same counter should not be used on more than one message block. To make this clear, the counter is called a nonce, which stands for "number used once". Note that the nonce is not a secret.
c1 = (m1 ⊕ AES(key, 0))
c2 = (m2 ⊕ AES(key, 1))
c1 ⊕ c2 = m1 ⊕ m2
WEP Stream Cipher — IV Collisions and related key attack
The WEP (Wired Equivalent Privacy) is a security algorithm for IEEE 802.11 wireless networks, based on the stream cipher RC4. All parties in the WEP network share a long term secret key k. Each frame uses a random 24 bit IV (Initialization Vector), which is the nonce.
RC4(IV || k) = random stream r, where || denotes concatenation.
As mentioned earlier, if 2 messages are encrypted with same IV (nonce) then c1 ⊕ c2 = m1 ⊕ m2. Given (m1 ⊕ m2) of sufficient length, the adversary can recover both messages m1 and m2 in the clear.
Due to the short 24 bit IV, after 4096 (2 power 12) frames, the probability that 2 messages are encrypted by the same IV is more than 50% (as this is counter-intuitive, it is called the birthday paradox or birthday attack). RC4 stream cipher was not designed for such use. WEP protocol has more serious flaws including vulnerability to related key attack, as all the keys (IV1 || k), (IV2 || k), (IV3 || k) have the same suffix k — an eavesdropper can recover the entire long term secret key k after getting a million WEP frames.
DSA and ECDSA — reuse of random k
There is a signature algorithm called DSA. A private key is used to compute the signature and the public key can be used to verify it. Every signature, which is a tuple (r, s), requires a unique random value called k. To be precise, k must be chosen randomly and uniformly from a set of modular integers. For a private key, the same random k should never be used more than once. If this requirement is ignored and 2 messages are signed using the same random k, the 2 signatures will have the same r (first item in the tuple) and with that the private key can be computed!
ECDSA is elliptic curve variant of the DSA algorithm and has the same requirement.
ECDSA — Sony Hack (2010)
Unfortunately, the engineers at SONY didn’t follow this requirement when they used ECDSA to sign Sony PS3 games. It appears that they signed all the games using 4 as the value of the random k. Sony’s private ECDSA key could be computed with the signatures from two PS3 games!
xkcd has a nice webcomic on this subject.
Based on the date of this webcomic, one can find out if xkcd was making fun of SONY or if SONY used this as the inspiration for their choice of k.
ECDSA — Google Android — theft of Bitcoins (2013)
Bitcoin also uses ECDSA algorithm. Your ECDSA public key is hashed to generate the bitcoin address that others can use to transact with you. In 2013, the Android implementation of the Java class SecureRandom was found to generate weak random numbers (that repeated) due to improper initialization of the underlying PRNG. So, if the user used his Android wallet to make 2 bitcoin spends, and the ‘random’ k was the same (due to the Android bug), then everyone can see that the 2 signatures (r, s1) and (r, s2) have the same r. This will allow them to compute the private key and transfer all the bitcoins to their account. Many users who use some Android Wallet apps were relieved of their bitcoins.
As someone put it aptly, Google pulled a Sony!
ECDSA scheme as described is fragile — it is broken if the same k is used to sign 2 distinct messages. Generating secure random number generators is a challenge on embedded systems such as smartcards. However, the actual requirement for k is that a) it must be chosen randomly and uniformly from a set of modular integers and b) it should not repeat.
k doesn’t have to be random. k can be computed as a pseudo-random function of the ECDSA private key and message. This deterministic value of k can still satisfy requirements a and b. This technique was proposed in 2013 by T. Pornin as RFC 6979 and is widely used for signing bitcoin transactions.
NIST FIPS 186-5 is proposing to adopt the deterministic variant of ECDSA in the standard.
Go+WebAssembly Demo of Sony ECDSA hack
To demonstrate that the private key can be retrieved if the random k is reused, I wrote a web demo using Go and webassembly. For the user interface, I used Vugu which is a modern UI library for Go+WebAssembly. Essentially, the whole demo is written in Go, which is a fine language with built-in Crypto.
As it is a web demo, you can play with it while viewing this blog article. You can also view the same demo by visiting sony-ecsda-hack-demo.srinivasan.biz