2WF80 -- Introduction to cryptology - Winter 2020

Contents Announcements Exams Literature Exercise sheets, notes, and slides Old exams

Tanja Lange
Coding Theory and Cryptology
Eindhoven Institute for the Protection of Information
Department of Mathematics and Computer Science
Room MF 6.104B
Technische Universiteit Eindhoven
P.O. Box 513
5600 MB Eindhoven
Netherlands

Phone: +31 (0) 40 247 4764

The easiest ways to reach me wherever I am:
e-mail:tanja@hyperelliptic.org

This page belongs to course 2WF80 - Introduction to cryptology. This course is offered at TU/e as part of the bachelor's elective package 'Security'. The official page is here.

Contents
Classical systems (Caesar cipher, Vigenère, Playfair, rotor machines), shift register sequences, DES, RC4, RSA, Diffie-Hellman key exchange, cryptanalysis by using statistics, factorization, attacks on WEP (aircrack).

Some words up front: Crypto is an exciting area of research. Learning crypto makes you more aware of the limitations of security and privacy which might make you feel less secure but that's just a more accurate impression of reality and it a good step to improve your security.
Here is a nice link collection of software to help you stay secure https://prism-break.org/en/ and private https://www.privacytools.io/.

Announcements

If you study mathematics, you should have participated in "2WF50 - Algebra" and "2WF70 - Algorithmic algebra and number theory".
If you study computer science or any other program you should have participated in "2DBI00 - Linear Algebra and Applications", "2IT50 or 2IT80 - Discrete structures", and "2WF90 - Algebra for security" before taking this course.
If not you can find some material in the Literature section but note that you are on your own for learning this.

Because of the Covid-19 situation we will not have any in-person lectures. I will provide recorded videos – one video per topic, so several videos per unit – and we'll have live sessions for the exercise hours
I had posted a quiz on Canvas to determine which of the assigned time slots I should keep for the exercise hours (default Thu 5 and 6) and whether there is enough interest in having a Q & A session as well. The outcome was that 68 students replied and 52 prefer Mon 3 & 4 and 52 prefer Thu 5 & 6 (so 36 are happy with both) I have thus decided to keep Thu 5 & 6 as the time slot for the exercises.
36 of the 68 students expressed interested in having a Q & A session in addition to the videos and exercise sessions. I will hold a Q & A sessions on Mondays in block 3 & 4.

The teaching assistants for this course are:

Literature and software

It is not necessary to purchase a book to follow the course.

For some background on algebra see

