Lecture 10: Cryptography 3

목차

 

Digital Signatures

Digital signature: Alex wants to send a message and proves that the message came from him

 

 

Goals for a Digital Signature

Authenticity (진위)

- Binds an identity (signer) to a message

- Provides assurance of the signer

 

Unforgeability (위조 불가능성)

- An attacker cannot forge a signature for a different identity

 

Non-repudiation (부인 방지)

- Signer cannot deny having signed the message

 

Integrity (진실성)

- An attacker cannot take a signature by George for a message and create a signature by George for a different message

 

 

Digital Signatures in practice

Use symmetric key encryption

- requires previous secure communication

- only works with single recipient

 

Can we use public key encryption? --> yes (how we make digital signatures)

 

 

Digital Signature with Public-Key Encryption

In a public-key cryptosystem (e.g. RSA), we can ofter reverse the order of encryption and decryption

E_PK (D_SK (M)) = M = D_SK (E_PK (M))

 

Alex "decrypts" plaintext message M with the secret key and obtains a digital signature on M

sign (M, SK) { 

  return S = D_SK (M)

}

 

Knowing Alex's public key, PK, Harm can verify the validity of signature S on M

Harm "encrypts" signature S with PK, and checks if the result is message M

verify(M, S, PK) {

  return (M == E_PK (S) )

}

 

 

 

Signing Hashes

Basic method for public-key digital signatures

- Signature as long as the message

- Slow public-key encryption/decryption

 

Preferred method

- Sign a cryptographic hash of the message

- Hash is short and fast to compute

 

Sign: S = D_SK (h(M))

 

Verify: h(M) == E_PK(S)

 

Security of signing hash

- Security of digital signature

- Collision resistance of hash function

 

 

Question

 

답: B (decrypt the hashed message)

 

 

 

Question

 

답 : D (None of the above)

 

George cannot use method A since he does not have the private key. Also, it's unclear what message M would be in this method.

Methods B and C assure George that he is interacting with a party who has possession of the private key corresponding to the posted public key. However, they do not prove this party is Alex.

 

 

Send a message securely

Alex wants to send a message that only Harm can read and that only he can have sent.

Requirements:

- Confidentiality of all communication

- Harm understands he is communicating with Alex

 

Message M needs to be encrypted and digitally signed

Active adversary can eavesdrop and modify messages

 

Adversary knows:

- PK_Alex

- PK_Harm

 

 

Encrypt then Sign

 

 

Attack:

- Lilika replaces S with her signature S' on Cs, and forwards (C, S') to Harm

- Harm now thinks he is communicating with Lilika

- Lilika can then forward Harm's response (intended for Lilika) to Alex

 

This can be dangerous:

- during a transaction

- Authentication protocol

 

To fix it, sign then encrypt.

 

 

Sign then Encrypt

 

 

Relying on Public Keys

The verifier of a signature must be assured: the public key corresponds to the correct party

The signer should not be able to deny the association with the public key

A trusted party could keep and publish pairs (identity, public key)

- e.g. government, private organizations

What isf the private key is compromised(stolen)?

- Need for key revocation (폐지) mechanism

 

 

MAC

Message Authentication Codes (MACs)

Similar to Digital Signatures, but symmetric

- Therefore does not provide non-repudiation (부인 방지) (anyone who can verify the message can also sign it)

MAC provides a guarantee that a message came from a certain sender and has not been changed.

 

 

MAC Properties

Unforgeability (위조 불가능성)

- Even after seeing many MAC-message pairs, an attacker cannot produce a valid MAC for a new message

 

Integrity (진실성)

- If the MAC or the message is altered, the recipient can detect it

 

 

Implementing MACs

Block Ciphers

CBC-MAC

- Using a block cipher in CBC mode, encrypt a message and use the last cipher block as a MAC

- requires some tweaks. You must:

→ fix the IV (Initialization Vector)

→ prepend each message with its length (if an attacker sees a lot of messages, then can generate a longer message?)

 

 

Cryptographic Hash Functions

HMAC

- Use hash function and a shared secret

Theoretical construction: H(M | | K)

- In practice: 

→ Length extension attacks for some hash function

 

 

MAC then Encrypt (MtE)

E (Message || MAC(Message))

 

MtE was used by TLS (although with special padding schemes)

Does not provide integrity of ciphertext, only plaintext

Not proven to be secure in general case

 

 

MAC and Encrypt (M&E)

(E(Message), MAC(Message)

Can leak message equality even if the encryption does not

Not proven to be secure (MACs do not give confidentiality)

 

 

Encrypt then MAC (EtM)

(E (Message), MAC(E(Message))

Integrity guarantee on both ciphertext and plaintext

Generally recommended order of operations

 

 

 

Key Exchange

Diffie Hellman Key Exchange

 

Vulnerable to man-in-the middle attack (can capture X and not let Harm see it)

*DH key exchange is prone to man in the middle attack, because it does not provide authentication of participating parties.

 

Man-In-The-Middle Attack

 

They both think they agreed on the key

Solution: Alex and Harm digitally sign X and Y respectively. Requires each to know the public key of the other.

 

 

 

 

Modular logarithm is hard: No efficient algorithm is known to compute x given y

Diffie Hellman is built upon this

 

 

 

Diffie Hellman Key Exchange

g and p are public parameters 

 

 

 

Merkle Trees

Collision-Resistant Hash Functions

It is hard to find a pair of plaintexts P and Q such that h(Q) = h(P)

 

 

Merkle Trees

- Hash Tree

- Prove membership

- Prove append-only

 

 

 

Proof of Membership

Alex stores a Merkle Tree and gives Harm H_root.

Can Alex prove to Harm that x4 is one of the elements of the Merkle Tree?

Provide the path + siblings → Authentication path

 

 

 

 

 

Applications: Secure Cloud Storage

Problem: File integrity

Alex stores his fiels in a cloud server managed by Harm

Alex later receives the files

What if Harm tampered with the files?

 

Solution:

Alex computes the cryptographic hash of each file and stores them locally

Alex checks the cryptographic hashes of the retrieved files against the stored ones

This requires Alex to store one hash per file

 

Better solution:

Alex computes a Merkle tree over his elements and stores H_root locally

When requesting element x_i, Alex also requests the authentication path

Alex verifies that the authentication path is correct and matches his root H_root.

 

 

Application: Certificate Transparency Logs

Web certificates

- A certificate that proves the identity of a website

 

Certificate Authority (CA)

- Trusted entity

- Verifies identity of website

- Issues certificates

 

Users trust that ing.com belongs to ING if there is a signed certificate because we trust that the CA verified ING's identity.

 

Given a certificate, how can we tell if it's corrupted or not? 

→ Distributed public logs of certifiactes 

 The log is an ever growing Merkle Tree

Goal: Ensure transparency

→ Everyone sees the same certificates, both the user and the certificate owner

 

 

 

In summary: 

Given a certificate, how can we tell if it's corrupted or not?

Transparency

→ All valid certificates are publicly available

→ Invalid certificates can be quickly detected and revoked.