Subject: RE: Straw poll for Algorithm Identifiers in Subject Public Key Info.

From: Stefan Santesson <[email-masked]>
Date: Tue, 16 Jan 2007 00:15:40 +0000

Russ,
I promised to come back on this issue after some more investigations. Sorry for the somewhat long reply.

For my rationales and reasoning I use the following simplified architectural model with some example modules.

                                   ------------
Apps                               |  E-mail  |
                                   ------------
                                        |
                  ---------        -----------    ---------
Protocol stacks   | TLS   |        |  S/MIME |    | IPSEC |
                  ---------        -----------    ---------
                      |                 |             |
                      ---------------------------------
                           |                    |
                  -----------------  -------------------------
Libraries         | Crypto Library|  | cert chain validation |
                  -----------------  -------------------------

This is not the only possible model but it is the one we use for the basis of certificate usage.

The initiative to use a certificate and its key comes from either an application or a protocol stack. For TLS it will come from the protocol stack. For E-mail it may come from the application itself.
The central problem with usage restrictions embedded with the subject public key OID is how to enforce it. When the application or the protocol stack wants to use a certificate it sends it to the validation module to verify and decode the certificate. The information returned contains the algorithm OID and the public key. The Crypto library in this example doesn't understand OIDs, so the app needs to do a translation to an internal AlgorithmID understood by the crypto library. In our environment the app/protocol can use a common OID table to do that. It also needs to map this usage to the algorithm usage negotiated in the protocol stack, e.g. map to a TLS cipher suite. So in worse case the app has 3 Algorithm IDs to map (Crypto library alg ID, Protocol alg ID and Cert alg ID).

Even if the common OID table is used, the cert alg ID may differ from the Crypto library alg ID. For example the former may be and ID for ECC-DSA, while the latter may be ECC-DSA-SHA256.

In addition to this the app or protocol stack needs to make sure this is consistent with any key usage set.

Adding this feature in the RFC4055 style is not impossible but it needs to be individually implemented in each cert using protocol and application. This is not trivial considering that legacy is a big complicating factor. In principle it worries me to put this complex mapping burden on applications. Another threat with this approach is if it leads to a requirement to define combinations of algorithm modes by single OIDs where we may end up with a very large space of OIDs.

Looking at this from an extension approach, we would have the option of critical/non critical. If the extension is critical, the cert validation module will return an unrecognized critical extension error, forcing the application to assume responsibility for honoring this extension or fail. This is a better guarantee for preventing misuse by applications. The extension could potentially contain mapping data that is more suitable for mapping usage towards the different alg IDs provided in different protocols. However this may cause the extension syntax to be overly complex.

The worse scenario of all the choices is the structured Certificates OID (á la X9.62), listing sub OIDs for acceptable algorithmic modes. This would create the most complex and confusing mapping graph for the applications and protocol stacks as it now has a magnitude of OIDs to map to algorithm IDs of the crypto library as well as Alg IDs from the protocol. As such it is the least favorable alternative.

In summary,

- The RFC 4055 approach is the simplest to define but is still hard to fully implement and we have to trust applications to get it right.

- The extension approach is the hardest to define but is friendlier to a gradual implementation and has the best prevention from applications getting it wrong.

- The structured algorithm OID is maybe not the hardest to define but the worse alternative in every other aspect.

My primary choice would be to not enforce algorithmic modes in certificates at all unless there is a cryptographic weakness in the algorithm to protect. As such the protocol usage negotiation should be solved on the protocol level. Then we only need 1 OID for ECC keys (defined in RFC 3279). The RFC 4055 OIDs would still exist for the legitimate reasons above, but we would not need any new OIDs for ECC.

If the WG decides that mode restriction for ECC keys is necessary then we need to choose the least evil alternative and I currently feel unsure of what that would be.

Stefan Santesson
Senior Program Manager
Windows Security, Standards

> -----Original Message-----
> From: Russ Housley [mailto:[email-masked]]
> Sent: den 15 december 2006 12:13
> To: Stefan Santesson
> Cc: [email-masked]
> Subject: RE: Straw poll for Algorithm Identifiers in Subject Public Key
> Info.
>
> Stefan:
>
> >I respect the need for clarification. In short, when the function of
> >OIDs not only instructions to the key import functions, but also a
> >constraining mechanism for the signing module, this poses an
> >architectural challenge. I will get back with more elaborate
> >information. It seems that this would not only be a problem for us
> >so others may also contribute with more elaborate description of the
> problems.
>
> As you know, I have been insistent since the X9.62 approach was
> revealed that the PKIX WG provide one way to handle this issue, not
> one way for RSA and another way for ECC.  Since RFC 4055 has been
> implemented, I think that a compelling argument is needed to make a
> change.  So far, I have not seen one.  I look forward to a more
> complete description of the implementation concerns with the approach
> used in RFC 4055.
>
> Russ

---

From: "Kemp, David P." <[email-masked]>
Date: Tue, 16 Jan 2007 12:21:27 -0500

Stefan,

Thank you for a very detailed and useful reply.  It provides an excellent
framework for discussing the alternatives, particularly the mapping
between certificate alg ID, protocol alg ID, and crypto library
alg ID, and the potential locations where mapping can be performed.

Assume that cert path validation and crypto libraries are unaffected
by the choice of alternatives: crypto libraries always require the
caller to provide the crypto lib alg ID, and cert path libraries have
no reason to examine subject public key info in EE certs.

For ECDSA-signed cert paths, the cert path library must understand
ECDSA public key info in CA certs.  There are no modes associated with
ECDSA, so it's a wash whether the cert alg OID is a generic EC-public-key
OID or a single OID for ECDSA-public-key.  Extension non-criticality
is meaningless because the path validation library cannot ignore
unrecognized certificate signature keys.  The certificate signature
algorithm ID specifies RSA-with-hash or ECDSA-with-hash, so the same
hash-specific signature OIDs must be defined regardless of which
approach is taken for the public key OID.

