Message-ID: <20140323172645.GA29626@openwall.com>
Date: Sun, 23 Mar 2014 21:26:45 +0400
From: Solar Designer <solar@...nwall.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Can I have two entries?

On Sun, Mar 23, 2014 at 05:53:19PM +0100, Kriszti?n Pint?r wrote:
> 
> Solar Designer (at Sunday, March 23, 2014, 5:35:55 PM):
> > For non-trivial algorithms, good pseudo-code is not any easier to produce
> > than a machine-readable implementation.
> 
> how about trivial algorithms? btw any algorithm is easier to write in
> pseudocode, especially compared to low level languages like c. i don't
> think there is a real debate about writing pseudocode is significantly
> less error prone than writing actual code. it is pretty much the
> rationale behind using them.

To me, pseudo-code is something half way between "human friendly yet
imprecise" and "machine-readable and more precise".  I'm not sure
regarding these being more or less error prone.  I guess it depends.

> they are also easier to read.

Sometimes.  And yes, I said "human friendly" above, which is about this
"easier to read" aspect.  However, this is not always true.

For example, I find scrypt's crypto_scrypt-ref.c more specific and in
some ways easier to read than the scrypt paper, which contains pieces of
pseudo-code.  Yet the paper is valuable to have in addition to the code,
because it clarifies other things that are not included or not explained
in the one implementation (even the reference implementation).  We need
both.  As to which to require for initial PHC submissions, if I were the
only one to decide, I'd require only the code, accepting specification
documents by a later date (although of course it'd be great if they're
submitted along with the code).

> > It's sort of OK if initial PHC submissions have bugs;
> 
> so what good a buggy reference implementation is? what is the added
> value?

I feel I'd be repeating.  It confirms that the algorithm exists and is
implementable, it allows to test its properties (to the extent the
hopefully minor bugs don't interfere with that), it allows us to better
evaluate complexity and efficiency of possible implementations.

Efficiency is crucial.  We can't compare PHC submissions against each
other without considering their efficiency.

For example, escrypt tries to ensure it's no weaker than bcrypt in terms
of attacks with GPUs, even at low memory settings.  The only way for me
to be reasonably confident of this claim I'm making is to actually run
an optimized implementation of escrypt on current machines and measure
the achieved frequency of random memory accesses and parallel groups of
accesses (two separate metrics) vs. those of bcrypt, and normalize for
the difference in S-box sizes where appropriate.  And guess what, this
goal was not fully achieved initially.  I had to go back and revise the
way escrypt is defined, a few times, until I finally achieved this goal
only a couple of days ago.  I produced several revisions of the
implementation in the process, but this wasn't even a substantial
portion of the effort involved.  Without the implementations, I would
end up making a false claim, or I'd need to give up on this desirable
property (not claim it and probably not achieve it).

Maybe for your PHC submission it's different.  Maybe it has different
goals and claims, where efficiency is somehow not as crucial (e.g., it
might be sufficiently unique in other aspects that it's not directly
competing with any other schemes in terms of attack/defense speed ratio).

Can we end this discussion, please?  You've stated your opinion.  I've
stated mine.  Let's move on.  We got real work to do.  Thanks!

Alexander

Powered by blists - more mailing lists