10
$\begingroup$

Modern computers (which crypto programs are usually run on) have a 64-bit multiply, and it only takes one cycle. It's pretty decent mixing at next to no cost.

For block ciphers:

Multiplication by a constant is nonlinear (when combined with other mixing operations), provides diffusion in one direction (easily amended with a rotate), is bijective (necessarily), and is as fast in both directions (with precomputed inverse).

For hashes:

With no need to efficiently reverse the permutation, it is safe to use polynomials (ones that aren't linear). They provide even better mixing and can mix more than one value at a time. If bijectivity is not important, the full 128-bit multiply result can be used, for example by xor-ing the low and high words. Otherwise, rotates should be in there somewhere so the high bits can affect the low bits. It is somewhat costly, but still less costly than what would provide equivalently good mixing with only "lower level" operations. Simple example: a^=(b&~c)<<<7 can be replaced with a+=(b*~c)<<<7, which imposes no extra cost and mixes better most of the time.

I'm sure there's other potential uses for multiply, but those are the first two I came up with.

So, why is multiplication uncommon in cryptographic primitives? Sure, AES and SHA3 are designed to be hardware friendly, but what about all the others? Especially the ones designed for software implementations.


RC6 uses a multiply, though not for the usual purposes, "usual" meaning "like every other block cipher".

$\endgroup$
15
$\begingroup$

There's at least 5 reasons why multiply is not more often used in symmetric ciphers and hashes:

  1. For use as mixer, multiplication requires more hardware/energy/time than other hardware constructs of comparable cryptographic interest. This is an argument mostly for hardware implementations, but many ciphers (and a few hashes) are designed so as to be fast in hardware (that was the explicit implementation target for DES, and an explicit target for AES, which often is in hardware nowadays).
  2. It is far from universal (and used to be uncommon) that wide multiplication is single-cycle, and the number of cycle(s) listed might not be the end of the story; often there is latency, and that cost extra cycles if the result is used for the next few instructions (for x64 otus pointed this source, the same applies to some ARM).

    Worst there is often timing dependency on one operand (opening an avenue for timing attacks), and no way to control which operand from the comfort of a high-level language (other than by forcing some high-order bits in both operands). For example, the common 32-bit ARM Cortex M3 has UMULL (32x32->64-bit result) documented as requiring 3 to 5 cycles, with

    early termination depending on the size of the source values.

  3. Multiplication only does bit mixing to the left: if $C=A\;B$ then bit $C_j$ is independent of bits $A_i$ and $B_i$ for any $i>j$. Fixing this requires computing the product with more precision than its operand (and some post-processing), which might not be fast/easy in high-level language.

  4. Multiplication by a constant is linear, and ciphers require non-linearity. While some derivatives of multiplication (like squaring) are not linear, multiplication as the sole source of non-linearity could open to algebraic attacks.
  5. As pointed in comment, when truncating the result of a multiplication (effectively working modulo some power of two), $F_A: B\mapsto F_A(B)=A\;B\bmod 2^k$ is a bijection only for odd $A$, and can loose a lot of entropy for other $A$, which is undesirable in a normal mixer.

The only widely used cipher I can name that heavily uses multiplication other than by constant is IDEA, where it is followed by modular reduction modulo the prime $2^{16}+1$, in order to fix issues 3 and 5.

Multiplication is in wide use in asymmetric cryptography: RSA, DSA, Elliptic Curve cryptography over a prime field..

$\endgroup$
  • 9
    $\begingroup$ Two AES finalists used multiplications not by constants: RC6 and MARS. The eSTREAM finalist Rabbit does as well. Today, Lyra2 and Argon2 use multiplications in their BLAKE2-derived round function BlakMka. Multiplication as a primitive gives a nice amount of 'mixing', but it makes the cipher harder to analyze. $\endgroup$ – Samuel Neves Sep 27 '17 at 11:42
  • 3
    $\begingroup$ (+1) There's also the matter of the existence of the modular inverse: If you want to have an inverse permutation, you require multiplication by the modular inverse. Since the multiplier operates modulo machine sized words, multiplication via a number that possesses 2 as a factor is not efficiently invertible. The words of the state cannot be guaranteed to not possess 2 as a factor (and almost certainly will at some point), and so using words of the state as inputs to the multiplier is not as straightforward as just using addition or xor. $\endgroup$ – Ella Rose Sep 27 '17 at 17:06
  • 2
    $\begingroup$ @Fanael, like fgrieu basically wrote it depends on whether you mean reciprocal throughput or latency. Modern x86 execution units typically have 1 cycle reciprocal throughput for multiplication, but e.g. Ryzen has 3-cycle latency. That is, if you are doing independent multiplies you get a similar throughput as with simpler ops, but if the next instruction needs the result you are slowed down. Anyway, with truly fast ciphers you need to also consider vectorization and things get more complicated. $\endgroup$ – otus Sep 28 '17 at 5:09
  • 2
    $\begingroup$ As for a source, I recommend agner.org/optimize/instruction_tables.pdf $\endgroup$ – otus Sep 28 '17 at 5:11
  • $\begingroup$ @Fanael most ciphers and such have some parallelism by design. E.g. if you look at argon2's permutation in appendix 2 of the specification, you can see that 16 64-bit words are mixed in sets of 4 so that computations from different $G$ can also be interleaved. $\endgroup$ – otus Sep 28 '17 at 13:19
1
$\begingroup$

I think simply put. However fast multiplication is, simple bitwise operations are even faster - and can be executed sometimes out of order, and in parallel by multiple execution units in the CPU. Moreover - major criteria of any algorithm design is the ability to implement it in hardware. Simplicity and ability to parallelise operation, thus lowering the cycles per byte number - is the key here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.