[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

RE: Encoding of INTEGER fields in PKIX certs



Title: FW: Encoding of INTEGER fields in PKIX certs
John,
 
We have looked into this problem a bit deeper and we feel that the problem is not with the P parameter that was issued by the entrust CA. I stepped through some of the process of verifying a DSA signature. To start with I dumped the asn encoded certificate, that contained the DSA parameters, during the function "checkTrustedCertSig" in "CM_cache.c". The dumped ASN.1 is attached in the file cert.asn1 and the encoded result is included in cert.txt. As you can see the parameters all have a single octet prepended, in which every bit is set to 0. So I stepped through the decoding of the DSA parameters to observe where this octet went. It happens in the file "X_DecodeCert.c" in the function
 
"short copyHugeIntToExistingBytes(Bytes_struct *cm_bytes, AsnOcts *octs, long zPad)".
 
At the start of this function it has the following section of code:
 
/* look at the first byte */
 if (count > 1)
 {
  if(data[0] == 0)
  {
   data++; /* skip that leading zero */
   count--; /* remove leading zero, indicating positive numeric value */
  }
 }
 
Obviously this means that our parameters now no longer have the zeroed octet on the front and so will fail the test in void "CSM_BigIntegerStr::Get(CSM_Buffer    &bigIntBuf, const size_t   octets)". According to the message you forwarded it looks like
 
"short copyHugeIntToExistingBytes(Bytes_struct *cm_bytes, AsnOcts *octs, long zPad)"
 
is performing the right steps since it says if every bit of the most significant octet is set to zero then it should be deleted. It looks like the check performed, which our parameters fail, does not take into account that the prepending octet might have already been removed and so checks the value of the MSB to late.
 
Could you please look at this to verify where the problem lies.
 
Regards
 

William Adams
Software Engineer
Nexor.
================
Tel:  +44 115 9535536
Fax: +44 115 9520519

-----Original Message-----
From: owner-imc-sfl@xxxxxxxxxxxx [mailto:owner-imc-sfl@xxxxxxxxxxxx]On Behalf Of Pawling, John
Sent: 10 August 2001 19:15
To: 'William.Adams'; SFL List (E-mail)
Subject: FW: Encoding of INTEGER fields in PKIX certs

William,

The Entrust CA has generated an invalid P parameter.  The SFL correctly reported the error.  Please see the attached message, subject: Re: Encoding of INTEGER fields in PKIX certs, for further details.

===========================================
John Pawling, John.Pawling@xxxxxxxxxxxxxxxx
Getronics Government Solutions, LLC
===========================================



-----Original Message-----
From: William Adams [mailto:William.Adams@xxxxxxxxxxx]
Sent: Thursday, August 09, 2001 11:00 AM
To: SFL List (E-mail)
Subject: Invalid DSA Parameters?



I am trying to validate a certificate that has been issued by a Entrust V6
CA. The certificate was signed using DSA. When I try to verify the
certificate the SFL returns the error "MSB is 1.". Stepping through this I
found that the error occurred when trying to Get the parameters in the
function

SM_RET_VAL CSM_DSAParams::Decode(CSM_Buffer *pParams)

This function calls

void CSM_BigIntegerStr::Get(CSM_Buffer    &bigIntBuf, const size_t   octets)

which performs several checks to see if the parameters are valid. One of
these checks is

if (bigIntData[0] >> 7 == 1)
{
     SME_THROW(BIGINT_DECODE_ERROR, "MSB is 1.", NULL);
}

According to the comment surrounding the code this check is:

/* Make sure value is not negative.  This rule only applies here
   because the octets variable is only used when decoding
   r,s,p,g,q, or y values; which MUST be positive. */

However are parameters all fail this check. If we comment out this line
check then the certificate is verified. To verify there was nothing wrong
with the certificate I imported it into the CAPI Certificate Store and this
managed to verify the certificate. The P parameter that fails is shown here:

b68b0f942b9acea5
25c6f2edfcfb9532
ac011233b9e01cad
909bbc48549ef394
773c2c713555e6fe
4f22cbd5d83e8993
334dfcbd4f41643e
a29870ec31b450de
ebf198280ac93e44
b3fd22979683d018
a3e3bd355bffeea3
21726a7b96dab93f
1e5a90af24d620f0
0d21a7d402b91afc
ac21fb9e949e4b42
459e6ab24863fe43

this was observed both during debugging and also when viewing the
certificate through the CA. Is there a fault with this parameter or is the
check wrong?

Regards

William Adams
Software Engineer
Nexor.
================
Tel:  +44 115 9535536
Fax: +44 115 9520519


+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
-----Original Message-----
From: John Pawling [mailto:jsp@xxxxxxxxxxxxx]
Sent: Wednesday, May 19, 1999 11:39 AM
To: pgut001@xxxxxxxxxxxxxxxxx; IETF-PKIX@xxxxxxxxxxxxxxxx;
dpkemp@xxxxxxxxxxxxxx
Subject: Re: Encoding of INTEGER fields in PKIX certs


All,

The US Department of Defense MISSI Key Privilege Certificate Management Working Group (KPCMWG) debated the issue of encoding large INTEGERs raised by Dave Kemp in his original msg in this chain.  The MISSI KPCMWG came to the same conclusion as Peter stated in the enclosed msg that X.680 must be followed and decided to adopt the following strategy:


Rules for ASN.1 encoding INTEGER values generated by the crypto token (i.e. hardware and/or software that implements the crypto algorithms):

IF the crypto token generates an INTEGER value in which the most significant 9 bits are all set to 0, THEN the encoding software deletes the most significant octet from the octets to be encoded.  This rule is applied repeatedly to the remaining octets until the most significant 9 bits are not all set to 0.

IF the crypto token generates an INTEGER value in which the most significant bit (MSB) is set to 1, THEN the encoding software prepends a single octet in which every bit is set to 0 to the octets to be encoded.


Rules for ASN.1 decoding INTEGER values to be supplied to the crypto token:

1) IF the encoded value is "missing" octets (i.e. there are fewer than the expected number of octets) THEN the decoding software ensures that the MSB is 0 and, if so, prepends the appropriate number of octets in which every bit is set to 0 to the decoded value to obtain the value to be supplied to the crypto token.  If the MSB of the value encoded in the certificate is set to 1, then an error condition is reported.

