Rabin-Williams, blinding and size of Integer r?

Question

I was reading the paper Breaking the Rabin-Williams digital signature system implementation in the Crypto++ library. The library uses blinding, but it was not enough to stop key recovery.

But my question is about the Integer r used for blinding. Crypto++ uses a random integer in the range [1, n-1]. Then, the operation proceeds by calculating m * r (mod N); (m * r)^d (mod N); and finally (m * r) ^d * r^-d (mod N) = m^d (mod N). If n is 3072 bits, then r is effectively 3072 bits.

Since r needs to provide a mask at an equivalent security level of 128-bits, wouldn't a 256-bit integer suffice to mask the operation? In this case, its 128-bits times 2 because there's a 50/50 chance of selecting a 0 or 1. So someone trying to build a system of equations to deduce bits in the private key would need a table at least 2¹²⁸ in size.

Is there criteria in selecting the size of the blinding integer r for Rabin-Williams? Or is it convention (or required) to always use the size of the modulus?

Answer 1

Blinding is usually applied on the whole modulus, and I see no incentive to do otherwise; random is cheap.

---

In RSA, blinding is not always applied as described in the question and article, for efficiency and security reasons: the technique described requires computing $r^d\bmod N$, which is just as costly as the $m^d\bmod N$ operation being protected, and involves the private key, which could be a security issue. Rather, the archetypal (external) blinding goes:

1. draw random $r$;
2. compute $\hat r=r^e\bmod N$, the blinding factor (since $e$ is typically short compared to $d$, this is much less costly than computing $r^d\bmod N\;$; further, only the public key is involved in computing $r^e\bmod N$, therefore a successful side-channel attack here can't directly endanger the private key);
3. compute $\hat m=m\cdot \hat r\bmod N$, the blinded message (or signature);
4. compute $\hat c=\hat m^d\bmod N$, the blinded result;
5. compute $r'=r^{-1}\bmod N$, the unblinding factor;
6. compute $c=\hat c\cdot r'\bmod N$, the result.

If $r$ was reduced from the width of $N$ to say $256$-bit:

• it would be proportionally less trouble to generate, but that's almost a non-issue in modern security environments, where random is relatively cheap (precisely to enable blinding and masking techniques);
• there would be a problem with very small $e$ like $3$, where $\hat r$ would not have all its bits random; we'd have at least a worry making a convincing argument that this is not a problem w.r.t. power analysis and timing attacks;
• when there's not this problem, the saving in step 2 would be marginal at best; in any case, step 4 dominates all the others for common $e$ like $e\le2^{16}+1$, or even random $e$ as sometime practiced (typically $e<2^{(2^k)}$ with $k\in\{5,6,7,8\}$; see footnote for unusually large $e$);
• we'd save in step 5, significantly relative to step 5, but overall negligibly;
• we'd have at least a worry making a convincing argument that $r'$ is unpredictable enough for our blinding purposes.

So all in all there's no appreciable saving reducing the width of $r$, it can only make attacks even so slightly easier, so why bother?

---

Footnote following comment: computing $r^d\bmod N$ for narrow $r$, rather than wide $r$, can indeed make a difference (like a saving of $1/3$ on this operation) if we use left-to-right scanning of the binary expression of the exponent; because then, while computing $r^d\bmod N$, about one in three modular multiplications is by $r$ (other faster modular exponentiation techniques do not allow so much saving). If we indeed use this exponentiation method and compute $r^d\bmod N$ (or compute $r^e\bmod N$ for unusually large $e$), narrow $r$ would be a saving worth consideration, saving up to about $1/6$ of the overall execution time for large size of $N$, and I do not immediately see that it would cause a security issue.