Re: question about certificate verifiy using TLS

From: Thomas Pornin (pornin_at_nerim.net)
Date: 08/31/04 

Date: Tue, 31 Aug 2004 07:20:53 +0000 (UTC)

According to Niklas Olsson <niklaso@hotmail.com>:
> It's quite clear that I should use the type and length fields of the
> handshake messages.
> I just don't know how to hash it.

It is a bit tricky. What is hashed is the concatenation of all handshake
messages, up to but not including the CertificateVerify message itself.
The type and length of the messages are hashed, but not the record
headers used to send the messages. Of course, the message contents are
hashed also.

Then the result must be signed. If the client certificate contains a
DSS key, this is simple. DSS works on a message by first hashing it
with SHA-1 and then using the 160-bit value as input to some modular
arithmetic formulae. Here, you use the SHA-1 hash of the handshake
messages as the 160-bit value.

With RSA, it is a bit more complex. Let us first review how standard
PKCS#1 v1.5 signatures work:

RSA PKCS#1 defines thus the signature of a message: the message is
hashed, then the hash result is encapsulated into an ASN.1 structure
which identifies the hash function used (the raw effect is that a
fixed header, of length between 15 and 19 bytes, depending on the
hash function, is prepended to the hash result). This data is then
left-padded in a so-called "type 1" block: the added bytes have values
0x00 0x01 0xFF .. 0xFF 0x00 (one byte of value 0, one byte of value 1,
some bytes of values 0xFF [at least eight of them], one byte of value
0). The number of bytes of vallues 0xFF is adjusted so that the whole
thing has the same length than the RSA modulus. Then that array of
bytes is converted into a big integer and the RSA modular arithmetic is
applied.

For instance, let us suppose I want to sign the message "foo" (in ASCII)
with a 512-bit RSA key, using the MD5 hash function. "foo" is a three-byte
message: 66 6F 6F. Its MD5 hash is:
AC BD 18 DB 4C C2 F8 5C ED EF 65 4F CC C4 A4 D8
The special header for MD5 is:
30 20 30 0C 06 08 2A 86 48 86 F7 0D 02 05 05 00 04 10
My key length is 512 bits; that's 64 bytes. I have already 16 + 18 = 34
bytes. Thus, PKCS#1 type 1 block will add 30 bytes. Accounting for the
leading 00 and 01, and the trailing 00, that's 27 bytes of value FF which
must be added. Hence, the total padded data is:

00 01 FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF 00 30 20
30 0C 06 08 2A 86 48 86 F7 0D 02 05 05 00 04 10
AC BD 18 DB 4C C2 F8 5C ED EF 65 4F CC C4 A4 D8

which is then used as the big-endian encoding of an integer, used for
input to the RSA modular exponentiation.

SSL/TLS does not use exactly this. The handshake messages are hashed
with both MD5 and SHA-1, yielding a 36-byte value. That value is then
padded directly as a "type 1" block, _without_ the special ASN.1 header.

Thus, if the hash of all handshake messages with MD5 yields this:
B7 1A 7D 69 2F 91 10 17 62 BA B9 67 6E 56 7E D4
and with SHA-1:
64 2E 23 AD 1A C0 64 2B A9 67 C5 3E 13 A9 45 5C 4E 58 B7 DF
then the padded block converted to an integer is:

00 01 FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF 00 B7 1A 7D 69
2F 91 10 17 62 BA B9 67 6E 56 7E D4 64 2E 23 AD
1A C0 64 2B A9 67 C5 3E 13 A9 45 5C 4E 58 B7 DF

for a 512-bit signing key.

The tricky point is that such signatures usually do not fit well in the
API of signature libraries. Such libraries usually expect to get the raw
data to sign, and hash it themselves; or, at least, to get the hashed
value but apply whatever standard padding is usually required. SSL/TLS
uses, for RSA, a non-standard padding (at least not standard beyond
SSL/TLS), which is confusing.

        --Thomas Pornin

Relevant Pages

  • Re: question about certificate verifiy using TLS
    ... and one MD5) is signed (encoded with the private key). ... Right now I'm using OpenSSL to hash (md5 and sha1). ... > With RSA, it is a bit more complex. ...
    (sci.crypt)
  • Re: Public key encryption
    ... > messages as to break the hash algorithm. ... it amounts to equivalence to the RSA problem. ... anything that can forge PSS signatures can do arbitrary RSA ... > message is small compared to the encryption exponent but still a hash ...
    (sci.crypt)
  • Re: ADVERT: Secure communications
    ... Hash: SHA1 ... security analysis on it in existence were by its author. ... I'm assuming this means RSA without hybridizing with a symmetric cipher. ... than encrypting a whole message block-by-block with a 2048-bit ...
    (sci.crypt)
  • Re: Public key encryption
    ... >>messages as to break the hash algorithm. ... > it amounts to equivalence to the RSA problem. ... > anything that can forge PSS signatures can do arbitrary RSA ... > attack on weak padding is Bleichenbacher's "Million Message Attack", ...
    (sci.crypt)
  • Re: Public key encryption
    ... The trouble is that RSA is only ... >>>encryption or signing are anything but random. ... > (from which I assume you're talking about signatures, ... > domain hash". ...
    (sci.crypt)