Subject: Re: How to Calculate Signatures?

From: [email-masked] ("Hal Finney")
Date: Sat, 2 Apr 2005 12:16:14 -0800 (PST)

Ben Laurie writes:

> The sections on calculating signatures are really confusing. I can't 
> currently suggest alternate text for most of it because its far from 
> clear to me what the actual algorithms are. If someone explains, I'll do 
> my best to write clarifying text.

You're right, this is really messed up.

The authoritative section on what to hash is 5.2.4.  We should refer
forward to that section and not include detailed information about
what is hashed in the sections on V3 and V4 signature packets.

We should make it clear that the DSA signature algorithm works directly
on the hash value that results from 5.2.4.

We should say that RSA signatures use that hash and prepend the sequence
of bytes identified as the "full hash prefixes".  We could probably remove
the hexadecimal equivalents to the ASN.1 OIDs; if someone understands
ASN.1 well then the OIDs are enough, and if not then they can just
follow the rule to prepend the proper byte sequences and that will work.
This then gets padded as in PKCS#1 v1.5 signatures.  We should have a
sentence clarifying that this is what gives us the value "m" used in
the signature calculation.

Hal

---

From: Ben Laurie <[email-masked]>
Date: Sun, 03 Apr 2005 03:53:26 +0100

> the signature calculation.

We also need to specify emLen, which I presume (by logic and experiment) 
is equal to the RSA key size.

I will send diffs soon. Thanks for the clarification.

Cheers,

Ben.

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

---

From: Ben Laurie <[email-masked]>
Date: Sun, 03 Apr 2005 16:03:10 +0100

Here are proposed diffs.

Cheers,

Ben.

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff
--- draft-ietf-openpgp-rfc2440bis-12.txt	Tue Nov 23 18:36:41 2004
+++ draft-ietf-openpgp-rfc2440bis-12-ben.txt	Sun Apr  3 15:29:31 2005
@@ -1137,13 +1137,6 @@
      - One or more multiprecision integers comprising the signature.
        This portion is algorithm specific, as described below.
 
-   The data being signed is hashed, and then the signature type and
-   creation time from the signature packet are hashed (5 additional
-   octets).  The resulting hash value is used in the signature
-   algorithm. The high 16 bits (first two octets) of the hash are
-   included in the signature packet to provide a quick test to reject
-   some invalid signatures.
-
    Algorithm Specific Fields for RSA signatures:
 
      - multiprecision integer (MPI) of RSA signature value m**d mod n.
@@ -1154,80 +1147,10 @@
 
      - MPI of DSA value s.
 
