Fixes for Timing and Brute Force Attacks.

[Bren2010]

The way you unsign cookies currently allows attackers to derive correct MACs for arbitrary values in significantly less than 1 day with a timing attack. They can do this because JavaScript's == operator works on a byte-by-byte basis, and they can determine which bytes of the MAC are correct and incorrect with high probability.

The way I've fixed this is by using the digest twice in comparison, so that an attacker can't determine on which byte the comparison has failed. There are other commonly accepted ways to do this, but I don't think that they would be more efficient or take less code.

Also, for simply brute forcing the MAC, the attacker has a probability of success of 1/(2^256) and an unlimited window of time to succeed. That's why I've bumped up the algorithm from sha256 to sha512--to further discourage such things.

Sorry if I seem like I'm bringing up little issues on a dead project, but these are incredibly dangerous attacks to larger websites that use this package through Express.js. =)

[Radagaisus]

@visionmedia can you address this?

[tj]

great thanks for the fix, sorry for the delay somehow this didn't get into my notifications

[tj]

yeah may have to revert this we're seeing strange race conditions

[tj]

reverted and published express 3.2.0

[tj]

hmm digging into this more, for us at least the session problem seems to be persist after reverting this

[rlidwka]

-1 for sha512, even 64 bits is enough to prevent dumb brute force over an internet. 128-256 bits could be necessary if an attacker tries to retrieve a secret using more advanced attacks, but 512 bits is just a waste.

As for timing attack, I just spend a few hours trying to figure out if it is possible or not, and only thing that I managed to find out is that I hate this kind of cryptography. So I just wanted to ask your opinion about that. :)

Do you have any test to determine if javascript/v8 is prone to timing attacks?

[Bren2010]

Actually, playing with the various hash sizes to compare with here shows that 128 is now considered insecure by most standards, and 256 is only considered secure for the near future. 512 was the next highest option.

Finding implementation-specific attacks is less important than finding attacks that could work on a given implementation, and attacks like this have shown up in other languages in the past. However, Dan Boneh has published a related paper here where he does carry out similar attack.

What do you mean 'this kind of cryptography'? :p

[rlidwka]

Actually, playing with the various hash sizes to compare with here shows that 128 is now considered insecure by most standards

It is completely secure against simple brute-force (which is presented as a threat model above).

and attacks like this have shown up in other languages in the past

Yup, but it still says nothing about javascript.

What do you mean 'this kind of cryptography'? :p

This kind. When you look at a numbers 97523833, 98689406, 98604523, 98797831, 98719864, 98575418, 98256335, 98350370, 98170658, knowing that each one of them represents a a median from 100 million experiments with all the noise supposedly filtered out. Note that first one is always lower, which means garbage collection is doing it's job screwing the results over randomly. Which one of them has difference in first character? Will an attacker be able to determine that? Yup, that kind of cryptography.

[Bren2010]

It is completely secure against simple brute-force (which is presented as a threat model above).

If you looked at the official and recommended standards, you would see that the minimum hash size in bits for security is as follows:

Name	Size
Lenstra / Verheul	160
Lenstra Updated	154
ECRYPT II	160
NIST	224
ANSSI	200

...

And you may notice that all of those are above the size of 128 bits, because 128 bit hashes are no longer considered cryptographically secure.

Yup, but it still says nothing about javascript.

JavaScript implements the equality operator the same way every other language does: through the operating system. So yes, it does say something about JavaScript...

[rlidwka]

If you looked at the official and recommended standards

I was answering to this sentence: "Also, for simply brute forcing the MAC, the attacker has a probability of success of 1/(2^256) and an unlimited window of time to succeed."

1000 requests per second seems reasonable enough for bruteforce attack? It would be roughly 2^42 requests in 100 years, so an attacker very likely die before he would break 64 bits.

But as I said before, in order to protect against more advanced attacks (namely, differential cryptanalysis), you might want to use 128 bits and above depending on an algorithm you choose. For example, I'd bet that rmd160 is more secure than sha256 because of two generators running at the same time. An amount of bits doesn't really matter that much.