Summary: for CA certs, the choice is between a single EC-public-key OID
and a single ECDSA-public-key OID.  An extension provides no advantage
for migration/legacy-interoperability, it just takes up space.

For EE certs, the apps and protocol stacks can use, as you say, an
algorithm ID mapping table with at worst 3 columns: cert ID, protocol
ID, and library ID.  Although you say an extension could provide
mapping aids, albeit complex, I don't believe this is practical at
all.  It is totally unreasonable for a certificate to contain, for
example, PKCS11 ID and cryptlib ID and crypto++ ID and MS CAPI ID
as well as manifest constants for other crypto libraries.

So assuming that the applications and protocol stacks are responsible
for containing mapping tables for OIDs contained in either
subjectPublicKeyInfo or in an extension, the only remaining issue
is combinatorial explosion.  First, how many combinations are
there?  The design team proposal only lists 3 Family OIDs:
ECDSA, ECDH, and ECMQV.  If you throw in modes, that adds
4 more: ECDH-Std, ECDH-Cofactor, ECMQV-Full, and ECMQV-1Pass.
My assumption is that no one would need mode-specific constraints
on certificate public keys, but even if PKIX decided to support
them, that only results in 8 OIDs total.

Second, unlike the flat TLS ciphersuite space and the
corresponding IANA number spaces for S/MIME, IPSec, etc, the
OID space is both hierarchical and unlimited.  It is both natural
and manageable to define a hierarchy of standardized OIDs for:

1 ECC
2   ECDSA
3   ECDH
4      ECDH-Std
5      ECDH-Cofactor
6   ECMQV
7      ECMQV-Full
8      ECMQV-1Pass
.      ECMQV-mode3 (new modes) ...
.   ECxyz (new families) ...

and experimental/private OIDs can be defined in other arcs without
either ambiguity or exhaustion of the OID space.  RFC 4055 specifies
a flat space for OIDs under PKCS-1 (with the highest assigned value
of 14), and it's reasonable to use a flat list for 4 (family) or
8 (family+mode) ECC public key OIDs.  But if a huge number of new
families or modes came up in the future, the OID space could
accommodate them easily.

> In summary,
>
> - The RFC 4055 approach is the simplest to define but is still
> hard to fully implement and we have to trust applications to get
> it right.

Agree that it is simplest to define.

>
> - The extension approach is the hardest to define but is friendlier
> to a gradual implementation and has the best prevention from
> applications getting it wrong.

Disagree that an extension can usefully provide library-specific
mapping constants, or that such information should be contained
in a certificate.

Disagree that a critical/non-critical extension aids gradual
implementation.  In every case where non-critical would be used,
applications gain no benefit from information in extension.  Cert
path module in updated apps might reject cert while path module
in legacy apps would ignore and accept cert, but what benefit is
that over having all apps accept 4055/3279 OID?  What motivation
is there for users to "upgrade" to a version that causes their
application to stop working?  In every case where critical
extension would be used, family OIDs in 4055 approach would give
same result.

Disagree that centralizing decision-making in cert path module
prevents applications from getting it wrong.  What if 1 family
(say ECMQV, or a new family) is supported by cert module but
not by crypto lib or protocol lib?

> - The structured algorithm OID is maybe not the hardest to define
> but the worse alternative in every other aspect.

Agree.

Dave

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Stefan Santesson
Sent: Monday, January 15, 2007 7:16 PM
To: Russ Housley; [email-masked]
Subject: RE: Straw poll for Algorithm Identifiers in Subject Public Key Info.

Russ,

                                   ------------
Apps                               |  E-mail  |
                                   ------------
                                        |

In summary,

Stefan Santesson
Senior Program Manager

---

From: Russ Housley <[email-masked]>
Date: Tue, 16 Jan 2007 14:04:08 -0500

Stefan:

Let's expand your "Crypto Library" box to include the
algorithms that are discussed in RFC 4055.

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

| Crypto Library|

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

|

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

|
|
|
|

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

| PKCS#1 v1.5 |  | PKCS#1 v1.5 |  | RSASSA-PSS |  |
RSAES-OAEP  |

| Signature   |  | Key Encrypt |  |
Signature  |  | Key Encrypt |

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

|
|
|
|

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

|

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

| RSA Math Routines |

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

In the RFC 4055 approach, the algorithm identifier says that the public
key may be used for any one of these RSA operations, or it names exactly
one of them.  If exactly one is named, it seems to help the crypto
library determine which of the routine to use.  If any is allowed,
then the application or the protocol stack needs to tell the crypto
library which operation to perform.

You say:

> Adding this feature in the RFC4055 style is not impossible but it
needs to be

> individually implemented in each cert using protocol and
application. This is

> not trivial considering that legacy is a big complicating factor.
In

> principle it worries me to put this complex mapping burden on
applications.

> Another threat with this approach is if it leads to a requirement to
define

> combinations of algorithm modes by single OIDs where we may end up
with a

> very large space of OIDs.

On your last point, RFC 4055 does not do any such thing.  It does
not define OIDs for OAEP with a particular hash algorithm as the mask
generation function.  No, it uses a parameter for that.

Certificate using applications need to map algorithm identifiers from
certificates, the protocol, and the crypto library.  Agreed.
It seems that the table approach that you describe will work well with
the simplified crypto library architecture that I have drawn above.
The one difference is that crypto libraries need to be able to handle the
fact that one public key might be useful in more than algorithm.
This is already the case.  RSA keys are used for PKCS#1 v1.5
signature and key encrypt.  If the key usage extension is not
present, then the certificate is not providing the context to select the
appropriate algorithm within the crypto library.

Russ

---

From: Stefan Santesson <[email-masked]>
Date: Tue, 16 Jan 2007 19:08:59 +0000

Thanks Dave,

Let me clarify where I think you missed my point.

