Chapter 2 - Symmetric Encryption

ไปทวนเรื่องของ Definition มาให้ดี ๆ

What is Cryptography?

Definitions

American Heritage Dictionary:
- "The art or process of writing in or deciphering secret code"
- deciphering ≠ enciphering
Webster Dictionary:
- "The science or study the techniques of secret writing"
Technical Definition:
- A way to transform data into an unintelligible form
- The process is reversible with no data loss
- Usually one-to-one mapping: plaintext $\xleftrightarrow{\text{encryption/decryption}}$ ciphertext

Think of cryptography like a lockbox: you put your message in, lock it with a key, and only someone with the right key can unlock and read it.

Cryptology Branches

Cryptology: The study of techniques for ensuring the secrecy and authenticity of information

Two main branches:

Cryptography (ศาสตร์การเข้ารหัส):
- Study of how to design encryption algorithms
Cryptanalysis:
- Study of how to break encryption algorithms

Cryptography Purpose

A study of encryption algorithms used for encrypting and decrypting messages
Allows users to transmit secret information (ciphertext) over unsecured networks

The Encryption Process

Encryption = Key + Algorithm

Plaintext → [Encryption] → Ciphertext → [Decryption] → Plaintext
                ↑                           ↑
           Shared secret key        Shared secret key

The encryption process is like sending a locked safe through the mail - even if someone intercepts it, they can't open it without the key.

Cryptography Terminology

Key Terms

Plaintext: Message in a clear form that can be read
Ciphertext: Message in an unreadable form
Encryption: Changing plaintext to ciphertext
Decryption: Changing ciphertext back to plaintext

         ┌─────────┐
         │Plaintext│
         └────┬────┘
              │
         ┌────▼────┐         ┌─────┐
         │ Encrypt │◄────────│ key │
         └────┬────┘         └─────┘
              │                 │
         ┌────▼────┐            │
         │CipherTxt│            │
         └────┬────┘            │
              │              ┌──▼──┐
         ┌────▼────┐         │ key │
         │ Decrypt │◄────────┴─────┘
         └────┬────┘
              │
         ┌────▼────┐
         │Plaintext│
         └─────────┘

Secret Writing Examples

Example 1: Hidden Message in Appraisal

The HR manager received this appraisal report:

"Bob, my assistant programmer, can always be found
working hard at his desk. He works independently, without
wasting company time talking to colleagues. Bob never
thinks twice about helping fellow employees, and always
finishes given assignments on time. Often he takes extended
measures to complete his work, sometimes skipping coffee
breaks. Bob is a dedicated individual who has absolutely no
vanity in spite of his high accomplishments and profound
knowledge in his field. I firmly believe that Bob can be
classed as a valuable employee, the type which cannot be
dispensed with. Consequently, I duly recommend that Bob be
promoted to executive management, and a proposal will be
executed as soon as possible."

Later that day, addendum:
"Bob was standing over my shoulder while I wrote the report sent to you earlier today. Kindly re-read ONLY the odd numbered lines."

This is an example of steganography - hiding a message within another message. Reading only lines 1, 3, 5, 7, 9, 11, 13 reveals the true message!

Example 2: Hidden Message Letter

Hidden message in highlighted text:
"your package ready Friday 21st room three destroy this immediately"

Steganography

Definition: Method to conceal a file or message within another file, message, image or video

Least Significant Bits (LSB) Method

An image file contains a binary representation of the color or light intensity of each pixel.
To do steganography, change the least significant bit of the image to be the information we want to hide.

Example:

Original pixel RGB values:
R202 G212 B75  → R203 G113 B75
R198 G99 B59   → R198 G98 B58
R209 G124 B65  → R208 G126 B67
...

Think of LSB steganography like changing a few grains of sand on a beach - the overall appearance stays the same, but the details contain hidden information.

Visual Comparison

JPEG file without embedded text vs JPEG file with embedded text
The images look identical to the human eye!

Another Steganography Method