If you looked at the official and recommended standards, you would see that the minimum hash size in bits for security is as follows

Yup, all the standards specify length 160-256. so your suggestion about 512 bits looks really awesome. </irony>

And you may notice that all of those are above the size of 128 bits, because 128 bit hashes are no longer considered cryptographically secure.

And there's another thing you seem to be forgetting. Standards are supposed to be some kind of a generic thing to be used mindlessly anywhere. But we're using HMAC here, and it has specific attack patterns.

For example, you can't really use 128bit hash in digital signatures because you'll get a birthday attack with only 2^64 complexity. So somebody would happily send you two different documents with the same signature which is a bad thing. That's why standards can't really recommend 128bit.

But it doesn't matter here, because as long as server key is kept secret, best attacks are much more complex than that. By the way, HMACs usually do double encryption, therefore even if you break underlining hash function, it won't be enough.

JavaScript implements the equality operator the same way every other language does: through the operating system. So yes, it does say something about JavaScript...

Operating system has nothing to do with it. stdlib does, but I'm not sure v8 uses that in this particular case.

Anyway, I wasn't able to reproduce this attack reliably myself, that's why I asked for tests. If you can't even show a difference on a local computer, worrying about somebody doing the same with all the noise your app does over an internet seems not very productive thing to do.

Just how many nanoseconds is the difference between comparing two different strings and two similar ones? That's the question I can't find an answer for.

[Bren2010]

This really isn't important, and it never has been, which is why I let it rot for... 9 months. No offense, but you clearly haven't studied cryptography very extensively and this is getting tired. Needless to say, I don't have any interest in continuing.

No need to resurrect the dead. :p Thank you for your interest, though.

[rlidwka]

No offense, but you clearly haven't studied cryptography very extensively

Well, at least I don't suggest to protect against brute forcing a 256-bit number over a network.

Needless to say, I don't have any interest in continuing.

I still have, so if anyone can show any tests proving that node/v8 is prone to timing attack, I'll be very much grateful.

[natevw]

Would using the built-in crypto verify helpers be a better alternative to this patch's method of avoiding timing attacks?

[Bren2010]

@natevw No, I'm fairly sure not. Verify is for signatures (asymmetric, by definition). This is an HMAC, which is symmetric. Verify might have some secret magic for HMACs, but I don't see that documented anywhere.

[natevw]

Ah, k. Shame node.js crypto doesn't seem to have a fixed-time comparison. Seems like I had seen something, but must be remembering Python or something. Not hard to implement, although I guess you never know what some optimizer's gonna do so it's nice to have something "official"…anyway, the OP probably had a good solution then.

Would be nice to get it unreverted, is there any particular reason why Etherpad couldn't handle that?

[rlidwka]

Ah, k. Shame node.js crypto doesn't seem to have a fixed-time comparison

Node.js crypto is more or less thin wrapper around OpenSSL library. If openssl does have this, it would be easy to add it to node.js crypto.

(removed, see below)

is there any particular reason why Etherpad couldn't handle that?

Etherpad issue is unrelated to timing thingy. It happened because somebody thought it was a good idea to change sha256 to sha512 (considering that even bitcoin is perfectly fine with sha256, lol). It was definitely a bug in Etherpad though.

[rlidwka]

Oh gosh, here I am again spending hours trying to make a timing attack work.

All right, this is proof of concept that v8 string comparison is prone to timing attacks: https://gist.github.com/rlidwka/7334175 .

This is an attempt to break node-signature: https://gist.github.com/rlidwka/7335696

Output described below has a following format. First number is a position where expected hmac and submitted hmac differ. Second number is an average time in nanoseconds script executes, and an array contains 5-quantiles.

When the output of the last script will produce results that are in perfect order vertically, you can be sure that a code is vulnerable to timing attack. For example, this is v8 string comparison without any openssl stuff attached:

