Computer Security - Cryptography

Computer Security: Cryptography and Network Security

Modern Block Ciphers

• Focus: DES (Data Encryption Standard).
• Illustrates block cipher design principles.

Block vs Stream Ciphers

• Block ciphers: Process messages in blocks (64-bits or more), en/decrypting each block.
  • Like a substitution on large characters.
• Stream ciphers: Process messages a bit or byte at a time when en/decrypting.
• Many current ciphers are block ciphers, offering a broader range of applications.

Block Cipher Principles

• Most symmetric block ciphers are based on a Feistel Cipher Structure.
• This structure is needed to efficiently decrypt ciphertext to recover messages.
• Block ciphers resemble extremely large substitutions.
• A 64-bit block would require a table of $2^{64}$ entries.
• Instead, they are created from smaller building blocks using the idea of a product cipher.

Ideal Block Cipher

• An ideal block cipher is conceptualized using decoders and encoders to transform input bits into output bits.

Claude Shannon and Substitution-Permutation Ciphers

• Claude Shannon introduced substitution-permutation (S-P) networks in a 1949 paper.
• S-P nets form the basis of modern block ciphers.
• Based on two primitive cryptographic operations:
  • Substitution (S-box)
  • Permutation (P-box)
• Provide confusion and diffusion of message and key.

Confusion and Diffusion

• Ciphers need to obscure the statistical properties of the original message.
• A one-time pad achieves this.
• More practically, Shannon suggested combining S & P elements to obtain:
  • Diffusion: Dissipates the statistical structure of plaintext over the bulk of ciphertext.
  • Confusion: Makes the relationship between ciphertext and key as complex as possible.

Origins of AES

• A replacement for DES was needed due to theoretical attacks and demonstrated exhaustive key search attacks.
• Triple-DES exists but is slow with small blocks.
• US NIST issued a call for ciphers in 1997.
• 15 candidates were accepted in Jun 98.
• 5 were shortlisted in Aug-99.
• Rijndael was selected as the AES in Oct-2000.
• Issued as FIPS PUB 197 standard in Nov-2001.

AES Requirements

• Private key symmetric block cipher.
• 128-bit data, 128/192/256-bit keys.
• Stronger & faster than Triple-DES.
• Active life of 20-30 years (+ archival use).
• Provide full specification & design details.
• NIST released all submissions & unclassified analyses.

AES Evaluation Criteria

• Initial criteria:
  • Security: Effort for practical cryptanalysis.
  • Cost: In terms of computational efficiency.
  • Algorithm & implementation characteristics.
• Final criteria:
  • General security.
  • Ease of software & hardware implementation.
  • Implementation attacks.
  • Flexibility (in en/decrypt, keying, other factors).

AES Shortlist (Aug-99)

• MARS (IBM) - complex, fast, high security margin.
• RC6 (USA) - very simple, very fast, low security margin.
• Rijndael (Belgium) - clean, fast, good security margin.
• Serpent (Euro) - slow, clean, very high security margin.
• Twofish (USA) - complex, very fast, high security margin.
• Subjected to further analysis & comment.
• Contrasted algorithms with few complex rounds versus many simple rounds.
• Refined existing ciphers versus new proposals.

The AES Cipher - Rijndael

• Designed by Rijmen-Daemen in Belgium.
• Has 128/192/256 bit keys, 128 bit data.
• An iterative rather than Feistel cipher.
• Processes data as a block of 4 columns of 4 bytes (state).
• Operates on the entire data block in every round.
• Designed to be:
  • Resistant against known attacks.
  • Fast and code-compact on many CPUs.
  • Design simplicity.

Rijndael Structure

• Data block of 4 columns of 4 bytes is the state.
• The key is expanded to an array of words.
• Has 9/11/13 rounds in which the state undergoes:
  • Byte substitution (1 S-box used on every byte).
  • Shift rows (permute bytes between groups/columns).
  • Mix columns (substitution using matrix multiplication of groups).
  • Add round key (XOR state with key material).
• View as alternating XOR key & scramble data bytes.
• Initial XOR key material & incomplete last round.
• Fast XOR & table lookup implementation.

Rijndael Rounds

• Diagram showing the steps in encryption and decryption rounds, including byte substitution, shift rows, mix columns, and add round key.

Byte Substitution

