March 31, 2015


Be wary of one-time pads and other crypto unicorns

Yesterday, a new messaging app called Zendo got some very favorable coverage from Tech Crunch. At the core of their sales pitch is the fact that they use one-time pads for encryption. With a few strong assumptions, namely that the pads are truly random and are only used once, it’s true that this scheme is “unbreakable” or more precisely that it offers information-theoretic guarantees that no eavesdropper can learn anything about the encrypted message. Zendo’s founder calls it a “crypto unicorn” and claims it is a game-changer in terms of security.

It isn’t. In this post I’ll explain why we don’t need (and shouldn’t want) to use one-time pads for a consumer secure-messaging app and why we should generally be wary of products like Zendo making grandiose claims about solving security problems through magic crypto. [Read more...]


Why ASICs may be good for Bitcoin

Bitcoin mining is now almost exclusively performed by Bitcoin-specific ASICs (application-specific integrated circuits). These chips are made by a few startup manufacturers and cannot be used for anything else besides mining Bitcoin or closely related cryptocurrencies [1]. Because they are somewhere between a thousand and a million times more efficient at mining Bitcoin than a general-purpose computer that you can buy for the same price, they have quickly become the only game in town.

Many have lamented the rise of ASICs, feeling it departs from the democratic “one computer, one vote” vision laid out by Satoshi Nakamoto in the original Bitcoin design. There is also significant concern that mining is now too centralized, driven by ASICs as well as the rise of mining pools. Because of this, there have been many efforts to design “ASIC-resistant” mining puzzles. One of the earliest alternatives to Bitcoin, Litecoin, chose the memory-hard scrypt instead of SHA-256 in the hope of preventing ASIC mining. Despite this, there are now ASICs for mining Litecoin and their speedup over general-purpose computers may be even greater than that of Bitcoin ASICs. Litecoin’s developers themselves have essentially given up on the principle of ASIC-resistance. Subsequent efforts have included X11, which combines eleven hash functions to attempt to make ASICs difficult to build, but it’s probably only a matter of time before X11 ASICs arise as well. It’s been convincingly argued that ASIC-resistance is probably impossible in the long-term, so we should all accept that ASICs are inevitable in a successful cryptocurrency.

I would like to expand on the argument  here though by positing that ASICs may actually make Bitcoin (and similar cryptocurrencies) more stable by ensuring that miners have a large sunk cost and depend on future mining revenues to recoup it. Even if it were technically possible to design a perfectly ASIC-resistant mining puzzle which ensured that mining was efficient on general-purpose computers, this might be a bad idea if it meant you could obtain a lot of computational capacity and use it in a destructive attack on Bitcoin without significantly devaluing your computational resources’ value. [Read more...]


Bitcoin mining is NP-hard

This post is (mostly) a theoretical curiosity, but a discussion last week at CITP during our new course on Bitcoin led us to realize that being an optimal Bitcoin miner is in fact NP-hard. NP-hardness is a complexity classification used in computer science to describe many optimization problems for which we believe there is no algorithm which can always solve such problems efficiently. We’re not talking about the well-known hash puzzle portion of Bitcoin mining here in which miners race to find a block with an unusually low hash value-that’s hard by design. Before hashing anything miners first have to assemble a candidate block by choosing which transactions to include from the set of all pending transactions. As it turns out, this requires solving two optimization problems, both of which are NP-hard!

[Read more...]


POODLE and the fundamental market failure of browser security

Last week saw the public disclosure of the POODLE vulnerability, a practical attack allowing a network attacker to steal plaintext from HTTPS connections. In particular, this attack can be used to steal authentication cookies. It’s a bad vulnerability, and it particularly hurts because it should have been fixed long ago. It only affects the ancient SSL v3 protocol, which was marked deprecated 15 years ago with the introduction of TLS v1.0.

Support for SSL should have been disabled long ago, but as has been pointed out, browser vendors delayed because they didn’t want users to lose access to outdated servers. Unfortunately, even now that we know of the POODLE bug making SSLv3 highly insecure against a competent network attacker, Firefox is the only major browser which has announced definitive plans to kill SSLv3 for good. [Read more...]


Guessing passwords with Apple’s full-device encryption

With the recently-introduced iOS 8, Apple has switched to a encrypting a much larger amount of user data by default. Matt Green has provided an excellent initial look at a technical level and big-picture level and Apple has recently released a slightly more detailed specification document and an admirable promise never to include backdoors. This move, and Google’s prompt promise to follow suit with Android, are big news. They’ve even garnered criticism from the director of the FBI and re-kindled debate about mandatory key escrow, which, as has been pointed out, is a debate the tech community seriously discussed for the last time while listening to Vanilla Ice on a cassette player in the early 90s.

It’s now 2014 and we have ample experience demonstrating that intentional backdoors are unacceptably risky and vulnerability-prone. More encryption without backdoors is a good thing and Apple should be commended for continuing to have their users’ backs. However, I’d like to sound an important note of caution though about the strength of Apple’s encryption against a determined (read: governmental) attacker:

Security is only as good as your device password is.

Encryption makes security into a matter of key management, and since iOS keys are solely derived from a password, iOS encryption makes security all about your password.

This will be a lengthy technical post, but the essential point is that security still relies on passwords, which often aren’t very good. Built-in hardware support can limit the number of guesses somebody who’s taken your phone can attempt to try to recover your data, which is a fundamental improvement over purely software encryption. Unfortunately, recent research on passwords suggests that Apple has set this rate-limiting too low, likely leaving a substantial proportion of users still at risk.

[Read more...]


On Decentralizing Prediction Markets and Order Books

In a new paper to be presented next week at WEIS by Jeremy Clark, we discuss the challenges in designing truly decentralized prediction markets and order books. Prediction markets allow market participants to trade shares in future events (such as “Will the USA advance to the knockout stage of the 2014 World Cup?”) and turn a profit from accurate predictions. Prediction markets have undergone extensive study by economists and have significant social value by providing accurate forecasts of future events.

Prediction markets have been traditionally run by centralized entities that holds all of their users’ funds and shares in escrow, don’t generally allow trades to be routed through different exchange services, and make many important decisions: which events to open a market for, what the correct outcome is, and how to match buyers with sellers. Our work examines the extent to which these tasks can be decentralized to reduce trust in single entities and increase transparency, fault-tolerance, and flexibility. Bitcoin’s success as a decentralized ledger of financial transactions suggests a decentralized prediction market may be within reach. [Read more...]


Heartbleed and passwords: don’t panic

The Heartbleed bug has captured public attention this week like few security vulnerabilities before it. This is a good thing, as indeed this is a catastrophic flaw. Many people have focused on its impact on passwords with headlines like “Security Flaw Exposes Millions Of Passwords” and “Change these passwords right now.” Heartbleed certainly could have been used to steal millions of passwords. However, while Heartbleed gives the security community plenty of new problems to worry about, it doesn’t introduce any problems for passwords that haven’t existed for a long time and I’d discourage widespread panic about passwords. [Read more...]