<style>
.red {
color: red;
font-weight: bold;
}

.blue {
color: blue;
font-weight: bold;
}

.lb {
color: rgb(0, 112, 192);
font-weight: bold;
}

.lg {
color: rgb(3, 176, 80);
font-weight: bold;
}

.pink {
color: rgb(214, 3, 160);
font-weight: bold;
}

.orange {
color: rgb(255, 153, 0);
font-weight: bold;
}
</style>

## Stream Ciphers and Block Ciphers

### Stream Cipher

- Structure
- Features
- **speedy**, lower hardware complexity, lower error propagation, typically vulnerable to key **reuse attacks** and **bit-flipping attacks**
- 一次對一個 bit 或 byte 加密
- 可以事先產生 $k_i$，在資料進來時即時加密或解密。
- Some widely used stream ciphers
- Vigenère cipher, Vernam Cipher, A5, RC4, Salsa20, ChaCha20

### Block Ciphers

- Structure
- Features
- typically **more secure**, higher hardware complexity, higher error propagation
- Some widely used block ciphers
- DES, LUCIFER, FEAL, LOKI, RC2, SKIPJACK, CAST, IDEA, BLOWFISH, RC5, RC6, AES

## Confusion and Diffusion (混淆與擴散)
- <font class="blue">混淆: 使 secret key 跟密文的關係盡可能複雜</font>
- <font class="blue">擴散: 明文的任何一個變動會讓密文產生很多不同的變化。</font>


## Feistel Cipher Structure

### Features

- Based on concept of **Product Cipher**, which is the execution of **two or more simple ciphers** in sequence
- Feistel Cipher is a practical application of a proposal by Claude Shannon to develop a product cipher that **alternates Confusion and Diffusion functions**.

### Motivation

- A block cipher operates on a plaintext block of n bits to produce a ciphertext block of n bits. There are $2^n$ possible different plaintext blocks, and each must produce a **unique** ciphertext block to ensure **reversibility**
- 4-bit（二進位）轉成十進位的值，替換後再轉回 4-bit。


### Feistel Encryption and Decryption (16 rounds)


:::info
**Note**: it is not necessary for the function $F$ to be reversible.
:::

### Parameters and Design Features

- Block Size
- Increasing size **improves security**, but **slows cipher**
- Key Size
- Increasing size **improves security**, makes **exhaustive key searching harder**, but may **slow cipher**
- Number of rounds
- Increasing number **improves security**, but **slows cipher**
- Subkey generation
- Greater complexity can **make analysis harder**, but **slow cipher**
- Round function
- Greater complexity can **make analysis harder**, but **slows cipher**
- Fast software encryption/decription
- Ease of analysis

## DES (Data Encryption Standard, 資料加密標準)

### Characteristics

- Block Cipher
- Product Cipher (Substitution and Permutations)
- Themost widely used **symmetric** encryption algorithm before 2000
- Security basis
- Confusion and Diffusion
- <font class="red">Block size: 64 bits</font>
- <font class="red">Key size: 64 (= 56 + 8) bits</font>
- **actual key** (56 bits) plus **parity** (8 bits)
- Number of rounds: 16

### Development of the Standard

> 略

### DES Encryption

Basic Building Blocks:

- Key Scheduling
- PC-1 (Permuted Choice 1)
- PC-2 (Permuted Choice 2)
- Left circular shift
- Initial Permutation: $IP$
- Inverse Initial Permutation ($IP^{-1}$)
- Round Function: F
- expansion permutation
- S-Box
- P-Box


### Initial Permutation ($IP$)

由左到右，由上到下


### Inverse Initial Permutation ($IP^{-1}$)


> It has been pointed out that IP and IP^-1^ serve **no cryptological function**.
> Therefore, both can be removed to speed up the processing (but cannot be called DES)

### Single Round (ith round)


### F


- Expansion Permutation (E)
- 32 bit + 16 bit 重複 = 48 bit
- Permutation Function (P\)
- S-Boxes (Substitution/Choice)
- Providing **Confusion**
- 8 S-boxes: $S_1, S_2, \dots, S_8$
- Example

### Key Scheduling



### Example of DES Enccryption


### DES Decryption

- Recall that
$$
\begin{align}
L_i &= R_{i - 1} \\
R_i &= L_{i - 1} \oplus F(R_{i - 1}, K_i)
\end{align}
$$
which can be rewritten as
$$
\begin{align}
R_{i-1} &= L_i\\
L_{i-1} &= R_i \oplus F(R_{i-1}, K_i) \\
&= R_i \oplus F(L_i, K_i)
\end{align}
$$
$\Rightarrow$ <font style="color: red; font-weight: bold;">DES is reversible</font>
- All steps are the same as in the encryption procedure except that the subkeys must be taken in reverse order, i.e., (K16,K15, …, K1)


### Strength of DES

- The Use of 56-Bit Keys
- A single PC can break DES in about a year.
- Supercomputers should be able to find a key in about an hour.
- Key sizes of 128 bits or greater are effectively unbreakable using simply a brute-force approach
- Weak Keys
- 加密等於解密
- Circular left shift does not affect a string consisting all 0’s or 1’s.
- Some keys (Weak Keys) will not produce distinct subkeys in key scheduling process.
- 4 Weak Keys
- k is a weak key iff $E_k(E_k(p)) = D_k(E_k(p)) = p$
- 
- Semiweak Keys
- Two keys k1 and k2 are semiweak keys if
$$
E_{k1}(E_{k2}(p)) = p
$$
- 12 Semiweak Keys (in 6 pairs)
- Avalanche Effect 雪崩效應
- 明文或 key 微小的改變能造成密文有很大的不同。
- A desirable property of any encryption algorithm is that a **small change** in either the **plaintext** or the **key** should produce a **significant change** in the **ciphertext**
- Example
- Algebraic Structure
- The question is whether, for any message p and two arbitrary keys k1 and k2 , there is always a third key k such that
$$
E_k(p) = E_{k1}(E_{k2}(p))?
$$
If so, the set of all keys would form a group (closed, associative, identity, inverse), where the composition law on k~1~ and k~2~ yields k.
- This would be very harmful to the security of DES.
- It would also render multiple DES encryption useless.
- However, DES is **not a group**.
- imply that techniques such as **triple encryption** do in fact **increase the security** of DES
- Number of Rounds
- Many cryptanalysts wonder whether 16 rounds are sufficient?
- After 5 rounds, every ciphertext bit is a function of every plaintext bit and every key bit
- After 8 rounds, the ciphertext was essentially a random function of every plaintext bit and every key bit. (**Avalanche Effect**)
- Justified by Differential Cryptanalysis
- Trapdoor 暗門
- Is there something special behind S-Boxes?
- There were **12 criterion used**, resulting in **about 1000 possible S-Boxes**, of which the designers particularly chose (S1, S2, …, S8)
- Timing Attacks
- attacks actual implementation of cipher
- use knowledge of consequences of implementation to derive information about some or all subkey bits
- exploits the fact that an encryption or decryption operation of some ciphers may take different amounts of time on different inputs
- particularly problematic on asymmetric (public) ciphers
- particularly problematic on using smartcards
- **DES** is shown to be **resistant** to **Timing Attacks**
- Differential Cryptanalysis
- The first attack on DES that is better than exhaustive search in terms of computational requirements was announced by Biham and Shamir (1993) using a new technique known as differential cryptanalysis. This attack requires the encryption of 2^47^ chosen plaintexts.
- This attack is not practical.
- Thus, DES is secure against Differential Cryptanalysis.
- Linear Cryptanalysis
- Matsui (1994) has developed linear cryptanalysis.
- This attack requires the encryption of 2^43^ known plaintexts.
- This attack is not practical.
- Thus, **DES is secure against Linear Cryptanalysis**
- Brute-Force Attack
- **RSA DES Challenge I** (Jan. 13, 1998): The organization distributed.net coordinated 22,000 participants (involving 50,000 CPUs) to solve it in 40 days. (Reward: $5,000)
- **RSA DES Challenge II** (July. 13, 1998): The Electronic Frontier Foundation (EFF) solved it within 56 hours by using EFF Cracker($250,000). (Reward: $10,000).
- Plaintext: It’s time for those 128-, 192-, and 256-bit keys.
- **RSA DES Challenge III** (Jan. 18, 1999): EFF solved it in 22 hours 15 minutes. They built a “Deep Crack” machine. (Reward: $10,000)
- Plaintext: See you in Rome (second AES Conference, March 22-23, 1999)
- DES has been replaced by TripleDES (broken in 2017) and AES.

## Padding Schemes for Block Ciphers

### ANSIX9.23 Padding Scheme

