2
$\begingroup$

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) = md (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 2128 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?

$\endgroup$
  • $\begingroup$ Using "the size of the modulus" will make m*r (mod N) be approximately uniformly distributed. $\hspace{.83 in}$ $\endgroup$ – user991 Apr 26 '15 at 23:47
  • $\begingroup$ @Ricky - if the adversary never sees the result m*r (mod N), does it need that property? (Please forgive my ignorance). $\endgroup$ – user10496 Apr 26 '15 at 23:50
  • $\begingroup$ I have no clue. $\;$ $\endgroup$ – user991 Apr 26 '15 at 23:55
  • 2
    $\begingroup$ It is not that blinding was not enough to stop key recovery. In the attack, blinding enabled key recovery, because of an implementation bug. That's a problem with RW signature: goof in the Jacobi, or let a multiplicative forgery due to padding creep, and the public modulus is effortlessly factored; in RSA, there are less goofs that can cause this. $\endgroup$ – fgrieu Apr 27 '15 at 4:27
  • $\begingroup$ Thanks @fgrieu. Any thoughts on the size of the integer needed to perform the blinding? Is it always the size of the modulus? Can it be something related to the security level provided by the modulus? Or can it be the size of max(p.bits(), q.bits())? $\endgroup$ – user10496 Apr 27 '15 at 4:31
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "...requires computing r^d (mod N), which is just as costly as the m^d (mod N) operation being protected" - right, that's why I thought reducing hamming weight might be helpful. "So all in all there's no appreciable savings..." - perfect, thanks. $\endgroup$ – user10496 Apr 27 '15 at 5:09
  • $\begingroup$ It's is obvious that r^ed mod n = r, as e*d mod phi(n) = 1 so this concept works (equals sign means "is congruent to"). However, what are the formal requirements for the random variable r so this is still mathematicaly correct? Thanks. $\endgroup$ – bayo Feb 26 '16 at 12:15
  • 1
    $\begingroup$ @bayo15: assuming $(e\cdot d\bmod\varphi(n))=1$ or equivalently $e\cdot d\equiv1\pmod{\varphi(n)}\;$, the equality $(r^{e\cdot d}\bmod n)=r$ holds for integers $r$ with $0\le r<n$, while the congruence $r^{e\cdot d}\equiv r\pmod n$ holds for all integers $r$. I can't think of another interpretation of mathematically correct. $\endgroup$ – fgrieu Feb 26 '16 at 13:24

Your Answer

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