2
$\begingroup$

I was reading a book called Serious Cryptography. There is a page saying that block size must be large enough to prevent codebook attacks:

When 16-bit blocks are used, the lookup table needs only 2^16 × 16 = 2^20 bits of memory, or 128 kilobytes. With 32-bit blocks, memory needs grow to 16 gigabytes, which is still manageable. But with 64-bit blocks, you’d have to store 2 70 bits (a zetabit, or 128 exabytes), so forget about it. Codebook attacks won’t be an issue for larger blocks.

Where is the 2^16 * 16 coming from? I think it's supposed to be 2^16 + 2^16 the sum of ciphertext possibilities and the sum of plaintext possibilities that match this specific ciphertext, right?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ sweet32.info $\endgroup$
    – kelalaka
    Aug 11, 2020 at 19:16
  • $\begingroup$ after $2^{n/2}$ message blocks encrypted with the same key (in the same message or in different messages), a collision between two ciphertext blocks $c_i = c_j$ is expected. Take $n=64$ then $2^{32}$ by birthday paradox. And, With $2^d$ blocks of data the expected number of collisions is roughly $2^{2d-n-1}$ (following the birthday paradox). $\endgroup$
    – kelalaka
    Aug 11, 2020 at 20:06

1 Answer 1

Reset to default
3
$\begingroup$

Where is $2^{16}\cdot16$ bits coming from?

The $2^{16}$ term is the number of possible 16-bit blocks. The $16$ bit term is the space needed to store a block (that can be a block of ciphertext, with the plaintext used as index; or vice versa). The two are multiplied to get the total size, much like the price for $n$ things is $n$ times the price for one thing.

If we added the number of plaintexts and ciphertexts blocks, we'd get a number of blocks, not a size. And while we need to be able to manipulate all the plaintexts and all the ciphertexts, we do not need space to store both all the plaintexts and all the ciphertexts: one kind comes for free as the index of the table, which uses no space. Much like if we want to store what output from 0 to 9 correspond to input 0 to 9, we need 10 digits (like 8730629415), telling that 0 corresponds to 8, 1 to 7, 2 to 3,… 9 to 5; rather than 20 digits.

In this table of $2^{16}$ values, there are never two identical values. That makes it slightly compressible, down to $\log_2((2^{16})!)$ bit, a 9% saving.

Such a table needs not cover all plaintext/ciphertext pairs to be useful. A much smaller table can allow some attack. For example, a table with $2^8$ entries instead of $2^{16}$ allows decryption of about one block out of $2^8$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I think i still cant get it why he multiplied 2^16 by 16 and didn't just add 2^16(those of the plaintext possibilities ) to the block cipher possibilities . $\endgroup$
    – KMG
    Aug 11, 2020 at 21:34
  • $\begingroup$ @Khaled Gaber: see update. $\endgroup$
    – fgrieu ♦
    Aug 12, 2020 at 6:43
  • $\begingroup$ thanks's for the update got it now $\endgroup$
    – KMG
    Aug 12, 2020 at 10:40

Your Answer

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

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