- Padding technique can be used to deal with the problem of **short block** (messages don’t divide neatly into blocks).
- Example (DES is taken as the example cipher)
- If the padding is used, it should always be used, i.e., no exception even if no short block.

### PKCS #7 Padding Scheme

- Pad the last **B − (L mod B)** bytes all having value B − (L mod B)
- L: the **message length** (in byte)
- B: the **block size** (in byte)
- Example

### PKCS #5 Padding Scheme

**Special case** of PKCS #7 Padding Scheme with fixed **B = 8**

## FEAL

- **F**ast data **E**ncipherment **AL**gorithm
- Basic Features
- 64-bit block
- 64-bit or 128-bit key
- 4 to 32+ rounds
- Cryptanalysis
- Many attacks have been developed against it, which has led to upgrade
- from 4 rounds to 32+ rounds
- from 64-bit key to 128-bit key
- Break FEAL-4
- only 20 chosen plaintexts
- Break FEAL-8
- only 225 known plaintexts.
- Break FEAL-N
- Biham and Shamir (1991) developed differential cryptanalytic attacks against FEAL-N for up to 31 rounds.
- FEAL and its derivatives should be considered **insecure**.

## IDEA

- <font class="lb">International Data Encryption Algorithm</font>
- Basic Features
- 64-bit block
- 128-bit key
- 8 rounds
- Techniques
- **mixing operations** from different algebraic groups
- three incompatible types of arithmetic operations
- Weak keys: a large class of 2^28^ weak keys
- Security
- <font class="pink">In 2011, IDEA was broken using a meet-in-the-middle attack</font>
- Speed: IDEA is a little slower than DES
- License: expired in 2012

## Blowfish

- Characteristics
- Block cipher
- Block size: 64 bits
- Key size: 32 ~ 448 bits
- i.e., 1 ~ 14 32-bit words
- Number of rounds: 16
- Speed
- Blowfish is faster than DES (and IDEA)

## RC2

- <font class="lb">Rivest Cipher 2 (or Ron’s Code 2)</font>
- In the past several years, RC2 was ever a **trade secret**
- Characteristics
- Block cipher
- Block size: 64 bits
- Key size: 8 ~ 1024 bits (must be multiple of 8 bits)
- range: 8-bit key, 16-bit key, …, 1024-bit key
- Number of rounds: 16
- Often used by ones who want to export their products
- An agreement between the Software Publishers Association (SPA) and the U.S. gives RC2 and RC4 special status by means of which the export approval process is easier, simpler, and quicker than the usual cryptographic export process.
- To qualify for quick export approval a product must limit the RC2 and RC4 keys size to **40 bits**; **56 bits** is allowed for foreign subsidiaries and overseas offices of U.S. companies
- Speed
- RC2 is a little slower than RC5

## RC5

- <font class="lb">Rivest Cipher 5 (or Ron’s Code 5)</font>
- Characteristics
- Block cipher
- General form: <font class="lg">RC5-w/r/b</font>
- w: word size (bits)
- allowable values: 16, 32, 64
- r: number of rounds
- allowable values: 0 to 255
- b: key length (bytes)
- allowable values: 0 to 255
- Easy to implement and analyze
- Speed
- RC5 is a little slower than Blowfish but still far faster than DES, IDEA, and RC2

## RC Family

- RC1: only in Notebook
- RC2
- Block Cipher
- <font class="pink">It was initially a trade secret</font>; later, it was published.
- RC3: has been broken in its development
- <font class="lg">RC4</font>
- <font class="orange">Stream Cipher</font>
- <font class="pink">It was initially a trade secret; later, it was posted on the Internet by someone</font>
- RC5
- Block Cipher (details are published in the beginning)
- RC6
- Block Cipher (details are published in the beginning)
- A modified version of RC5 as the proposal for AES competition

## CAST-128

- Characteristics
- Block cipher
- Block size: 64 bits
- Key size: <font class="lg">40, 48, 56, ..., 128 bits</font> (multiple of 8 bits)
- Number of rounds: 16

## Skipjack

- Characteristics
- Block cipher
- Block size: 64 bits
- Key size: 80 bits
- Number of rounds: 32
- It can only be implemented in tamper-proof hardware
- Contained in the Clipper chip and Capstone chip (with Key-Escrow mechanism)
- Initially the details of Skipjack were classified
- Skipjack has been declassified by the NSA (June 1998 )