12
$\begingroup$

I am working on a device whose OS provides an RSA Private primitive, where the inputs are the message, and the usual components of a private key. Unfortunately it is bugged so that in some cases of supplying garbage for the private key, the device panics instead of returning an error code.

To try and avoid panics I would like to perform some pre-checks on the private key components. However, due to limited device resources, I'd prefer not to install a full Bignum library.

Are there any simple calculations I can do on the key components to check the key is valid? Time-efficiency is not a problem.

For example I can do peasant multiplication to verify $n = pq$; but what about validating $d_P$, $d_Q$, $q_{\mathrm{inv}}$ and $d$ ?

$\endgroup$
  • 1
    $\begingroup$ For some devices (like smart cards) doing a Russian peasant multiplication of the two prime factors is not a good idea, as it broadcasts one of the factors via power consumption, which can be easily attacked using Single Power Analysis. How is the key used on your device? For using it some Bignum libary has to be already available!? Can't you simply use the key once catching the exception? $\endgroup$ – hope that's a start Jan 10 '17 at 11:51
  • 4
    $\begingroup$ You could consider writing your own special-purpose bignum implementation. It'd be more work than using an existing library, but if space is constrained enough it might be worth it, since you can leave out any features that you don't need for RSA. For example, you don't need negative numbers or non-modular arithmetic, and you can fix the length of all numbers to equal that of the modulus. $\endgroup$ – Ilmari Karonen Jan 10 '17 at 14:30
  • $\begingroup$ Yeah, I second Ilmari here. BigNum calculations can be quite complex, but they don't need to be necessarily large or memory consuming. $\endgroup$ – Maarten Bodewes Jan 10 '17 at 14:48
  • 4
    $\begingroup$ You say the device fails on "some cases" of garbage; do you know what these cases are? $\endgroup$ – TonyK Jan 10 '17 at 17:29
  • $\begingroup$ @hopethat'sastart The operating system must have one but it doesn't expose that to me, it only exposes rsa public and rsa private operation. $\endgroup$ – M.M Jan 10 '17 at 22:35
14
$\begingroup$

Mathematical checks of the consistency of an RSA key can include: $$\begin{align*} e&\text{ odd}\\ n&\text{ odd, and of prescribed bit size (if any)}\\ p&\text{ odd, and of prescribed bit size (if any)}\\ q&\text{ odd, and of prescribed bit size (if any)}\\ n&=p\cdot q\\ 1&=(d_p\cdot e)\bmod(p-1)\\ 1&=(d_q\cdot e)\bmod(q-1)\\ 1&=(q\cdot q_\text{inv})\bmod p\\ d_p&<p-1\;\text{ [redundant with }d_p=d\bmod(p-1)\text{ ]}\\ d_q&<q-1\;\text{ [redundant with }d_q=d\bmod(q-1)\text{ ]}\\ q_\text{inv}&<p\\ d_p&=d\bmod(p-1)\\ d_q&=d\bmod(q-1)\\ \end{align*}$$ All parameters must be non-negative. In the above, $\bmod$ is akin to the %operator in C or java, extended to large integers. The upper range checks for $d_p$ and $d_q$ (and to some degree $q_\text{inv}$) are not mathematically indispensable, but are very customary and simplify the check of $d$, hence are included.

As pointed out by Maarten Bodewes, a primality check of $p$ and $q$ could also be performed; that will catch most random errors on these parameters. This will involve operations on large numbers though. And, chances that an accidental modification of the private key cause $p$ or $q$ to become composite while passing all the above checks is low.

