Hi all,
On 6 February 2014 14:24, Solar Designer <[email protected]> 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.
Random noise is random. We're talking about attacks over a network -
if folk can resolve network jitter to a resolution of mere
nanoseconds, dumping another random element on top of that isn't going
to do a lot. They can always increase their sample size to compensate.
It just doesn't anything worth pursuing.
> 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.
And for uses where it does matter, one has to wonder WHY it matters.
If I figure out a secret is 32 bytes long, I still have that many
bytes to guess without assistance from a comparison timing leak. So
where does a leaky length cause problems? Short secrets? Low entropy
secrets? I suppose one could use the length leak to ascertain the
hashing function used, but again it should be a strong hashing
function for a secret and if it's not - it should be fixed.
> 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.
Agreed.
>> 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.
It's a case of the more work you try to do, the more leaks you can end
up accumulating ;). Has anyone reviewed what Symfony are doing out of
interest? I see this noted as length leak proof but I'm not qualified
to examine the underlying C ops.
--
Pádraic Brady
http://blog.astrumfutura.com
http://www.survivethedeepend.com
Zend Framework Community Review Team
Zend Framework PHP-FIG Representative