RSA keys: 2047 bits == 2048 bits?

[Paul Tiemann]

Technical question:

"All CAs should stop issuing intermediate and end-entity certificates with RSA key size smaller than 2048 bits."

https://wiki.mozilla.org/CA:MD5and1024

I've heard that 2047 bits is equivalent to 2048 bits. Some platforms (Cisco VPNs, IIS) sometimes generate 2047 bit RSA keys. If the security is equivalent, can we accept these CSRs without forcing the customer to go back and generate their keys again and hope for a 2048 bit output?

Should we modify the language to make allowance for those cases?

Paul Tiemann
CTO, DigiCert

[Brian Smith]

Paul Tiemann wrote:
> "All CAs should stop issuing intermediate and end-entity certificates
> with RSA key size smaller than 2048 bits."
>
> https://wiki.mozilla.org/CA:MD5and1024
>
> I've heard that 2047 bits is equivalent to 2048 bits. Some platforms
> (Cisco VPNs, IIS) sometimes generate 2047 bit RSA keys. If the
> security is equivalent, can we accept these CSRs without forcing the
> customer to go back and generate their keys again and hope for a 2048
> bit output?

This is basically the issue that Kasper mentioned here, right?:
https://bugzilla.mozilla.org/show_bug.cgi?id=360126#c10

If so, then my understanding is that insisting on a 2048 bit key (vs 2047) is basically insisting that the 2048th bit to be one (1). I don't see how that is helpful.

> Should we modify the language to make allowance for those cases?

Sure. Presumably, when we have an n-bit minimum limit for an RSA private key, we should allow keys of n-7 bits or more, up to the maximum limit we set, assuming n is a multiple of 8. This might not be appropriate for all algorithms though. It should be decided on an algorithm-by-algorithm basis.

- Brian

[Peter Gutmann]

Paul Tiemann <paul.tiem...@gmail.com> writes:

>I've heard that 2047 bits is equivalent to 2048 bits. Some platforms (Cisco
>VPNs, IIS) sometimes generate 2047 bit RSA keys. If the security is
>equivalent, can we accept these CSRs without forcing the customer to go back
>and generate their keys again and hope for a 2048 bit output?

Unless you take special steps in your keygen (by setting fixed bit patterns in
the high bits of the primes) you're going to occasionally get keys shorter
than the nominal 2048 bits as part of the standard keygen process. My code
allows keys a few bits shorter than the nominal size because they're going to
turn up and it's effectively the same thing anyway.

The counterargument to this is that since the use of 2048 bits is pure
numerology, any deviation from the mystical values is a sin, and so the 2048-
bit magic number should be strictly enforced.

Peter.

[Paul Tiemann]

(Thanks very much to everyone who gave an answer today! I just picked Brian's to reply to - but I really appreciate the helpful replies and thoughts.)

On Nov 29, 2011, at 10:12 AM, Brian Smith wrote:

> Paul Tiemann wrote:
>> "All CAs should stop issuing intermediate and end-entity certificates
>> with RSA key size smaller than 2048 bits."
>>
>> https://wiki.mozilla.org/CA:MD5and1024
>>

>> I've heard that 2047 bits is equivalent to 2048 bits. Some platforms
>> (Cisco VPNs, IIS) sometimes generate 2047 bit RSA keys. If the
>> security is equivalent, can we accept these CSRs without forcing the
>> customer to go back and generate their keys again and hope for a 2048
>> bit output?
>

> This is basically the issue that Kasper mentioned here, right?:
> https://bugzilla.mozilla.org/show_bug.cgi?id=360126#c10

Yeah, I think it's that same issue.

> If so, then my understanding is that insisting on a 2048 bit key (vs 2047) is basically insisting that the 2048th bit to be one (1). I don't see how that is helpful.

+1

>> Should we modify the language to make allowance for those cases?
>
> Sure. Presumably, when we have an n-bit minimum limit for an RSA private key, we should allow keys of n-7 bits or more, up to the maximum limit we set, assuming n is a multiple of 8. This might not be appropriate for all algorithms though. It should be decided on an algorithm-by-algorithm basis.
>
> - Brian

I'd love it if the document said something like "RSA 2048 is required (understanding that 2047 bits is 2048 bit equivalent)" to allow for 2047, because I'd actually prefer to face unenlightened critics than to force customers to do meaningless supplicatory dances. The 2047 bit police (if any) deserve a little enlightenment, but the customers don't deserve the runaround.

Paul

[Peter Gutmann]

Paul Tiemann <paul.tiem...@gmail.com> writes:

>I'd love it if the document said something like "RSA 2048 is required
>(understanding that 2047 bits is 2048 bit equivalent)" to allow for 2047,
>because I'd actually prefer to face unenlightened critics than to force
>customers to do meaningless supplicatory dances. The 2047 bit police (if
>any) deserve a little enlightenment, but the customers don't deserve the
>runaround.

In that case I'd use words like "within a few bits of 2048 bits", because with
purely randomly-chosen primes and no special tricks you can, with rapidly
decreasing probabilities, get values less than 2048, and if you've got keygen
baked into firmware then you're not going to get it changed in a hurry.

Peter.