Speed Matters

Some work done at UCL regarding bitcoin and speed:

  • HOW to crack bitcoin passwords at a very high speed: brainflayer cracker where we read that:
    “The bulk of Brainflayer was written by Ryan Castellucci. Nicolas Courtois and Guangyan Song contributed the code in ec_pubkey_fast.c which more than doubles the speed of public key computations compared with the stock secp256k1 library from Bitcoin. This code uses a much larger table for ec multiplication and optimized routines for ec addition and doubling”.
  • HOW TO MINE bitcoin data at a very high speed: a tutorial on how to acquire and transform Bitcoin core data to an SQL database and mine this data at a very high speed (up to 50 Mb/second, the fastest solution known). See UCL bitcoin transaction data mining tutorial.
  • HOW to design a faster crypto currency and could bitcoin be fast and efficient?: a vast question not yet solved in a satisfactory way but there are definitely some ideas. See Courtois-Emirdag-Nagy paper “Could Bitcoin Transactions Be 100x Faster” in proceedings of SECRYPT 2014  and here is a poster presented at the same conference. See also Section 7 inside this paper here, some other posts in speed category, and here is our video interview about these questions for the Financial Times. Related work: see bitcoin-NG proposal.
  • Evolution-Photo-by-Johanna-Pung1-450x180

Criminals Exploit Lack Of Knowledge of How Bitcoin Works

A so called Bitcoin Generator Tool v.2.9 have been released today (Sat 3 Oct 2015) and already 260 downloads within a few hours!

It is a ZIP file which claims that it performs full access on the Bitcoin central SQL database and allows one to add bitcoins to his account.

Needless to say there is no such thing as the Bitcoin central SQL database and this is a pure criminal operation which infects our computers with malware.

redh-bad-wolf

 

 

 

 

Another similar  scam which also very clearly will put off anyone who knows how bitcoin works (they claim bitcoin block reward is 50 BTC while it is 25 BTC) however will work for naive people who don’t know much about bitcoin (which is the majority of people). And here is yet another similar operation.

More on bitcoin crime at Coindesk (very different, very rarely warned the public actual ongoing crime scams or major security risks, BUT it is a good resource about past major high-profile incidents).

NSA Plans To Retire Current Cryptography Standards

Breaking news:
the cryptography that we all know and use, such AES-128, SHA-1 and SHA-256, RSA/DH, and the most commonly used elliptic curve P-256 (a.k.a. secp256r1) are NO LONGER wholeheartedly supported by the NSA. In fact most of these, if not all, are not quite recommended anymore.

canstock10713649

Until now and for the last 10+ years the NSA and the NIST urged everybody to use these things.
Now the NSA has a very different message:

 

 

  • There will be a transition to new crypto algorithms coming very soon.
  • For the time being all current algorithms are already UPGRADED: the NSA recommends now to use at least AES-256, SHA-384, RSA-3072, DH mod p 3072, and the elliptic curve P-384.
  • These should be used only for now, in the ‘transition phase’. These cryptographic algorithms are NOT presented as long term solutions anymore!
  • The security of elliptic curve cryptography takes a serious blow in a series of statements,
    while RSA seems to come back as an acceptable solution for the time being.
  • Yes P-256 is no longer recommended, even though it is so massively used today (e.g. in 98% in SSL/TLS connections which use elliptic curves).
  • Even upgrading to P-384 today from maybe systems which use RSA or traditional discrete log mod p is NOT quite recommended anymore (the usage of elliptic curves was still increasing slowly and has not reached a very high level):
    • the NSA states: “For those partners and vendors that have not yet made the transition to Suite B elliptic curve algorithms, we recommend not making a significant expenditure to do so at this point but instead to prepare for the upcoming quantum resistant algorithm transition”.
  • Even more interesting: “For those vendors and partners that have already transitioned […] “elliptic curve cryptography is not the long term solution many once hoped it would be“. So that ECCs are going to disappear altogether and new forms of public key cryptography are going to become dominant.
    This is absolutely incredible.

    • BTW: NSA does not admit however that better elliptic curves might exist outside of current NIST/NSA curves: “Where elliptic curve protocols are to be used, we prefer Suite B standards be used to the fullest extent possible as they have a long history of security evaluation and time tested implementation that newer proposals do not yet have”.
    • Instead they make it very clear that “it is prudent to use larger key sizes in algorithms”, for example use the P-384 in the current transition period.
  • In addition, even today, P-384 is NOT quite enough in high-security systems.
    • More precisely the NSA states: “customers using layered commercial solutions to protect classified national security information with a long intelligence life should begin implementing a layer of quantum resistant protection. Such protection may be implemented today through the use of large symmetric keys and specific secure protocol standards.
      For example, CSfC deployments involving an IKE/IPsec layer may use RFC 2409-conformant implementations of the IKE standard (IKEv1) together with large, high-entropy, pre-shared keys and the AES-256 encryption algorithm. RFC 2409 is the only version of the IKE standard that leverages symmetric pre-shared keys in a manner that may achieve quantum resistant confidentiality. Additionally, MACsec key agreement as specified in IEEE 802.1X-2010, and the RFC 4279 TLS specification provide further options for implementing quantum resistant security measures today.”
  •  Overall the NSA promises to retire more or less all the cryptography that we know and they make it quite clear that the cryptography we are using today are NOT recommended anymore. Instead NEW crypto algorithms will be very soon standardized.

