I just realized that supporting RSA with SHA-512 leads to an interface problem.
For RSA keys to work with PKCS#1 signatures, the modulo n has to be large enough. Up to now, I have used two defines, RSA_MINIMUM_N_OCTETS and RSA_MINIMUM_N_BITS, which are determined so that pkcs#1 works with *all* supported hash function.
The rsa_public_key_prepare and rsa_private_key_prepare functions check that n is large enough and returns a success/failure value. Then no other rsa functions are expected to ever fail due to n being too small.
With sha256, the minimum was 62 octets or 489 bits. But for sha512, the minimum is 94 octets or 745 bits. So if I just bump the RSA_MINIMUM_N_* accordingly, support for 512 bits RSA keys disappears. (And for comparison, with md5, the minimum is 353 bits).
I really hope noone still uses 512 bit RSA for anything important, but I nevertheless don't think it's appropriate to just drop support for it. Some applications may have modest security requirements where small keys are somehow appropriate, and then there are legacy applications and old keys. It should still be *possible* to verify signatures made many years ago, using 512-bit RSA, even though they can no longer be considered very secure.
I haven't figured out yet how I want to handle this, and I see no solution without its own problems. Some alternatives:
* Discontinue the RSA_MINIMUM_N_*, or use some reasonable value which isn't large enough for rsa-sha512. Let signature functions abort if they encounter a too small key. Possibly define new hash-specific constants, RSA_<hash>_MINIMUM_N_BITS or so.
* Add some argument to the rsa_*_key_prepare functions to say what the key is to be used for, so that it can check if the key is large enough. I don't quite like this; it's against the spirit of the rest of the Nettle interface.
* Introduce a return value for the signing functions, to let them return a success/failure indication. This is analogous to the rsa_encrypt function, which checks if the key size is large enough for the current message size. If we do this, is the return value from the rsa_*_key_prepare functions still useful?
I think it's less of a problem with public key operations, since signature verification and rsa decryption have a return value and for too small keys they can easily return fail for all messages. The problem is the signing functions.
No matter how the problem is solved, it will break backwards compatibility in some way. Suggestions?
Regards, /Niels
On 03/23/2010 04:16 PM, Niels Möller wrote:
I just realized that supporting RSA with SHA-512 leads to an interface problem.
ugh, sorry about this.
- Introduce a return value for the signing functions, to let them return a success/failure indication. This is analogous to the rsa_encrypt function, which checks if the key size is large enough for the current message size.
This sounds like the best option of the ones above; i really don't like the idea of the library aborting the calling program because of unexpected arguments.
would nettle still need to export RSA_MINIMUM_N_* with this option?
If we do this, is the return value from the rsa_*_key_prepare functions still useful?
I'm not sure about this -- i haven't used nettle widely enough to be able to give good feedback here.
No matter how the problem is solved, it will break backwards compatibility in some way. Suggestions?
yuck. it sounds like an soname bump will be needed. Do you know if any nettle client uses the #defines that we're talking about?
This exercise is probably a good one to go through (even though it's painful) so that nettle is flexible enough to be able to handle new message digests when they show up (e.g. when the SHA-3 contest reaches a conclusion).
Regards,
--dkg
Daniel Kahn Gillmor dkg@fifthhorseman.net writes:
- Introduce a return value for the signing functions, to let them return a success/failure indication.
This sounds like the best option of the ones above; i really don't like the idea of the library aborting the calling program because of unexpected arguments.
Hmm, I also think that alternative makes the most sense. Question is only how to deal with old programs.
would nettle still need to export RSA_MINIMUM_N_* with this option?
It's not mentioned in the manual, so I don't consider it a part of the advertised interface.
If we do this, is the return value from the rsa_*_key_prepare functions still useful?
I'm not sure about this -- i haven't used nettle widely enough to be able to give good feedback here.
Not sure what to do about these functions. The point of them is to compute and check the octet size of the key. Which is somewhat subtle in case of a private key; the private key structure includes p and q, but not n. And since #n = #p + #q *or* #p + #q - 1 (# denotes bit size), the only simple way to find the correct size of n in all cases is to perform the bignum multiplication p * q. (Maybe this can be improved too; in most cases I'd expect the caller to have n available).
No matter how the problem is solved, it will break backwards compatibility in some way. Suggestions?
yuck. it sounds like an soname bump will be needed. Do you know if any nettle client uses the #defines that we're talking about?
I think the backwards compatibility issue is more subtle than the removal of that #define, and its breaking backwards compatibility on both the source and binary level. The problem I see is as follows:
Program reads or generates a private rsa key which is too small for the hash functon it's going to be used with. The program calls rsa_private_key_prepare, checks return value like it should, and if everything is ok, goes on to call one of the signing functions.
With the released version of nettle, this program would detect the problem after calling rsa_private_key_prepare. But if the same program, with no changes, is recompiled or relinked with a version of nettle with the changes we're discussing, it will get no error from rsa_private_key_prepare, and the signing will fail. But since the program don't expect any return value, that error is silently ignored and the program will generate a bogus signature.
I think that when the signing functions fail, they should probably set the signature bignum to 0, so one at least won't leak the previous contents in the above scenario.
This exercise is probably a good one to go through (even though it's painful) so that nettle is flexible enough to be able to handle new message digests when they show up (e.g. when the SHA-3 contest reaches a conclusion).
With these changes, I don't exect any further problems there, but there may be other interface quirks that could be fixed at the same time.
Since it's inconvenient to have configure checks to test if a function has a return value, I may also be a good time to add some NETTLE_VERSION constants.
Regards, /Niels
nettle-bugs@lists.lysator.liu.se
-
Daniel Kahn Gillmor -
nisse＠lysator.liu.se