Timing safety

[solardiz]

Kudos for the impressive results and this very interesting project! Also, let me apologize in advance for reporting the obvious, as well as in case I am missing something about the below; I only looked at the code and didn't actually trigger any of the issues described here. I just felt these concerns needed to be brought up somewhere in here, as people might start actually using this code very soon.

As far as I can tell, the current implementation of the collision detector is not timing-safe, containing conditional branches based on data (and not only when a collision attack is fully detected, which could be acceptable). If this code is meant for actual use rather than just as a proof-of-concept perhaps this should be fixed - or at least it should be documented.

Specifically, there are many "if (mask & DV_...)" in ubc_check.c (coming from sha1collisiondetection-tools/parse_bitrel/parse_bitrel.cpp, so that one should be enhanced and the file regenerated), as well as some relevant if's in sha1.c: sha1_process(). There are also some in ubc_check_verify.c, but since this file is only needed for testing (right?), I guess they're OK to stay as-is (but maybe this is best to document in a comment).

ubc_check_simd.cinc got this right (I mean timing-safe) as it is, so I think parse_bitrel.cpp simply needs to have its SIMD logic replicated for its scalar code generation as well. And sha1.c needs to be edited manually.

For a conceptually similar yet much simpler example (almost trivial), here's my crypt_blowfish bug workaround from 2011, where it deviates from computing the correct hash only when a would-be-collision is detected and does so in a timing-safe manner:

http://cvsweb.openwall.com/cgi/cvsweb.cgi/Owl/packages/glibc/crypt_blowfish/crypt_blowfish.c.diff?r1=1.19;r2=1.20

[cr-marcstevens]

This version of the collision detection library checks if any unavoidable attack conditions are not satisfied to opportunistically skip work. Because of this it can not execute in constant time.

If you need constant time then you at least need to disable unavoidable attack conditions, but may require further code changes, e.g.:
SHA1DCSetUseUBC(&cxt,0);

[solardiz]

Thank you, Marc!

I now see that even if we did make the scalar ubc_check() constant time, it'd be difficult and probably meaningless to make the corresponding code in sha1.c: sha1_process() constant time as well, because it uses ubc_dv_mask to decide on skipping work. By "probably meaningless" I mean that the resulting constant time code would effectively be the same as the case of running with ctx->ubc_check = 0 (as you suggest).

So focusing on the case of ctx->ubc_check = 0 instead, it looks like at least the check ihvtmp[0] == ctx->ihv[0] && ihvtmp[1] == ctx->ihv[1] && ihvtmp[2] == ctx->ihv[2] && ihvtmp[3] == ctx->ihv[3] && ihvtmp[4] == ctx->ihv[4] would need to be changed to a set of bitwise ops, so that the only if would be on an integer expression indicating whether the full 160-bit values match or not. Perhaps it should become !((ihvtmp[0] ^ ctx->ihv[0]) | (ihvtmp[1] ^ ctx->ihv[1]) | (ihvtmp[2] ^ ctx->ihv[2]) | (ihvtmp[3] ^ ctx->ihv[3]) | (ihvtmp[4] ^ ctx->ihv[4])). With this, it looks like we'll have constant time except when a collision attack is fully detected.

For speed, maybe the original check, with its short-circuit evaluation, should be reached instead when ctx->ubc_check != 0.

Related: I guess (and assume above) that ctx->reduced_round_coll is only for testing, debugging, and research, and it's what the comment // to verify SHA-1 collision detection code with collisions for reduced-step SHA-1 refers to (even though it precedes an if statement with two independent checks). If so, it's OK to keep that portion of the check non-constant-time, but perhaps this needs to be clearly documented.

