𝖄𝕺🌎𝕿𝕽𝕺¥

Motivation for Using Operating Modes in Symmetric Encryption#

Symmetric encryption algorithms (such as AES) use the same key for both encryption and decryption. They can only securely encrypt fixed-size data blocks. To encrypt messages of arbitrary length, these basic algorithms need to be applied in specific operating modes.

• A block cipher can encrypt N bits of information. But what about non-multiples of N, variable lengths, or TCP-like streams?
• Operating modes provide different methods for encrypting flexible amounts of data using block ciphers.

! CBC and CTR Satisfy IND-CPA

Deterministic and Integrity?#

Deterministic: The same plaintext block will produce the same ciphertext block.

Integrity: Ensures that data is not tampered with during transmission or storage. CTR mode does not provide integrity because it only offers encryption and does not include a mechanism to verify data integrity.

ECB (Electronic Code Book) Mode:#

The simplest mode for encrypting longer messages using block ciphers, where the message is divided into blocks and encrypted independently. Its main drawback is that it encrypts in the same way (with a fixed key), so the same plaintext block will produce the same ciphertext block (this is deterministic), making it prone to information leakage. Not recommended.

• Padding may be required for the last block.
• Padding needs to be handled carefully to avoid errors. A small error in a block can lead to incorrect decryption of the entire block.
• Encryption can be done in parallel.
• Encryption is deterministic, without integrity.
• Rarely used, except for searchable encryption targeting high-entropy plaintext spaces.

Cracking?#

• Building a codebook makes weak passwords easy to crack.
• If the password remains the same, it can be identified when it appears again, such as permutation.

CBC (Cipher Block Chaining) Mode#

Before encrypting each block (which must be complete blocks, considering padding), it is XORed with the previous ciphertext block. This requires an initialization vector (IV) to start the process. It enhances security but still has potential issues, such as predictable IVs.

• IV must be uniformly random, otherwise it leads to attacks.
• No determinism, no integrity.
• Must be complete blocks, multiples of N, can consider padding, but N too small can cause issues.
• Must use different keys, encrypting ciphertext blocks multiple times with the same key leads to ciphertext block collisions, meaning if Pj is known, Pi can be recovered, as shown below:

CTR (Counter) Mode#

Transforms the encryption algorithm into a stream cipher. It does not directly encrypt the message, but encrypts a counter (with different values assigned) and then XORs the output with the plaintext. This provides high flexibility and parallel processing capability.

• Uses an incrementing counter ctr to generate pseudo-random output blocks (viewing ctr bit string as an integer, addition mod 2^n).
• Can run in parallel.
• Pre-compute encryption masks Ri before knowing the plaintext.
• Fast: Block ciphers are typically slower than dedicated stream cipher designs.
• No Integrity, applies to all stream ciphers.
• Deterministic.
• No padding required, as the last output block rN can be truncated to the exact length pN.
• Usually send ctr as part of the ciphertext, if the decryption process can recover ctr through other means, we can omit ctr.
• Encryption uses Enc, decryption also uses Enc:
• Therefore, no need to implement Dec - in fact, Enc does not need to be reversible!
• Technically, this means that CTR mode can use a pseudo-random function instead of a pseudo-random permutation.

Key Requirements#

Key security requirement: For a fixed key k, all counter values used (across all encryptions) must be different.

• If a counter is repeated, the XOR of the ciphertext blocks will produce the XOR of the plaintext blocks.
• Similar to the problem of reusing a one-time pad/key stream in stream ciphers.

Error Propagation#

Flipping a bit in the ciphertext can cause a corresponding bit flip in the plaintext.

Steps#

Ensure uniqueness of encryption by using different counter (ctr) values, choose one of the following methods:

1. Start ctr from 0 for each encryption, change the key (high cost).
2. Start with a random ctr each time (need to control key usage to avoid collisions).
3. Keep track of the last used ctr value, increment by 1 for the next encryption (requires maintaining state).
4. ctr consists of a fixed-size random number (nonce N) provided by the application and an internal counter, start counting from 0 for each encryption (prevents nonce repetition, limits plaintext size to avoid internal counter overflow). This method is used in GCM mode (as described below).

GCM (Galois/Counter Mode)#

A variant of CTR mode that adds data integrity verification. It is widely used to protect network data, such as in the TLS protocol.

• GCM requires one block cipher operation and one 128-bit multiplication for each encrypted and authenticated data block.
• Deterministic.
• Each block cipher operation can be parallelized.
• Encryption and authentication are independent, allowing software implementations to improve speed through overlapping verification and encryption.

IND-CPA Security of Symmetric Encryption#

IND-CPA is an important standard for considering the security of symmetric encryption algorithms, often achieved by introducing randomness (such as using different initialization vectors IV for each encryption).

Four Elements: KeyGen, Enc, Dec, Correctness#

• KeyGen: Uniformly random.
• Enc: key K + plaintext M → output C
  • Usually random, such as CBC, CTR
  • Later Enc can have additional inputs but must be deterministic.
