Messages

Welcome to the course TEK4500 Introduction to Cryptography Fall 2020!

This is the main page for the course. Here you will find course information and any announcements I make for the course, as well as links to lecture slides, recordings, problem sets, and any other material. So please check it regularly. There is also a Canvas page for the course, but we will only use it to publish solutions to home work problems, as well as discussions for the course.

 

 

Published Dec. 16, 2020 9:55 AM

Update 2: the grades are now available (for real this time!) on StudentWeb.

Update: it turns out that a few more buttons must be pushed before the grades become available. Sorry for the false promise. Hopefully the grades will become available soon.

The grading is now done and should be available to you in Inspera.

I've also updated the solution file on Canvas to also include the grading guide for the exam.

Generally, I think you did very well on the exam, and my worry that it was too hard turned out to be unwarranted.

Again, thank you all for taking the course, and have a safe and happy holiday!

Cheers,

H?kon

Published Nov. 25, 2020 10:57 PM

The solutions to the exam are now posted on Canvas. While the exam might have been on the more challenging end of the scale, I hope you also found some of the problems interesting.

Some comments based on the questions I received during the exam:

  • Unfortunately, the hint for Problem 5 was missing in the problem description on Inspera. I became aware of this midway through the exam and posted a comment about it here. Hopefully everyone got it.
  • Problem 6 and 7 had some ambiguities in their descriptions, but hopefully it was still possible to understand what was being asked. 

The above points will be taken into consideration during the grading process. An updated solution with a detailed grading rubric will be posted once the grading is done.

------------------------------------------------------------------------------------

This marks the end of the course and I hope you enjoyed it. I...

Published Nov. 25, 2020 11:19 AM

The hint for Problem 5 is missing in the problem text in Inspera. Please refer to the full text PDF to see the hint for Problem 5.

Here are some clarifications on some of the specific exam questions:

  • In Problem 4, the nonce is not considered part of the ciphertext. Thus, if you send (N, C), where N is the nonce and C is the ciphertext output by Sigma, then you don't have to worry about this breaking the nAE security of the scheme. This is implicitly encoded in the nAE game given in the text, but I just wanted to make this clear.
  • In Problem 5 (on Inspera) there is a missing A in the sentence: "... (assuming is not taking exponential time). ".
    The correct should be: "...(assuming A is not taking exponential time).
  • Also in Problem 5, to clarify: A is only able to solve the RSA-problem ...
Published Nov. 17, 2020 11:22 AM

Hi everyone. 

Lecturer H?kon Jacobsen will arrange a digital "tr?sterunde" in Zoom, during the examination time. (Link below) H?kon will make a break out room for each student. 

 

Topic: TEK4500 - Exam questions

Time: Nov 25, 2020, 09:00 - 13:00 AM, Oslo

 

Join Zoom Meeting:

https://uio.zoom.us/j/68085853710

 

Documentation on how to use Zoom can be found here:

/english/services/it/phone-chat-videoconf/zoom/

Published Nov. 16, 2020 1:49 PM

General rules:

  • The exam time is 4.5 hours. 
  • All examination support materials are allowed (eg textbook, online resources, mathematical software, etc.).
  • It is not allowed to collaborate or communicate with others about the assignments during the exam.
  • You can be selected for a control interview on your examination answer, in order to determine your ownership to the answer. This discussion will not affect the grade, but can lead to the Department issuing a suspicion-of-cheating case. Read more about what we consider to be cheating on UiO's website: /english/about/regulations/studies/studies-examinations/routines-cheating.html
  • Otherwise, the information from the MN F...
Published Nov. 14, 2020 3:32 PM

As mentioned in the last lecture (November 3), I will give a recap lecture on November 17. Currently I have no fixed plans for this lecture, and intend to keep it pretty free-format depending on your wishes. Please use this opportunity to ask about anything that you want me to repeat or clarify.

I've created a Padlet document were you can post suggestions for the lecture (anonymously).

Published Nov. 14, 2020 3:19 PM

I have now made some old exams available on Canvas. However, be aware that previous years and lecturers may have covered and emphasized different things from what we have done this year, so not all problems may be equally relevant.

Published Nov. 7, 2020 5:29 PM

