Information Security Stack Exchange is a question and answer site for information security professionals. It only takes a minute to sign up.
Sign up to join this community
I'm having trouble understanding AES and would like to know if encrypting the same text with the same key two times in a row should give the same output.
Is there any salt or something that would change the ouput?
If it doesn't give the same thing, how could one decrypt the message (with the key) if the salt is random and he doesn't know it?
If it gives the same thing, could rainbow tables be used to recover the message?
A blockcipher like AES is a keyed permutation. In the case of AES it takes a key and then turns a 16 byte block into another 16 byte block deterministically.
To encrypt something with a block-cipher you need to use a mode of operation. Typically those modes take an IV (similar to a salt) which should be different for each message you encrypt. This difference in the IV leads to a totally different encrypted message. Encrypting the same message with the same IV and key returns always the same ciphertext. Encrypting several messages with the same IV and key weakens security, but by how much depends on the mode.
The required properties for an IV depend on the chosen mode, sometimes it needs to be unique(e.g. for CTR mode), sometimes it needs to be unpredictably random (e.g. for CBC mode). But it generally doesn't have to be secret, so you send it to the recipient alongside the ciphertext, typically as a prefix.
There are some modes designed for deterministic encryption. Using those modes you still leak if two messages are the same, but nothing more. You should only use those modes when you require determinism.
AES is a block cipher: it takes as input a block (16 bytes, in the case of AES) and a key (16, 24 or 32 bytes, for AES), and outputs another block (again, 16 bytes). It is a fully deterministic algorithm, fully specified, and everybody in the world ought to obtain the same output block for the same input block and key.
However, you don't encrypt a block, you encrypt a message. The block cipher is only a building element; actual encryption uses a mode of operation which invokes the block cipher repeatedly. There are good modes, and there are bad modes; the goal is to achieve confidentiality of the message as a whole and not leak partial information, such as whether two parts of the message are equal to each other. In particular, if we are to encrypt two messages with the same key, we usually do not want to reveal whether the two messages were identical or not, so something has to change, somewhere, between the two encryptions.
Most modes of operation use an initialization vector which is where the non-determinism is injected. Some modes (e.g. GCM or EAX) require only a non-repeating IV; a counter can be fine for them, and can be implicit in some context (e.g. when there are successive messages on a given communication stream, the message number can serve as IV). Some other modes, notably CBC, are secure in all generality only if the IV is chosen randomly, uniformly, with a strong PRNG, and the next IV to use is not already known when the plaintext data is chosen. failure to meet all these requirements has been the source of many problems, e.g. the BEAST attack on SSL.
So one could say that secure symmetric encryption requires at least memory (for instance, to remember a counter value) or randomness. The "memory" can be a common worldwide counter (e.g. current time, but beware clock adjustments !).
If you are ready to tolerate the small leak about whether two given input messages are identical or not, then it is possible to have a fully deterministic, memory-less encryption system, but it will not be compatible with streamed encryption (you have to keep the whole message in memory during the process). Basically you compute a deterministic MAC algorithm over the message (such as HMAC) and use its output as IV. This is a two-pass algorithm, and that's rather unavoidable. If two source messages are identical, then they will yield the same encrypted message, but if they differ anywhere (even on their last bit) then, with high probability, the encrypted messages will be wholly different.
Unfortunately, platforms for which memory and/or randomness are hard requirements (e.g. smart cards) are also platforms where RAM is at a premium, and a two-pass system can be overly expensive.
