Cracking a key using a combination of partial keys

Question

As part of a cryptanalytic attack I've carried out, I used a divide-and-conquer strategy to divide the secret key $k$ into several equal-sized partial keys $k = {k_1, k_2, ...}$.

The attack works successfully against these partial keys, and outputs a list of possible values for each partial key along with their likelihood. The list is ordered by likelihood such that the first value of the output is the attack's best guess for that part of the key.

This likelihood also tells me what kind of confidence exists in each partial key -- a certain high likelihood value means that the correct partial key will almost surely be in the first 10 best guesses; some other lower likelihood value means that the partial key guesses aren't as good and you only expect to find the correct partial key after testing 120 guesses.

What is the optimal strategy (in terms of number of attempts) to combine the partial key guesses into a guess of the entire key?

For this, let's imagine that, from the lists of partial key values, I want to build a list of possible (complete) key values, ordered by likelihood.

My best guess for the complete key is, trivially, the best guess for each partial key, and thus that's the first item in my list. For the second item in that list, I will take the partial key which has less likelihood, and instead of using the best guess, I'll try the second best guess and see if that works.

Now, how do I proceed to complete my list? I've already tried the second best guess of the least confident partial key, but indeed I could continue, and just brute-force the least confident partial key. After, I could do so for every other partial key, from least confident to most confident.

This approach is sensible, however, it may not be optimal. It seems to me that if I know the expected position of the correct value for the lists of each partial key, perhaps I don't actually need to test all the positions of the least likely partial key first, and actually, one of the more confident partial keys perhaps has the correct answer as the second best guess.

If I can define which kind of strategy is optimal, then I can finally reach my goal of computing the expected position of the correct value of the key in the candidate list of complete keys, in terms of the expected position of the correct values for each partial key. This is because my final goal is to get some measure of entropy (guessing entropy, for example) for the complete keys calculated from the partial keys.

If you know any scholarly sources (conference papers, articles, books, etc. for further reading) for this kind of problem and possible solutions, that'd be greatly appreciated.

Answer 1

If you know the probabilities $P(k_1), P(k_2), \dots, P(k_n)$ of candidate keys $k_1, k_2, \dots, k_n$, the fact that the probability mass function $P$ factors into a product for independent subkeys is irrelevant; if you sort the $k_i$ by descending $P(k_i)$ so that the most probable answer is $k_{\pi(1)}$ with probability $P(k_{\pi(1)})$, the second-most probable answer is $k_{\pi(2)}$ with probability $P(k_{\pi(2)}) \leq P(k_{\pi(1)})$, etc., then this minimizes the expected number of guesses because each successive guess covers the maximal fraction of probability mass left unguessed so far.

Specifically, the expected number of guesses is $$\sum_{i=1}^n i\cdot P(k_{\pi(i)}).$$ Any transposition of the weights that puts a higher weight $P(k_{\pi(i)})$ on a larger number $i$ will lead to a higher weighted sum.

Answer 2

This can be a little tricky, and more complicated than suggested in the other answer, in terms of the ordering of keys for guessing, I will give an example with a key with 3 parts: Let $$k=k_1 || k_2||k_3,$$ and note that unknown key determines the random variables $$K,K_1,K_2,K_3,\quad\textrm{with}\quad K=K_1||K_2||K_3.$$

Let the keyspace for $k_i$ for $i=1,2,3$ be $\{z_i(1),z_i(2),\ldots,z_i(n_i)\}$ where we renumber the elements such that $$ Pr[K_i=z_i(s)]\geq Pr[K_i=z_i(s+1)],\quad \forall s=1,\ldots,n_i-1. $$

Assumption: The system does not allow partial testing of keys, the whole key $k$ must be tested (in guess and verify fashion). It is clear that guessing keys in decreasing order of probability is optimal in terms of minimizing the expected number of guesses until the correct key is determined.

Now we need to determine the order in which the key guess should proceed. Since there are $n_i$ values for $k_i$ there are a total of $n=n_1 n_2 n_3$ values for $k.$

We initialize an empty list and now need to loop over the $n$ possible values, say

for $i=1,2,\ldots,n_1$ do for $j=1,2,\ldots,n_2$ do for $l=1,2,\ldots,n_3$ do

Compute $Pr[(k_1||k_2||k_3)=(z_1(i)||z_2(j)||z_3(k))]$ as $Pr(k_1=z_1(i))Pr(k_2=z_2(j))Pr(k_3=z_3(l))$ and insert the index $(i,j,l)$ into a single list so that it is smaller than all the entries before it and larger than all the entries after it.

end for; end for; end for;

This list determines the optimal order of guesses. And the order of the overall guesses need not be monotone in the order of the subkeys sorted in decreasing order of probability. For example we might have $$ Pr[k_1=z_1(1)]=1/2,Pr[k_1=z_1(2)]=1/8,Pr[k_2=z_2(1)]=7/8, Pr[k_2=z_2(2)]=6/8,Pr[k_3=z_3(1)]=7/8, Pr[k_3=z_3(2)]=6/8 $$ so the correct order of guesses is $$ k=z_1(1)||z_2(1)||z_3(1)\quad\textrm{with Probability }\frac12\frac78\frac78=\frac{49}{128}$$ followed by $$ k=z_1(1)||z_2(2)||z_3(1)\quad\textrm{with Probability }\frac12\frac68\frac78=\frac{42}{128}$$ followed by $$ k=z_1(1)||z_2(1)||z_3(2)\quad\textrm{with Probability }\frac12\frac78\frac68=\frac{42}{128}$$ and then followed by $$ k=z_1(2)||z_2(1)||z_3(2)\quad\textrm{with Probability }\frac18\frac78\frac78=\frac{49}{512}$$

This is why the above ordering needs to be computed first.

Edit: Thanks to the comment pointing out the related work in this paper where techniques for ordering of keys in the case of dependent subkeys are considered.