2) IF the encoded value includes an "extra" octet (i.e. the length of the decoded value is one greater that what is expected) THEN the decoding software ensures that every bit in the most significant octet is set to 0 and, if so, deletes the most significant octet from the decoded value to obtain the value to be supplied to the crypto token.  If the most significant octet contains a bit set to 1, then an error condition is reported.


Example 1:

Encoding: The software uses the crypto token to generate a 128 byte DSA public key in which the most significant octets are "FF0B".  The aforementioned encoding rules are applied. Because the MSB is set to 1, then the software prepends a single octet in which every bit is set to 0 to the octets to be encoded.  In this case, a 129 byte DSA public key is encoded in the DSAPublicKey ASN.1 INTEGER in which the most significant octets are "00FF0B"

Decoding: The certificate-using software discovers that a 129 byte DSA public key in which the most significant octets are "00FF0B" is encoded in the certificate.  Because the crypto token demands a 128 byte DSA public key, the decoding software ensures that every bit in the most significant octet is set to 0 and deletes the most significant octet from the decoded value to obtain the value to be supplied to the crypto token to obtain a 128 byte value in which the most significant octets are "FF0B".


Example 2:

Encoding: The software uses the crypto token to generate a 128 byte DSA public key in which the most significant octets are "001FFF". The aformentioned encoding rules are applied.  Because the most significant 9 bits are all set to 0, then the most significant octet is not included in the encoding of the public key.  The aforementioned encoding rules are applied to the remaining octets.  The most significant nine bits are neither all set to 1 nor all set to 0, so the ASN.1 rules are satisfied.  In this case, a 127 byte DSA public key value is encoded in the DSAPublicKey ASN.1 INTEGER in which the most significant octets are "1FFF"

