591640 - CKM_ECDH1_DERIVE and CKM_ECDH1_COFACTOR_DERIVE ignore non-empty shared data

Status: RESOLVED FIXED

(NSS :: Libraries, defect)

Description

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

When the KDF is not CKD_NULL, then the code allows non-empty shared data. But, it never actually processes it. The PKCS#11 specification isn't clear what to do, and I don't have the IEEE/ANSI specifications, but it doesn't make sense to allow the ignore the parameter when it's there.

Comment 1

[David Cooper]

If this is referring to the code for CKM_ECDH1_DERIVE and CKM_ECDH1_COFACTOR_DERIVE in NSC_DeriveKey in mozilla/security/nss/lib/softoken/pkcs11c.c, then I also believe there is a problem with the CKD_SHA1_KDF.

I have have access to ANSI X9.63 either, but RFC 5753 refers to the KDF in Section 3.6.1 of [SEC1]: "Standards for Efficient Cryptography Group, "SEC 1: Elliptic Curve Cryptography", version 2.0, May 2009, available from www.secg.org.

Section 3.6.1 of [SEC1], ANSI X9.63 Key Derivation Function, supposedly specifies the KDF from ANSI X9.63.

In NSC_DeriveKey, the CKD_SHA1_KDF seems to be implemented as simply the SHA-1 hash of the shared secret that is derived using ECDH_Derive.  However, Section 3.6.1 of [SEC1], the secret key is computed as Hash(Z||Counter||[SharedInfo]), where Counter is a 32-bit counter.  If the key that needs to be created from the KDF is longer than the output of the hash function then Hash is computed multiple times with the Counter being incremented each time.

While I see that PKCS #11 v2.3 is still in draft form, it would be nice to see CKD_SHA256_KDF, CKD_SHA384_KDF, and CKD_SHA512_KDF implemented as well at the same time that the implementation of CKD_SHA1_KDF is revisited.  I also think it would be helpful if the KDF were written as a separate function, so that it could be used by other parts of NSS.

Comment 2

[David Cooper]

Attachment: Implemention of CKD_SHAxxx_KDF

As I noted in Comment 1, PKCS #11 states:

     CKD_SHA1_KDF, which is based on SHA-1, derives keying data
     from the shared secret value as defined in ANSI X9.63.

This patch implements the ANSI X9.63 KDF as described in Section 3.6.1 of "SEC1: Elliptic Curve Cryptography", version 2.0, which is available at http://www.secg.org.

I implemented this KDF as part of an effort to add the ability to NSS to encrypt and decrypt S/MIME messages using ECDH, and using this patch I have been able to successfully exchange ECDH encrypted messages with Microsoft Outlook 2010, so I am fairly confident that I have implemented the KDF correctly.

In addition to CKD_SHA1_KDF, this patch also implements CKD_SHA224_KDF, CKD_SHA256_KDF, CKD_SHA384_KDF, and CKD_SHA512_KDF from the draft of PKCS #11 v2.30 that is currently on the www.rsa.com web site. I added these since RFC 5753, Use of Elliptic Curve Cryptography (ECC) Algorithms in Cryptographic Message Syntax (CMS), states that implementations MUST support the SHA-256 KDF and RFC 6318, Suite B in Secure/Multipurpose Internet Mail Extensions (S/MIME), requires the use of the SHA-384 KDF in conjunction with ECDH with P-384 keys.

Finally, I created a new key derivation mechanism, CKM_NSS_ANSI_X9_63_KDF, that just performs the KDF, since some smart cards can only perform the ECDH primitive.  So, when implementing ECDH with such smart cards it is necessary to perform the ECDH primitive on the card, move the resulting shared secret into software PKCS #11 module, and then perform the KDF to derive the secret key.  The way I support such smart cards in my implementation is to call C_DeriveKey with the CKD_NULL KDF, use pk11_ForceSlot to move the shared secret to the software cryptographic module, and then call C_DeriveKey again specifying CKM_NSS_ANSI_X9_63_KDF as mechanism.

Comment 3

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

The new mechanism you propose should be split into multiple mechanisms like was done for CKM_NSS_HKDF_*. This is ugly, but it is useful because it allows the calling application to easily query the module about what hash functions it supports for the CKM_NSS_ANSI_X9_63_KDF mechanism. For example, a module might not support SHA-1 but might support SHA-256.

Comment 4

[David Cooper]