The official version is that all this is because of Quantum Computers…
There is however another explanation. It seems that someone finally got the message of the Catacrypt 2014 conference which took place in San Francisco on 29 Oct 2014.

 

UPDATES:

  • Link to Catacrypt 2015 (30 Sept 2015).
  • On explanations: We recall that Bruce Schneier has also said in Sept 2013 that he does no longer trust elliptic curves with magical constants and advised to move to discrete logs mod p, just after [reportedly] examining Snowden documents.
    • A new paper on how to select elliptic curve parameters.
  • On discrete logs in elliptic curves in general: this is no longer taken for granted, mostly based on NSA recent actions, less in actual crypto research.
    • There are some serious results on binary elliptic curves, see a survey of recent research on this topic and our more recent result.
  • On future crypto: Wild speculation about what will be the NSA’s next move have started.
    Very few alternative public schemes are known and their security does not inspire a lot of trust (the author of this blog has published some 20 papers on this topic, mostly breaking alternative public key schemes, and very few remain unbroken, for example HFEv- is not broken.).

What’s New in Bitcoin Mining?

20 million dollars have just been invested in BitFury (July 2015), totaling 60 million which this company has raised (source: coindesk). There was nothing like this for at least 5 months.
money-tree-wallpaper-money-tree-clipart1-245x168

 

 

 

On Mining Profitability

I find it very surprising that people invest in bitcoin mining. Why?

My [private] conjecture is as follows:
mining profitability is almost always negative.

More precisely [in a market equilibrium situation] given the anonymity services mining provides, people are willing to mine at a loss. This is basically because freshly mined coins have no origin and cannot be linked to the origin of funds used in their production.

Having said this, negative profitability property holds on average, and for a substantial proportion of miners. It could be positive for people who are able to produce better ASICs than their competitors. And have been even more negative for people who trusted companies such as Bitmine.CH to deliver miners for them. In fact IMHO all miner companies in existence have deceived their customers in some way, but some of them have deceived them a lot more… see also Section 2.4 in this paper.

Some Works on Technical Aspects of Mining

Mining with SHA256 calls for many very special optimizations which allow to reduce the IC cost and energy consumption:

  • There are countless highly technical papers about implementing SHA256 with traditional techniques such as CSA adders, see bibliography inside our paper.
  • However many optimizations were NOT covered by traditional SHA256 ASICs developers, because there are also many improvements which are SPECIFIC to bitcoin: see sections 10-12 and pages 16-24 in our paper.  This is about saving some 37% w.r.t a naive implementation. Savings are obtained in the first and last rounds of the computations.
  • Here is a shorter conference paper about these optimizations, cf. this paper as published by Springer.
  • More advanced optimizations for additions (carry reduced adders) are explained in this blog post, expected to save another 5%, maybe.
  • Another family of interesting optimizations are those which aim at saving the message expansion in the second application of the SHA256 compression function: with several specialized engines with a fixed nonce and variable mid-state H0, see page 118 here. Allows to save some 25% for one out of three compression functions. There are some technical issues with making sure that there is enough variability in the first 512 bits, without re-computing the Merkle Root too frequently.

In other works we have also studied the Stratum protocol used in mining, cf. this paper and this blog entry.

 

Is Bitcoin Going to Split in Two?

