3
$\begingroup$

Talking about symmetric encryption, I have 3 elements which I keep trying to puzzle together: IV, encryption mode, and padding.

My question really is which of these elements makes the ciphertext be random?

What I believe right now:

Padding: The padding does not "add" randomness. It only solves the problem of being able to divide the plaintext into the block size defined.

Encryption mode: Here I have a little bit of confusion. So, lets compare ECB mode with CBC mode. As far as I know, the problem with ECB is that, for example, if I have two plain text that I want to encrypt:

P1A, P1B P2A, P2B

where P1A would be the first block of plain text 1.

If P1B and P2B are the same, then C1B and C2B would also be the same, even if P1A and P2A are different. ¿Am I right? Therefore is easy to "swap" ciphertext blocks of data.

On the opposite side. CBC mode (without details) chains the ciphertext blocks one with another. Therefore, if we apply CBC mode to the last example. C1B and C2B would not be the same.

But.. And here is one of my questions. The mode "by it self", in this case CBC, does not add randomenes right? Because the ciphertext will always be the same for the same plain text. Am I wrong? Is there any mode that obtains randomness by itself?

IV: And at last, the IV, which I think is actually the only element from these 3 which makes the cipher text be random.

How much wrong am I?

Thank you and sorry if I made some mistake with the technical language of crypto.

$\endgroup$
  • $\begingroup$ The actual answers have mentioned this, but it struck me as I read the question and thought I should highlight it: your question fails to mention the key, which is generally required to be randomly selected. And that already partially answers your question. $\endgroup$ – Luis Casillas Oct 18 '17 at 18:19
2
$\begingroup$

The padding does not "add" randomness. It only solves the problem of being able to divide the plaintext into the block size defined.

Correct.

The mode "by it self", in this case CBC, does not add randomenes right? Because the ciphertext will always be the same for the same plain text. Am I wrong? Is there any mode that obtains randomness by itself?

No, CBC doesn't add randomness by itself. The modes are deterministic algorithms. This is like asking if a mathematical formula such as $z = x + y$ can introduce randomness of $z$ without using $x$ or $y$. The answer is no.

IV: And at last, the IV, which I think is actually the only element from these 3 which makes the cipher text be random.

Correct; the combination of the IV and key . And depending on the mode of operation the IV may have to be of a particular size. More importantly, the IV may need to be unpredictable or not.

If, for instance the IV for CBC is a counter then the attacker may propose a plaintext where the first block has the same value. In that case the first block to be encrypted by the block cipher will just contain zeros, which is obviously not secure. So for CBC the IV needs to be unpredictable to an attacker.

With CTR mode the IV is a starting counter value consisting of a nonce and block counter part. As long as the final counter is unique the blocks within the resulting key stream will be unique. For that to happen the nonce needs to be unique and a limited number of blocks should be encrypted. To an attacker the key stream (the output of the cipher before XOR with the plaintext) will look random (without repeating blocks) as the attacker doesn't know the key.


TL;DR you are not wrong.


The IV doesn't need to be random in any mode; the key will provide the necessary randomness. The IV is just needed to perform encryption over multiple messages. In other words: it diversifies the randomness that is already present in the key for the messages.

$\endgroup$
  • $\begingroup$ Sorry, "can't be encrypted"? I don't understand the comment. $\endgroup$ – Maarten Bodewes Oct 18 '17 at 12:24
  • $\begingroup$ Where is the randomness if you don't use an IV? You don't have to and the message still can't be decrypted. And why is 'decrypted' highlighted as a misspelling on a crypto site? $\endgroup$ – Paul Uszak Oct 18 '17 at 12:59
  • $\begingroup$ I've updated the question with a remark at the bottom. The IV doesn't necessarily increase randomness, it simply needs to bring out the randomness that is already present in the key for the specific mode of operation. And yes, any cipher (or mode of operation) that needs to be CPA secure over multiple messages requires an IV (or tweak, or something) . So you cannot decide not to use it. ECB can only do without an IV because it is not secure for every kind of message; the message itself needs to provide the diversification. SIV is possible because it relies on the message to be unique. $\endgroup$ – Maarten Bodewes Oct 18 '17 at 14:37
  • $\begingroup$ Please explain the downvote! $\endgroup$ – Maarten Bodewes Oct 18 '17 at 20:44
3
$\begingroup$

“Random” is a complicated concept and this question does not have a one-word answer.

The ciphertext is not random, in the sense that it's possible to relate it to the plaintext. Just decrypt and compare. The ciphertext is constructed deterministically from the plaintext, the key, the IV and the message.

The ciphertext appears random to someone who doesn't know the key and has plausible computational power. (Someone who has effectively infinite computational power can try all possible keys.) This is a definitional property of encryption schemes.

The block cipher algorithm (e.g. AES or DES), the chaining mode (e.g. CBR or CTR), the key and the IV all contribute to this randomness in their own way.

  • The key, of course, is where the randomness starts. It's directly extracted from an entropy source. It's the one element that absolutely needs to be random in the sense that an adversary has no knowledge of the key beyond its format (for symmetric encryption, an array of bits of known length).
  • The block cipher, given a key, makes the encryption of a plaintext block look random. That is, to someone who doesn't know the key, the block cipher acts like a random permutation — it always transforms the same input into the same output, but the outputs for distinct inputs are not related in any visible way. The job of the block cipher is to transform the “raw” randomness of the key into a structured randomness: a random-looking permutation function.
  • The chaining mode extends this randomness to multiple blocks. The encryption of each block may look random, but when you consider multiple blocks together, the combination is not random if there is correlation between the blocks. The job of the chaining mode is to break any correlation. This is where ECB fails: all blocks undergo exactly the same transformation. CBC and other feedback modes break the correlation by inserting a step of the block cipher between each block. CTR breaks the correlation by using different inputs for each block. In all cases the chaining mode leverages the block cipher's decorrelating action from the block level to the message level.
  • The IV extends this randomness to multiple messages. The encryption of a single message may look random, but the same transformation of the same plaintext would result in the same ciphertext. The job of the IV is to ensure that there is no correlation between any two uses of the same key. The chaining mode uses the IV to leverage the block cipher's decorrelating action from the message level to the multiple-message level.
$\endgroup$
  • $\begingroup$ Nice answer, I like the fact that you started off with the key being random, not the IV. $\endgroup$ – Maarten Bodewes Oct 18 '17 at 14:40

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.