0
$\begingroup$

Since the practical security of a symmetric-key primitive is determined by evaluating its resistance against an almost exhaustive list of known cryptanalytic techniques.

My problem is that could we evaluate the minimum complexity of key recovery of a cipher from an information theory perspective when the success probability $p$ is given ?

For example: The best single-key attacks against 7-round AES-128 by impossible differential attack that is : Data complexity is $2^{104.9}$, Time complexity is $2^{110.9}$ and Memory complexity is $2^{71.9}$.

Do these numbers have lower bound? We know the upper bound of Time complexity of key recovery is $2^{128}$ and the probability of success is 1, so the lower bound of complexity of key recovery determines the difficulties of recovering Key thus maybe exist.

Also if these lower bounds exist maybe the security of different cipher could be comparable directly. If there is any relevant research available I would greatly appreciate it.

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ Are you asking about the least possible time it might take? Well, you could start guessing keys, just happen to guess the correct one at first, and so the minimum time taken would be 1 AES operation. Is that what you're asking? $\endgroup$
    – poncho
    Commented Nov 14, 2023 at 13:58
  • 1
    $\begingroup$ You should consider probabilities. If you try one key, you have odds $\frac{1}{2^{128}}$ of finding the correct key, and so on. After testing $2^{127}$ keys you will have $\frac{2^{127}}{2^{128}}=0.5$ odds of having found the correct key $\endgroup$
    – Ruggero
    Commented Nov 14, 2023 at 14:21
  • 2
    $\begingroup$ There is somewhat of a disconnect between the title and the question. The body seems to make it clear that the goal is the complexity of key recovery. Key recovery is not the only way algorithms get broken. Other attacks when possible are usually cheaper. Can you clarify this point? $\endgroup$
    – Marc Ilunga
    Commented Nov 14, 2023 at 15:24
  • $\begingroup$ And, @MarcIlunga the title is a bit complex as researchers did in AES. They counted the necessary operations on the AES and their idea to conclude that it is faster than brute force. $\endgroup$
    – kelalaka
    Commented Nov 14, 2023 at 15:41
  • 2
    $\begingroup$ what does "minimum complexity of recovering all keys" mean? You need to correct and clarify this question. Use mathematical notation as needed. $\endgroup$
    – kodlu
    Commented Nov 14, 2023 at 15:46

1 Answer 1

Reset to default
1
$\begingroup$

For common cryptographic algorithms, there is no known lower bound to the complexity of key recovery with a given (and sizable) probability. We can't mathematically exclude the possibility of a much better attack than those known.

Even if we reason asymptotically, we don't have a proof that there exists any encryption algorithm such that the difficulty to find the key (with a fixed non-zero probability) grows exponentially with the bit size of the key. That would require proving the $P\ne NP$ conjecture.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for your answer and this has helped me a lot. $\endgroup$
    – HelloSpace
    Commented Nov 15, 2023 at 11:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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