0

I was thinking about a thought experiment.
Let's imagine a world full of crackers such that whenever you encrypt something there will be someone who will try to crack your cryptographic key through bruteforce.
Suppose furthermore that we are using secure key based cryptography where keys are randomly generated by the creator such that on average it will need unsustainable computational power to crack it (not much different from reality).

Suppose that in the initial state of our system all crackers use a rudimentary algorithm that starts from 0 and searches the key one by one by bruteforce.
Now let's imagine that we want to encrypt our message in the mentioned world, we run our RNG and we get 10 (a low value). For the hypothesis above we are absolutely certain that if we encrypt the message with 10 as key it would be immediately cracked. So we need to drop 10 and basically we have to raise the floor of our RNG, reducing the key space size, or to shift it completely. When most encrypters will end up adopting these measures as a consequence crackers will start to change their starting point for bruteforce and I guess we will get some kind of predator-prey process. Now I know it's not a specific question but I was wondering if there is any scientific literature about this phenomenon, if it has a name and basically if there is any kind of reference to something similar somewhere. I googled things like "Cryptography game theory" and similar but did not really find anything pertinent.

Improve this question
2
  • 1
    Reminds me of the Unexpected hanging paradox. The location of the key in a sequential search is the unexpected thing, and instead of "you will be surprised", the paradoxical clue is "you won't find it quickly".
    – user54862
    Jul 28, 2018 at 18:03
  • I can actually recognize some similarities, yes.
    – Claudio P
    Jul 28, 2018 at 18:23

2 Answers 2

Reset to default
2

Any usable random source for keys will give you keys that are as randomly distributed across the whole key space as possible.

Thus, the expectation value for "an attacker tries this key in their N-th attempt" is N=|key space|/2.

If you have knowledge of your attacker's search order, you can of course exploit that. But in practice, it's always going to be worse to restrict your key space (or change the uniformity of key generation), because you then give your attacker, who previously had 0 bit of info on your key, some amount of bits of certainity about your key.

Best case is that the slow down in attack is linear to the secrecy you've lost, but realistically, you weaken your overall system, because from a non-uniformity of the key bits follow non-uniformities in the ciphering process, and suddenly you're converting a cipher against which the best attack is a brute-force one, into one where you can make statements about the plaintext from the ciphertext without even knowing the key completely.

So, no, don't do that.

Improve this answer
4
  • All this is already implicit in the question, which indeed tries to study the consequences that a high number of threats has over the choice of a method to chose a key. The problem is that in a situation as that described above, the theoretical mean of the number of attempts does not consider the fact that some of those value are certainly insecure because the hypothesis of the uniform distribution of the attempts is wrong.
    – Claudio P
    Jul 28, 2018 at 18:17
  • 1
    My answer addresses exactly that: the fact that the test order isn't uniform but ordered mustn't have an effect on key generation. The time you might slow down the attacker is only best-case as much as you speed it up. Restricting your key space is a zero sum or losing move, in every situation. Hence, you don't do that move.
    – Marcus Müller
    Jul 28, 2018 at 19:05
  • But you are wrong in that. You are silently making the hypothesis that you are doing your key space restriction based on information of a single or limited number of attackers and still supposing that the uniform distribition hypothesis is valid for the rest of the world, but this is not the case. Indeed it is clear that in the situation above restricting, at leat temporarily, the key space effectively reduces the probability thay your message get cracked. You are practically talking about a case of overfitting.
    – Claudio P
    Jul 28, 2018 at 19:21
  • 1
    No! That's exactly my point: By changing the probabilities of your key distribution, you best case earn as much as you lose. You can measure all your attacker knows about your key and data in bits. By shifting the probability of that, you give them bits. Even if they don't know exactly what you've done, you've still given them info about your key and hence weaken your system. There's really no positive side about this trade off. It's simply bad from a cryptographic point of view . It's really basic information theory why you don't do that.
    – Marcus Müller
    Jul 28, 2018 at 19:43
0

I take it you are asking why we should accept keys that are at the "beginning" of the keyspace, given that, intuitively, an attacker will start at the beginning and progress onward. The answer is simply that an attacker will make use of parallelism, splitting the keyspace up into smaller chunks and working on each chunk in parallel. For a keyspace from 0 to 99, they will not start at 0 and go forward. Instead, they will spawn ten workers that start at 0, 10, 20, etc. and each only need to cut through a fraction of the keyspace. Because of this, it's not safe to assume that putting the key higher up in the keyspace will make it take longer for an attacker to find it by exhaustive search.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.