5
$\begingroup$

I am stuck with AES-CFB decryption.

Assume I encrypted plaintext helloworld (10 bytes) using AES-CFB.

Now I want to decrypt the second byte e individually, that is I don't want to decrypt the first bytes or any other bytes except the second one.

Is it possible to do that without decrypting the first byte?

I did my fair share of research and even tried several practical approaches to find an answer myself, but somehow I’m stuck.

In case it helps answering my question, here’s what my latest attempt looks like (think of it as “pseudo-code” as I’m definitely not asking an off-topic question related to the code itself):

char *key = "whatever";
char *data = "helloworld";
unsigned char out_cipher[10], out_plain[10];
unsigned char iv_enc[AES_BLOCK_SIZE], iv_dec[AES_BLOCK_SIZE];
RAND_bytes(iv_enc, AES_BLOCK_SIZE);
memcpy(iv_dec, iv_enc, AES_BLOCK_SIZE);
AES_KEY enc_key, dec_key;
AES_set_encrypt_key(key, 256, &enc_key);
AES_set_encrypt_key(key, 256, &dec_key);
AES_cfb8_encrypt(data, out_cipher, 10, &enc_key, iv_enc, &num, AES_ENCRYPT);
AES_cfb8_encrypt(out_cipher + 1, out_plain + 1, 1, &dec_key, &out_cipher[0], &num, AES_DECRYPT);

But even trying to approach this programmatically didn’t help me grasp this. Sure, I managed to retrieve an answer. Yet, it was clearly wrong because the 2nd byte of the decrypted plaintext differs from the original plaintext.

As I’ve now run out of ideas on how to find the answer to my question, I decided to ask here hoping someone can enlighten me if it is possible to decrypt the 2nd byte of an AES-CFB ciphertext without decrypting the 1st byte? Or maybe am I missing something else?

$\endgroup$
6
$\begingroup$

Yes, CFB just takes the previous block as the IV for the next block making it a stream cipher.

If you modify your iv_dec equal the result of the previous block, however long that is, it should work.

aes-cfb encrypt


Perhaps my answer was confusing because the image included above was for encryption and your asking about decryption.

aes-cfb decrypt

images from Wikipedia

$\endgroup$
  • $\begingroup$ Sorry I don't think I get it, what means modify iv_dec to the next previous block? Is that out[0] ? $\endgroup$ – ryuu Dec 19 '16 at 8:44
  • $\begingroup$ Apologies I fixed that. Yes out[0] in your example $\endgroup$ – dave.zap Dec 19 '16 at 9:09
  • 1
    $\begingroup$ @MaartenBodewes Actually I if I decrypt the first byte by passing the original IV, and the original IV will be modified by the decryption process. Then I pass the Modified IV as the IV to decrypt second byte will give me correct result. $\endgroup$ – ryuu Dec 19 '16 at 12:26
  • 2
    $\begingroup$ Eh, is that second image correct, it says CBC decryption... $\endgroup$ – Maarten Bodewes Dec 19 '16 at 13:05
  • 1
    $\begingroup$ CBC image is wrong here. Decryption mode for CFB is actually CFB itself. $\endgroup$ – ddddavidee Dec 19 '16 at 13:21
7
$\begingroup$

