Subject: S/MIME v3.2 IDs key size text

From: "Turner, Sean P." <[email-masked]>
Date: Wed, 19 Mar 2008 15:07:41 -0400

The key size text is the remaining issue with the S/MIME v3.2 IDs.  What I'm
hoping to do is consensus on the text so we can issue a WG LC on these two
IDs. To make sure there's no confusion I've included the old and new text
from the two IDs. If you have comments on the new text please be specific
about the change you are proposing.

spt

--------------

In 3850bis, the update is to section 4.3 (this is the only sentence that
refers to key sizes):

(old) Key sizes from 512 bits to 2048 bits MUST be supported.

(new) Key sizes from 1024 bits to 2048 bits MUST be supported.

In 3851bis, the update is to section 4.1:

(old) If an S/MIME agent needs to generate an RSA key pair, then the S/MIME
agent or some related administrative utility or function SHOULD generate RSA
key pairs using the following guidelines.  A user agent SHOULD generate RSA
key pairs at a minimum key size of 768 bits.  A user agent MUST NOT generate
RSA key pairs less than 512 bits long. Creating keys longer than 1024 bits
can cause some older S/MIME receiving agents to not be able to verify
signatures, but gives better security and is therefore valuable.  A
receiving agent SHOULD be able to verify signatures with keys of any size
over 512 bits. Some agents created in the United States have chosen to
create 512 bit keys in order to get more advantageous export licenses.
However, 512 bit keys are considered by many to be cryptographically
insecure. Implementers SHOULD be aware that multiple (active) key pairs can
be associated with a single individual.  For example, one key pair can be
used to support confidentiality, while a different key pair can be used for
authentication.

(new) If an S/MIME agent needs to generate an RSA key pair, then the S/MIME
agent or some related administrative utility or function SHOULD generate RSA
key pairs using the following guidelines.  A user agent SHOULD generate RSA
key pairs at a minimum key size of 1024 bits.  A user agent MUST NOT
generate RSA key pairs less than 1024 bits long. Creating keys longer than
1024 bits can cause some older S/MIME receiving agents to not be able to
verify signatures, but gives better security and is therefore valuable.  A
receiving agent SHOULD be able to verify signatures with keys of any size
over 512 bits. 

- the last four sentences from old text were moved to the security
considerations.

---

From: "Tony Capel" <[email-masked]>
Date: Wed, 19 Mar 2008 16:12:22 -0400

My only concern is making key size generation requirements a MANDATORY part of
this standard.  I understand it may have been appropriate in the past.

I agree with making non-mandatory RECOMMENDATIONS regarding key size generation.
Also agree with making support for minimum key size ranges mandatory.  And have
no problems with the sizes proposed.

However MANDATING (MUST/MUST-NOT) the generation and use of specific minimum
sizes (or algorithms for that matter) seems to me to be better addressed by Cert
Policies, etc. - and indeed in many cases key generation and use ends up being
imposed by the PKI design - and defined in the corresponding CP - anyway.

I agree the RFC should set out as mandatory the minimum specifications required
to ensure a high likelihood of interoperability.  However, if users choose to
use small keys (and are allowed to under their CP) then does this make the
implementation non-compliant to S/MIME v3.2?  For example, if S/MIME is used to
implement a compartmentalized security policy and used over a secure
infrastructure, do we presume to say a 768 bit key is insufficient for this
particular application?  

The only change I would suggest is to remove the sentence:
" A user agent MUST NOT generate RSA key pairs less than 1024 bits long"

The previous sentence to this already captures the RECOMMENDATION against keys
of less than 1024 anyway.

I think in earlier versions of the RFC it was appropriate to mandate minimum key
sizes, but nowadays, we should leave this decision to the designers who are
working against the threat and risk assessment (and sure, include
recommendations aimed at less sophisticated users).

Tony