-   The signature calculation is based on a hash of the signed data, as
-   described above.  The details of the calculation are different for
-   DSA signature than for RSA signatures.
-
-   The hash h is PKCS-1 padded exactly the same way as for the above
-   described RSA signatures.
-
-   With RSA signatures, the hash value is encoded as described in
-   PKCS-1 section 9.2.1 encoded using PKCS-1 encoding type
-   EMSA-PKCS1-v1_5 [RFC2437].  This requires inserting the hash value
-   as an octet string into an ASN.1 structure. The object identifier
-   for the type of hash being used is included in the structure.  The
-   hexadecimal representations for the currently defined hash
-   algorithms are:
-
-     - MD5:        0x2A, 0x86, 0x48, 0x86, 0xF7, 0x0D, 0x02, 0x05
-
-
-
-Callas, et al.          Expires May 23, 2005                  [Page 21]
-INTERNET-DRAFT          OpenPGP Message Format             Nov 23, 2004
-
-     - RIPEMD-160: 0x2B, 0x24, 0x03, 0x02, 0x01
-
-     - SHA-1:      0x2B, 0x0E, 0x03, 0x02, 0x1A
-
-     - SHA256:     0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01
-
-     - SHA384:     0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x02
-
-     - SHA512:     0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x03
-
-   The ASN.1 OIDs are:
-
-     - MD5:        1.2.840.113549.2.5
-
-     - RIPEMD-160: 1.3.36.3.2.1
-
-     - SHA-1:      1.3.14.3.2.26
-
-     - SHA256:     2.16.840.1.101.3.4.2.1
-
-     - SHA384:     2.16.840.1.101.3.4.2.2
-
-     - SHA512:     2.16.840.1.101.3.4.2.3
-
-   The full hash prefixes for these are:
-
-       MD5:        0x30, 0x20, 0x30, 0x0C, 0x06, 0x08, 0x2A, 0x86,
-                   0x48, 0x86, 0xF7, 0x0D, 0x02, 0x05, 0x05, 0x00,
-                   0x04, 0x10
-
-       RIPEMD-160: 0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2B, 0x24,
-                   0x03, 0x02, 0x01, 0x05, 0x00, 0x04, 0x14
-
-       SHA-1:      0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2b, 0x0E,
-                   0x03, 0x02, 0x1A, 0x05, 0x00, 0x04, 0x14
-
-       SHA256:     0x30, 0x31, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86,
-                   0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01, 0x05,
-                   0x00, 0x04, 0x20
-
-       SHA384:     0x30, 0x41, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86,
-                   0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x02, 0x05,
-                   0x00, 0x04, 0x30
-
-       SHA512:     0x30, 0x51, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86,
-                   0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x03, 0x05,
-                   0x00, 0x04, 0x40
-
-   DSA signatures MUST use hashes with a size of 160 bits, to match q,
-   the size of the group generated by the DSA key's generator value.
-   The hash function result is treated as a 160 bit number and used
-   directly in the DSA signature algorithm.
+   The signature calculation is based on a hash of the signed
+   data. This is described in detail in section 5.2.4. The high 16
+   bits (first two octets) of the hash are included in the signature
+   packet to provide a quick test to reject some invalid signatures.
 
 Callas, et al.          Expires May 23, 2005                  [Page 22]
 INTERNET-DRAFT          OpenPGP Message Format             Nov 23, 2004
@@ -1263,20 +1186,16 @@
      - One or more multiprecision integers comprising the signature.
        This portion is algorithm specific, as described above.
 
-   The data being signed is hashed, and then the signature data from
-   the version number through the hashed subpacket data (inclusive) is
-   hashed. The resulting hash value is what is signed.  The left 16
-   bits of the hash are included in the signature packet to provide a
-   quick test to reject some invalid signatures.
-
    There are two fields consisting of signature subpackets.  The first
    field is hashed with the rest of the signature data, while the
    second is unhashed.  The second set of subpackets is not
    cryptographically protected by the signature and should include only
    advisory information.
 
-   The algorithms for converting the hash function result to a
-   signature are described in a section below.
+   The algorithms for calculating the hash and converting the result
+   to a signature are described in section 5.2.4. The left 16 bits of
+   the hash are included in the signature packet to provide a quick
+   test to reject some invalid signatures.
 
 5.2.3.1. Signature Subpacket Specification
 
@@ -1936,7 +1855,72 @@
    resulting hash field is used in the signature algorithm, and placed
    at the end of the signature packet.
 