I believe that it is less likely that a certificate with a critical extension will be falsely accepted and misused by an application. I believe the risk is greater that applications get it wrong and makes wrong use of a public key if the restriction comes as a public key OID.

But this is just an educated guess.

I agree that it will be hard to define complete mapping info in an extension. That was my point - It may make the extension overly complex.

Stefan Santesson
Senior Program Manager

> From: [email-masked] [mailto:owner-ietf-
> [email-masked]] On Behalf Of Kemp, David P.
> Sent: den 16 januari 2007 09:21
> To: [email-masked]
> From: [email-masked] [mailto:owner-ietf-
> [email-masked]] On Behalf Of Stefan Santesson
> For my rationales and reasoning I use the following simplified
> architectural model with some example modules.
>
>
>                                    ------------
> Apps                               |  E-mail  |
>                                    ------------
>                                         |
> The initiative to use a certificate and its key comes from either an
> application or a protocol stack. For TLS it will come from the protocol
> stack. For E-mail it may come from the application itself.
> The central problem with usage restrictions embedded with the subject
> public key OID is how to enforce it. When the application or the
> protocol stack wants to use a certificate it sends it to the validation
> module to verify and decode the certificate. The information returned
> contains the algorithm OID and the public key. The Crypto library in
> this example doesn't understand OIDs, so the app needs to do a
> translation to an internal AlgorithmID understood by the crypto
> library. In our environment the app/protocol can use a common OID table
> to do that. It also needs to map this usage to the algorithm usage
> negotiated in the protocol stack, e.g. map to a TLS cipher suite. So in
> worse case the app has 3 Algorithm IDs to map (Crypto library alg ID,
> Protocol alg ID and Cert alg ID).
>
> Even if the common OID table is used, the cert alg ID may differ from
> the Crypto library alg ID. For example the former may be and ID for
> ECC-DSA, while the latter may be ECC-DSA-SHA256.
>
> Adding this feature in the RFC4055 style is not impossible but it needs
> to be individually implemented in each cert using protocol and
> application. This is not trivial considering that legacy is a big
> complicating factor. In principle it worries me to put this complex
> mapping burden on applications. Another threat with this approach is if
> it leads to a requirement to define combinations of algorithm modes by
> single OIDs where we may end up with a very large space of OIDs.
>
> Looking at this from an extension approach, we would have the option of
> critical/non critical. If the extension is critical, the cert
> validation module will return an unrecognized critical extension error,
> forcing the application to assume responsibility for honoring this
> extension or fail. This is a better guarantee for preventing misuse by
> applications. The extension could potentially contain mapping data that
> is more suitable for mapping usage towards the different alg IDs
> provided in different protocols. However this may cause the extension
> syntax to be overly complex.
>
> The worse scenario of all the choices is the structured Certificates
> OID (á la X9.62), listing sub OIDs for acceptable algorithmic modes.
> This would create the most complex and confusing mapping graph for the
> applications and protocol stacks as it now has a magnitude of OIDs to
> map to algorithm IDs of the crypto library as well as Alg IDs from the
> protocol. As such it is the least favorable alternative.
>
> In summary,
>
> - The RFC 4055 approach is the simplest to define but is still hard to
> fully implement and we have to trust applications to get it right.
>
> - The extension approach is the hardest to define but is friendlier to
> a gradual implementation and has the best prevention from applications
> getting it wrong.
>
> - The structured algorithm OID is maybe not the hardest to define but
> the worse alternative in every other aspect.
>
> My primary choice would be to not enforce algorithmic modes in
> certificates at all unless there is a cryptographic weakness in the
> algorithm to protect. As such the protocol usage negotiation should be
> solved on the protocol level. Then we only need 1 OID for ECC keys
> (defined in RFC 3279). The RFC 4055 OIDs would still exist for the
> legitimate reasons above, but we would not need any new OIDs for ECC.
>
> If the WG decides that mode restriction for ECC keys is necessary then
> we need to choose the least evil alternative and I currently feel
> unsure of what that would be.
>
>
> Stefan Santesson
> Senior Program Manager

---

From: Stefan Santesson <[email-masked]>
Date: Tue, 16 Jan 2007 20:12:44 +0000

Russ,
I can't see that we have any disagreements.

My point is that the mapping and as such the responsibility for doing the mapping correctly rests fully on the applications or protocol stacks.
You can't just add this feature in the crypto library or the validation module, and use current protocol stacks and applications. If you do that, they most likely either fail or get it wrong.

So we have a situation with multiple possible points of failure.

An expansion of the public key OIDs for ECC will in short require the following changes:

1) Update chain validation to recognize new OIDs and enforce them in chain validation
2) Update the OID table (voluntarily used by protocols and applications)
3) Update the mapping logic in all protocol stacks and cert using applications

The interesting question is what will happen if you do 1) and 2) but not 3). Or do 1) and 2) and gradually update 3)
Keeping in mind that many applications are designed out of the notion that a public key obtained through a validated certificate path, associated with a matching key usage and EKU, either works (then it is a good one) or don't work, I wouldn't be surprised if an application receiving a new Alg ID that it can't map to the protocol Alg ID, still will try to use the key it has to see if it works. Neither the chain validation engine nor the Crypto library will catch or prevent this abuse.

Of course, a correct application will get it right, but many developers have learned to make their code as fault tolerant as possible and are used to process cases of conflicting information in a way that succeeds when it should be "safe" to do so. Example: a chain should fail if Issuer name and subject name matching fails. But still, if signature of the leaf cert matches the public key of the CA cert and subject/issuer name are "Example Inc"/"example, inc" in different encoding. It would be safe to allow it to pass. Strictly such chain should fail, but you will find that "fault tolerant" designs, knowing that users will get things wrong, may actually pass such chain, because it is safe to do so.

In the "old" logic, when a subject public key OID had no constraining semantics. It would be safe to use a trusted key if it works (if all other checks are good). This change of semantics is the danger when it hits old applications not designed for it. If they were designed to honor RFC 4055 OIDs, this would not be an issue. However RFC 4055 has not been implemented in many places.