(In reply to comment #3)
> The new mechanism you propose should be split into multiple mechanisms like
> was done for CKM_NSS_HKDF_*. This is ugly, but it is useful because it
> allows the calling application to easily query the module about what hash
> functions it supports for the CKM_NSS_ANSI_X9_63_KDF mechanism. For example,
> a module might not support SHA-1 but might support SHA-256.

I'd be glad to re-write the code to define five different mechanisms, one for each hash function, rather than a single mechanism that takes the hash function as a parameter.  Defining one mechanism just seemed more efficient, and I didn't think there was a question of which hash functions a module supported since I thought that all of the CKM_NSS_* mechanisms were only supported by Softoken.  It's also not clear that there would be much use for this mechanism outside of pk11_PubDeriveECKeyWithKDF (bug #676114).

Comment 5

[David Cooper]

Attachment: Implemention of CKD_SHAxxx_KDF

(In reply to Brian Smith (:bsmith) from comment #3)
> The new mechanism you propose should be split into multiple mechanisms like
> was done for CKM_NSS_HKDF_*. This is ugly, but it is useful because it
> allows the calling application to easily query the module about what hash
> functions it supports for the CKM_NSS_ANSI_X9_63_KDF mechanism. For example,
> a module might not support SHA-1 but might support SHA-256.

Okay.  I've modified the patch to define a separate mechanism for each hash function.

Comment 6

[Robert Relyea]

OK, so I prefer your previous patch, basically because it mirrors what CKM_ECDH1_DERIVE does (which has all the issues brian meantioned, but is already part of the standard), since the purpose is to handle the case where CKM_ECDH1_DERIVE was deficient in the token with the private key. I would like you to write up your new mechanism and propose it to the PKCS#11 working group (they'll probably give it a new number, of course).

Taking your previous patch I have some questions and a few comments....

1) what is the purpose of trying to ''save' the key size returned from pk11_GetPredefinedKeyLength? (I'm not saying it's wrong, but I am worried if this change was necessary because of some issues you were running into.

2) The handling of tokens that only support CKD_NULL_KDF should be in the pk11wrap layer, not pushed up in, say cms;).

Comment 7

[Robert Relyea]

Comment on attachment 550196 [details] [diff] [review]
Implemention of CKD_SHAxxx_KDF

r+ rrelyea

Comment 8

[Robert Relyea]

Comment on attachment 551567 [details] [diff] [review]
Implemention of CKD_SHAxxx_KDF

r-

Comment 9

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

Comment on attachment 551567 [details] [diff] [review]
Implemention of CKD_SHAxxx_KDF

Clearing review based on rrelyea's comments. Please re-request review of the patch that you think we should go with.

I do not care much which strategy for supporting multiple hash functions is used. However, if the "one mechanism with hash parameter" strategy is used, then please explain how an application that would normally use PK11_GetBestSlotMultiple/PK11_GetBestSlot would select which slot(s) to use when each slot has differing support for hash functions with these mechanisms. In particular, how to cope with the case where some tokens only support SHA-1 and others support SHA-2, or future cases where some tokens implement SHA-3 and others don't and Thunderbird prefers SHA-3 hash algorithms. How would an application deal with this? How will the existing mechanisms, and the proposed new mechanism, deal with SHA-3 hash functions? Would new parameter values for the existing mechanisms be added for the SHA-3 hash functions, or will there be new SHA-3-capable mechanisms added?

The PKCS#11 (draft?) spec does define a metadata mechanism that allows for queries other than "is this mechanism supported," but IIRC, Softoken doesn't implement it, and pk11wrap doesn't expose that functionality it to applications. When I looked into adding support for such metadata queries to softoken during the time I implemented HKDF, it seemed like it would require too much work (in softoken, and likely in other implementations) to be worthwhile. Further, I was unsure how many other tokens actually implement that metadata mechanism in a useful way. That is why I implemented HKDF as an ugly family of separate mechanisms.

Comment 10

[David Cooper]

(In reply to Robert Relyea from comment #6)
> I would like you to write up your new mechanism and propose it
> to the PKCS#11 working group (they'll probably give it a new
> number, of course).

Given the feedback that I've received on the Cryptoki mail list and the fact that the most recent document on the RSA web site is a draft version 2.3 from July 2009, it seems that waiting for a new mechanism to be added to PKCS #11 is not a viable option.  So, it seems that the way to move forward is to:

1) use an NSS-specific mechanism (or set of mechanisms) based on one of the previously submitted patches; or

2) implement the KDF using existing mechanisms, as was suggested on the Cryptoki mail list.  This would involve implementing the KDFs using sequences of calls to mechanisms such as CKM_CONCATENATE_BASE_AND_DATA, CKM_CONCATENATE_BASE_AND_KEY, CKM_CONCATENATE_DATA_AND_BASE, CKM_SHA1_KEY_DERIVATION, CKM_SHA256_KEY_DERIVATION, etc.

