Tarsnap critical security bug

http://www.daemonology.net/blog/2011-01-18-tarsnap-critical-security-bug.html

by spuz • 16 years ago

231 124 16 years ago

poet2• 16 years ago

When even someone like Colin introduces a crypto bug like this, it makes you wonder. Are we ever going to get to a place where crypto engineering is something the open source community can take on? How long did it take to push people to stop writing C programs with trivial vulnerabilities? And that's something you can write a static analyzer for. No so with crypto.

yellowbkpk• 16 years ago

Why pick on the open source community? Even people working for commercial entities can write bad code.

In the open source world at least others get to look at the code and find (and perhaps fix) problems.

cperciva21• 16 years ago

Indeed, this bug was found because the Tarsnap source code is open -- someone was looking through out of curiosity when he saw the problem.

tptacek19• 16 years ago

I think that second sentence is somewhat wrongheaded. Crypto bugs aren't like normal bugs. Thousands of eyes aren't likely to surface them. Open source does not have a particularly excellent track record with exposing crypto flaws.

Simultaneously, we routinely find crypto flaws on black-box reviews of commercial products, sometimes even in firmware and hardware settings.

To my eyes, it's not the availability of source code that smokes out flaws like this, it's simply the incentive structure. Colin's project gets the attention of someone like Taylor Campbell, but Colin has made a name for himself and for Tarsnap. Even if your project becomes popular, if you aren't shouting from the mountaintops about your use of cryptography, you may be unlikely to garner the specific kind of attention you need.

poet2• 16 years ago

I should clarify. I'm not picking on the open source community. I'm differentiating the open source community form the private sector because the incentives are different. There are crypto guys in the private sector that can build secure crypto systems for $600/hour. Now, crypto is devilishly hard to do, so there's no guarantee their system would be secure either. But if you have nation-state levels of funding, you certainly can buy a system that would take serious talent and funding to break. On the other hand, open source communities are motivated by intrinsic incentives. Clearly this is enough to implement state-of-the-art operating systems, but is intrinsic motivation enough to implement secure crypto? It may well be that the bar is too high in this area and I think the next decade will yield some interesting results here. Even if we count OpenSSL as a point for open source (generous), that's one reasonably secure system over the course of a decade.

shpxnvz• 16 years ago

Are we ever going to get to a place where crypto engineering is something the open source community can take on?

I'm not sure I understand the question - are you suggesting that authors of open source security code are less qualified or more bug prone than those who work on closed source software?

One of the promises of open source code is fewer bugs through exposure to many eyes. That seems to be exactly how this security bug was found, according to the blog post. How long do you suppose this bug would have stayed hidden if the source were not available? Personally, I'd guess a lot longer.

drx• 16 years ago

That's fast. I got the email two minutes earlier :)

I meant to say this in an email, but big props to Colin for being transparent about this and responding to the issue the way he did. I'm sure it wasn't an easy weekend.

cperciva21• 16 years ago

It was remarkably fast. I put up the blog post, updated the website, sent out the emails, tweeted, updated the /topic in the #tarsnap IRC channel, and then came here to submit only to find that it already had 5 votes.

mrduncan• 16 years ago

This is an excellent example of why you shouldn't write your own crypto code - Colin is awesome at it and even he makes mistakes.

Edit: To be clear, this isn't aimed at Colin but meant to point out that if he still occasionally gets it wrong there's a pretty good chance that your fancy custom encryption method does too.

chaosmachine• 16 years ago

"if you roll your own crypto, and it breaks, you will look incompetent." - tptacek to cperciva, 313 days ago.

http://news.ycombinator.com/item?id=1183757

(not that I know anything about crypto)

tptacek19• 16 years ago

I was pretty mean to Colin in that post. In the intervening year I've come to respect Colin's practical experience a lot more than I did before, when I thought he was hopelessly academic. I'd like to make it clear that Colin doesn't look incompetant (actually, he seems to be earning accolades from the Twitterverse for how he wrote it up).

But yeah, I hope it's obvious that I see this as a very strong vindication for my argument that generalist devs shouldn't build crypto. At all, ever. Use TLS for data in motion; use PGP for data at rest. Systems much bigger and heavier than yours have gotten away with this.

djcapelis7• 16 years ago

Colin is wildly competent, but I was always uncomfortable with how much he was willing to do his own work without review. He is probably one of the best people in the world to do this work, but even the best person in the world will occasionally make mistakes, as happened here.

Generalist devs shouldn't build crypto. Expert devs shouldn't build crypto without review.

As for academics... a lot of us aren't as hopeless as some of the trash that appears in conferences and journals might appear. :)

