Endong Liu

Stay Hungry, Stay Foolish

9 minute read

UCL Course COMP0133: Distributed Systems and Security LEC-12

Symmetric Encryption (Private Key Encryption)

Definition

The detailed definition of Private Key Encryption in COMP0025 Lecture 3

One Time Pad

Secretly share a truly random bit string \( P \) at sender and receiver

\( Enc: M \oplus P \)

\( Dec: C \oplus P \)

Use bits of \( P \) only once (never use them again)

e.g., \( C_1 = M_1 \oplus P \) and \( C_2 = M_2 \oplus P \) \( \implies \) \( M_1 = C_1 \oplus C_2 \oplus M_2 \)

Block Cipher

Ideas

Divide arbitrary length plaintext into fixed-size blocks (typically 64 or 128 bits)

Block cipher maps each plaintext block to same-length ciphertext block

Naïve Scheme: Electronic Code Book (ECB)

  1. Divide message \( M \) into blocks of cipher’s block size

  2. Simply encrypt each block individually using the cipher

  3. Send each encrypted block to receiver

Insecure: Deterministic Encryption

Repeated blocks in the plaintext \( \implies \) Repeated blocks in ciphertext

Better Scheme: Cipher Block Chaining (CBC)

Make encryptions of successive blocks depend on one another

where Initialization Vector (\( IV \)) known to receiver (use different \( IV \) for different messages)

Message Authentication Codes

Definition

The detailed definition of Message Authentication Codes in COMP0025 Lecture 5

MAC has unforgeablility such that message with MAC is tamper-resistance (not modified)

Use Encrypt-then-MAC to keep confidentiality and interity of plaintext \( m \)

However, replay attacks are still possible (solutions in COMP0025 Lecture 5)

Applications: HMAC

\[H((k \oplus \textit{opad}) \ || \ H((k \oplus \textit{ipad}) \ || \ m))\]

where

\( H \) is a CRHF

\( \textit{opad} \) is 64 repetitions of 0x36

\( \textit{ipad} \) is 64 repetitions of 0x5c

Benefits: Fixed-size output (even for long messages) for efficiency, black box implementation

Asymmetric Encryption (Public Key Encryption)

Definition

The detailed definition of Public Key Encryption in COMP0025 Lecture 7

Public Key \( K \): published for all to see

Private Key \( K^{-1} \): keep in secret

Security

  • Cannot derive plaintext from ciphertext without knowing \( K^{-1} \)

    even knowing the encryption and decryption methods

  • Cannot derive \( K^{-1} \) from \( K \)

    even knowing the encryption and decryption methods

    such that \( K \) can be used to encrypt all messages to the same recipient

Number Theory in Cryptography

The detailed information of Number Theory in Cryptography in COMP0025 Lecture 6

Modular Operation

  • \( (a+b) \ mod \ n = ((a \ mod \ n) + (b \ mod \ n)) \ mod \ n \)

  • \( (a \cdot b) \ mod \ n = ((a \ mod \ n) \cdot (b \ mod \ n)) \ mod \ n \)

Benefits of Modular Operation

  • Limit precision required: fewer precision \( \implies \) faster arithmetic

  • Exist computationally hard problem: Integer Factorization Problem & Discrete Logarithm Problem

  • When \( a \) and \( n \) are relatively prime (coprime),

    modualr inverse \( x \) exists and is unique (can be found by Extended Euclidean Algorithm)

    \[a^{-1} \equiv x \ (mod \ n)\]

Euler’s Theorem

\[a^{\phi(n)} \equiv 1 \ (mod \ n)\]

Fermat’s Liitle Theorem

\[a^{\phi(n)-1} \equiv a^{-1} \ (mod \ n)\]

RSA Encryption

Definition

  1. Choose two large prime numbers \( p \) and \( q \) where \( \lvert p \rvert = \lvert q \rvert \)

  2. Calculate \( n = pq \), and \( \phi(n) = (p-1)(q-1) \)

  3. Choose random value \( e \) where \( e \) and \( \phi(n) \) should be relatively prime

  4. Compute \( d = e^{-1} \ mod \ \phi(n) \)

  5. Public Key \( K=(e,n) \) and Private Key \( K^{-1}=(d,n) \)

  6. \( p \) and \( q \) should be discarded; otherwise, \( d \) can be derived from \( e \)

Process

Encryption

  • Divide message \( m \) into blocks \( m_i \), each shorter than \( n \)

  • Compute ciphertext blocks \( c_i \) with: \( c_i = m_i^e \ mod \ n \)

Decryption

  • Recover plaintext blocks \( m_i \) with: \( m_i = c_i^d \ mod \ n \)

Correctness Proof

This is another proof process that differs from what in COMP0025 Lecture 7

Proof:

\( c_i^d = (m_i^e)^d = m_i^{ed} \)

\( ed \equiv 1 \ (mod \ \phi(n)) \implies ed \equiv 1 \ (mod \ (p-1)(q-1)) \implies \exists \ k \in \mathbb{N}: ed = k(p-1)(q-1)+1 \)

