0
$\begingroup$

I've been wondering about this paragraph for some time:

Multiplication is a great mixing function. If you work out what multiplication looks like in terms of ANDs and XORs it becomes apparent how elaborate a 64bit multiply is. The amount of transistors required to implement it in hardware prohibits multiplication from being used in most cryptographic algorithms. But for non-cryptographic PRNGs which only need to run on a general purpose CPU, multiplication is very useful because there is already a hardware implementation.

https://tom-kaitchuck.medium.com/designing-a-new-prng-1c4ffd27124d

Usually in encryption algorithms we use modular addition, rotation, and exclusive OR operations. But is there anything that could stand in the way of using modular multiplication, rotation, and exclusive OR operations?

Modular multuiplication is slower than addition, but it's probably not that much slower, and for sure it is stronger mixing function. Multiplication is in fact a great mixing function, so why it is so rarely used in symmetric cryptography? I think even smarphones can do 64-bit multiplication very quickly and have some hardware implementation for multiplication (but I'm not sure).

Is the slowness of multiplication really such a big problem that multiplication can't find widespread use in fast lightweight encryption algorithms? Probably on IOT devices or RFID chips it can be a problem, but when it comes to computers and smartphones, an encryption algorithm based on multiplication couldn't be a problem, isn't it?

$\endgroup$
1
  • 1
    $\begingroup$ Unless the CPU has a integer hardware multiplier it shouldn't be a problem. The problem starts when using in a very small environment like smartcards when the tiny processor only do very basic operations as the ones you cited, $\endgroup$ May 9, 2022 at 14:11

3 Answers 3

5
$\begingroup$

Is the slowness of multiplication really such a big problem that multiplication can't find widespread use in fast lightweight encryption algorithms? Probably on IOT devices or RFID chips it can be a problem, but when it comes to computers and smartphones, an encryption algorithm based on multiplication couldn't be a problem, isn't it?

Part of the issue appears to be the definition of 'lightweight', and the intended platforms it is targeted. The CPUs on smartphones are actually quite capable; I would not characterize those platforms (or laptop computers) as necessarily 'lightweight'. Lightweight crypto is generally designed with microcontrollers in mind; typically, those microcontrollers don't have built-in 64x64 bit multiplication instructions.

Now, modular multiplication (for modulus a power of 2) can be implemented by a series of shifts and conditional additions; certainly doable, but considerably more expensive than an addition operation.

