phc-discussions - Re: [PHC] Can I have two entries?

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20140323163555.GA29264@openwall.com>
Date: Sun, 23 Mar 2014 20:35:55 +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 04:16:52PM +0100, Kriszti?n Pint?r wrote:
> Solar Designer (at Sunday, March 23, 2014, 4:03:55 PM):
> > I think having an implementation right away is very important.  It shows
> > that the algorithm actually exists.
> 
> but i'm quite sure there are other ways to convince you about it, like
> a good and easy to read pseudocode.

For non-trivial algorithms, good pseudo-code is not any easier to produce
than a machine-readable implementation.  With an implementation, you can
test that it actually works on some machines.  With pseudo-code, all you
can do is review it very carefully, multiple times, with attention to
detail.  Even try to execute it in your brain to test the corner cases
(thresholds, potential off-by-ones).  This process can get ridiculous.
It's easier and more reliable to (temporarily) put assert()s or similar
into an implementation to verify the same corner cases.

> > Test vectors could be postponed, yes, but they are relatively quick to
> > produce,
> 
> they are also notoriously hard to test and debug. having a bug in a
> reference implementation is ... not so good.

Is a bug in pseudo-code in the specification any better?  (I guess it is
if it's said that the reference implementation prevails anyway, but
that's the opposite from the point you're making.)

> > Test vectors are a trivial technicality,
> [...]
> > Implementation is not as trivial, but is important to have right away.
> 
> see the contradiction?

No, just a dependency.  Once you have an implementation, producing test
vectors is trivial.  This does not imply that producing an implementation
_and_ test vectors together is trivial.

> > I can implement that in a weekend (in
> > fact, I readily have implementations of each past revision of escrypt)
> 
> just like i did. but without checking every single corner case, down
> to each and every operations on byte level, considering all the
> different possible architectures, compilers and the like, i would not
> call that a reference implementation, and whatever it produces, i
> would not call test vectors.

You do have a point here.  It's sort of OK if initial PHC submissions
have bugs; it's unrealistic to expect they would not.  Yes, those are
not "test vectors" for anything we'd recommend for actual use yet - but
they are "test vectors in progress" for our own analysis of the
submissions in PHC.

Alexander