5
$\begingroup$

NSA recommendation for the pre-quantum period allows the use of RSA-3072 (https://apps.nsa.gov/iaarchive/programs/iad-initiatives/cnsa-suite.cfm), nevertheless, is it safe enough to do it with the above exponent (of $2^{16}+1$), and are there any known vulnerabilities for scheme EMSA-PSS (RFC8017) or for scheme RSAES-PKCS1-v1_5 done with this signature system?

$\endgroup$
4
  • 1
    $\begingroup$ RSAES-PKCS1-v1_5 is en encryption scheme. Do you mean RSASSA-PKCS1-v1_5? Also, EMSA-PSS is a portion of a signature scheme which full proper name is RSASSA-PSS. $\endgroup$ – fgrieu Jun 3 at 18:25
  • 1
    $\begingroup$ If there is a modern CPU other than terribly power-constrained, and a millisecond of delay is tolerable, then the RSA signature verification can be entirely in software, which many oppose to hardware even when the software is in ROM, thus "taped out". Verification is hundreds time faster than signature generation, and relatively easy to get right. Hoping to design without prior experience something that does RSA signature generation and remains safe from side-channel attack for 10 years (even with key rotation) is being uh, very optimistic. $\endgroup$ – fgrieu Jun 3 at 19:20
  • $\begingroup$ The value $2^{16} + 1$ is the fifth prime of Fermat or F4 (F0 is the first one). It is used by most software libraries as a sensible default (OpenSSL, Java etc.) $\endgroup$ – Maarten Bodewes Jun 4 at 20:53
  • $\begingroup$ yes, thank you fgrieu for the correction $\endgroup$ – Evgeni Vaknin Jun 8 at 11:05
8
$\begingroup$

is it safe enough to do it with the above exponent (of 2^16+1), and are there any known vulnerabilities for scheme EMSA-PSS (RFC8017) or for scheme RSAES-PKCS1-v1_5 done with this signature system?

Let's go through the potential vulnerabilities:

  • Attack on the modulus using a conventional computer using known algorithms. In this case, the most efficient algorithm known is NFS, which would take an estimated $2^{128}$ operations to factor a 3072 bit modulus - it would be infeasible for anyone to perform this many operations in the next 10 years.

  • Attack on the RSA problem using a conventional computer using a yet-undiscovered algorithm. While this is difficult to discount, there hasn't been any significant advances in factoring algorithms in the last 20+ years, and there is no indication of an algorithm that can solve the RSA problem without factoring the modulus. This does not look like a significant concern.

  • Attack on the RSA padding method; however, PSS has a security proof that an attack here would not be significantly easier than an attack on the RSA problem, and while RSASSA-PKCS1-v1_5 does not have such a proof, it has been out there for 30 years without any found vulnerability (assuming that you perform the necessary checks as a part of the validation).

  • Attacks on the entropy used to generate the RSA keys. While this is not an attack on the system, this needs to be considered (especially if the hardware device generates its own key pairs).

  • Side channel attacks on the RSA private key. While this might not be a concern (say, if the hardware device only does signature verification and so doesn't have the RSA private key), it may be - here so that it's on the needs-to-be-solved list.

  • Attack on the modulus using a Quantum Computer. I list this last because (assuming a good hardware implementation) the most likely concern. I have been monitoring the progress in Quantum Computer technology; my opinion is that there are enough significantly large hurdles that I don't personally expect a large scale reliable Quantum Computer (e.g. one that can factor a 3072 bit modulus) to be available within 10 years. You should be aware that there are experts who have publicly stated that this might actually be a possibility.

Bottom line: I personally expect it to be secure (again, assuming a well designed system) for the next 10 years - if you asked for 20, I would likely give another answer. However, that expectation is my opinion, and is not shared by everyone in the community.

$\endgroup$
1
  • 3
    $\begingroup$ Addition: the public exponent $e=2^{16}+1$ is fine, and unobjectionable from a security standpoint. Most believe $e=3$ is just as safe at least when it comes to signature, and RSASSA-PSS is used, and we put side-channel attacks on the signature-generating device aside. Everyone agrees $e=3$ makes signature verification even faster, by a factor up to 8. $\endgroup$ – fgrieu Jun 3 at 19:55

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.