# Information Systems and Network Security

## Schedule

- Tuesday 9:30 - 11:30. Room A1.2.
- Thursday 11:30 - 13:30. Room A1.2

**Office hours:** Thursday 16:30 - 18:30. Please send me an email or ask before/after the lectures.

## Lectures and Material

### Lecture 1: Introduction

Basic information about the course: schedule, prerequisites, course program, textbooks, and exams.

Modelling communication through an insecure channel. The Confidentiality, Authentication, and Integrity properties.

An overview of some advanced applications of cryptography (informal): Secret Sharing (t-out-of-n threshold secret-sharing schemes), secure multiparty computation, zero knowledge protocols.

Types of cryptography, the private-key (symmetric) and the public-key (asymmetric) settings. Formal definition of a private-key encryption scheme. Security through obscurity and Kerckhoffs’ principle.

#### Material

- Sections 1.1 and 1.2 of [KL].
- Slides of the lecture.

### Lectures 2 and 3: Historic Ciphers

Caesar cipher and shift ciphers: encrypting and decrypting messages, formal definition and correctness of the encryption scheme. Breaking shift ciphers: bruteforce attacks. The sufficient key-space principle.

Monoalphabetic substitution ciphers: encrypting and decrypting messages. Security: the sufficient key-space principle not a sufficient condition for security, breaking the cipher once a small part of the plaintext is known, guessing the initial part of the plaintext with frequency analysis.

The Vigenère cipher: encrypting and decrypting messages, the tabula recta. Security: splitting the ciphertext into multiple ciphertext with the same shift, recovering the key length (bruteforce, Kasiski’s method, the index of coincidence method), recovering the plaintext by breaking the shift ciphers.

The scytale cipher: encrypting, decrypting, and breaking the cypher using a tapering cone. The scytale cipher as a special type of transposition cipher.

Regular and irregular columnar transposition ciphers, double (irregular) transposition ciphers. Weaknesses of transposition ciphers.

#### Material

- A discussion of the Ceasar cipher, the shift cipher, and the Vigenère cipher can be found in Section 1.3 of [KL].
- Slides of the lecture.
- Two challenge ciphertexts. Can you decrypt them and recover the corresponding key? first ciphertext, second ciphertext.
- Solution: Jupyter notebook demonstrating how to break shift and Vigenère ciphers.

### Lecture 4: Defining Security, Perfect Secrecy

Ingredients of a security definition: *security guarantee* and *threat model*. Common threat models (Ciphertext-only attacks, Known-plaintext attacks, Chosen-plaintext attacks, Chosen-ciphertext attacks) and real-word scenarios in which these attacks can be carried out.

Security Guarantees: several informal attempts at a good definition and counterexamples, Shannon's treatment and his definition of Perfect secrecy, an alternative definition of perfect secrecy (with proof of equivalence). Proving that shift ciphers are not perfectly secret (using both definitions). A third definition based on a perfect indistinguishability experiment. Equivalence of the three definitions (with proof). Proving that the Vigenère cipher is not perfectly indistinguishable.

#### Material

- Sections 1.4.1 and 2.1 of [KL].
- Slides of the lecture.

### Lecture 5: The Vernam Cipher (One-time Pad)

The *Vernam cipher* (or *one-time pad*, *OTP*): formal definition, proof of correctness, proof of security using the alternative definition of perfect secrecy.

Caveats and limitation of OTP: sharing and storing long keys, generating random bits, reusing the key leaks the XOR of the plaintexts. Attacks based on the malleability of OTP.

Necessary and sufficient conditions for perfectly secret private-key encryption schemes: the key-space must be at least as large as the message space (with proof and corollaries); two attacks on schemes with less keys than messages; Shannon's theorem. Proof of security of OTP using Shannon's theorem.

#### Material

- Sections 2.3, 2.3, and 2.4 of [KL].
- A proof of Shannon's theorem along with the stronger version discussed in class can also be found in Section 1.3.4 of [PS].
- Slides of the lecture.

### Lecture 6 (π day): Computational Secrecy and Pseudorandom Generators

The notion of computational secrecy. Relaxing perfect indistinguishability by (i) considering only efficient adversaries; and (ii) allowing secrecy to fail with small probabilities.

The concrete definition of computational secrecy: (t, epsilon)-indistinguishability. Problems with the concrete definition, and the asymptotic approach. Polynomially bounded functions and negligible functions.

Redefining private-key encryption schemes to account for the security parameter. Redefining the adversarial indistinguishability experiment to account for the security parameter and polynomial-time adversaries. Formal definition of computational indistinguishability.

The indistinguishability experiment does protect against leaking the length of the message: discussion and implications for security.

Pseudorandom Generators (PRGs): intuitive definition, existence, and the relation with the P vs NP problem. Formal definition of PRG. Statistical tests. Non-efficient statistical tests can always distinguish the output of a PRG from true randomness with a non-negligible probability gap. Applications of PRGs: replacing random bits in randomized algorithms and derandomization.

