So many times we have learned about cryptography and security the hard way. One of the key problems is ignoring the advice and warnings, which are plainly written in the current crypto literature. This without the slightest ambiguity, so that there is very little doubt about what a reasonable and professional security practice is.

The Story of Dual_EC_DRBG

Everybody in crypto community knew that the Dual_EC_DRBG was a true disgrace, a monster ignoring almost everything which it is reasonably possible to know about security. Basically well-known crypto experts have for a long time made very clear  that Dual_EC_DRBG:

• was “just plain bad random number generator all the way back in 2006”,
• it was “dodgy in 2007, and still dodgy now”,
• already in 2007, Shumow and Ferguson “raised the possibility of a backdoor”,
• it was “hilariously slow”, RNGs are usually made with symmetric crypto which is much faster (however it would be much harder to embed a backdoor in a symmetric cryptography RNG)
• to summarize, “no sensible cryptographer would go near the thing.”

Finally the NSA needed to plainly bribe a whole group of people with 10 million dollars in order for this utterly unprofessional solution to be used, and this by default. This was done in order to allow the NSA to spy on Internet connections when using RSA BSafe, a software tool which was expected to enhance the security, not degrade it.

How does it Compare to the Bitcoin Elliptic Curve?

It is hard to believe that in bitcoin things could ever become as bad as above.
In bitcoin arguably, there is maybe no reason to panic yet, no efficient attack is known, nobody is yet quite sure if this curve could be broken. There just some vague very academic shortcut attacks and definite suspicion and a further more precise stronger security criterion with Field Discriminants which just happens to be incredibly low for the bitcoin secp256k1, and no other standard elliptic curve has ever done as bad.  However fundamentally this is just strong suspicion, and there is nothing solid.

Yet however there is the same definite pattern of totally ignoring any sort of expert, professional or informed security advice.

We do not release our report on this topic yet, to be released in the future, however the main points are again already widely known, see for example our presentation at the Catacrypt workshop on CATAstrophic events in CRYPTography, which took place in San Francisco on 29 October 2014, cf. our slides.

We need therefore to stress that again NO SENSIBLE CRYPTOGRAPHER we have ever heard about would approve of bitcoin using this super-dodgy elliptic curve.
Here is what Dan Brown, the chair of SECG, the very same industrial standards body which have proposed, specified and standardized this elliptic curve in the first place, have written about this back on 18 September 2013:

I did not know that BitCoin is using secp256k1.
I am surprised to see anybody use secp256k1 instead of secp256r1. 

In other words, bitcoin should not use it and nobody else should.

Bitcoin Developers and Secp256k1

It is very interesting to discover that apart from bitcoin nobody else uses this elliptic curve ever (cf. also these slides). This is probably because crypto developers usually understand that they are subject to professional and legal liability, which is particularly strong in the financial sector. It would clearly be a serious professional mistake to ignore what every single cryptographer would recommend, including the very people who introduced this curve in the first place.

Yet bitcoin developers seem to always find some excuses to continue using this k1 curve:

• an anonymous founder who mandated it,
• ridiculous claims that the NSA could not embed a backdoor in number 7, cf. for example here, while on the contrary, there is like 30 papers each year published in cryptographic literature in which cryptosystems fail exactly because many number theory problems (e.g. solving non-linear polynomial equations) with small integers are easier than with general (larger) numbers (and discrete logs on elliptic curves rely on exactly this: solving polynomial equations known as Semaev or summation polynomials),
• incredible claims that r1 would be the insecure curve, and k1 is secure, as claimed by Vitalik Buterin,
• a pretended cautious and conservative approach to change anything in the current source code,
• unanimous allergic reactions when serious security questions are raised by uninvited academics
• more recently setting a clear agenda in which 1) a preventive upgrade is out of the question according to Jeff Garzik, and 2) on the contrary, recent efforts to develop a new super-specialised dedicated library (which focuses on this specific elliptic curve) will make that it will be even harder for bitcoin developers to accept to switch in the future (because they spent so much effort on this curve).

In fact a real cautious and conservative approach and good security engineering practice should be to upgrade ASAP, in order not to take chances and precisely avoid legal liability in case of problems.
All this sounds like really bad news for bitcoin. In fact it is not that bad.

Solutions and Risk Mitigation

The main solutions to this problem are:

• It is easy to upgrade and use another elliptic curve starting today, see this post.
• We should further lobby the developers of bitcoin apps to implement stricter policies on not revealing our public keys ever,
  • maybe up to simply destroying every bitcoin address as long as it is used once
• Great hopes are raised by moving our bitcoins to a sidechain which should allow at least some bitcoins a better protection.

On Professional Security Standards

It is bizarre to see such a  level of obstinateness in crypto currency developer circles about NOT changing the elliptic curve. I believe that  one cannot safely just dimiss the advice of the cryptographic community about the elliptic curves.  Not taking these questions seriously is bad, potentially a gross professional misconduct, and one could in theory even go to prison for that on the basis of some existing laws, for example safeguards rule in the US Gramm-Leach-Bliley Act [GLBA] from 1999.

On the Need For Elliptic Curve Agility

No one can guarantee that one elliptic curve is secure enough for a serious application such as bitcoin.
For this reason we need to switch, and switch again… We need crypto agility. It is important to switch once to be able to ever switch at all. It is like a security drill.

