# Do ciphertexts leak information about their algorithmic creators?

If an adversary holds thousands of encrypted files that were encrypted with the same cipher, can he determine which cipher method had been used on the files? Assume that the adversary has no prior knowledge about the encryption environment.

Details: Let's say I have a encryption program that allows me to select 1 out of 5 well established and well implemented encryption algorithms. I use that program to encrypt thousands of file, using always the same block cipher, while following proper cryptographic procedures (e.g. use different passwords every n files encrypted). The files are stored off-site, and an adversary gets a hold of the files. I wonder if by selecting a less common algorithm, e.g. Serpent, I would increase the workload of the adversary by factor of 5, or encryption algorithms do leak some information, some recurring properties, that will help the adversary to identify the encryption method I had used?

-
I would remove the "Details" part out of the question and your protocol. Choosing a different cipher does not strengthen the security sufficiently to make it worth while. Using 5 different schemes you would only strengthen your scheme by 2.5 times (as the attacker will only have to test until the plaintext is revealed). That can be compared with adding about 1.25 bits of security to the key. You would severely complicate your protocol. Furthermore, about 20% of your users would still be affected if an attack is found on one of the five ciphers. –  Maarten Bodewes - owlstead Aug 29 '13 at 9:42

A good block cipher should be indistinguishable from a random permutation (otherwise it is considered broken). A consequence of this is that two good block ciphers are indistinguishable from each other (with at most a doubling of the adversary's advantage).

In your scenario, it means that finding a way to succeed in learning which algorithm has been used implies finding a cryptanalytic attack on at least one of the algorithms you are considering.

[Note that this answer disregard any implementation flaw in your program that would leak the algorithm being used.]

-
I am more concerned about out-in-the-field good crypto program, not a theoretical cipher. If a practical cipher whould produce a perfect random output, we could have used it as a perfect RNG, which is not the case. So I wonder if any approved cipher engine out there (e.g. AES-128, Twofish, Serpent etc) might somehow leak out a characteristic tell-tale sign of their algorithm. I guess that an answer to this question may appear in some cryptanalysis paper, but I don't know of any. –  Ninveh Aug 24 '13 at 17:58
Minar's point was that a good block cipher is computationally indistinguishable from a random permutation. That is, AES (with a random key) may not be a perfect random permutation, but in practice attackers cannot tell the two apart. This is a design goal for block ciphers that is expected to hold "out-in-the-field"; if someone were to demonstrate that AES lacks this indistinguishability property in practice, they would send cryptographers scrambling for a new block cipher. Most experts believe this is unlikely to happen any time soon. –  Seth Aug 24 '13 at 18:22

Note that a block cipher is not an encryption algorithm. It's a building block. To get encryption you need a mode-of-operation that uses that block cipher. For example CBC-AES128 (and even here, it's not clear how the IV is being generated).

Many encryption algorithms overtly leak their identity. Some have packaging, they put the IV in a weird place, they use padding. It is not a requirement for security that the algorithm used be obscured whatsoever.

Now we can re-interpret your question differently and say, "Suppose you take a list of 128-bit block ciphers and you generate a list of 1 billion random 128-bit plaintexts, enciphering each under a random key with every block cipher in the list. Can you tell which cipher is which simply by examining the ciphertexts?" In other words, does some block cipher have a "signature format" to its output? No, it isn't possible. Because block ciphers are permutations (given a fixed key) so worrying about "block cipher XYZ tends to output a lot more 1's than 0's" cannot happen.

-
"Many encryption algorithms overtly leak their identity" - which ones? –  hunter Aug 24 '13 at 17:47
@Fixee: I meant an encryption engine using a block cipher - an approved cipher engine like AES-128, Twofish, Serpent etc. So if, as you claim, there are some indications as to a known IV structure in some ciphers, then one can deduce for example, seeing a 256 bit IV, that engines of 128 bit have not been used in the process. This is my concern: since algorithms used are normally public knowledge and are not meant to be secret, they might leak some info out. I wonder if the literature has any info on this. –  Ninveh Aug 24 '13 at 18:17
The other way the encryption algorithm is leaked is via the protocol. For example, TLS negotiates which ciphersuite it'll use in the clear; hence anyone listening can determine which cipher is (initially) being used, but not by a specific cryptographical weakness. –  poncho Aug 24 '13 at 19:13
@Ninveh You're confusing block cipher encipherment with full-blown encryption again. The concept of an "IV" does not apply to AES, Twofish, Serpent, etc. That's an idea used with modes in order to (typically) implement randomization. So you can't say "IV structure in some ciphers". In any case, the normal approach to security in crypto is to NOT try to hide which algorithms have been used at all (unless you are the NSA). –  Fixee Aug 25 '13 at 3:08
@Fixee - I have a difficulty following your nuance in terminology. In commercial programs and books I looked at, although there is a noticable tilt toward defining cipher as a building block of an encryption algorithm, many use cipher and encryption process interchangeably. openSSL, for example, calls blowfish AES etc ciphers. See openssl.org/docs/apps/enc.html . And openSSL and various books do refer to IV as an injectable entity to Feistel block cipher in AES for randomization, so the concept does seem to apply. Anyway, I assume that from my detailed scenario my intent was clear. –  Ninveh Aug 25 '13 at 6:00

