RE: Encoding of INTEGER fields in PKIX certs
William Adams <[email protected]> Mon, 13 Aug 2001 10:39:30 +0100
| Newsgroups | gmane.ietf.sfl |
|---|---|
| Message-ID | <000101c123db$daefe790$8b353fc1@dell32022k> |
FW: Encoding of INTEGER fields in PKIX certsJohn,
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: [email protected] [mailto:[email protected]]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, [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 pu
blic 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.
>
>
cert.asn1
(application/octet-stream, 994 B) - not displayed
cert.txt
(text/plain, 3.3 KB)
{
{
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
}