Information Systems and Network Security

Stefano Leucci
Academic Year 2023/2024


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

Exam Dates

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.


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.


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.


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.


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.


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.


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.


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.


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.


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.


Lecutre 12: Practical Constructions of Block Ciphers: SPN Netorks and Feistel Netorks

Designing Block Ciphers: Substitution Permutation Networks (SPN) . The Confusion/Diffusion Paradigm. Structure of a SPN with one or multiple rounds. The avalanche effect. Attacking SPNs with a small number of rounds.

Designing Block Ciphers: Feistel Networks. Structure of a (balanced) Fesitel Network. Inverting a Feistel network. Security of Feistel Networks with one, two, three, and four rounds.


Lecture 13: DES, AES, Active Adversaries and the Need for Integrity

The Data Encryption Standard (DES): structure of DES, the DES mangler function, how S-boxed and the mixing permutation are designed to achieve the avalanche effect. The security of DES: weaknesses related to the short key length and the short block length. Double encryption and meet-in-the-middle attacks. Triple encryption: two-key triple encryption and three-key triple encryption. Triple DES.

The Advanced Encryption Standard (AES): High-level structure of AES as a substitution permutation network and security considerations. The AddRoundKey, SubBytes, ShiftRows, and MixColumns steps.

Active adversaries and denial of service attacks. Two orthogonal concerns: secrecy and integrity. Using Message Authentication Codes (MACs) to guarantee integrity.


Lecture 14: Message Authentication Codes

Formal definition of a MAC and canonical verification for deterministic MACs. Security definition: threat model (adaptive chosen message attack) and security goal (existential unforgeability), the message authentication experiment, formal definition. Dealing with replay attacks.

Constructing secure MACs. A fixed-length MAC from a PRF with proof of security. Drawbacks of the construction (short messages) and domain extension for MACs. Block re-ordering attacks, truncation attacks, mix-and-match attacks. A secure construction of a MAC for arbitrary-length messages from a fixed-length MAC. Drawbacks of the construction (number of evaluations of the fixed-length MAC and length of the computed tag).

A MAC for long fixed-length messages with a short tag: Basic CBC-MAC. Caveats and attacks to improper implementations. CBC-MAC for arbitrary length messages: prepending the message length, using two independent keys.

Strongly secure MACs: the strong message authentication experiment, formal definition of security. All deterministic secure MACs that use canonical verification are also strongly secure.


Lecture 15: CCA Security and Authenticated Encryption

Secrecy against active adversaries: CCA security and its formal definition. Considerations about the strength of CCA-security requirement in the real world. Malleable encryption schemes cannot be CCA-secure. Padding oracles and a padding-oracle attack against PKCS#7 and block ciphers in CBC-mode.

Authenticated encryption and its formal definition. Modular construction of Authenticated Encryption schemes from MACs and CPA-secure encryption schemes. Three approaches (Encrypt and Authenticate, Authenticate then Encrypt, Encrypt then Authenticate) and their security. Secure sessions.


Lecure 16: Hash Functions

Definition of (cryptographic) hash function. Collisions and the need to prevent them. Collision-resistant hash functions. The hash-collision experiment. Weaker notions of security for hash functions (preimage resistance, second preimage resistance). A general attack against hash functions: the birthday attack and analysis of its success probability. Finding meaningful collisions. Relation between collision-resistant hash functions and the P vs. NP problem.

Constructing a hash function for long inputs from a hash function for short inputs: domain extension and the Merkle-Damgård transform. Length Extension Attacks on Hash functions based on the Merkle-Damgård transform. Hash functions in practice.

Using hash functions for message authentication: the Hash-and-MAC construction (with proof of security). Proofs of security in the Random Oracle model and why they are controversial.

Other applications of hash functions: Fingerprinting & Deduplication, Password Hashing, Key Derivation (and the concept of min-entropy), Commitment Schemes. Efficient commitment schemes with partial-reveal, Merkle-trees.


Lecture 17: Number and Group Theory for Public-Key Cryptography & The RSA Assumption

Representing large integers, Modular arithmetic, Efficiently computing modular addition, multiplication, and exponentiation. Bézout’s identity, modular inverses, and their efficient computation.

Definition of group, consequences, and examples. Additive and multiplicative notation for group operations. Efficient group exponentiation. The group Z_N under addition modulo N. The group Z*_N of invertible elements modulo N under multiplication modulo N.The order of Z*_N and Euler's totient function. Fermat’s little theorem and some corollaries.

"Hard" problems for public-key cryptography. Generating Prime numbers, Testing Primality, Factoring, formalizing the hardness of factoring, the factoring assumption, the RSA problem and the RSA assumption. Relation between the RSA assumption and the factoring assumption.


Lecture 18: The Diffie-Hellman Assumption & The Key Distribution Problem

