2WF80 -- Introduction to cryptology - Winter 2016

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 MF 6 (except for 12 Dec, when it's in PAV M23) and Thursdays 13:45 - 17:30 in Laplace 1.05. There is a holiday break between Christmas and New year so that there are no lectures between 23 Dec and 08 Jan. All courses will be given in their allocated slots, hence there will be no lectures in the repetition week.

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. Each participant must have communicated with me at least once using GPG/PGP. My key can be found here.
There will be an exam on 23 January 2017, 13:30 - 16:30 (with a retake on April 20, 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 class notes.
The first exam takes place in matrix atelier 1.

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.

14 Nov 2016
Substitution cipher, Caesar cipher, Viginere, one-time pad, Playfair system. Some statements about the number of possible keys for these schemes.
Pictures of white boards are here.

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

For most of the exercises the solution is obvious when you have it. We discussed how to break the Hill cipher given some plaintext-ciphertext pairs and in particular repeated the extended Euclidean algorithm.

In the lecture we discussed the column transposition cipher (see pictures). You can play with it in the C1.3 exercise of the old Mystery Twister if you have Flash Player installed.

I wanted to show an Enigma animation but it didn't work in the browsers I tried. Justin Szanto tweaked a few things and made it work again. You can play with it at his copy of the page. Have fun!
We discussed a bit about rotor machines and cryptanalysis.

One-time pad with bits, and problems with reuse. Try the 4th challenge in the old Mystery Twister to see the reusse problems. Finally, we discussed stream ciphers.
Pictures of black boards are here.

21 Nov 2016
Feedback shift registers and how to use them for encryption; k-th order feedback sequence (=a sequence with k coefficients), 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 black board are here. I was too fast in erasing the board at some point. Take a look at the pictures from last year's lecture.

24 Nov 2016
Here is the exercise sheet for block 5 and 6: exercise-2.pdf.
We summarized the results of exercise 1 to derive some conjectures on the periods and factorization patterns. If you solve the second one, note that for the Fibonacci squence you need to use minus signs to get the characteristic polynomial and that there was a sign error when we derived the result (we need (-1)k and (-1)k-1 on the terms.

Defintion of irreducible polynomials, order/period of a polynomial, Rabin's irreducibility test, period of an irreducible polynomial of degree n divides 2n-1. Order of C matches period of its characteristic polynomial. 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.
We tried to prove that for irreducible characteristic polynomials the period of the polynomial equals the maximum least period of the LFSR. The proof uses generating functions and I got stuck in the order of summation. I stated without proof that if F and G are the characteristic polynomials of (si) and (ti) then (si)+(ti) has characteristic polynomial lcm(F,G).
Further reading on finite fields and LFSRs, including the missing proof, is in Lidl/Niederreiter (see literature section).

Pictures of black boards are here.

28 Nov 2016
Lecture given by Andreas Hülsing.
Concept of public-key cryptography: key generation, producing a keypair (sk,pk); encryption, using pk; and decryption, using sk. Similar set up for signatures. Signatures are used e.g. in your browser.
Recap of number theory background: multiplicative group modulo n, Euler-phi function (examples + general formula), Lagrange's theorem).
RSA cryptosystem: 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. Some examples of how bad schoolbook RSA will come on Thursday.
Security notions of public-key cryptography: semantic security as game between attacker and challenger; the attacker should not have higher probability than guessing in deciding which of two messages m0 and m1 was encrypted, given the messages and one ciphertext. Thanks to Andreas for taking pictures of the black boards.

01 Dec 2016
Lecture given by Christine van Vredendaal.
Here is the exercise sheet for block 5 and 6: exercise-3.pdf

Exponentiation by square and multiply and how many operations this takes, examples; can choose small e but d must be large/random.
More on security notions. 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; schoolbook RSA is not CCA-II secure; RSA OAEP.

The first homework is due on December 08, 2016 at 13:45. Here is the first homework sheet.
Please remember to submit your homework by encrypted, signed email. Don't forget to include your public key for me to reply.

Christine was so nice to make the photos available online.

05 Dec 2016
I couldn't really write, so I showed some slides. The slides are here.

Pictures of black boards are here.

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

Diffie-Hellman key exchange in different groups, including some insecure ones. A good choice is to use the intergers modulo a large prime or elliptic curve crypto (not covered in this class).
CDHP, DDHP, DLP, relations between these problems. Problem with active man-in-the-middle attacks, authenticated DH needs long-term keys.
Semi-static DH, ElGamal encryption, encryption is homomorphic -- asking for (r,2c) can be used to decrypt (r,c). ElGamal signatures and why these systems work. Baby-Step Giant-Step algorithm: any system based on DLP has at most squareroot of the group oder hardness of the DLP.
I wrote slides because I still couldn't write on the board.

12 Dec 2016
Needham-Schroeder authentication protocol and why it doesn't actually proof 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. There is an error on the board for the Lagrange coefficient: the numerator in the product is ji, not jl
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.

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. More modes on Thursday; we quickly covered CBC mode.
Some details on DES, 56 bits for the key is not secure enough! Key schedule take k of 56 bits and turns it into 16 round keys. Rough description of DES and the 16 rounds and why this can encrypt and decrypt with the same circiutry. I still need to explain how the boxes taking ki are instantiated.
The black board pictures are here.

15 Dec 2016
Here is the exercise sheet for block 5 and 6: exercise-5.pdf

More details on DES. S-box is non-linear part and designed to avoid differential attacks. In the exercises we saw that small changes in the input lead to big changes in the output. Quick comment on PRESENT and that it uses a single S-box and on the current standard AES.
Discussion of brute force attacks on DES. 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 with k1=k3 and use k2 with decryption instead of encryption. This needs 2^112 steps to break. Modes of operations: CBC, OFB, CTR; the exercises mentioned issues with CBC used in the POODLE attack; would like to achieve local encryption and decryption and parallelization; CRT has these features; but need large enough counter.

Pictures of black boards are here.

19 Dec 2016
Short discussion of key schedule for DES and exercises 5-7 from sheet 5.

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.
Collisions are problems e.g. for signatures, because the signature is on h(m) instead of on m.

Short summary 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.

Encryption with stream ciphers is malleable -- changing a bit in the ciphertext leads to a decryption in which the same bit is changed. Need extra checksum to achieve integrity. Also want to achieve authenticy.

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. Some namedropping of HMAC, GCM, and Poly1305.

I briefly explained how RC4 works. There will be much more on this in the lecture and exercises on Thursday.

Pictures of black boards are here.

22 Dec 2016
Here is the exercise sheet for block 5 and 6: exercise-6.pdf.

The second homework is due on January 12, 2017, 13:45. 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.

Results from the exercises:
RC4 has a strong bias towards 0 in the second byte. We saw this experimentally and also gave the 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.
I mentioned slides on more biases of RC4 by Daniel J. Bernstein. They are 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.
Comparision of properties of MACs vs. signatures. The most important part is to whom A can prove that the message is from B -- to anybody for signatures and just to herself for MACs. Sometimes the latter is a desired property, see e.g. OTR.

Pictures of black boards are here.

09 Jan 2017
Missing details of LFSRs: generating function S(x) satisfies S(x)=F(x)/f*(x), where * gives the reciprocal, f is the characteristic polynomial and F(x) is a polynomial of degree less than deg(f). The characteristic polynomial is the polynomial of smallest degree with this property. The characteristic polynomial of the sequence {si+ti} is the lcm of the characteristic polynomials of the two sequences. An irreducible polynomial generates a sequence with period equal to its order.

Short summary of factorization of polyomials. Most important part: this is a fast process -- taking polynomial time. Steps are

Pictures of black boards are here.

12 Jan 2017
We spent all hours on the old exams and questions about them.
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