2
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Key of what? AES? SHA-2 MAC? RSA? What do you mean "the attack works against these partial keys"? What attack? It's really not obvious (to me at least) what attack would allow a divide-and-conquer approach to splitting up the keys like this. Basically, can you please define your scenario a lot more carefully before launching into your question? $\endgroup$ – Mike Ounsworth Sep 25 '17 at 17:43
  • $\begingroup$ Though this is not relevant to the theoretical question in itself, this is a side-channel attack to an AES cipher, attacking every byte individually. I believe the framework I provided is complete. In any case, there are several types of classical cryptanalytic attacks where you may be able to recover only parts of the key (due to weaknesses in an Sbox, for example). I imagine this problem is also similar to when you have a password that follows some known pattern with a certain number of parts, and you have some knowledge of what the parts may be. In all these cases, what is the optimal way? $\endgroup$ – Ricardo M. Sep 25 '17 at 17:47
  • $\begingroup$ Plus, I already solved the divide-and-conquer problem (I have experimental results for partial keys ^^). Thus though it may not be obvious to you, I assure you it is definitely possible, and that's why my question takes this as a given. Hopefully someone could help me with the key reassembly, however, even if just by directing me to a relevant source. $\endgroup$ – Ricardo M. Sep 25 '17 at 17:55
  • 1
    $\begingroup$ Interesting problem. I'm not sure this site is the best for it, however. Math or maybe even CS could be better. Especially since the crux of the question is about proving optimality of some strategy to accomplish some objective. This same problem could be cast into a non-cryptographic version, and the core of the problem would remain the same. $\endgroup$ – mikeazo Sep 25 '17 at 19:52
  • $\begingroup$ Do you have any memory constraints? It would seem that for each choice of each position, multiplying probabilities would give you a way to rank each possible complete key. $\endgroup$ – mikeazo Sep 25 '17 at 20:12
0
$\begingroup$

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.

$\endgroup$

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.