Message-ID: <CAOLP8p6koNZLK6K7nkF19wTFHwqDsj47WNjG6eCXjdSO9CfHBg@mail.gmail.com>
Date: Thu, 30 Oct 2014 12:39:15 -0400
From: Bill Cox <waywardgeek@...il.com>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Subject: Re: [PHC] Overview of PHC Candidates and Garbage-Collector Attacks

On Thu, Oct 30, 2014 at 11:45 AM, Jakob Wenzel <jakob.wenzel@...-weimar.de>
wrote:

> On 30.10.2014 10:55, Bill Cox wrote:
> > Hi, Jacob.  This is a nice analysis.
>
> Hi Bill,
>
> Thank you!
>
> > You misread TwoCats.  It is easy to do, which is one reason I wrote
> > SkinnyCat, which indeed is vulnerable to both GC and WGC attacks.
> > However, TwoCats has strong defense against both.  I would argue that
> > TwoCats has the strongest GC and WGC defense of all the entries.
>
> The attacks for skinnycat are clear. For twocats, we totally agree that
> it is strong against GC attacks (we just misread that the early memory
> within twocats is always overwritten). But, regarding WGC attacks, we
> still see the attack as described in the paper. According to our
> definition of a Weak Garbage-Collector Attack an algorithm is
> vulnerable, if it maintains a function $F$ with $y = F(pwd)$, where the
> value $y$ is later used in the hashing process. Thus, $y$ has to remain
> in memory during the time until it is used again at the end.
>
> For twocats (and skinnycat), the value $y$ is given by PRK, which is
> initialized with the password. PRK is later used in the function
> addIntoHash(PRK, state). Thus, it has to remain in memory and can be
> used by a WGC adversary to filter password candidates as described in
> the paper.
>
> Did we misunderstood something?
>

Yes, I think so.  addIntoHash mixes state into PRK, not the other way
around, overwriting the PRK.  This inside the garlic application loop.  The
PRK is overwritten much faster than in Catena, for instance.


> > By default, Catena runs with minGarlic == maxGarlic == 18.  In this
> > mode, Catena does not begin to overwrite memory derived from the
> > password until it has finished filling memory.  During this entire time,
> > H(H(key material)) is present in memory.  If Catena tries to use too
> > much memory, this memory might get swapped to disk.  If Catena is
> > running continuously, as it might on an authentication server, with
> > lambda == 3, there is about a 1 in 4 chance that a cold-boot attack, DMA
> > attack, or forced hibernation, will reveal H(H(key material)).
> >
>
> For Catena-BRG, this is indeed an attack which succeeds with a chance of
> $1/(lambda+1)$. Thanks for pointing this out! We will recommend to use
> Catena-BRG with MinGarlic = 1 in the next version of our submission
> paper to thwart this attack.
>

That would slow you down 2X, meaning you would lose another 2X in
memory*time defense against brute-force password guessing attacks.
Instead, please consider doing what TwoCats does, and apply Garlic starting
at 0, but when you get close to the m_cost, just skip ahead and to the last
level of garlic.  This enables your algorithm to trade-off defense against
brute-force guessing attacks vs memory-leak attacks.

I certainly have copied many good ideas from Catena.  It would be nice to
contribute back something :-)


> When considering Catena-DBG (our new instance using a double-butterfly
> graph), such an attack succeeds only with probability of
>         1/((lambda*2(logn-2))+2logn-1),
> which leads to a much stronger resistance in this case. Therefore, we
> plan to recommend MinGarlic = 1 for Catena-BRG and MinGarlic=MaxGarlic
> for Catena-DBG. What do you think?
>

I'll read through it and get back to you.  Thanks for bringing this issue
up.  I do think it is one of the more important things for defense.  OTOH,
it does complicate algorithms...

Bill

Content of type "text/html" skipped

Powered by blists - more mailing lists