2WF80 -- Introduction to cryptology - Fall 2015

Contents Announcements Exams Literature Pictures 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 optional 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/.

Announcements

You should have participated in "2WF50 - Algebra" or "2WF90 - Algebra for security" before taking this course. If not you can find some material in the Literature section.

All lectures take place Mondays 10:45 - 12:30 in multimedia paviljoen zaal 1 and Thursdays 13:45 - 17:30 in flux 1.12. There is a holiday break between Christmas and New year so that there are no lectures between Dec 18 and Jan 3.

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 cryptoimplementations 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. I'm OK with having only the attachment encrypted, 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 two sets of homework during the quarter. You may hand in your homework in groups of 2. To make sure that you get used to crypto I require solutions to be sent encrypted with GPG/PGP. My key can be found here.
There will be an exam on January 18, 13:30 - 16:30 (with a retake on April 11, 18:00 - 21:00) which accounts for the remaining 70% of the grade. You may use a simple (non-programmable) calculator but no cell-phones or other devices containing calculator applications. You may not use books or your classnotes.

Here is a test exam. Note that the CRT exercise would have somewhat smaller keys for the exam.

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 2015
Substitution cipher, Caesar cipher, Viginere, one-time pad, Playfair system, Hill cipher. Some statements about the number of possible keys for these schemes..
Pictures of white boards are here.

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

I wanted to show an Enigma animation but it doesn't work in the browsers I tried. Please check whether http://www.codesandciphers.org.uk/enigma/emachines/enigmacn.htm works for you. It should show exactly the enigma and not a long page with lots of individual pictures. If it works, try clicking on things.

In last year's lecture part we had Benne de Weger do a show and tell about his Hagelin BC-38. He has it in his office; maybe we can manage a viewing at some point.
In the lecture we covered the extended Euclidean algorithm for computing modular inversion and did part of exercise 6b. Other systems we covered: scytale, column transposition cipher, the one-time pad with bits, and problems with reuse. Try the 4th challenge in the old Mystery Twister to see the reusse problems.
Pictures of black boards are here.

16 Nov 2015
Feedback shift registers and how to use them for encryption; n-th order feedback sequence, period, pre-period, ultimately periodic sequences, Linear feedback shift registers (LFSRs), want c0=1, can run backwards, is periodic, max period is 2^n-1, relation to matrix multiplication. characteristic polynomial of the matrix.
Pictures of white boards are here.

19 Nov 2015
Here is the exercise sheet for block 5 and 6: exercise-2.pdf.
The results for the first round of exercises are included on the blackboard pictures. If you do the second one, note that for the Fibonacci squence you need to use minus signs to get the characteristic polynomial. (check with the way we derived the polynomial from C).

Irreducible polynomials, order of matrix is divisible by period, characteristic polynomial of the LFSR; factors of the characteristic polynomial.
Further reading on finite fields in Lidl/Niederreiter or van Tilborg.
Order of a polynomial and why it is defined; some examples using the characterisitc polynomials from the exercises; this order matches the order of the matrix C -- because f is C's characteristic polynomial; if f is irreducible of degree n its order divides 2n-1.

Pictures of black boards are here.

23 Nov 2015
I was late, thanks to NS having a defect train and no plan of how long it would take (or rather, optimistic ideas ...)

Proof that for irreducible characteristic polynomials the order of the polynomial equals the maximum least period. The proof uses generating functions and along the way we showed that if f and g are the characteristic polynomials of (si) and (ti) then (si)+(ti) has characteristic polynomial lcm(f,g).

I did not get around to giving details about RC4. Please read up on it. I would have covered what is stated on the Wikipedia page under Description; we will cover the (in)security on Thursday. (And next time tell me when we still have 13 min and the clock is off).
Pictures of white boards are here.

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

The first homework is due on December 3, 13:30. Here is the first homework sheet. Please remember to use PGP.

Results from the eexercises:
RC4 has a strong bias towards 0 in the second byte. Check exercise 2 (also homework) for an explanation. The first byte has a strong bias towards the first key byte unless the first key byte it zero. RC4 does not provide for refreshing the key stream, so one needs to remember the last values for j and i. WEP needs a place to put some per connection data and uses key bits for that, so we get the known biases plus known key bits plus known plaintext/ciphertext pairs. Aircrack uses these to break WEP encryption. The slides on more biases of RC4 that I showed are by Daniel J. Bernstein and available here.
History of stream cipher development; check out the cell phone ciphers A5/1 and A5/2. For good choices check out Salsa20, Trivium, and Chacha20.
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.
Here is the more detailed summary of what I wanted to say about the state of hash functions: MD4 is completely broken; for MD5 it's esasy to find collisions, we expect to see SHA-1 collisions any day now. SHA-256, SHA-512 and SHA-3 (and the other SHA-3 finalists) are likely to be OK.
There was a lot of namedropping today; please check out the detailed descriptions online and remember the big picture of what the respective functions are used for.

