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, [email protected]
Getronics Government Solutions, LLC
===========================================



-----Original Message-----
From: William Adams [mailto:[email protected]]
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:[email protected]]
Sent: Wednesday, May 19, 1999 11:39 AM
To: [email protected]; [email protected];
[email protected]
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   
[email protected]                             
J.G. Van Dyke & Associates, Inc.           
================================



At 03:59 PM 12/6/97, [email protected] wrote:
>David P. Kemp <[email protected]> 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.
>
>