Doesn't the choice of encryption algorithm add entropy by itself?

Question

Let's say someone has my encrypted data and he wants to decrypt it. People always talk about how the length of the key (e.g. 256 bits) decides about the entropy of the encryption, which totally makes sense. If the attacker tries all 2²⁵⁶ possibilities, his great-great-…-grand-children will have my data.

But what if all the years he was using the wrong algorithm? Isn't the choice of the algorithm itself adding entropy as well or am I wrong to assume this? So instead of naming my file super_secret.aes256 I would just name it super_secret.rsa256 or maybe even not give it a file ending at all?

Answer 1

If you’re designing a cryptosystem, the answer is No. Kerckhoffs's principle states “A cryptosystem should be secure even if everything about the system, except the key, is public knowledge.” Restated as Shannon's maxim, that means “one ought to design systems under the assumption that the enemy will immediately gain full familiarity with them.”

Making the assumption that the attacker won’t learn your algorithm is security through obscurity, an approach to security that is considered inadequate.

Relying on the attacker to not know the algorithm won’t add any work on his or her end, because according to Kerckhoff, he or she either knows it, or can be reasonably expected to find out. If it adds no uncertainty it adds no entropy. And their capabilities are not something you can quantify.

In the case of a lost cryptosystem, like you describe, there is usually enough historic or statistical information to determine the nature of the algorithm (if not the key itself.) But you can’t design a system under the assumption that it will be lost as soon as it’s used. That’s OpSec, not cryptography.

EDIT Comments have mentioned using algorithm selection as a part of the key. The problem with this approach is that the algorithm selection must necessarily be determined prior to the decryption of the data. This is exactly how protocols such as TLS work today.

If you’re truly looking to mix algorithms together and use a factor of the key to determine things like S-box selection, etc., you’re effectively creating a singular new algorithm (adopting all the well-known risks that rolling your own algorithm entails.) And if you’ve created a new algorithm, then all of the bits of the key are part of that entropy computation. But if you can point out specific bits that determine algorithm instead of key material, you still have to treat them as protocol bits and exclude them.

Regarding secrecy of the algorithms, your protocol may be secret today but if one of your agents is discovered and his system is copied, even if no keys are compromised the old messages are no longer using secret algorithms. Any “entropy” you may have ascribed to them is lost, and you may not even know it.

Answer 2

In practical terms, no, as John's answer neatly explains.

Hypothetically, if you had enough secure encryption methods to choose from, you could potentially select one method at random and use it to encrypt the data using – for example – a 256-bit key. The choice of algorithm used would need to be "added" to the key and become part of the "not to be revealed secret" (taking the combined entropy to 259 bits if there were eight encryption algorithms to choose between).

The problems with doing this include:

• Only a small number of bits are added: eight algorithms only adds three bits of entropy. To add eight bits (for a total of 264 bits with a 256-bit key) would require 256 different encryption algorithms. Finding enough secure algorithms to make a practical difference is almost certainly much harder than simply extending the key-length of a single, known-to-the-attacker, algorithm.

• You have to "extend" the key with the choice of algorithm: this means passing the choice to the "user" to be "remembered" alongside the normal key. This greatly complicates the process of key-management. Storing the choice in the encrypted data is a non-starter, since an attacker with "total knowledge" would be able to find the information and know which algorithm to use.

• If any of the algorithms chosen leave some kind of "fingerprint" that allows an attacker to identify the algorithm used (or at least reduce the range of possible algorithms), then this will (partially) nullify the extra bits of entropy.

All-in-all, it is much easier to extend the length of the key used and not worry that an attacker knows the encryption method.

Answer 3

The answers from @John Deter and @TripeHound explain things very well, but I wanted to give an example that would put Kerckhoffs's principle in context. It's natural to approach these questions from the perspective of an outside attacker, but that's not the only relevant threat model. In fact, roughly half of all data breaches start from inside agents (aka employees, contractors, etc...), with a mix of both accidental and intentional leaks.

More realistic Threat Vectors

Having a hidden encryption algorithm may help against an outside attacker if they can't easily deduce what system you used. However, it provides absolutely no additional protection against an inside attacker who have access to your code. As an extreme example, if your system keeps critical Personally Identifiable Information (PII) in your database, but both production database access credentials, encryption algorithms, and encryption keys are stored directly in your code repository, then you have effectively given everyone who has access to your code repository access to all of your customers' PII.

Of course you don't want to do that, so you keep production systems segregated from everyone expect admins, you keep encryption keys stored in a separate key management system accessible (as much as possible) only to the application, etc... Your developers know what encryption algorithms are used (because they can see it in the code repository), but they don't have access to the production database, and even if they did get read access to the database they wouldn't have the keys to decrypt the data that is there.

Applying Kerckhoff's Principle

That's the whole point of Kerckhoffs's principle - the only thing that you have to keep a secret is the actual secret (aka your encryption key). Everything else can be known by everyone and you're still secure. Which is good, because keeping just one secret is hard enough. Trying to devise a system that hides not just the keys but also the encryption algorithms and other details from as many people as possible is quite a bit harder and more prone to failure.

In short, people are bad at keeping secret. As a result, designing your system so you have less secrets to keep actually makes you more secure, even if it seems counter intuitive. After all, what you suggest makes sense on some level: why should we only encrypt our data? Let's hide the encryption method too and be extra secure! In practice though, hiding more things gives you more room to make mistakes and a sense of false security. It is much better to use an effective encryption method that makes keeping secrets as simple as possible - hide the key and the message is secure.