The difference with an extension is that the application will get a critical extension error, which applications currently are designed to honor. They either need to recognize and honor that extension or fail. The risk for abuse during transition is thus considerably lower.

What ever we do, I hope we can do it as simple as possible. But even though defining a few new alg OIDs seems simple, it may not provide for a safe and simple transition.

Stefan Santesson
Senior Program Manager

From: Russ Housley [mailto:[email-masked]]
Sent: den 16 januari 2007 11:04
To: Stefan Santesson; [email-masked]
Subject: RE: Straw poll for Algorithm Identifiers in Subject Public Key Info.

Stefan:

Let's expand your "Crypto Library" box to include the algorithms that are discussed in RFC 4055.

                       -----------------
                       | Crypto Library|
                       -----------------
                               |
       ----------------------------------------------------
       |                |                |                |
 ---------------  ---------------  --------------  ---------------
 | PKCS#1 v1.5 |  | PKCS#1 v1.5 |  | RSASSA-PSS |  | RSAES-OAEP  |
 | Signature   |  | Key Encrypt |  | Signature  |  | Key Encrypt |
 ---------------  ---------------  --------------  ---------------
       |                |                |                |
       ----------------------------------------------------
                               |
                     ---------------------
                     | RSA Math Routines |
                     ---------------------

In the RFC 4055 approach, the algorithm identifier says that the public key may be used for any one of these RSA operations, or it names exactly one of them.  If exactly one is named, it seems to help the crypto library determine which of the routine to use.  If any is allowed, then the application or the protocol stack needs to tell the crypto library which operation to perform.

You say:
> Adding this feature in the RFC4055 style is not impossible but it needs to be
> individually implemented in each cert using protocol and application. This is
> not trivial considering that legacy is a big complicating factor. In
> principle it worries me to put this complex mapping burden on applications.
> Another threat with this approach is if it leads to a requirement to define
> combinations of algorithm modes by single OIDs where we may end up with a

On your last point, RFC 4055 does not do any such thing.  It does not define OIDs for OAEP with a particular hash algorithm as the mask generation function.  No, it uses a parameter for that.

Certificate using applications need to map algorithm identifiers from certificates, the protocol, and the crypto library.  Agreed.  It seems that the table approach that you describe will work well with the simplified crypto library architecture that I have drawn above.  The one difference is that crypto libraries need to be able to handle the fact that one public key might be useful in more than algorithm.  This is already the case.  RSA keys are used for PKCS#1 v1.5 signature and key encrypt.  If the key usage extension is not present, then the certificate is not providing the context to select the appropriate algorithm within the crypto library.

Russ

---

From: Daniel Brown <[email-masked]>
Date: Tue, 16 Jan 2007 16:03:10 -0500

> > but the worse alternative in every other aspect.

Suppose that a subject has an ECMQV-only cert, and wishes to allow either 
SHA-256 or SHA-384 based KDFs, but no other KDFs.  Also, the EKU field 
says that the cert can be used for SMIME, IPSec, SSH, or TLS (suppose the 
private key is on the user's smart card).  The X9.62 "structured" approach 
allows for this.  How would the other approaches allow for this?

Regards,

Dan Brown
(905) 501-3857
http://www.certicom.com

---

From: Russ Housley <[email-masked]>
Date: Tue, 16 Jan 2007 16:54:15 -0500

Stefan:

If a certificate says that the public key is only to be used with
RSAES-OAEP, then it should fail if it trys to use it with some other
algorithm.  In the three steps that you cite, this has no impact on
1).  It is not a signature algorithm, so it should no have any
impact on the certification path validation.  Updating the OID table
seems very straightforward.  Something like this needs to be done
anytime a new algorithm is added to the system.  It will need to be
added to the table to handle the appearance in S/MIME for example.
Finally, the pain involved with 3) is the leverage to get application
developers to use the OID table.  There may be some
application-specific things that need to be done as well, but that does
not necessarily have anything to do with the certificate.

I disagree with one thing you said.  You said:

> In the “old” logic, when a subject public key OID had no
constraining semantics.

> It would be safe to use a trusted key if it works (if all other
checks are good). This

> change of semantics is the danger when it hits old applications not
designed for

> it. If they were designed to honor RFC 4055 OIDs, this would not be
an issue.

> However RFC 4055 has not been implemented in many places.

The subject public key information has always included an algorithm
identifier.  The table of contents of RFC 3279 shows the ones that
have been in use for at least four years:

2.3  Subject Public Key Algorithms

2.3.1  RSA Keys

2.3.2  DSA Signature Keys

2.3.3  Diffie-Hellman Key Exchange Keys

2.3.4  KEA Public Keys

2.3.5  ECDSA and ECDH Public Keys

DSA and KEA public keys can also be used in DH operations from a purely
mathematical perspective.  However, we choose to assign three
different OIDs.  We did not assign one OID for discrete log public
keys.

Russ

At 03:12 PM 1/16/2007, Stefan Santesson wrote:

Russ,

I can’t see that we have any disagreements.

My point is that the mapping and as such the responsibility for doing the
mapping correctly rests fully on the applications or protocol
stacks.

You can’t just add this feature in the crypto library or the validation
module, and use current protocol stacks and applications. If you do that,
they most likely either fail or get it wrong.

An expansion of the public key OIDs for ECC will in short require the
following changes:

1) Update chain validation to recognize new OIDs and enforce them in
chain validation

2) Update the OID table (voluntarily used by protocols and
applications)

3) Update the mapping logic in all protocol stacks and cert using
applications

The interesting question is what will happen if you do 1) and 2) but not
3). Or do 1) and 2) and gradually update 3)

Keeping in mind that many applications are designed out of the notion
that a public key obtained through a validated certificate path,
associated with a matching key usage and EKU, either works (then it is a
good one) or don’t work, I wouldn’t be surprised if an application
receiving a new Alg ID that it can’t map to the protocol Alg ID, still
will try to use the key it has to see if it works. Neither the chain
validation engine nor the Crypto library will catch or prevent this
abuse.