Yes, you can do this. If you want to know how to do it (as opposed to just blindly copying a code snipped written by someone else and hoping it'll work), you'll need to understand a little bit about how CFB mode encryption works.

First of all, CFB is a block cipher mode of operation. That is, it's a recipe for taking a block cipher like AES, which can only encrypt 16-byte blocks into other 16-byte blocks, and using it to securely encrypt (and decrypt) arbitrary streams of bytes.

Why do we even need a "mode of operation" like CFB? Why can't we just split the message into 16-byte blocks and encrypt each of them with AES? Well, yes we can, but such an encryption scheme, known as "ECB mode", turns out to not be as secure as we'd like. So, instead, we use slightly more complicated schemes like CBC, CFB, OFB or CTR, all of which can be proven to provide full semantic security when used properly.*

This causes a bit of terminology confusion sometimes. When we speak of "encrypting something with AES", in the context of describing a mode of operation, we mean using the raw AES block cipher to transform a 16-byte input block into a 16-byte output. (Your crypto library might have a separate API for this, or it might simply expose it as "ECB mode".) However, the words "encrypt" and "decrypt" are also used for the entire process of applying e.g. CFB mode encryption to the entire message. This gets particularly confusing when you realize that CFB decryption still uses AES encryption!

Second, there are actually several different CFB modes! The most common (and efficient) one, which is illustrated in the image included in several earlier answers, is called the "full-block" CFB mode, and works like this (assuming we're using AES as the block cipher):

  1. To encrypt the first 16 bytes of the message, take the 16-byte IV, feed it into AES, and XOR the resulting 16-byte block with the first 16 message bytes to produce the first 16 bytes of ciphertext. (If the message is shorter than 16 bytes, just truncate the AES output to match its length.)

  2. To encrypt the next 16 bytes of the message, take the 16-byte ciphertext (i.e. the AES output XORed with the message) that we just produced in the previous step, feed it into AES, and XOR it with the 16 message bytes that we want to encrypt to produce another 16 bytes of ciphertext.

  3. Repeat the same process for every subsequent block of 16 message bytes, every time using the previous 16 bytes of ciphertext as the AES input, until you reach the end of the message. Again, if the last message block is less than the full 16 bytes long, truncate the AES output to match its length.

However, what you seem to be using, based on your code, is the variant of CFB mode that encrypts a single byte at a time, sometimes called CFB-8 (because a byte has 8 bits; full-block CFB using AES would be CFB-128, and there's even a CFB-1 variant that encrypts a single bit at a time).

This CFB-8 mode works exactly the same as the full-block CFB mode, except that you always truncate the AES output to just one byte and XOR it with just one byte of the message to produce a single byte of ciphertext. (You still always take the previous 16 bytes of ciphertext, prefixed with the IV for the first 16 message bytes, as the AES input.) That is to say, CFB-8 encryption works like this:

  1. To encrypt the first byte of the message, take the 16-byte IV, feed it into AES, and XOR the first byte of the AES output with the first byte of the message to produce the first byte of ciphertext. (The remaining 15 bytes of AES output are just thrown away!)

  2. To encrypt the second byte of the message, take the last 15 bytes of the IV plus the first byte of ciphertext that we just produced and, just like before, feed them into AES, take the first byte of the output, and XOR it with the second message byte to produce the second ciphertext byte.

  3. To encrypt the third byte of the message, take the last 14 bytes of the IV, plus the two bytes of ciphertext that we've just produced, feed them into AES and XOR the first byte of the output with the third message byte, just like above, etc.

(Why would you want to use this CFB-8 mode, given that it's about 16 times slower than full-block CFB? Well, unless you really want to be able to start decrypting the ciphertext at any byte, you really don't — that's the only real advantage it offers over full-block CFB mode.)

In both cases, CFB decryption is just the inverse of this process: to decrypt a (16-byte or 1-byte, depending on the CFB variant used) block of ciphertext, you take the previous 16 bytes of ciphertext (again, with the IV treated as a prefix of the ciphertext for the first 16 bytes), feed them through AES (in the same direction as for encryption!), and XOR the result with the following block (or byte) of ciphertext that you want to decrypt.

Now, while CFB encryption needs to be done sequentially from the start of the message, because you need to encrypt the previous block / byte of the message in order to know the 16 bytes of ciphertext needed for encrypting the next block / byte, CFB decryption can be done in any order (or even in parallel!) because the entire ciphertext is already known.

It turns out that you can, in fact, do this even if your crypto library doesn't give you access to the raw AES block cipher. The crucial observation here is that, for CFB mode, the IV is really just treated as prefix of the ciphertext that is used to get the encryption / decryption process started.

Thus, to decrypt a CFB ciphertext starting from the $n$-th block / byte, you just take the previous 16 bytes of the ciphertext (prefixed with the actual IV) and pass them to your crypto library as the IV for CFB decryption.

For example, using your CFB-8 "pseudocode" as a basis, you could decrypt a message starting from the $n$-th byte like this:

// key setup
char *key = "whatever";
AES_KEY aes_key;
AES_set_encrypt_key(key, 256, &aes_key);

// encrypt message using CFB-8, prepend IV to ciphertext
unsigned char *in_plain = "helloworld";
const int enc_len = 10;
unsigned char iv_enc[AES_BLOCK_SIZE];
RAND_bytes(iv_enc, AES_BLOCK_SIZE);
unsigned char ciphertext[AES_BLOCK_SIZE + enc_len];
memcpy(ciphertext, iv_enc, AES_BLOCK_SIZE);
unsigned char *out_cipher = ciphertext + AES_BLOCK_SIZE;
AES_cfb8_encrypt(in_plain, out_cipher, enc_len, &aes_key, iv_enc, &num, AES_ENCRYPT);

// decrypt dec_len message bytes starting from byte dec_start of ciphertext
const int dec_start = 1, dec_len = 1;
unsigned char out_plain[dec_len];
unsigned char iv_dec[AES_BLOCK_SIZE];
memcpy(iv_dec, ciphertext + dec_start, AES_BLOCK_SIZE);
unsigned char *in_cipher = ciphertext + dec_start + AES_BLOCK_SIZE;
AES_cfb8_encrypt(in_cipher, out_plain, dec_len, &aes_key, iv_dec, &num, AES_DECRYPT);

Note that I'm using a single ciphertext buffer to store both the IV and the ciphertext, and just passing a pointer into that buffer to the encryption / decryption API. (I do make a copy of the IV, since apparently the OpenSSL API this is based on modifies the IV string in place.) In a real application, this ciphertext buffer is what you'd send to the recipient after encryption. For CFB mode, this is a natural arrangement, and allows the IV for decryption to be obtained simply by taking a pointer to AES_BLOCK_SIZE = 16 bytes before the start of the ciphertext portion we wish to decrypt.

Essentially the same code should work for full-block CFB, too, except that you need to ensure that the starting offset dec_start is an integer multiple of the AES block size, so that decryption starts correctly at a block boundary.


*) Basically, semantic security means that an eavesdropper who can see all your encrypted messages (but cannot modify them or feed you fake messages, and does not know the encryption key) cannot learn anything about the plaintext messages except their length. Note that none of the "classical" encryption modes, including CFB, offer sufficient protection against active attackers who may try to modify or forge messages; for that you need an authenticated encryption mode.

$\endgroup$
  • $\begingroup$ Your answer is just awesome, very helpful to me, now I have some ideas of cryptography. I'll try your way tomorrow morning. And by "(The remaining 5 bytes of AES output are just thrown away!)", you may mean 15.:) $\endgroup$ – ryuu Dec 19 '16 at 17:25
2
$\begingroup$

CFB works as a stream cipher, where the random stream is generated encrypting the previous block of ciphertext. Then, the plaintext is just xored with this random generated stream.

CFB

To decrypt a particular byte, without decrypting all the others one can select the previous block (or the IV, if one is trying to decrypt a byte on the first block), encrypt it, select the corresponding byte and xoring it with the ciphertext.

In your example, you should encrypt the IV, select the second byte of the output and xor it with the second byte of the second block of the ciphertext (the first one being the IV).

$\endgroup$
  • $\begingroup$ What should I use to encrypt the IV? IV himself ? $\endgroup$ – ryuu Dec 19 '16 at 12:50
  • $\begingroup$ You encrypt the IV with the key. Give a look to the image. $\endgroup$ – ddddavidee Dec 19 '16 at 12:55
  • $\begingroup$ The API I am using must give an IV to encrypt something, key is required too of course. $\endgroup$ – ryuu Dec 19 '16 at 12:58
  • $\begingroup$ Because the API you're using is to encrypt/decrypt with the CFB mode. Here, in the image above, encryption is a single block, using ECB. $\endgroup$ – ddddavidee Dec 19 '16 at 13:00
  • $\begingroup$ I mean every single encryption is a ECB. The whole image is the CFB mode. $\endgroup$ – ddddavidee Dec 19 '16 at 13:01

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.