October 6, 2022

Archives for October 2014

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

Four Fair Use Takeaways from Cambridge University Press v. Patton

The most important copyright and educational fair use case in recent memory (mine, at least) was decided by the Eleventh Circuit Court of Appeals last week. The case, Cambridge University Press v. Patton, challenged Georgia State University’s use of e-reserves in courses offered by the university. The copyrighted works at issue were scholarly books–i.e., a mix of monographs, edited volumes, and portions thereof–not textbooks. This case is important because of its broad applicability to similarly situated academic institutions throughout the country that routinely engage in the same practices for which GSU was sued. It’s also important because the court’s decision re-articulated and faithfully followed some foundational fair use principles from prior case law. Readers of the case who are proponents of a vigorous fair use doctrine shouldn’t be disheartened by the fact that the Eleventh Circuit reversed the district court’s ruling in favor of GSU and remanded the case for reconsideration. Ultimately, this case is good news for educational fair use. Here are four reasons why:
[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…]

On the value of encrypting your phone

This is a true story.

Yesterday my phone crashed, and it wouldn’t reboot. Actually it would do nothing but reboot, over and over, with a seemingly different error message every time. I tried all of the tricks available to a technically handy person, and nothing worked—I couldn’t get it out of the crash-reboot cycle.

So I need to send my phone in for service. The problem is: the phone is full of my data, and I don’t want a random service guy to get his hands on that data. Nor do I want a random service guy to be able to resume whatever logged-in sessions I had on apps and sites when the phone started crashing.

What I want is to have the data on my phone encrypted. Strongly encrypted. Without a backdoor, because the service guy has no need to see my data and no right to get it. I would have wiped the phone’s memory before sending it in for service, but that would have required the phone to stay functional long enough to wipe itself.

What I don’t want is for the service guy to have access to a “secure golden key” that gives him access to my data.

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