| -----Original Message-----
| From: [email-masked] 
| [mailto:[email-masked]] On Behalf Of Turner, Sean P.
| Sent: March 19, 2008 3:08 PM
| To: [email-masked]
| Subject: S/MIME v3.2 IDs key size text
| 
| 
| 
| The key size text is the remaining issue with the S/MIME v3.2 
| IDs.  What I'm hoping to do is consensus on the text so we 
| can issue a WG LC on these two IDs. To make sure there's no 
| confusion I've included the old and new text from the two 
| IDs. If you have comments on the new text please be specific 
| about the change you are proposing.
| 
| spt
| 
| --------------
| 
| In 3850bis, the update is to section 4.3 (this is the only 
| sentence that refers to key sizes):
| 
| (old) Key sizes from 512 bits to 2048 bits MUST be supported.
| 
| (new) Key sizes from 1024 bits to 2048 bits MUST be supported.
| 
| In 3851bis, the update is to section 4.1:
| 
| (old) If an S/MIME agent needs to generate an RSA key pair, 
| then the S/MIME agent or some related administrative utility 
| or function SHOULD generate RSA key pairs using the following 
| guidelines.  A user agent SHOULD generate RSA key pairs at a 
| minimum key size of 768 bits.  A user agent MUST NOT generate 
| RSA key pairs less than 512 bits long. Creating keys longer 
| than 1024 bits can cause some older S/MIME receiving agents 
| to not be able to verify signatures, but gives better 
| security and is therefore valuable.  A receiving agent SHOULD 
| be able to verify signatures with keys of any size over 512 
| bits. Some agents created in the United States have chosen to 
| create 512 bit keys in order to get more advantageous export 
| licenses. However, 512 bit keys are considered by many to be 
| cryptographically insecure. Implementers SHOULD be aware that 
| multiple (active) key pairs can be associated with a single 
| individual.  For example, one key pair can be used to support 
| confidentiality, while a different key pair can be used for 
| authentication.
| 
| (new) If an S/MIME agent needs to generate an RSA key pair, 
| then the S/MIME agent or some related administrative utility 
| or function SHOULD generate RSA key pairs using the following 
| guidelines.  A user agent SHOULD generate RSA key pairs at a 
| minimum key size of 1024 bits.  A user agent MUST NOT 
| generate RSA key pairs less than 1024 bits long. Creating 
| keys longer than 1024 bits can cause some older S/MIME 
| receiving agents to not be able to verify signatures, but 
| gives better security and is therefore valuable.  A receiving 
| agent SHOULD be able to verify signatures with keys of any 
| size over 512 bits. 
| 
| - the last four sentences from old text were moved to the 
| security considerations.
|

---

From: Paul Hoffman <[email-masked]>
Date: Wed, 19 Mar 2008 13:43:29 -0700

>(new) Key sizes from 1024 bits to 2048 bits MUST be supported.

This is about verification, not about signing. Why should we increase 
it from 512 bits? I support leaving it as in RFC 3850 at 512 bits.

>receiving agent SHOULD be able to verify signatures with keys of any size

I fully disagree with "MUST NOT generate RSA key pairs less than 1024 
bits long". A signature that is of little value that is only supposed 
to last a week is fine at 512 bits.

---

From: Russ Housley <[email-masked]>
Date: Wed, 19 Mar 2008 16:48:25 -0400

Sean:

>A receiving agent SHOULD be able to verify signatures with keys of any size
>over 512 bits.

This is asking for denial of service attack.  What if someone sends a 
certificate that contains a 64Kbit value claiming to be a public key 
and a blob of random bits claiming to be a signature?  The amount of 
time to check the signature (and probably find that it is not valid) 
is onerous.

Today, I cannot imagine someone making use of a public key larger 
than 8192 bits.  Double that it you want to be very future proof.

Russ

---

From: "Turner, Sean P." <[email-masked]>
Date: Tue, 25 Mar 2008 10:16:42 -0400

Russ,

This sounds reasonable. I replace the following sentence in 3851bis:

with 

A receiving agent SHOULD be able to verify signatures with keys up to 16384
bits.