In addition, some devices have extra requirements or/and perform extra checks that are not mathematically necessary. When not met, this could cause the observed device panic; in that case it would be a good idea to identify these requirements/checks, and externally check that they are met. Here is a list, believed exhaustive for industry-standard devices/libraries that I have happened to meet:

  • $d<n$, or perhaps the stronger $d<(p-1)(q-1)$, or the even stronger $d<(p-1)(q-1)/\gcd(p-1,q-1)$; that later one might be gaining traction since it is in FIPS 186-4, Appendix B.3.1 additional requirement 3(a) (at least for key generation).
  • $2^{2k-1}<n<2^{2k}$ for some specified values of $k$ (like $k\ge512$ with $k$ multiple of $2^w$ for some $w\ge7$, as in ANSI X9.31:1998; I have also seen lower minimum $k$, and lower $w$ down to 3); FIPS 186-4 requires $2k\in\{1024,2048,3072\}$ (at least for key generation).
  • If the above applies, that $2^{k-1}<p<2^k$ or the stronger $2^{k-1/2}<p<2^k$ (same bounds for $q$); FIPS 186-4 specifies the later, stronger bounds (at least for key generation).
  • That $|p-q|$ is above some threshold; FIPS 186-4 uses $2^{k-100}$. Notice that proper random generation of $p$ and $q$ makes this overwhelmingly probable, so much that this check is often (safely) skipped at key generation.
  • $e$ less than some threshold, like $2^{32}$ in an old Windows cryptoAPI, or $2^{256}$ in FIPS 186-4, or $n$ (that one is commonly specified), or $2^{2k}$ with $k$ as above.
  • $e\ge3$ (necessary for security), or $e\ge2^{16}+1$ (helping towards security of some variants of RSA with questionable padding), or $e=2^{16}+1$ (the most common value), or $e=3$ (the value leading to the simplest and fastest implementation of the public-key function, and believed safe for proper RSA padding).
  • I've seen code that requires some special condition on the high order bits of $n$ or/and $p$ and/or $q$ for reliable estimation of quotient in some modular reduction; or have other odd requirements on the public modulus; if that's not well documented, that's a bug.
  • I've once seen an implementation with a tendency to fail for large values of $q_\text{inv}$, and wondered if forcing $p<q$, or vice versa, would prevent that failure (note that exchanging $p$ and $q$ changes $q_\text{inv}$, though).

Various conditions beyond being prime are often specified for $p$ (and similarly $q$) at key generation; like, $p-1$ or/and $p+1$ having a large prime factor (a requirement in FIPS 186-4 for 1024-bit $n$); but I have never seen that checked after key generation (and such check would be uneasy). Similarly, I have seen requirements for a minimal value of $d$, but have never seen that enforced after key generation.

Note: it is rarely made actual use of both $d$ and $(p,q,d_p,d_q,q_\text{inv})$ for the same private key; sometime things will work without $d$, or with only $(n,e,d)$; that would simplify external checks.

A check that $n=p\cdot q$ can be conveniently performed modulo one auxiliary modulus $r$ (or a few relatively coprime moduli). We compute $\widehat n=n\bmod r$, $\widehat p=p\bmod r$, $\widehat q=q\bmod r$, and check that $\widehat n=(\widehat p\cdot\widehat q)\bmod r$. Convenient values of $r$ are $2^{32}-1$ (because modular reduction is easy; like casting out nines, only in base $2^{32}$ rather than base 10), and $2^{32}$ (which operates only on the low-order 32 bits of $n$, $p$, $q$; and thus should not be the only $r$ used for a check). As a consequence of the Chinese Remainder Theorem, these heuristic checks modulo $r$ become a proof if enough $r$ are used that the Least Common Multiple of all the $r$ is at least $n$.

An equivalent shortcut for operations involving $\bmod$ with a large right-hand operator is much more complex. It seems to involve computing the quotient. Assuming $e$ is less than 32-bit, to check that $1=(d_p\cdot e)\bmod(p-1)$ we might compute $x=\lfloor(d_p\cdot e)/p-0.05\rfloor$ using 64-bit floating point ($x$ will be less than $e$, thus fit 32 bits, and most often the correct quotient), then check that $x\cdot(p-1)+1=d_p\cdot e$ using reduction modulo a small $r$ (or a few ones), as above; if that check fails, we increase $x$ by one (always finding the right quotient if $d_p$, $e$ and $p$ are consistent), then repeat the check. But when the quotient gets large, basically we need full blown bignum arithmetic.

CAUTION: beware that most of the above checks (except those manipulating only $n$ and/or $e$) manipulate secret material, and thus can be vulnerable to side-channel attacks. These checks must be done in a safe environment (or protected against side channels such as timing or power analysis, which is complex).

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Checking $n = p \dot q \bmod 2^{32}$ will obviously fail to spot corruption of the high order bits of any of the values. $\endgroup$ – Henrick Hellström Jan 10 '17 at 12:20
  • 1
    $\begingroup$ Ideally, I guess one would like to ensure that $d < \lambda(n) = \operatorname{lcm}(p-1, q-1)$, but I suspect there may be RSA key generators that output $d$ values that fail that check. However, it should still always be valid to reduce $d$ modulo $\lambda(n)$. $\endgroup$ – Ilmari Karonen Jan 10 '17 at 14:23
6
$\begingroup$

Probably the easiest way to do this is to take a canonical encoding of the private key and compare it to a hash value. I presume a hash function is needed anyway to do anything sensible with the private key. The hash value over the contents of the key would normally be called a key check value.

