Avoid that repeated same messages look always same after encryption, and can be replayed by an attacker?

Question

I'm looking to authenticate that a particular message is coming from a particular place.

Example: A repeatedly sends the same message to B. Lets say this message is "helloworld" which is encrypted to "asdfqwerty".

How can I ensure that a third party C doesn't learn that B always receives this same encrypted string, and C starts sending "asdfqwerty" to B?

How can I ensure that when B decrypts "asdfqwerty" to "helloworld", it is always receiving this "helloworld" from A?

Thanks for any help.

Answer 1

For the former, you want to use a Mode of Operation for your symmetric cipher that uses an Initialization Vector. The IV ensures that every encrypted message is different, even if it contains the same plaintext.

For the latter, you want to sign your message using the private key of A(lice). If B(ob) has the public key of Alice, he can then verify she really created the message.

Finally, beware of replay attacks, where C(harlie) records a valid message from Alice, and later replays it to Bob. To avoid this, add a nonce and/or a timestamp to your encrypted message (yes, you could make the IV play double-duty as a nonce).

Answer 2

Add random value to the data being encrypted, and whenever it's decrypted, strip it from the original unencrypted data.

You need decent random number generator. I'm sure Google will help you on that.

Answer 3

C noticing that B receives twice the same encrypted message is an issue called traffic analysis and has historically been a heavy concern (but this was in times which predated public key encryption).

Any decent public encryption system includes some random padding. For instance, for RSA as described in PKCS#1, the encrypted message (of length at most 117 bytes for a 1024-bit RSA key) gets a header with at least eight random (non-zero) bytes, and a few extra data which allows the receiver to unambiguously locate the padding bytes, and see where the "real" data begins. The random bytes will be generated anew every time; hence, if A sends twice the same message to B, the encrypted messages will be different, but B will recover the original message twice.

Random padding is required for public key encryption precisely because the public key is public: if encryption was deterministic, then an attacker could "try" potential messages and look for a match (this is exhaustive search on possible messages).

Public key encryption algorithms often have heavy limitations on data size or performance (e.g. with RSA, you have a strict maximum message length, depending on the key size). Thus, it is customary to use a hybrid system: the public key encryption is used to encrypt a symmetric key K (i.e. a bunch of random bytes), and K is used to symmetrically encrypt the data (symmetric encryption is fast and does not have constraints on input message size). In a hybrid system, you generate a new K for every message, so this also gives you the randomness you need to avoid the issue of encrypting several times the same message with a given public key: at the public encryption level, you are actually never encrypting twice the same message (the same key K), even if the data which is symmetrically encrypted with K is the same than in a previous message. This would protect you from traffic analysis even if the public key encryption itself did not include random padding.

When symmetrically encrypting data with a key K, the symmetric encryption should use an "initial value" (IV) which is randomly and uniformly generated; this is integrated in the encryption mode (some modes only need a non-repeating IV without requiring a random uniform generation, but CBC needs random uniform generation). This is a third level of randomness, protecting you against traffic analysis.

When using asymmetric key agreement (static Diffie-Hellman), since are a bit more complex, because a key agreement results in a key K which you do not choose, and which could be the same ever and ever (between given sender and receiver). In that situation, protection against traffic analysis relies on the symmetric encryption IV randomness.

Asymmetric encryption protocols, such as OpenPGP, describe how the symmetric encryption, public key encryption and randomness should all be linked together, ironing out the tricky details. You are warmly encouraged not to reinvent your own protocol: it is difficult to design a secure protocol, mostly because one cannot easily test for the presence or absence of any weakness.

Answer 4

You may want to study block cipher modes of operation. However, the modes are designed to work on a data stream that is sent over a reliable channel. If your messages are sent out of order over an unreliable transport (e.g. UDP packets), I don't think you can use it.