Message-ID: <20150211202716.GA8512@openwall.com>
Date: Wed, 11 Feb 2015 23:27:16 +0300
From: Solar Designer <solar@...nwall.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] PHC status report

Edit: I wrote the below before I saw Donghoon's follow-up posting, and
JP's and Samuel's replies.  In fact, I am sending this without having
carefully read those newer postings yet.

Hi,

This is my personal reply.  Not speaking on behalf of the entire panel,
even though I (obviously) do refer to the panel as "we" here.

(In fact, the same applies to my other postings in here, so I will omit
this disclaimer from this point on.)

On Wed, Feb 11, 2015 at 09:16:30PM +0530, Donghoon Chang wrote:
> In the beginning of the competition, the criteria were clearly mentioned
> from the following link.
> 
> https://password-hashing.net/call.html
> 
> However, as mentioned from another following link, when 9 candidates have
> been recently selected, new criteria, which are totally unrelated to the
> original ones, were added.
> 
> https://password-hashing.net/report1.html
> 
> The two new criteria are added as follows:
> 
> 1. Elegance of design

To me, this one is closely related to the "Simplicity" criteria listed
on the call for submissions.  Specifically, I think "Overall clarity of
the scheme (design symmetries, modularity, etc.)" and "Use of other
primitives or constructions internally (the fewer, the better)" (from
the call for submissions) are consistent with "Elegance and simplicity
of design" on the status report.

> 2. Originality and innovation

The call for submissions also says: "Submitters are encouraged to
propose innovative constructions [...]".  While this is said (right)
below the bulleted list of criteria, rather than explicitly included
among them, it is nevertheless right there in the same text.

> I wondered who added these new criteria, which were never mentioned before,
> without the request of any permission of changing it internally and
> publicly.

IIRC, this wasn't specifically discussed, but as far as I'm aware we
listed "Originality and innovation" as an explicit bullet point on the
report after examining past discussions and the rationale given by some
panel members in favor of some candidates.  In particular, Makwa was
selected in part for its "Unique design supporting delegation" (quoting
the report), and Parallel in part for "Original distinction of
sequential vs. parallel cost".  Also, a panel member found some aspects
of Schvrch innovative, which worked in favor of this submission, but
obviously not to a sufficient extent for us to select it (as it has
fatal shortcomings).  These are 3 occasions that I recall.

... Oh, with grep I just found 4 more occasions, for 4 other candidates
(not affecting the final selection, as it happened).  So yes, some panel
members were considering this aspect, along with many others.

I see nothing wrong in us "promoting" an "encouragement" into a bullet
point when listing the selection criteria on the report.

> Due to the above new criteria, some of the candidates were not selected.

This doesn't match my understanding.  While any of the listed criteria
could have resulted in a candidate (not) getting selected, in this
competition I think only the selection of Makwa and Parallel was
(positively) influenced, and not at the expense of not selecting any
other candidate (since these two had no direct competitors).

I guess you might be referring to Gambit's and RIG's "similarity to
Catena" (as per the report), but the similarity isn't a drawback per se.
(Note that for the non-finalist TwoCats, the report mentions
"Interesting mix of ideas", which obviously is not a drawback as well.
For all three of Gambit, RIG, and TwoCats the phrase starts with
"<Something OK>, but ...")

Rather, the panel's assessment that Catena, Gambit, and RIG compete for
the same use cases and are using similar defenses provides a baseline
for comparison.  Gambit and RIG didn't appear to have significant
advantages over Catena while appearing less mature (and Gambit had what
many considered a drawback: Keccak).  That alone is sufficient for the
panel to prefer Catena over them, without the (possible) lack of
"originality and innovation" playing enough of a role to affect the
(non-)selection.