Of course, a correct application will get it right, but many developers
have learned to make their code as fault tolerant as possible and are
used to process cases of conflicting information in a way that succeeds
when it should be “safe” to do so. Example: a chain should fail if Issuer
name and subject name matching fails. But still, if signature of the leaf
cert matches the public key of the CA cert and subject/issuer name are
“Example Inc”/”example, inc” in different encoding. It would be safe to
allow it to pass. Strictly such chain should fail, but you will find that
“fault tolerant” designs, knowing that users will get things wrong, may
actually pass such chain, because it is safe to do so.

In the “old” logic, when a subject public key OID had no constraining
semantics. It would be safe to use a trusted key if it works (if all
other checks are good). This change of semantics is the danger when it
hits old applications not designed for it. If they were designed to honor
RFC 4055 OIDs, this would not be an issue. However RFC 4055 has not been
implemented in many places.

The difference with an extension is that the application will get a
critical extension error, which applications currently are designed to
honor. They either need to recognize and honor that extension or fail.
The risk for abuse during transition is thus considerably lower.

What ever we do, I hope we can do it as simple as possible. But even
though defining a few new alg OIDs seems simple, it may not provide for a
safe and simple transition.

Stefan Santesson

Senior Program Manager

From: Russ Housley
[
mailto:[email-masked]]

Subject: RE: Straw poll for Algorithm Identifiers in Subject
Public Key Info.

Stefan:

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

| Crypto Library|

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

|

|
|
|
|

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

| PKCS#1 v1.5 |  | PKCS#1 v1.5 |  | RSASSA-PSS
|  | RSAES-OAEP  |

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

|
|
|
|

|

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

| RSA Math Routines |

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

In the RFC 4055 approach, the algorithm identifier says that the
public key may be used for any one of these RSA operations, or it names
exactly one of them.  If exactly one is named, it seems to help the
crypto library determine which of the routine to use.  If any is
allowed, then the application or the protocol stack needs to tell the
crypto library which operation to perform.

application. This is

applications.

> very large space of OIDs.

On your last point, RFC 4055 does not do any such thing.  It
does not define OIDs for OAEP with a particular hash algorithm as the
mask generation function.  No, it uses a parameter for
that.

Russ

---

From: Stefan Santesson <[email-masked]>
Date: Tue, 16 Jan 2007 22:30:21 +0000

The fact that you can put the info into a cert does not mean that the whole system will do what you want.

We are dealing with a field that historically has not been used to carry such information and where it will be a challenge make sure they will act in a "good" manner if they do. The situation is different for private key operations protected by a smart card than using the public key from a certificate. Both sides need to honor the restriction.

Stefan Santesson
Senior Program Manager

From: [email-masked] [mailto:[email-masked]] On Behalf Of Daniel Brown
Sent: den 16 januari 2007 13:03
To: Kemp, David P.
Cc: [email-masked]
Subject: RE: Straw poll for Algorithm Identifiers in Subject Public Key Info.

> > but the worse alternative in every other aspect.

Suppose that a subject has an ECMQV-only cert, and wishes to allow either SHA-256 or SHA-384 based KDFs, but no other KDFs.  Also, the EKU field says that the cert can be used for SMIME, IPSec, SSH, or TLS (suppose the private key is on the user's smart card).  The X9.62 "structured" approach allows for this.  How would the other approaches allow for this?

Regards,

Dan Brown
(905) 501-3857
http://www.certicom.com

---

From: "Kemp, David P." <[email-masked]>
Date: Tue, 16 Jan 2007 18:07:48 -0500

Is KDF an appropriate level of granularity for certificate-based
constraints on the usage of public keys?  And if so, is it
cryptographically appropriate to use a single public key size
with both SHA-256 and SHA-384 KDFs?  

Specifying a list of allowed features does not satisfy the design
team's goal of using certificates to reduce protocol negotiation -
if more than one KDF is possible with a pair of peer certificates,
it is still necessary to negotiate which KDF to use.

But to answer the question, the design team slides stated:

* Define an optionally critical certificate extension
   - Sequence of Algorithm Identifiers, as in X9.62 parameters
   - Reuse X9 algorithm Identifiers
       . Deprecating "with recommended"? 
   - Add three "family" OIDs (ECDSA, ECDH, ECMQV)

So the extension approach allows a list of KDFs, but the RFC 4055
approach does not.  I believe that a list is unnecessary because
an ECMQV public key of a given size should imply the acceptable
KDF size (or conversely, a key derive function should imply the
acceptable public key size).

Dave

________________________________________
From: Daniel Brown [mailto:[email-masked]] 
Sent: Tuesday, January 16, 2007 4:03 PM
To: Kemp, David P.
Cc: [email-masked]
Subject: RE: Straw poll for Algorithm Identifiers in Subject Public Key Info.

Regards, 

Dan Brown
(905) 501-3857
http://www.certicom.com

---

From: Stefan Santesson <[email-masked]>
Date: Tue, 16 Jan 2007 23:22:39 +0000

There is no single way that applications and protocol stacks may operate.

In my example, applications don't understand any public key OID. They would simply consult OID table to get a translation into something they can pass to the crypto lib. If that look-up is unsuccessful, the application will most certainly fail. But if it is successful, the application will attempt to map that key to the usage negotiated in the protocol, e.g. a TLS cipher suite. This is where I'm not at all sure that "old" applications will get it right. I have indications that they might get it wrong but I don't have any hard facts to offer yet. It worries me though to have to depend on various applications to get it right.

I would prefer to have more control in the library layer and more actively prevent applications from doing the wrong thing.

Stefan Santesson
Senior Program Manager

> From: Kemp, David P. [mailto:[email-masked]]
> Sent: den 16 januari 2007 15:08
> Hmmm, I'd guess that applications would fail, either gracefully
> or catastrophically, when faced with an unrecognized Subject
> Public Key Info OID.   I did miss the point that they might
> falsely accept and misuse the public key, but even after considering
> the possibility it still seems highly improbable.
>
> Dave
>
> From: Stefan Santesson [mailto:[email-masked]]
> Sent: Tuesday, January 16, 2007 2:09 PM
> To: Kemp, David P.; [email-masked]
> I believe that it is less likely that a certificate with a critical
> extension will be falsely accepted and misused by an application. I
> believe the risk is greater that applications get it wrong and makes
> wrong use of a public key if the restriction comes as a public key OID.
>
> I agree that it will be hard to define complete mapping info in an
> extension. That was my point - It may make the extension overly
> complex.
>
>
> Stefan Santesson
> Senior Program Manager

---

From: Stefan Santesson <[email-masked]>
Date: Tue, 16 Jan 2007 22:25:08 +0000

You are correct in all you say, but that does not prevent applications from getting it wrong. They can treat RSA and ECC keys differently than DH/DSA where a distinction is known to them.
I'm venting my fear of what might be a problem. I will look further into this.

Stefan Santesson
Senior Program Manager

From: Russ Housley [mailto:[email-masked]]
Sent: den 16 januari 2007 13:54
To: Stefan Santesson; [email-masked]
Subject: RE: Straw poll for Algorithm Identifiers in Subject Public Key Info.

Stefan:

If a certificate says that the public key is only to be used with RSAES-OAEP, then it should fail if it trys to use it with some other algorithm.  In the three steps that you cite, this has no impact on 1).  It is not a signature algorithm, so it should no have any impact on the certification path validation.  Updating the OID table seems very straightforward.  Something like this needs to be done anytime a new algorithm is added to the system.  It will need to be added to the table to handle the appearance in S/MIME for example.  Finally, the pain involved with 3) is the leverage to get application developers to use the OID table.  There may be some application-specific things that need to be done as well, but that does not necessarily have anything to do with the certificate.

