Message-ID: <20150302063849.GA27227@openwall.com>
Date: Mon, 2 Mar 2015 09:38:49 +0300
From: Solar Designer <solar@...nwall.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] PHC status report

Dear Donghoon,

On Mon, Mar 02, 2015 at 07:15:20AM +0530, Donghoon Chang wrote:
> I am sorry for replying late to your above concerns. It took time to
> prepare a note for the answer. (It took time to uproad it  on Eprint.) Rig
> team wrote a note regarding your concern.
> 
> -------- Performance Analysis of Some Password Hashing Schemes (
> http://eprint.iacr.org/2015/139.pdf)

This is very nice, and no problem with the delay - now that this is just
a discussion, and not something related to the PHC timeline, although it
might have mattered to have these results presented so clearly months ago.

Overall, your results look sane to me.  Thank you for the helpful effort!

> In terms of performance comparison, as you can see from the note, our
> experiment shows that Catena is the worst design among the category
> "Catena, Gambit, Rig." from performance perspective. And based on our
> implementation, Lyra2, Rigv2, TwoCats and yescrypt provides good
> performances in a wide range of use cases.
> 
> Nonetheless, the PHC chose Catena as one of finalists due to other reasons,
> though it looks that Catena is not-good choice in terms of performance.
> According to the PHC status report, (
> https://password-hashing.net/report1.html), Catena was chosen by the
> following reasons.
> 
>    - Well-motivated design, convincing theoretical framework
>    - Well-understood side-channel and TMTO resistance
> 
> But, in the PHC status report it was not mentioned that Catena seems to be
> one of slowest designs compared to others. See  Fig. 1 of
> http://eprint.iacr.org/2015/139.pdf. Actually, among 8 designs we
> considered, our experiment comparion shows that Catena is the wost among 8.

I counted 7 of them there, but yes.

> I just want to know whether the PHC panel already knew the negative aspects
> of Catena from the performance-perspective.

I can't speak for the entire panel, and I am posting this without having
discussed it with other panel members.

I think the performance difference between Catena and Rig was not
emphasized enough in past discussions, neither public nor private.

In hindsight, my own assessment is that performance in the cache-timing
resistant category was not considered in finalists selection to an
extent it deserved.

I can't speak for others, but personally it didn't occur to me to object
on performance grounds to the preference for Catena for a combination of
these reasons:

- Cache-timing resistance has a "practical" security cost, so I view all
3 of these schemes as favoring "theoretical" vs. immediate "practical"
security aspects.  (I acknowledge that there are some scenarios, which
might become more common in the future, where the lack of cache-timing
resistance has practical security cost, too.  And I'd like to thank
Krisztian for reminding us of these on several occasions.)  In other
words, these schemes are (arguably) meant to be conservative.  In this
light, it does make sense for a candidate in this category to please its
current supporters by being conservative in aspects other than
cache-timing as well, such as in use of a full round count primitive.

- I did not realize the performance difference between Catena and Rig
was so large.  If I were to participate in the pre-discussion voting, or
if Catena and Rig came close, possibly I would have looked into this
closer, but when the overwhelming difference in support (in favor of
Catena) became apparent I'm afraid we didn't have enough motivation to
perform analyses like this.  (To avoid having the votes biased towards
a prevailing opinion, the votes were initially collected in private by
JP and only posted to the rest of the panel when the voting finished.)

- I have relatively little interest in and familiarity with this
category.  (And my guess is that those panel members who are more into
it are mostly also the ones who favor other criteria over performance,
especially when applied to this category.  This is similar to my own
first point above.)

> If the PHC panel knew it, I
> want to know why in the PHC status report it was not mentioned, only with
> full of praises for Catena!
> 
> *Emphasize that This mail is not for blaming Catena design, but for
> pointing out that it seems that the PHC status report was written with
> biases!*

That's simply because of the general decision to list only the criteria
for selection of finalists, and (with minor exceptions) only for
non-selection of non-finalists.  Whether this was the right thing to do
was debated (within the panel before the report was finalized), but we
ended up doing it in this way because we didn't appear to have the
resources to produce a balanced report listing both advantages and
drawbacks of every candidate considered (and also because the report
should primarily have reflected the selection).  This isn't specific to
Catena in any way.  We're aware of drawbacks of other finalists as well,
and of advantages of some non-finalists.  The paragraphs leading to the
lists of finalists and non-finalists acknowledge this.

> On the other hand, let us see the case of non-finalists. As one example,
> see the PHC panel's evaluation on Rig case.
> 
>    - Similar to Catena, but received less attention (cf. bugs found in the
>    specification and code)
> 
> "Bugs found in the specification and code" is NOT true in the second
> version of Rig, which was accepted by the PHC panel.

Yes, Rig update was accepted and was considered along with other
submissions after that point, but Rig already ranked poorly by that time
and there was no policy to require panel members to reconsider their
assessment of a candidate whenever an update was received and accepted.
So bugs in the earlier version did affect the non-selection.

> I personally do not want to ask why Rig was not chosen, but I want to ask
> to the PHC panel why the evaluation on Rig was very poorly written without
> mentioning any good points of Rig.

Already answered above, in Catena context.  You are likely to find this
answer unsatisfactory, but it is a true one.

> I personally do not want to ask any kind
> of praise on Rig. But, I believe that the PHC panel, as the name of the
> world-wide competition panel, though the PHC panel members have own jobs,
> "has to" provide a much better report with more evidences based on facts.
> 
> I, personally, humbly request to the PHC panel to provide a better report,
> please!

Thank you for your reasonable request.

I think the current status report, with all of its shortcomings, is
reflecting the panel's decisions in selecting the finalists.  A report
that describes the finalists' properties in a carefully balanced manner
might at the same time be worse at reflecting the selection.  Subjective
criteria such as many panel members being convinced by one design and
not by another did play a role, and arguably they should have.

A report from the PHC panel that would compare the PHC candidates based
on the currently available information, but would not reflect the
selection, would make sense to me - as an additional report, not a
replacement for the current status report.  Realistically, though, I
don't see the panel putting effort into this now (especially given that
this didn't happen when it mattered more).

I can see how the current status report claiming "bugs found in the
specification and code" reflects on Rig v2 badly and unfairly.  Given
that this was among the things that resulted in Rig's non-selection as a
finalist, perhaps the wording should be adjusted to e.g. "bugs found in
the initial specification and code"? or "pre-v2" in place of "initial",
to be more specific?  What do you think?

Thanks again,

Alexander

Powered by blists - more mailing lists