illumos gate

Interesting. So, it's probably this change set:

changeset: 12573:fb4ef506980f
user: Dina K Nimeh <Dina.Nimeh@Sun.COM>
date: Mon Jun 07 08:54:25 2010 -0700
description:
6875651 move asymmetric crypto to libsoftcrypto
6816864 collect together padding methods used by PKCS#11
6917508 bignum library needs big random number function
6249983 softtoken based RSA/DSA slow on Niagara
6917506 arcfour lint check missing from usr/src/uts/sun4v/Makefile
6917513 move softFipsDSAUtil.c to common/crypto/fips/fips_dsa_util.c
6834849 dsa_sign() produces invalid signature when pkcs11 engine is used via openssl(1) for certain keys

One way to track this down might be to build the version of this code before the above change set, and compare old and new DH behavior with dbx.

Gordon Ross wrote:

Interesting. So, it's probably this change set:

changeset: 12573:fb4ef506980f

It is.

One way to track this down might be to build the version of this code before the above change set, and compare old and new DH behavior with dbx.

Can't do that strictly, because of it being at a time of signed crypto. What I've done instead is to back out the change, merge it forward, then re-apply it in logical chunks. Sadly, the bug I found (which caused me to open this CR, for the fix), turns out to not be the bug, but a bug. Most annoying. Work continues.

I'm convinced it'll be obvious, and I'm just blinded to it by hours of staring at it.

Just to add some commentary to the bug, DH takes two known values (a base 'g', and a prime number 'p'), creates a private random number x, and generates a public key y = g^x mod p. When combined with the other party's y value, yields a secret key that cannot feasibly be computed from only the two public values.

The values of g, p, and x must obey these rules (there are a couple more that aren't relevant):
0 < g < p
0 < x < p-1
Since y = g^x mod p, 0 < y < p

Thus the sizes (used to store the values) of g, x, and p must obey:

• sizeof (g) <= sizeof (p)
• sizeof (x) <= sizeof (p)
• sizeof (y) sizeof (p)

Since g, p, and sizeof (x) are given as parameters. In source:usr/src/lib/pkcs11/pkcs11_softtoken/softDH.c

/*
  * The integer public value y shall be converted to an octet
  * string PV of length k, the public value.
  */
if ((rv = soft_genDHkey_set_attribute(pubkey, CKA_VALUE, public_y,
    CRYPTO_BITS2BYTES(k.value_bits), B_TRUE)) != CKR_OK) {
        goto ret;
} 

value_bits is the size of x. Thus when sizeof (x) < sizeof (y), this will only partially copy the public value into the pkcs11 key object.

Also, in source:usr/src/common/crypto/dh/dh_impl.c there is

        /* Convert public-value y to bignum. */
         if ((brv = big_extend(&(dhkey.y), CHARLEN2BIGNUMLEN(value_bytes))) !=
             BIG_OK) {
                 rv = convert_rv(brv);
                 goto ret;
         }
         bytestring2bignum(&(dhkey.y), bkey->public_y, value_bytes);

In this case value_bytes is the size (in bytes instead of bits) of x. Again, this will truncate the value of y, which will produce an incorrect secret key. The remaining fixes should clarify the sizing used (the old code sometimes just use the size of the prime, while should be the largest sized number during the calculation, can lead to confusion when doing analysis).

While we're not sure if the original submitter tripped over this, there is another potential problem with 64-bit systems in the conversion of the secret key from the bignum format to a bytestring. In source:usr/src/common/crypto/dh/dh_impl.c

 #ifdef _KERNEL
         if ((s = kmem_alloc(P2ROUNDUP_TYPED(prime_bytes,
             sizeof (BIG_CHUNK_SIZE), size_t))) == NULL) {
 #else
         if ((s = malloc(P2ROUNDUP_TYPED(prime_bytes,
             sizeof (BIG_CHUNK_SIZE), size_t))) == NULL) {
 #endif
                 rv = CKR_HOST_MEMORY;
                 goto ret;
         }

In this instance, it will always allocate a size rounded up to a multiple of 4 since BIG_CHUNK_SIZE is either '32' or '64' (i.e. sizeof(32) sizeof(64) == sizeof (int)). However, the bignum library words on chunks BIG_CHUNK_SIZE bits (i.e. 4 or 8 bytes, depending on if a 32 or 64-bit object is being built). This means that depending on the size of prime_bytes, it could possibly allocate a buffer that is insufficient to hold the most significant 1-8 bytes of the secret key (it will be truncated). If *secretkey_len (the desired length of the secret key, since an app can request a key size smaller than sizeof (p)) is sufficiently large, this will truncate the secret key value.