Section 12 comments (Padding for DSS signatures)

The following represents some discussions that went on a long time ago.  The
reasons for needing the padding are still valid for us.  SHould this go into
the new section 12 for the CMS draft or else where?

-----Original Message-----
From: John Pawling [mailto:jsp(_at_)jgvandyke(_dot_)com] 
Sent: Thursday, October 09, 1997 5:20 AM
To: Phil Hallin; Jim Schaad (Exchange)
Cc: renich1(_at_)missi(_dot_)ncsc(_dot_)mil
Subject: RE: FW: Comments on PKCS #7, version 1.6: Digest-encryption
process for DSA

Phil,

I agree with your recommendation to allow the signer the flexibility to
include the extra padding, but that the padding is not a mandatory
requirement.  I agree with you that the padding will not cause ASN.1
decoding problems since the padded values are ignored by the decoder.  

Please note that bytes can be added to the R and S values in addition to
leading zeroes being deleted.  Recommend that you set your maximum
Dsa-Sig-Value size to include the worst case scenario in which both the
R
and S values each have a zero octet prepended (i.e. 129 bytes each).

==============================================================
John Pawling                               (301) 953-3600
J.G. Van Dyke & Associates, Inc.           (410) 880-6095
141 National Business Pkwy, Suite 210      FAX: (301) 953-2901
Annapolis Junction, MD  20701              jsp(_at_)jgvandyke(_dot_)com

At 06:26 PM 10/8/97 -0700, Phil Hallin wrote:


      The EncryptedDigest is an OCTET STRING. For DSS, the initial
bytes of the OCTET STRING contain the ASN.1 sequence of the R and S
unsigned integers. The length of the sequence is dependent on the
unsigned integers having or not having leading 0's that are removed for
DER encoding. I also believe, that  DSS resigning of the same content
with the same private key results in different R and S values. This

also

leads to different lengths for the sequence.

      In our PKCS #7 streaming code, if the PKCS #7 is definite length
encoded, we need to make an initial pass to calculate the overall

length

of the message. When doing the length calculation, we skip the hash
step. On the second pass, we update the outer sequence lengths with the
correct lengths and hash the content. When we get to the signer info,

we

do the DSS signature and update the EncryptedDigest. Since R and S are
encoded as unsigned integers, they can have leading 0's that will be
stripped off. This will change the length of the sequence. If we don't
allow padding, then, it will also change the length of EncryptedDigest.
However, if we allow padding, then, we can set the length of the
EncryptedDigest to the maximum length the sequence of unsigned integers
can have to contain the DSS R and S components.

      The verify code, simply decodes the initial bytes of the OCTET
STRING. The verifier simply skips the padding. I have seen similar
padding in certificate extension values. We ASN.1 decode the initial
bytes of the extension and ignore the trailing, padding bytes.

      In summary, I  want to allow the signer the flexibility to
include the extra padding. I used it when doing Definite Length
streaming of DSS SignedData messages. However, the padding is not
required.

-----Original Message-----
From:        jsp(_at_)jgvandyke(_dot_)com [SMTP:jsp(_at_)jgvandyke(_dot_)com]
Sent:        Wednesday, October 08, 1997 4:22 PM
To:  Jim Schaad (Exchange)
Cc:  Russ Housley (E-mail); renich1(_at_)missi(_dot_)ncsc(_dot_)mil
Subject:     Re: FW: Comments on PKCS #7, version 1.6:
Digest-encryption process for DSA

Jim,

The process that you describe in your message is exactly what we are
planning to implement except for a couple of minor changes:

1) To comply with PKIX I, we are planning on using the X9.57 OID 
        as follows: id-dsa-with-sha-1 {1 2 840 10040 4 3}. 
   We are planning on using the NIST OID for SHA1 as follows:
    id-sha1 (iso(1) identified-organization(3) oiw(14) secsig(3)
algorithm(2) 26}.

2) We are planning to correctly implement the R and S values as
unsigned
ASN.1 INTEGERs.  The attachment explains our planned strategy.  This
strategy could result in octets being omitted or prepended to the R
and S
values.  I disagree with your plan to pad the ASN.1 encoded
EncryptedDigest
so that it is always the same length.  It seems that this just adds
more
compexity to an already complex process.  I believe that we should
just
transfer the ASN.1 encoded EncryptedDigest without padding it.

Please note that Russ Housley will be writing an Appendix to PKCS #7
that
describes the use of SHA1 and DSA with PKCS #7 v1.5.

ATTACHMENT:

ASN.1 Encoding/Decoding unsigned INTEGERs:

All SHA1/DSA related crypto values (i.e. P, Q, G, R, S, Y) need to be
unsigned numbers.  

The following strategy is planned for ASN.1 encoding r, s, p, q, g

and

y
INTEGER values:

IF the crypto token generates an r, s, p, q, g or y value in which

the

first
9 bits are all set to 0, THEN the encoding software deletes the first
octet
from the octets to be encoded.  This rule is applied repeatedly to

the

remaining octets until the first 9 bits are not all set to 0.

IF the crypto token generates an r, s, p, q, g or y value in which

the