Two prominent bitcoin gurus Gavin Andresen and Mike Hearn decided to release their own software distribution of bitcoin and ALTER the specification of bitcoin!

There will be a possibility to mine blocks with a new version number and new rules. This is meant to make bitcoin more democratic: larger blocks, more transactions per second, lower fees, wider adoption. Current bitcoin has reached near its capacity limits (not much more than 3 transactions per second) in the recent months and bitcoin developer community has FAILED to solve this problem. Bitcoin developers have typically adopted a conservative “wait and see” approach on almost all major issues (speed, centralization, some crypto and crypto engineering issues, etc..) and frequently failed to embrace the necessary reforms and fixes to be standardized and implemented in time, before it is too late. It takes some courage for two guys to split from the bitcoin community and to try to tackle the elemntary yet necessary reforms of bitcoin, which questions a larger group of developers has somewhat failed to take seriously so far.

It will be now for bitcoin adopters and miner pools to vote with their feet to show if this important modification of rules which govern the whole of bitcoin is going to be adopted. A lot is at stake:

  • The fork called Bitcoin XT is initially compatible, but soon likely to become incompatible.
    • The main modification update is known as BIP 101, the block size is increased to 8 megabytes on 11 January 2016 and will then double every two years for many years to come.
    • There are also other proposals, mainly BIP 100/101/102 to solve the same problems.
    • If there is enough people who adopt the new BIP101 rule for block formatting, this could result in monetary loss for people who hold their bitcoins on the wrong side of the divide.
    • More specifically the new version is adopted inside Bitcoin XT software if 75% of miners accept it.
    • If so, Bitcoin XT could become the main software distribution of bitcoin and dictate the rules in the future.
  • A divorce or a fork in bitcoin community should lead to additional very hard to predict consequences, like further updates by both groups and a sort of divorce in bitcoin blockchain, and possibly emergence of two bitcoins which would NOT have the same market price.
  • These events also reflect growing divisions inside the bitcoin community, for example bitcoin core developers and the bitcoin foundation do no longer agree.

Very clearly a majority of renowned bitcoin crypto currency and infosec technical experts and developers view this is a hostile takeover of bitcoin by just two guys who decided to seek popular support for their sudden and unilateral fork of bitcoin core software AND of the bitcoin specification.

6773434_s

Speaking to CoinDesk Mike Hearn compared their move to creating a political party. It appears that unlike Bitcoin Core, the new software distribution will not seek to achieve consensus inside the bitcoin dev community, as the two trouble makers in question became frustrated with this process, but this distribution will simply apply the decisions of the maintainer, yet people will also be invited to fork and modify the software. Thus moving the question of consensus to a later decision, well essentially by miners. So rather “Chinese miner oligarchy” than real democracy, yet somewhat more democratic and a lot more flexible than now.

Some links:

  • Here is a coindesk account of the controversy around this bid.

 

At Least 200,000 USD in Bitcoins Exposed to Theft Due to Usage of Brainwallets

Ground breaking research on insecurity of brainwallets by Ryan Castellucci was presented at DefCon 2015 on 7 August 2015:

  • At least 733 BTC (about 200,000 USD) was at one time (more or less recently) exposed to immediate theft.
  • Many very complex passwords such as “No need to worry, my accountant handles that” already cracked.
  • A dozen of active thieves already in operation.
  • A super-fast brainwallet cracker is available to download, more thefts to come!

372c15f

 

 

See the slides.

 

 

On InfoSec Apathy

An interesting paper on the state of InfoSec apathy in which we have lived for too long now.

redh-bad-wolf

 

 

 

 

 

 

 

Some citations:

“[…]stop buying from vendors who don’t have a strong public – and practical – commitment to security”.

“We need to show that we will use our wallets with purpose, not merely convenience.”

“Sadly, we also need to agitate for legislation. The market has completely and utterly failed to address the issue.”

“I […] am not ready to wait until I find myself surrounded by self-driving cars, automated weapons that can make their own decision about who to kill and $DEITY knows what other robots and computers that will be responsible for keeping me alive… or choosing whether or not to kill me.

I won’t wait until we move past counting the cost of our electronic arrogance in billions of dollars and start counting it in bodies. Fix your shit.”

 

 

 

Bitcoin did NOT Soar, Litecoin Did!