Answer 4

Abstractly, if there were 2^n encryption schemes that were exactly equally hard to break, and had the same space of possible keys, then sure, you could define a new encryption scheme as "randomly pick one of these 2^n schemes" and effectively consider those n bits to be added to the key.

But in practice, even if this were possible, that's a lot of unnecessary complexity when you could instead just pick a single algorithm and make the key a bit longer.

Answer 5

I think OPs question demonstrates insight and the answer is, at least in theory, yes it does. There is something here. I think that's the first point that should be made. The responses given are mostly of the view: in practice it doesn't work like that. These aren't wrong but I think they miss the validity/interest of OP's point.

The way I reason this: From a theoretical black box point of view the choice between 2 encryption systems is analogous to the choice of the first bit of the key. In fact they really are the same thing (if you add the bit back). In a black box, there really is nothing special about the key. They are just a good way of enumerating your options of which encryption transformations you want to use.

To see this:

Say I make a new variant of AES128 lets call it JES_0_128. The way this works is: I add a a binary encoding of 0 (in this case 128 zeros) to the front of the key supplied and use this in (standard) AES256. Then I make another one called JES_1_128: an encoding of 1 etc all the way up to JES_(whatever 2^128 is in base 10)_128. All of these are perfectly valid 128 bit key encryption algorithms. But if you don't know which one... it's a 256 bit key encryption algorithm. AES256 to be precise. Which is indeed a lot more entropy.

The differences the other answers point out is that in practice a key is a really good way of picking which of the 2^256 AES-256 encryption algorithms to use. It's flexible, well understood and leaves the generating and trusting of the mutual secret to the users. Why use anything else?

On the other hand, picking one of the handful of 256 bit families of encryption algorithms to use and hard coding it, is not a very good way. Even relative to a very small increase in key size. Or at all. You may as well just tell everyone. From a practical / writing software / type point of view this is not at all safe to rely in this being kept from an attacker of any interest. There are a host of reason why. Not least because if an attacker had a copy which value you picked would be easy to test which. But they are 'just' practical considerations...

Answer 6

If you just encrypt something with one algorithm and pretend another one was used, Kerckhoff's principle applies as pointed out in other answers, so that's kinda useless, at least against an attacker with knowledge about our implementation. It will still "work" against an attacker who e.g. steals the encrypted file from your OneDrive or whatever cloud store without knowing anything about it.

If you require the choice of encryption algorithm to be included in the decryption process (i.e. your tool chooses one out of several algorithms, depending on what you input) then you effectively add bits to your key length. Kerckhoff's principle does not apply here. It is however kinda hard to add a significant amount of bits -- one would need many algorithms to choose from -- and it doesn't make any sense (see last paragraph).

In either case, whatever you want to do is pretty much pointless. The assumption that someone's great-great-grand children may have your data if they invest a couple of billions in equipment and elictricity bill is arguably true for keys in the 90-100 bit range. Although realistically, nobody (not even the NSA) would do that. The cost-benefit ratio doesn't give that away. Social engineering, or torture followed up by murder is a much cheaper, faster, and practical approach.

For anything noticeably larger than 110 or so bits, a brute force attack isn't realistic even if you neglect the cost-benefit ratio. You should be more worried about backdoors built into AES which is more likely to be the case than you seeing one single 128 bit key broken by brute force during your lifetime.

Now, the mere idea of cracking a 256-bit key via brute force is outright ridiculous, and the idea of adding bits on top of that is nonsensical, it makes exactly zero difference. Impossible doesn't get any better than "impossible".

Answer 7

I think this is a good way to look at it:

You have a secret, which may be a 256-bit key, or a password from which you derive that key, or either of those plus other information like which encryption algorithm you used.

The attacker wants to guess your secret. They do this by trying various possibilities until they find the right one or they run out of time, money, or motivation.

You have no idea what possibilities they are trying. In your question, you say "what if all the years he was using the wrong algorithm?" and the only answer to that is "what if he wasn't?" You have no control over that. If you knew which possibilities the attacker was going to try, you could just pick anything not on their list as your secret, and the security problem would be trivially solved.

What you can do, though, is roughly estimate how many possibilities they can try before running out of time and/or money, based on the state of computing technology. This assumes that they don't secretly have access to technology that the rest of the world doesn't, such as quantum computing or a backdoor in AES - which is probably a safe assumption since they would have better things to do in that case than try to crack your password. (Cf Cut Lex Luthor a Check, though see also this rebuttal.)

You can also prove the following result: if you choose your secret uniformly at random (using a high quality RNG) from n possibilities, and the attacker tries k possibilities, no matter what they are, the chance that they'll guess your secret is at most k/n.

The nice thing is that n grows exponentially with the amount of information you have to store/remember, whereas k grows only linearly with the amount of time/money they spend, so it's not hard to make k/n very small.

So, you should choose your secret uniformly at random from a large set of possibilities. A random 256-bit symmetric key is chosen uniformly from a set of size 2²⁵⁶, which is (far more than) large enough.

You can pick randomly from a bag of (algorithm,key) pairs as well, but it's pointless because any single algorithm already offers plenty of choices.

You can pick an obscure algorithm and hope that the attacker won't try it, but that's not picking at random any more, and therefore you can't prove that it helps at all. If there were no other options then this would be better than nothing, but there are other options.

This is the fundamental reason that cryptographers advise you to treat only the key as your secret: there are plenty of keys and keys are the easiest thing to choose at random. You don't need anything else.