eru5• 16 years ago

> Use TLS for data in motion; use PGP for data at rest.

That's useful advice, if you need and _want_ the guarantees given by TLS or PGP. If you have other needs then a look at, say, off-the-record messaging may be useful.

alnayyir• 16 years ago

>(not that I know anything about crypto)

Me either, and while I chuckled, I think cperciva is one of the better qualified people to be implementing crypto.

djcapelis7• 16 years ago

No one is qualified to implement crypto without review.

cperciva is extremely qualified to implement crypto, but not without review. I think it is wise that he has implemented a bug bounty procedure. He should make sure it applies to unreleased versions too so maybe someone will put an RSS feed of his SCM checkins into their RSS reader and try and catch bugs as he's making them. :)

It would be nice if he had the money to spring for paying someone else to look at all his changes, but alas... that stuff is expensive!

miGlanz• 16 years ago

Colin, one question: let's say I'm not paranoid about my backups' security. So I don't want to re-encrypt anything (even though it's only about 1GB). How does upgrade to 1.0.28 affect existing and new backups (and deduplication among those)?

cperciva21• 16 years ago

Tarsnap 1.0.28 is completely compatible with earlier versions (except for key file format changes in 1.0.22). The only nontrivial change was to make new uploaded data get encrypted correctly.

StavrosK• 16 years ago

Cryptography is hard, but someone has to do it.

tptacek19• 16 years ago

Tarsnap had a CTR nonce collision. It's a bad bug that's fairly common and easy to explain.

CTR mode turns AES into a stream cipher, meaning it can encrypt a byte at a time instead of 16 bytes at a time. It does this by using the block cipher core to encrypt counters, which produces a "keystream" that you can XOR against plaintext to use as a stream cipher.

For this to be secure, as with any stream cipher, it is crucial that the keystream never repeat. If you encrypt two plaintexts under the same keystream, you can XOR them together to cryptanalyze them; even easier, if you know the contents of one of the plaintexts, you can XOR the known plaintext against the ciphertext to recover the keystream!

To avoid repeating keystreams, CTR mode uses a nonce, which is a long cryptographically secure random number concatented to the counter before encrypting.

To avoid that catastrophic security bug, CTR mode users have to make sure the nonce never repeats (and also that the counter never repeats, e.g. by wrapping). We have found both bugs multiple times in shipping products, and now Colin found it in his product.

And so I come to the moral of my story: Colin is clearly a gifted crypto dev. He can talk lucidly and at length about the best ways to design crypto-secured protocols. He has found crypto flaws in major systems before. He is as expert as you could expect anyone to be on any product.

And Colin didn't get it right; what's more, the manner in which he got it wrong was devastating (in cryptographic terms).

Colin handled this well, largely due to the fact that he's an expert and knows how to handle it.

How likely is it that anyone less capable than Colin could have handled it so well? Moreover, if Colin can make a devastating mistake with his crypto code, how many worse mistakes would a non-expert make?

You should avoid writing crypto code if at all possible. Nate Lawson is fond of saying, "you should budget 10 times as much to verification as you do for construction of cryptosystems"; I would amend that only to add a price floor to it, because you cannot get real validation of a cryptosystem for less than many tens of thousands of dollars --- if your system is simple.

zdw• 16 years ago

TL;DR: "Even crypto experts make mistakes. Don't design or write your own crypto code, use someone else's well tested and analyzed code"

ErrantX• 16 years ago

Even more thought provoking; a mistake that was not due to a crypto mistake, but the sort of programming error you or I make daily....

andyv• 16 years ago

Nonces aren't cryptographically secure random numbers. They merely have to be different for each encryption, which is why even a counter suffices. The problem was, the counter was being incorrectly reset to zero.

  It's just as secure to concatenate a string that is a function of the time of day with the counter.  Another scheme would be to start out with a cryptographically hard number that is incremented each time.

tptacek19• 16 years ago

You're right in the CTR case; I just default to recommending random nonces because that's what you need for CBC.

cperciva21• 16 years ago

The problem was, the counter was being incorrectly reset to zero.

The counter was being correctly reset to zero. The nonce was being incorrectly not set to non-zero. (In CTR mode, there is a 64-bit nonce which is different for each message and a 64-bit counter which starts at zero for each message and increments as you move through the message.)

inklesspen4• 16 years ago

What should you do if you can't avoid writing crypto code?

I found myself in this situation when I tried to find a bcrypt implementation for Common Lisp. There wasn't one. Folks in #lisp suggested I adapt the blowfish implementation in Ironclad, since 'bcrypt is just blowfish anyway'.

I ended up writing a Lisp wrapper around one of the C implementations, a process documented at my blog (http://www.letsyouandhimfight.com/2010/07/14/cl-bcrypt-a-fir...), but it's unsatisfactory for a couple of reasons:

1) Both the current C implementations are designed to be integrated into libc. The Openwall implementation does have the code factored out into its own file, but there is no support structure for building a shared library. (Python's bcrypt bundles a modified version of the Openwall C source directly with it, for example.) Common Lisp's FFI is intended for working with installed shared libraries

2) There appears to be a bias in the Lisp community towards pure-Lisp implementations, for (hopefully obvious) reasons, so an implementation as hacky as what I came up with is unlikely to see much use.

If I do go back to trying to write a webapp in Common Lisp, I think I will find myself having to reimplement bcrypt in Common Lisp. First, I'll have to find a sufficiently portable method of getting cryptographically secure random numbers; as of the writing of that blog post, there wasn't one that I could find anyone recommending. The more difficult part will be to convert the C code into Lisp code without missing any places where operations on the C types don't precisely correspond to the same operations on the Lisp types (due to, say, overflow).

I'm worried I might get something wrong, but I can't just use the crypto code written by wiser folks than I, because, at least in the Common Lisp community, that code doesn't seem to exist.

tptacek19• 16 years ago

First, don't obsess too much about your password digest. I know this is head-explodey considering the source, but all I'm trying to do by ranting about it is to get people to stop using SHA1 (or SHA256 or Whirlpool or whatever) hashes. The risk to your users for doing that bit wrong is not very high.

Second, my advice about how to do crypto security is very simple:

* Use PGP for data at rest.

* Use TLS for data in motion.

Do not trust your own judgement (say, by using OTR because it "feels" like most of what you need, or trusting that you'll use Keyczar safely) on anything else without a formal external review. In practice, you will almost never need anything more than TLS or PGP.

weichi2• 16 years ago

A comment and a question:

1. It should be fairly trivial to test that your implementation is giving exactly the same output as the c libs (once you have chosen a particular random number that feeds into the algorithm). It seems like the trickiest part of testing will be ensuring that you are using the same character set everywhere.

2. Why is it important to have a "cryptographically strong" PRNG? Doesn't this just turn into a salt? Does a salt generator really need to be cryptographically strong?

Someone please correct me if I am being naive here.

pjscott• 16 years ago

If you're trying to make something in pure Lisp, your odds of failure are less if you take an existing hashing algorithm (e.g. SHA-256) and just iterate it a bunch of times. Ironclad has SHA-256, so this is really easy:

    (defun slow-hash (password salt &key (iterations 10000))
      "Produces a 256-bit hashed value of password and salt, slowly. Uses
      a tweakable number of iterations, which should not be less than
      1000, and which defaults to 10000."
      (let ((hash (ironclad:make-digest :sha256)))
        ;; First, hash the salt and password
        (ironclad:update-digest hash
           (ironclad:ascii-string-to-byte-array salt))
        (ironclad:update-digest hash
           (ironclad:ascii-string-to-byte-array password))
        ;; Repeatedly hash the hash, to slow things down
        (dotimes (x iterations)
          (ironclad:update-digest hash (ironclad:produce-digest hash)))
        (ironclad:produce-digest hash)))

cookiecaper2• 16 years ago

The mistake he made is not specifically a "crypto code" problem, it was merely forgetting to increment the new variable, and that kind of thing happens in a lot of non-crypto contexts. I think that the reason people should use tested and well-known crypto code is because the stakes are high and not necessarily because cryptography is super complex; a mistake like this can have serious consequences since most encrypted data is serious by nature. As such, the maxim "don't write your own crypto" could also be applied to any high stakes programmatic endeavor; if you can't tolerate any downtime on your server, "don't write your own server", etc.

The great thing about widely used open-source utilities is the extensive vetting they receive. I was a bit uncomfortable using tarsnap's custom client and now I'm happy I went with duplicity, which is a Python script combining rsync, tar, and gpg to create encrypted archives of your data and only send the differences.

Also, perhaps Colin could look into writing a test suite for tarsnap that would automatically test for mistakes like this. It doesn't sound like the particular applicable exploit is too hard to automate.

wladimir3• 16 years ago

You are right. I use duplicity for remote backups too, I can really recommend it :)

However, in crypto the 'NIH' syndrome is especially prevalent because of the inherent secrecy and paranoia. Especially as there are still a lot of people on the obscurity side of security versus obscurity. A good recent example of this would be Sony...

cperciva21• 16 years ago

The mistake he made is not specifically a "crypto code" problem, it was merely forgetting to increment the new variable

It wasn't even that. My mistake was refactoring code incorrectly. The increment was there for two years until it got lost in the refactoring.

The great thing about widely used open-source utilities is the extensive vetting they receive

Wearing my FreeBSD Security Officer hat: It's nice to think that, but most open source code gets a shockingly small amount of auditing.

alecco• 16 years ago

"Tarsnap compresses its chunks of data before encrypting them. While the compresion is not perfect (there are, for instance, some predictable header bits), I do not believe that enough information is leaked to make such a ciphertext-only attack feasible."

That part is very important. Compress then encrypt. Here you see competent crypto applications playing safe covering for unexpected problems. I say well done Colin! Full disclosure and best practices.

tptacek19• 16 years ago

Compression prior to encryption is generally a good practice, but as Colin points out, it doesn't actually do much to mitigate this bug; in a bulk encryption setting, you're going to find known compressed plaintexted to back keysteam out of.

It's true, and Colin's right to point it out, that it's unlikely that this bug will be exploited (you have to be Colin to do it, and it's a general PITA to deal with), but I wouldn't want anyone to have the impression that CTR mistakes are survivable just because you compress.