Encoding message on an image using position:

Secret Data: H J K L M D A B C P F G E I

Carrier: Grid numbered 1-72

Encoding: Each letter mapped to specific grid positions
Result: Message hidden in carrier image

Cryptographic Algorithms

Key Concepts

Mathematical functions that work with a key
Security of data relies on:
- Strength of the algorithm
- Secrecy of the key

Important Principles

Usually, the key is kept secret
But, the encryption algorithm is known publicly (Kerckhoffs's principle)
The same plaintext data is encrypted into different ciphertext with different keys

\text{Enc(M1,K)}=\text{CT1}

\text{Enc(M1,K2)}=\text{CTx}

Like a lock and key system: everyone knows how the lock works, but only the person with the right key can open it.

What is Encryption Used For?

Primary Uses

Prevent eavesdropping
- Must have a secure channel for key exchange
- เวลาจะส่งข้อความ แล้วให้อีกฝ่ายอ่านได้ เราก็ต้องส่ง Key ไปให้ถูกมะ เราก็มี techinque ที่จะ encrypt key อีกทีนะ
Secure storage
- I have to remember my key
Authentication
- Challenge/Response – verify who sends and who receives
Integrity check
- Encrypt the checksum of the message

How Cryptography Provides Security

Five Security Services

Confidentiality
- Allow only authorized users to access information
Authentication
- Verify who the sender was and trust the sender is who they claim to be
Integrity
- Trust the information has not been altered
Non-repudiation
- Ensure that sender or receiver cannot deny that a message was sent or received
Access control
- Restrict availability to information

Classification of Cryptographic Systems

Classified according to three dimensions:

1. Type of Operations Used

Substitution: Replace characters with other characters
Transposition (Permutation): Rearrange the order of characters
Product system: Combination of both methods

2. Number of Keys Used

Symmetric/single-key/secret-key/conventional encryption
- Symmetric Encryption - we use the same key to both encrypt and decrypt
Asymmetric/two-key/public-key encryption
- Each user we have both public key and private key (key-pair)

3. Way Plaintext is Processed

Block cipher: Process 1 block at a time
Stream cipher: Process the input elements continuously

Symmetric vs. Asymmetric Encryption

(a) Symmetric Cryptosystem

Plaintext → [Encryption] → Ciphertext → [Decryption] → Original Plaintext
                ↑                           ↑
               Key ←────────────────────────┘
           (Same key for both)

Easy to use
Faster
Example: AES

(b) Asymmetric Cryptosystem

Plaintext → [Encryption] → Ciphertext → [Decryption] → Original Plaintext
              ↑                             ↑
        Encryption Key              Decryption Key
        (Different keys)

Example: RSA, Electric curve

เราจะไม่พูดว่าอันไหนปลอดภัยกว่า แต่จริง ๆ แล้ว AES ยังไม่สามารถ Attack ได้นะ แต่ RSA 5-6 ปีก็ crack ได้ละ

Symmetric Encryption

Goal: Confidentiality

Process Flow

Sender                                              Recipient
  │                                                     │
  ├─ Plaintext                                         │
  │      ↓                                             │
  ├─ [Encrypt] ←── Shared secret key ───→ [Decrypt]   │
  │      ↓                                      ↓      │
  └─ Ciphertext ──────────────────────→   Plaintext ──┘

Detailed Components

Sender Side:

Plaintext input (X)
Encryption algorithm (e.g., AES)
Secret key shared by sender and recipient (K)
Output: Y = E[K,X] (Transmitted ciphertext)

Recipient Side:

Transmitted ciphertext (Y)
Decryption algorithm (reverse of encryption)
Same secret key (K)
Output: X = D[K,Y] (Plaintext output)

Symmetric Encryption Methods

Classical Methods

Focus on confidentiality of sending messages

Substitution: One letter is exchanged for another
Transposition: The order of letters is rearranged
Product system: Combination of both methods

Modern Methods

Provide more features than classical methods:

Authenticity
Anonymity
Integrity

Examples:

Data Encryption Standard (DES) – Broken
Advanced Encryption Standard (AES) – Current standard

Symmetric Encryption: Substitution vs. Transposition

Substitution Example

Mapping table:
a b c d e f g
g b c d 6 @ a

message → w688ga6

Transposition Example

หรือจะเรียก Transposition ว่า Permutation

Mapping table:
0 1 2 3 4 5 6
3 0 2 1 5 4 6

message → essmgae

Substitution changes what the letters are (like replacing A with Z), while transposition changes where the letters are (like rearranging "cat" to "act").

Symmetric Encryption: Substitution - Caesar Cipher

How It Works

Replace each character with a number:
- A=0, B=1, C=2, ..., X=23, Y=24, Z=25
Add the key value to each number (e.g., key=3)
Convert back to a character corresponding to that number
Note: No transformation for characters not in the mapping list

Mathematical Formula

Encryption: $\boxed{C_i = (P_i + 3) \bmod 26}$
Decryption: $\boxed{P_i = (C_i - 3) \bmod 26}$

Where:

$C_i$ = ciphertext character
$P_i$ = plaintext character

Caesar Cipher with Key = 13 (ROT13)

Shift of 13 positions:

A  B  C  D  E  F  G  H  I  J  K  L  M
↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓
N  O  P  Q  R  S  T  U  V  W  X  Y  Z

Example:
HELLO → URYYB

Caesar Cipher Variations

General Caesar Cipher:
$\boxed{C_i = E(P_i, K) = (P_i + K) \bmod 26}$

Variations:

Multiplicative: $C_i = E(P_i, K) = (n \cdot P_i + K) \bmod 26$
Reflective: $C_i = E(P_i, K) = (n(26 - P_i) + K) \bmod 26$
Quadratic: $C_i = E(P_i, K) = (a \cdot P_i^2 + b \cdot P_i + K) \bmod 26$

Where:

$K$ = key of encryption
All possible transformations = $26! \approx 4 \times 10^{26}$

Exercise 1

Find the ciphertext of "Thammasat" using Caesar Cipher given that:
$C_i = (P_i + 3) \bmod 26$

Cryptanalysis of Caesar Cipher

Patterns of Frequency Distribution

Weakness: Character frequency patterns remain the same!

In English, 'E' is the most common letter
After Caesar cipher, the most common letter in ciphertext reveals the shift

Result: Cryptanalyst can use frequency analysis to break encryption without searching $26!$ combinations

If you shift every letter by 3, 'E' becomes 'H'. If 'H' appears most often in your ciphertext, you know the shift is probably 3!

Symmetric Encryption: Polyalphabetic Substitutions

Purpose

To flatten the frequency distribution of alphabets using multiple substitution functions

Vigenère Cipher

A collection of 26 permutations
Uses a 26 × 26 matrix
All letters appear in each row and column

How it works:

The key is a sequence of letters
A plaintext letter is the index to a row
A key letter is the index to a column
The intersection gives the ciphertext letter

Example:

Plaintext = THAMMASAT
Key = SIIT (repeated)

Vigenère Cipher Table

The Modern Vigenère Tableau

    a b c d e f g h i j k l m n o p q r s t u v w x y z
a   A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
b   B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
c   C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
d   D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
e   E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
f   F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
g   G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
h   H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
i   I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
j   J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
k   K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
l   L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
m   M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
n   N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
o   O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
p   P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
q   Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
r   R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
s   S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
t   T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
u   U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
v   V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
w   W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
x   X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
y   Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
z   Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

"Perfect" Substitutions

Characteristics

Use random distribution for many alphabets
No predictable pattern for the choice of an alphabet
A perfect key: an unlimited, non-repeating series of numbers

Result

The repeated plaintext would not be encrypted the same way twice
The duplication of two ciphertext letters is almost accidental

Some Efforts

One-time pad
Vernam Cipher

One-Time Pad

Concept

Using a large non-repeating set of keys having the same length as the message
The key is used only once

Three Problems

How to generate the key & have safe distribution of keys
Need absolute synchronization between sender and receiver
Need unlimited number of keys

Solution Approach

Using time synchronization
Key is changing every minute

One-Time Pad (Formal)

Let $Z_m = \{0, 1, \ldots, m-1\}$ be the alphabet.

Components:

Plaintext space = Ciphertext space = Key space = $(Z_m)^n$
The key is chosen uniformly randomly

Given:

Plaintext: $X = (x_1, x_2, \ldots, x_n)$
Key: $K = (k_1, k_2, \ldots, k_n)$
Ciphertext: $Y = (y_1, y_2, \ldots, y_n)$

Operations:

Encryption: $\boxed{e_K(X) = (x_1+k_1, x_2+k_2, \ldots, x_n+k_n) \bmod m}$
Decryption: $\boxed{d_K(Y) = (y_1-k_1, y_2-k_2, \ldots, y_n-k_n) \bmod m}$

The Binary Version of One-Time Pad

Simplified for binary:

Plaintext space = Ciphertext space = Keyspace = $\{0,1\}^n$
Key is chosen randomly

Example:

Plaintext:    11011011
Key:          01101001
            ⊕ (XOR)
Ciphertext:   10110010

XOR Truth Table:

A	B	A ⊕ B
0	0	0
0	1	1
1	0	1
1	1	0

Vernam Cipher

Use a long non-repeating sequence of numbers to be combined with the plaintext

Example

Plaintext	V	E	R	N	A	M
Numeric Equivalent	21	04	17	13	0	12
+ Random number	76	48	16	82	44	03
= Sum	97	52	33	95	44	15
= mod 26	19	0	7	17	18	15
Ciphertext	T	A	H	R	S	P

Why Vernam Cipher is Called "One-Time Pad"

It is an unbreakable cipher when:

The key is exactly the same length as the message
The key is used one time only
The key is never used again for any other message

Think of it like a scratch-off lottery ticket - once you've used it, you throw it away and never use it again.

Key Randomness in One-Time Pad

Question: What if the key is not chosen randomly?

For example, if texts from a book/dictionary are used as keys:

This is NOT One-Time Pad anymore
This does NOT have perfect secrecy
This CAN be broken

Why?

Natural language has patterns and redundancies
These patterns can be exploited by cryptanalysts

Key Reuse Problem

The key in One-Time Pad should NEVER be reused.

If it is reused:

It becomes "Two-Time Pad"
It is insecure!

Why? The attacker can learn and study the relationship between ciphertexts

If two messages $M_1$ and $M_2$ are encrypted with the same key $K$ :
$C_1 = M_1 \oplus K$
$C_2 = M_2 \oplus K$
Then:
$C_1 \oplus C_2 = (M_1 \oplus K) \oplus (M_2 \oplus K) = M_1 \oplus M_2$

The key cancels out, exposing patterns between the two messages!

Usage of One-Time Pad

The Challenge

To use one-time pad, one must have keys as long as the messages.

To send messages totaling certain size, sender and receiver must agree on a shared secret key of that size.

Typically by sending the key over a secure channel

The Paradox

Question: Can't one use the channel for sending the key to send the messages instead?

Answer: Not necessarily! The secure channel may have different properties.

Why is OTP Still Useful?

The secure channel for distributing keys may have the property that:

Keys can be leaked
BUT such leakage will be detected

Example:

Quantum cryptography allows key distribution where any eavesdropping can be detected

Like a tamper-evident envelope - if someone tries to peek at the key, you'll know about it!

Symmetric Encryption: Transposition (Permutation)

Goal: Rearrange letters in a message to break established patterns

Columnar Transpositions

Rearrangement of plaintext characters into columns
May use 'x' to fill in any short column

Example:

Message: "this is a message to show"

T H I S I
S A M E S
S A G E T
O S H O W

Reading column by column:

TSSO HAAS IMGH SEEO ISTW

Disadvantages

Delay since all characters must be received before decoding
- Needs to get complete ciphertext, before decrypting it (not on the fly)

Columnar Transposition Examples

Example 1: Simple Column Rearrangement

Original:    d b a c
Key order:   2 3 4 1

Result:      Rearrange columns according to key

Example 2: With Message

Message: JAMESBONDNEEDSBACKUP
Code: JEONDAUASNESCPMBDEBK

Grid arrangement (key order determines column reading):
J  E  O  N  D  A  U
A  S  N  E  S  C  P
M  B  D  E  B  K

Reading in key order gives the ciphertext.

Symmetric Encryption: Product Cipher

Concept

Objective: Increase cipher strength
Method: Combine two techniques of basic ciphers
Have many steps and perform one after another

Important Note

However, two ciphers in combination are not always stronger than individual cipher!

Like mixing two locks - sometimes it's more secure, but if one lock is weak, the whole thing might still be vulnerable.

Shannon's Characteristics of Good Ciphers

Claude Shannon (Father of Information Theory)

Six Characteristics

The amount of secrecy needed should determine the amount of labor appropriate for encryption/decryption
- The degree of secrecy ก็ขึ้นอยู่กับว่าเราต้องใช้คน/resource มากแค่ไหนในการ encrypt/decrypt
- ใช้ทั้งหมดที่มีในชีวิตในการ decrypt/encrypt - Aj. Somchart (Ohm)
Set of keys and algorithm should be free from complexity
Implementation should be simple
Should have no error propagation that causes the corruption of further message
- Error Propagation
- M1, M2, …, Mn → CT1, CT2, …, CTn
- Problem with M1 or CT1, it should not be propagated with M2, and so on.
Size of ciphertext should be no longer than that of plaintext
- Why? Longer ciphertext means more data to transmit and store (You give more information to the attacker!)
The algorithm should be mathematically sound and provably secure

Security of Encryption

1. Unconditionally Secure Algorithm

No matter how much computer power or time is available, the cipher cannot be broken
The ciphertext provides insufficient information to uniquely determine the corresponding plaintext
Only one method is unconditionally secure: One-Time Pad

ไม่ว่าจะใช้ supercomputer เริ่ดแค่ไหน ก็ไม่สามารถแก้ ciphertext นี้ได้ ถ้าใช้ one-time pad

2. Computationally Secure Algorithm

Given limited computing resources, the cipher cannot be broken
Encryption is computationally secure if:
- Cost of breaking cipher exceeds information value, OR
- Time required to break cipher exceeds the useful lifetime of the information

Reality:

Usually very difficult to estimate the amount of effort required to break
Can estimate time/cost of a brute-force attack

แตกได้ในทางทฤษฎี (crack ได้)
แต่ ในทางปฏิบัติ = ไม่คุ้ม / ทำไม่ได้จริง

Cryptanalysis: Breaking the Key

Attack Types

Brute-Force Attack

Try all possible keys
Guaranteed to work eventually, but may be infeasible

Cryptanalysis Attacks

Know something about the system:

Ciphertext only – The hardest one
Known plaintext – Know some plaintext-cipher pairs
Chosen plaintext – Get own plaintext-cipher pairs
Chosen ciphertext – Not easy to find

Types of Cryptanalytic Attacks

Type of Attack	Information Known to Cryptanalyst
Ciphertext only	• Encryption algorithm • Ciphertext to be decoded
Known plaintext	• Encryption algorithm • Ciphertext to be decoded • Plaintext-ciphertext pairs generated by the secret key
Chosen plaintext	• Encryption algorithm • Ciphertext to be decoded • Plaintext chosen by cryptanalyst and corresponding ciphertext generated by the secret key
Chosen ciphertext	• Encryption algorithm • Ciphertext to be decoded • Ciphertext chosen by cryptanalyst, corresponding plaintext generated by the secret key

Ciphertext-Only Attack

Scenario:

Eve (attacker) can only observe the ciphertext
Must deduce plaintext or key from ciphertext alone

Alice                   Eve                     Bob
  │                      │                       │
  ├─ Plaintext          │                       │
  │      ↓              │                       │
  ├─ [Encrypt]          │                       │
  │      ↓              │                       │
  └─ Ciphertext ───────►├─ [Analyze] ───────►  │
                         │      ↓               │
                         └── Plaintext          └─ Ciphertext
                             (attempt)              ↓
                                               [Decrypt]
                                                   ↓
                                               Plaintext

This is the weakest attack model from the attacker's perspective - like trying to decode a message with no hints at all.

Known-Plaintext Attack (KPA)

Definition: A cryptanalytic attack model where the attacker knows:

One or more plaintext messages, and
Their corresponding ciphertexts
Both encrypted under the same secret key

Goal: Recover the secret key or decrypt other ciphertexts encrypted with that key

Alice                   Eve                           Bob
  │                      │                             │
  ├─ Plaintext          │   ┌──────────────┐         │
  │      ↓              │   │Previous pair:│         │
  ├─ [Encrypt]          │   │Plaintext ←→ │         │
  │      ↓              │   │ Ciphertext  │         │
  └─ Ciphertext ───────►├───┴──────────────┘         │
                         │      ↓                     │
                         ├─ [Analyze]                 │
                         │      ↓                     │
                         └── Plaintext                └─ Ciphertext
                             (attempt)                    ↓
                                                     [Decrypt]
                                                         ↓
                                                     Plaintext

Chosen-Plaintext Attack (CPA)

Attacker know the source

In this attack:

The attacker/cryptanalyst can select or choose the plaintext
The plaintext is sent through the encryption algorithm
The attacker observes the resulting ciphertext

This is an active model where the attacker actually gets to choose the plaintext and do the encryption.

     ┌──────────────────────┐
     │Pair created from     │
Eve ──┤chosen plaintext      │
     │Plaintext → Ciphertext│
     └──────────────────────┘
             ↓
Alice                   Eve                           Bob
  │                      │                             │
  ├─ Ciphertext         │                             │
  │      ↓              │                             │
  │                     ├─ [Analyze]                  │
  │                     │      ↓                      │
  │                     └── Plaintext                 └─ Ciphertext
  │                         (attempt)                     ↓
  │                                                   [Decrypt]
  │                                                       ↓
  └────────────────────────────────────────────────► Plaintext

Formal Definition - CPA

Let:

$E_K(\cdot)$ be an encryption algorithm with secret key $K$

In a chosen-plaintext attack, the adversary is allowed to:

Query $E_K(P)$ for any plaintext $P$ of their choice

The attacker's goal is to:

recover $K$ , or
distinguish encryptions of chosen messages, or
break semantic security

Simple Example: Caesar Cipher (Broken under CPA)

Encryption:
$C_i = (P_i + k) \bmod 26$
Attacker chooses:
$P = A$
Receives:
$C = D$
Conclusion:
Since $A = 0$ and $D = 3$ :
$k = 3$
The key is recovered in one query!

Chosen-Ciphertext Attack (CCA)

In this attack:

The attacker can both encrypt and decrypt
They can select plaintext, encrypt it, observe the ciphertext
Then reverse the entire process

Note: The cryptanalyst is trying to decipher the algorithm and secret key, not necessarily just find the plaintext.

Alice                   Eve                           Bob
  │                      │   ┌──────────────────┐    │
  ├─ Ciphertext         │   │Pair created from:│    │
  │      ↓              │   │Chosen ciphertext │    │
  │                     ├───┤Ciphertext        │    │
  │                     │   │     ↓            │    │
  └─────────────────────┼───┤[Decrypt]         │    │
                        │   │     ↓            │    │
                        │   │Plaintext         │    │
                        │   └──────────────────┘    │
                        │      ↓                     └─ Ciphertext
                        ├─ [Analyze]                     ↓
                        │      ↓                     [Decrypt]
                        └── Plaintext                    ↓
                                                     Plaintext

CCA - Chosen-Ciphertext Attack

Overview

A Chosen-Ciphertext Attack (CCA) is the strongest and most realistic attack model in symmetric and public-key cryptography.

In a CCA, the attacker can actively submit ciphertexts of their choice to a decryption oracle and observe the corresponding plaintexts—with one critical restriction in the formal game.

Attacker Capabilities

In a CCA, the attacker can:

Choose plaintexts and see their encryptions (CPA power), and
Choose ciphertexts and see their decryptions

Goals

Recover the secret key, or
Distinguish which plaintext was encrypted

What Is an Oracle?

In cryptography, an oracle is an abstract, black-box interface that answers specific queries for an attacker or algorithm, as if a perfect service were available.

Think of an oracle like a magic box: you can ask it questions (like "decrypt this"), and it gives you answers, but you can't see how it works inside.

Formal Security Notions - CCA

IND-CCA (Indistinguishability under CCA)

Game outline:

Attacker can query:
- Encryption oracle $E_K(\cdot)$
- Decryption oracle $D_K(\cdot)$
Attacker submits two messages $m_0, m_1$
Challenger returns:
$c^{*} = E_K(m_b), \quad b \in \{0, 1\}$
Attacker may continue decryption queries except on $c^{*}$
Attacker guesses $b$

A scheme is IND-CCA secure if the attacker's advantage is negligible.

Idea: ถ้าเราเอาไปผ่านหลาย ๆ algorithm ในการ encrypt มันมีผลยังไงใน math ของเวลาในการ crack

Step 3 — Challenge Ciphertext Generation

What happens:

The attacker submits two plaintexts of equal length:
$m_0, m_1$
The challenger:

Picks a random bit:
$b \leftarrow \{0, 1\}$
Encrypts only one of them:
$c^{*} = E_K(m_b)$
Sends $c^{*}$ to the attacker

What this step means

This is the core challenge:

"Can you tell which plaintext was encrypted?"

The attacker knows:

Both $m_0$ and $m_1$
The encryption algorithm

But does not know:

The key $K$
The random bit $b$

If the attacker can guess $b$ with probability significantly greater than $1/2$ , the scheme is not secure.

Step 4 — Restricted Decryption Queries

What happens:

After receiving $c^{*}$ , the attacker may:

Continue querying the decryption oracle:
$D_K(C)$
⚠️ With one strict restriction:
$C \neq c^{*}$
The attacker is not allowed to decrypt the challenge ciphertext itself.

Why this restriction is necessary

If the attacker could query:
$D_K(c^{*})$
Then:
$D_K(c^{*}) = m_b$
This would trivially reveal which message was encrypted!

The restriction prevents the attacker from simply asking for the answer directly.

Remark on Steps 3 and 4

Step 3 creates a challenge ciphertext encrypting one of two chosen messages.

Step 4 allows the attacker to decrypt any ciphertext except the challenge itself.

This models realistic adaptive attacks while preventing trivial key recovery.

Think of it like a test: you can practice with similar problems (Step 4), but you can't look up the answer to the actual test question (Step 3).

Why Step 4 is the Core of CCA Strength

This step allows attacks like:

Modifying bits of $c^{*}$
Observing accept/reject behavior
Exploiting error messages, padding checks, MAC failures

If any information leaks, the attacker may still infer $m_b$ .

A scheme that survives this is truly robust.

Step 4 Is Where CCA Attacks Happen

Recall Step 4 in IND-CCA:

The adversary may query a decryption oracle on any ciphertext except the challenge ciphertext.

If the decryption algorithm:

Outputs plaintext, or
Leaks any distinguishable information (errors, timing, padding validity)

Then the attacker can adaptively modify ciphertexts and learn information about the challenge.

⚠️ This is exactly how CCA attacks work.

How to Enable Step 4 to be CCA-Resistant?

When authentication is added (e.g., AEAD):