I disagree with one thing you said.  You said:
> In the "old" logic, when a subject public key OID had no constraining semantics.
> It would be safe to use a trusted key if it works (if all other checks are good). This
> change of semantics is the danger when it hits old applications not designed for
> it. If they were designed to honor RFC 4055 OIDs, this would not be an issue.

The subject public key information has always included an algorithm identifier.  The table of contents of RFC 3279 shows the ones that have been in use for at least four years:

DSA and KEA public keys can also be used in DH operations from a purely mathematical perspective.  However, we choose to assign three different OIDs.  We did not assign one OID for discrete log public keys.

Russ

Russ,

Stefan Santesson
Senior Program Manager

From: Russ Housley [ mailto:[email-masked]]
Sent: den 16 januari 2007 11:04
To: Stefan Santesson; [email-masked]
Subject: RE: Straw poll for Algorithm Identifiers in Subject Public Key Info.

Stefan:

                       -----------------
                       | Crypto Library|
                       -----------------
                               |

Russ

---

From: "Kemp, David P." <[email-masked]>
Date: Tue, 16 Jan 2007 18:08:28 -0500

Dave

-----Original Message-----
From: Stefan Santesson [mailto:[email-masked]] 
Sent: Tuesday, January 16, 2007 2:09 PM
To: Kemp, David P.; [email-masked]
Subject: RE: Straw poll for Algorithm Identifiers in Subject Public Key
Info.

Thanks Dave,

I agree that it will be hard to define complete mapping info in an
extension. That was my point - It may make the extension overly complex.

Stefan Santesson
Senior Program Manager

---

From: Daniel Brown <[email-masked]>
Date: Wed, 17 Jan 2007 11:30:29 -0500

David Kemp wrote on 01/16/2007 06:07:48 PM:
 
> constraints on the usage of public keys? 

Well, only to those who strive for strict compliance to SP 800-56A, in the 
face of application protocols allowing noncompliant KDFs.

> And if so, is it

Many in IETF have argued that a SHA-1 based KDF (such as the TLS's or 
IPSec's) provides 160 bits of security, so it is acceptable for use with 
128-bit security, i.e. 256 bit ECC keys.  By the same argument, a SHA-256 
based KDF ought to be acceptable for an 384-bit ECC key. 

> it is still necessary to negotiate which KDF to use.

Doesn't it reduce negotiation?  Alice and Bob can state their crypto 
abilities using certs.  Then one of them chooses an algorithm in the 
intersection of the abilities, and tells the other that he/she's used it. 
The certs have saved the protocol from sending at least some "crypto 
capabilities" message flows.

>    - Sequence of Algorithm Identifiers, as in X9.62 parameters

Yes, that does it.

> acceptable public key size).

I'm a little confused now.  While we're deprecating "with recommended" 
syntax, we're introducing a "family" syntax, where the crypto parameters 
(KDFs, etc.) are implicitly "recommended" by association with key size. 
This seems a paradoxical to me.  They're are some distinctions: the 
"family" OIDs are meant for a cert, whereas the "with recommended" OIDs 
are being deprecated at both the cert and application level; also, some 
people would construe the "family" OIDs to mean "any" acceptable crypto 
parameters are okay, not that some parameters are "recommended"; but 
neither point completely resolves my confusion.  I will go back to the 
design team slides to see if it clarifies things for me, but I thought I'd 
raise this now, just in case it helps anybody else.

Best regards,

Dan Brown
(905) 501-3857
http://www.certicom.com