• Dec: key K + ciphertext C → output M or error
  • Assuming determinism, let the maximum length of encryptable plaintext be L, so M belongs to {0,1}≤L
• Correctness: Holds for all k
• K is key space, M is message space, C is ciphertext space
• Ciphertext is usually longer than plaintext but should be as short as possible to minimize expansion.

INDistinguishability (IND) Security#

This is a security property that means given two different plaintexts, the ciphertext produced by the encryption algorithm should make it impossible for an attacker to determine which ciphertext corresponds to which plaintext (semantic security). Ideally, even if the attacker knows or can choose the plaintext, they should not be able to extract any useful information from the ciphertext.

Chosen Plaintext Attack (CPA)#

This is an attack model where the attacker can choose any number of plaintexts and obtain their corresponding ciphertexts. The attacker's goal is to use this information to break the encryption algorithm, obtain the key, or decrypt other ciphertexts.

Properties#

• IND-CPA security captures information recovery attacks: Any attacker who can recover m from c can be transformed into an attacker who breaks IND-CPA security.
• IND-CPA security captures key recovery attacks: Any attacker who can recover the key k given some key pairs (m, c) can be transformed into an attacker who breaks IND-CPA security.
• IND-CPA security ensures that every bit of the plaintext is hidden.
• It can be proven that if schemes like CBC mode and CTR mode are used, they satisfy IND-CPA security definition if a good block cipher is used.

How to Guess?#

Padding and Padding Oracle Attacks#

Why Padding?#

To ensure that the length of the plaintext matches the fixed block size required by the encryption algorithm and to prevent issues with incomplete lengths in block encryption.

• For CBC mode, padding - encryption - remove padding.
  • But it is vulnerable to attacks, can be combined with MAC for integrity detection of modified ciphertext, MAC needs to be combined with encryption scheme.
• Padding can be random or deterministic.
• Needs to be a bit string that is a multiple of N.
• Should be extensible.

Simple Example of Padding for AES#

For AES algorithm, where N = 128 bits, which is N/8 = 16 bytes. Therefore, the padding string (in byte format) that may be added to the message is from 0x01 to 0x0F, depending on the number of bytes needed for padding. For example, if you need to pad 5 bytes to reach the next 128-bit boundary, each padding byte value will be 0x04, as 0x04 is the hexadecimal representation of 5 minus 1.

Padding Requirements#

At least add one byte of padding: To allow the padding mechanism to be recognized and removed during decryption, even if the length of the message is already a multiple of the block size required by the encryption algorithm, at least one byte of padding should be added.
Message length is a multiple of N: Add a complete new block consisting only of padding.
Security consequences: Padding may introduce security risks, such as padding oracle attacks.

Error Propagation#

In symmetric encryption, an error in one ciphertext block will result in that block being completely incorrect during decryption and affect a portion of the next block, as errors propagate during the decryption operation.

Full Plaintext Recovery Attack#

The goal of full plaintext recovery is to recover plaintext information from the ciphertext, not necessarily to recover the key; it may only decrypt one or more ciphertexts.

Padding Oracle Attack is a Chosen Ciphertext Attack#

A security vulnerability.

• If the padding is not one of the expected values, an exception is thrown with useful error information.
• It exploits the way the encryption system handles padding errors. This can be exposed through error messages in the network or logs, or timing behavior.
• Errors may result in session termination.
• Additional restrictions may apply to the ciphertext (minimum/maximum length).
• Belongs to chosen ciphertext attack (CCA) (as the attacker needs to decrypt information), therefore not covered by IND-CPA security model.
• Leads to full plaintext recovery attack.
• 128 attempts per byte, 8 bits per byte.
• Target byte from right to left in the block, gradually increasing the length of the valid padding pattern. (See previous slide)

Example uses 0x01, which represents when only one bit of padding is missing. It changes based on the number of missing bits.

attack_process

Attack on CBC Mode with Predictable IVs#

• Can be extended to full plaintext recovery.
• First major attack on the SSL/TLS record protocol in many years.

BEAST Attack#

• JavaScript needs to be able to inject its chosen plaintext blocks at the very beginning of the SSL/TLS record protocol information.

• JavaScript also needs to communicate with the MITM attacker.

• Related to same-origin policy issues.

  

The success of the BEAST attack depends on the following conditions:

• The attacker is able to run their code on the victim's browser.
• An easily attackable protocol version is used (SSL 3.0 or TLS 1.0).
• Predictable IVs are used (in TLS 1.0, the IV is the previous ciphertext block, hence predictable).

What are the consequences of BEAST?#

• BEAST has been a headache for TLS.
• Most client implementations "stick" to TLS 1.0.
• Best solution: Upgrade to TLS 1.1 or 1.2.
• Use random IVs to prevent the attack.
• But also requires server-side support.
• For TLS 1.0, there are multiple workarounds:
• Client-side 1/n-1 record splitting can block the attack.
• Send virtual records with length 0 before each real record.
• Or switch to RC4?