aristus• 16 years ago

This may be a naive question, but are unit tests for encryption code a reasonable idea? eg, each revision is tested against a known set of data and a known set of common attacks.

tptacek19• 16 years ago

It's hard to test the behavior of crypto code (even insecure crypto code can still generate data indistinguishable from random noise), so your unit tests end up tightly coupled to the actual implementation. You can do it, but it's not as clear a win as it is in other settings.

nwmcsween2• 16 years ago

I planned on modifying tarsnap to work on local files and upload to different resources (dropbox, local, etc) but as I dug in and looked at the license I noticed this little gem in COPYING "Redistribution and use in source and binary forms, without modification, is permitted for the sole purpose of using the "tarsnap" backup service". Why even provide source if the license doesn't allow me to do anything with said source? I can't create a patch without being litigated and I won't due to that.

tptacek19• 16 years ago

This is silly. Colin clearly isn't going to "litigate" against you. He provides the source precisely so that people can find bugs in it. It's a commercial product, though, not a GNU project. It's a good thing that he provided source code, and it's disingenuous and petty to try to punish him for doing that.

ptomato• 16 years ago

Also, that way he doesn't have to compile/package it for every system somebody might want to run it on.

nwmcsween2• 16 years ago

Why not just have a non-compete clause within the license. At least legally this would allow for internal use with local backups. I highly doubt execution of a similar service using tarsnap would even happen, if that's what the worry is.

