Re: Re: Fwd: little request :)

Hi Alexander, On Thu, Feb 6, 2014 at 10:24 PM, Solar Designer <solar@openwall.com> wrote: > On Wed, Feb 05, 2014 at 11:20:27AM +0100, Pierre Joye wrote: > > About the timing attack RFC, I have asked for some review and advice > > and here is a useful one already, thanks Alex :) > > > > Please keep him as CC as I do not know if he is on this list. > > Thanks. I am in fact not subscribed, and I appreciate the CC's. > (I also find the "little request" message Subject weird for use on a > public mailing list, but now it's stuck.) > > On Thu, Feb 06, 2014 at 07:57:17AM +0900, Yasuo Ohgaki wrote: > > Another way to protect from timing attack is have a random sleep, but > > this is tricky also. Too short or too long sleep doesn't help. > > Let's not even consider this. Adding random noise doesn't necessarily > prevent the signal from being heard, even if the noise is louder than > the signal. > > There's a related approach, though: blinding. Instead of comparing the > two strings directly, they may be hashed along with some secret input > (may be a newly generated random number) and the hashes then compared. > There are some arguments in favor of this approach when it's implemented > in a scripting language - e.g., if someone were writing code in PHP - > but when we're talking about native implementation (to be part of PHP), > those arguments don't apply. Some references to this approach were in > yesterday's and today's Twitter discussion between @zooko and others, > including me. There were lots of tweets. You may take a look at: > > > > https://www.isecpartners.com/blog/2011/february/double-hmac-verification.aspx > > > http://openwall.info/wiki/people/solar/algorithms/challenge-response-authentication#Timing-attacks > > > https://tahoe-lafs.org/trac/tahoe-lafs/browser/trunk/src/allmydata/util/hashutil.py?annotate=blame&rev=a4a6c02ef8ae2e0edb30bb0051873ffca6af6fc0#L205 > https://tahoe-lafs.org/trac/tahoe-lafs/ticket/2165 > > When the secret component is very low entropy, this attack may work: > > > http://lists.randombit.net/pipermail/cryptography/2011-December/001866.html > > http://lists.randombit.net/pipermail/cryptography/2011-December/001874.html > > @mik235 pointed out that Python 3.4+ already does something similar for > the == operator all the time, by using SipHash and, if I understood > correctly, caching SipHash values along with the strings (just like it's > also done for the lengths). There's no attempt at not leaking the > length. I haven't looked at the code, so this is merely my current > understanding based on @mik235's tweets. > > On Wed, Feb 05, 2014 at 03:00:10PM -0800, Stas Malyshev wrote: > > I'm not sure the issue of hiding length is a real one here. Most crypto > > algorithms would have fixed-length or one-of-the-very-short-list length > > results, and in this scenario it is usually obvious from the app code > > what the hash length would be, at least within very small number of > > options, so I'm not sure how big a deal it is. > > You're right, for most uses it should not matter. > > On Thu, Feb 06, 2014 at 01:06:26AM +0100, Rouven We?ling wrote: > > I may just be blind, because it's getting late. I don't see any integer > division occurring. > > As Tjerk Meesters pointed out, the % operator involves integer division. > This function can easily spend 10x more time doing the (variable time) > integer division than anything else, thereby exacerbating timing leaks. > > > > Is MAX() implemented without branching? Hardly. > > > > It's not (for reference the code is below). I think the impact of this > is reduced by the fact, that unless the length is 0 always the same branch > is used. > > Yes, it will most likely only leak whether the secret's length is 0 or not. > > > I think we should just document this as potentially leaking information > about the length. > > I agree. > > > If we do find ways to reduce this, by all means, we should take them. > > Some of them may involve tradeoffs or in some cases actually make the > timing leaks worse (while reducing them in other cases), so it's not so > simple. For example, this suggestion: > > On Thu, Feb 06, 2014 at 12:06:35PM +0900, Yasuo Ohgaki wrote: > > For example, read few random bytes and add them to get number of > > iterations, then iterate something for the number. Although it's not > > perfect, it makes much harder than nothing. > > This may potentially make the leak even worse: the random noise may be > filtered out given enough measurements, whereas the multiple iterations > may be amplifying the signal. Let's not do something so questionable. > > On Thu, Feb 06, 2014 at 11:51:55AM +0800, Tjerk Meesters wrote: > > Btw, could we use the name hash_equals() instead? This > > function > returns a > > boolean whereas a standard comparison functions return -1, 0, 1. > > Makes sense to me. In the Twitter discussion, it was pointed out that > Tor project actually has a memcmp()-like constant time comparison > function, but ends up using it to compare only for equal/not-equal > anyway. So the extra complexity of supporting 3 possible return values > is not needed. > > Also, I recommend an approach-neutral, purpose-centric function name. > This operation doesn't have to be constant-time to achieve the end goal. > It may as well be e.g. random time, as long as it does not leak info > about the secret via timings. And the approach taken may change in a > future version, as long as the function's properties are retained (or > even improved upon). e.g. Tahoe-LAFS went with timing_safe_compare() > today: > > > > https://github.com/zooko/tahoe-lafs/commit/a79b6927af57dc701af2f9037f11accc324a9cfb > > but you may use a name more consistent with PHP's other related function > names, and also emphasizing that the return value is TRUE if the strings > match (if this is how you define the function to behave). e.g. > timing_safe_eq() or hash_eq(). > > On Thu, Feb 06, 2014 at 01:53:29PM +0900, Yasuo Ohgaki wrote: > > hash_compare() may only compare hashed values as the function > > name imply. If length differs, it may return FALSE simply. (As well as > > wrong type) > > > > This way, we don't have to worry about length leak and constant > operation. > > Hash string length is not a secret. > > Right. > > > If user have 'raw data' (e.g. raw password, > > etc) to compare, make them apply hash function first. > > ... which will leak the length via timing of the hash function. > > More from Twitter, on trying to hide the length (no, that discussion was > not about PHP, but in general): > > <@SteveBellovin> @marshray @tqbf You could, I suppose, "compare" dummy > data to reach a constant length, making sure you match cache line alignment. > > As you can see, after getting rid of the modulo division, we quickly get > to consider how our memory reads pattern differs from what we'd have > when comparing against a sufficiently long secret string. It's tricky. > I've given this problem some more thought and the following looked promising; it would be great to get your feedback on it. Basically, to remove the modulo and MAX(), I've used a combined buffer that's used for the comparison, in two ways: 1. PAD := known (padded with \0 based on given_len) 2. PAD := known CONCAT given The comparison is straightforward because we already know the buffer is at least given_len. Implementations of above can be found here: 1. https://github.com/datibbaw/php-src/compare/master...const-cmp 2. https://github.com/datibbaw/php-src/compare/master...const-cmp-2 Bottom line is that this attempts to compromise memory against time stability. > > Alexander > > -- > PHP Internals - PHP Runtime Development Mailing List > To unsubscribe, visit: http://www.php.net/unsub.php > > -- -- Tjerk