spt

>-----Original Message-----
>From: [email-masked] 
>[mailto:[email-masked]] On Behalf Of Russ Housley
>Sent: Wednesday, March 19, 2008 4:48 PM
>To: Turner, Sean P.; [email-masked]
>Subject: Re: S/MIME v3.2 IDs key size text
>
>
>Sean:
>
>>A receiving agent SHOULD be able to verify signatures with 
>keys of any 
>>size over 512 bits.
>
>This is asking for denial of service attack.  What if someone 
>sends a certificate that contains a 64Kbit value claiming to 
>be a public key and a blob of random bits claiming to be a 
>signature?  The amount of time to check the signature (and 
>probably find that it is not valid) is onerous.
>
>Today, I cannot imagine someone making use of a public key 
>larger than 8192 bits.  Double that it you want to be very 
>future proof.
>
>Russ 
>

---

From: "Turner, Sean P." <[email-masked]>
Date: Tue, 25 Mar 2008 10:14:58 -0400

Tony,

This sounds reasonable, I'll remove the sentence.

spt 

>From: Tony Capel [mailto:[email-masked]] 
>Sent: Wednesday, March 19, 2008 4:12 PM
>To: 'Turner, Sean P.'; [email-masked]
>Subject: RE: S/MIME v3.2 IDs key size text
>
>My only concern is making key size generation requirements a 
>MANDATORY part of this standard.  I understand it may have 
>been appropriate in the past.
>
>Also agree with making support for minimum key size ranges 
>mandatory.  And have no problems with the sizes proposed.
>
>However MANDATING (MUST/MUST-NOT) the generation and use of 
>specific minimum sizes (or algorithms for that matter) seems 
>to me to be better addressed by Cert Policies, etc. - and 
>indeed in many cases key generation and use ends up being 
>I agree the RFC should set out as mandatory the minimum 
>specifications required to ensure a high likelihood of 
>interoperability.  However, if users choose to use small keys 
>(and are allowed to under their CP) then does this make the 
>implementation non-compliant to S/MIME v3.2?  For example, if 
>S/MIME is used to implement a compartmentalized security 
>policy and used over a secure infrastructure, do we presume to 
>say a 768 bit key is insufficient for this particular application?  
>
>The previous sentence to this already captures the 
>RECOMMENDATION against keys of less than 1024 anyway.
>
>I think in earlier versions of the RFC it was appropriate to 
>mandate minimum key sizes, but nowadays, we should leave this 
>decision to the designers who are working against the threat 
>and risk assessment (and sure, include recommendations aimed 
>at less sophisticated users).
>
>Tony
>
>
>| The key size text is the remaining issue with the S/MIME v3.2 IDs.  
>| What I'm hoping to do is consensus on the text so we can 
>issue a WG LC 
>| on these two IDs. To make sure there's no confusion I've 
>included the 
>| old and new text from the two IDs. If you have comments on the new 
>| text please be specific about the change you are proposing.
>| 
>| spt
>| 
>| --------------
>| 
>| In 3850bis, the update is to section 4.3 (this is the only sentence 
>| that refers to key sizes):
>| 
>| (old) If an S/MIME agent needs to generate an RSA key pair, then the 
>| S/MIME agent or some related administrative utility or 
>function SHOULD 
>| generate RSA key pairs using the following guidelines.  A user agent 
>| SHOULD generate RSA key pairs at a minimum key size of 768 bits.  A 
>| user agent MUST NOT generate RSA key pairs less than 512 bits long. 
>| Creating keys longer than 1024 bits can cause some older S/MIME 
>gives better 
>| security and is therefore valuable.  A receiving agent 
>SHOULD be able 
>| to verify signatures with keys of any size over 512 bits. 
>Some agents 
>| created in the United States have chosen to create 512 bit keys in 
>| order to get more advantageous export licenses. However, 512 
>bit keys 
>| are considered by many to be cryptographically insecure. 
>Implementers 
>| SHOULD be aware that multiple (active) key pairs can be associated 
>| with a single individual.  For example, one key pair can be used to 
>| support confidentiality, while a different key pair can be used for 
>| authentication.
>| 
>| (new) If an S/MIME agent needs to generate an RSA key pair, then the 
>| S/MIME agent or some related administrative utility or 
>function SHOULD 
>| generate RSA key pairs using the following guidelines.  A user agent 
>| SHOULD generate RSA key pairs at a minimum key size of 1024 bits.  A 
>| user agent MUST NOT generate RSA key pairs less than 1024 bits long. 
>| Creating keys longer than 1024 bits can cause some older S/MIME 
>gives better 
>| security and is therefore valuable.  A receiving agent 
>SHOULD be able 
>| to verify signatures with keys of any size over 512 bits.
>| 
>| - the last four sentences from old text were moved to the security 
>| considerations.
>| 
>

