Security of RSA for paranoids with padding?

Question

RSA for Paranoids (RSAP) (in CryptoBytes v1n3), also known as Unbalanced RSA, is a variant of RSA proposed in 1995 by Adi Shamir, as a mean to increase the RSA public modulus size while keeping computation cost moderate. It is getting renewed interest, as part of a lightweight authentication and key agreement protocol born as SPAKE: A Single-Party Public-Key Authenticated Key Exchange Protocol for Contact-Less Applications (Financial Cryptography 2010 Workshops, paywalled with free extract), renamed ALIKE: Authenticated Lightweight Key Exchange (nice slides), and standardized in ISO/IEC 29192-4:2013 (paywalled with free extract).

RSAP is an asymmetric encryption algorithm, which I simplify to three parameters:

• the bit size $n$ of the public modulus $N=p\cdot q$;
• the bit size $\kappa$ of the private key modulus $p$;
• the odd public exponent $e$.

For key generation, it is drawn a random $\kappa$-bit prime $p$ with $\gcd(p-1,e)=1$; and a random prime $q$ such that $N=p\cdot q$ has $n$ bits and $\gcd(q-1,e)=1$. The public key is $(N,e)$, as in RSA. It is precomputed $d=e^{-1}\bmod(p-1)$ [that would be $dp$ in standard RSA]. The private key is $(p,d)$.

Except for a restriction that the message can be at most $\kappa-1$ bits, encryption in naked RSAP is as in naked RSA: $C=M^e\bmod N$. Decryption uses $M=C^d\bmod p$. That works because $C=M^e\bmod N$ implies $C\equiv M^e\pmod p$, that implies $M\equiv C^d\pmod p$ per Fermat's little theorem, and it holds that $M<2^{\kappa-1}<p$.

The main advantage of RSAP is that decryption is much faster than in RSA: compared to a CRT implementation of RSA with two primes of equal size $n/2$, the speed-up is by a factor of $\approx 2({n\over2\kappa})^3$ [that exponent assumes a classical multiplication algorithm]. That is at least twice faster when using the same modulus as our reference ($\kappa=n/2$); and up to $\approx250$ faster (for $n=5000,\kappa=500$, an aggressive parametrization considered in the original RSAP article).

Naked RSAP is vulnerable to a disastrous attack (in addition to those that plague naked RSA encryption): $N$ can be factored (and thus all security lost) if the plaintext $M$ corresponding to ciphertext $C$ chosen by the adversary leaks; for example if $M$ is the plaintext for ciphertext $C=(2^{\kappa})^e\bmod N$, then $p=2^\kappa-M$ (notice that this choice of $C$ ensures that the corresponding $M$ has at most $\kappa-1$ bits).

An obvious improvement (considered in SPAKE but dismissed as not proven secure) is to use random padding before encryption as in RSAES-OAEP or OAEP+, except parametrized so that the padded message $\tilde M$ has slightly less than $\kappa$ bits instead of slightly less than $n$ in RSA; and perform the corresponding redundancy check after decryption before using (and perhaps releasing) the deciphered message (with, even more than in RSA, the requirement that the check of padding on decryption must not leak information about what in the padding is wrong, e.g. by timing difference).

For a concrete example of parameterization: with $n=2048, \kappa=576, e=17$, the padding of RSAES-OAEP using SHA-1 hash for 576-bit modulus, we can transfer 240-bit messages (padded to 576-bit $\tilde M$ and enciphered to a 2048-bit cryptogram $C=\tilde M^e\bmod N$), but with decryption like 10 times faster than in RSA-CRT with standard 2048-bit modulus, and hopefully security about equivalent to that.

Questions:

1. Are there theoretical (implementation-independent) attacks more efficient than factoring the modulus?
2. Can we prove security of RSAP with padding under some assumptions?
3. What would be implementation attacks, and appropriate countermeasures?
4. How much can we lower $\kappa$ for a given $n$?

---

I have left aside some other tweaks and considerations:

• $n-\lambda$ bits in $N$ can be predetermined or a function of the holder's identity, in order to reduce the size of the public key certificate, for some parameter $\lambda$; that's the case in Shamir's RSAP and SPAKE/ALIKE.
• The message exponentiated can be reduced to $\gamma$ bits with $\gamma<\kappa$ (rather than $\gamma=\kappa-1$ in my simplified naked RSAP).
• The minimum $e$ depends on $n$ and $\gamma$; $e>2n/\gamma$ seems safe according to Shamir and my understanding of SPAKE/ALIKE.
• When an adversary can obtain extremely many public keys and would be content breaking any, we may need extra precautions; I'll make someone else made a separate question allowing an answer discussing this.

Answer 1

Parameters. Fix positive integers $\kappa$, say 896 or 1024; $n \ggg \kappa$, say 2048 or 3072; and odd $e > n/(\kappa - 1 - 192)$, say 3 or 5, for a 112-bit or 128-bit security level, respectively. Fix a random oracle $H \colon \{0,1,\dots,2^{\kappa - 1} - 1\} \to \{0,1\}^{256}$, say SHA-256. (The length is fixed, so no length extension attacks.)

Key generation. Pick primes $p$ with $2^{\kappa - 1} < p < 2^\kappa$ and $\gcd(p - 1, e) = 1$ uniformly at random, and prime $q$ with $2^{n - 1} < pq < 2^n$ uniformly at random. Publish $N = pq$ as the public key.

Sender. Given $N$, pick integer $0 < x < 2^{\kappa - 1}$ uniformly at random. Compute $y \equiv x^e \pmod N$. Transmit $y$ as associated data for AEAD of message under key $H(x)$.

Receiver. Given $p$, on receipt of $y$, compute the least nonnegative $x' \equiv y^d \pmod p$ where $d$ solves $e d \equiv 1 \pmod{p - 1}$, and open AEAD message under key $H(x')$.

Correctness. $\newcommand{\divides}{\mathop{\vert}}$ Since $p \divides N$, the congruence $y \equiv x^e \pmod N$ implies $y \equiv x^e \pmod p$. Thus by Euler's theorem, $$x' \equiv y^d \equiv (x^e)^d \equiv x^{e d} \equiv x \pmod p,$$ since $\phi(p) = p - 1$ and $e d \equiv 1 \pmod{p - 1}$. And because the sender chose $x < 2^{\kappa - 1} < p$ and the receiver chose the least nonnegative $x'$ so that $0 < x' < p$, there is a unique common solution $x = x'$.