| 10 3002383 [ 2395349, 2705458, 3097018, 3251824, 6689893 ]
| 15 3279719 [ 3032376, 3051084, 3294605, 3624598, 5547536 ]
| 20 4222771 [ 3756009, 4057681, 4282280, 4335509, 6388672 ]
| 25 4589714 [ 4280940, 4350486, 4600462, 5023399, 6586360 ]
| 30 5889997 [ 5493294, 5656721, 5918552, 6168720, 7635889 ]
| 35 6775090 [ 5111281, 6419308, 6885680, 7023605, 7271953 ]
| 40 6952325 [ 6612243, 6666798, 6996075, 7360266, 7916661 ]
| 45 7240008 [ 6860779, 7071495, 7170988, 7507104, 8690445 ]
= iterations: 8000000 , time= 0 sec

"3002383, 3279719, 4222771, 4589714, 5889997, 6775090, 6952325, 7240008" <-- wow, perfect order, time of v8 string comparison is not fixed. Q.E.D.

This is comparison done by this module after openssl hmac. Note that string comparison take less than 0.1% of the entire time 'cookie-signature.unsign' executes.

| 10 1233861944 [ 1222343398, 1228834954, 1233349839, 1239528943, 1284708105 ]
| 15 1236123547 [ 1220491812, 1228549994, 1235290967, 1244667391, 1320477543 ]
| 20 1235465677 [ 1222250143, 1228906166, 1234781660, 1242866814, 1277247677 ]
| 25 1233900273 [ 1218440454, 1226059769, 1232803590, 1243045329, 1323427112 ]
| 30 1236021402 [ 1221344253, 1229267911, 1234739928, 1244220475, 1304768862 ]
| 35 1236402262 [ 1220555482, 1228761708, 1235656109, 1244971026, 1308658256 ]
| 40 1236312632 [ 1223483076, 1229700208, 1235258425, 1244177703, 1289753370 ]
| 45 1236068410 [ 1220372333, 1229002048, 1233455709, 1246031718, 1320708979 ]
= iterations: 84000000 , time= 1046 sec

Too much noise. Damn. I'm not even sure my code works right. If I can't do anything locally, how an attacker would to the same over a network?

Finally, I monkey-patched node.js crypto, so openssl don't get called. Here is a gist: https://gist.github.com/rlidwka/7336075

| 10 373613465 [ 367961153, 370709506, 372968420, 377184204, 388490849 ]
| 15 376515838 [ 369744450, 373338954, 376610790, 379579083, 390071956 ]
| 20 376798023 [ 371808021, 374045838, 376414415, 379941350, 396790089 ]
| 25 377399901 [ 372508928, 374571995, 376993361, 380623172, 388500420 ]
| 30 378391352 [ 373125801, 375687006, 378192093, 381276141, 396194878 ]
| 35 378961906 [ 372297593, 375945512, 378713753, 382221469, 394693488 ]
| 40 381075882 [ 374122878, 377976434, 381098405, 384172277, 399591680 ]
| 45 380622112 [ 376079810, 378085564, 380213448, 383569191, 393783017 ]
= iterations: 536000000 , time= 203 sec

I guess if you remove all the noise caused by openssl (I didn't even measure network delay), this attack will actually be possible.

PS: all right, in theory there is a exploitable flaw in it, so it'd be nice to fix this. But I wouldn't worry too much about this being in my application, it's easily billions of iterations there.

[natevw]

Thanks for testing, very interesting results. Skimming through the paper, it seems the authors might be dealing with a more significant timing difference, but the title is Remote Timing Attacks Are Practical.

Also, keep in mind there's a lot of people deploying Express/Connect/node.js apps to say, Heroku or directly on AWS where anyone can launch a machine in the same infrastructure — so it'd be easy to collect timings using a network interface just a switch or two away from the target.

[freewil]

Can this patch be further improved using a constant-time string comparison?