Message-ID: <CAOLP8p7SiNMs=W4At_F9eFU-4_JP4Ht2iOSn-ZJSBgMZNE+K4g@mail.gmail.com>
Date: Mon, 14 Apr 2014 15:09:19 -0400
From: Bill Cox <waywardgeek@...il.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] gambit wiki strength

On Mon, Apr 14, 2014 at 12:36 PM, Krisztián Pintér <pinterkr@...il.com>wrote:

>
> i wasn't aware that the wiki is open for editing. not that i want to
> manage anyone's lives, but if i may have a suggestion:
>
> i would not go awry with the editing. i think maintaining the
> information there should be mostly the task of the panel and whoever
> they ask. if someone edits, we need to conform to strict guidelines to
> maintain unified style and phrasing.
>

Fair enough.  I'll stop making edits.  I was just trying to be helpful, but
my writing skills are not at the level the wiki deserves.


> here are some of my, uncalled for, woes, taken from catena page:
>
> "Provably cache timing attack resistant"
>
> i don't think that "provably" adds anything, it is obviously cache
> timing resistant.
>

That should probably be reworded to make it clear that Catena has a proof
of required recomputations for TMTOs.  So far, the only such proofs I've
been able to come up with for other entries, including TwoCats and Gambit,
are motivated from Catena's.  Without TMTO resistance, I do not see how to
insure a cache-timing attack resistant algorithm cannot be attacked on a
massively parallel scale on GPUs.


> "Advanced framework features"
>
> weasel phrase without actual meaning.
>

Fair enough.


> "which have strongly influenced other entries"
>
> did it? which ones? anyway, it is not important.
>

Just for fun, I'll try to list them:

Argon: supports "server relief" and "client-independent update", and cites
Catena paper

Catfish mentioned client-independent update by a different name in the
paper, but didn't code it.

Lyra contrasts it's reverse order to bit-reversal, and adopted a
cache-timing-resistant first loop in what I call a "hybrid" architecture.
 I'm hopeful I might have influenced this decision to go hybrid, but it was
probably Catena.  IIRC, the original Lyra had little cache-timing attack
resistance (like Scrypt), but I could be wrong.

Makwa has "offline workfactor increase" and references the Catena paper.
 Not a clear indication that the idea was from Catena, but the fact that
this feature was included may vs be Catena inspired.

POMELO: has "client-independent update", which is a phrase I think the
Catena paper coined

RIG: Seems to have copied Catena, using almost the same algorithm, with
some changes they likely feel are improvements, like XORing over memory
rather than overwriting.  I would like RIG more if they presented the
algorithm as an improved version of Catena, but they never refer Catena,
except in the Bibliography.  They also renamed most of Catena's features,
and all the variables in the code.  Lambda became "n", for "number of
iterations".  Do they feel we wouldn't notice the similarity if they just
renamed things?  That kind of turned me off to RIG.

TwoCats: I used Catena's client-independent update, client/server relief
API, and was inspired by Catena's strategy for cache timing defense and
having a pluggable cryptographic hash function.  My predictable memory
access pattern in the first loop is a combination of Solar Designer's
sliding-power-of-two window and Catena's bit-reversal.  I was probably the
second-worse offender after RIG in terms of copying good ideas from Catena,
but at least I'm being up-front about it.  Most of the other good ideas in
TwoCats I have to credit to Alexander.

Yescript: The is surprisingly little in the Yescript code that seems
inspired by Catena.  I think Alexander is a fan of client-independent
update, but I don't see support for it in the code.  Perhaps Solar Designer
feels worse about using other people's good ideas than me.  He does have
server-relief, but it's an extended version meant to be nearly compatible
with SCRAM.


> "Advanced TMTO defense"
>
> advanced is a weasel word
>

I wanted to say something like TMTO defense that kicks in hard with even
one less memory location is used.  IMO, no real attacker will ever bother
with a TMTO of any kind against Catena.  There are algorithms like Gambit
that kick in much harder, but at lower TMTO.  I'm not sure how to put that
in a bullet point.


> "KISS"
>
> not sure i would use this term in this context, but also arguable and
> imprecise.
>

Multiple authors list simplicity as a strength.  Catena is not the
simplest, but I think it has about the highest feature set to complexity
ratio.  It is not as simple as Gambit, but it still benefits from ease of
analysis and the resulting confidence we can have in simple algorithms vs
complex ones.  Catena deserves some bullet point for simplicity.


> just my 2c.
>
>
Your criticisms are fair.  Those were all my edits.  I do stink at writing,
so I'll stop trying to fill in bullet points for the strengths of the
various entries.  Most don't have any listed, so I thought even a weak
first attempt would be better than none.

Bill

Content of type "text/html" skipped

Powered by blists - more mailing lists