Schneier on Security

MCD • May 20, 2011 6:23 PM

As cryptographers are stuck with XOR, ADD and fixed rotations and can’t even use s-boxes these days, has anyone ever considered partly replacing mod 2^64 ADDs by mod 2^8 ADDs in cryptographic primitives to further increase algebraic complexity by having 3 different algebraic operations: ADD mod 2^64, ADD mod 2^8 and XOR (= ADD mod 2^1)?

For the MIX primitive in Threefish, I would suggest a small change in replacing the 2/4/8 parallel mod 2^64 ADDs of every odd round number to 8-times the number of parallel mod 2^8 ADDs and keeping the 2^64 ADDs of every even round number as they are.

This way, you get more algebraic complexity for a little less computational resources, because we have exchanged some longer ADDs to some shorter ADDs, which needs less carry ripple time|lookahead-gates|fixed-wired rom space|clock cycles|power depending on what kind of hard- or software you are implementing Threefish or Skein.

You don’t even need to double the minimum cell instance size for extremely low gate count single-round implementations, as you can easily toggle an 64 bit adder into 8x 8 bit adders when using carry ripple adders(usual in such small designs) by just breaking the carry line every 8th propagation bit depending on the last bit of the round counter(needed in such implementations anyways).

Nevertheless, this modification would be a little slower on most RISC CPUs and µC that do not have 8 bit adders, in which case you would need to use a few instructions(2 ands, 1 or, 2 adds, 1 shift for every 8×8 bit adds instead of 1 64 bit add on a 64 bit CPU) to hack around it: old ALPHA before BWX, simple MIPS, ARM, SPARC and PowerPC all without any SIMD extensions and a few whacky integer DSPs. However, the test platform from NIST, the Intel Core Duo and the x86/x86-64 in general, the AVRs and small µCs, the ASIC and FPGA implementations are all not affected by this little performance drawback. The question is whether this is acceptable.

This seems like a great novel idea, but maybe to novel to be applied to a real-world cryptographic primitive without being thoroughly analyzed beforehand. And maybe to late to be applied to Threefish/Skein at this stage in the NIST SHA3 competition.

Just my offhanded thoughts by a cup of tea.