-5.2.4.1. Subpacket Hints
+5.2.4.1. Signature Algorithms
+
+5.2.4.1.1. DSA Signatures
+
+   A DSA signature is performed as specified in [FIPS-186-2] on the
+   value of the hash, calculated as above.
+
+   DSA signatures MUST use hashes with a size of 160 bits, to match q,
+   the size of the group generated by the DSA key's generator value.
+   The hash function result is treated as a 160 bit number and used
+   directly in the DSA signature algorithm.
+
+5.2.4.1.2. RSA Signatures
+
+   With RSA signatures, the hash value is encoded as described in
+   PKCS #1 section 9.2.1 encoded using PKCS #1 encoding type
+   EMSA-PKCS1-v1_5 [RFC2437].  This requires inserting the hash value
+   as an octet string into an ASN.1 structure. The object identifier
+   for the type of hash being used is included in the structure.
+
+   The ASN.1 OIDs are:
+
+     - MD5:        1.2.840.113549.2.5
+
+     - RIPEMD-160: 1.3.36.3.2.1
+
+     - SHA-1:      1.3.14.3.2.26
+
+     - SHA256:     2.16.840.1.101.3.4.2.1
+
+     - SHA384:     2.16.840.1.101.3.4.2.2
+
+     - SHA512:     2.16.840.1.101.3.4.2.3
+
+   In practice this amounts to prefixing the hash with one of the
+   following, then padding as described in PKCS #1:
+
+       MD5:        0x30, 0x20, 0x30, 0x0C, 0x06, 0x08, 0x2A, 0x86,
+                   0x48, 0x86, 0xF7, 0x0D, 0x02, 0x05, 0x05, 0x00,
+                   0x04, 0x10
+
+       RIPEMD-160: 0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2B, 0x24,
+                   0x03, 0x02, 0x01, 0x05, 0x00, 0x04, 0x14
+
+       SHA-1:      0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2b, 0x0E,
+                   0x03, 0x02, 0x1A, 0x05, 0x00, 0x04, 0x14
+
+       SHA256:     0x30, 0x31, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86,
+                   0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01, 0x05,
+                   0x00, 0x04, 0x20
+
+       SHA384:     0x30, 0x41, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86,
+                   0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x02, 0x05,
+                   0x00, 0x04, 0x30
+
+       SHA512:     0x30, 0x51, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86,
+                   0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x03, 0x05,
+                   0x00, 0x04, 0x40
+
+   The value emLen needed for the padding is equal to the length in
+   bytes of the RSA public modulus, n.
+
+   Once the hash has been encoded and padded, the resulting string is
+   encrypted with the RSA private key as described in [RSA].
+
+5.2.4.2. Subpacket Hints
 
    It is certainly possible for a signature to contain conflicting
    information in subpackets. For example, a signature may contain
@@ -3084,7 +3068,7 @@
        2          - RSA Encrypt-Only
        3          - RSA Sign-Only
        16         - Elgamal (Encrypt-Only), see [ELGAMAL]
-       17         - DSA (Digital Signature Algorithm) [SCHNEIER]
+       17         - DSA (Digital Signature Algorithm) [DSA]
        18         - Reserved for Elliptic Curve
        19         - Reserved for ECDSA
        20         - Reserved (formerly Elgamal Encrypt or Sign)
@@ -3946,6 +3930,10 @@
                     1983, August 1996.
    [RFC2119]        Bradner, S., "Key words for use in RFCs to Indicate
                     Requirement Level", BCP 14, RFC 2119, March 1997.
+   [FIPS186-2]      "Digital Signature Standard", FIPS 186-2, January
+                    2000.
+   [RSA]            Menezes, A., et al. "Handbook of Applied
+                    Cryptography", Section 8.2., October 1996.

---

From: Ben Laurie <[email-masked]>
Date: Sun, 03 Apr 2005 17:41:59 +0100

> Here are proposed diffs.

Oh, yes. This left me with an unresolved issue: how does one use 
SHA{256,384,512} with DSA (which requires a 160 bit hash).

Cheers,

Ben.

---

From: Konrad Rosenbaum <[email-masked]>
Date: Sun, 3 Apr 2005 19:48:18 +0200

> SHA{256,384,512} with DSA (which requires a 160 bit hash).