Decoding: The certificate using software discovers that a 127 byte DSA public key in which the most significant octets are "1FFF" is encoded in the certificate.  Because the cryto token demands a 128 byte public key and because the MSB of the decoded value is 0, then the decoding software prepends an octet consisting of all zeroes (i.e. 00) to the decoded value to obtain a 128 byte value in which the most significant octets are "001FFF".


Example 3:

Encoding: The software uses the crypto token to generate a 128 byte DSA public key in which the most significant octets are "00001FFF". The aformentioned encoding rules are applied.  Because the most significant 9 bits are all set to 0, then the most significant octet is not included in the encoding of the public key.  The aforementioned encoding rules are applied to the remaining octets. Because the most significant 9 bits of the remaining octets are all set to 0, then the most significant of the remaining octets is also not included in the encoding of the public key.  The aformentioned encoding rules are applied to the remaining octets.  The most significant nine bits are neither all set to 1 nor all set to 0, so the ASN.1 rules are satisfied.  In this case, a 126 byte DSA public key value is encoded in the DSAPublicKey ASN.1 INTEGER as in which the most significant octets are "1FFF"

Decoding: The certificate using software discovers that a 126 byte DSA public key in which the most significant octets are "1FFF" is encoded in the certificate.  Because the cryto token demands a 128 byte public key and because the MSB of the decoded value is 0, then the decoding software prepends two octets each of which consist of all zeroes to the decoded value to obtain a 128 byte value in which the most significant octets are "00001FFF".

================================
John Pawling  
jsp@xxxxxxxxxxxxx                            
J.G. Van Dyke & Associates, Inc.          
================================



