Re: Encoding of INTEGER fields in PKIX certs

[jsp@xxxxxxxxxxxxx (John Pawling)]

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@jgvandyke.com                             
J.G. Van Dyke & Associates, Inc.           
================================



At 03:59 PM 12/6/97, pgut001@cs.auckland.ac.nz wrote:
>David P. Kemp <dpkemp@missi.ncsc.mil> 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.
>
>