Pictures of black boards are here.

30 Nov 2015
Block cipers. ECB (electronic code book) mode encrypts each block separately, this means that identical blocks encrypt the same way. A famous example of how weak this is is the ECB penguin.
Details on DES, 56 bits for the key is not secure enough! Three levels of details on DES, general Feistel cipher, how to en- and decrypt. Concepts of confusion and diffusion, The epansion and S-box design of DES achieves these. 2-DES only marginally harder to break than DES; use 3-DES with k1=k3 and use k2 with decryption instead of encryption. Some discussion on brute force attacks on DES, and meet-in-the middle attacks.
Pictures of white boards are here.

03 Dec 2015
Here is the exercise sheet for block 5 and 6: exercise-4.pdf.
Quick namedropping of AES and Present
Modes of operations: CBC, OFB, CTR; the exercises mentioned issues with CBC used in the POODLE attack; would like to achieve local encryption & decryption and parallelization; CRT has these features; but need large enough counter.
Message Authentication Codes (MACs): easiest version is to use a hash function to compute cryptographic checksum. Want to have checksum on the ciphertext for easy and quick rejection of forged packets = Encrypt, then MAC. A message from B authenticated with a MAC can convince A but not C that it really originated from B.
Please look up HMAC, GCM, and Poly1305.
There are several possible issues depending on how the hash function H is designed. Many hash functions work in rounds using a compression function which takes in blocks of the input in a way that means that if H(m) and H(m') collide then H(m|x) and H(m'|x) collide for any x, e.g. if H(m1|m2|m3)=H(H(m1|m2)|m3). If E can find another ciphertext c' which collides with c and such a hash function is used then E can use B's valid tag H(c|k) as a tag for H(c'|k) even though she doesn't know k. If the unknown k comes first then H(k) and H(k) trivially collide but put the hash function in an unknown inital state, so havin a collision on H does not break the system.
At the same time, for such a hash function the authenticator a=H(k||c) can be used to compute a'=H(a|x) which is is a valid authenticator for c||x.
Pictures of black boards are here.

07 Dec 2015
Concept of public-key cryptography, some recap of number theory background (multiplicative group modulo n, Euler-phi function, Lagrange's theorem), 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); encryption, decryption, sign, verify. Attention, this is schoolbook RSA, do not use this in practice. For functionality (and security) we want to sign h(m) and not m.
Exponentiation by square and multiply and how many operations this takes, examples; can choose small e but d must be large/random.
Pictures of black boards are here.

10 Dec 2015
Note: no lectures on Dec 10. Please solve the exercises from exercise-5.pdf and watch two of the videos from PSC (once they are onlie).

14 Dec 2015
Lecture given by Henry de Valence.
Attack on RSA using gcd computation. First problem with schoolbook multiplication: we can recover a message that is sent to multiple people, if they all use the same small exponent. More issues with schoolbook RSA: can decrypt linearly related messages; RSA is homomorphic; security notions, schoolbook RSA is not CCA-II secure; RSA OAEP.
Henry was so nice to make the photos available online.

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

Diffie-Hellman key exchange, CDHP, DDHP, DLP, relations between these problems. Problem with active man-in-the-middle attacks, authenticated DH via signatures or triple-DH, semi-static DH, emphemeral DH (ephemeral can mean time-based or mean connection-based), a good choice is to use the intergers modulo a large prime or elliptic curve crypto (not covered in this class). ElGamal encryption, encryption is homomorphic, DSA signatures (as example of ElGamal signatures) and why these systems work. DSA is completely broken if a nonce becomes public or is reused. Baby-Step Giant-Step algorithm: any system based on DLP has at most squareroot of the group oder hardness of the DLP.
Pictures of black boards are here.

The second homework is due on Januar 07, 2016 at 13:30. Here is the second homework sheet.
Please remember to submit your homework by encrypted, signed email and that this time the other team member should submit. If you're in a team of three have the third person send me some additional encrypted email.

04 Jan 2016
Lecutre given by Gustavo Banegas.
Repetition of some background on DLP systems and the BSGS algorithm. Not that taking m as floor or ceiling of the square-root of the group order both work.
Needham-Schroeder authentication protocol and why it doesn't actually prove to B that he is talking to A. 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; 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.
Factorization algorithms: Fermat factorization, p-1 method.
Gustavo was so nce to take pictures of the white boards here.

07 Jan 2016
This session (blocks 5-8) will be given jointly by Gustavo and Henry as a 'ask-me-anything session'. Please prepare questions and try to solve the practice exam during this time or try the rest of the exercises from sheet 6.
This is the last lecture, see you all on Jan 18!

11 and 14 Jan 2016
No lectures. Please watch YouTube video and take a look at ECCHacks webpage and slides to learn a bit about elliptic curves. This will not be part of the test but is good for you.
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).

Old Exams

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