Chapter 6.1 (Block Ciphers | Description) is confusing
Opened this issue · 3 comments
First of all, the illustrations seem to be wrong as mentioned in other issues. So probably most of the confusion can be eliminated by looking at correct visual explanations of the concepts.
We illustrate this by looking at a block cipher with an impractical, tiny 4-bit block size. 2^4 = 16 possible blocks.
This doesn't make much sense to me. Why does block size determine number of possible blocks? How do we divide plaintext into blocks in the first place? I had an impression that what we do is choose a size for a block and then just split plaintext sequentially into chunks of that size, i.e. plaintext of size 40 split into blocks of size 16 will contain 40/16 = 2 full blocks and 1 partial block. Probably this is not the case at all so would be nice to have some ELI5 explanation before introducing the example.
In Figure 6.2, note that the permutation is not just one big cycle. It contains a large cycle of 7 elements, and several smaller cycles of 4, 3 and 2 elements each.
Term "cycle" appeared out of nowhere. What is a cycle in this context? I though we are taking plaintext blocks, encrypting them and "mapping" to ciphertext blocks (e.g. encrypted block 1 of plaintext becomes block 5 of ciphertext, and this 1→5 mapping is determined by key). Probably this is not the case either so I have no idea what's going on.
It is also perfectly possible that an element encrypts to itself.
What does that mean? To me this sounds like block of plaintext is identical to a block of ciphertext. That would be silly so I guess it means something else.
At this point I'm ready to throw the towel because it's the very beginning of the book and I'm already having trouble understanding the basic concepts without having to consult other sources of information, which probably defeats the purpose of 101.
Why does block size determine number of possible blocks?
A block cipher is a (pure) function. If your block size is 4 bits, there are only 16 different blocks you could feed to it. From the rest of your comment I'm inferring you're thinking of how to chop up a message into blocks; but we're still dealing with the block cipher, and hence individual blocks, here.
Perhaps another key piece of information: there is no fundamental difference between "ciphertext" and "plaintext" blocks. A block cipher is just a pseudorandom permutation: it maps blocks to blocks. Hopefully this helps with understanding cycles.
To me this sounds like block of plaintext is identical to a block of ciphertext.
That is precisely what it means :)
If your block size is 4 bits, there are only 16 different blocks you could feed to it.
What is exactly a block? Is it like a piece of the input/output of a certain size or something else? And by "blocks" here you mean individual instances of blocks (like assume if input is a string "Hello World!" then blocks could be for example 3-char substrings like "Hel", "lo ", "Wor", "ld!")? Or is it different kinds of blocks of varying sizes, where size is expressed by 4-bit number and thus there could be 16 different sizes (like a 1-char wide block, 2-char wide block, …, 16-char wide block)?
A block cipher is just a pseudorandom permutation: it maps blocks to blocks. Hopefully this helps with understanding cycles.
No, not really. To my understanding a permutation is a rearrangement of items in a set. Like if we have a set [A1, A2, A3] and then we apply some shuffling logic to it and get [A2, A1, A3] in return.
I still didn't look up any alternative sources of information so I think this is a good opportunity to understand how people with little prior crypto knowledge approach the reading of this book :)
Yes, a block is an input or output to a block cipher. The block width is a property of that block cipher; you can't give the same block cipher e.g. a 2 char block and a 16-char block. That comes into play once you build a stream cipher out of your block cipher, in the form of padding: but you haven't gotten there yet. As the book says:
A block cipher is an algorithm that encrypts blocks of a fixed length.
Plaintext and ciphertext blocks are sequences of bits and always match in size. The block cipherʼs block size is a fixed
size. Keyspace is the set of all possible keys.
Re: permutation: yes, that is exactly what a block cipher is! Specifically, it's an efficient way to compute a permutation (it needs to be efficient because real block ciphers have large, e.g. 128-bit, block widths). As the book says:
A block cipher is a keyed permutation. It is a permutation because the block cipher maps each possible block to another block. It is also a keyed permutation because the key determines exactly which blocks map to which. It is important for the block cipher to be a permutation because the recipient must map blocks back to the original blocks.