most
significant bit (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.

The following strategy is planned for ASN.1 decoding r, s, p, q, g

and

y
INTEGER values:

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 initial octet is set to 0 and,
if so,
deletes the initial octet from the decoded value to obtain the value
to be
supplied to the crypto token.  If the "extra" octet contains a bit

set

to 1,
then an error condition is reported.

Example 1:

Encoding: The CA software uses the crypto token to generate a 128

byte

Y
value that begins with "FF0B".  The 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 Y value is encoded in the DSAPublicKey ASN.1 INTEGER
beginning 
with "00FF0B....."

Decoding: The certificate-using software discovers that a 129 byte Y
value
beginning with "00FF0B...." is encoded in the certificate.  Because
the
cryto token demands a 128 byte Y value, the decoding software ensures
that
every bit in
the initial octet is set to 0 and deletes the initial octet from the
decoded
value to obtain the value to be supplied to the crypto token to

obtain

a
128 byte value beginning with "FF0B.....".


Example 2:

Encoding: The CA software uses the crypto token to generate a 128

byte

Y
value that begins with "007FFF". The encoding rules are applied.
Because the first 9 bits are all set to 0, then the leading octet is
not
included in the encoding of the Y value.  The encoding rules are
applied to the remaining octets.  The first nine bits are neither all
set to
0 nor is the MSB set to 1, so the rules are satisfied.  In this case,
a 127
byte Y value is encoded in the DSAPublicKey ASN.1 INTEGER as
"7FFF....."

Decoding: The certificate using software discovers that a 127 byte Y
value
("7FFF....") is encoded in the certificate.  Because the crypto token
demands a 128 byte Y value, then the decoding software ensures that
the MSB
is 0 and prepends an octet consisting of all zeroes (i.e. 00) to the
decoded
value to obtain "007FFF".


Example 3:

Encoding: The CA software uses the crypto token to generate a 128

byte

Y
value that begins with "00007FFF".  The encoding rules are applied.
Because the first 9 bits are all set to 0, then the leading octet is
deleted
from the octets to be encoded in the Y value.  The rules are
applied to the remaining octets.  Because the first 9 bits are all

set

to 0,
then the leading octet is deleted from the octets to be encoded in

the

Y
value.  The encoding rules are applied to the remaining octets.
The first nine bits are neither all set to 0 nor is the MSB set to 1,
so the
rules are satisfied.  In this case, a 126 byte Y value is encoded in
the
DSAPublicKey ASN.1 INTEGER as "7FFF....."

Decoding: The certificate using software discovers that a 126 byte Y
value
("7FFF....") is encoded in the certificate.  Because the crypto token
demands a 128 byte Y value, then the decoding software ensures that
the MSB
is 0 and prepends two octets consisting of all zeroes (i.e. 0000) to
the
decoded value to obtain "00007FFF".


END OF ATTACHMENT


At 12:24 PM 10/8/97 -0700, Jim Schaad (Exchange) wrote:

Some of our people have implemented this.  How close is this going

to

match to what you are spec-ing for S/MIME V3?

jim schaad

-----Original Message-----
From:     Phil Hallin 
Sent:     Wednesday, October 08, 1997 11:18 AM
To:       Jim Schaad (Exchange)
Subject:  FW: Comments on PKCS #7, version 1.6: Digest-encryption
process for DSA



-----Original Message-----
From:     Phil Hallin 
Sent:     Wednesday, June 18, 1997 1:58 PM
To:       'pkcs-editor(_at_)rsa(_dot_)com'
Cc:       Keith Vogel; 'burt(_at_)rsa(_dot_)com'; 
'kevin(_at_)rsa(_dot_)com'; Craig

Sinclair;

Sanjay Menon
Subject:  Comments on PKCS #7, version 1.6: Digest-encryption
process for DSA

The document, Extensions and Revisions to PKCS #7, alluded to
deficiencies in the Digest-encryption process that should be
considered in version 2.0. I believe this deficiency needs to be
addressed sooner in 1.6 and possibly in 1.5 to allow DSA

signatures.


The digest-encryption process defined in version 1.5 isn't

compatible

with the signature format in DSA signed X.509 certificates used

for

Java and recommended in the <draft-ietf-pkix-ipki-part1-04.txt>.

To be compatible with the DSA X.509 signatures I propose the

following

for the PKCS#7 SignedData Digest-encryption process used for DSA
signature keys.

When signing, DSA generates two values. These values are commonly
referred to as r and s. To easily transfer these two values as one
signature, they shall be ASN.1 encoded using the following ASN.1
structure:
Dsa-Sig-Value ::= SEQUENCE {
   r       INTEGER,
   s      INTEGER }

When a PKCS #7 SignerInfo has a digestEncryptionAlgorithm

indicating

the use of a DSA signature key, for instance, {iso(1)
identified-organization(3) oiw(14) secsig(3) algorithm(2) 12} and

digestAlgorithm indicating the use of sha1, then, the SignerInfo's
EncryptedDigest should contain the DER encoding of the above
Dsa-Sig-Value and not the encryption with the signer's private key

of

the BER encoding of the DigestInfo as defined in Section 9.4 of

the

PKCS#7 document.

The input to the DSA signature process is the same message digest

that

is input for the DigestInfo.

The DSA signature process proposed here for PKCS#7 is identical to

the

DSA signature process used for signing DSS X.509 certificates.

One additional refinement on the octets in the EncryptedDigest for
DSA. Since the Dsa-Sig-Value is encoded as a sequence of unsigned
integers, the length can vary depending if the unsigned integers
having leading 0's. To allow the EncryptedDigest to have the same
length for different signatures, the EncryptedDigest can be padded
with trailing 0's after the ASN.1 encoding of the Dsa-Sig-Value
sequence.

Since S/MIME is using PKCS #7 version 1.5, I would also recommend

that

the above DSA signature would also be allowed in version 1.5.