An industry-leading example of how to manage this process was explained to us by Alison Mankin, director of VeriSign Labs, during the same recent CataCrypt conference in San Francisco in October 2014. The example to imitate is  DNSSec where they mandate the roll-over between crypot algorithms. Every quarter you MUST switch and change the crypto algorithm. This is a great idea (though some people disagree with it). Forcing everybody to switch allows to make sure that everybody remains compatible wrt to future upgrades and the crypto CAN be changed and upgraded much more easily at ANY moment in the future. Otherwise you are NOT able to upgrade at all when there is a problem, for example just because many systems will stop working or some angry customers will complain.

Crypto currencies should embrace the same philosophy: change the elliptic curve more frequently, not because it will be broken soon, but in order that it CAN be changed at all WHEN there is a serious security alert in the future.

Recent Developments

ADDED in 2015:
Gregory Maxwell has written a long rebuttal for this paper and disputes several points here. There is no new argument or fact not previously discussed in known sources. We just rediscover the same key issues and we disagree all the same. Quick feedback:

• It is claimed that our paper (this blog post here above) was written to address an “ignorant” audience. It is not easy to write for an ignorant audience. However much I try to discuss cryptographic questions which seem very important to me on this blog, I cannot claim to achieve this goal [other people with less technical focus do a lot more]. It is very frequent that cryptographers fail to convince people responsible for cryptography used by millions of users to upgrade their crypto, before something happens. Let’s hope this is not going to happen in bitcoin. The dominant cryptography  culture in cryptography is to err on the safe side. The startup and industry culture is sometimes just the opposite.
  The rebuttal does not admit that chief crypto standard manager and highly respected mathematician at Certicom, arguably the most prominent security company worldwide in the space of modern applied public key cryptography could have some reasons not to support the bitcoin curve (or not anymore). It could be because [we] cryptographers are excessively paranoid as a rule. Or because researchers in cryptography only understand well the arguments and motivations of other researchers in cryptography.
  I would be careful though, when cryptographers say something is probably secure, it is frequently broken nevertheless. When cryptographers have doubts like with bitcoin elliptic curve, I would think twice before putting all my eggs in my basket, sorry everybody’s bitcoins in one basket, even though officially there is only a tiny “insignificant” hole in this basket. In cryptography attacks get better each year, they rarely get worse.
• In addition, in this rebuttal, our highly respected bitcoin crypto and development authority claims that it is reportedly very difficult to upgrade and that it requires a large consensus. Here we regret that by default the consensus is to be more careful about cryptography and have a backup solution in place. I believe that bitcoin users who don’t trust this elliptic curve should be allowed to use another curve. As soon as they are clearly at least some cryptographers on this planet who think that this form of cryptography is potentially dangerous and should not be used, developers should work produce fixes and alternatives.
• It seems that the established bitcoin gurus and developers always know better, better again than most cryptographers, and better again than the NSANIST  NATO BSI and 99% of people who use elliptic curves worldwide etc. [yes bitcoin uses a peculiar elliptic curve which absolutely nobody else ever uses outside of bitcoin, that’s quite bizarre].
• It is claimed that there are no good alternatives and we are stuck in a match of type bad vs. ugly, suspicious curve versus another suspicious curve both without a  real attack. In fact, we do have alternatives which are supported without reserves in the crypto community as far as I can see.
• Maxwell specifically strongly objects our tentative recommendation from 2014 of using (for example) NIST P-256 as an immediate upgrade, repeating again some known “paranoid” arguments like NIST curves are those which are suspicious and may have been manipulated by the NSA.

I have limited sympathy to P-256 and it is no longer what cryptographers recommend nowadays either. A lot of things are happening in this space recently. All of the sudden NSA also stopped recommending P-256 and this curve is officially outdated, but not necessarily less secure than before, simply an upgrade P-384 in the same kind is now recommended. Clearly however even today the NSA said these curves are not so bad and the arguments has some weight. The NSA says that standard NIST elliptic curves are still maybe  a more secure choice than any other, simply because they have been extensively studied, see here. The bitcoin elliptic curve remains an ultra sectarian choice.

All the points in this controversy remain open and we recommend to study them as a good example of controversy about cryptographic standards. The debate is likely to get exacerbated even more in the near future (for example due to Microsoft FourQ proposal). Finally maybe one day we will discover some really serious attacks. If only one elliptic curve is weak, any of these, it will be a major worldwide security scandal [ADDED 2016: not anymore, because now we are warned in advance]. In the meantime users who want their bitcoins to be safe are politely asking for bitcoin developers not to gamble with their bitcoins in the name of a conservative choice.

RELATED TOPICS [added in 2020]

Suspicious choice of the base point in Bitcoin Elliptic Curve where if we halve this point, we get a unusally short integer

00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63

In fact the same integer is also obtained for secp224k1 and secp256k1 of bitcoin. This partly explains it yet it makes it not less suspicious. In both cases we have lot of leading zero bits in binary: in secp224k1 there are 50 leading zero bits, in secp256k1 there are 90 leading zero bits. It was suggested but there is no proof that this generator was obtained deterministically by a hash function. Some speculation about this.