What do you call a random number that affects the calculation, but not the result?

Question

This is about the same random ladder algorithm as my previous question. It computes f(g,n,r)=n*g or g^n (depending on the group notation), where g is a generator of a group. Suppose n=5882353. This can be calculated as

((((((((((1*2*2+1)*2+1)*2*2*2+1)*2+1)*2+1)*2*2*2*2*2*2+1)*2+1)*2+1)*2+1)*2+1)*2*2*2*2+1
(((((((1*3*3+2)*2+1)*2+1)*3*3+2)*2+1)*3*2*3*2+1)*2*2+1)*2*2*2*3*2+1
((((((1*3+2)*3*3+2)*2*3+1)*3+2)*2*3*2*3+1)*2*2+1)*3*2*2*2*2+1
((((((((1*3*3+2)*3*3*3+1)*3+2)*3+1)*3+2)*3*3*3+1)*3+2)*3+2)*3+1

and about 215,000 other ways of expressing n by multiplying by 2 or 3 and adding 1 or 2, depending on r. r is a number between 0 and 1, expressed as a/b, where b is at least 78.8% as big in bits as n. The intent is to make it difficult for Eve, watching the side channel, to figure out what n is. Is there a name for the number r? If not, can you suggest one?

Answer 1

The technique of using an auxiliary input that affects intermediate values, but not the final result, is called blinding. The auxiliary input can be called a “blinding parameter” or some other variant that depends on how it's used in the calculation, for example “blinding factor” if it's used in a multiplication. When the blinding is done with bitwise operations, it's often called masking.

Blinding is a common technique to avoid side channel attacks in cryptographic computations. The blinding parameter is usually random, but not always — there are cases where deterministic blinding is useful (for example, a blinding factor derived deterministically from the private key and the message in a signature operation). Random blinding only helps if the side channel cannot reveal all the secret data in a single trace, but that's a common case.

---

(Note that I'm not good at attacks — what follows is from my experience as a defender, where experts come to me and say “hey, we found this side channel in your products” and I look for a way to eliminate this side channel.)

The blinding strategy proposed here does not look good to me. Reading the bits of an exponentiation is a very well-known side channel, and breaking the exponentiation with a large exponent into a variable series of multiplications does not eliminate this side channel. On many platforms, code running on the same machine can measure with reasonable accuracy the exponents in a single trace. Even on better isolated platforms (for example, a remote attack), by observing many traces, the adversary can learn the distribution of factors, and that is probably enough to reconstruct the exponent with a practically feasible number of traces.

In general, adding noise to a computation is only a limited defense against side channel attacks. It forces the adversary to observe more instances of the calculation, but that's only a good defense if the side channel is limited, so that a non-noisy computation needs significant time to attack and the noise causes the attack time to become impractical. Noise doesn't help if even a single instance of the calculation leaks secret information.

You're reinventing a well-known wheel, and yours is very square. I strongly urge you to browse the literature on attacks and implementations of exponentiation, and look at how existing cryptography libraries do it. The preferable way to avoid timing side channels is not randomization (making the timing dependent on a combination of the secret inputs and an auxiliary secret), but to have the timing of operations be completely independent of secret inputs.

Answer 2

Is there a name for the number r?

The term I've come across to describe this would be blinding factor

Now, for modexp operations, the standard way to do blinding on the exponent is Coron blinding, that is, to compute $g^x \bmod p$ is to select a random $r$ and compute:

$$g^{x + rq} \bmod p$$

(where $q$ is the size of the subgroup; if you're doing exponentiation over a finite field, then $q = p-1$).

If $q$ doesn't have a long string of 0's and 1's in its binary representation, then this works well with a modest $k$; if there is such a large string, that can be worked around, but it's more complex. In any case, you may want to consider this, either as an alternative to your technique or a supplement.

Answer 3

There are several kinds of algorithms that "use" random number(s) in ways that have no (significant) effect on the result:

• a blinding factor is used in cryptographic blinding, resulting in exactly the same result but (hopefully) blocking side-channel attacks (as others have already answered)
• A random key is used to fight hash flooding attacks -- such keyed hash table produces exactly the same results as non-keyed hash tables no matter what key is chosen, but if the key is kept secret, attackers cannot force hash table collisions that would cause servers to run much slower.
• A random key is often internally on SSDs (reducing wear when "the entire disk is erased" by physically erasing only the random key)
• A unique (and often random) per-message nonce such as an initialization vector is used internally in many cryptosystems in order to provide semantic security
• An ephemeral key (often random) is used by some cryptosystems for forward secrecy.

Outside of cryptography,

• random values are used in stochastic algorithms and randomized algorithms and random direction in synthetic random walks. Often such algorithms "usually" produce close to the correct answer, and the randomization makes it unlikely to generate a really bad answer.
• While Brownian motion of small visible particles is apparently caused by the unpredictably random velocities of even smaller submicroscopic molecules, Einstein and Smoluchowski showed that (practically independently of the particular random velocities) the mean squared displacement of those small particles can be used to measure the size of molecules.
• Some robots occasionally turn a randomized angle to try to avoid getting stuck -- in particular, early robot vacuums used such randomized navigation. The particular random values don't effect the final result -- eventually the entire floor gets explored.
• Simulations of flocking behavior sometimes produce surprisingly lifelike sophisticated and unpredictable behavior that appears to be at least partially random, using a surprisingly simple and deterministic "boids" algorithm.