Date: Wed, 25 Jun 2014 08:10:59 +0400
From: Solar Designer <solar@...nwall.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] not bossy

This is getting quite off-topic, but not more so than some of Bill's. ;-)

On Tue, Jun 24, 2014 at 01:20:31PM +0200, Thomas Pornin wrote:
> On Tue, Jun 24, 2014 at 02:55:56AM +0400, Solar Designer wrote:
> > IIRC, a hurdle was that Solaris of the time would clobber high 32 bits
> > of 64-bit integer registers on context switches (the kernel was
> > 64-bit, but userland 32-bit)
> 
> It was the other way round: the kernel was 32-bit, and unaware that
> the userland was doing things with the high halves of the 64-bit
> registers (actually, the kernel was unaware that the registers were
> longer than 32 bits).

Perhaps I didn't recall correctly, but if it were exactly as you describe
there would be no clobbering when running just one process using 64-bit
registers on a UP system.  IIRC, detection of clobbering was needed on
UP systems as well.  I _guess_ the kernel was using 64-bit registers
at least to speed up things such as in-kernel memcpy() and memset(), etc.

> Solaris 7, released in November 1998, was 64-bit aware and removed this
> limitation. The DES-frenzy at distributed.net reached its end on January
> 1999 (the DES-III challenge) so the 64-bit Solaris did not have enough
> time to percolate before people lost interest in bitslice DES
> optimization.

Right.

I was still interested in optimizing descrypt, but didn't have access to
enough UltraSPARC systems to bother with VIS myself (although it'd be
fun).  So I just kept it with C code, which compiled into 64-bit integer
instructions only.

> > While arriving at the absolute lowest gate count (and having any sort
> > of certainty of that) is already intractable for DES S-boxes even with
> > few gate types, an interesting question is whether we likely get
> > closer or stay farther away from that holy grail in practice when we
> > have more gate types.
> 
> As far as I know, Kwan's work for almost entirely manual (that's what
> he told me, at least) so he cannot easily do it again under other
> conditions.

Luckily, there's no need: Roman Rusakov generated more optimal S-box
expressions since, although Roman's work was also a mix of automated and
manual effort (and I contributed to the final selection out of thousands
of same-gate-count versions, by parallelism and register pressure,
which also involved much manual effort).

> Apart from UltraSPARC, a number of other processors have opcodes which
> go beyond the elementary operations corresponding to C operators. For
> instance, Alpha offered the classic NOT, AND, OR and XOR, but also
> ANDNOT, ORNOT and XORNOT.

Sure.  IIRC, Matthew Kwan originally generated sboxes.c for the
"classic" gates only, and he added nonstd.c after I e-mailed him to
suggest that (a bit later in 1998, it was like March vs. May).  IIRC, I
initially confused which exact additional gates were available and
needed to be made use of, but he got it right anyway. ;-)  I was later
running this stuff on my 21164PC throughout 1999 on descrypt hashes.
I haven't powered it up in a while now... although I did re-test with
Roman's improved S-box expressions in 2011 when we were about to release
them, so the machine was still alive then.

Thank you for jogging the memories.

Alexander

Powered by blists - more mailing lists