Useless signing?

[tenbits]

Hi Team,
at the #L42 val and mac are already equal strings (in case signing was successful), should they be signed anyway before equallity check?
Cheers, Alex

[natevw]

Thanks, but yes this is intentional. The extra signature is a simple and clean way to avoid timing attacks. (See the last commit on that line, I think it links to a bit more detailed explanation.)

[tenbits]

@natevw, sorry, I missed that thread. Though I assumed, that it was for timing attacks. But in this case double signing is also useless, as sign function returns pattern: ORIGINAL_STRING.HMAC. So back to the line 42, it will be like

return 'MAC.HMAC' === 'VAL.HMAC' ? str: false;

// and when `mac` and `val` are not equal, then from timing view it is the same as just:
return 'MAC' === 'VAL'
// this is again linear comparison same as:
return mac === val ? str : false;

Instead of signing, there should be SHA1 hash created for each val and mac, like

return sha1(mac) === sha1(val)
function sha1(str){
  retturn crypto
      .createHash('sha1')
      .update(str)
      .digest('hex'));
}

Anyway, I would prefer per-charcode comparison function.

---

But this is only my point of view, and I could be wrong.
Cheers, Alex

[natevw]

Uh-oh, you might be right. In that case it's probably time to add in a local constant time helper.

[natevw]

Whoops, no. The attacker has control over val, but mac is simply the first part of that, re-signed with the known-correct secret. The ORIGINAL_STRING in your example is always str on the left and str on the right.

So I'm inclined to leave this as @Bren2010 had it. Before I realized this, I did make up https://github.com/natevw/node-cookie-signature/tree/const_compare but it's code I wish didn't have to be written (or trust some other dependency to provide/maintain/securely publish…) and since AFAICT, it doesn't, I think I'll re-close :-)

Thanks for reviewing this, though, and of course please correct me if I am still wrong in the correctness of @Bren2010's version!

[tenbits]

Hm, and I will continue to insist on uselessness of such approach) Your str_eq_const function is good - it ensures const-timing check. But there is another way (what you actually trying to accomplish): compare hash encrypted strings, but as I proposed earlier, it should be done with real hash encryption - this approach brings not the const time, but the randomness. And the exports.sign method does not provide this: the first part of the output string is always the input string, exactly this I meant under ORIGINAL_STRING.HMAC.

// assume attacker sends this:
val = 'hello.INVALID_SIGNATURE'
// now after re-sign we have
mac = 'hello.VALID_SIGNATURE'

// now to compare this strings at the line 42, sign them and will have
val_signed = 'hello.INVALID_SIGNATURE.FOO_SIGNATURE'
mac_signed = 'hello.VALID_SIGNATURE.BAZ_SIGNATURE'
return val_signed === mac_signed ? str : false

You see what I mean - we have here no const-time check, and no randomness. Additional double signature plays here no role, and wont be compared until real val not eq mac.

With sha1, the values will be:

val_sha1 = "bee92cfd16956c7fa9864845d0b589bd47d972dc"
mac_sha1 = "f838a520bc67ee75a2d79a011dd733b41d330f21"
return val_sha1 === mac_signed ? str : false;
// and now we have that randomness

Any time the hacker modifies vals signature, even when only one char is incorrect, hash is completely different string

val = 'hello.VALID_SIGNATURQ'
val_sha1 = '408e6401686b8715456df97ffcceefb1b0bef81f' 
mac_sha1 = 'f838a520bc67ee75a2d79a011dd733b41d330f21' 

But as I already sad, I can miss something somewhere, or just explain my thoughts not good enough.

Thank you for your patience.

[rlidwka]

Agreed. The general idea is to compare hashes, not signed strings with cleartext part (which attacker has control over). So this:

 return exports.sign(mac, secret) == exports.sign(val, secret) ? str : false;

Should look like this:

 return sha1(mac) == sha1(val) ? str : false;

... and this bikeshed shall be painted purple.

[tenbits]

I understand that this subject is overrated. I was just confused with the code, I assumed that it should be against timing attacks. But then saw, it does nothing against, so decided to ask what is this for then.
In general I think, that there should be some unbelievable conditions for timing attack to succeed, just like this http://www.tau.ac.il/~tromer/papers/acoustic-20131218.pdf

[Bren2010]

/me facepalms

@tenbits, You're absolutely right and I apologize for being so thick.

Probably the best option would be to change to @natevw's constant-time compare branch, or I can write another pull request that works properly (it'll definitely be uglier, though). I maintain that comparing hashes isn't the right way to go, though.

However, as far as I can tell, this line of code isn't even in use anymore. expressjs/cookies is what's used now, which relies on expressjs/keygrip--neither of which I've looked at, yet.

[natevw]

Sorry for the delay, should we just publish my constant-time branch as a bugfix then or is there a slightly-less-ugly approach? It's a bummer require('crypto') doesn't offer something built-in for this stuff!

[tenbits]

From crypto we can use, as was already said, sha1:

   // ...
   return sha1(mac) === sha1(val) ? str : false;
}
function sha1(str){
  return crypto.createHash('sha1').update(str).digest('hex'));
}

[natevw]

That seems cleaner, do you mind submitting a pull request?

[dminkovsky]

Sorry to keep on the bike shed, but why not just use https://github.com/SalesforceEng/buffer-equal-constant-time?—either the module or just copy/paste the code.

[dminkovsky]

I mean why use sha1? Is the implementation of that function always going to be constant time? (sorry, I don't know how sha1 is implemented).

Anyway, a loop seems much simpler: https://github.com/SalesforceEng/buffer-equal-constant-time/blob/a48282ae383e6728d1dea74e2de43e8a8a434326/index.js#L8-L34. Pretty standard stuff, have seen it elsewhere: https://gist.github.com/jtan189/3804290#file-javapasswordsecurity-java-L103-L109.

[tenbits]

sha1 is not about the constant time, but on the contrary - it ensures randomness.

[jtlapp]

Do we know that the faster CRC32 wouldn't suffice? It's less random than SHA1, but how much information can be gleaned from a single CRC byte? I'm just concerned that we may be unnecessarily eating clock cycles.

(Okay, I think I've got it. There are more opportunities for different session values to have equal CRCs than equal SHA1 hashes, making a CRC solution more vulnerable to guesswork. Tradeoffs.)

[jtlapp]

If the purpose is to prevent timing attacks, why aren't you using a constant time comparison? SHA1 is computationally expensive, and you are doing it twice on each request for a signed cookie. I've been testing XOR comparisons with benchmark.js and find them to be constant time on my machine.

Moreover, by comparing the cryptographically random signatures instead of SHA1 hashes, you are forcing the attacker to find collisions in 256 bits instead of only 160. It seems that a constant-time comparison is not only faster, but more secure.

Do constant-time comparisons have a machine-dependence that makes them unreliable? What's the deal?

[jtlapp]

(The reason I ask is that I would like to verify session ID signatures as a means for reducing the impact of DDoS attacks. I'll confirm the ID too, but that may require hitting the database. I want to keep the cost of each invalid request to a minimum by only hitting the DB if the signature verifies. I don't need the signature otherwise. But the more costly it is to verify signatures, the less clear the benefit gained.)