Cryptanalysis of a feedback shift reigister with an S-box

Question

I’m just getting started on learning cryptography and here is a problem from exercises about which I'm totally confused:

This is a 32-bit feedback shift register to encrypt some message. The register shifts circularly by 4 bits. Before each shift the S-box takes the last 4 bits and feeds the 4-bit output back into the four bits just next to them (as shown above). This cryptosystem is keyed by the contents of the S-box. The questions are:

If the S-box is not invertible, how many bits of information does it contain? And what if the S-box is invertible but entries selected randomly without replacement?

So what I'm confused about is: why is this cryptosystem "keyed by the contents of the S-box"? How to decrypt the ciphertext if we know the S-box (and times the register shifted if necessary)? And what does "information contained by the S-box" mean? How does the invertibility of the S-box affect the bits of information it contains?

I know that the initial value of an FSR is called the "seed" and from that the register can generate some pseudorandom keys to be used in some cryptosystems. But in this problem it seems that the seed itself is the plaintext to be encrypted and the ciphertext is one of its successors. Also, I know an S-box is used to perform substitution but I've never heard something about "the information it contains".

Hope that I've described this problem clearly. Thank you guys in advance :)

Answer 1

why is this cryptosystem "keyed by the contents of the S-box" ?

It means that the content of the S-box is assumed secret, and part of the key (in addition to whatever part of the initial state is not a given).

How to decrypt the ciphertext if we know the S-box ?

My reading is that what's shown is the keystream generator of a stream cipher, that gets combined by XOR with the plaintext outside of the drawing. We have to guess that, as in a Fibonacci LFSR, the keystream is what's output on the right, so that the first 32 bits of the keystream are the initial state per some untold convention on bit order, likely the same as in reference material by the same author on Fibonacci LFSR.

To decipher, the legitimate user would need to know the initial state, and repeatedly extract the right 4 bits and do three independent things with these:

• XOR these with 4 bits of ciphertext to decipher 4 bits of plaintext
• push these (not the ciphertext nor plaintext) on the left of the LFSR, removing them from the right
• feed these in the S-box, and get 4 S-box output bits, that must be combined with XOR into the 4 bits that the above shift has moved on the right of the LFSR, and that the next step will extract.

What does "information contained by the S-box" mean ?

That means the effective key length that the S-box represents, equivalently the entropy¹ necessary for coding an S-box (that is fully describing the input to output function that it implements). If there is a total of $s$ possible distinguishable S-boxes of equal probability, that's $\log_2(s)$.

How does the invertibility of the S-box affect the bits of information it contains?

Invertibility of an S-box means that no two distinct combination of the $i$ input bits yield the same combination of the $b$ output bits. By the pigeonhole principle it implies $i\le b$ (this is the case here: we have $i=b=4$). This invertibility restricts the number of S-boxes, thus $s$ changes.

---

¹ If we knew how the keys are turned into an S-box (which is not the case here), we could compute the probability $p_j$ of each distinguishable S-box, and the Shannon entropy could be computed as $$\displaystyle-\sum_{j\text{ with }p_j>0}p_j\,\log_2(p_j)$$