Transcribed TextTranscribed Text

In this problem we will see the issue with having short block sizes for block ciphers in CBC (cipher block chaining) mode. Suppose a message is broken up into blocks m1 , . . . , mn, and the corresponding ciphertext blocks are c1 , . . . , cn. (a) Suppose after a while of encrypting, two blocks are encrypted to the same ciphertext: ci=cj . In CBC mode, what information do we find out about mi and mj ? (We do not necessarily know everything about mi and mj , we do find out something though.) (b) DES and Triple DES use 64 bit blocks. Estimate the number of blocks in a message before we expect (with probability at least 50%) to see at least two identical ciphertext blocks. (Hint: this is a birthday problem. Since there are 2 64 different blocks, what does the birthday problem tell us about when we should expect a collision?) (c) Since each block is 8 bytes long, about how large a message (in bytes, KB, MB, or GB) is needed before we expect (probability 50%) to see a collision? Hints: •2 10 bytes≈1 KB •2 20 bytes≈1 MB •2 30 bytes≈1 GB

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

a). We write the encryption law in CBC-mode for both ciphertexts Ci and Cj.
Ci = Enck(Pi ⨁ Ci-1)
Cj = Enck(Pj ⨁ Cj-1)
Since Ci = Cj => Pi ⨁ Ci-1 and Pj ⨁ Cj-1 get encrypted to the same value.
Thus Pi ⨁ Ci-1 = Pj ⨁ Cj-1
Now, using the basic properties of XOR function (a ⨁ b =c => a⨁ c=b), we obtain:
Pi ⨁ Pj = Ci-1 ⨁ Cj-1
This tells us that, if know the previous two ciphertext blocks (namely Ci-1 and Cj-1 respectively), then we can also find out the XOR between the two original plaintext blocks. In terms of security, this means that two identical ciphertext blocks in CBC mode might lead to data leakage. Even if we do not know actual plaintext blocks, we pull some information about a relationship between them, which might facilitate other cryptographic attacks further....

By purchasing this solution you'll be able to access the following files:

for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Cryptography Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Upload a file
Continue without uploading

We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats