ModCrypt Exam 2020-05-15

• Subject: Introduction to Modern Cryptography from WS 2019/20
• Date: 2020-05-15
• Type of Exam: oral Exam via video conference software + iPad + Apple Pen (my private ones) for drawing
• Examiner: Prof. Dr. Dominique Schröder
• Grade: 1.0
• Undergone Preparation:
  • active collaboration in lecture/exercises during the semester
  • preparation before exam was split over multiple weeks since it was unknown when exams could be conducted again due to COVID-19
  • in total perhaps 4-5 weeks of preparation side-to-side to my regular studies (would perhaps correspond to 2.5-3.5 weeks of full-time studying depending on your personality)
  • I focussed very much on relating things, e.g. how do OWFs induce PRFs (minicrypt)? Why do we need this or that?
  • Nonetheless, I have still done some of standard reduction proofs (e.g. for DH or El-Gamal). However, I did not learn, for instance, hybrid proofs by heart. I could very much tell about the intuition and sketch the proof, but would probably end up in indices hell when I would have been asked mid-exam :)
• Evaluation
  • The exam is fair! You can achieve 1.0 even with errors. As Prof. Schröder says themself, it's about understanding things and not so much about learning everything by heart. Of course you have to know all main definitions and security properties, but, for instance, I forgot this one construction of a CCA-secure KEM. I could replicate it with some hints mid-exam and hence it was not counted against me.
  • If you don't know something, keep thinking aloud. Prof. Schröder will work with you towards answering the question correctly.
  • It's crucial to be able to draw something! If you also conduct the exam virtually via video conference software, be sure to have/borrow a tablet/convertible with a pen!

• What did you like the most?

DH Key Exchange Protocol and how it induces the El Gamal public-key enc. scheme

• Okay, show me what a key exchange protocol is

I drew Alice and Bob and how they shared some (non-further-specified) messages and at the end agreed on a key K. Then, I also explained its security notion and drew the game the adversary plays (gets a transcript, the actual key OR a faked key etc.)

• What is a key exchange protocol good for?

All private-key enc. schemes implicitly assume a key being shared off-band somehow. You can use a key exchange protocol for doing this.

• Exchanging a key without somebody else being able to recover that sounds magic, no?

Yes, but I can give you once instance of such a protocol. I drew the DH protocol.
[editor's note: the protocol assumes an authenticated channel!]

• Why is it secure, though?

Well, it's funny because it's by DDH-hardness which was created exactly to model that.

• How does it give rise to the El Gamal enc. scheme now?

I gave definitions for Gen, Enc, Dec from El Gamal and elaborated which part originated from which part in the DH protocol:
Gen: subsumes what Alice initially does in DH; pk is what Alice transmitted to Bob; sk is Alice's internal stateEnc
Enc: amounts to Bob completing DH and blinding a message with the obtained key
Dec: amounts to Alice completing DH and recovering the message

• What security does El Gamal achieve?

IND-CPA

• Why not IND-CCA? What even is IND-CCA?

I drew the IND-CCA game in sloppy form (always decryption oracle).

• But then decryption of c_b would be trivial?

Well, actually I meant: in phase 1 arbitrary access to dec. oracle, in phase 2 restricted access

• Okay, why is El Gamal not IND-CCA-secure?

You can mall with the ciphertext. [editor's note: no details were asked, but I think the counterexample is simple enough to know!]

• How does one get an IND-CCA-secure scheme?

By combining MAC and IND-CPA-secure scheme to achieve Authenticated Encryption. [editor's note: I mistakenly switche to the private-key world.]

• But that's in private-key world, is there something analogous in public-key world?

Uh, possibly we could replace MAC by public-key signatures and IND-CPA in private-key sense by IND-CPA in public-key sense, and then use the Encrypt-then-Auth/Sign idiom. [editor's note: no, that's not that easy, carry on reading why]

• No, that's not that easily possible, let's see why. Prof. Schröder then drew the supposed `Enc(pk, m) := Sign(sk_{sig}, Enc_{cpa}(pk_{cpa}, m))`. Do you see why now?

Ah, we cannot access sk_{sig} since Enc(pk, m) must be possible with pk alone.

• Right, so let's adapt to `Enc(pk, m) := (sk_{sig}, pk_{sig}) ← GenSig, return Sign(sk_{sig}, Enc_{cpa}(pk_{cpa}, m))`.

But then I can just fake ciphertexts by generating signature key pairs on my own as an adversary.

• Right. So how does one achieve IND-CCA in public-key world?

[editor's note: after some thinking and hints by examiners to KEM and FDH-RSA] Ah as follows. I then drew a CCA-secure KEM. At first I forgot hashing, but then after a hint added it.

• Okay, let's switch over to private-key world. How does one construct MACs?

I drew minicrypt starting with OWF →* OWP → OWP with hardcore predicate → PRG → length-doubling PRG → PRF → MAC. [editor's note: details of →* was not covered in class; but you should know that such a step is necessary]

• Perfect, let's inspect some PRFs. Is F'(K, m) := F(K, m || 0) || F(K, m || 1) a PRF ignoring length preservation conditions?

Yes because the inputs to the individual PRF calls are always different (in last bit), hence their outputs are intuitively independent.

• Yes, how about `F'(K, m) := F(K, 0 || m) || F(K, m || 1)`?

My last argument now fails, e.g. with first message `m_0 := 0^{n-1}1` and second message `m_1 := 0^n`. We can then relate structure of both outputs by `F'`.