May 27, 2022

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…]