Info.
> Suppose that a subject has an ECMQV-only cert, and wishes to allow 
> either SHA-256 or SHA-384 based KDFs, but no other KDFs.  Also, the 
> EKU field says that the cert can be used for SMIME, IPSec, SSH, or 
> TLS (suppose the private key is on the user's smart card).  The X9.
> 62 "structured" approach allows for this.  How would the other 
> approaches allow for this? 
>

---

From: Russ Housley <[email-masked]>
Date: Wed, 17 Jan 2007 14:57:40 -0500

> constraints on the usage of public keys?

Well, only to those who
strive for strict compliance to SP 800-56A, in the face of application
protocols allowing noncompliant KDFs.

I do not think that it is the role of the certificate to
"enforce" compliance.  Rather, the application needs to be
run in "FIPS mode" so that all of the choices necessary to
conform to NIST guidance are made.

> with both SHA-256 and SHA-384 KDFs?

Many in IETF have argued
that a SHA-1 based KDF (such as the TLS's or IPSec's) provides 160 bits
of security, so it is acceptable for use with 128-bit security, i.e. 256
bit ECC keys.  By the same argument, a SHA-256 based KDF ought to be
acceptable for an 384-bit ECC key.

So?  What does this have to do with the best way to represent the
algorithm constraints in the certificate?

> Specifying a list of
allowed features does not satisfy the design

> it is still necessary to negotiate which KDF to use.

Doesn't it reduce
negotiation?  Alice and Bob can state their crypto abilities using
certs.  Then one of them chooses an algorithm in the intersection of
the abilities, and tells the other that he/she's used it.  The certs
have saved the protocol from sending at least some "crypto
capabilities" message flows.

The closest thing that we have for something like this is
SMIMECapabilities.  In this case, the store-and-forward nature of
email makes this a reasonable thing to do.  If real-time
negotiations are possible in the protocol, then keeping the CA out of the
picture is desirable.

>    - Sequence of Algorithm Identifiers, as in X9.62
parameters

Yes, that does
it.

I'm a little confused
now.  While we're deprecating "with recommended" syntax,
we're introducing a "family" syntax, where the crypto
parameters (KDFs, etc.) are implicitly "recommended" by
association with key size.  This seems a paradoxical to me.
They're are some distinctions: the "family" OIDs are meant for
a cert, whereas the "with recommended" OIDs are being
deprecated at both the cert and application level; also, some people
would construe the "family" OIDs to mean "any"
acceptable crypto parameters are okay, not that some parameters are
"recommended"; but neither point completely resolves my
confusion.  I will go back to the design team slides to see if it
clarifies things for me, but I thought I'd raise this now, just in case
it helps anybody else.

I interpreted the design team output to say that the family OIDs would
specify ECDSA, ECDH, and ECMQV without saying anything about the KDF at
all.

Russ

---

From: Daniel Brown <[email-masked]>
Date: Wed, 17 Jan 2007 16:20:27 -0500

Russ Housley <[email-masked]> wrote on 01/17/2007 02:57:40 PM:

[> Dan Brown wrote on 01/17/2007 11:30 AM:] 
[>> David Kemp wrote on 01/16/2007 06:07:48 PM:]

>> Well, only to those who strive for strict compliance to SP 800-56A, 
>> in the face of application protocols allowing noncompliant KDFs. 
> 
> I do not think that it is the role of the certificate to "enforce" 
> compliance.  Rather, the application needs to be run in "FIPS mode" 
> so that all of the choices necessary to conform to NIST guidance are 
made.

Yes, Alice can run in FIPS mode, but she may also like to tell Bob to 
please only secure email to her using FIPS mode.  Well, perhaps, nobody 
else but me really cares?

Back to the original question: 4055 optionally allows the cert to specify 
the MGF in OAEP.  So why not be able to specify the KDF for ECMQV/ECDH in 
a cert?  I see these as analogous.

>> Many in IETF have argued that a SHA-1 based KDF (such as the TLS's 
>> or IPSec's) provides 160 bits of security, so it is acceptable for 
>> use with 128-bit security, i.e. 256 bit ECC keys.  By the same 
>> argument, a SHA-256 based KDF ought to be acceptable for an 384-bit ECC 
key.
> algorithm constraints in the certificate?

Nothing: I was only addressing David's specific question of whether it's 
"cryptographically appropriate" to used mixed sizes.

>> intersection of the abilities, and tells the other that he/she's 
>> used it.  The certs have saved the protocol from sending at least 
>> some "crypto capabilities" message flows. 
> 
> negotiations are possible in the protocol, then keeping the CA out 
> of the picture is desirable.

What extra involvement of the CA is there, when the KDF (or MGF for OAEP) 
is specified in the cert?

>> I'm a little confused now.  While we're deprecating "with 
>> recommended" syntax, we're introducing a "family" syntax, where the 
>> crypto parameters (KDFs, etc.) are implicitly "recommended" by 
>> association with key size.  This seems a paradoxical to me.  They're
>> are some distinctions: the "family" OIDs are meant for a cert, 
>> whereas the "with recommended" OIDs are being deprecated at both the
>> cert and application level; also, some people would construe the 
>> "family" OIDs to mean "any" acceptable crypto parameters are okay, 
>> not that some parameters are "recommended"; but neither point 
>> completely resolves my confusion.  I will go back to the design team
>> slides to see if it clarifies things for me, but I thought I'd raise
>> this now, just in case it helps anybody else.
> 
> I interpreted the design team output to say that the family OIDs 
> would specify ECDSA, ECDH, and ECMQV without saying anything about 
> the KDF at all.

So, with family OIDs, the protocol would determine/negotiate the KDF. That 
should be fine with David's preference of implied acceptable KDF size, 
provided the protocol specifiers adhere to it.

I like this open functionality of family OIDs.  But I think there should 
be an option to make them specific, less open-ended, as is available in 
4055, the design team proposal, and the X9.62 syntax.  In retrospect, 
family-like OIDs could have easily been added to the X9.62 syntax, simply 
by making the parameters field optional, then defining their absence to 
mean that any (legal) parameter is allowed.  (E.g. ecdsa-with-Specified, 
omitting the hash parameter.)

If we don't like lists, then PKIX can limit the list length to 1, and 
still comply the X9.62 syntax.  If we need family OIDs, then only a small 
tweak of X9.62 syntax is needed (as described above).

On the other hand, I like the gradual migration possibilities of a 
critical/noncritical extensions.  Critical extensions are functionally 
like 4055/X9.62, so the noncritical is the added value.  If the relying 
party is understands the noncritical extensions, is he/she required to 
comply with them?

Regards,

Dan Brown
(905) 501-3857
http://www.certicom.com

---

From: Russ Housley <[email-masked]>
Date: Wed, 17 Jan 2007 16:45:26 -0500

Dan:

>> > Is KDF an
appropriate level of granularity for certificate-based

> I do not think that it is the role of the certificate to
"enforce"

made.

Yes, Alice can run in FIPS
mode, but she may also like to tell Bob to please only secure email to
her using FIPS mode.  Well, perhaps, nobody else but me really
cares?

I care.  However, I do not see the certificate as the enforcement
tool.  In the case of S/MIME, the SMIMECapabilities extension is
used.  It tell the message originator the capabilities of the
recipient.  If the recipient only offers "FIPS mode"
algorithms, then those are the only ones that will be used by the message
originator.  In the case of TLS and other protocols where real-time
negotiation happens, either of the parties can ensure that "FIPS
mode" algorithms are used, as long as both parties actually support
them.

Back to the original question:
4055 optionally allows the cert to specify the MGF in OAEP.  So why
not be able to specify the KDF for ECMQV/ECDH in a cert?  I see
these as analogous.

RFC 4055 allows the parameters to be absent when used in the certificate
subject public key information.  If they are present, then the MGF,
for example, is carried there.

I would be happy with a similar arrangement for elliptic curve
algorithms.  That is, we must have the same flexibility to omit the
ECDH/ECMQV KDF.

>> > And if so, is
it

>> argument, a SHA-256 based KDF ought to be acceptable for an
384-bit ECC key.

> algorithm constraints in the certificate?

Nothing: I was only
addressing David's specific question of whether it's
"cryptographically appropriate" to used mixed
sizes.

>> > Specifying a
list of allowed features does not satisfy the design

> of the picture is desirable.

What extra involvement of
the CA is there, when the KDF (or MGF for OAEP) is specified in the
cert?

The CA is the one that is signing the certificate.  A CA should not
sign stuff that it does not understand, so it is involved in the
ECDH/ECMQV KDF selection or the OAEP MGF selection if it is included in
the certificate.

> the KDF at all.

So, with family OIDs, the
protocol would determine/negotiate the KDF.  That should be fine
with David's preference of implied acceptable KDF size, provided the
protocol specifiers adhere to it.

I like this open
functionality of family OIDs.  But I think there should be an option
to make them specific, less open-ended, as is available in 4055, the
design team proposal, and the X9.62 syntax.  In retrospect,
family-like OIDs could have easily been added to the X9.62 syntax, simply
by making the parameters field optional, then defining their absence to
mean that any (legal) parameter is allowed.  (E.g.
ecdsa-with-Specified, omitting the hash parameter.)

As said above, I'm okay with that as long as it is possible to omit the
algorithm identifier parameters (as is allowed in RFC 4055) in a
certificate subject public key.  Obviously, there are places where
the same OID will be used where the parameters are required to be present
(as is also the case in RFC 4055).

If we don't like lists, then
PKIX can limit the list length to 1, and still comply the X9.62
syntax.  If we need family OIDs, then only a small tweak of X9.62
syntax is needed (as described above).

At the risk of repeating myself too much, I am not happy if the
parameters to select the KDF are required.  I have no problem with
one being present.

On the other hand, I like the
gradual migration possibilities of a critical/noncritical
extensions.  Critical extensions are functionally like 4055/X9.62,
so the noncritical is the added value.  If the relying party is
understands the noncritical extensions, is he/she required to comply with
them?

Yes.

Russ

---

From: "Kemp, David P." <[email-masked]>
Date: Wed, 17 Jan 2007 17:39:44 -0500

> Well, only to those who strive for strict compliance to SP 800-56A, in the > face of application protocols allowing noncompliant KDFs. 

An application can comply with SP 800-56A recommendations, protocol
specifications, both, or neither.  This is independent of certificate
contents.  In fact, an SP 800-56 compliant application must refuse
to honor a non-compliant KDF specification contained in a certificate
either by refusing to derive a key using that cert or by substituting
a compliant KDF to use with the cert's public key.  (The latter
is admittedly shady behavior, but it is possible.)

> based KDF ought to be acceptable for an 384-bit ECC key.

Strict compliance with SP 800-56A says not.  The minimum bit length of the hash function for 384-511 bit ECC key is 384.  A SHA-256 based KDF is, however, acceptable for a 383 bit ECC key :-).

