4
$\begingroup$

According to Wikipedia block cipher modes of operation, simplified CFB supports random read access. but what about the real CFB where we have a shift register? below are pictures extracted from the book "Cryptography and Network Security by William Stallings" for CFB. enter image description here And enter image description here

Does it support random read access? if yes, how?

$\endgroup$
0
4
$\begingroup$

Yes, with some more ciphertext.

The CFB mode encryption equations;

\begin{align} I_0 &= \text{IV}\\ I_i &= \big((I_{i-1} \ll s) + C_i\big) \bmod 2^b,\\ C_i &= \operatorname{MSB}_s\big(E_K(I_{i-1})\big) \oplus P_i\\ \end{align}

and decryption equations;

\begin{align} I_0 &= \text{IV}\\ I_i &= \big((I_{i-1} \ll s) + C_i\big) \bmod 2^b,\\ P_i &= \operatorname{MSB}_s\big(E_K(I_{i-1})\big) \oplus C_i\\ \end{align}

As you can see, to read one value one needs more than one ciphertext and that is defined by the CFB mode is used. NIST has CFB-1, CFB-8, and CFB-128. The $s$ in the CFB-$s$ represents the encryption size per block cipher encryption/decryption.

  • CFB-1 needs to read 129 ciphertexts block, one can be IV, to decrypt one block
  • CFB-8 needs 9 to read 129 ciphertexts block, one can be IV, to decrypt one block
  • CFB-128 needs 2 to read 129 ciphertexts block, one can be IV, to decrypt one block

The good is that if you read sequentially then the need is not linear, for example, 2 sequential ciphertext blocks will need only 3 on CFB-128, 10 in CFB-8, and 120 in CFB-1.

Actually, even in the reduced sizes like CFB-1, this is not really a problem, since the 128 ciphertexts are bits and that is only two reads if the data can be access 128-bit per reading. The memories can handle this and harddisk has wider read access. This, however, has a drawback on the decryption time. AES-CFB-1 needs 128 decryptions, AES-CFB-8 needs 16 decryptions.

Note that we don't use CFB or CTR on-disk encryption, we rather prefer XTS or XEX modes.

$\endgroup$
3
$\begingroup$

simplified CFB supports random read access. but what about the real CFB where we have a shift register?

Sure it does; actually, it's not that difficult. In CFB, the "plaintext" submitted to the underlying block cipher is the previous $b$ bits of the ciphertext (where $b$ is the block size). The shift register is there just to allow us to track what those bits are during the encryption/decryption process. The only distinction between "real" CFB (which is the original understanding) and the modern understanding of CFB is that the original understanding allowed us to use $s$ bits per iteration, which may be fewer than $b$ bits (in the modern understanding, we always use all $b$ bits per iteration, or in other words, $s = b$; when $s = b$, the previous $b$ bits of ciphertext is precisely the ciphertext block we just output or saw, and so we don't need a shift register).

And, the IV is to give us previous ciphertext bits at the start of the ciphertext (where we don't have previous ciphertext bits); we can use that.

For example, suppose you want to start reading at offset $1024$ bits (and $b=128$); you would read the 128 ciphertext bits starting at $1024-128 = 896$ and use those as the CFB-mode IV; you can then start decrypting at ciphertext offset 1024, and it will decrypt properly. The only thing we need to be careful about is that we need to start at an offset which is a multiple of $s$ bits.

Background: the original CFB idea allowed us to deal with ciphertext errors that inserted or removed blocks of $s$ bits; for example, if we were encrypting data going over an RS-232 channel, that would sometimes insert an extra character or delete it. CFB had the advantage that, should that happen, the next 8 characters (back then, we had $b=64$) would be decrypted incorrectly, but then the shift registers would resync, and everything would be fine (in contrast, CBC mode would never resync until we've inserted/removed a multiple of 8 bytes). Nowadays, this property of being able to resync is not considered important (we're more sensitive to attackers inserting deliberate errors, and so we're prefer to reject everything that can't decrypt properly), and so this special property of CFB mode is not considered important (and it is expensive; if $s=8$, we perform a block mode operation of each byte)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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