requinot592• 16 years ago

> it's disingenuous and petty to try to punish him

Where does he try to "punish" him?!

Plus it's a real legal concern, sure in practice cperciva will not sue him, but still...

palsecam2• 16 years ago

"No matter how secure Tarsnap's design is, however, you don't run the design on your computer — you run the code. For this reason, all of the source code to the Tarsnap client is available. You don't need to simply trust that Tarsnap does things right (and that it isn't a trojan planted by the US government): You can read the source code and check for yourself."

Last § of https://www.tarsnap.com/security.html

cpach• 16 years ago

Are you sure you can't do that?

http://cr.yp.to/softwarelaw.html

cperciva21• 16 years ago

I planned on modifying tarsnap to work on local files and upload to different resources (dropbox, local, etc) but as I dug in and looked at the license I noticed this little gem in COPYING...

Exactly. That is deliberate. I don't want to end up competing with my own code.

Why even provide source if the license doesn't allow me to do anything with said source?

So that people can audit it if they wish to do so.

paulitex• 16 years ago

This is a perfect example of why we shouldn't have (or not allowing the use of) ++ in languages. If instead of being buried in a long statement, the increment had been explicit on its own line there's a much smaller chance this bug would have happened.

Which is easier to miss?

aes_ctr(&encr_aes->key, encr_aes->nonce++, buf, len, filebuf + CRYPTO_FILE_HLEN);

aes_ctr(&encr_aes->key, encr_aes->nonce, buf, len, filebuf + CRYPTO_FILE_HLEN);

ncr_aes->nonce += 1;

palsecam2• 16 years ago

Golang does that, right (++ is a statement, not an expression)?

enneff• 16 years ago

Yes. Go's assignments, increments, etc cannot be used as expressions.

eru5• 16 years ago

Python has this feature. But if you want to get serious, eliminate [1] all side-effects like Haskell.

[1] Or rather, make all side effects explicit---including visible to the type system.