Option 2 would avoid the need to specify an NSS-specific mechanism (or set of mechanisms), but it would be far less efficient, so I would prefer option 1.  If option 1 is used, it doesn't matter to me whether one or multiple mechanisms are defined, although I will raise one issue.

There are really (at least) three mechanisms that need to be supported:

1) The ability to perform the ECDH primitive.

2) The ability to perform the KDF.

3) The ability to perform whatever operations need to be performed with the derived symmetric key.

My patch addresses the known problem of a cryptographic module that can perform the ECDH primitive, but that cannot do anything else.  The patch simply assumes that the cryptographic module that can perform the KDF (whether it is the same module or a different module than the one that performed the ECDH primitive) can also make use of the derived key (e.g., to perform bulk decryption using 3DES or AES).  If there is a chance that multiple cryptographic modules will support the new KDF mechanism(s) (i.e., CKM_NSS_ANSI_X9_63_KDF, CKM_NSS_ANSI_X9_63_SHA1_KDF, ...) and that these modules may differ in their capabilities, then should the patch associated with bug #676114 include two calls to pk11_ForceSlot, with the second call coming after key derivation is complete (both ECDH primitive and KDF) to verify that the slot holding the key supports the "target" mechanism?

Comment 11

[Robert Relyea]

OK, looking at the list, the comments are mostly "No one is editting the spec, we have lots of mechanisms that are waiting inclusion and 2.3 isn't done yet". Maybe we need to find an editor. There was only one comment on the proposal itself and it suggested 

In the meantime we need to choose between option 1 and option 2. Option 2 has the advantage of having the most compatibility (it would work with systems that have older versions of softoken -- which exist out there) at the cost of some efficiency. The Red Hat VPN solution uses option 2 pretty successfully. My question is there really a performance hit for S/MIME that's actually perceptible? If we are worried about SSL servers I can see the argument for case 1.

My preference would be include the new KDF's not yet supported by softoken in the patch, but use option 2 to implement the KDF's if for KDF free tokens.

Also, thanks for the work you've put into this hand the hoops you've jumped through, I totally agree that supporting tokens that only support the most basic ECC primitives is a worthwhile goal.

bob

Comment 12

[David Cooper]

Attachment: Implementation of CKD_SHAxxx_KDF when used as part of CKM_ECDH1_DERIVE and CKM_ECDH1_COFACTOR_DERIVE

I'll work on trying to implement option 2 from Comment 10 as soon as I can find some time.  In the meantime, this patch contains just those portions of the original patch that implement the KDF in Softoken when Softoken is called upon to perform CKM_ECDH1_DERIVE or CKM_ECDH1_COFACTOR_DERIVE with a KDF other than CKD_NULL (i.e., it addresses the original problem raised in this bug, but does not address the problem of supporting tokens that only implement the ECDH primitive).

Once I implement the KDF by itself (hopefully based on option 2 in Comment 10), I'll submit another patch with that code.  However, I think it would be more appropriate to submit that code as part of a revised patch for bug #676114.

Comment 13

[Robert Relyea]

Comment on attachment 604185 [details] [diff] [review]
Implementation of CKD_SHAxxx_KDF when used as part of CKM_ECDH1_DERIVE and CKM_ECDH1_COFACTOR_DERIVE

r-, for some nits.

The following is the two things that do need to be fixed:

1) in pk11skey.c we're now punting on the key length if the kdf is specified. I don't think that is necessary. (And I'm worried it will break things that used to work). At some point is seems we will want to map the kdf number to a hash, which will give us the length right away.

2) It's a nit, but we should be consistant with naming. The two new full upper case functions you added in softoken should be mixed case and preceded with sftk_ (e.i. sftk_AnsiX9_64Kdf). I'm OK with sftk_ANSI_X9_63_KDF even since ANSI is really all caps, but as it stands in the code now, it looks like it's supposed to be a macro from the 'ANSI' component'. The NSC_XXX looks like a PKCS #11 entry point. I'm not really all that hung up on the names, but they are quite far off the naming standard for local functions in this file. (I'll use your current names for the rest of the review).

Other nits I would like fixed. 

The entire key length calculation should probably live in it's own helper function now. Take a pubKey and a kdf and return a key size from that kdf. The changes I require above would now go into this function.

In softoken, I'd like to see a mapping function from CKD_XXX_KDF to HashType, then NSC_ANSI_X9_63_KDF would simply be a call to softoken_GetHashTypeFromKDF()
and then call ANSI_X9_63_KDF with the hash object for the kdf.