At 03:59 PM 12/6/97, pgut001@xxxxxxxxxxxxxxxxx wrote:
>David P. Kemp <dpkemp@xxxxxxxxxxxxxx> writes:
>
>>ASN.1 INTEGERS are encoded as two's-complement numbers, which implies that if
>>a BER-encoded value is decoded into a larger native storage value, the high
>>bit of the encoded value will be sign-extended into the excess bits of the
>>native value. For cryptographic purposes, it is my understanding that bignums
>>are always the same size as the encoded values, so the issue of sign
>>extension never arises.  (Additionally, for cryptographic algorithms using
>>modular arithmetic with a 2^n modulus, any sign-extended bits larger than the
>>modulus are ignored - chopped off in the modular reduction.)
>>
>>[...]
>>Since a distinguished encoding of these values is required, there MUST be an
>>encoding convention for whether to do sign padding when MSB=1. Most of the
>>cert examples I have seen do not do sign padding.
>
>The only certs I've seen that very consistently do this are the ones produced
>by Microsoft software, who encode all (well, strictly speaking about 50% on
>average) of their INTEGERs incorrectly.  Everyone else seems to get it right
>(this is from a random sample of 50-odd CA certs pulled from browsers and
>things).  My ASN.1 dump program
>http://www.cs.auckland.ac.nz/~pgut001/dumpasn1.c, will flag negative integers
>as encoding errors and can be used to check for this problem.
>
>>* Does a convention for sign padding of INTEGERs already exist anywhere?
>
>Yes.  X.680 says:
>
>  8.3.2 If the contents octets of an integer value encoding consists of more
>        than one octet then [the first 9 bits]
>       
>        a) shall not be all ones; and
>        b) shall not be zero.
>
>  8.3.3 The contents octets shall be a two's complement binary number equal to
>        the integer value and consisting of [lots of stuff on how the bits are
>        ordered].
>
>Therefore if the high bit in the value to be encoded is set, the first octet
>is zero; if the high bit is not set, the first octet is nonzero (in other
>words INTEGERs have to be zero-padded).
>
>>If not, Part 1 should be amended to specify that compliant CAs SHALL NOT
>>generate padding 00 bytes for INTEGERs, and that verifiers SHOULD accept both
>>padded and unpadded INTEGERs.  And I will correct the examples accordingly.
>
>Doing this would be in violation of the BER and DER, which is unhealthy (you
>could try asking about messing with the encoding rules on the OSS ASN.1 list,
>but I'm pretty sure I know what they'd say).  It should be the other way
>around, always pad 00 for integers.
>
>(As an aside, it's a bit of a pain to work with these padding bytes because
>your encoded integers have a 50% chance of growing by 1 byte after your
>signature is generated.  However the standard says you have to do this, and it
>makes sense even if it's a bit of a nuisance).
>
>Peter.
>
>

Attachment: cert.asn1
Description: Binary data

{
   {
      version 2,
      CertificateSerialNumber 997353155,
      signature {
         algorithm 1.2.840.10040.4.3
      },
      issuer {
         {
            {
               2.5.4.6,
               "CA"
            }
         },
         {
            {
               2.5.4.10,
               "gc"
            }
         },
         {
            {
               2.5.4.11,
               "dnd-mdn"
            }
         },
         {
            {
               2.5.4.11,
               "entrust ca"
            }
         }
      },
      validity {
         "010809100235Z",
         "210809103235Z"
      },
      subject {
         {
            {
               2.5.4.6,
               "CA"
            }
         },
         {
            {
               2.5.4.10,
               "gc"
            }
         },
         {
            {
               2.5.4.11,
               "dnd-mdn"
            }
         },
         {
            {
               2.5.4.11,
               "entrust ca"
            }
         }
      },
      subjectPublicKeyInfo {
         algorithm {
            algorithm 1.2.840.10040.4.1,
            parameters {
               [UNIVERSAL 2] '00b68b0f942b9acea525c6f2edfcfb9532ac011233b9e01cad909bbc48549ef394773c2c713555e6fe4f22cbd5d83e8993334dfcbd4f41643ea29870ec31b450deebf198280ac93e44b3fd22979683d018a3e3bd355bffeea321726a7b96dab93f1e5a90af24d620f00d21a7d402b91afcac21fb9e949e4b42459e6ab24863fe43'H,
               [UNIVERSAL 2] '00b20db0b101df0c6624fc1392ba55f77d577481e5'H,
               [UNIVERSAL 2] '009abf46b1f53f443dc9a565fb91c08e47f10ac30147c2444236a99281de57c5e0688658007b1ff99b77a1c510a580917851513cf6fcfccc46c6817892843df4933d0c387e1a5b994eab1464f60c21224e28089c92b9669f40e895f6d5312aef39a262c7b26d9e58c43aa81181846daff8b419b4c211aed0223baa207fee1e5718'H
            }
         },
         subjectPublicKey '00028180751dc7dedc0c17b7c85d08987116bb856f43bf45f8912e8b7befbccfd957d2c6056fc80060506e5618d6eaafd7fb37c201017eb6a55970a4b2a364d097a13cd53080bc80a6cc5ed24da39605077f7baf21a0a9eac845da7522ebe4d5905cab2591e171c61903a21f2c9d253a06a4b9190f36e59aa2ce2f50fcee66484d8d45df'H
      },
      extensions {
         {
            extnId 2.16.840.1.113730.1.1,
            extnValue '03020007'H
         },
         {
            extnId 2.5.29.31,
            extnValue '305a3058a056a054a4523050310b3009060355040613024341310b3009060355040a130267633110300e060355040b1307646e642d6d646e31133011060355040b130a656e7472757374206361310d300b0603550403130443524c31'H
         },
         {
            extnId 2.5.29.16,
            extnValue '3022800f32303031303830393130303233355a810f32303231303830393130333233355a'H
         },
         {
            extnId 2.5.29.15,
            extnValue '03020106'H
         },
         {
            extnId 2.5.29.35,
            extnValue '30168014ba72f961cdfab7dd245fe35b4dae4e7af66b186a'H
         },
         {
            extnId 2.5.29.14,
            extnValue '0414ba72f961cdfab7dd245fe35b4dae4e7af66b186a'H
         },
         {
            extnId 2.5.29.19,
            extnValue '30030101ff'H
         },
         {
            extnId 1.2.840.113533.7.65.0,
            extnValue '300e1b0856362e303a342e3003020490'H
         }
      }
   },
   {
      algorithm 1.2.840.10040.4.3
   },
   [UNIVERSAL 3] '00302c0214665271dcd535310f005e8a5848f9b03f47cf64310214466ba3dc3169757f56d8baba06b4e167b0d00819'H
}