Simple: you don't. DSA was designed to be used with SHA-1, which is 160 bit. 
Since SHA-1 is theoretically broken (practically will probably follow in a 
few months) one should see what the NIST makes of it. Supplanting a broken 
hash with another hash doesn't make much sense with DSA, since it does not 
contain the ID of the hash (as PKCS#1 does for RSA) - so any attacker could 
find a collission with the broken hash and then simply change the hash ID 
in the signature packet.

	Konrad

---

From: Ian G <[email-masked]>
Date: Sun, 03 Apr 2005 19:40:31 +0100

> find a collission with the broken hash and then simply change the hash ID 

I would agree with that.  There was some discussion
on the user's list about an attempt at producing a
code path to use SHA256... which seemed to confuse
the issue.

Would it be a good idea to put in a statement
explicitly limiting OpenPGP's view of DSS to be
SHA1 only?  And add a comment perhaps that in the
light of weaknesses in SHA1, that RSA with a fatter
digest be used instead as a workaround?

(SHA1 will remain a current issue until "something
is done".  When it was debated a month back, did we
reach a consensus to do something about it?  I got
the feeling that we didn't, but I might be just
remembering one side.)

iang
-- 
News and views on what matters in finance+crypto:
         http://financialcryptography.com/

---

From: Ben Laurie <[email-masked]>
Date: Sun, 03 Apr 2005 19:50:49 +0100

> find a collission with the broken hash and then simply change the hash ID 

The hash does include the ID of the hash, and hence the signature does.

---

From: Ben Laurie <[email-masked]>
Date: Sun, 03 Apr 2005 19:52:55 +0100

Ian G wrote:
>> Simple: you don't. DSA was designed to be used with SHA-1, which is 
>> 160 bit. Since SHA-1 is theoretically broken (practically will 
>> probably follow in a few months) one should see what the NIST makes of 
>> it. Supplanting a broken hash with another hash doesn't make much 
>> sense with DSA, since it does not contain the ID of the hash (as 
>> PKCS#1 does for RSA) - so any attacker could find a collission with 
>> the broken hash and then simply change the hash ID in the signature 
>> packet.
> 
> 
> 

The cost of that is that anyone with a DSA key is screwed. Seems like a 
last resort to me.

---

From: Ian G <[email-masked]>
Date: Sun, 03 Apr 2005 21:02:54 +0100

Ben Laurie wrote:

> The cost of that is that anyone with a DSA key is screwed. Seems like a 

Anyone who has a DSA key now is screwed if:

    * the SHA1 hash is shown to be breached for:
       - pre-images, or
       - they have a collision-sensitive signature system,
    and,

    * the attacks are within reach by their attackers, and
    * they cannot change their document format, and
    * they cannot change to RSA, and
    * they cannot simply repudiate any false dox, and
    * they actually use DSA sigs for something important.

Seems like a tough list to me.  My systems use OpenPGP
sigs for real stuff (as opposed to just signing mail
because it exists there) and none of the above are
even remotely a threat that I can see.  Maybe I am
screwed, but seeing as I don't see how, I'm willing to
run that risk and maybe I'll find out :)

I personally don't see much merit in changing the situation
until something decent comes along.

iang

---

From: Konrad Rosenbaum <[email-masked]>
Date: Sun, 3 Apr 2005 21:33:50 +0200

On Sunday 03 April 2005 20:50, Ben Laurie wrote:
> Konrad Rosenbaum wrote:
> > Simple: you don't. DSA was designed to be used with SHA-1, which is 160
> > bit. Since SHA-1 is theoretically broken (practically will probably
> > follow in a few months) one should see what the NIST makes of it.
> > Supplanting a broken hash with another hash doesn't make much sense
> > with DSA, since it does not contain the ID of the hash (as PKCS#1 does
> > for RSA) - so any attacker could find a collission with the broken hash
> > and then simply change the hash ID in the signature packet.
>

That does not prevent a downgrade attack.

Presume the following scenario:

The signature S is under Text A with hash algorithm H. The hash is deemed 
secure.

So s contains the number of H and the content of A. The structure looks like 
this:

Text packet A
Signature packet S
 Hash number H
 signed(Hash_H(H_number || A)) # or something very similiar

Now we want the signature to refer to Text B and we know that hash algorithm 
X is insecure (and we know how to use that). What we need to do now is we 
need to find a text C that consists of the the number of X, and B plus some 
"random" that is chosen in a way that does not distort the meaning (eg. a 
"geek code block" below the actual eMail text). The structure will look 
like:

Text packet C ( = B || "random")
Signature packet S'
 Hash number X
 signed(Hash_H(H_number || A)) == signed(Hash_X(X_number || C))

...and that all because a weak Hash X will enable us to find a text that 
creates the same hash sum in X that we want to supplant for a hash sum of H 
- regardless of whether we hash the hash number, a "magic" code or my grand 
mothers birthday into it.

MD5 is already beaten down to 33 bit, it is only a question of time till 
SHA-1 is there as well (granted, we'll probably have some months left). 
Currently we are only save because there is no 160-bit Hash in OpenPGP that 
is vulnerable enough to make the attack worthwhile.

The days of DSA with a 160-bit p are counted. Period.

	Konrad

PS.: please view my DSA signature on this mail as my last action of respect 
to DSA. It was a good fellow... ;-)