---

From: "Turner, Sean P." <[email-masked]>
Date: Tue, 25 Mar 2008 10:15:21 -0400

Paul,

These sounds reasonable. To resolve the 2nd comment I'm deleting the
sentence, which Tony also commented on.

spt

>[mailto:[email-masked]] On Behalf Of Paul Hoffman
>Sent: Wednesday, March 19, 2008 4:43 PM
>>In 3850bis, the update is to section 4.3 (this is the only sentence 
>>that refers to key sizes):
>>
>This is about verification, not about signing. Why should we 
>increase it from 512 bits? I support leaving it as in RFC 3850 
>at 512 bits.
>
>>
>>(old) If an S/MIME agent needs to generate an RSA key pair, then the 
>>S/MIME agent or some related administrative utility or 
>function SHOULD 
>>generate RSA key pairs using the following guidelines.  A user agent 
>>SHOULD generate RSA key pairs at a minimum key size of 768 bits.  A 
>>user agent MUST NOT generate RSA key pairs less than 512 bits long. 
>>Creating keys longer than 1024 bits can cause some older S/MIME 
>>receiving agents to not be able to verify signatures, but 
>gives better 
>>security and is therefore valuable.  A receiving agent SHOULD be able 
>>to verify signatures with keys of any size over 512 bits. Some agents 
>>created in the United States have chosen to create 512 bit 
>keys in order to get more advantageous export licenses.
>>insecure. Implementers SHOULD be aware that multiple (active) 
>key pairs 
>>can be associated with a single individual.  For example, one 
>key pair 
>>can be used to support confidentiality, while a different key 
>pair can 
>>be used for authentication.
>>
>>(new) If an S/MIME agent needs to generate an RSA key pair, then the 
>>S/MIME agent or some related administrative utility or 
>function SHOULD 
>>generate RSA key pairs using the following guidelines.  A user agent 
>>SHOULD generate RSA key pairs at a minimum key size of 1024 bits.  A 
>>user agent MUST NOT generate RSA key pairs less than 1024 bits long. 
>>Creating keys longer than
>>1024 bits can cause some older S/MIME receiving agents to not be able 
>>to verify signatures, but gives better security and is therefore 
>>valuable.  A receiving agent SHOULD be able to verify signatures with 
>>keys of any size over 512 bits.
>
>I fully disagree with "MUST NOT generate RSA key pairs less 
>than 1024 bits long". A signature that is of little value that 
>is only supposed to last a week is fine at 512 bits.
>

---

From: Paul Hoffman <[email-masked]>
Date: Tue, 25 Mar 2008 11:11:32 -0700

>A receiving agent SHOULD be able to verify signatures with keys up to 16384

I disagree with the upper limit. Verifying signatures with 16K bit 
keys is very difficult for constrained  devices; this "SHOULD" may 
have the effect of making device makers need to use faster CPUs than 
they would normally want to have.

It is unclear which part of the SHOULD is not a MUST here. Because we 
are talking only about interoperability, then the number is 1024, 
which is what the key creators SHOULD be making. But that is clearly 
a lower bound of what a typical receiver might expect. Therefore, a 
short sentence like the one proposed is insufficient. How about:

