Cryptography and Protocol Engineering

Aims

We all use cryptographic protocols every day: whenever we access an https:// website or send a message via WhatsApp or Signal, for example. In this module, students will get hands-on experience of how those protocols are implemented. Students start by writing their own secure messaging protocol from scratch, and then move on to more advanced examples of cryptographic protocols for security and privacy, such as private information retrieval (searching for data without revealing what you’re searching for).

Syllabus

This is a practical course in which the first half of each of the 2-hour weekly sessions is a lecture that introduces a topic, while the second half is lab time during which the students can work on their implementations, discuss the topics in small groups, and get help from the lecturers. The module is structured into three blocks as follows: 

1. Cryptographic primitives (2 weeks). Using common building blocks such as symmetric ciphers and hash functions. Implementing selected aspects of elliptic curve Diffie-Hellman and digital signatures. Protocol security, Dolev-Yao model, side-channel attacks. 
2. Secure communication (3 weeks). Authenticated key exchange (e.g. SIGMA, TLS), password-authenticated key exchange (e.g. SPAKE2), forward secrecy, post-compromise security, double ratchet, the Signal protocol. 
3. Private database lookups (3 weeks). Lattice-based post-quantum cryptography, learning with errors, homomorphic encryption, private information retrieval. 

In each block, students will be given a description of the algorithms and protocols covered (e.g. a research paper or an RFC standards document), and a code template that the students should use for their implementation. The implementation language will probably be Python (to be confirmed after the practical materials have been developed ). Students will also be given a set of test cases to check their code, and will have the opportunity to test their implementation communicating with other students’ implementations. Finally, for each block, students will write and submit a lab report explaining their approach and the findings from their implementation.

Objectives

On completion of this module, students should:

• Understand that cryptography is not magic! The mathematics can look intimidating, but this module will show students that they needn’t be afraid of cryptography.
• Gain appreciation for the complexity and careful implementation of real-world cryptography libraries ,and understand why one should prefer vetted implementations.
• Be familiar with the mathematical notation and concepts commonly used in descriptions of cryptographic protocols, and be able to understand and implement research papers and RFCs in this field.
• Be comfortable with cryptographic primitives commonly used in protocols, and able to correctly use software libraries that implement them.
• Have gained hands-on experience of attacks on cryptographic protocols, and an appreciation for the difficulty of making these protocols correct.
• Have been exposed to ideas and techniques from recent research, which may be useful for their own future research.
• Have practised technical writing through lab reports.

Assessment

Students will be provided with code skeletons in one or two different programming languages (probably Python, maybe Rust) to avoid them struggling with setup issues. For each assignment, students are required to produce a working implementation of the protocols discussed in the course, using the programming language and skeleton provided. Here, “working” means that the algorithms are functionally correct, but they are not production-quality (in particular, no side-channel countermeasures such as constant-time algorithms are required). For some primitives (e.g. symmetric ciphers and hash functions) existing libraries should be used, whereas other cryptographic algorithms will be implemented from scratch. Students should submit their code as a Docker container that can be run against specified test cases. 

After each of the three blocks, students will be asked to submit a lab report of approximately 2,000 words along with their code for that block. In the lab report, the students should explain how their implementation works and why it is correct, as well as any findings from the work (e.g. any limitations or trade-offs they found with the protocols). The report structure and marking scheme will be specified in advance. The lab reports provide an opportunity for students to provide critical insights and creativity. For instance, they might compare their implementation with existing real-world implementations which provide additional features and guarantees. 

Each of the three lab reports (along with the associated code) will be marked, forming the basis of assessment, and feedback on the reports will be given to the students before the next submission is due, so that students can take the feedback on board for their next submission. Of the three reports, the worst mark will be discarded, and the other two reports each contribute 50% of the final mark. As such, students might decide to submit only two reports. 

Students may discuss their work with others, but the implementations and lab reports must be individual work.

Recommended reading

Textbook: Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography (3rd edition). CRC Press, 2020.

The textbook covers prerequisite knowledge on cryptographic primitives, such as ciphers, MACs, hash functions, and signatures. This book is also used in the Part II Cryptography course. For the protocols we cover in this course, we are not aware of a suitable textbook; instead we will use research papers, lecture slides, and RFCs as resources, which will be provided at the start of the module.