Public Key Cryptography
Introductions
- introductions of two students
Questions on the readings
The readings today are from Computer Security and the Internet, Chapter 2, sections 2.3, 2.4
Public Key Cryptography
- Each party creates a separate key pair, (public key, private key). These are also called the encryption key and decryption key.
- If Alice knows Bob’s public key, she can encrypt a message using his public
key (eB) and only Bob can decrypt the message using his private key
(dB).
- c = EeB(m)
- m = DdB(c)
- Bob must keep his private key secret, otherwise anybody could decrypt private messages sent to him.
- Standard public key cryptography algorithm is called RSA — provides computational security
- Raw RSA is deterministic: the same message always encrypts the same way. RSA
is always used with a padding scheme that adds randomness and structure.
- For encryption, use RSA-OAEP (from PKCS #1 v2), e.g. with SHA-256.
- For signatures, use RSA-PSS, e.g. with SHA-256.
- The older PKCS #1 v1.5 padding is no longer recommended. Its encryption padding is vulnerable to padding-oracle and timing attacks (see the Marvin attack below). Its signatures are not broken, but PSS is the recommended choice for new designs, and TLS 1.3 uses PSS.
Hybrid Encryption
Usually, we use public key cryptography to bootstrap a shared, symmetric key. This is because encrypting and decrypting with a symmetric key is much faster than encrypting and decrypting with public key cryptography.
- Alice chooses a symmetric key, then encrypts it with Bob’s public key and sends it to him. Now they both have a symmetric key they can use to encrypt and decrypt messages to each other.
- Alice and Bob typically choose a new symmetric key each time they communicate, so we call this a session key.
Digital Signatures
We can also use public key cryptography to implement digital signatures. Here, the private key is used to sign and the public key is used to verify. With RSA, signing resembles encrypting with the private key, and verifying resembles decrypting with the public key.
- Alice signs (encrypts) a message with her private key (sA). Bob can verify (decrypt) the message with Alice’s public key (vA). Here we use (v, s) to represent the (public key, private key).
- Be sure to use separate key pairs for encryption/decryption and signing/verifying.
-
Digital signatures provide:
- data origin authentication — we can verify who signed the message
- data integrity — we can verify whether the message is the same as what was signed
- non repudiation — the signer can’t claim they didn’t sign the message (unless someone stole their private key)
-
Use of public key cryptography by the general public is hard because it requires you to keep your private key safe and to have a reliable way to distribute your public key to others. These are key management issues.
-
A valid signature does not prove freshness: an attacker can replay an old signed message. Protocols prevent this by having the verifier choose a fresh random nonce and checking that the signature covers that nonce, as in the Encrypted Communication project.
Hybrid encryption with integrity
- A digital signature of a hash of the message ensures Bob knows the message came from Alice and that the message hasn’t been altered.
- AES with GCM provides integrity and, assuming only Alice and Bob know the symmetric key, then assures Bob that Alice sent the message.
- Getting all the pieces right is tricky. See Defective Sign & Encrypt in S/MIME, PKCS#7, MOSS, PEM, PGP, and XML. Use TLS where possible.
Extra reading
- The Marvin attack
- Stop using RSA PKCS#1 v1.5 encryption! On the TLS level, only servers that enable RSA encryption are affected. Most modern clients support the use of Elliptic Curve Diffie Hellman, thus disabling ciphersuites that use RSA encryption is the recommended way to fix this vulnerability.
- The Rust
rsacrate had this timing problem before version 0.10 (RUSTSEC-2023-0071). Version 0.10 fixes it by using constant-time arithmetic, and it only offers PKCS #1 v1.5 if you explicitly turn on itspkcs1v15feature.
Class exercises
We are using the Rust Crypto crates.
See the Rust Cryptography repo
for RSA code examples. The
rsa-example uses version 0.10 of the rsa crate (run rustup update to get
Rust 1.98 or newer, as the Rust book uses):
- encryption with OAEP and SHA-256 (
Oaep::<Sha256>) - signatures with PSS and SHA-256 (
pss::SigningKey<Sha256>andpss::VerifyingKey<Sha256>) - public keys in PEM format (
to_public_key_pemandfrom_public_key_pem)
These are the same calls the updated Encrypted Communication project uses.