2
$\begingroup$

According to Computer Networking: a top down approach, Chapter 8 (6th edition), block ciphers involves breaking the input message into blocks of size k, where generally k = 64. However since k = 64 implies that we need to create a table of input size 2k or 264 in our case, therefore we simulate randomly permuted tables. To simulate, we use the following process. The function first breaks a 64-bit block into 8 chunks, with each chunk consisting of 8 bits. Each 8-bit chunk is processed by an 8-bit to 8-bit table, which is of manageable size. For example, the first chunk is processed by the table denoted by T 1 . Next, the 8 output chunks are reassembled into a 64-bit block. The positions of the 64 bits in the block are then scrambled (permuted) to produce a 64-bit output. This output is fed back to the 64-bit input, where another cycle begins. After n such cycles, the function provides a 64-bit block of ciphertext.

Here is the question: Why do we need to process the text through n such cycles? The book states that

The purpose of the rounds is to make each input bit affect most (if not all) of the final output bits. (If only one round were used, a given input bit would effect only 8 of the 64 output bits.)

The key for this block cipher algorithm would be the eight permutation tables (assuming the scramble function is publicly known).

*Personal Comment - However, if the input text has gone through even a single cycle still all the inputs would have been affected since each block went through a mapping based on the corresponding table Tj table. Hence we shouldn't be required to cycle it through n cycles. Figure - Flow Diagram

Improve this question
$\endgroup$
3
  • $\begingroup$ That's not a very god description; if you want to learn about block ciphers you should get a book on that subject. $\endgroup$
    – fkraiem
    May 17, 2017 at 14:08
  • $\begingroup$ Please link any good sources that you might want to recommend for block cipher. However, reading an entire book for a basic conceptual question will be infeasible. $\endgroup$
    – PallavBakshi
    May 17, 2017 at 14:20
  • $\begingroup$ I found a truly beautiful visual explanation of why this is important (though in this case, it is for a stream cipher, albeit one that operates in blocks): cr.yp.to/snuffle/diffusion.html $\endgroup$
    – forest - on strike ♦
    Mar 22, 2018 at 2:45

2 Answers 2

Reset to default
2
$\begingroup$

First of all, I wouldn't rely on that book for information about modern cryptography. It might be a fine reference for networking in general, however based on the example they gave, it would appear that they really don't know their crypto. The example cipher they gave feels like something from the '90s.

Modern block ciphers use $k=128$; the issue with $k=32$ is that you tend to leak information about the plaintext after encrypting a few gigabytes with the same key; with modern networks, you can hit a few gigabytes easily. In addition, key dependent sboxes have gone out of fashion; they are a bit expensive in hardware, they tend to leak timing data in software (due to caching), and the sboxes are sometimes not particularly strong against differential or linear cryptanalysis.

As for your question:

Why do we need to process the text through n such cycles?

Consider the case where $n=1$, and you have two different plaintexts that differ in a single bit. Then, if you look at the two parallel encryptions, the inputs for seven of the sboxes are precisely the same (because they only depend on inputs that have not changed), and so only one sbox (say, $T_0$) has its output changed. That sbox has 8 output bits, and so when you go through the 64-bit scrambler, then you have 56 output bits that would always be the same, and 8 that are potentially changed. This is far short of 'any input bit can potentially affect any output bit'.

There are more sophisticated things we can do for larger $n$; this simple reasoning shows that the $n=1$ case just doesn't cut it...

Improve this answer
$\endgroup$
7
  • $\begingroup$ If we have 64 bit message consisting of "000...111" where first 32 bits are "0" and last 32 bits are "1" then we will break the message into 8 blocks where each block contains 8 bits. If we process each of these 8 blocks parallel then we will find the output of each 8 blocks to be different from the input of those same 8 blocks. For example, if the first block was "0000 0000" and depending upon the Table, it might become "0010 0001" and similarly the output for each block will change. Therefore, we may not need to go through the cycle n times... What do you say? $\endgroup$
    – PallavBakshi
    May 17, 2017 at 14:18
  • $\begingroup$ @PallavBakshi: but also consider the 64 bit message consisting of "000.111", where the first 33 bits are "0", and the last 31 bits are "1"; this differs from your message in only 1 bit. Consider how that block would be processed, compared to your block; how would the two 64 bit blocks of ciphertext (of the encryption of your message and my message) compare... $\endgroup$
    – poncho
    May 17, 2017 at 14:30
  • $\begingroup$ It seems we have a really different view of how does the table map each 8-bit block. Let me try to explain what I understood about the table mapping process from the book and then you can let me know if my understanding is correct or not. So let's assume we are working with block size, k = 3, which means each block is made up of only 3 bits. So we create the following input/output table - (input/output) pair - (000 input gives 110), (001 input gives 111), (010 -> 101), (011 -> 100), (100 -> 011), (101 -> 010), (110 -> 000) and (111 -> 001). So when we get input as 100 we get output as 011 $\endgroup$
    – PallavBakshi
    May 17, 2017 at 14:43
  • $\begingroup$ As you may see from the previous example, each T<sub>j</sub> will change multiple bits in each block which implies that within one cycle it will change almost all the bits since we are using 8-bit block. I can give you the exact page number from the book where they have explained how does the table map input to the output. I might be wrong about all of it, so I really appreciate your help. $\endgroup$
    – PallavBakshi
    May 17, 2017 at 14:48
  • $\begingroup$ @PallavBakshi: no, we have a really different view about what's important; you're looking at the differences between the inputs and the outputs; I'm looking at the differences between the outputs when the inputs are related. $\endgroup$
    – poncho
    May 17, 2017 at 14:48
1
$\begingroup$

Consider what happens when we have a known-plaintext attack on the one-round version. I know the input to each Ti, and by undoing the scramble I can determine the corresponding output. So now I have one entry in each Ti. Each additional message will allow me to determine more entries in the Ti tables, so with enough messages (probably a few thousand since there will be duplicate Ti inputs) I can determine the entire contents of the Ti tables.

Now think about a 2-round version, again using a known-plaintext attack. I know the input the inputs to the first round of the Ti tables, but get the output from the second round. So now I have to map the inputs to the first round to the (unknown) outputs of the first round, and thus the input to the second round. So while this would still be weak, it is still much stronger than the one-round version.

So adding additional rounds means I have to attack the entire cipher as a whole, instead of being able to break it down into individual tables.

Improve this answer
$\endgroup$

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.