Why does PKI use a hash function?

Question

I'll preface my question with my understanding of PKI in case I have any misconception.

1. Owner of domain D generates a public-private key pair (d,e), and constructs a certificate c consisting of (d, D, time range, other metadata).

2. D convinces certificate authority X that information in c is accurate.

3. X computes H(c) using some cryptographic hash function H.

4. X encrypts H(c) using their private key to generate c', and gives this back to D.

5. I try to access D, and D sends me (c, c')

6. My browser applies X's public key to c' and compares to H(c).

7. If they match, my browser trusts c conditional on trusting X. Repeat up to some implicitly trusted root certificate authority.

Problems with H can weaken the scheme; this is why people stopped using MD5 and are moving away from SHA1. So why not just skip step 3 and encrypt c directly?

From my understanding, one reason is to limit the length of the message to be encrypted/decrypted in steps 4, 6. However my browser only really needs (d, D, time range) (and not even D for intermediate CAs). This is bounded, probably < 10x the length of H(c), and usually much shorter than the page content which my browser will presumably decrypt anyway. The metadata could be useful for auditing CAs to keep them honest, but that information could be provided separately by the CA (eg written to this append only log).

Answer 1

Your main question is:

Problems with H can weaken the scheme; this is why people stopped using MD5 and are moving away from SHA1. So why not just skip step 3 and encrypt c directly?

Yes, MD5 can currently be broken in about 2^24.1 guesses (24.1 bits of security). SHA1 currently offers about 80 bits of security against the same attacks. You're claiming that dropping the hash entirely and getting 0 bits of security is somehow an improvement?

---

Your understanding is close, but you seem to be missing a few core concepts.

@LieRyan's answer gives the direct answer: that asymmetric crypto like RSA can only operate on fixed-length input.

---

To expand on that, you said:

[the certificate is] usually much shorter than the page content which my browser will presumably decrypt anyway.

You are mixing together a whole bunch of different misconceptions here and comparing apples to oranges.

1. What you are describing with "encrypting the hash" is called an RSA signature. I'm squeemish about even calling it "encrypting the hash" because technically you are decrypting the hash using the decryption key.

2. In practice real Certificate Authorities use Digital Signature Algorithm (DSA) or Elliptic Curve DSA which are based on completely different math, and can definitely not be described as "encrypting the hash".

3. Comparing the running times of "decrypting the hash" (aka "verifying the signature") with the running time of decrypting the content of the web page is apples and oranges because the signature is done with an asymmetric crypto (RSA or Elliptic Curve Cryptography (ECC)), which as @LieRyan said, can only encrypt a single fixed-length block, whereas the content of the web page is encrypted with symmetric cryto (usually AES) which is designed to encrypt / decrypt bulk data very quickly.

---

Ignoring all of the above, there's still a good answer to the question:

So why not just skip step 3 and encrypt c directly?

Because this would be much easier for an attacker to spoof. You are proposing that the webserver provide an encrypted version of their certificate that I can decrypt with the CA's public key. As an attacker I can change a byte of the ciphertext, decrypt it with the CA's public key and see what it says, repeat several billion times until I have what appears to be a legitimate certificate from that CA claiming that I am the owner of the website (ie the public key is one that I own).

Adding in a hash to the process stops that kind of attack because you've also got to check what the hash pre-image of the modified ciphertext is, and try again if it doesn't match. By adding a hash step, we've cranked up the cost of performing this attack from "a couple months on a laptop and ~$10,000 in electricity" to "centuries on a supercomputer and a power-plant to size of the sun".

(I'm only slightly exaggerating - assuming we could do single-electron computations, just building a counter from 0 to 2^256 would require energy equivalent to half the matter in the Milky Way galaxy).

Answer 2

The main reason for this is that the asymmetric encryption algorithm used in the signing (RSA) cannot be used to encrypt large amount of data and it is extremely slow. In particular, RSA cannot encrypt data that is larger than its key size:

RSA, as defined by PKCS#1, encrypts "messages" of limited size. With the commonly used "v1.5 padding" and a 2048-bit RSA key, the maximum size of data which can be encrypted with RSA is 245 bytes. No more.

The bulk of the data encrypted when using asymmetric encryption is actually encrypted using a symmetric encryption, such as AES, with randomly generated key that is then encrypted using RSA and sent together with the data. This is how TLS, PGP, S/MIME, and most other PKI-based encryption systems work.

A PKI Certificate usually contains more data than what one can fit in the RSA size limit because a Certificate contains an RSA public key, which is usually of the same size as the CA's own RSA key. So we need a way to reduce the size of the encrypted data, while still faithfully representing the entire data. Thus, the use of hashing. The hash can then be encrypted using RSA directly, instead of using the RSA+AES method.

If we insist the entire certificate to be signed using plain RSA, then the CA would only be able to sign certificates whose key length is strictly shorter than the CA's key. And each step of intermediate CA's would only be able to sign consecutively smaller keys.

The metadata could be useful for auditing CAs to keep them honest

The metadata isn't actually just used to keep CA honest. The metadata in a Certificate also encodes:

1. the certificate purpose (code signing certificate, S/MIME certificate, client certificate, server certificate),
2. identifying information about the key owner that the CA were able to verify (legal name, organization identifier, organization's address and legal jurisdiction), this should be used by the peer to decide whether they are communicating with the right entity
3. how to find the certificate revocation list or OCSP responder, and
4. the process that the CA used to verify the certificate, which represents the strength of the attestation (EV, OV, or DV).

Some information like CRL/OCSP cannot be safely communicated in a side channel, as that would defeat the purpose of the field.

Answer 3

Because asymmetric (aka public key) encryption is SLOW... Literally thousands of times slower than symmetric encryption. It's faster to just encrypt a small amount of data (the hash) than a large amount of data.