moconnor• 16 years ago

For better or worse I've been working on the same codebase for almost a decade; now whenever I patch the code I've got half an eye on how likely it is that I or someone else could accidentally break this code in the future.

If you've got to write code that's not allowed to fail, you can't afford set up little traps like this for yourself.

apowell• 16 years ago

Will a backup created in 1.0.28 still be de-duplicated against backups created in previous versions of Tarsnap?

cperciva21• 16 years ago

Yes. This is why you need to upload data with a new key in order to ensure that it is re-encrypted.

Splines• 16 years ago

Isn't this the same category of bug that led to the Sony master key leak? Amusing, if so.

tptacek19• 16 years ago

Sort of but not really. Apart from the fact that Sony broke DSA (a wildly different crypto primitive than AES-CTR), the mistake Sony made was more fundamental to the design. I think you're right to notice that in both cases a nonce wasn't actually a nonce.

DavidSJ2• 16 years ago

Colin, thanks for the explanation. I suggest an additional change to your pre-release process: all code must be peer reviewed. This is by far the most effective quality control measure you can implement, much more so than unit testing or "double-checking". I wouldn't trust any mission-critical production code that hasn't been peer-reviewed, much less crypto code.

cperciva21• 16 years ago

Code review is always good, but some code deserves more checking that other code. There are some parts of Tarsnap where the worst that could happen is that you'll get some mangled messages printed to the terminal -- that code is clearly not as deserving of testing as the core cryptographic functionality.

DavidSJ2• 16 years ago

I didn't word what I said as well as I could have, but what I meant was to emphasize the "require review before submission" part, not the "all code" part. Do you have mandatory peer review on security-critical code already?

there• 16 years ago

tarsnap had a government backdoor! colin just did this to get publicity! colin just did this to get a free security audit!

</sarcasm>

cperciva21• 16 years ago

I've never had a DoD grant revoked. :-)

monological• 16 years ago

tarsnap.com has exceeded their app engine quota. Not good for business.

cperciva21• 16 years ago

Tarsnap doesn't use app engine. Google's index went nuts and I have absolutely no clue why. The real Tarsnap website is at http://www.tarsnap.com/

grourk• 16 years ago

Looks like you rolled a hard six. ;-)

Groxx• 16 years ago

This seems like it would be a fantastic reason to develop a crypto-linter. Not that I think such a thing would be easy - but it could be immensely simplified by defining things like a "must change" attribute on parameters like that "encr_aes" pointer in library code, to flag potential incorrect use.

tptacek19• 16 years ago

Buffer overflows are a fantastic reason to develop secure code linters. I'll let you know when we figure out how to make one that can count reliably.

cperciva21• 16 years ago

Make sure that it can also divide. My favourite Coverity glitch is when it looked at some IPv6 code and announced "assuming i % 8 != 0" and "assuming i == 128" at the same time. (And then claimed that we would access ipv6addr[16].)

joanou• 16 years ago

I applaud the openness of this submittal. Nobody's perfect and the topic is difficult and the implementation is tricky to get absolutely right.

At AltDrive, we use a nonce generated w/ secure random and that is used for encrypting an entire file in CTR (EAX) mode. The issue with 64k chunks does not apply. The mature and well-respected BouncyCastle AES-256 libraries are used from the low level API. Usage of the API was independently reviewed by the BouncyCastle organization. I can share that on the AltDrive blog if anyone is interested. http://altdrive.com

mooneater• 16 years ago

Its good users were notified to upgrade, but I am surprised he revealed as many details this soon. Does that not further reduce security for the end user for data they have stored with the old version?

JoachimSchipper• 16 years ago

It's not like running diff against both versions wouldn't pinpoint the problem anyway.

cperciva21• 16 years ago

I did consider that, but the NSA knows perfectly well how to attack CTR nonce collisions, and anyone looking at the diff between version 1.0.27 and version 1.0.28 can see what the change was; so I didn't disclose anything which potential attackers couldn't already figure out easily.

dauphin• 16 years ago

My new online code analyser program, sponsored by AMD, could have prevented this bug.

JacobAldridge• 16 years ago

I'm a massive fan of tarsnap, even though I have no need for it and probably don't have the technical competence to use it anyway. Given that using the product isn't why I'm a fan, I can only put that down to Colin - and this post, with its technical openness, easy to understand (for a layman-of-sorts) crypto and code explanation, and humility demonstrates why.

All that, plus explaining how to delete and offering a refund will probably cost only a small number of picodollars, and is worth a lot more to tarsnap's credibility.

Tarsnap critical security bug

Related Stories