Re: Re: Fwd: little request :)

Hi all, On 6 February 2014 14:24, 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. 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