Most of the cryptography that is widely used in commercial use has been created by govt agencies particularly of USA through National Institute of Standards and Technology (NIST). Generally when government creates ciphers for public use it raises some red flags but the cryptographers who know there job well, analyze and vet these algorithms. Unless, though highly unlikely, if govt has created some advanced math which is not known to the academic circle, these ciphers are highly secure. But this is not the case.
In 2007 Bruce Schneier reported a back door in the random number generator of Dual-EC-DRBG ceated by NIST).
‘This is how it works:
There are a bunch of constants
— fixed numbers — in the
standard used to define the
algorithm’s elliptic curve.
These constants are listed
in Appendix A of the NIST
publication, but nowhere
is it explained where they
came from.
What Shumow and Ferguson
showed is that these numbers
have a relationship with a
second, secret set of numbers
that can act as a kind of
skeleton key. If you know the
secret numbers, you can
predict the output of the
random-number generator after
collecting just 32 bytes of
its output. To put that in
real terms, you only need
to monitor one TLS internet
encryption connection in
order to crack the security
of that protocol. If you know
the secret numbers, you can
completely break any
instantiation of Dual_EC_DRBG.This was an important development as the random number generator is a key component of cryptographic protocol. It can compromise the cipher. Edward Snowden was responsible for leaking the information that it was actually created by NSA and then given to NIST with a back door entry. What is more disturbing is that RSA security which widely develops this commercial encryption applications kept on using it until it was revealed by Snowden., even after knowing the truth of backdoor created by NSA. NSA paid RSA 10 million dollars to keep the backdoor.
Vitalik Buterin in one of his article revealed that a variant of that algorithm used in bitcoin also has the backdoor. But bitcoin was able to protect itself.
Bitcoin uses the ECDSA- Elliptic curve digital signature algorithm for signing transactions. This is used to prove that the private address is linked to a particular public address holding bitcoin. The ECDSA keys are derived from certain parameters of the elliptic curve. NIST recommended everyone to use the secp256r1 parameters as they are fully secure but this has a quite similar to Dual-EC-DRBG which has a backdoor.
The secp259r1 creates a random number by using a hash function of a seed. As the output of hash function is not predictable so the seed need not be random. Instead of creating a seed like 12, the secp256r1 creates a seed like D67Hjkk0987jJlnBbGgH5478 and there is no documentation as to how it was chosen.
How bitcoin dodged the bullet. Even if NSA came to know about a specific elliptic curve with vulnerabilities, then also they will not be able to rig the system because brute forcing of hash is not feasible. But if they find one flaw in say one curve in a billion then they will have to test those 1 billion to find the exploit.
NSA developed the parameters for secp256r1. But bitcoin uses the secp256k1 instead of the secp256r1. It uses the koblitz curve instead of the random curve, and id believed to be secure till now. Satoshi chose the 256k1 instead of 256r1, but no one knows why he chose this instead of the one which was used by everyone.
Was it a luck or stroke of genius of Satoshi who made the choice but whatever be the reason he was successful in avoiding the backdoor created by NSA and circulated by NIST.
Nice article