No, giving your users the ability to choose the encryption scheme, and telling them to choose a less common block cipher, will not increase the security strength. As long as each option is equally strong, it will however not decrease the security strength, compared to if there is only one option for the encryption scheme.

The reason for this answer, is that you give the users explicit control over which cipher to use, and ask if choosing a less common one, might increase security. This is somewhat equivalent to arguing that choosing "p455w0rd" instead of "password" for password, would be relatively more secure. It is not, if it is done consistently. It is, if each of the letter/digit substitutions is selected randomly.

Hence, a better question would be: Assume your software is deriving a $128$ bit key from a password and use it for encrypting files with a single encryption scheme. Would deriving a $k+128$ bit key and using the extra $k$ bits for picking one of $2^k$ encryption schemes be more secure?

The answer to the alternative question, is that it might be, but there is still no guarantee that you get $k + 128$ bit security in the latter case, even if you get $128$ bit security in the former case.

The first thing we must assume is that the password you use, does in fact have at least $k + 128$ bits of entropy. If it doesn't, the effective strength will be bounded by the entropy of your password, and adding the block cipher choice component, will not increase security.

-
@ Henrick: I fail to see the applicability of the password substitution example you provided, since attacks on passwords carry different methodology compared to attacks on cipertexts. Just as side note, I think that with your PW example I will increase the strength if I choose a consistent (i.e. non-random) substitution character(s) outside the 7-bit ANSI range, since dictionary attacks will fail on that. (continued) –  Ninveh Aug 25 '13 at 18:33
Now, why aren't you sure that I can realize 128+k cipher strength of I choose one among k encryption engines (assuming a PW of 128 strength or more) ? please consider the following 2 scenarios: (continued) –  Ninveh Aug 25 '13 at 18:35
1.If an attacker carries a futuristic computer such that iterating through 2^128 key space would be feasible, she would still have to go through k key-space cycles - in effect the strength is increased to 128 + log2(k) 2. If we talk about practical attacks, the only option that I see is finding a weakness in an algorithm, let's say reducing its cipher strength to a barely feasible 2^70. Such weakness will surely impose months of effort to decrypt but has a chance of only 1:k to succeed if the algorithm is not known - again increasing the strength of my proposal by a work factor of k. –  Ninveh Aug 25 '13 at 18:36
@Ninveh: If an attacker has software that carries out a dictionary attack, modifying it so that it tests words with a constant letter substitution is trivial, and the modified attack will run in the exact same time as the generic attack. –  Henrick Hellström Aug 25 '13 at 20:30
@Ninveh: The problem I pointed out is human choices have low entropy. Giving a human a choice between $n$ options, will not correspond to $log_2(n)$ bits of entropy, but far less. Also, the argument that one of the ciphers might be broken, is a completely different one. This is the usual reason why encryption software includes multiple versions - not to increase security, but to make it possible for users to use a different cipher, if their first choice gets broken. –  Henrick Hellström Aug 25 '13 at 20:38

Look up semantic security. The top ciphers you'd consider all have semantic security, which basically means that an efficient adversary cannot tell the difference between a plaintext encrypted with a one time pad and a plaintext encrypted with any given semantically secure cipher.

Since that is true of each cipher, then you cannot distinguish between individual ciphers, either.

-

Your problem is not with the encryption engines, because their output will not reveal patterns if implemented correctly. The output of the cipher is a bitstring with roughly the same length as the input, + some overhead for the IV.

• Since the IV is chosen randomly uniform from its entire domain, this does not reveal anyway.
• The ciphertext appears to be the output of a random function.
• This means, the complete data is just random without knowledge of the key.

The real problem here is, that your own program will not be able to know which encryption scheme to use. Even if you have the key, you still don't know which algorithm to choose, since the key should also be random uniform from its entire domain.

So in order to be able to distinguish between encryption schemes in your program, you need to add some kind of pattern in the key or the ciphertext or the IV, or some encapsulation. And this might decrease the security of your scheme, because an attacker might know this pattern, too.

In general, when estimating security, you should always assume that the attacker knows everything except the key.

-
It is possible to put a pattern e.g. in the first block of the plaintext to quickly establish the algorithm to be used. The IV does not need to be unpredictable or random for modes other than CBC. Otherwise most of the answer is correct, but I don't think it adds much to the other answers already provided. The last sentence is right on the mark though. –  Maarten Bodewes - owlstead Aug 29 '13 at 9:48

Yes, they do. For example, suppose all of the files where a multiple of 8 or 16 bytes. That would be good evidence of a block cipher. Or, suppose only the characters A-Z appear in the encrypted file. That could indicate that it's a cipher like Enigma.

You can rarely say for certain, but you can often infer information. This isn't a great defense, though. To try the top 40 ciphers when cracking your files slows down an attacker, but only as much as if you had one extra character in your password.

And, of course, there are alternate ways of inferring what cipher is used. For example, if someone connects over the internet on port 22, they are probably using SSH. Further, they are probably using the latest version with default settings. Going back to filesystems, there are programs which can identify Truecrypt containers fairly accurately.

-
The question was about encrypted files, which are almost always block ciphers. This doesn't help in deciding, which block cipher it actually was. Besides, I don't think anyone would encrypt files with the Enigma today, especially in computers with all sorts of encodings, where A-Z is none of them. –  tylo Aug 29 '13 at 9:31