Block cipher modes of operation

(block cipher) mode of operation

A block cipher takes a fixed-length block of text of $b$ bits and a key as input and produces a $b$-bit block of ciphertext.

If our messages exceed the block-width, then the block cipher can still be used by breaking up the plaintext. NIST defines 5 modes of operation for use with any symmetric block cipher, including triple DES and AES.

A mode of operation is a technique for enhancing the effect of a cryptographic algorithm or adapting the algorithm for an application.

Link to original

All of NIST-approved block cipher modes of operation (except ECB) involve feedback

Think of encryption as taking input from a input register whose length equals encryption block length and with output stored in an output register. Input register updated one block at a time by feedback mechanism. After each update, encryption algorithm is executed, producing a result in output register. Meanwhile, a block of plaintext is accessed.

Electronic Codebook (ECB)

Electronic Codebook (ECB)

This is the simplest mode, plaintext message is broken into $N$ independent blocks $P_1,\dots ,P_N$.

• Each block $P_i$ with $1\le i\le N$ encrypted individually, independently of other blocks: $C_i=E(K,P_i)$.
• Requires last block be padded to a full $b$ bits if it is a partial block.
• Each $P_i$ is a value that is substituted, like a codebook.

Each ciphertext block is decrypted also individually, with same $K$: $P_i=D(K,C_i)$

Link to original

Limitations

For lengthy messages, ECB may not be secure. If the same $b$-bit block of plaintext appears more than once, it always produces the same ciphertext. So if the message is highly structured, it may be possible for someone to exploit these regularities.

Ideal Use

This is ideal for a short amount of data, such as an encryption key. e.g. transmitting a DES / AES key securely

Cipher Block Chaining (CBC)

Cipher Block Chaining (CBC)

Cipher input is XOR of current plaintext block with preceding ciphertext block. For $C_0=IV$ (initialisation vector) and $1<i\le N$:

Encryption	Decryption
$\begin{array}{rl}{C}_1& =E(K,IV\oplus P_1)\\ C_i& =E(K,C_{i-1}\oplus P_i)\end{array}$	$\begin{array}{rl}{P}_1& =D(K,C_1)\oplus IV\\ P_i& =D(K,C_i)\oplus C_{i-1}\end{array}$

This requires the last block to be padded to a full $b$ bits if it is a partial block.

Link to original

Proof of Correctness

$$\begin{array}{rl}{P}_i& =D(K,C_i)\oplus C_{i-1}\\ & =D(K,E(K,C_{i-1}\oplus P_i))\oplus C_{i-1}\\ & =(C_{i-1}\oplus P_i)\oplus C_{i-1}\\ & =P_i\end{array}$$

Initialisation Vector $IV$

The initialisation vector is a data block that is the same size as the cipher block. IV must be known to both sender and receiver but be unpredictable by third party & protected against unauthorised changes.

Properties and Use

• Repeating patterns of $b$ bits are not exposed as the input to the encryption function for each plaintext block bears no fixed relationship to the plaintext block.
• Identical plaintext blocks mapped to different ciphertext.
• Chaining dependencies: $C_i$ depends on all preceding plaintext.
• Self-synchronising: if an error occurs (changed bits, dropped blocks) in $C_i$ but not $C_{i+1}$, then $C_{i+2}$ is correctly decrypted.

CBC is appropriate for encrypting messages of length greater than $b$ bits.

Stream Ciphers

It is possible to convert a block cipher into a stream cipher using one of the modes CFB and OFB (or CTR but not covered).

A stream cipher eliminates the need to pad a message to be an integral number of blocks. It can also operate in real time: character stream can be encrypted and transmitted immediately.

Cipher FeedBack (CFB)

Cipher FeedBack (CFB)

As with Cipher Block Chaining (CBC), units of plaintext are chained together, so that ciphertext of any plaintext unit is a function of all the preceding plaintext.

Rather than blocks of $b$ bits, plaintext is divided into segments (‘units of transmission’) of $s$ bits. A common value is $s=8$.

Link to original

CFB Encryption & Decryption

The input is a $b$-bit shift register initially set to some initialisation vector. Let ${\text{MSB}}_S(X)$ be the most significant $s$ bits of $X$.

First unit of ciphertext $C_1=P_1\oplus {\text{MSB}}_S(E(K,IV))$ is XOR of:

• first segment of plaintext $P_1$
• leftmost (most significant) $s$ bits of output of encryption function

Contents of shift register are shifted left by $s$ bits, and $C_1$ is placed in rightmost (least significant) $s$ bits of shift register.

Process continues until all plaintext units have been encrypted.

Decryption uses the same scheme, except that the received ciphertext unit is XORed with the output of encryption function to produce plaintext unit:

$$P_1=C_1\oplus {\text{MSB}}_S(E(K,IV))$$

Although CFB can be seen as a stream cipher, it does not conform to typical construction of a stream cipher: usually stream ciphers take as input some initial value and a key and generate a stream of bits, which is then XORed with plaintext bits. In CFB, the stream of bits that is XORed with plaintext also depends on the plaintext.

Output FeedBack (OFB)

Output FeedBack (OFB)

Similar to Cipher FeedBack (CFB), except:

• Output of encryption function is fed back to shift register in OFB. (CFB: ciphertext unit is fed back to shift register)
• OFB operates on full blocks, not on an $s$-bit subset.

$$C_i=P_i\oplus E(K,(\dots ))\text{ and }{P}_i=C_i\oplus E(K,(\dots ))$$

Nonce

Nonce: time-varying value that has at most a negligible chance of repeating.

Link to original

Link to original

OFB: Encryption & Decryption

Nonce $I_1=IV$ unique to each execution of encryption operation:

• Sequence of $O_i$ depends only on key and IV and not on plaintext.
• For given $K$ and $IV$, stream $O_i$ used to XOR with stream $P_i$ is fixed.
• If 2 different messages had an identical block of plaintext in identical position, an attacker could determine that portion of $O_i$ stream.

If we let block size be $b$: if last plaintext block $P_N$ contains $u<b$ bits (indicated by *), most significant $u$ bits of last output block $O_N$ are used for XOR. Remaining $b-u$ bits of last output block are discarded.

Introduction to Public-Key Cryptography

• Present an overview of the basic principles of public-key cryptosystems. 
• Explain the different uses of public-key cryptosystems. 
• List and explain the requirements for a public-key cryptosystem.

Principles of public-key cryptosystems

• Secrecy (public-key cryptosystem)

  Secrecy (confidentiality) means only $B$, who possesses $P{R}_b$, can decrypt $Y=E(P{U}_b,X)$, where $X$ is a secret intended for $B$.

  Link to original

• Authentication (public-key cryptosystem)

  Authentication means only $A$, who possesses $P{R}_a$ can have generated $Y=E(P{R}_A,X)$. (everyone may decrypt $Y$ and read $X$ as $P{U}_a$ is public)

  Link to original

Overview of Public-Key Cryptography

Applications of public-key cryptosystems

• Encryption / decryption: sender encrypts a message with recipient’s public key
• Key exchange: two sides cooperate to exchange a session key different approaches are possible, involving private key(s) of one or both parties
• Digital signature: sender “signs” a message with its private key signing is achieved by a cryptographic algorithm applied to a message or small block of data that is a function of message

Requirements for public-key cryptography

1. Computationally easy for any principal $B$ to generate a pair (public key $P{U}_b$, private key $P{R}_b$)
2. Computationally easy for sender $A$, knowing $P{U}_b$ and $M$, to generate $C=E(P{U}_b,M)$.
3. Computationally easy for receiver $B$ to decrypt $C$ using $P{R}_b$ to recover $M$: $M=D(P{R}_b,C)=D(P{R}_b,E(P{U}_b,M))$
4. It is computationally infeasible for an adversary:
   • Knowing $P{U}_b$ to determine $P{R}_b$
   • Knowing $P{U}_b$ and $C$ to recover $M$
5. (useful but not always necessary) The two keys can be applied in either order: $M=D(P{U}_b,E(P{R}_b,M))=D(P{R}_b,E(P{U}_b,M))$

Function terminology

$f:X\to Y$ is a function from the set $X$ (f’s domain) to the set $Y$ (f’s codomain).

Image (functions)

Image of $f$ is a subset of $f$‘s codomain that is output of $f$ on a subset of its domain (image is the smaller oval inside $Y$).

• Image of $x\in X$ under $f$ is $f(x)=y$ (value of $f$ when applied to $x$)
• Image of a subset $A\subseteq X$ under $f$ is subset $f[A]\subseteq Y$ defined by $f[A]=\{y\in Y|y=f(x)\text{ for some }x\in A\}$
• Image $f[X]$ of entire domain $X$ of $f$ is called the image of $f$.

Link to original

Inverse image (functions)

Inverse image (or preimage) of a particular subset $B\subseteq Y$ of the codomain of a function $f$ is the set of all elements of the domain that map to the members of $B$.

$$f^{-1}[B]=\{x\in X|f(x)\in B\}$$Link to original

One-way function

A function $f:X\to Y$ is a one-way function, if $f$ is ‘easy’ to compute for all $x\in X$, but $f^{-1} is ‘hard’ or ‘infeasible’ to compute.

• ‘easy’: solved in polynomial time as function of input length
• ‘infeasible’: effort to solve grows faster than polynomial time as a function of input size

Link to original

Trapdoor one-way function

A trapdoor one-way function is a one-way function $f_k:X\to Y$ easy to calculate in one direction and infeasible to calculate in the other direction unless certain additional information is known (with which the inverse can be calculated in polynomial time, it is feasible to find for $y\in \text{Image}(f)$, an $x\in X$ where $f_k(x)=y$).

Link to original

Public-key cryptanalysis

• Brute-force attacks are possible: we use large keys to counter this.
• Computing private key from public key: no proof that this attack is infeasible. (not even for RSA)
• Probable-message attack: suppose a short message $M$ is encrypted with $P{U}_a$. $C=E(P{U}_a,M)$ The attack computes all $Y_i=E(P{U}_a,X_i)$ for all possible plaintexts $X_i$ for $i=1,\dots ,2_{56}$ and stops as soon as $Y_i=C$ concluding that $M=X_i$ (the message sent). Solution: append random bits to $M$ before encryption.