A receiving agent needs to be able to verify signatures whose key 
length is chosen by the signer. At a minimum, a receiving agent MUST 
be able to verify signatures whose key length is 1024 bits or 
shorter. However, most receiving agents are likely to see signatures 
whose key length is longer than that during the next decade.

---

From: Russ Housley <[email-masked]>
Date: Tue, 25 Mar 2008 15:57:05 -0400

Paul:

How would you suggest warning people that they should not attempt to 
handle really huge keys?  Would you put it in the security 
consideration instead?

Russ

At 02:11 PM 3/25/2008, Paul Hoffman wrote:

>It is unclear which part of the SHOULD is not a MUST here. Because 
>we are talking only about interoperability, then the number is 1024,

---

From: Paul Hoffman <[email-masked]>
Date: Tue, 25 Mar 2008 13:38:23 -0700

>handle really huge keys?  Would you put it in the security 

Sure. It is a consideration ("don't fall for a DoS attack"), it's not 
an interoperability issue for a SHOULD or MUST.

---

From: Dr Stephen Henson <[email-masked]>
Date: Tue, 25 Mar 2008 21:34:02 +0000

Paul Hoffman wrote:
> 
> 
> I disagree with the upper limit. Verifying signatures with 16K bit keys 
> is very difficult for constrained  devices; this "SHOULD" may have the 
> effect of making device makers need to use faster CPUs than they would 
> normally want to have.
> 

I made a study of the use of public keys in a DoS attack a while ago.

It isn't merely a key size issue. A signature using a 16K key and a 
small public exponent (such as 65537) can be verified using far less
effort than one with a 16K public exponent.

A separate issue is whether such a signature is verified before or after 
the certificate itself is verified and whether one can persuade a CA to 
issue a certificate containing such a key.

Steve.
-- 
Dr Stephen N. Henson.
Core developer of the   OpenSSL project: http://www.openssl.org/
Freelance consultant see: http://www.drh-consultancy.co.uk/
Email: [email-masked], PGP key: via homepage.

---

From: Russ Housley <[email-masked]>
Date: Tue, 25 Mar 2008 18:02:28 -0400

Steve:

>A separate issue is whether such a signature is verified before or 
>after the certificate itself is verified and whether one can 
>persuade a CA to issue a certificate containing such a key.

Indeed, this is the best solution.  Perhaps we should drop the max 
size limit and discuss this point in the security considerations.

Russ

---

From: Blake Ramsdell <[email-masked]>
Date: Tue, 25 Mar 2008 15:04:43 -0700

On Tue, Mar 25, 2008 at 09:34:02PM +0000, Dr Stephen Henson wrote:
>  It isn't merely a key size issue. A signature using a 16K key and a small 
>  public exponent (such as 65537) can be verified using far less

Based on this and Paul's comments, I think that there are definitely two
separate issues:

1. Guidance for interoperability (MUST / SHOULD for keylengths)

