BYU logo Computer Science
CS 465 Introduction to Security and Privacy

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

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.

hybrid encryption
  • 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.

digital signatures
  • 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 vs encryption
  • 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

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 rsa crate 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 its pkcs1v15 feature.

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> and pss::VerifyingKey<Sha256>)
  • public keys in PEM format (to_public_key_pem and from_public_key_pem)

These are the same calls the updated Encrypted Communication project uses.