You are dangerously bad at cryptography

Outside of computing: health and diet. Sure, you get some feedback, but you also can screw up things in some ridiculously slow-acting way. Pharma companies (are supposed to) monitor drug use for decades after introduction for the same reason.

Construction. Just build that chunk out of two steel beams instead of one, and witness it work perfectly until someone decides to throw a party on that balcony. Or witness your construction slowly turn itself from a perfectly normal tower to a major tourist attraction over the centuries.

Parenting. Things like sudden stimuli in early life have been linked to ADD, the way you do attachment can have tremendous consequences, and sometimes singular events you barely have any control over can have unpredictable consequences later in your life.

In fact, I'm tempted to say "life in general".

Memory safety in memory-unsafe languages. We've had Valgrind and ASan for a while, and people still find crippling bugs in C and C++ code all the time.

XSS vulnerabilities. Maybe Content Security Policy will help some here when it becomes ubiquitously available.

Integer overflow. This is a particularly insidious problem because your well-formed test cases often won't catch it.

- Relying on undefined or implementation-specified behavior. Problems only show up years down the road. (example issue: expecting signed overflow to wraparound in C)

- Avoiding statistical biases when transforming random values. Statistical unit tests are hard. (example issue: shuffling via lots of uniformly random swaps)

- Integer overflow ruining algorithms that would be correct, given unbounded integers. (example issue: average = (a+b)/2)

The biggest candidate:

* Pure mathematics: Consider e.g. the difficulty in verifying the recent proofs of Fermat's Last Theorem (Wiles-Taylor-Frey theorem?), the Poincaré conjecture (Perelman-Hamilton-Thurston theorem?), and now the ABC conjecture (Mochizuki-Szpiro theorem?): there is essentially no indication of the correctness of a mathematical proof besides simply having a whole lot of smart people look at it and think very hard. This may be of particular interest because pure math has lately experienced a turn towards the use of proof-verifying systems, and so it may be of some interest if one of these can be designed for cryptography.

In particular, consider the following method of verification: a cryptographically secure function h(M, k), known or at least believed to be hard, a message M, a secret key k, and a channel C(h) over which data is transmitted. We wish to prove the following combination of statements: a: given C and h, a method to obtain the message M also obtains the key k, and b: given M, C, and h, it is "impossible" to obtain the key k -- i.e. it would require breaking the hash function; this means that if the cryptography is broken, so must be the hash function. The latter portion of the proof is necessary because we must always consider the possibility of a rubber hose or a stupid user.

EDIT: I should add here that side channel attacks depend on an incorrect understanding of the content of C. So perhaps we should include c: we send only what we wish to in C.

In the interest of pedantry, I dreamed up an example "cryptosystem" which may fit the bill, though I have no honest idea of the difficulty of the h function [and I know almost nothing about cryptography!]: consider a large prime number p, the finite field F_p, and its algebraic closure Fbar_p. A message M is a [presumaly long] polynomial M(x) over Fbar_p, and a key consists of the pair k = [p, z], where z is some arbitrary element of Fbar_p. h(M, k) is obtained by expanding (x - z) * M(x) in Fbar_p, and we send over C the coefficients of the resulting polynomial. Verification is obtained by computing C(z) in Fbar_p and the message is extracted by polynomial division. Then (a) rests on the difficulty of factoring a polynomial and (b) rests on the secrecy of p: so we cannot, for example, simply compute C/M.

Note that Fbar_p is countable, so the whole procedure uses only integer math.

Along the lines of of your examples, I would add distributed systems.

Still, cryptography is much, much worse than all these examples for a simple reason: with a sufficient amount of testing for functionality you can convince yourself that you've gotten things like concurrency correct, or at least correct enough that it won't be a problem most of the time. You can't do that with security - instead of testing for functionality you have to test for attack resilience, but whereas you know what functionality to test for, you can't test for attacks you don't know about. Furthermore, you can't be correct merely most of the time - you have to be correct all of the time, because if you slip up just once, your adversary will exploit you.

I really don't think there's any parallel.

"Thinking Fast and Slow" tackles this issue.