\( \exists \ k_1 = k(q-1)\in \mathbb{N}: ed = k_1(p-1)+1 \)

\( \exists \ k_2 = k(p-1)\in \mathbb{N}: ed = k_2(q-1)+1 \) —– RSA encryption definition

Consider \( p \) condition:

When \( m_i \) and \( p \) is co-prime:

  • \( m_i^{p-1} \ \equiv 1 \ (mod \ p) \) —– Euler’s Theorem

  • \( m_i^{ed} = m_i^{k_1(p-1)+1} = m_i \cdot (m_i^{p-1})^{k_1} \equiv m_i \ (mod \ p) \)

When \( m_i \) and \( p \) is not co-prime:

  • \( m_i^{ed} = 0^{ed} = 0 \equiv m_i \ (mod \ p) \)

therefore, \( m_i^{ed} \equiv m_i \ (mod \ p) \)

similarly, \( m_i^{ed} \equiv m_i \ (mod \ q) \)

\( m_i^{ed} \equiv m_i \ (mod \ p) \implies m_i^{ed} - m_i \equiv 0 \ (mod \ p) \)

\( m_i^{ed} \equiv m_i \ (mod \ q) \implies m_i^{ed} - m_i \equiv 0 \ (mod \ q) \)

because \( p \) and \( q \) are both prime and distinct

\( m_i^{ed} - m_i \equiv 0 \ (mod \ pq) \implies m_i^{ed} - m_i \equiv 0 \ (mod \ n) \implies m_i^{ed} \equiv m_i \ (mod \ n) \)

Therefore*

\( c_i^d = (m_i^e)^d = m_i^{ed} \equiv m_i \ (mod \ n) \)

Misuse of RSA

Small Plaintext Message Set

Textbook RSA is deterministic

Naive Escrow

Company wants employees to encrypt their documents with RSA

To make sure company can decrypt documents after employee fired or dies (business continuity)

Process

  • Company has public key \( K=(e, n) \)

    requires employees to encrypt their documents in \( (e, n) \)

    give to company for storage

  • if employee dies, company decrypts plaintext document

    gives to remaining employee

Attack

Employee E and F cannot access A’s plaintext \( m \)

  • Employee E takes employee A’s ciphertext \( c = m^e \ mod \ n \)

  • Employee E computes \( c’ = c \cdot 2^e \ mod \ n \), escrows \( c’ \) to company

  • After employee E gets fired, company releases \( c’=(c \cdot 2^e)^d \ mod \ n = 2m \) to employee F

    such that employee E can collude with employee F to get \( m \)

Because Textbook RSA is Homomorphic encryption

Adaptive Chosen Ciphertext Attacks

Example: Adaptive Chosen Ciphertext Attack on RSA in SSL 3.0

  • padding plaintext \( m \) using PKCS #1 standard:

    \[0x00 \ | \ 0x02 \ | \ r \ | \ 0x00 \ | \ m\]

    where \( r \) is 8 or more non-zero random bytes

  • SSL decrypts received ciphertext, checks if result in this format and returns “format error” if not

  • When chosen ciphertext accepted by server for million times, attacker knows first two plaintext bytes must be \( 0x00 \) and \( 0x02 \)

Correct Use of RSA

plaintext input to RSA to be all-or-nothing transform of actual message

Properties

  • Randomness

    Unique ciphertext for repeated identical messages

  • Redundancy

    Make most strings invalid ciphertexts

  • Entanglement

    Knowing partial information about input to RSA should reveal nothing about message

  • Invertibility

    Must be able to recover original message when decrypting

Example: Practical Padding for RSA: OAEP+

Digital Signatures with RSA

The detailed definition of Digital Signatures in COMP0025 Lecture 8

Definition

  • Sign

    \( \text{Sign}(K^{-1}, m) \rightarrow {m}_{K^{-1}} \)

  • Verify

    \( \text{Verify}(K, {m}_{K^{-1}}, m) \rightarrow {\textit{true}, \ \textit{false}} \)

Attack

Eve wants to recover \( m \) from \( e \)

  1. Eve chooses random number \( r < n \)

  2. Eve computes \( y = cr^e \ mod \ n \)

  3. Eve asks Alice to sign \( y \)

  4. Alice sends Eve \( y^d \ mod \ n = c^dr^{ed} \ mod \ n = c^dr \ mod \ n \)

  5. Eve computes \( r^{-1} \ mod \ n \), then recovers \( m \) by

\[c^drr^{-1} \ mod \ n = c^d \ mod \ n = (m^e)^d \ mod \ n = (m^{ed}) \ mod \ n \equiv m \ mod \ n\]

Lesson

Don’t sign whole messages presented to you by others

Only Sign Message Hashes with RSA (Full-Domain Hash) since hash reveals nothing about the input message

Costs of Cryptography

Asymmetric Encryption (Public Key Encryption)

is much more expensive than

Symmetric Encryption (Private Key Encryption)

Goal

Mix speed of symmetric key encryption and flexibility of asymmetric-key encryption

Application

Send symmetric key encrypted with asymmetric key whose payload encrypted with symmetric key

You may also enjoy