The midterm assignment has now been graded and posted on Canvas together with the proposed solution. Please read the feedback the TA has provided for your submission.

 

If you have taken TEK4500 previously, but would like to retake the exam this year, please send me an email as soon as possible.

Published Oct. 27, 2020 12:03 AM

Next lecture is going to cover public-key encryption and the corresponding security definitions (IND-CPA, IND-CCA). We also going to look at some concrete schemes, namely ElGamal and RSA. This is covered in Chapter 11 and Chapter 10.3 in [BR].

Published Oct. 18, 2020 12:40 PM

I've prepared a midterm evaluation survey (link found on Canvas). If you have the time, please add your opinion about the course so far. I will be very grateful for any feedback I get that can help make the course better. The survey is anonymous.

Regarding the final exam, as you might already have heard, due to the Covid-19 situation there will be no on-campus exam this  fall. Thus, the exam in TEK4500 will be a digital home exam. I'm currently planning for a 4-hour exam on the same date as the originally planned exam, using the Inspera examination tool. However, this is subject to change, and a 1-week home-exam is also a possibility. I will return with the final confirmation once I have it.

Published Oct. 13, 2020 10:26 PM

During today's lecture (Lecture 8, October 13), a student asked whether the generic DLOG algorithms are guaranteed to find the discrete logarithm. I said that the Pollard-rho algorithm is probabilistic and has a chance of failure. However, I don't think I actually answered the question for the baby-step giant-step algorithm! So here it is: baby-step giant step is guaranteed to succeed. I've written a 0.5-page note describing the baby-step giant step in a little more detail here. The included figure should explain why it always succeeds.

Published Oct. 12, 2020 12:31 AM

Next lecture (October 13) we'll start looking at the details of asymmetric cryptography, which was already hinted at in last week's guest lecture.  From [BR] I recommend to read Chapter 9 (minus Section 9.4) and Chapter 10.1-Chapter 10.2. This material may feature some mathematics you might not have seen before, namely group theory, hence I strongly recommend you to read it carefully. 

Group theory is a really fascinating and deep subject, with an enormous number of connections to other parts of mathematics. If you want a more high-level and conceptual introduction to group theory, I highly recommend you to watch the following incredible presentation of the topic: https://www.youtube.com/watch?v=mvmuCPvRoWQ

Published Sep. 29, 2020 9:53 PM

Next week (Tuesday 6. October) there will be a guest lecture in TEK4500. Martin Strand PhD, is a researcher at the Norwegian Defence Research Establishment (FFI) and works on various topics within the field of cryptography. I hope as many as possible will be able to attend.

After the lecture the midterm assignment will become available on Canvas from 17:00, October 06. This is a home assignment and is due October 20, 23:59 (2 weeks). Please submit your solution in PDF formatonly on Canvas. I highly recommend to write-up your answer using LaTex. I will make a LaTex template file available together with the assignment which you are encouraged to use. There are multiple resources online you can consult if you've never used LaTex before, e.g. this one from UiO (some in Norwegian, some in English)....

Published Sep. 20, 2020 11:02 PM

Some students asked whether I could publish the topics and recommended reading for the upcoming lectures some days in advance. So here are the topics and recommended readings for the next two weeks.

  • 22.09: Authenticated encryption (AE). Alas, the chapter on AE in the [BR] book has not been written yet, and the other sources that cover AE are either: a bit too short and using different notation [Rosulek]; a bit too advanced and using different notation [Boneh & Shoup]; not freely available [Katz & Lindell], [Aumasson]. Thus, there are currently n...
Published Sep. 20, 2020 5:24 PM

Recently, a new highly critical Windows vulnerability was discovered which affects the Active Directory domain controller (essentially the main "gatekeeper" to access a Windows network). The fun part about this vulnerability is that it is solely due to the bad/wrong usage of cryptography. In fact, it goes straight to what we have talked about in lectures 3 and 4:

  • Using encryption instead of MACs in order to achieve integrity/authentication.
  • Misusing the requirements of the chosen encryption primitives (using all-zero IVs when a new random IV is required for each encryption).
  • Exploitation of the malleability of an encryption scheme not designed for integrity.

In particular, the exploit targets a mode-of-operation which we did not cover in class called Cipher feecback (CFB) mode. However, it share...

Published Sep. 15, 2020 12:07 AM

