Steganography

Steganography conceals the existence of a message, whereas methods of cryptography render the message unintelligible to outsiders by various transformations of the text.

Steganography Techniques

Example techniques include:

• Arrangement of words or letters within an apparently innocuous text spells out the real message.
• Invisible ink: substances used for writing that leave no visible trace until heat / chemical is applied to paper
• Pin punctures: small pin punctures on selected letters are ordinarily not visible unless paper is held up in front of a light
• Least significant bits of frames of an image (or sound file) For example, for a picture of resolution 2048x3072, each pixel contains 24 bits of RGB colour information, the least significant bit of each 24-bit pixel can be changed without greatly affecting the quality of the image.

Relative Advantages of Steganography

Use-cases of Steganography

Watermarking

Watermarking is hiding digital information in a carrier signal; usually some kind of marker covertly embedded in a noise-tolerant signal such as audio (e.g. mp3) or image data (e.g. mpeg).

Link to original

Digital Rights Management

Digital Rights Management (DRM) is a class of technologies that are used by hardware manufacturers, publishers, copyright holders, and individuals with the intent to control the use of digital content and devices after sale.

Link to original

Composite (product) ciphers

Ciphers just based on substitutions or transpositions are not secure, however we can combine ciphers: a substitution followed by a transposition makes a new harder cipher.

Product Cipher

Product (composite) ciphers chain substitution-transposition combinations, it is the execution of $2$ or more simple ciphers in sequence so that the result (product) is cryptographically stronger than any of the component ciphers.

• The idea is that a cipher with $k$-bit key and $n$-bit blocks allows a total of $2^k$ possible transformations rather than $2^n$.

Link to original

Abstract

Most common complex ciphers in use before modern ciphers were rotor machines.

Idea of Feistel Cipher

Many symmetric block encryption algorithms in current use are based on a structure called the Feistel block cipher.

Block Cipher

A block cipher is an encryption scheme that breaks up the plaintext message into strings (blocks) of a fixed length $n$ and encrypts one block at a time.

• Encryption: takes in input one block of $n$ bits of plaintext and key of $k$ bits, producing an output of one block of ciphertext of $n$ bits.
• Decryption: takes in input one block of $n$ bits of ciphertext and a key of $k$ bits, producing an output of one block of plaintext of $n$ bits.

Link to original

With a block cipher that encrypts $n$-bit plaintext to $n$-bit ciphertext, there are $2^n$ possible different plaintext blocks. This means we have $2^n!$ different transformations. For encryption to be reversible, each of the $2^n$ plaintext blocks must produce a unique ciphertext block.

Ideal (most general form of) block cipher

Can be used to define any reversible mapping plaintext-ciphertext. The $4$-bit input produces one of $16$ possible input states, which is mapped by the substitution cipher into a unique one of $16$ possible output states, each of which is represented by $4$ ciphertext bits. The encryption / decryption mappings can be defined by a tabulation.

Problems with block ciphers

For a small block size (n = 4): equivalent to a classical substitution cipher and hence easily attackable.

For a large block size: usually not practical implementation and performance.

• Mapping is the key.
• Block $n$: key $n\times 2^n$ bits
  • Block $n=4$: key of $64$ bits = ($4$ bits x $16$ rows)
  • Block $n=64$: key of $2^{70}$ bits = ($64$ bits x $2^{64}$ rows)

Feistel’s suggestion is to use an invertible product cipher, i.e. approximation to ideal block cipher for large $n$, built out of components that are easily realisable.

S-boxes and P-boxes: confusion and diffusion

The Feistel cipher is a practical application of a proposal by Shannon to develop a product cipher that alternates confusion and diffusion functions.

Product ciphers chain combinations of substitutions and transpositions.

• S-Boxes confuse input bits
• P-Boxes diffuse bits across S-box inputs

Feistel Cipher

In a nutshell, the encryption / decryption works as such:

• Partition input block into two halves
• Process through multiple rounds (usually $16$ rounds) which
  • perform substitution on left data half (based on round function of right half and subkey)
  • then have permutation swapping halves

Details of Feistel encryption

The encryption input is a $2w$-bit plaintext block and a key $K$.

The plaintext block is divided into $2$ halves $L{E}_0$ and $R{E}_0$ which pass through $n$ rounds of processing (here we use $n=16$) and then combine to produce a ciphertext block.

Feistel encryption round

Each round $i$ has the inputs:

• $L{E}_{i-1}$ and $R{E}_{i-1}$ which are derived from the previous round.
• Subkey $K_i$ derived from overall $K$ (subkeys are different from $K$ and each other).

A substitution is performed on $L{E}_i$ by applying a round function $F$ to $R{E}_i$ and then XORing the output with $L{E}_i$.

$F$ has same general structure for each round but parameterised by round subkey $K_i$:

$$F(R{E}_i,K_{i+1}):w\text{ bits}\times y\text{ bits}\to w\text{ bits}$$

Then a permutation is performed by an interchange of the two halves of data. (the final round is followed by an interchange to undo the final round’s interchange in order to simplify decryption later)

Decryption

Decryption is the same as encryption but performed in reverse. The decryption input is the ciphertext, and the subkeys $K_i$ in reverse order ($K_n$ to $K_1$).

The intermediate values of the decryption process are equal to the corresponding value of encryption process with two halves of the value swapped. $L{D}_{n-i}||R{D}_{n-i}=R{E}_i||L{E}_i$

