added 563 characters in body
Source Link
Maarten Bodewes
  • 82.8k
  • 12
  • 131
  • 286

Lets assume first that the bit string can have any value. This is not explicit from the question, but it does't make any other claims about the contents either, so we have to assume this is the case.

Furthermore, let's assume that no out of band communication can exist. That means that, for instance, that no state can be kept. In other words, we cannot use a counter on both sides to create indistinguishability.

 

The ciphertext needs to be the same size as the plaintext. That means that the number of plaintext messages and ciphertext messages are equal: both are limited to $2^n$ where $n$ is the number of bits. Each plaintext message will therefore be mapped to exactly one ciphertext message; if this isn't the case then some plaintext messages are impossible to encrypt/decrypt.

This in turn means that an adversary can see identical messages because each message will be mapped to the same ciphertext message. This means that information about the messages is leaked: identical messages can be distinguished and conversely it is also possible to see that no identical messages are send.

To change the mapping we need to add state, as both the encryption and decryption will have to change the mapping in the same way. We cannot use any of the bits of the ciphertext, because if we re-assign one of the bits or even one pattern then some plaintext messages cannot be reached anymore by the mapping.

This means that the encryption / decryption needs to be deterministic; there is no way to add information to the ciphertext message that can be used on both sides to generate a different ciphertext / plaintext message given identical input.


The pseudo random 1:1 mapping of plaintext and ciphertext is called a permutation. Block ciphers are permutations for a specific value of $n$: the block size.

From this question you can see that ECB mode cannot be IND_CPA secure: information is leaked already when you encrypt the second block. If the second plaintext block is identical to the first one then the second ciphertext block will be identical to the first ciphertext block. So you can find any identical sets of blocks, or you can identify that there aren't any, which of course also leaks information.

Hence you require a mode of operation to make a block cipher IND_CPA secure.

Lets assume first that the bit string can have any value. This is not explicit from the question, but it does't make any other claims about the contents either, so we have to assume this is the case.

Furthermore, let's assume that no out of band communication can exist. That means that, for instance, that no state can be kept. In other words, we cannot use a counter on both sides to create indistinguishability.

The ciphertext needs to be the same size as the plaintext. That means that the number of plaintext messages and ciphertext messages are equal: both are limited to $2^n$ where $n$ is the number of bits. Each plaintext message will therefore be mapped to exactly one ciphertext message; if this isn't the case then some plaintext messages are impossible to encrypt/decrypt.

To change the mapping we need to add state, as both the encryption and decryption will have to change the mapping in the same way. We cannot use any of the bits of the ciphertext, because if we re-assign one of the bits or even one pattern then some plaintext messages cannot be reached anymore by the mapping.


The pseudo random 1:1 mapping of plaintext and ciphertext is called a permutation. Block ciphers are permutations for a specific value of $n$: the block size.

From this question you can see that ECB mode cannot be IND_CPA secure: information is leaked already when you encrypt the second block. If the second plaintext block is identical to the first one then the second ciphertext block will be identical to the first ciphertext block. So you can find any identical sets of blocks, or you can identify that there aren't any, which of course also leaks information.

Hence you require a mode of operation to make a block cipher IND_CPA secure.

Lets assume first that the bit string can have any value. This is not explicit from the question, but it does't make any other claims about the contents either, so we have to assume this is the case.

Furthermore, let's assume that no out of band communication can exist. That means that, for instance, that no state can be kept. In other words, we cannot use a counter on both sides to create indistinguishability.

 

The ciphertext needs to be the same size as the plaintext. That means that the number of plaintext messages and ciphertext messages are equal: both are limited to $2^n$ where $n$ is the number of bits. Each plaintext message will therefore be mapped to exactly one ciphertext message; if this isn't the case then some plaintext messages are impossible to encrypt/decrypt.

This in turn means that an adversary can see identical messages because each message will be mapped to the same ciphertext message. This means that information about the messages is leaked: identical messages can be distinguished and conversely it is also possible to see that no identical messages are send.

To change the mapping we need to add state, as both the encryption and decryption will have to change the mapping in the same way. We cannot use any of the bits of the ciphertext, because if we re-assign one of the bits or even one pattern then some plaintext messages cannot be reached anymore by the mapping.

This means that the encryption / decryption needs to be deterministic; there is no way to add information to the ciphertext message that can be used on both sides to generate a different ciphertext / plaintext message given identical input.


The pseudo random 1:1 mapping of plaintext and ciphertext is called a permutation. Block ciphers are permutations for a specific value of $n$: the block size.

From this question you can see that ECB mode cannot be IND_CPA secure: information is leaked already when you encrypt the second block. If the second plaintext block is identical to the first one then the second ciphertext block will be identical to the first ciphertext block. So you can find any identical sets of blocks, or you can identify that there aren't any, which of course also leaks information.

Hence you require a mode of operation to make a block cipher IND_CPA secure.

Source Link
Maarten Bodewes
  • 82.8k
  • 12
  • 131
  • 286

Lets assume first that the bit string can have any value. This is not explicit from the question, but it does't make any other claims about the contents either, so we have to assume this is the case.

Furthermore, let's assume that no out of band communication can exist. That means that, for instance, that no state can be kept. In other words, we cannot use a counter on both sides to create indistinguishability.

The ciphertext needs to be the same size as the plaintext. That means that the number of plaintext messages and ciphertext messages are equal: both are limited to $2^n$ where $n$ is the number of bits. Each plaintext message will therefore be mapped to exactly one ciphertext message; if this isn't the case then some plaintext messages are impossible to encrypt/decrypt.

To change the mapping we need to add state, as both the encryption and decryption will have to change the mapping in the same way. We cannot use any of the bits of the ciphertext, because if we re-assign one of the bits or even one pattern then some plaintext messages cannot be reached anymore by the mapping.


The pseudo random 1:1 mapping of plaintext and ciphertext is called a permutation. Block ciphers are permutations for a specific value of $n$: the block size.

From this question you can see that ECB mode cannot be IND_CPA secure: information is leaked already when you encrypt the second block. If the second plaintext block is identical to the first one then the second ciphertext block will be identical to the first ciphertext block. So you can find any identical sets of blocks, or you can identify that there aren't any, which of course also leaks information.

Hence you require a mode of operation to make a block cipher IND_CPA secure.