0
$\begingroup$

I've already asked a few - as yet officially unanswered - questions about RSA-KEM with regards to the input secret encrypted using the public key here and (less on topic for this question) here.

CodesInChaos already commented in the first question linked to. It seems logical that having the most significant bit set to zero during generation of the random value $z$ to not impact security all that much.

Still, the use of random number generators for large amounts of data can be a draw back of the mode of operation, especially when they are required to generate 4096 bits of randomness for a single RSA operation. This could be an issue if said random number generator is slow or if insufficient entropy is available to the random number generator.

My related questions are:

  1. Can we reduce the amount of input keying material to the KDF further without reducing the security of the RSA operation? If yes, by how much?

  2. If yes, is there a good distribution of random bits required (half to the left, half to the right?)

  3. If no, could we use a one-way primitive such as a XOF or indeed MGF-1 after retrieving the required number of bits for secure key derivation, and feed that to RSA-KEM?

Or should I just run away and use RSA OAEP instead if I run into situations where a fast DRBG is not available?

Improve this question
$\endgroup$
7
  • $\begingroup$ If the PRNG provides sufficient entropy for 32-bytes, you could use a stream-cipher like ChaCha20 to expand the random bytes by using them as key... AFAIK libsodium does something like this internally. $\endgroup$
    – K. Biermann
    Commented Nov 17, 2017 at 16:22
  • $\begingroup$ Your 3rd paragraph is seems nonsensical. If a RNG is cumbersome, what do you call RSA and it's tentacles? Are you actually hinting at something else? $\endgroup$
    – Paul Uszak
    Commented Nov 17, 2017 at 16:28
  • $\begingroup$ Ok, what I meant was that requesting large amounts of data from a DRBG can be cumbersome; I'll adjust the question. $\endgroup$
    – Maarten Bodewes ♦
    Commented Nov 17, 2017 at 16:35
  • $\begingroup$ If requesting large amounts of data from a DRBG is cumbersome…get a better DRBG? You want a uniform random element of $\mathbb Z/n\mathbb Z$; the modulo bias at worst, for a modulus $n$ halfway between the generating power of two and the next one below, puts same mass in $[0,n/3)$ it puts in the double-length $[n/3,n)$. Usual heuristic is to pick $2\lceil\log_2n\rceil$ as the number of bits from which to reduce $n$ (e.g., why Ed25519 uses SHA-512 to get 256-bit scalar); I leave it as exercise for reader to quantify how nonuniform this is, and whether $256+\lceil\log_2 n\rceil$ is enough. $\endgroup$
    – Squeamish Ossifrage
    Commented Nov 17, 2017 at 16:50
  • 1
    $\begingroup$ @daniel No, that's for key pair generation, I was talking encryption. Encryption needs a random component as well, and with RSA-KEM the random component is a random number between $0$ and $n$, the modulus, which is used to derive the symmetric key, which is used to encrypt the message. $\endgroup$
    – Maarten Bodewes ♦
    Commented Nov 18, 2017 at 1:34

1 Answer 1

Reset to default
1
$\begingroup$

Theoretical concern. The standard security reduction of RSA-KEM to the RSA problem relies on the ability of the decryption oracle to handle most of the input space. If you don't feed all the bits into the KDF, or if you treat some inputs equivalently, you may shoot yourself in the foot, like failure to verify lHash in OAEP.

Practical concern. If you don't generate all of the bits of the element $x \in \mathbb Z/n\mathbb Z$ from which you derive a key $k = H(x)$, even if you spread them out so that the standard real number cube root attack doesn't work on exponent $e = 3$, you may nevertheless be walking headfirst into the Franklin–Reiter related-message attack, which applies even to exponent $e = 65537$ that everyone quietly accepts without the PTSD over $e = 3$ left from the dark ages of cryptography engineering in the '90s.

Performance concern. It costs at best about 20k cycles on a modern AMD CPU to compute $x^3 \bmod n$ for 2048-bit $n$—the faster half of RSA with the fastest exponent; any other exponent is slower (except perhaps in Rabin territory), and decryption is much slower. It costs at worst about 1k cycles to generate 2048 bits with Salsa20 using naive C code, and that's about the easiest option, not the cheapest option.

OAEP also needs to generate about $\lg n$ bits of data, but usually with a much more expensive PRNG (‘MGF’), such as SHA-256. Under what circumstances could the generation of $x$ be a bottleneck, but not the MGF computation of OAEP?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.