Key secrecy vs Algorithm secrecy

Question

it's a well known statement that

"Cryptographic security must rely on a secret key instead of a secret algorithm."

I would like to ask about some details about it. And which are their differences?

I see the obvious thing that for a multi user system, generating a key is overwhelmingly easier than generating a distinct alghorithm for every user pair, (and even for a single pair of users one could argue that updating the key is easier)

But, Is it the only argument?

I mean, if we define

AlgorithmA = AlgorithmX + key A
AlgorithmB = AlgorithmX + key B

Then a change on the key is not different from a change in the algorithm.

The only different I see is that for a new pair of users/keys

• Most of the Algorithm structure remains constant in the case of secret key,

• Most of Algorithm structure need to change in the case of secret Algorithm

But where is the limit? "most of" meaning?

I would like to have more views and clues to understand why this distinction is usually mentioned.

Answer 1

Problem Definition

The goal of cryptography is to approximate a process whereby

crypt(x)

conveys no information about x but there exists a function decrypt such that

decrypt(crypt(x)) == x

If decrypt and crypt were only done in the same run of the same program, you could implement this perfectly using hidden state:

var map = {};  // A hidden hashmap.

function crypt(x) {
  var k = unique_unforgeable_value();
  map[k] = x;
  return k;
}

function decrypt(k) { return map[k]; }

In practice though, crypt and decrypt are called by different programs or different runs of the same program, so we need to approximate crypt using a deterministic function whose output is indistinguishable from random bits -- it has to be incompressible (in the Shannon coding sense) so there are no extra structure bits that can be used to glean information about x.

Algorithms are highly structured therefore compressible. So what we need is a way to get apparent randomness while retaining the determinism that is required for $decrypt \circ crypt = identity$.

Answer

By currying a simple compressible algorithm with an incompressible secret

crypt = crypt_algo(secret)
decrypt = decrypt_algo(secret)

we can approximate the goal above. crypt and decrypt have high information content due to the high information content of secret even though crypt_algo and decrypt_algo have low information content.

secret needs to be kept from attackers for this to work since otherwise an attacker could simply do the currying above. The algorithm does not need to be kept secret since it only provides a small portion of the information content of the curried function.

Caveat

"Cryptographic security must rely on a secret key instead of a secret algorithm."

I disagree with the instead of part.

You might get some measure of defense-in-depth by keeping both secret, but testing crypt_algo is hard, so historically, secret algorithms developed in-house by amateurs have fared worse when subjected to attack than those which have been carefully reviewed by large numbers of professional cryptographers. This is why security by obscurity has gotten a deservedly bad name. The "obscurity" there refers to attempts to keep the algorithm secret as a substitute for properly protecting keys.

Answer 2

The distinction you want to make between the key and the algorithm proper is not based on whether most of the operation is contained in one or the other, but on where the complexity lies. I am not talking about algorithmic complexity here, but complexity in its everyday meaning: difficulty to understand and reason about.

The algorithm proper is complex and hard to reason about. It generally does a whole bunch of arbitrary-seeming bit manipulations, logical and arithmetic operations, and general shuffling of the data. It's very hard for a layperson or even for a cryptographer to know how much privacy all those manipulations actually buy you, and what kind of cryptanalysis it might be vulnerable to. So the best way to be confident about the algorithm's security is to put it out in the open and have it reviewed by experts as widely as possible. MAKE IT PUBLIC.

The key, on the other hand, is a simple concept: it's a bunch of bits which need to be random. There is no need to review the key to assure the correctness of the crypto. Any key is supposed to be as strong as any other key (and if this is not true then it can in principle be discovered by review of the algorithm, not the key). We know that the quality of randomness that is available to generate keys is less than perfect, so in practice some keys may be weak due to lack of randomness, but at least everyone can know without needing to be an expert cryptographer and without needing to make a difficult analysis of the key that good randomness WILL lead to a good key. So use the best randomness you've got available then you need not (MUST not!) share the key with everyone in order to have confidence in your crypto.

Answer 3

I asked the same question a few years ago from one of the well-known experts in cryptography.

The more interesting point here is that you can think of the key to contain the algorithm's code and the algorithm being a simple Universal Turing Machine (UTM). Remember that we want to do is having a fixed algorithm for the cryptographic task that doesn't change from one run of the algorithm to another run, if you consider the key to be part of the algorithm then the algorithm needs to change each time to make sure it is secure. With a fixed algorithm plus a randomly chosen key we don't have that problem.

The original difference is more clear if you think about the pre-modern cryptography. If the adversary knew the algorithm everything was lost, it would be of no use, keeping algorithm was essential. If in one particular case the algorithm was known everything would be lost for all future uses. In modern cryptography, the key is not part of the algorithm, it is chosen randomly, revealing the cryptographic algorithm (and even the previously used keys) doesn't compromise the security of its future uses since in the future runs the key will just another randomly chosen string and that would grantee the security, the previously used keys are of no help in breaking the new run.

So what happens if we consider UTM plus a random key? Unless the key has a nice structure you cannot prove that the algorithm will be secure, e.g. a key chosen randomly from the uniform distribution will not work. The key would need to be "essentially" a fixed algorithm plus a random string in which case it is not really different from moving the fixed algorithm part of the key into UTM, it is not changing from one run to another.