2WF80 -- Introduction to cryptology - Fall 2014

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 potentiaal 9.05. There is a holiday break between Christmas and New year so that there are no lectures between Dec 19 and Jan 4. 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.

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 was an exam on January 19, 13:30 - 16:30 (with a retake on April 13, 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.

10 Nov 2014
Substitution cipher, Caesar cipher, Viginere, one-time pad, Playfair system, Hill cipher. Some thoughts on strenghts and cryptanalysis of these schemes.
Pictures of white boards are here.

13 Nov 2014
Here is the exercise sheet for block 5 and 6 (now with fixed exercses, sorry): exercise-1.pdf.

In the lecture part we had Benne de Weger do a show and tell about his Hagelin BC-38.
I showed some pages about the Enigma by Tony sale. Lots of pages are linked from here, including a simulator for the Enigma. Unfortunately the page only seems to work in Internet Explorer.
Scytale, extended Euclidean algorithm, one time pad with bits, problems with reuse.
Pictures of black boards are here.

17 Nov 2014
Feedback shift registers and how to use them for encryption; n-th order feedback sequence, period, pre-period, ultimately periodic sequences, least period. Linear feedback shift registers (LFSRs), want c0=1, can run backwards, is periodic, max period is 2^n-1, relation to matrix multiplication, order of matrix is divisible by least period, characteristic polynomial of the matrix, characteristic polynomial of the LFSR; factors of the characteristic polynomial.
Further reading can be Lidl/Niederreiter or van Tilborg.
Pictures of white boards are here.

20 Nov 2014
Here is the exercise sheet for block 5 and 6: exercise-2.pdf.
The results are included on the blackboard pictures, it's the only white board in the set. Note that for the Fibonacci squence uses minus signs (check with the way we derived the polynomial from C).

The lecture had a quick tour through finite fields, defining fields, characteristic, irreducible polynomials, (a+b)p=ap+ bp in characteristic p, how to generate extension fields, Fp[x]/f is a field with pn elements if f is irreducible and of degree n; compute inversion in this field Fpn by using XGCD with f.
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.

24 Nov 2014
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). RC4: some history, description, example of key setup. Note the output is S[(S[i]+S[j])] and not S[i]+S[j] as I wrote on the board.
Pictures of white boards are here.
The first homework is due on December 4, 13:30. Here is the first homework sheet.

27 Nov 2014
Here is the exercise sheet for block 5 and 6: exercise-3.pdf.
We used some of the lecture time to present the results from the exercises. RC4 has a strong bias towards 0 in the second byte. This is explained in exercise two: if the third byte of the state equals 0 then the seecond byte is 0, no matter what value the other cells have.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 Chacha12. 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. 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.

01 Dec 2014
Details on DES, Feistel cipher, how to en- and decrypt, 56 bits for the key is not secure enough; confusion and diffusion and how 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. 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.
Pictures of white boards are here.

04 Dec 2014
Here is the exercise sheet for block 5 and 6: exercise-4.pdf.
Modes of operations: CBC, OFB, CTR, mention of GCM. Want to precompute stream and to access blocks without computing decryptions of all preceding blocks.
Message Authentication Codes (MACs): use hash function to compute cryptographic checksum. Want to have checksum on the ciphertext for easy and quick rejection of forged packets; H(k||m) vs. H(m||k). I forgot to mention that H(k||m) allows message extension attacks -- if a is a valid authenticator for message m them by the iterative nature of cryptographic hash functions H(a||x) is a valid authenticator for m||x. Please look up HMAC and GCM.
Pictures of black boards are here.

08 Dec 2014
Lecture given by Jens Bauch.
Concept of public-key cryptography, some recap of number theory background (multiplicative group modulo n, Euler-phi function, Euler's theorem), public key for RSA is (e,n), private key is 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. First problem with schoolbook multiplication: we can recover a message that is sent to multiple people, if they all use the same small exponent.
Jens scanned his class prep for you instead of pictures.

11 Dec 2014
Here is the exercise sheet for block 5 and 6: exercise-5.pdf.
More issues with schoolbook RSA: can decrypt linearly related messages; RSA is homomorphic; security notions, schoolbook RSA is not CCA-II secure; RSA OAEP.
Jens scanned his class prep for you instead of pictures.
The second homework is due on December 23, 12:00. Here is the first homework sheet.
Additional comments: I've tweaked the description of 1 and 1b to make things clearer of what is and what is not possible and included a part with concrete numbers. Please state in detail one XGCD computation in 2 and the XGCD computation in 3.

15 Dec 2014
RSA-OAEP and why it protects against attacks using the homomorphic properties of RSA; n has at least 1024 bits, so no shortage of space for message, randomness, and padding. Use of RSA in TLS (example of DigID ciphersuite). Security relies on strength of the used encryption systems and on the security of the certificate (cryptographic strength and operational security).
Diffie-Hellman key exchange, use in TLS, example of google.com for use of DH for encryption, ephemeral vs. static DH, ephemeral can mean time-based or mean connection-based, two bad choices for g and the operation; a good choice is to use the intergers modulo a large prime.
Pictures of white boards are here.

18 Dec 2014
Here is the exercise sheet for block 5 and 6: exercise-6.pdf.
Some hints on exams; there will be a test exam ready by Jan 5. For now you can try the old exams for the masters course Crypto I but note that those students know more tools and can use books during the exam.
Computational and Decisional Diffie-Hellman problem (CDHP/DDHP), Discrete Logarithm problem, relations between these problems. ElGamal encryption, DSA signatures (as example of ElGamal signatures) and why these systems work, typical sizes for primes and group orders, Baby-Step Giant-Step algorithm, any system based on DLP has at most squareroot of the group oder hardness of the DLP. Problems with ElGamal encryption -- e.g. (r*g, c*HA) is another encryption of m. DSA is completely broken if a nonce becomes public or is reused. Check out the exam from Jan 28 2011 for Crypto I to see an exercise to find out.
Pictures of black boards are here.

05 Jan 2015
Repetition of some background on DLP systems. 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.
Undeinable signatures and disavowal protocol based on Chaum and van Antwerp, with example.
Pictures of white boards are here.

08 Jan 2015
Lecture given by Jens Bauch.
For the exercise part please do exercise-6 from last week or work on the test exam.
Repetition of finite fields and whatever the students want more explanations on. This is the last lecture.

12 and 15 Jan 2015
No lectures.

Old Exams

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