A price increase in bitcoin was expected after the Greek crisis. HOWEVER.

  • Greek economy is not that big and modern bitcoin market is nowadays driven primarily by China.
    • There seem to be some permanent price difference on exchanges: like Chinese people are buying bitcoins against Chinese Yuan paying some 6% more, see here,  and getting out US dollars and getting less than the market price. This could be permanent and it is maybe one of the primary usages of bitcoin today: to dodge government restrictions on free movement of money.  This is primarily getting cash out of China, not out of troubled Greece which again is not that large.
    • This is also clearly related to the collapse of the stock market in China. A new bubble must be created elsewhere in order to milk stupid investors
  • Also bitcoin have had some bad press recently and was shaken by some forks in early June due to mandating some good rules on DER formatting of digital signatures.

So it is the Litecoin price which has increased like 6 times, with a peak on 9 July.

After this sudden spike, it has not collapsed. It seems to have stabilized at 3x the price of May 2015.

LTC_price_May_July2015

 

 

 

 

 

 

This is a very similar pattern to what happened with Ripple since Nov 2014.

 

Trojanized TrueCrypt Software

Open source security software also helps criminals.

372c15f

For example TrueCrypt being free and easy to modify has lowered entry barriers for establishing criminal and cyber-espionnage operations (the same applies, well to Bitcoin software!).

Example: Operation Potato Express.

  • A fully functional clone of TrueCrypt was since at least 2011 distributed from Russian web sites such as truecryptrussia.ru. The web site would only serve a rogue version to a handful of well-chosen customers/IP addresses, in particular to Ukrainian government & military institutions and journalists. In addition the malicious data-stealing functionality was activated rarely, ONLY for active long-term TrueCrypt users. As a result the operation was not discovered for years.
  • The software would later also spread malware through USB, and used a very clever trick to make people click on a file contained on a USB drive: the executable was disguised to appear as a disk drive itself, and most users would simply double click to open it and.. run malware.  Wicked.
  • More info here.

 

 

Should One Be Able to Undetectably Impersonate Citizens?

Researchers at UCL and in the US claim that the current systems for e-government citizen/user authentication (for example when dealing with taxes or public services), are deeply FLAWED.  The main issue raised is that the current systems which are under roll-out in the UK and the US are very poorly engineered with respect to central server/hub compromise threats.

Is it that our governments have (again!) betrayed our confidence to expose us to even more dependency on the assumption that large banks, governments and hackers are not going to abuse us, or that researchers are simply (again!) pushing for more fancy cryptography and expensive ‘more privacy-friendly’ systems to be used?Both: for example current systems are claimed to be conducive to a mass surveillance agenda, but, what’s isn’t nowadays? Most things we ever do with computers are.

In my view, forget privacy for a while, it is all about fraud and most basic human rights to be protected rather than exposed(!) to threats. The main thing to consider here is that YES, first of all it is actually possible to design identity systems where the government or any hacker would NOT be able to impersonate users easily without leaving traces. If this is possible and even relatively easy, as researchers claim, THEN it is a terrible thing to carry on building yet another centralized system which is designed in violation of modern privacy-friendly professional standards and principles, and as such is as almost bound to fail us, and expose us to threats, and apparently also provide a degree of invisibility and thus also impunity for wrongdoers who have an interest in exploiting such systems.

This reminds me that recently a Cambridge professor have been very heavily criticised after he proposed to scrap SIM cards in mobile phones and use passwords instead. If this is not done very carefully with latest very advanced but rather untested fancy authentication technologies, this is likely to bring our personal security 30 years back. Knowing that 90% of all human-generated passwords are excessively weak, hackers will be able to impersonate MOST people MOST of the time and simply own their devices possibly without any ‘hard to forge’ cryptographic or forensic evidence about authentication/authorization events. Really terrible! No, I would not advocate to my worst enemy to follow this sort of security advice.

This has also a lot to do with blockchain technology: it would surely also help in this process to mandate public audit trails for all authentication events ever! Honesty is subversive, as they say at Factum. In Estonia they have invented it years ago and they are trying to building systems which are audit-able and where fraud is going to be visible and detectable. Incidentally Estonia is also a worldwide leader in e-Government, citizen authentication and few other things, historically up to 10 years ahead of the UK and most other countries in this space.  Small country, fiercely independent, full of geeks, and not quite supportive of the pro-big brother agenda nowadays openly promoted in the UK.

Researchers are asking for a security review of government e-Id systems and are confident that we can do a lot better.