4
$\begingroup$

These 2 similar questions are from Paar's Understanding Cryptography. I could not see the answer so if someone can help I will appreciate:

Question1: We consider known plaintext attacks on block ciphers by means of an exhaustive key search where the key is $k$ bits long.The block length counts $n$ bits with $n>k$ .

(i) How many plaintexts and ciphertexts are needed to succesfully break a block cipher running in ECB mode? How many steps are done in the worst case?

(ii) Assume that the initialization vector IV for running the considered block cipher in CBC mode is known. How many plaintexts and ciphertexts are now needed to break the cipher by performing an exhaustive key search? How many steps need now maximally be done? Briefly describe the attack.

(iii) How many plaintexts and ciphertexts are necessary if you do not know the IV?

(iv) Is breaking a block cipher in CBC mode by means of an exhaustive search considerably more difficult than breaking an ECB mode block cipher?

Question 2: Keeping an IV secret in OFB mode does not make an exhaustive key search more complex. Describe how we can perform a brute force attack with unknown IV?What are the requirements regarding plaintext and ciphertext?

Improve this question
$\endgroup$
6
  • $\begingroup$ hint: when saying n>k, it says DES, so here i $\endgroup$
    – kelalaka
    Commented Oct 25, 2018 at 21:50
  • 1
    $\begingroup$ OK, I did scan through the book. A few remarks: it definitely isn't as bad as these questions seem to indicate. However, it misses quite a lot of information about attacks. Padding or plaintext oracle attacks are, for instance, not even mentioned. CBC-MAC is mentioned without any indication that or when it may be insecure, while AES-CMAC is mentioned as a new construct. So please note that the information in the book may be good but definitely incomplete. The order of the chapters in the book is also a bit weird in my opinion, but that's OK. $\endgroup$
    – Maarten Bodewes ♦
    Commented Oct 26, 2018 at 1:02
  • 1
    $\begingroup$ It also downplays side channel attacks too much. You don't need physical access to a CPU to attack RSA private key operations, for instance. A very successful attack was performed on RSA when RSA was simply calculated on the same core and the attacker could abuse hyperthreading on the same CPU. $\endgroup$
    – Maarten Bodewes ♦
    Commented Oct 26, 2018 at 1:08
  • $\begingroup$ @MaartenBodewes I 've edited the question and add one more question with a solution which I also did not get some parts. Could you please check it also? $\endgroup$
    – esra
    Commented Oct 26, 2018 at 15:24
  • $\begingroup$ I'm fine with you asking additional questions, but please separate them into a separate post. Having to answer 5 related questions and followups is enough for one post, if you don't mind. It makes it harder for others to find their Q/A as well. $\endgroup$
    – Maarten Bodewes ♦
    Commented Oct 26, 2018 at 15:26

1 Answer 1

Reset to default
3
$\begingroup$

Let me proceed by giving the answers, some of which are probably considered wrong by the book:

(i) One. If you have two ciphertext blocks that are identical you leak information about the message itself, so the cipher would be broken. A message may well consist of multiple blocks with repeated plaintext after all. You'd need $m$ messages of a single block (max) before they start to repeat in the worst case, assuming non-random padding. Here $m$ is the number of messages in the message space, with $m \leq 2^n$ - so $2^n$ is the maximum of the maximum.

(ii) One. You can verify the correctness of the key with high probability using the a single known block as $n > k$. Even if this is not the case the message may occupy multiple blocks. You'll never be completely certain though. The maximum time for an exhaustive key search is of course $2^k$ (this one is probably correct by the book).

(iii) Still one, because you can simply consider any blocks after the first block.

(iv) Yes, generally it is considered more difficult. ECB is insecure and exhaustive key search is often not practically possible for high enough $k$.

2 You just consider the next blocks as you know the first (known) ciphertext block. The plaintext and thus ciphertext needs to consist of more than one block for this, but only if the IV is random instead of just "unknown"; the more bits you know of each message the better.

As indicated, horrible questions. I would presume I would have quite a few wrong, if just out of sheer unwillingness to understand.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ Note that I got a 9,5 for economics. I scored a 9 but I got 0.5 extra because I said that the break even point that I had to calculate was outside the considered range. I liked that tutor, even though he was one of the persons responsible for the exam in the first place. Other teachers... not so good. I'd be the one asking: "should we consider 0 bit messages for the worst case scenario?" $\endgroup$
    – Maarten Bodewes ♦
    Commented Oct 25, 2018 at 22:15
  • 1
    $\begingroup$ iii) requires a case if there is only one block encrypted. $\endgroup$
    – kelalaka
    Commented Oct 25, 2018 at 23:05
  • 1
    $\begingroup$ @kelalaka True, but if I look at the question it never says that I have to assume one block. This is one reason why I didn't like the questions. How the plaintext and ciphertext should be created is never made explicit. $\endgroup$
    – Maarten Bodewes ♦
    Commented Oct 25, 2018 at 23:24
  • 1
    $\begingroup$ Well, once can choose as your answer, once can choose more general. I understand that from the intent, actually, they wanted to add the IV into search. $\endgroup$
    – kelalaka
    Commented Oct 25, 2018 at 23:26
  • 2
    $\begingroup$ @MaartenBodewes, I like your answer, just fixed a typo [a message may well consist of..] $\endgroup$
    – kodlu
    Commented Oct 26, 2018 at 0:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.