The other issue would appear to be that modular multiplication isn't as wonderful as you would have hoped. For this discussion, I'll limit my discussion to multiplication modulo a power of 2 (multiple modulo a prime doesn't have these issues; they do have have issues around the range not being a power of 2).

  • Modular multication does not have any 'right-word' propagation; for example, flipping the high bit of one of the inputs would only affect the high bit of the output; the other bits are unaffected. Of course, modular addition has the same issue; however it's also cheaper.

  • Modular multiplication does have strong differentials; the strongest is based around the identity $(-x)*y = -(x*y)$ (and the modulus operation does not break this up).

Both of these issues can be designed around in a proper design; however the fact that you have to do so makes it less attractive. In addition, it begs the question: why not use multiplication in $GF(2^k)$ instead? If we're doing a shift/add implementation, a double/xor implementation of Galois multiplication isn't much more expensive, and it avoids the above two issues...

$\endgroup$
5
  • $\begingroup$ Of course multiplication mod 2^n has big issues with mixing the bits (especially low), that's why we combined it with xor and rotate. But so far as I know addition has even bigger issues of this type. I'm not sure but probably even stronger differentials. $\endgroup$
    – Tom
    May 9, 2022 at 16:59
  • $\begingroup$ Can multiplication GF(2^k) be similarly fast as multiplication 64-bit numbers mod 2^64? I think it has to be GF(2^64) to get the same amount of bits. $\endgroup$
    – Tom
    May 9, 2022 at 17:15
  • $\begingroup$ @Tom: obviously, any such answer would be quite hardware-dependent. On large CPUs, I believe that they have 'carryless multiply' operations; the necessary fixup isn't free, so it'll be slower than a straight 64x64 multiply, but it wouldn't be bad. On small CPUs (without a multiply), a constant-time double/conditional xor $GF(2^{64})$ should be close to the analogous shift/conditional add 64x64 multiplication... $\endgroup$
    – poncho
    May 9, 2022 at 17:47
  • $\begingroup$ I made 32-bit LCG generator and LCG generator in GF(2^32). And multiplication in GF(2^32) perfmorms slightly worse in PractRand. It looks like there are also some problems with low bits. Won't there be some other differentials? I'm not sure. It seems that the multiplication in GF(2) does not mix the bits any better. Or maybe the main advantage is that it's harder to find multiplicative inverse? $\endgroup$
    – Tom
    May 11, 2022 at 4:55
  • 1
    $\begingroup$ @Tom: the advantage of GF multiplication is this: if $a \ne 0$ and $b$ is unknown and uniformly distributed, then $a \times b$ will also be uniformly distributed. This is not true for multiplication modulo a power of 2, if $a = 2$, and $a \times b$ will always be even. $\endgroup$
    – poncho
    May 11, 2022 at 12:44
4
$\begingroup$

The block cipher IDEA from 1991 used modular multiplication mod $2^{16}+1$ for diffusion (where 0 is mapped to $2^{16}$).

As zero-divisors are not good from a cryptological standpoint, the modulus should be prime, and of the form $2^b+1$ as one prefers to work with bits (and not use the 0), so $b=2, 4, 8, 16$ ($b=1$ would be linear).

If you design a cipher using these modular multiplications, you will run into (at least) two problems:

  • the cryptographic properties of the modular multiplications are not well understood, making it hard for you to show that your cipher is good
  • for smaller devices side-channel attacks have to be considered, but it's hard to protect these modular multiplications against those (especially againt DPA; but already timing attacks might be a problem, if multiplication is not constant time)
$\endgroup$
8
  • $\begingroup$ I would argue that the cryptographical properties of modular multiplication are understood. In addition, as far as DPA, modular multiplication is threshold-friendly, based on the identity $(A+B)*(C+D) = (A*C + B*D) + (A*D + B*C)$ (which extends in the obvious way for 3+-way thresholding) $\endgroup$
    – poncho
    May 9, 2022 at 16:17
  • $\begingroup$ Side-channel attacks and timing attacks are really issue that has to be considered, I forgot about it. Hovewer, isn't addition similarly vulnerable to such a problems? Or maybe it isn't because we can easily transform it into shift and xors, which are constant time? $\endgroup$
    – Tom
    May 9, 2022 at 17:07
  • 1
    $\begingroup$ @Tom: the main problem with timing and multiply is on lower-end platforms, on those platforms, the multiply instruction might not be constant time (e.g. stop when one of the operands runs out of '1' bits). Now, you could implement a constant-time multiply on those platforms; however a crypto-naïve implementor might not. In contrast, CPUs almost always implement addition in constant time... $\endgroup$
    – poncho
    May 9, 2022 at 17:56
  • $\begingroup$ One more question. To get analog of 64-bit multiplication (mod 2^64), what GF should be used? I want to multiply 64-bit numbers and get 64-bit results. Am I right I have to use GF(2^64)? There are examples of GF(2^8) everywhere, AES is also operating on GF(2^8), but it works on bytes. If someone would like to replace 64-bit multiplication, he has to use GF(2^64), am I right? Or maybe it could be something different, like in AES GF(2^8), but on bytes? Then rules of such arithmetic are slighty different, than in GF(2^64), if I understand it right. $\endgroup$
    – Tom
    May 9, 2022 at 18:52
  • $\begingroup$ @poncho: The formulas you gave for threshold implementations hide two implementation issues: The addition is mod $2^{16}+1$, so the additive shares don't fit into 16 bits, and you need a modular reduction that is easily implemented, but you have to consider that the un-reduced values are visible to the attacker (via DPA). But the real problems for a DPA-secure implementation will show up, when you mix the modular multiplication with other operations like xor or addition mod $2^{16}$, as you have to switch between different masking operations, which is non-trivial (and time-consuming). $\endgroup$
    – garfunkel
    May 20, 2022 at 12:19
0
$\begingroup$

Encryption, of any type, is costly in hardware area and power. Multipliers are indeed large, and deep and thereby slow compared to the base ALU full adder. I'm going to do a bunch of hand waving, but if you grab a CPU architecture book, you'll find the following: The design of the multipliers are always different, but the MUL unit pipeline for a 64-bit result is 4-deep, and for a 128-bit result is 8-deep on most CPUs. This is because you use chained full adders blocks, and the maximum depth in the 4-deep design is 16. The full-adder depth for an XOR, ROL, or ADD is equivalent to a single full-adder. Super-scaler processors hide much of the delays of multipliers; however, if you are really grinding away on a problem, will find an empty pipeline with a lot of delays.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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