Parameters and design features of Feistel cipher

• Block size Larger means greater security but reduced en/de-cryption speed. Greater security achieved by greater diffusion.

  New AES uses a 128-bit block size.

• Key size Larger increases security but may decrease en/de-cryption speed. Greater security achieved by greater resistance to brute-force attacks and greater confusion. 128-bits is a common size.
• Number of rounds Single round offers inadequate security. Multiple rounds offer increasing security (typically $16$ rounds)
• Subkey generation algorithm and Round function $F$ Greater complexity means greater resistance to cryptanalysis

One of the strengths of the Feistel cipher is that each round of encryption and decryption has the general shape where the only difference is that: at each encryption round $i$, the key $K_i$ is used, and at each decryption round $i$, the key $K_{17-i}$ is used.

Math behind Feistel encryption / decryption

Show that the output of decryption round $1$ is equal to $w$-bit swap of input to encryption round $16$.

Let us take the ciphertext $L{E}_{17}||R{E}_{17}=R{E}_{16}||L{E}_{16}$ (equal to the $w$-bit swap of output of round $16$) and use it as input to the same algorithm.

Let’s assume that $L{D}_0=R{E}_{16}$ and that $R{D}_0=L{E}_{16}$.

Encryption side:

$$\begin{array}{rl}L{E}_{16}& =R{E}_{16}\\ R{E}_{16}& =L{E}_{15}\oplus F(R{E}_{15},K_{16})\end{array}$$

Decryption side:

$$\begin{array}{rl}L{D}_1& =R{D}_0=L{E}_{16}=R{E}_{15}\\ R{D}_1& =L{D}_0\oplus F(R{D}_0,K_{16})\\ & =R{E}_{16}\oplus F(R{E}_{15},K_{16})\\ & =(L{E}_{15}\oplus F(R{E}_{15},K_{16}))\oplus F(R{E}_{15},K_{16})\\ & =L{E}_{15}\end{array}$$

Hence $L{D}_1||R{D}_1=R{E}_{15}||L{E}_{15}$ as required.

Correspondence holds all the way through the $16$ iterations

Inputs to $i^{th}$ iteration of encryption can be recast as a function of the outputs:

$$\begin{array}{rl}L{E}_i& =R{E}_{i-1}\\ R{E}_i& =L{E}_{i-1}\oplus F(R{E}_{i-1},K_i)\end{array}$$

After rearranging terms:

$$\begin{array}{rl}R{E}_{i-1}& =L{E}_i\\ L{E}_{i-1}& =R{E}_i\oplus F(R{E}_{i-1},K_i)\\ & =R{E}_i\oplus F(L{E}_i,K_i)\end{array}$$

Finally, output of last round of decryption is $R{E}_0||L{E}_0$. A $w$-bit swap recovers the original plaintext.

In general, for $1\le i\le 16$, we can prove that the output of decryption round $16-i$ (i.e. $L{D}_{16-i}||R{D}_{16-i}$) is equal to the $w$-bit swap of the input to encryption round $i+1$ (i.e. $L{E}_i||R{E}_i$).

That is, we can prove the equation $L{D}_{16-i}||R{D}_{16-i}=R{E}_i||L{E}_i$ for $1\le i\le 16$.

We carry out the proof by induction, by assuming that we have already proved that the output of the decryption round $16-i-1=15-i$ is equal to the $w$-bit swap of the input to the encryption round $i+1+1=i+2$, by assuming $L{D}_{15-i}||R{D}_{15-i}=R{E}_{i+1}||L{E}_{i+1}$ and then showing that the output of decryption round $16-i$ is equal to the $w$-bit swap of the input to encryption round $i+1$:

$$\begin{array}{rl}L{D}_{16-i}& =R{D}_{16-i-1}\\ & =R{D}_{15-i}\\ & =L{E}_{i+1}\\ & =R{E}_i\\ & \\ R{D}_{16-i}& =L{D}_{16-i-1}\oplus F(R{D}_{16-i-1},K_{i+1})\\ & =L{D}_{15-i}\oplus F(R{D}_{15-i},K_{i+1})\\ & =R{E}_{i+1}\oplus F(L{E}_{i+1},K_{i+1})\\ & =R{E}_{i+1}\oplus F(R{E}_i,K_{i+1})\\ & =(L{E}_{i+1-1}\oplus F(R{E}_{i+1-1},K_{i+1}))\oplus F(R{E}_i,K_{i+1})\\ & =L{E}_i\end{array}$$

Specific example of Feistel cipher

Consider encryption round $15$ corresponding to decryption round $2$.

Supposed that $32$-bit blocks (two $16$-bit halves) with a $24$-bit key. At the end of encryption round $14$, the value of the intermediate block is $DE7F03A6$ ($L{E}_{14}=DE7F,R{E}_{14}=03A6)$ and the value of $K_{15}=12DE52$.

Then $L{E}_{15}=03A6=R{D}_1$ and $R{E}_{15}=F(03A6,12DE52)\oplus DE7F=L{D}_1$. We prove that $L{D}_2=R{E}_{14}=03A6$ and $R{D}_2=L{E}_{14}=DE7F$:

$$\begin{array}{rl}L{D}_2& =R{D}_1\\ & =03A6\\ & \\ R{D}_2& =L{D}_1\oplus F(03A6,12DE52)\\ & =(F(03A6,12DE52)\oplus DE7F)\oplus F(03A6,12DE52)\\ & =DE7F\end{array}$$