Security. $\newcommand{\Z}{\mathbb{Z}}\newcommand{\divides}{\mid}\newcommand{\ndivides}{\nmid}\newcommand{\given}{\mathrel{|}}$ Let $A\colon \Z^+ \times \Z^+ \to \Z^+$ be a random algorithm making a decryption attempt $x' = A(N, y) < 2^{\kappa - 1}$. $A$ is successful if $x' = A(N, y) = y^d \bmod p$, with success probability $\Pr[x' = A(N, y) = y^d \bmod p]$.

Define the random algorithm $F[A]\colon \Z^+ \to \Z$ by $F[A](N) = u - u'$, where $u \sim U[2^{\kappa - 1}, 2^\kappa)$, $v = u^e \bmod N$, and $u' = A(N, v)$, so that $u \equiv v^d \bmod p$. This algorithm is successful if $F[A](N) = p$.

If $u \leq p$, then there is no $0 < u' < 2^{\kappa - 1}$ such that $u' \equiv u \pmod p$, so $A$ and $F[A]$ fail. If $p < u$ and $u' \equiv u \pmod p$, then $u - u' = \ell p$ for some $\ell$. Since $0 < u' < 2^{\kappa - 1} < u < 2^\kappa$ and $2^{\kappa - 1} < p$, we have $2^\kappa < 2p$ and hence $0 < u - u' < 2^\kappa < 2p$, so $\ell = 1$ and $u - u' = p$.

Thus \begin{align*} \Pr[F[A](N) = p] &= \Pr[A(N, v) = v^d \bmod p, p < u] \\ &= \Pr[A(N, v) = v^d \bmod p \given p < u]\cdot\Pr[p < u]. \end{align*} The probability that $p < u$ depends only on the density of primes in the interval $(2^{\kappa - 1}, 2^\kappa)$, and can probably be safely taken to be at least 1/3.

The remaining missing part in this reduction is that the set $\{x^e \bmod N : 2^{\kappa - 2} \leq x < 2^{\kappa - 1}\}$ is disjoint from the set $\{u^e \bmod N : 2^{\kappa - 1} \leq u < 2^\kappa\}$, so conceivably a decryption algorithm that always works on the former could always fail on the latter. It's not clear how we could change the ranges of $x$ and $u$ to force a decryption algorithm to work on both, since the whole point of $x$ is to be below $p$ without knowing $p$, and the whole point of $u$ is to be above $p$ without knowing $p$. On the other hand, any algorithm that somehow consistently fails on integers whose $e^\mathit{th}$ roots modulo $N$ exceed $p$ could be converted into an algorithm to find $p$ by binary search, at the expected cost of about $\kappa$ invocations rather than one invocation.

If we filled in that missing part, then we could prove that an adversary who can decrypt a message generically for arbitrary $H$ can factor $N$ with negligible additional effort and a little lower probability.

The use of the random oracle $H$ is crucial: revealing any information about $x$ destroys the security.

The uniform random choice of $x$ by a sender is also crucial: if $x < \sqrt[e]{N}$, then the least nonnegative $y \equiv x^e \pmod N$ is actually $y = x^e$, so the adversary can just compute the real number $\sqrt[e]{y}$ to recover $x$. The probability that $$x < \sqrt[e]{N} < \sqrt[e]{2^n} = 2^{n/e} \leq 2^{\kappa - 1 - 192}$$ is bounded by $2^{\kappa - 1 - 192}/2^{\kappa - 1} = 2^{-192}$ since $x$ was uniformly distributed among integers in $[0, 2^{\kappa - 1})$. Even if a trillion users encrypt a quadrillion messages each, the probability that this will happen once is bounded by the negligible $2^{-100}$.

We could also parametrize it by the security level, or perhaps drive it to zero if we always pick $x$ above $2^{\kappa - 2}$, in which case we could relax $e$ to be merely above $n/(\kappa - 1)$. But there are also likely other attacks on structured messages to worry about.

Cost.

• Sender must compute one $n$-bit modular exponentiation in constant time. For $e = 3$, this requires only one $n$-bit modular squaring and one $n$-bit modular multiplication; for $e = 5$, two squarings and one multiplication.

• Receiver must compute one $\kappa$-bit modular exponentiation in constant time.

• Key is encapsulated in $n$ bits.

WARNING: Most bignum libraries are bad at the whole constant time thing, even ones that should know better and should feel bad about it like OpenSSL.

Answers.

1. Are there attacks easier than factoring? If the security reduction can be filled in, not appreciably—by the security reduction, any algorithm recovering the enclosed key from RSAP-KEM with success probability $p_0$ and cost $C$ can be extended to a factoring algorithm with success probability $p_0/3$ and cost $C$ plus one $\kappa$-bit subtraction.
2. Is there a security reduction? Maybe!
3. Are there implementation attacks? Undoubtedly, much like ordinary RSA. I highlighted the obvious one: a good constant-time arbitrary-modulus modular exponentiation is hard to find.

4. How much can we lower $\kappa$ for a given $n$? From my understanding of the best (pre-quantum) factoring algorithms, a lower bound on $\kappa$ is determined by ECM, whose running time is a function of $\kappa$, and a lower bound on $n$ is determined by NFS, whose running time is a function of $n$. (The post-quantum factoring story is partly addressed by pqRSA, which considers RSAP but does not use it.)

   Extrapolating from experimental evidence of ECM performance, which gives a cost of roughly $\exp(0.9 \sqrt{2 \log 2^\kappa \log \log 2^\kappa})$ scalar multiplications; heuristically adding three bits because scalar multiplications cost at least eight bit operations apiece; and rounding to neat sums powers of two—this back-of-the-envelope calculation gives estimates of up to an 80-bit security level for $\kappa = 512$, a 100-bit security level for $\kappa = 768$, a 112-bit security level for $\kappa = 896$, and a 128-bit security level for $\kappa = 1024$.

   These are upper bounds: if you choose $n$ too small the smart attacker will use NFS instead of ECM. Finding and extrapolating from experimental evidence of NFS performance to estimate upper bounds on the security level as a function of $n$ is left as an exercise for the reader.

Caveat lector: Crypto.SE is not a respectable peer-reviewed academic cryptology journal. I get to blather whatever I want here with the weight of my numerical reputation and no adverse consequences for my tenure prospects. It is your responsibility to make sure this is right!