• A simple substitution of each byte.
• Uses one table of 16x16 bytes containing a permutation of all 256 8-bit values.
• Each byte of the state is replaced by a byte indexed by row (left 4-bits) & column (right 4-bits).
  • Example: byte {95} is replaced by the byte in row 9, column 5, which has value {2A}.
• The S-box is constructed using a defined transformation of values in GF($2^8$).
• Designed to be resistant to all known attacks.

Shift Rows

• A circular byte shift in each row:
  • 1st row is unchanged.
  • 2nd row does a 1-byte circular shift to the left.
  • 3rd row does a 2-byte circular shift to the left.
  • 4th row does a 3-byte circular shift to the left.
• Decryption inverts using shifts to the right.
• Since the state is processed by columns, this step permutes bytes between the columns.

Mix Columns

• Each column is processed separately.
• Each byte is replaced by a value dependent on all 4 bytes in the column.
• Effectively a matrix multiplication in GF($2^8$) using prime poly $m(x) = x^8 + x^4 + x^3 + x + 1$.

Mix Columns - Equations and Polynomials

• Each column can be expressed as 4 equations to derive each new byte in the column.
• Decryption requires the use of an inverse matrix, which is a little harder due to larger coefficients.
• Alternate characterization:
  • Each column is a 4-term polynomial with coefficients in GF($2^8$).
  • Polynomials are multiplied modulo ($x^4 + 1$).

Add Round Key

• XOR the state with 128-bits of the round key.
• Processed by column (though effectively a series of byte operations).
• The inverse for decryption is identical since XOR is its own inverse, with reversed keys.
• Designed to be as simple as possible, a form of Vernam cipher on an expanded key.
• Requires other stages for complexity / security.

AES Round Overview

• Diagram showing the sequence of SubBytes, ShiftRows, MixColumns, and AddRoundKey.

AES Key Expansion

• Takes a 128-bit (16-byte) key and expands it into an array of 44/52/60 32-bit words.
• Starts by copying the key into the first 4 words.
• Then loops, creating words that depend on values in previous & 4 places back.
• In 3 of 4 cases, it just XORs these together.
• The 1st word in 4 has rotate + S-box + XOR round constant on previous, before XORing 4th back.

Key Expansion Rationale

• Designed to resist known attacks.
• Design criteria included:
  • Knowing part of the key should be insufficient to find many more key bits.
  • Invertible transformation.
  • Fast on a wide range of CPUs.
  • Use round constants to break symmetry.
  • Diffuse key bits into round keys.
  • Enough non-linearity to hinder analysis.
  • Simplicity of description.

AES Decryption

• AES decryption is not identical to encryption since steps are done in reverse.
• However, an equivalent inverse cipher can be defined with steps as for encryption but using inverses of each step with a different key schedule.
• Works since the result is unchanged when:
  • Swap byte substitution & shift rows.
  • Swap mix columns & add (tweaked) round key.

AES Decryption Rounds

• Diagram illustrating the inverse operations in the decryption rounds.

Implementation Aspects

• Can be efficiently implemented on 8-bit CPUs.
  • Byte substitution works on bytes using a table of 256 entries.
  • Shift rows is a simple byte shift.
  • Add round key works on byte XORs.
  • Mix columns requires matrix multiply in GF($2^8$) which works on byte values and can be simplified to use table lookups & byte XORs.
• Can be efficiently implemented on 32-bit CPUs.
  • Redefine steps to use 32-bit words.
  • Can precompute 4 tables of 256-words.
  • Each column in each round can be computed using 4 table lookups + 4 XORs at a cost of 4Kb to store tables.
• Designers believe this very efficient implementation was a key factor in its selection as the AES cipher.

Summary of AES

• The AES selection process.
• The details of Rijndael – the AES cipher.
• Steps in each round.
• The key expansion.
• Implementation aspects.

Multiple Encryption & DES

• A replacement for DES was needed due to theoretical attacks and demonstrated exhaustive key search attacks.
• AES is a new cipher alternative.
• Prior to this alternative was to use multiple encryption with DES implementations.
• Triple-DES is the chosen form.

Double-DES?

• Could use 2 DES encrypts on each block: $C = E<em>{K2}(E</em>{K1}(P))$.
• Issue of reduction to a single stage.
• Vulnerable to