Attack against modular inversion operation using side-channels?

I'm building a device that performs a modular inversions using a secret modulus. I would like to know if it is possible to recover all or part of this modulus by side-channels (timing, power, EMR, etc.).

All information I found related to side-channels in modular arithmetic applies to modular exponentiation.

The algorithm used for inversion is the standard Extended Euclidean algorithm.

The attacker may be able to measure, for example, computing time. He does not have access to the output, nor to the modulus. He knows only the value that will be inverted.

-
The obvious question is "what can the attacker observe"? If he can observe inputs and outputs, he doesn't need a side-channel attack; he can recover the secret modulus algebraically. If he can't observe anything, it's not likely that a side channel attack can tell him anything. – poncho Dec 15 '13 at 12:43
He may be able to measure computing time. He does not have access to the output nor to the modulus. He knows only the value that will be inverted. – SDL Dec 15 '13 at 13:10

Because the time that the Extended Euclidean algorithm depends on the inputs (and, in particular, is a complex function of the two, depending on the ratio expressed as a continguous fraction), there may be some leakage there.

It occurs to me, however, that there is a very simple countermeasure; assuming that the secret modulus you are inverting is $p$, and that the value you want to invert is $x$:

• Select a random number $r$ that is $0 < r < p$ and is relatively prime to $p$ (and latter condition is trivial if $p$ is prime)

• Compute $blind = r \times x \mod p$

• Compute the modulus inverse $blindinv = blind^{-1} \mod p$ (using the Extended Euclidean algorithm)

• Return the value $result = r \times blindinv \mod p$

It is easy to see that this computes the modulus inverse correctly, and the value given to the underlying modulus inverse function is uncorrelated to the original value $x$ (and that the additional cost of the two modular multiplications is trivial compared to the cost of the modular inverse).

Is this really required? I don't know; however it seems to me that the above is so cheap that even if there is a chance of a weakness, this randomization looks warranted.

Now, this hides the value being inverted from the attacker, but it doesn't apply a blinding factor to $p$; however while the time taken on average (given unknown inputs) by the EE algorithm does vary somewhat based on the modulus, it is a much weaker function (and gives far less information). Blinding $p$ would be considerably more expensive; whether you would want to do so depends on the risk of any such leakage (e.g. if it's the country's missle defense codes, you probably will be willing to pay the additional costs), as well as how much you can afford additional costs.

If you are willing to pay the additional cost, the obvious way would be to select a value $r'$ that's relatively prime to $x$ (e.g. a prime larger than $p$), and in steps two and three, compute:

$blind = r \times x$

$blindinv = blind^{-1} \mod (p \times r')$

(and the rest of the algorithm stays the same; the $\bmod$ operation in the next step will discard the extra information included by the $r'$ factor)

Assuming you pick $r'$ values about the same size as $p$ (or slightly larger), you would approximately double the cost.

-
It seems that you solved the problem, while we still don't know if there is a problem or not. I'm sure that someone must have analyzed modinv side-channels in the past... – SDL Dec 16 '13 at 17:13
@SDL: true; I haven't presented an attack that recovers the modulus given values being inverted and the time taken (although it might not be too hard to outline; if $x \bmod p$ happens to be a small value, then EE goes faster; a first step might be to look for fast inversions and see if they have a $kx + \epsilon$ in common; that'll give you partial information about $p$). However blinding the value being inverted is so cheap, it makes sense to do it even if we have a hint that there might be a problem. – poncho Dec 16 '13 at 18:05
@poncho Why do you think that your proposed countermeasure is not published or mentioned elsewhere while at least two papers address the same problem ? In OpenSSL the solution to "New Branch Prediction Vulnerabilities in OpenSSL and Necessary Software Countermeasures" is to employ the classical extended euclidean algorithm based on divisions operations. Recently, the paper "Constant Time Modular Inversion" addresses the same problem. Both proposals, in my opinion are more costly that the one you propose :( What do you think about that ? – mackandal Jun 5 '15 at 19:41

I found a reference of a side-channel attack to modular inversion being performed:

New Branch Prediction Vulnerabilities in OpenSSL and Necessary Software Countermeasures (Onur Acıic¸mez, Shay Gueron, and Jean-Pierre Seifert) February 7, 2007

The Main Result: Modular Inversion Via Binary Extended Euclidean Algorithm Succumbs to Simple Branch Prediction Analysis (SBPA)

-

ie

$$a^{phi(m)-1}=a^{-1}\mod{m}$$

Although this would require repeated squaring (which is also vulnerable to side channel attacks) the number you would obtain from any attack would be the exponent, not the thing you were calculating the inverse of. As you would have already given this away as your public key there's no point spending any effort to obtain it.

Example:

If the inverse you were trying to find was $17\mod{397}$ you calculate $17^{395} = 327 \mod{397}$.

Notice the repeated squaring would be for the binary equivalent of $395$ not the value $17$ which would remain secret.

-
As stated in the question, the value to be inverted is not secret. The modulus factorization (and phi(m)) are the secret values, so using Fermat's Little Theorem makes inverting similar to an RSA private operation regarding timing attacks. – SDL Feb 24 '14 at 15:01