[cryptography] 17% smaller DES S-box circuits: 44.125 and 32.875 gates per S-box

Solar Designer solar at openwall.com
Wed Jun 22 20:06:32 EDT 2011


Hi,

We've just released those, as part of John the Ripper 1.7.8, but freely
licensed for reuse anywhere else.  Our understanding is that S-box
expressions themselves are mathematical formulas and thus are not
subject to copyright.  The specific code implementing them is licensed
under a heavily cut-down BSD license (no restrictive clauses).

Roman Rusakov and I have been working on this for a long while, with
Rapid7's sponsorship.

The primary idea was Roman's, and he did all the work to generate the
S-box expressions (which took months on his overclocked water-cooled
quad-core machine with 24 GB RAM).  My humble contribution was code
generation and feedback to Roman such that we'd have not only the
smallest gate count, but also decent program code (not requiring too
many registers, reasonably efficient on 2-operand architectures, yet
containing inherent parallelism).  In the end, we had thousands of
same-gate-count "circuits" to choose from for some of the S-boxes and
some of the target instruction sets.

For AND, OR, XOR, NOT, and AND-NOT gates (MMX/SSE2/AVX, typical RISC CPUs):

Gate counts: 49 44 46 33 48 46 46 41
Average: 44.125

Previous best result: 53.375 (or 51 with XNOR gates), by Matthew Kwan

For "bit select" gates (Cell, PowerPC with AltiVec, AMD XOP, high-end
ATI GPUs):

Gate counts: 36 33 33 26 35 34 34 32
Average: 32.875

Previous best result: 39.875, by Dango-Chu

More detail:

http://www.openwall.com/lists/john-users/2011/06/22/1

Collection of previous results:

http://download.openwall.net/pub/projects/john/contrib/bitslice-des/

I'd appreciate any comments, and once again - feel free to use/reuse.

Thanks,

Alexander



More information about the cryptography mailing list