Only the first 2 are required for an r+. The next 2 are just my own preference and I'll not hang up a review on them.

bob

Comment 14

[David Cooper]

Attachment: Revised implementation of CKD_SHAxxx_KDF when used as part of CKM_ECDH1_DERIVE and CKM_ECDH1_COFACTOR_DERIVE

I made the first two changes that you requested.

I didn't make either of the other changes.  There may be a another way to implement NSC_ANSI_X9_63_KDF (now sftk_ANSI_X9_63_kdf), but I can't think of a way to implement it that would make the overall resulting code and cleaner.

Comment 15

[Robert Relyea]

Comment on attachment 607619 [details] [diff] [review]
Revised implementation of CKD_SHAxxx_KDF when used as part of CKM_ECDH1_DERIVE and CKM_ECDH1_COFACTOR_DERIVE

r+ rrelyea.

Thank David.

I do have a question, why did you add the key_size variable to cache in symKey->size? It's not wrong, but it should also be unnecessary unless there is some other code that references symKey->size directly (rather than calling the PK11_ function to return the key size).

In general the pk11wrap layer sets the keysize to 0 for keys where the length is known from the type. This keeps PKCS #11 modules happy because the usually specifically don't expect a key size in those situations. We're fine in this case since we don't send the length down to the PKCS #11 module and once the key is created, it never needs to deal with the length from the module point of view.

Anyway the field is just a cache, so setting it is fine, just wanted to know if there was some specific issue you were trying to fix with this change (since we should go back and fix that underlying issue)

bob

Comment 16

[David Cooper]

Bob,

Are you referring to the line where I changed:

    if (pk11_GetPredefinedKeyLength(keyType)) {

to

    if ((key_size = pk11_GetPredefinedKeyLength(keyType))) {

If this shouldn't have been changed, you can go ahead and change it back.  The reason that I changed it was that it simply looked like a bug.  

            key_size = keySize;
	    if (key_size == 0) {
		if (pk11_GetPredefinedKeyLength(keyType)) {
		    templateCount --;
		} else {
		    /* sigh, some tokens can't figure this out and require
		     * CKA_VALUE_LEN to be set */
		    key_size = SHA1_LENGTH;
		}
	    }
	    symKey->size = key_size;

It appeared to me that the entire point of this code was to determine the correct value for key_size, and thus symKey->size, and yet if pk11_GetPredefinedKeyLength(keyType) returned the correct value for the key size (thus avoiding the need to use a default value of SHA1_LENGTH), the results of pk11_GetPredefinedKeyLength(keyType) were just thrown away.

This doesn't affect the code that I wrote for bug #676118, since that code always calls PK11_PubDeriveWithKDF() with a non-zero value for keySize.

(In reply to Robert Relyea from comment #15)
> Comment on attachment 607619 [details] [diff] [review]
> Revised implementation of CKD_SHAxxx_KDF when used as part of
> CKM_ECDH1_DERIVE and CKM_ECDH1_COFACTOR_DERIVE
> 
> r+ rrelyea.
> 
> Thank David.
> 
> I do have a question, why did you add the key_size variable to cache in
> symKey->size? It's not wrong, but it should also be unnecessary unless there
> is some other code that references symKey->size directly (rather than
> calling the PK11_ function to return the key size).
> 
> In general the pk11wrap layer sets the keysize to 0 for keys where the
> length is known from the type. This keeps PKCS #11 modules happy because the
> usually specifically don't expect a key size in those situations. We're fine
> in this case since we don't send the length down to the PKCS #11 module and
> once the key is created, it never needs to deal with the length from the
> module point of view.
> 
> Anyway the field is just a cache, so setting it is fine, just wanted to know
> if there was some specific issue you were trying to fix with this change
> (since we should go back and fix that underlying issue)
> 
> bob

Comment 17

[Ryan VanderMeulen [:RyanVM]]

Bob, who was going to check this in?

Comment 18

[Kai Engert (:KaiE:)]

Checking in pk11wrap/pk11skey.c;
/cvsroot/mozilla/security/nss/lib/pk11wrap/pk11skey.c,v  <--  pk11skey.c
new revision: 1.125; previous revision: 1.124
done
Checking in softoken/pkcs11c.c;
/cvsroot/mozilla/security/nss/lib/softoken/pkcs11c.c,v  <--  pkcs11c.c
new revision: 1.124; previous revision: 1.123
done
Checking in util/pkcs11t.h;
/cvsroot/mozilla/security/nss/lib/util/pkcs11t.h,v  <--  pkcs11t.h
new revision: 1.22; previous revision: 1.21
done