Doctors who asses xray fotos for cancer usually get feedback ~6 months later. What's worse is they become more confident in their abilities as they age, and subsequently diverge from the standard checklists inexperienced doctors follow. This leads to even worse results from doctors with 10-15 years of experience.

The opposite case is surgeons who gain immediate feedback and generally become better with experience.

Just curious how far the Excel hacker(s) got... Also, have you made any hires from the contest yet?

When you undo the C and C++ merger, how does the list look? They are very different languages, in particularly in that they attract very different people, so it is interesting to know which is actually being used rather than "C/C++".

Is that the number of people working on that level, or the number of people who've finished that level? My guess was the former, but if so, how many people have finished level 6? And if it's the latter, how many people have started level 0 but not finished?

I'm also curious what the stats look like for how long people are taking to complete each level.

Hmm, nobody has tried using Brainfuck yet...

What we really need is a cryptography language, to do for cryptography what SQL does for databases. I should be able to say, "Messages have this form, and they need to be encrypted end-to-end with authentication and without surreptitious forwarding," and have the right components assembled for me. Unfortunately, our understanding of cryptography is not well-developed enough to create such a system, and so we still fumble around and usually produce systems that are vulnerable (did you remember to have a good source of entropy? did you make sure your messages are all the same length? does your system compose well with others?).

The world needs more broken crypto like a dissident strapped to a chair in a concrete cell in South America needs another car battery alligator clipped to their fingers.

How about, if the world really needs more cryptography, the people who bring it to us take the time to become just a little bit literate in how crypto is actually attacked, instead of pretending like they understand it just because they were able to produce intelligible outputs from OpenSSL's AES?

You're using raw RSA. How much practicing have you done of attacks on RSA? How literate are you in RSA? If the answer is "not at all", why are you allowing yourself to use RSA? How is that not negligent?

(I don't know you, or didn't read your name closely enough to detect that I do, so maybe you have done this legwork; in which case, share with us why you think everyone else shouldn't do the same work?)

If you have a crypto heavy app I recommend the fast and easy to use correctly NaCl project.

http://nacl.cace-project.eu

What the world needs is more managers that hire engineers instead of lawyers when someone points out to them that their crypto is broken.

> I would guess that most developers should stay at around level 2 as much as possible, delving into level 3 only when required and never further.

Why would you advocate that people stay away from learning cryptography? They should know as much as possible, they just should avoid implementing it.

Funny story - quite a few years back I was a sysadmin for a company that was compiling their own PHP with a couple of patches. When I asked about it, my co-worker said it was to suppress some warnings that were spamming the logs whenever someone created an account.

Yes, those warnings were telling us that we weren't using an initialization vector (IV, aka a salt) when hashing the passwords. Facepalm. I suppose that demonstrates the dangers of developers thinking they should be diving into level 3), and also the benefit of (my) being aware of more of the theory than we should have been implementing ourselves.

Yes, I filed a bug to start using hashes, re-hash all our users' passwords, and get rid of the patch. This was also well before those massive GPU cracking systems, so everything turned out fine.

There aren't any, learn how the libraries work and use them. I agree with your point, in that respect.

Also, about the cookies, you can definitely have a plaintext cookie saying userid=42, as long as it's signed.

Point by point:

* Despite all the press password hashing gets, bad password hashes are rarely the worst mistakes people make in their applications. I'm glad there's a meme now about using bcrypt or scrypt, but I don't think people should be afraid to deploy password hashing.

* The alternative to signed requests is to credential the requests directly and not build delegation features. Many applications that use signed requests to solve authorization problems are in fact overbuilding; they're in effect building the infrastructure for federated authorization to solve simple point-to-point authentication problems. Just use HTTP Auth and a long random credential.

* You said it right here: just use random tokens to key a serverside session store.

So, I'd suggest those are four bad examples.

But backing your point out a little: so what if you feel like you need to use crypto in your application? Cryptography doesn't get easier just because you want/need it to. I find myself tearing my hair out at the circumvention/liberation tech people, all of whom respond to the same argument with, "so what if the engineering is hard, people need this stuff*. Well, they need it to work, too, don't they?

> * Storing passwords. You can't store them in plaintext.

Why not. Just write upfront on the signup form, "we don't hash or protect your passwords in any way. Do not reuse passwords from other sites. Create a unique password and retrieve it using a password manager."

Password hashing is a losing battle:

* the users who aren't educated enough to use unique passwords are the same ones who will always use a really weak one anyway, and those will always be crackable

* salting is nearly pointless. the GPU killed the rainbow table, the "bad passwords" keyspace is small enough it's easy enough to recompute, and in most hacks I've seen, the database has been compromised together with the source code so the salt is never really secret.

* the first advice after a hack is still always going to be "change your passwords".

> Encrypting cookies. You should store as little as possible in cookies--ideally just a single identifier. But even so, it's very important to make cookies tamper-resistant. You can't, e.g. just have a plaintext cookie that says "userid=42."

Note that you possibly don't want to _encrypt_ the cookie (particularly if it's transmitted over SSL); you certainly want to _authenticate_ it.