#### Material

- Sections 3.1, 3.2.1, and 3.3.1 of [KL].
- Slides of the lecture.

### Lecture 7: Pseudo-OTP and CPA-Security

Redefining OTP to account for the security parameter and combining it with a PRG to obtain the pseudo-OTP encryption scheme. Security proofs and cryptographic assumptions. Proving that pseudo-OTP is EAV-secure (conditioned on the existence of PRGs) via a security reduction.

Issues with pseudo-OTP. Definition of security for multiple messages. Pseudo-OTP does not have indistinguishable multiple encryptions in the presence of an eavesdropper. Multiple message security and deterministic encryption schemes. The stronger notion of CPA-security. The CPA indistinguishability experiment. Formal definition of CPA-security. The relation between CPA-security, EAV-security, EAV-security for multiple encryptions, and deterministic encryption schemes.

#### Material

- Sections 3.3.2, 3.3.3, and 3.4 of [KL].
- Slides of the lecture.

### Lecture 8: Pseudorandom Functions and Permutations

Intuition behind the notion of random and pseudorandom functions (PRFs). Formalizing the intuition: random functions, counting the number of functions, keyed functions, definition of pseudorandom function. Examples functions that are not pseudorandom, and the corresponding distinguishers.

Building a PRG from a PRF (with proof). Building a PRF with short input length from a PRG (with proof). Building a PRF from a length-doubling PRG using the Goldreich-Goldwasser-Micali construction (without proof). Building a length-doubling PRG from a PRG with expansion factor n+1 (with proof).

Informal definition of pseudorandom permutations (PRPs). Counting the number of permutations and relating it with the number of functions. Keyed permutations and the formal definition of pseudorandom permutation. Definition of strong pseudorandom permutations.

#### Material

- Sections 3.5.1, 8.4.2, and 8.5 (without proof) of [KL].
- Slides of the lecture.

### Lecture 9: Achieving CPA-Security, Stream Ciphers

Achieving CPA-security using PRFs and PRPs: a failed attempt using PRPs and CPA-secure encryption scheme using a PRF with proof of security. Caveats of the above CPA-secure encryption scheme: reusing the random values, using non-uniform distributions, ciphertext expansion.

Avoiding ciphertext expansion: stream ciphers as a better interface to PRGs and PRFs. Formal definition of (secure) stream ciphers. Building a stream ciphers with an initialization vector from a PRF. Modes of operation of stream ciphers: synchronized mode and unsynchronized mode.

#### Material

- Sections 3.5.2, 3.6.1, and 3.6.2 of [KL].
- Slides of the lecture.

### Lecture 10: Practical Constructions of Stream Ciphers: LFSRs, NLFSRs, and Trivium

Linear Feedback Shift Registers (LFSRs): description of their operation and mathematical formalization. Using a LFSR as a stream cipher. State graph of a LFSR, and maximum-length LFSRs. (In)security of LFSRs: recovering the key, recovering the coefficients.

Nonlinear Feedback shift registers (NLFSRs): nonlinear feedback, nonlinear output, and combination generators. Avoiding biases in nonlinear feedback shift registers. Correlation attacks on combination generators. Trivium.

Extra: implementing LFSRs in hardware.

#### Material

- Sections 7.1.1, 7.1.2, and 7.1.3 of [KL].
- Slides of the lecture.
- Digital file implementing a LFSR of degree 8 (schematic). The Digital circuit simulator can be found here.

### Lecture 11: RC4, Block Ciphers and Some Common Modes of Operation

RC4: the Init and Next algorithms. Implementing RC4 and the bias of the second output byte. Analysis of the output bias. Misusing RC4 by adding IVs and a key recovery attack. ChaCha20 as a secure replacement for RC4.

Definition of block cipher. Using a block cipher to build a stream cipher. Some common modes of operation of block ciphers: Electronic Code Book (ECB), Cipher Block Chaining (CBC), Stateful CBC (Chained CBC), Output Feedback (OFB), Stateful OFB, Counter (CTR). Security of the different modes of operation (without proofs). Demonstration of the EAV-insecurity of CBC.

#### Material

- Sections 7.1.4, 7.1.5, and 3.6.3 of [KL].
- Slides of the lecture.
- Jupyter notebook implementing RC4 and demonstrating its output bias.
- Jupyter notebook deonstrating the insecurity of ECB.

## References

**[KL]**: Jonathan Katz, Yehuda Lindell.*Introduction to Modern Cryptography*, 3rd edition. CRC Press. ISBN: 978-0815354369.**[S]**: Nigel P. Smart.*Cryptography Made Simple*. Springer. ISBN: 978-3319219356.**[G]**: Oded Goldreich.*Foundations of Cryptography: Volume 1, Basic Tools*. Cambridge University Press. ISBN: 978-0521035361.**[PS]**: Rafael Pass and Abhi Shelat.*A Course in Cryptography (3rd ed.)*