Cyclic groups and group generators, definition of discrete logarithm, the discrete logarithm problem and the discrete logarithm assumption. The Diffie-Hellman Problems: computational and decisional. The CDH and the DDH assumption. Relation between the discrete logarithm assumption, the CDH assumption, and the DDH assumption. Choosing suitable groups.

The key management problem and the necessity of key distribution protocols. Key distribution centers (offline and online solution), open systems. Informal and formal security definitions for key exchange protocols.


Lecture 19: Diffie-Hellman Key Exchange & Public-Key Encryption Schemes

The Diffie-Hellman Key Exchange with proof of security. Turning a random group element into a random binary string. Security against active adversaries and the man-in-the-middle attack.

The public-key setting: benefits and drawbacks. Public-Key Encryption Schemes: intuition and formal definition. Security notions for public-key encryption schemes: CPA-Security and CCA-Security. Equivalence between EAV-security and CPA-security. Consequences of the security definitions.


Lecture 20: the KEM/DEM paradigm, El Gamal and RSA Encryption

Encrypting long messages by splitting a message into blocks and encrypting each block separately: security and drawbacks.

Hybrid encryption: Key Encapsulation Mechanisms and Data Encapsulation Mechanism (the KEM/DEM paradigm), CPA-Security of KEMs, CPA-Security of Hybrid encryption. El Gamal Encryption and proof of security. El Gamal Key Encapsulation Mechanism, DDH-Based Key Encapsulation Mechanism.

RSA-Based Public Key Encryption and (in)security of plan RSA. A better-than-bruteforce attack on plain RSA. Attacks for short messages and small exponents, attacks for partially-known messages, attacks on messages encrypted multiple times.


Lecture 21: Paddad RSA, Digital Signatures, and Digital Certificates

CCA Security of Plain RSA and a concrete attack exploiting malleability. Padded RSA and its security, PKCS #1 v1.5 and the short-message attack, RSA-OAEP (optimal asymmetric encryption padding). Using RSA as a KEM with a key derivation function.

Digital signatures: formal definition, correctness, and security definitions. Comparison between digital signatures and MACs. The Hash-and-Sign Paradigm and its security. Plain RSA signatures and attacks (signing short messages, signing some arbitrary message, combining signatures). RSA full-domain hash.

Signcryption: the naive encrypt-then-authenticate and authenticate-then-encrypt approaches. Problems of the naive approaches. Secure versions of encrypt-then-authenticate and authenticate-then-encrypt.

Digital Certificates & the Public-Key Infrastructure. Certification authorities and certificate chains. Expiration and revocation of certificates. The Transport Layer Security (TLS) protocol.


Lecture 22: Secret Sharing and Two-Party Computation

Secret sharing. Intuition and motivation. Formalizing secret sharing: access structure and qualifying sets, formal definition, correctness and security definitions. A special case: t-out-of-n threshold secret sharing scheme. Constructing a 2-out-of-2 threshold secret sharing scheme, its security, and a visual interpretation. A generalization to a n-out-of-n threshold secret sharing scheme.

Secret sharing with arbitrary access structures: the Ito–Nishizeki–Saito construction. Drawbacks of Ito–Nishizeki–Saito construction.

The Shamir Secret Sharing scheme. Lagrange interpolating polynomials with real coefficients. Lagrange interpolating polynomials with coefficients in Z_p (where p is prime). Definition of the Shamir secret sharing scheme and its security.

Two-Party computation: definition and the "honest but curious" model. Yao's Garbled Circuit construction: building and evaluating the circuit.


Lecture 23: The Oblivious Transfer Protocol, Multi-Party Computation, and Interactive Proof Systems

The Oblivious Transfer protocol: intuition and construction from the DDH-based KEM and pseudo-OTP.

Multi-party computation: arithmetic circuits and their equivalence to Boolean circuits. Homomorphic properties of the Shamir secret sharing scheme: addition gates and multiplication gates (through recombination vectors).

Reminder of some related complexity classes. The concepts of proofs, provers, and verifiers. A proof for graph isomorphism. Interactive Proof Systems: a physical example, formal definition, the class IP. The role of error probabilities in the definition and probability amplification. Relation between the classes IP, NP, and BPP. An Interactive Proof for a candidate problem that is neither in NP nor in BPP: graph non-isomorphism.


Lecture 24: Zero-Knowledge Proof Systems

Perfect Zero-Knowledge Proof Systems: modelling the notion of "knowledge" (the simulation paradigm), relaxing the requirement on the success probability of the simulator. A PZK Proof System for Graph Isomorphism. Zero-knowledge proofs-of-knowledge.

Designing Computational Zero-Knowledge (CZK) Proof Systems for any problem in NP: the notion of Computational Zero-Knowledge, the Graph 3-Coloring problem, definition of perfectly binding and computationally hiding commitment scheme, constructing a commitment scheme from a PRG, a CZK Proof System for Graph 3-Coloring.

Zero-Knowledge Proof Systems for Languages not in NP: A CZK proof system for graph non-isomorphism. Relation between the classes PZK, CZK, IP, and PSPACE.