Some nice books on crypto (but going beyond what we need for this course) are For easy prototyping of crypto implementations I like the computer algebra system Sage. It is based on python and you can use it online or install it on your computer (in a virtual box in case you're running windows).
For encrypting your homeworks you should use GPG/PGP. If you're running linux then GnuPG is easy to install. If you're using windows I recommend using GPG4win; if you're using MAC-OS you can use GPG Suite. We are OK with having only the attachment being encrypted and signed, but for proper encryption of your email you might want to look into Enigmail which works well with Thunderbird.

Examination

30% of the grade is determined by homeworks. There will be four sets of homework during the quarter. You should hand in your homework in groups of 2 or 3. To make sure that you get used to crypto we require solutions to be sent encrypted and signed with GPG/PGP. Each participant must have communicated with the TAs at least once using GPG/PGP. You can find my public key for tanja@hyperelliptic.org on the key servers and on my homepage here. You can find the keys for the TAs linked above or also on the key servers.

The exam will take place on 25 January 2021, 13:30 - 16:30. The format of the exam is Timed exam on Ans Delft without proctoring + video upload after the exam. See blow for details.
The retake is scheduled for April 12, 18:00 - 21:00. The exam accounts for the remaining 70% of the grade.

Here is the cover sheet for the exam, stating what you permitted to do and what not.

Here is a longer explanation of the exam format:
Each student gets an individualized exam, with all numbers generated by a Python script in Ans Delft so that students cannot copy solutions from each other. After the exam each student has to record a video in which they give a short explanation of how they solved the exercises. This video gets uploaded directly after the exam and checked as part of the corrections. This is to ensure that it was the student him/herself writing the exam. The student should also show the student ID at the beginning of the exam. The video will be uploaded to Surfdrive; the upload time does not count against the exam time, but has a separate block of 30 min directly after the exam (shifted appropriately for those with extra time).
To upload your video, use this link. To not use this link to tet this feature, see below for a link for testing.
For students opting out of the video we'll have capacity for about 30 short live interviews right after the exam (5 TAs, 5 min chats, during the 30 min after the exam and twice that if I go for 60 min after of if the opt-outs are balanced between people with extra time and not -- we just cannot handle 130). The live calls are fully ephemeral on jitsi or big-blue-button and not recorded. Please let Tanja know a few days before the exam if you want to go for this.
The numbers will be bigger this year because I need numbers per student. On the plus side you can use your computer for the calculations and you can cut-and-paste between the browser and the system, so that you should never copy a number by hand. Please make sure that your set-up works for this. I don't want to see any mistakes that happen because you mistyped a number.
I do expect your answer to be typed into the Ans Delft system. Do not write on paper and upload a epicure. You may have paper on your table if you like to sketch out things, but still should type up your solution.
To be clear: The exam will be open book open Internet. I don't have the cover sheet for your course ready, but you can see one from a Q1 course here.
A few days before the exam I'll make a test exam available so that you can try out how Ans works. I need to wait for the study administration to add you to Ans for this, so it's not me being the bottle neck here. The test exam is only to understand the interface, it is not replacing the exams from the past years that you should use to practice.
You can test the file upload using this link

Class notes

This section will fill in gradually after the lectures. I'll provide short summaries and links to pictures of the blackboards. The homeworks will be posted here as well.

09 Nov 2020
Please watch

which covers basic concepts of cryptology. See also the slides.

Then watch

to learn about the substitution cipher, Caesar cipher, one-time pad, and Viginere encryption as well as how to analyze them. See also the slides.
I posted a Canvas quiz so that you can check that you decrypted the challenges correctly.

I updated the slides to include what we discussed in the live Q & A session.

12 Nov 2020
Here is the exercise sheet for block 5 and 6: exercise-1.pdf. See also the raw data if paste fails.

If you don't recall how to invert integers modulo other integers I made a video explaining the extended Euclidean algorithm (XGCD)

with slides.

For most of the exercises the solution is obvious when you have it. There are many more pages on the web with tools for cryptanalysis of classical ciphers, e.g. https://www.guballa.de/vigenere-solver, http://www.braingle.com/brainteasers/codes/index.php, http://www.cryptool-online.org.

This video

covers more historical ciphers (Playfair, Hill cipher, column transposition, and very briefly rotor machines. The slides are here.

We currently have one rotor machines from the Cryptomuseum on show in the MetaForum (near the elevator on floor 6 - not that that helps you now, but it's something to look forward to). Check out their extensive website on crypto machines and spy craft. You can also play with an online Enigma.

The second video for this play list introduces basic concepts of stream ciphers and highlights the importance of the IV (initialization vector). To show why it is necessary I review issues with the "two-time pad".

The slides are here.
Stream ciphers are much more practical than the OTP in that the key is much shorter. To encrypt a message, expand the key into a stream of pseudo-random bits and xor those to the message, i.e., treat the stream-cipher output as the one-time pad. To encrypt multiple message it becomes necessary to remember how many bits have been used and either stay in that state or forward by that many positions the next time one uses the cipher. This is impractical. Initialization Vectors (IVs) deal with that problem in that they move the beginning of the stream to a random position. The IV is then sent in clear along with the ciphertext, so that the receiving end can compute the same starting position.

16 Nov 2020
Please watch

to learn about feedback shift registers and how to use them for encryption; the definitions of state, period, pre-period,, ultimately periodic sequences, We also prove the following lemma: If the sequence is periodic with period r and si = si+l for all i then r divides l. The slides are here.

The second video

introduces linear feedback shift registers (LFSRs) and how we draw them, motivates that we want c0=1 (else there is just a delay in output).. The zero state produces the zero sequence, thus the max period is 2^n-1, For two examples it determines all periods that can be generated by those LFSRs. See here for the slides.

The third video

establishes a relationship between state update and a matrix, the state-update matrix. The order of the matrix is a multiple of the period of the LFSR.The video gives an example of how this order is computed and proves a formula for the characteristic polynomial of the matrix. This will be useful for further investigations. See here for the slides.

Slides from the live Q & A session from today are up now.

19 Nov 2020
Here is the exercise sheet for block 5 and 6: exercise-2.pdf. You should really try to solve these exercises and make some conjectures about how orders, degrees, and periods fit together. I'm holding back on some video with explanations to make you solve these. .

I recorded a video to explain public-key cryptography.

You should watch this video to understand the data flow in GPG. You can find the slides here.

The video explains public-key cryptography for encryption and signatures. To submit your homeworks you will need to use PGP/GnuPG. See above for software suggestions. Note that the sender needs the public key of the recipient in order to send a message. This means that you need to send your public Key and those of your team mates to the TAs so that they can reply to you.

The first homework is due on 26 November 2019 at 13:30. Here is the first homework sheet. Please remember to submit your homework by encrypted, signed email to the TAs. Don't forget to include your public key and those of your team mates.

Do not watch this video before you're done with exercise 1 on sheet 2 and have developed some conjectures.

This video takes some of the conjectures that you should have found, turns them into theorems and proves them. Once they are proven, you can use them as facts, so proofs are useful. The video also recalls the definition of irreducible polynomials and Rabin's irreducibly test. See here for the slides.

Hardware design motivates combining short LFSRs, so this video looks at sums of LFSRs.

The video develops some hypotheses about sums of LFSRs and (partially) disproves them. Like for every movie ending with tension, there will be a sequel. Stay tuned for finding out why 21 is missing!
See here for the slides.

23 Nov 2020
We have accumulated a bunch of open problems and hypotheses. This video

cleans everything up so that now we can look at an LFSR and with very few steps determine its properties. The slides are here.

and on discussing PGP installations. Apparently Thunderbird with version 78 has decided to ship it's own PGP implementation which means that the instructions above are no longer correct. There may also be some bad interplay with Microsoft mail servers handling messages. Please test your setup before Thursday by sending an email to me or one of the TAs.

Further reading on finite fields and the mathematical theory of LFSRs is in Lidl/Niederreiter (see literature section), van Tilborg (see literature section), and David Kohel's lecture notes.

You should recognize factors x, x+1, x^2+x+1, x^3+x+1, and x^3+x^2+1 as factors of polynomials. From 2WF50 or 2WF90 you should know Rabin's irreducibly test, else look it up.

LFSRs are used in practice because they are small and efficient, but they need a non-linear component to be secure. I cover three examples (A5/11, A5/2, and SNOW-3G) in this video:

The slides show the LFSRs and some details. I also cover the history. It sounds like the 54 bits were a compromise between countries wanting strong crypto and others wanting weak crypto. One of the first postings on it with some details on the history (note that the original link does not work now) an attack idea for A5/1 by Ross Anderson is from 1994, but many details were missing. The full algorithm descriptions of A5/1 and its purposefully weakened sibling A5/2 were reverse engineered and posted in 1999 by Marc Briceno, Ian Goldberg, and David Wagner. The same group also showed a devastating attack on A5/2, allowing for real-time decryption. Sadly enough, the A5 algorithms allow downgrade attacks, so this is a problem for any phone which has code for it, which is most until recently. Also A5/1 does not offer 2^54 security (54 bits is the effective key length) but only 2^24 (with some precomputation/space). However, A5/2 is broken even worse, in 2^16 computations, with efficient code online, e.g A5/2 Hack Tool.

A nice overview of lightweight ciphers, including more modern and less broken ones is given by Alex Biryukov and Leo Perrin.

In the live session we covered a short introduction to sage, see here for an annotated history of what I typed. you can load this into sage interactively using the load command or starts sage from the command line with the file name as the argument -- but the purpose of the file is mostly to give you a few useful commands so that you can find your way. Also take a look at the cheat sheet I linked fro exercise sheet 2.
The rest of the time was spent on doing some examples of sums of LFSRs see pictures 1 and 2

26 Nov 2020
Here is the exercise sheet for block 5 and 6: exercise-3.pdf.

The cipher we analyzed in the exercise session is RC. I find it quite surprising that such a widely used cipher exhibits properties we can find in an exercise session (well, knowing where to look, of course).
I've recorded a video to summarize the biases and explain some.

The slides are here.

Note that RC4 was a secret design, available only as black box implementation. Soon after it was leaked as "arcfour" weaknesses were found.

Better stream ciphers exist, e.g. the final portfolio from the eSTREAM competition has held up well.

The second homework is due on 03 December 2020 at 13:30. Here is the second homework sheet. Please remember to submit your homework by encrypted, signed email to all the TAs. Don't forget to include your public key and those of your team mates. Do not submit as a singleton, the minimum group size is 2.

30 Nov 2020
The topics for the Q & A session are the videos

The slides from the live session are here. I've also fixed a typo in the math vs. mystery slides that we found during the session.

The first video for today covers cryptographic hash functions

see here for the slides

Cryptographic hash functions need to provide preimage resistance, second preimage resistance, and collision resistance.

If the output of the hash function has n bits then finding a collision takes on average 2n/2 trials (use the birthday paradox to see this) and finding a preimage or second preimage takes on average 2n trials.

We covered design of hash functions using the Merkle-Damgaard construction and how this enables length-extension attacks. We used this as a feature in computing more SHA-1 iterations per second when searching for near collisions. See our write-up for more details. But there are also situations when this property is not welcome. One can deal with it by insisting on a fixed padding in the last block and checking for that.

Short summary of hash functions: MD4 is completely broken; for MD5 it's easy to find collisions, first SHA-1 collisions were computed in 2017 (see https://shattered.io/). SHA-256, SHA-512 and SHA-3 (and the other SHA-3 finalists) are likely to be OK.

The second video is on message authentication codes (MACs)

see here for the slides

Stream ciphers are susceptible to attacks flipping bits in the ciphertext, which cause the same bits to flip in the plaintext. A fingerprint protects against accidental bit flips, but a proper Message Authentication Codes (MACs) need to resist adversarially chosen changes. Communicating parties A and B need an authentication key along with the encryption key. The easiest version of a MAC is to use a hash function to compute cryptographic checksum over the authentication key and the ciphertext. We want to have checksum on the ciphertext for easy and quick rejection of forged packets = Encrypt, then MAC. If you would use the simple MAC you would run into trouble with length-extension attacks. There are many MACs either as standalone constructions ore integrated into a block cipher + mode as in AES-GCM. The video covers HMAC as an example of MAC used in practice..

03 Dec 2020
Here is the exercise sheet for block 5 and 6: exercise-4.pdf.

The exercise session today covered DES as an example of a block cipher. For more details and historical background watch the video:

The slides are here.

Block ciphers can encrypt data in blocks of fixed length n. If you encrypt each block separately your encryption is vulnerable to statistical attacks, A famous example of how weak this is is the ECB penguin. The name for this approach is ECB (electronic code book) mode. The approach means that identical blocks encrypt the same way. See below for better modes.

The video covers some details on DES, including how to decrypt a Feistel cipher. S-box is the non-linear part; the NSA strengthened the S-boxes in the original design (Lucifer) against differential attacks (but made the keys much shorter). In the exercises we saw that small changes in the input lead to big changes in the output. 56 bits for the key is not secure enough! First brute force attack was done with "DES Cracker" for 250k USD. In 2006 a team from Bochum and Kiel built COPACOBANA which can break DES in a week for 8980 EUR (plus some grad-student time).

2-DES takes only 2^56 trials for complete key search. 2-DES is only marginally harder to break than DES, taking 2^57 with a divide-and-conquer approach. Still common use is 3-DES, sometimes with k1=k3. Full 3-DES needs 2^112 steps to break, there are some more weaknesses in 2-key 3-DES.

To encrypt messages longer than one block you need to use a mode of operation. Modes are covered in this video

See here for the slides. Note that the slides have been fixed to cover an error in OFB mode.

More reasonable modes than ECB are CBC,OFB, and CTR. These modes ensure that identical plaintext blocks do not lead to identical ciphertext blocks.

Always make sure to include a MAC!

I have updated exercise 1c to fix the upper bound for i and also extended the hint.>
The third homework is due on 10 December 20i20 at 13:30. Here is the third homework sheet. Please remember to submit your homework by encrypted, signed email to all TAs. Don't forget to include your public key and those of your team mates. Do not submit as a singleton, the minimum group size is 2.

07 Dec 2020
The topics for the Q & A session are the videos

The questions in the live session were about smart brute-force attacks on DES, the number of rounds, and how the compression function in the Merkle-Damgaard construction is instantiated. I pieced the drawings from the live session together with two slides showing the internals of MD4. The slides are here

For the question regarding the number of rounds for DES, I showed a table from Differential Cryptanalysis of the Data Encryption Standard by Biham and Shamir. Note that linear cryptanalysis is a more powerful attack against DES than differential cryptanalysis. If you want to see some nice explanation of linear and differential cryptanalysis, take a look at the Master thesis by Eran Lambooij. This part is purely optional.

New topics for today are in public-key cryptography. You should have watched Public-key and symmetric-key cryptology – or re-watch it now.

As a warm up, watch this video on how to compute exponentiation efficiently

The slides are here

Exponentiation by square and multiply with an l-bit exponent takes l squarings and as many multiplications as the exponent has all bits set to 1.

As a first public-key system we look at RSA. Warning: do not use schoolbook RSA in practice

The slides are here

The video covers
Public-key encryption requires 3 algorithms: Key generation, encryption, and decryption. Signatures also require 3 algorithms: Key generation, signing, and verification.

RSA encryption: public key for RSA is (n,e), private key is (n,d), where n=pq for two different primes p and q, φ(n)=(p-1)(q-1) and d is the inverse of e modulo φ(n). We showed how to encrypt and decrypt and why this works. Attention, this is schoolbook RSA, do not use this in practice.
If you don't remember how to compute modulo an integer or what φ(n) is, now is a good moment to catch up on this.

There are several problems with schoolbook RSA. This video covers just part 1.

The slides are here Note that a typo has been fixed on the slides.

If message and exponent are small reduction modulo n might not happen and the ciphertext is an integer e-th power of the message. Furthermore, we can recover a message that is sent to multiple (at least e) people, if they all use the same small exponent e.
Both of these issues can e sold with padding; the second attack shows that the padding has to be randomized.

10 Dec 2020
Here is the exercise sheet for block 5 and 6: exercise-5.pdf.

I've recorded a short video to recap the Chinese remainder theorem and how to compute solutions.

The slides are here

This video covers some cute attack if the messages are linearly related


The slides are here

Given just two ciphertexts of linearly related messages we can decrypt the message. The same holds for messages related via a known function.

We need to cover formal security notions so that we can say when a system is broken.

The slides are here

Security notions and attack definitions for encryption and signatures:
These formalize what we consider an attack and what powers the attacker has.
In a full break the private key is recovered. For signatures, the attack goal is to forge signatures, this could mean to generate any valid (m,s) pair (existential forgery) or to generate valid (m,s) for a meaningful message m (universal forgery).
For encryption the goal is to recover plaintext from ciphertext;, i.e. to break one-wayness. We typically request that a scheme is so strong that the attacker learns no information about the plaintext from the ciphertext; this is called semantic security. However, this is hard to deal with in practice. An equivalent and more practical security requirement is indistinguishability: the attacker chooses two messages m0 and m1 and is then presented with a ciphertext c which encrypts one of m0 and m1. The attacker wins if he correctly guesses which, i.e., if he can distinguish the ciphertexts. To deal with a 50% chance of guessing, the advantage of the attacker is defined as the extra chance on top of the 50%. See the video and slides for the full formal definition.

The abilities of the attacker vary; for signatures it might be a key-only attack (KOA), a known message attack (KMA), or a chosen message attack (CMA). In the latter two cases the attacker sees valid signature pairs (m,s); in CMA the attacker can choose for which messages he sees signatures.

For encryption the attacker may do a chosen-plaintext attack (CPA) or a chosen-ciphertext attack (CCA). There are two versions of CCA security: in CCA-I the attacker gets to request decryptions of arbitrary ciphertexts until he sees c; in CCA-II the attacker can request decryptions of ciphertexts c' (not equal to c) also after receiving c.

If you really needed another reason to not use schoolbook RSA, here we go. The video also covers the idea behind Bleichenbacher's attack on PKCS#1 1.5

The slides are here

RSA is homomorphic, which defeats some security notions and can mean real attacks (depending on the setting). Schoolbook RSA is not is not OW CCA-II secure, because of the homomorphic property: to decrypt c the attacker can ask for the decryption of c'=c*2^d, obtain m' and get m = m'/2.
The homomorphic property gives existential forgery under KMA: (m1*m2, s1*s2) is a valid signature different from the observed ones. This works as long as the attacker sees at least one message (he can use m1=m2). It also gives universal forgery under CMA: in order to create a signature on m the attacker asks to see a signature on m*2^e. He receives (m^d*2,s) and then obtains a valid signature on m as (m,s/2).
Because schoolbook RSA is deterministic, it is not even CPA secure: the attacker can simply encrypt m0 and m1 himself and compare the results to c..

To make RSA a randomized encryption one uses some padding; however this is also error prone. PKCS#1 v1.5 is a negative example which is broken using Bleichenbacher's attack. Take a look at https://robotattack.org/ for a recent use of Bleichenbacher's attack in practice. You should be able to understand details of the full paper Return Of Bleichenbacher's Oracle Threat. RSA-OAEP is a better padding scheme.

The fourth and last homework is due on 07 January 2021 at 13:30. Here is the homework sheet. At this point you can solve the first part of the exercises, you will have all material necessary by next Thursday.
Please remember to submit your homework by encrypted, signed email to all TAs. Don't forget to include your public keys.

14 Dec 2020
New topics for today are all things RSA.

The live session went a bit different from planned because by tablet crashed and didn't recover for the lecture. :-(
I explained that for IND proofs there is some limit on the message space – in schoolbook RSA we have that messages are positive integers less than n and for RSA with padding the message space will be further restricted. In symmetric cryptography the message length for IND proofs is similarly fixed. In reality this is achieved by adding padding.
Finally we did all the steps of the CRT computation from the "Problems with schoolbook RSA I" slides. I've annotated the sage history for the session.

How does RSA get broken if it's not schoolbook RSA?

The slides are here

See https://factorable.net/) for an internet-wide scan and several factored keys. I was involved in finding a similar case in the RSA keys of Taiwanese Citizen Cards, see https://smartfacts.cr.yp.to/.

Factorization methods: trial division, p-1 method., namedropping of other factorization methods, see also http://facthacks.cr.yp.to/ for descriptions and code snippets.

The next topic is the Diffie–Hellman key exchange

The slides are here

Diffie-Hellman key exchange in different groups, including some insecure ones. CDHP, DDHP, DLP, relations between these problems.

DH has a problem with active man-in-the-middle attacks. Eve can establish communications with A and B and pass messages between them so that each of them is convinced they are securely talking to the other party while Eve gets all plaintext. This does require Eve to stay in the middle of the conversation and decrypt and re-encrypt all messages.

Semi-static DH has A have a fixed key which B knows to be authentic. B picks fresh random values d for each new interaction to get key freshness. If both A and B should be authenticated they can use the triple-DH handshake to combine long-term and short-term keys.

we will see more usage of DLP and DHP on Thursday. For today just one more attack.

The slides are here

BSGS is an algorithm to compute discrete logarithms in a cyclic group with generator g, i.e. given g and h_A =g^a it computes a.
Put m=floor(√n), where n is the order of g. BSGS computes all powers of the generator from g^0=1 up to g^(m-1), these are the baby steps (incrementing by 1 in the exponent). Then it computes S=g^(-m) and checks for each h_A * S^j for j = 0,... whether it is in the list of baby steps; these are the giant steps (moving by m in the exponent). If a match happens, we have g^i=h_A * S^j = g^a*g^(-mj), thus a=i+mj.

17 Dec 2020
Here is the exercise sheet for block 5 and 6: exercise-6.pdf.

I have recorded a short video to give an example of BSGS

The slides are here

In 2016 I wrote some slides for this lecture. You might find them interesting as a different way to explain BSGS.

The second video for today covers ElGamal encryption (mostly for historical purposes) and ElGamal signatures and why they work.

The slides are here

Finally we cover the cost analysis of DLP, CDHP, and DDHP

The slides are here

Any system based on DLP has at most square root of the group order hardness of the DLP. For elliptic-curve groups that's also the best known attack complexity while there are faster attacks on finite-field DLP which reduce the complexity to that of RSA numbers of the same size.

To analyze the hardness of DDH we worked out how we can test whether the DL is even or odd and how to turn this into an attack on DDH that succeeds with non-negligible probability. A way out is to work in subgroups of F_p which have prime order. If you stay on for 2MMC10 you will encounter the Pohlig-Hellman attack, an attack that reduces the security to that of the largest prime-order subgroup, so restricting to it does not give up any security.

Enjoy your holidays. If you want to do some crypto take a look at the old exams (below). Ask on Zulip or email me if you have questions or think you have solutions to old exams (= send me scans of your solutions and I'll send comments back).

04 Jan 2021
In the live session we went through two examples for BSGS and did some more details on the (weak!) case of DH in the additive group of a finite field.
Here are image 1 and image 2 from the live session.

The first video for today covers the KEM-DEM framework

The slides are here

KEM (Key Encapsulation mechanism) is a more modern security notion than public-key encryption, using the public-key part only to generate a shared secret for use i symmetric-key cryptography, then called DEM (Data Encapsulation Mechanism). The video shows how to turn a PKE into a KEM and gives RSA and DH as examples.

The second video is about Shamir secret sharing

The slides are here

Shamir secret sharing: allows to share a secret in a t-out-of-N fashion so that any set of t people can recover it; It works by picking a random degree-(t-1) polynomial with constant term as the secret and giving each user a share (i,f(i)) for non-repeating and nonzero i. Recovering the secret works by simple Lagrange interpolation.

Note that the secret never needs to be re-computed -- for applications in RSA or DH the shares can be applied individually and then only the per-message secrets be combined. Also note that there is no need to ever have the secret -- it can be generated from t shares; these shares are then re-shared in a t-out-of-N fashion.

07 Jan 2021
Here is the exercise sheet for block 5 and 6: exercise-7.pdf.

The first video deals with authenticated key agreement.

The slides are here

The lecture introducing DH had left open the details on how to avoid that Eve can be in the middle. The video first covers the Needham-Schroeder authentication protocol and why it doesn't actually prove to B that he is talking to A. Triple DH or DH together with signatures achieves authentication and key freshness.

The second video is about different types of signatures.

The slides are here

Blind signatures are used in eCash and easy to get from homomorphic RSA signatures. For undeniable signatures Chaum showed a protocol relying on the hardness of the discrete-logarithm problem.

11 Jan 2021

For this round you can ask any question, not just on the material of the last two sessions. We will also do an exercise session on 14 Jan during which you can ask questions about old exams.

We ended up covereing some details on Needham-Schroeder, 3DH, KEMs, blind signatures and undeniable signatures. Here are the pictures from the screenshots:
page 1, page 2, page 3, page 4,


Old Exams

This course was given for the first time in Q2 of 2014. Here are my exams so far