Basically, if you wanted to convince the panel to select Gambit or RIG,
you needed to make a clear case on why you think(?) they're more
suitable than Catena.  Well, or someone else could have.  As they were,
they appeared somewhat less suitable.  Similarly, Catena would benefit
in the competition from having comparisons showing it being in some ways
more suitable than Gambit and RIG.  Luckily for it, the panel felt that
way as-is, due to Catena's maturity and Gambit's use of Keccak.

(I hope it's OK for me to address Gambit and RIG at once like that.)

> Directly speaking, the new criteria were secretly created, which is against
> the rule of competition, to kick out those candidates,

I can see how you could arrive at that conclusion, but I don't share it.

> which is unfair

Maybe it would be, or maybe not.  I wouldn't see much of a problem in
the panel making unanticipated decisions, if we had to, and announcing
them (the earlier, the better - but obviously they can't be announced
before being made).

> and even a crime.

Now you're crossing a line. :-(

> Another main issue of the PHC is that 9 candidates were chosen without
> providing comparison results with proper metrics, which are against all
> other competitions such as AES, SHA-3, Caesar Competitons, etc. The
> competition should be scientifically based on proper metrics with clear
> comparison (not based on voting out of favoritism), according to the
> criteria which were given in the beginning.

I think PHC is rather unique in that:

1. The performance ratio on defenders' systems vs. ASICs can at best be
guesstimated, yet needs to play a role in selection.

2. The implementations submitted so far are often very far from optimal,
and in fact a submitter complained that we were asking for any
implementations at this time at all.  Just where would the optimized
implementations for a fair comparison necessarily come from at this
stage in the competition?  And how confident would we be that similar
effort went into optimizing one vs. another?  And that they got
similarly close to being optimal?  Ditto about attack-optimized
implementations, for multiple platforms.

3. TMTO affects the performance ratio, but there's no confidence in how
close to an optimal attack for a given scheme we have arrived.

4. This is first such competition, and it appears to receive less
attention than AES and SHA-3 so far, and with lower "stakes" by the
submitters too.  (It may be a good thing that the stakes are lower,
given the accusations you make.)  Hence, less incentive for the
submitters and for third-parties to produce multiple optimized
implementations for various platforms.

I hope that now that we have 9 post-tweaks finalists instead of 24 or 22
pre-tweaks candidates, these 9 will receive extra attention, including
more implementations for us to benchmark.

You, the submission authors, could have done your part in providing more
performance comparisons.

If we were judging by performance numbers of current implementations,
with "non-performance" criteria not considered, we could probably select
TwoCats as the winner now.  A very good candidate in my opinion, but
not to the exclusion of all others, which have other good properties.

Overall, I think some subjective judgment by panel members was needed.
Even if we could have near-optimal performance numbers for current
hardware platforms (both defense and attack), we'd need to extrapolate
into the future - and that's subjective.

> Since I was one of internal evaluators of SHA-3 candidates as a guest
> researcher of NIST for three years, it more seems to me that the procedure
> of the PHC looks immature to me.

Being the first such contest, it isn't mature.

> Even the PHC panel's recent selecting
> procedure undermines the dignity of the PHC, the PHC panel, submitters, and
> even crypto community. Please think it seriously.

This is a rather strong statement, but let's keep in mind that this
bitterness comes from a non-finalist co-author.  It is understandable as
such, given the unfortunate shallow evaluation of some submissions and
the brevity of the report.

It is unclear what a better selection procedure would be.  I gave some
reasons above why "a scientific comparison using proper metrics"
wouldn't have worked at this stage with the effort the submitters and
third-parties have invested and the panel could afford to invest, and
why it couldn't have been the only input to the decision-making anyway.

Do you have a suggestion that would actually have worked?

> I hope that the PHC panel might accept and correct their mistake and make
> every effort to restore our dignity including everyone participating in the
> PHC.

Do you have specific suggestions?

Here's mine: discuss everything on the public list.  Given you having
crossed the line, this is starting to feel a little dangerous, though. ;-)

Alexander

Powered by blists - more mailing lists