February 26, 2017

RIP, SHA-1

Today’s cryptography news is that researchers have discovered a collision in the SHA-1 cryptographic hash function. Though long-expected, this is a notable milestone in the evolution of crypto standards.

Kudos to Marc Stevens, Elie Bursztein, Pierre Karpma, Ange Albertine, and Yarik Markov of CWI Amsterdam and Google Research for their result.

SHA-1 was standardized by NIST in 1995 for use as a cryptographic hash function (or simply “hash”).  Hashes have many uses, most notably as unique short “fingerprints” for data. A secure hash will be collision-resistant, which means it is infeasible to find two files that have the same hash.

One consequence of collision-resistance is that if you want to detect whether anyone has tampered with a file, you can just remember the hash of the file. This is nice because the hash will be small: a SHA-1 hash is only 20 bytes, and other popular hashes are typically 32 bytes. Later, if you want to verify that the file hasn’t changed, you can recompute the hash of the (possibly modified) file , and verify that the result is the same as the hash you remembered. If the hashes of two files are the same, then the files must be the same–otherwise the two files would constitute a collision.

By 2011 it had become clear that SHA-1 was not as strong as expected. Any hash can be defeated by a brute-force search, so hashes are designed so that the cost of brute-force search is too high to be feasible. But methods had been discovered that reduced the cost of finding a collision by a factor of about 100,000 below the cost of a brute-force search.  All was not lost, because even with that cost reduction, defeating SHA-1 was still massively costly by 2011 standards. But the writing was on the wall, and NIST deprecated SHA-1 in 2011, which is standards-speak for advising people to stop using it as soon as practical.

The new result demonstrates a collision in SHA-1. The researchers found two PDF files that have the same hash. This required a lot of computation: 6500 machine-years on standard computers (CPUs), plus 100 machine-years on slightly specialized computers (GPUs).

Today, some systems in the field still rely on SHA-1, despite stronger hashes like SHA-2 getting more use, and the presumably stronger SHA-3 standard was issued in 2015. It is well past time to stop using SHA-1, but the process of phasing it out has taken longer than expected.

There are two lessons here about crypto standards. First, it can take a long time to phase out a standard, even if it is deprecated and known to be vulnerable. Second, the work by NIST and the crypto community to plan ahead, deprecate SHA-1 early, and push forward successor standards, will pay many dividends.

[Post updated (24 Feb) to improve terminology (collision-resistant, rather than collision-free), and to reflect the correct status of the SHA-3 standard.]

Smart Contracts: Neither Smart nor Contracts?

Karen Levy has an interesting new article critiquing blockchain-based “smart contracts.”  The first part of her title, “Book-Smart, not Street-Smart,” sums up her point. Here’s a snippet:

Though smart contracts do have some features that might serve the goals of social justice and fairness, I suggest that they are based on a thin conception of what law does, and how it does it. Smart contracts focus on the technical form of contract to the exclusion of the social contexts within which contracts operate, and the complex ways in which people use them. In the real world, contractual obligations are enforced through all kinds of social mechanisms other than formal adjudication—and contracts serve many functions that are not explicitly legal in nature, or even designed to be formally enforced.

To review, “smart contracts” are a feature of some blockchain-based systems, which allow an interaction between multiple parties to be encoded as a set of rules which will be executed automatically by the system, so that neither the parties nor anyone else can prevent those rules from being enforced. There are lots of variations on the basic idea, which differ in aspects such as exactly what kind of code is used to program the rules, what kinds of actions can be expressed in a ruleset, and so on.

A simple example is an escrow arrangement, where Alice puts some money into escrow, and the money is released to Bob later if an arbiter Charlie determines that Bob performed some required action; otherwise the money returns to Alice. An escrow mechanism can be encoded as a “smart contract” so that once put into escrow the funds can only be disbursed to Alice or Bob, and only as specified by Charlie. Additional features, such as (say) splitting the money 50/50 between Alice and Bob if Charlie fails to act, can be built in. Indeed, the whole idea is that complicated rules can be encoded and then automatically executed with no dispute or appeal possible.

