Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I am trying to get my head around the circumstances under which a cipher is (or is not) semantically secure under a chosen-plaintext attack.

I can't seem to find a good reference explaining this.

I think I am missing a fundamental concept, so If I explain it as I see it perhaps someone can correct me.

Semantic security means that the adversary cannot learn anything about the plaintext from the ciphertext (except for the length of the message which is known beforehand).

I.e. the message is entirely indistinguishable from random bits.

So it seems to me that if a stream cipher is using a true PRG, it's output will always be indistinguishable from random, a chosen plaintext attack will not assist the adversary.

However if the encryption is deterministic then a chosen plaintext attack will reveal "information" about messages, as the ciphertexts can be compared to one another.

Am I missing something?

share|improve this question

2 Answers 2

Encryption using a block cypher such as AES by passing plaintext blocks directly to the encryption function is known as Electronic Code Book mode (ECB) and is not CPA secure as (as you say in your question) it is entirely deterministic and two identical plaintext blocks will result in two identical ciphertext blocks.

To prevent this an initialisation vector or nonce can be used in combination with a cryptographic mode such as cipher block chaining or randomised counter mode which will prevent the encryption from being deterministic and allowing the comparison of ciphertexts.

share|improve this answer
    
How about stream ciphers? Is there a way to make a stream cipher not be deterministic? –  trideceth12 Jan 20 '13 at 13:14
    
With a stream cipher the key is one time only. If you re-use a key the effect is the same as using a one time pad more than once. –  Andy Jan 20 '13 at 14:10
    
Could you mark the question as answered please? –  Andy Jan 22 '13 at 11:27
    
The stream cipher issue is generally addressed by introducing an IV as part of the stream cipher's key somehow, unfortunately there is no generic way to securely accomplish this (unlike for block ciphers) which is why stream ciphers often end up being used with the same key (or related keys) more than once. –  Thomas Jan 24 '13 at 13:01

To be secure against a chosen-plaintext attack, an encryption scheme must be non-deterministic — that is, its output must include a random element, so that e.g. encrypting the same plaintext twice will result in two different ciphertexts.

Indeed, if that was not the case, an attacker could easily win the IND-CPA game just by using the encryption oracle to encrypt the challenge ciphertexts in advance, and then comparing the response to the challenge with the ciphertexts obtained from the oracle.

Now, the usual way in which this non-determinism is achieved is by choosing a random "tweak" or "IV" of sufficient length (say, 128 bits), combining it somehow with the key to change the way the plaintext is encrypted, and then including it as part of the ciphertext. That way, it's as if every plaintext was encrypted with a different, random key, and there are so many possible effective keys that it's basically impossible for any of them to ever be used twice.

Of course, the tweak or IV itself need not be truly random; it only needs to be indistinguishable from random by any plausible attacker. For example, the output of a cryptographically secure pseudorandom number generator (which is pretty much the same thing as a stream cipher) seeded with a truly random number (or, again, something indistinguishable from it) will do just fine.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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