Please don't distribute further.

Published Sep. 9, 2020 8:06 PM

With your newfound knowledge of IND-CPA, you should now be able to answer why the seemingly innocuous change to CTR$-mode suggested in this crypto.stackexchange.com question is actually not a good idea! Try to figure it out yourself before looking at the answer.

Published Sep. 8, 2020 1:18 AM

Some students asked for longer worked examples to see how we calculate the advantage of an adversary, so I've now updated the solution to Problem set 2 to include a veeeery detailed calculation for question 2.a). Note that this level of detail is not something which is usually done (nor is expected of you), but I've tried to include all the steps that we implicitly do in our head .

While all these calculations might seem intimidating, they are in fact quite routine once you have seen and done a few of them yourself.

NOTE: in the previous version of the file, there was a mistake in the answer to question 2.a): it said 2^(2n+1), but it should have been 2^(n+1).

Published Sep. 2, 2020 7:18 PM
  • In Lecture 2 I mentioned the T-table approach to implementing AES, where the whole round function is basically just a bunch table lookups from a few precomputed tables. Here's a real-world example of this implementation strategy: https://github.com/libtom/libtomcrypt/blob/develop/src/ciphers/aes/aes_tab.c
  • Leo Perrin has some really interesting findings regarding the design of the S-box used in the Russian-standardized block cipher Kuznyechik (link). TL;DR: basically, the designers of Kuznyechik claim that it was chosen at random from the set of all possible invertible 8-bit S-boxes (which has what size?). However, Perrin has shown that this is veeeeeeeeeeeery unlikely (like 1 in 21601 chance). Instead, th...
Published Sep. 2, 2020 6:46 PM

Lecture 2 (including recording) + Problem set 2 is now available here. Unfortunately, the recording is again only capturing my presenter view, and not what was shown on the projector screen. For some reason, the recording software would not allow me to record the external screen. While I will try to investigate how to avoid this issue, we might have to live with it for the rest of the semester.

Published Sep. 2, 2020 6:45 PM

The (proposed) solutions for Problem set 1 are now available on Canvas under "Files". Please to do not distribute them further.

I realize now that we will probably only use Canvas for two things: problem set solutions and discussion forum. Everything else I will make available on the semester page.

Published Aug. 26, 2020 8:39 AM

In Lecture 1 I made the claim that no symmetric encryption scheme can have perfect privacy (one-time or otherwise) if the key space is smaller than the message space. In this note I provide a proof of this claim.

 

Published Aug. 25, 2020 9:32 PM

In lecture 1 I gave the following puzzle:

Suppose a group of friends are playing a game of Where's Waldo? where the first person to spot Waldo gets $10. However, the remaining players want to continue the game after the first player spots Waldo (with the second player finding Waldo maybe getting $5, and so on), so the winner shouldn't actually reveal where Waldo is!

How is this possible? That is, how can the winner convince the others that it actually knows where Waldo is (and thus should be paid the $10), but without spoiling the game for the rest?

Published Aug. 25, 2020 9:16 PM

The slides from lecture 1 are now available (see course schedule). The recording of the lecture is also available. Unfortunately, there are a few issues with it:

  • I managed to capture the wrong screen! So you only get the presenter view, not the actual presentation as shown on the canvas. But hopefully you should be able to make out what I'm presenting anyway.
  • When answering some questions from the audience I answered by writing on the blackboard in the room, totally forgetting that it would not be visible on the recording.

I will try not to make these mistakes for the next lecture. For those watching the recordings, please let me know if there is anything else that needs to be improved.

Problem set 1 is now also available. I highly encourage you to work on these problems. Good luck.

Published Aug. 17, 2020 5:26 PM

Lectures: Tuesdays 14:15-16:00 + 1 hour course work (voluntary) in Lille Auditorium in Kristen Nygaards Hus. Video recordings of the lectures (voice + screen capture) will be available on Canvas after the lectures.

Course literature: the main source for the course will be the freely available lecture notes Introduction to Modern Cryptography[BR], by Mihir Bellare and Phil Rogaway. Previous years used the textbook Understanding Cryptography [PP], by Christof Parr and Jan Pelz, and you are welcome to consult this text as well; however, you are not required to buy it! These two sources cover m...