Karen’s argument, that contracts serve functions that are not merely legal, is correct–and that is one reason why “smart contracts” may not be street-smart.  But in addition to failing to do the non-legal work that contracts do, “smart contracts” also fail to do much of the legal work that contracts do, because they don’t work in the same way as contracts.

To give just one example, a legal contract need not try to anticipate absolutely every relevant event that might occur. If some weird thing happens that is not envisioned in a regular legal contract, the parties can work out a modification to the contract that seems reasonable to them, and failing that, a judge might decide the outcome, subject to established legal principles.  Similarly, a single error or “bug” in writing a regular contract, causing its literal meaning to differ from what the parties intended, is unlikely to lead to extreme results because the legal system will often resolve such a problem by trying to be reasonable.

Contrast this with “smart contracts” where a bug in a “contract’s” code can lead to a perverse result that may allow one party to exploit the bug, extracting much of the value out of the arrangement with no recourse for the other parties. That’s what happened with the DAO in Ethereum, leading to a controversial attempt to unwind a legal-according-to-the-rules set of transactions, and dividing the Ethereum community.

So if “smart contracts” may not be smart, and may not be contracts, what are they? It’s best to think of them not as contracts but as mechanisms. A mechanism is a sort of virtual machine that will do exactly what it is designed to do. Like an industrial machine, which can cause terrible damage if it’s not designed very carefully for safety or if it is used thoughtlessly, a mechanism can cause harm unless designed and used with great care.  That said, in some circumstances a mechanism will be exactly what you need.

Discarding the term “smart contract” which promises too much in both respects–being sometimes not smart and sometimes unlike a contract–and instead thinking of these virtual objects as nothing more or less than mindless mechanisms is not only more accurate, but also more likely to lead to more prudent application of this powerful idea.

 

 

Regulation and Anti-Regulation

[Hi, Freedom to Tinker readers. I’m back at Princeton, having completed my tour of duty as Deputy U.S. CTO, so I can resume writing here. I’ll start with some posts on specific topics, like the one below. As time goes on, I’ll have a lot more to say about what I learned.  –Ed Felten]

Politicians often talk about regulation as hindering business and economic development. Witness President Trump’s executive order  that tries to reduce the number of Federal regulations. Sometimes regulation inhibits innovation and limits freedom of action. But often regulation acts to open up new opportunities.

A good example is the FAA’s “Part 107” rule that was announced last summer. This rule established requirements for commercial flights of drones up to 55 pounds. For the first time, commercial flights became possible without requiring special permission from the FAA, as long as certain restrictions were followed: fly below 400 feet; avoid airports and other special facilities; don’t fly at night; don’t fly over people; and maintain visual line of sight to the drone.

Because flying aircraft in the national airspace is forbidden by default, for obvious safety reasons, regulation that permits flight, within limits, has the effect of expanding rather than reducing what companies and individuals can do. Part 107 made more types of drone flights legal.  This has already been an important enabler of beneficial innovation and use of drones.

But the FAA’s work is not done. The agency had been planning a series of follow-on rules designed to relax the boundaries of Part 107, to allow flight over people, beyond visual line of sight, and so on, as it became clear how to do so safely.  

Will the new executive order make this more difficult?  It’s hard to tell, because many aspects of the order are unclear or await further clarification from the Office of Management and Budget.  But a policy that creates new barriers to the FAA responsibly loosening the restrictions on drone flights will not increase freedom and will not benefit the American people.

I hope the interpretation and implementation of the new executive order accounts for the full range of regulatory actions.  A policy that starts out assuming that regulation limits action too much, and thereby inhibits innovation and economic growth, may or may not be correct. But a policy that tries to prevent all action by regulatory agencies cannot be the right approach for the American people, especially if the goal is to reduce the burden imposed by regulation.