2
$\begingroup$

NIST SP800-56B standard (addressing IFC-based Key Establishment schemes) defines some key establishment (KE) schemes using the RSASVE primitive in which the common secret $Z$ is encrypted with RSA-EP (basic RSA encryption without padding).

I understood that RSA encryption should mandate one of the two padded schemes (PKCS#1 v1.5 or OAEP) as defined in the PKCS#1 standard.

I've got two related questions about this:

  1. Is such basic RSA encryption of common secret $Z$ without any padding - of which all security obviously relies) secure?
  2. If yes, for what use cases is RSA encryption without padding secure? In which use case is padding required?
$\endgroup$
  • $\begingroup$ could you please name (examples of) the KE schemes that use raw RSA, because its security is highly dependent on how it's used. $\endgroup$ – SEJPM Mar 22 '16 at 15:38
  • $\begingroup$ @sejpm : for key agreement KAS-1 and KAS 2 schemes use RSASVE and so RSAEP algorithm for shared secret element encryption ; for Key Transport KTS-KEM-KWS uses as well RSASVE and so RSAEP algorithm for shared secret Z encryption $\endgroup$ – william_fr Mar 22 '16 at 17:27
4
$\begingroup$

Yes, RSA encryption without padding as used by RSASVE in NIST SP800-56B is secure.

The RSASVE Generate Operation in NIST SP800-56B §7.2.1.2

  • is given on input an RSA public key $(n,e)$;
  • generates a random secret bitstring $Z$ uniformly distributed on range $[2,n-2]$;
  • computes $C=Z^e\bmod n$ (as in textbook RSA encryption);
  • outputs the secret $Z$ and the public $C$ (as bitstrings).

and the RSASVE Recovery Operation

  • is given as input $C$ and the private key $(n,d)$ (or some equivalent);
  • computes $Z=C^d\bmod n$ (as in textbook RSA decryption);
  • outputs the secret $Z$.

It is used to generate a secret bitstring $Z$, then share it with the legitimate holder of the private key $(n,d)$.

This is safe (in the sense that an adversary intercepting $C$ gains no knowledge about $Z$ chosen in RSASVE Generate), despite the lack of padding, because what's passed to textbook RSA is random. Breaking RSASVE is, quite precisely, the RSA problem, defined as gaining information about random plaintext randomly chosen on $[2,n-2]$ (give or take $0$, $1$, $n-1$) and encrypted using textbook RSA encryption. Padding is unnecessary here. One way to see that is that the aim of RSA padding is to transform plaintext (or message to sign) into something close enough to random that the RSA problem is safe, and here we have something assumed random in the first place.


Update: as rightly pointed by SEJPM in comments, the above is not enough to show that the uses of RSASVE in NIST SP800-56B are safe. According to a cursory review, that's indeed the case, for I only see that $Z$ is

  • optionally, first concatenated with another similarly shared secret, to form a wider one;
  • used as the input of some KDF, where it is subject to $H(\text{counter}\|Z\|\text{OtherInfo})$

and this prevents any exploitation of the homomorphic property of RSA.


We can safely use RSA encryption without padding when

  1. The plaintext enciphered is guaranteed to be about uniformly random (from the adversary's standpoint) over $[0,n-1]$ (or a large-enough subset of that, say with more than $n^{2/3}$ elements); this is enough to insure that the adversary can not gain knowledge of what's enciphered.
  2. And it does not matter that the alleged plaintext obtained by deciphering unauthenticated ciphertext can have special relations to some true plaintext.

Two common applications of that are

  • Encryption of a freshly generated secret, for secret sharing, when that secret is then hashed (as in NIST SP800-56B) or otherwise used in a manner matching 2.
  • Encryption of a freshly generated RSA signature, when the modulus used for encryption is different form the one used for signature (and not with much more bits); in this application, deciphered plaintext is then naturally submitted to signature verification using a different modulus than in encryption, which insures 2 is met. In the common case of moduli of the same bit size, there is a standard trick to shorten the signature by one bit so that it is always less than the encryption modulus: replacing signature $S$ by $\min(S,n_s-S)$ where $n_s$ is the signature modulus. Enciphering a signature is useful to insure confidentiality of some of what's signed.

Note: I have silently assimilated bitstrings to integers using big-endian convention.

$\endgroup$
  • 1
    $\begingroup$ The interesting part (why I asked for clarification in the comments) is: a) What does happen with $z$? Can you somehow exploit the homomorphic property of RSA? $\endgroup$ – SEJPM Mar 22 '16 at 20:12
  • 1
    $\begingroup$ @fgrieu: i understand that if rsa encryption applies to a random plaintext rather than to an applicative/structured message, textbook rsa encryption may be considered. However from my understanding most of rsa encryption applications is to distribute symmetric key, rather than to protect traffic / applicative data (symmetric encryption does it well); so cases where unpadded / textbook rsa encryption may be considered (as with RSASVE) appear not so rare and are not an exception. $\endgroup$ – william_fr Mar 23 '16 at 5:57

Your Answer

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

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