I'm not sure why SP 800-56A doesn't specify a maximum hash size.  Using
SHA-384 with a 160 bit ECC key would seem to provide less than the
implied amount of entropy for the derived key.

> capabilities" message flows.

That assumes that cert exchange occurs before algorithm negotiation,
which is not the case for RFC 4306 - the first cert request is
contained in the same message as algorithm acceptance.  Even if certs
were sent in the first two messages, they wouldn't reduce the
number of messages, and if multiple certs (e.g. RSA and ECC)
were sent before algorithm negotiation was done, the size of
the messages would go way up, not slightly down.

> This seems a paradoxical to me.

Good question.  I'd guess that the family OID means to use configured
or negotiated parameters if available, with recommended parameters as
a default if the application has no other guidance.  A
KDF-specific OID (including "with recommended" if it weren't
deprecated) means mandatory use of the specified parameters.  An
RFC would need to unambiguously specify the semantics of family OIDs.

Regards,
Dave

---

From: Stefan Santesson <[email-masked]>
Date: Tue, 16 Jan 2007 23:22:39 +0000

Stefan Santesson
Senior Program Manager

---

From: Stefan Santesson <[email-masked]>
Date: Tue, 16 Jan 2007 23:22:39 +0000

Stefan Santesson
Senior Program Manager