2. Security considerations (don't bite off keys bigger than you can chew)

Unfortunately, this opens up a new can of worms for the security
considerations -- how do you specify the right combination of exponent and
modulus values for RSA that are a problem? Are there a similar set of
giant parameters that might be used with DSA?

Blake
-- 
Blake Ramsdell | Sendmail, Inc. | http://www.sendmail.com

---

From: [email-masked] (Peter Gutmann)
Date: Tue, 01 Apr 2008 00:11:17 +1300

>I made a study of the use of public keys in a DoS attack a while ago.

I made an indirect study via SSH a few years ago.  The client I was using (no
choice, it was corporate policy) froze solid for about 5s doing a 4Kbit key
exchange with an SSH server.  When I complained to the server admin, his
response was that the spec allowed up to 4Kbit keys and numerous other servers
were run this way as well, so that's what he was using.

Building the tools for a DoS into the spec, especially a self-inflicted one,
doesn't seem like a good idea.  Give a geek a device with controls that go to 
11 and they'll set them to 11 and leave them there.

Peter.

---

From: [email-masked] (Peter Gutmann)
Date: Tue, 01 Apr 2008 00:07:10 +1300

>A receiving agent SHOULD be able to verify signatures with keys up to 16384

Even that's a significant DoS.  What about MUST to 4K and MAY to 16K, with a
note about the DoS issue?

The 16Kbit value is going to cause the same problems as 256-bit keys do for
AES, once you give some arbitrary large upper bound it creates the perception
that keys of the same size as the upper bound are somehow "better" than
smaller-sized keys, and so all the tinfoil-hat implementations will insist on
using 16Kbit keys, and then others will have to follow in order to be as
"good" as the tinfoil-hat versions.

Also, how many implementations actually support 16Kbit values?  How much
legacy hardware can handle 16Kbit keys?  How many smart cards can do 16Kbit
keys?  Specifying this is opening a real can of worms...

Peter.

---

From: [email-masked] (Peter Gutmann)
Date: Tue, 01 Apr 2008 00:20:59 +1300

Blake Ramsdell <[email-masked]> writes:

>modulus values for RSA that are a problem? Are there a similar set of giant
>parameters that might be used with DSA?

I know that someone else on this list has looked at DoS-enabling parameters in
the past so maybe they'll want to comment, I've looked at this too and (for
example) feeding a DLP-based key exchange that expects g = 2 a value of g
that's something much, much larger than 2 (like 2^256 times larger), or an RSA
key where e is a bignum, can lead to disappointing effects at the other end.
(that is, you can trivially knock a server off the net with this... apologies
if I tried this on your server :-).  Taking out an S/MIME gateway shouldn't be
much more difficult.

Having said that, my code checks for stupid parameter values and has never had
any (reported) problems with rejecting keys, so it seems quite possible to
restrict yourself to sensible/safe values without adverse side-effects.

Peter.

---

From: Dr Stephen Henson <[email-masked]>
Date: Mon, 31 Mar 2008 13:23:18 +0100

> if I tried this on your server :-).  Taking out an S/MIME gateway shouldn't be

The study was a small and didn't look in a huge amount of detail but the 
results agree with the above paragraph pretty well.

16K keys with 16K e can lock up modern systems (or what counted for 
modern systems a when I checked a couple of years back) for several 
minutes and 8K keys with 8K e tens of seconds. So embedding large 
numbers of requests with such keys could easily cause problems.

Some implementations (by accident or design) restrict e to 32 bits in size.

A separate issue was where such verification of keys might take place.

If a CA issues a trusted EE certificate with such a key then an 
implementation will check the signature if it doesn't reject large 
parameters. But it would be a less useful attack since the certificate 
should reveal some details of the attacker's identity.

In practice an attempt might be made using untrusted certificates.

The signature using the EE certificate key may be checked either before 
the certificate chain is validated or performed even if the chain 
validation fails as useful debugging information.

A separate attack could be performed during chain validation itself. 
This depends on the order certificate signatures are checked.

Consider a forged chain from trust anchor TA to end entity certificate EE...

TA->CA1->CA2->CA3....->EE

Where the signature of CA1 is bogus but all others are valid. An 
implementation might check signatures from TA to EE and reject the chain 
on the first invalid signature.

If an implementation checks from EE to TA it will only reject the chain 
after checking several CA signatures along the way. If the bogus CAn 
certificates have such keys this could itself be a DoS attack.

Alternatively it might check all signature for debugging purposes even 
after a failure.

Steve.

---

From: Simon Josefsson <[email-masked]>
Date: Mon, 31 Mar 2008 16:50:03 +0200

> restrict yourself to sensible/safe values without adverse side-effects.

What are the "stupid parameters" boundaries that you use?  I'd like to
consider adopting something similar.  Using values that someone else has
already tried appear less likely to introduce new problems.

/Simon