I may not care if the user knows that he is user ID 42; I very much care if he's able to tell me that he is user ID 43 instead.

Author here. A good place to start (mentioned in the article).

http://www.matasano.com/articles/crypto-challenges/

Never met any of them in real life, but they seem like good people to me. I've actually used knowledge I picked up from those exercises to fix vulnerabilities in past clients code, and I'm not yet half-way through them.

Try Dan Boneh's crypto course on coursera [1]. It covers quite a lot of ground, both practical and theoretical, and includes programming exercises similar to the matasano puzzles. Without a doubt it's one of the best courses of the dozen MOOCs I've taken. There's also a followup course [2] (I haven't taken it yet personally, but I believe the currently scheduled run will be the first).

Interestingly enough, there's also an upcoming security course (with no date planned yet) which will cover the application programming part of security and will be co-taught by him. [3]

[1] https://www.coursera.org/course/crypto [2] https://www.coursera.org/course/crypto2 [3] https://www.coursera.org/course/security

Roughly a hundred people have implemented a milliseconds-granular timing attack in our crypto challenges. Our challenge isn't totally realistic (in reality, you'd be timestamping as close to the wire as possible, and if you used Python, you'd be using it to postprocess samples you took in C) but I think if you get through it you'll understand why the attack is viable.

Keep in mind that most target applications will allow you to colocate yourself for ~$100; you just get your sampling server onto a VM in the same hosting center.

There are programming environments that don't readily admit to over-the-wire timing attacks. Nate Lawson did a Black Hat talk about this a few years ago. It is difficult- bordering- on- implausible to remotely time memcmp. It's hard to say whether it's going to get harder to carry out this attack as machines get faster, or easier as attackers discover more filtering techniques and better ways of pessimizing execution on target machines.

Is there a repository or central location of the established and well tested solutions for developers to use? Where does one start?

Hi, author here, I'm glad you found it useful!

> I didnt know for example that you can basically extend an MD5ed string and keep the original MD5 value

Thank tptacek for that knowledge, I think I picked it that up in a talk he did that's somewhere on Vimeo (will link to it).

> Then again, I know that MD5 isn't a secure cryptographic hash function so I wouldn't have used it from the start. Nice to know why thats the case.

Nope! I was going to mention in this in the post but removed it to keep things simple: This particular vulnerability is not due to MD5 collisions or MD5 being cryptographically insecure. It's because of the internal mechanism (a "Merkel Damgard Construction") intrinsic to hash functions like MD5, SHA1, SHA256 and friends. Even if MD5 were cryptographically secure, this vulnerability would still present itself if used in the way I described.

Don't mean to nitpick, but with crypto small misunderstandings lead to big vulnerabilities. Hope that makes sense :)

Doesn't matter if it's MD5 or SHA512. You can extend either hash function in the exact same way (http://en.wikipedia.org/wiki/Length_extension_attack)

"a throttle measure built in"

It's my understanding that bittorrent sync uses the latency of the network for such a throttle. Wild hair: a cyclotron-style router roundabout could hold millions of packets "in suspension" for n seconds.

If you do not manage SSL certificate properly (trust only your server's certificate), a MITM attack can break the system easily. Otherwise I don't think you can intercept the signed message if everything is over TLS.

Hi, author here. I would have liked to have made useful suggestions, but having made so many errors with cryptography in the past, I don't really feel qualified to do so.

I do however recommend getting in touch with tptacek and co and doing the crypto challenges. I mentioned this at the bottom of the post.

Edit: re: timing attacks, it helps if you're in the same data centre. I've never personally implemented a timing attack, so I'm hesitant to make any assertions further than that either way.

>Also, out of curiosity, in his timing attack example, the difference in time caused by the string being equal seems like it'd get absolutely swallowed up by the random nature of the universe - do those things actually work in the real world, on real servers with varying loads and numbers of users and network traffic?

You could make each request many times, and then average them together. I don't know how many requests you'd have to make to overcome the random fluctuations though -- probably a lot.

You are of course correct. Thanks! Will fix and rollout once traffic from HN/reddit dies down.

I'm not an expert, but I can see a problem with schemes along those lines. MD5 (and similar) extension attacks also take advantage of the padding added after the thing you want to hash; so eg

Secret: secret Message: foo&bar Let's include the length and hash 'secretfoo&bar13'

What you actually hash is 'secretfoo&bar130x80...padding...0x20'. What the attacker sees as the 'known hash' includes this padding. When you perform an extension attack, the attack message would look like: secretfoo&bar130x80...padding...0x02&evil . At this point you're adding on the length and hashing it, so what you compare with is 'secretfoo&bar130x80...padding...0x02&evil93' ... but the attacker can precompute that hash just as easily as the one with just 'evil' appended.

You could argue that your hashes would be constructed a bit differently (eg make messages that appear to have internal padding illegal; still vulnerable, btw), but the point is - you're still tinkering with the same basic structure, and are likely to make more mistakes. You're better off switching to HMAC for this application.

The attacker just needs to include the updated length, which he can likely calculate since the shared secret is probably the same length for all accounts-even if it is not he only needs it for this request--and he knows the length of the parameters and their values. It would take some guesswork and trial and error to nail it down, and the attacker would have to guess that the length was included in the first place. Assuming he has plenty of time and processing power it is not infeasible. There are a lot of fairly easy things you could add to make it more difficult to attack.

MD4, MD5, SHA1, and all the SHA2 variants use a structure called Merkle Damgard, which does include the message size. Most are vulnerable to length extension attacks. SHA3 (Ketchup) is not vulnerable to length extension attacks, because resistance to length extension was a design criteria for the SHA3 contest.

Edit: Doh, SHA2-224 and SHA2-384 are truncated and aren't vulnerable

> another worry is that what is considered secure today might not be secure tomorrow

If history is anything to go by then what is secure today will definitely be insecure tomorrow. No real solution to this AFAIK. If vulnerabilities in the crypto itself doesn't get you eventually, quantum computing will.

The message extension attack is pretty well known by crackers, which could leave your webapp open to pre-scripted kit attacks that simply crawl the web.

This is a very dangerous question. Thinking like this leads to huge security vulnerabilities in important systems. A better question is "What is the worst thing that could possibly happen if this system were successfully attacked?" If the answer is anything bad, it is probably best to assume someone will try to attack it.

As for the second part of the question, are we talking about the same internet? Because the one I'm on appears to be full of technically savvy people with loads of free time.

Make sure you are using HTTPS exclusively so you aren't vulnerable to Firesheep-style attacks.

Not the way a naive reading of your post suggests, no.

If you add a random amount of time, the timing attack still works; it averages out, the same way network jitter does. What you need to do is make every request take the same amount of time; randomness is not helpful here.

With thousands of tries, you can apparently average the noise out pretty effectively, so timing attacks are very possible.

State of the art multiple years ago was 100ns over LAN (aka datacenter). It's something to worry about. Honestly, I'd be extra paranoid and use a construct that hashes the supplied digest an extra time on top of doing a timing-safe comparison.

SHA2 has the same problems.

So if the attacker can make a million attempts, don't you think that if the hmac calculation has the most variance of all the other moving parts, that it wont give up the secret?