(Of course, C and CPUs don't actually guarantee us constant time either way, but so far the practice has been that bitwise ops achieve it.)

[zbeekman]

@solardiz I have an ignorant question: What is the advantage or motivation for a constant time approach over opportunistically skipping work? Wouldn't a constant time approach end up being slower than the current implementation?

[cr-marcstevens]

Constant time is a requirement for some uses, ensuring no information on sensitive hashed data is leaked via timing discrepancies, particularly during the execution of a network protocol.

The cost of turning off the speedup using UBCs is significant, but may remain unnoticable to the end-user.

[zbeekman]

Thanks for the explanation

…

On Tue, Feb 28, 2017 at 10:32 AM Marc Stevens ***@***.***> wrote: Constant time is a requirement for some uses, ensuring no information on sensitive hashed data is leaked via timing discrepancies, particularly during the execution of a network protocol. The cost of turning off the speedup using UBCs is significant, but may remain unnoticable to the end-user. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#7 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAREPM5GtnkKY1zrs4a4VlhHuN5j1DXCks5rhD4pgaJpZM4MLWVb> .

[solardiz]

@zbeekman The advantage/motivation or lack thereof depends on the use case - in some cases the timing leaks could allow for practically relevant attacks, in many others they won't. Having to consider potential attacks of this sort on a case-by-case basis prevents this implementation from being a universal drop-in replacement to typical implementations of SHA-1. I think that's a major limitation and drawback. It'd be so much simpler and thus better to be able to say that we can always replace this with that and be safe. Not being able to do that universally defeats much of the would-be point of having this collision-attack-detecting implementation: we'd be replacing risk of collisions (and need to evaluate their relevance and risk impact in a given case) with risk of timing leaks (and need to evaluate their relevance and risk impact in a given case), so not necessarily simplifying our reasoning.

Yes, a constant time implementation will definitely be slower. From the code, my guess is it'd be tens of times slower, but we need to benchmark and see. For some use cases, this performance cost is clearly acceptable - perhaps more clearly (that is, easier to reason about) than the risks of timing leaks.

As Marc pointed out, a constant time implementation almost already exists - it's just a matter of setting the flags differently, and making minor(?) code and documentation changes.

I think only minor changes are needed except for the case of actually fully detecting a collision. Making that case constant time as well would require more invasive changes and perhaps generation of different safe mode hashes than the current code produces. Luckily, the probability of false positives is low enough that this can probably be disregarded, except if triggered on purpose - not to produce a collision, but to force a timing leak. That last possibility might in fact be important (at least for the ease of reasoning), so maybe it's worth considering those more invasive changes as well.

[zbeekman]

Thanks for the detailed explanation

…

On Tue, Feb 28, 2017 at 10:45 AM Solar Designer ***@***.***> wrote: @zbeekman <https://github.com/zbeekman> The advantage/motivation or lack thereof depends on the use case - in some cases the timing leaks could allow for practically relevant attacks, in many others they won't. Having to consider potential attacks of this sort on a case-by-case basis prevents this implementation from being a universal drop-in replacement to typical implementations of SHA-1. I think that's a major limitation and drawback. It'd be so much simpler and thus better to be able to say that we can always replace this with that and be safe. Not being able to do that universally defeats much of the would-be point of having this collision-attack-detecting implementation: we'd be replacing risk of collisions (and need to evaluate their relevance and risk impact in a given case) with risk of timing leaks (and need to evaluate their relevance and risk impact in a given case), so not necessarily simplifying our reasoning. Yes, a constant time implementation will definitely be slower. From the code, my guess is it'd be tens of times slower, but we need to benchmark and see. For some use cases, this performance cost is clearly acceptable - perhaps more clearly (that is, easier to reason about) than the risks of timing leaks. As Marc pointed out, a constant time implementation almost already exists - it's just a matter of setting the flags differently, and making minor(?) code and documentation changes. I think only minor changes are needed except for the case of actually fully detecting a collision. Making that case constant time as well would require more invasive changes and perhaps generation of different safe mode hashes than the current code produces. Luckily, the probability of false positives is low enough that this can probably be disregarded, except if triggered on purpose - not to produce a collision, but to force a timing leak. That last possibility might in fact be important (at least for the ease of reasoning), so maybe it's worth considering those more invasive changes as well. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#7 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAREPEGv7yj9bk5FnoqRFFpmMHgM4kEeks5rhEElgaJpZM4MLWVb> .

[solardiz]

Yes, a constant time implementation will definitely be slower. From the code, my guess is it'd be tens of times slower, but we need to benchmark and see.

I had totally missed the paper, which says the performance difference is around 16 times: https://eprint.iacr.org/2017/173

[cr-marcstevens]

For constant-time we should be able to activate the SIMD stuff to get a nice factor back.

[cr-marcstevens]

I've made the constant-time changes to the comparisons.
I'll leave this issue open now for documentation.

[zbeekman]

Will constant time always be enabled, or will there be a separate API and/or build flag to switch between optimized and constant time?

P.S. I forgot (perhaps optimistically) that people might still be using SHA1 for password authentication, HMAC, etc. which is partially what prompted the question about constant time... (I'm not in info-sec, just a hobby interest)

[cr-marcstevens]

This is already a run-time option, see README.
Since constant time hasn't been really tested, we make no such claims.
But I don't see any obvious reason why disabling UBC checks would not be constant time.
Except there is always conditional code when a collision is detected.

/** disable use of unavoidable attack conditions to speed up detection (enabled by default) **/ // SHA1DCSetUseUBC(&ctx, 0);

[zbeekman]

great, thanks, sorry to have overlooked that.

[cr-marcstevens]

No problem, it wasn't very clear.
Also I see I should rephrase the README comment to make clear that disabling UBCs will slow it down significantly.