Assuming that the sensitive private key values cannot be read (or replaced completely) it should be impossible even for an attacker to create a hash value for an altered key. You should however make sure that the sensitive parts of your key cannot be replaced for your protocol if you want to protect against active attacks.


You could also create a hash over the modulus and compare that with a stored hash. This is called a key ID. You could then perform the checks that fgrieu has supplied. Or you could simply perform your own signature generation and check it internally against the public key - I presume this operation is already available to you. If one of the components is off the signature should not verify.

Beware that different values may be used for "plain" RSA using just $e$ and $n$ or RSA using the components required for the Chinese Remainder Theorem when doing the checks described by fgrieu or when doing the signature verification. CRT parameters may not always be available - a key can be valid without them.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Verifying a MAC or signature over the private key values would be even better of course, but that's harder to do. Since the private key should have enough entropy you should be OK with just a hash - as long as the set private key + hash cannot be replaced. $\endgroup$ – Maarten Bodewes Jan 10 '17 at 14:22
  • $\begingroup$ What scenario do you imagine where the attacker would be able to substitute the private key, but not the private key plus the hash? And my understanding of the question is that the device can import multiple private keys, and the point is to validate, not authorize, a private key. $\endgroup$ – Gilles 'SO- stop being evil' Jan 10 '17 at 14:34
  • $\begingroup$ @Gilles Yeah, I was clearing this up right before you posted this comment. I'm mainly targeting validation as well, the fact that an attacker cannot easily alter parts of the key without validation failing is mainly a bonus. You can of course separate the hash and private key value into multiple systems, with different levels of access (spread the hash around or sign it and keep the private key - eh - private). $\endgroup$ – Maarten Bodewes Jan 10 '17 at 14:37
2
$\begingroup$

The simplest solution would be to use OpenSSL's RSA_check_key() function.

Or from the command line:

$ openssl rsa -check -in good.key -noout
RSA key ok

# (change 1 bit of key data)
$ openssl rsa -check -in bad.key -noout
RSA key error: dmp1 not congruent to d
| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Evidently openssl is not an option since even a mere bignum library has a significant cost. $\endgroup$ – Gilles 'SO- stop being evil' Jan 10 '17 at 14:35
  • 1
    $\begingroup$ @Gilles On the other hand, OpenSSL is going to have far fewer flaws and side channel vulnerabilities than any hand-rolled software. I think it would be more prudent to invest a little more now in memory and processing power, instead of hoping that no problems come to light further down the road. $\endgroup$ – r3mainer Jan 10 '17 at 14:58
  • $\begingroup$ The OP may want to take a look at (and trust) what RSA_check_key does, and reimplement it for a memory-constrained environment. $\endgroup$ – pts Jan 10 '17 at 19:25
  • 2
    $\begingroup$ @squeamishossifrage “OpenSSL is going to have far fewer flaws” Hold on, this is Openssl we're talking about, not some library with a good reputation. And you're talking not just about “a little more” if the device is running a custom OS with limited libraries, but several orders of magnitude. As someone who works on such a custom OS, and who thinks we do a better job at implementing crypto than OpenSSL, I have to say that the suggestion to use OpenSSL is completely ludicrous. $\endgroup$ – Gilles 'SO- stop being evil' Jan 10 '17 at 22:45
  • 1
    $\begingroup$ @Gilles So you reckon it's safer to implement your own crypto libraries than to use OpenSSL? That sounds like hubris to me. $\endgroup$ – r3mainer Jan 11 '17 at 9:58
0
$\begingroup$

As you write that you can call the private and the public operations on the imported key, why don't you simply use these two operations to verify that the key is not corrupted? After importing the key, just try calling the available functions catching possible exceptions. Of course this works best, if you know also the matching public key.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ The device panics if the key is corrupted and I call the private operation $\endgroup$ – M.M Jan 11 '17 at 12:11
  • $\begingroup$ @M.M: The "panic" cannot be controlled?! That's a pity. $\endgroup$ – hope that's a start Jan 11 '17 at 12:31
  • $\begingroup$ @M.M: Am I right in thinking that the crypto operations are given to you as library programmed by another company (not source code)? Can you tell me what kind of device it is? $\endgroup$ – hope that's a start Jan 11 '17 at 12:34
  • $\begingroup$ You're right in thinking that, I'd rather not go into more detail - I don't want to start hacking their binaries or anything $\endgroup$ – M.M Jan 12 '17 at 4:42

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.