We are going to integrate some hardware accelerator for RSA into our next system on chip. This chip can accelerate the core RSA operation, i.e. modular exponentiation $y=A^x \mod(N)$. The private key ($x$) to use can either be provided from the outside or will be stored inside the hardware core, unaccessible to any other hardware /software component. Side-channel attacks are not an issue in this question.

We assume that the software can query the accelerator to do the modular exponentiation using the on-chip key ($x$) and just gets the result ($y$) for any arbitrary $A$ he provides. Would this setup be susceptible to any oracle-kind attack which would allow extraction of the on-chip key $x$? If so is there any countermeasure against this (using padding according to PKCS #v1.5 or RSASSA-PSS)?

  • 1
    $\begingroup$ If your private key isn't truly badly picked (ie with a low entropy process or to have a small value), all known attacks don't recover the private key. $\endgroup$ – SEJPM Dec 6 '18 at 12:59

Would this setup be susceptible to any oracle-kind attack which would allow extraction of the on-chip key $x$?

Not as far as we know.

Any such Oracle attack that could recover the private key would demonstrate that the "RSA problem" and the "factorization problem" are equivalent. Currently, that is an open question; such an attack would be a noteworthy advance...

  • $\begingroup$ Would this attack be equivalent to a chosen plaintext attack on RSA? $\endgroup$ – Maarten Bodewes Dec 6 '18 at 16:15
  • 1
    $\begingroup$ @MaartenBodewes: chosen ciphertext, actually (assuming the private key does "decryption" and not "signing"). $\endgroup$ – poncho Dec 6 '18 at 16:18
  • $\begingroup$ D'oh! Yes, that's what I should have meant :) $\endgroup$ – Maarten Bodewes Dec 6 '18 at 16:19
  • $\begingroup$ Thanks! Actually, it is used for signing some sort of chip identification data ;). Assuming that our product's gonna be in the market for ~20 years... what kind of RSA key would you suggest? I have the options from 512-bit to 4096-bit and would tend to 2k, 3k or 4k. $\endgroup$ – TrinityTonic Dec 7 '18 at 9:04
  • 3
    $\begingroup$ @TrinityTonic: for something that long term, I wouldn't suggest RSA at all; it is plausible that someone would build a crypto-relevant Quantum Computer (that can break RSA of such key sizes) in the next 10-15 years. For something that needs to be shipped now, and needs to be secure that long, I'd suggest a hash based signature, such as LMS (datatracker.ietf.org/doc/draft-mcgrew-hash-sigs ) or XMSS (datatracker.ietf.org/doc/rfc8391 ) $\endgroup$ – poncho Dec 7 '18 at 13:46

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.