2
$\begingroup$

An adversary $A$, eavesdrops $n$ cipher-texts, $c_{1}, c_{2} ..., c{_n}$. It also knows a value $v$ and a function $f$ such that $$f(k_{1}, k_{2}, ..., k_{n}) = v$$ where, $k_{i}$ is used to encrypt $m_{i}$ to obtain $c_{i}$, $\forall i| 1\leqslant i\leqslant n $.

As a concrete example say, $A$ listens to three cipher texts, $c_{1}, c_{2} \text{ and } c_{3}$, and knows that $k_{1} \oplus\ k_{2} \oplus\ k_{3} = 1^l $, where cipher $c$, message $m$ and key $k$ are of the same bit length $l$.

In the concrete case, how could $A$ use this information in guessing $m_{1}, m_{2} \text{ and } m_{3}$ ? In the general case, are there any well known methods that I should be aware of? Where can I learn about such general techniques in detail?

Assume, messages are drawn uniformly at random (frequency analysis is not possible).

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ For your concrete example, if $n=2$ it is usual crib-draging 1 and crib-draging 2. The attack works since x-or function cancels the keys. In your concrete case it will only complement. Crib-dragging can be generalized, it will be much harder (?) to solve. $\endgroup$
    – kelalaka
    Dec 11, 2018 at 18:23

1 Answer 1

Reset to default
2
$\begingroup$

Let's first look at the concrete case;

We already know that when a key is used more than once, one-time pad becomes insecure with this two questions and nice answers on crib-dragging.

But, in your case the keys are not the same, only a relation is given by

$$k_1 \oplus \ldots \oplus k_n = 1^l $$ (message length $n$ and number of keys confuse here let $l$ be the message length)

  • now, let $n=2$ messages $m_1$ and $m_2$ than $k_1 \oplus k_2 \oplus 1^l $

    If we x-or the two ciphertexts $c_1$ and $c_2$ of $m_1$ and $m_2$, respetively; $$ c_1 \oplus c_2 = m_1 \oplus k_1 \oplus m_2 \oplus k_2 = m_1 \oplus m_2 \oplus 1^l$$ then;

    $$c_1 \oplus c_2 \oplus 1^l = m_1 \oplus m_2 $$ So the solution for this is nothing but the usual two-time pad.

  • now let we $n=3$ messages $m_1, m_2$ and $m_3$ than $k_1 \oplus k_2 \oplus k_3 \oplus 1^l $. than we will have $$c_1 \oplus c_2 \oplus c_3 \oplus 1^l = m_1 \oplus m_2 \oplus m_3$$

    This can be also attacked but will be harder, since we have to guess two words and see that it reveals from the third message. The expected time is the square of the $n=2$ case for the initial guesses.

  • When $n$ becomes bigger it will require more guess and trials.

Arbitrary $f$

Here, let's look only the case $n=2$, and only ideas;

We have $c_1 = m_1 \oplus k_1$, $c_2 = m_2 \oplus k_2$, and $f(k_1, k_2) = v$

We can't apply crib-dragging here since

$$ c_1 \oplus c_2 = (m_1 \oplus m_2) \oplus (k_1 \oplus k_2)$$ guessing $m_1$ will not give any information. An attack can be performed by guessing two words and verifying that $k_1$ and $k_2$ satisfies two relations;

$$k_1 \oplus k_2 = m_1 \oplus m_2 \text{ and } f(k_1, k_2) = v$$

Improve this answer
$\endgroup$
2
  • $\begingroup$ thank you for your time and efforts. I assume all secret encryption schemes are studied under the assumption that the keys remains secret and such occurrences are rare. I don't find anything in the literature explaining such adversaries. I don't think this is a legit use case either. But, for the concrete case, from the idea you have sketched, I'm concluding that, given a tuple ($m1, m2\ and\ m3$), $A$ has a non negligible advantage (more than a mere $1 \over 2$). $A$ gains this non negligible advantage in the general case too. Is my understanding correct ? $\endgroup$
    – rranjik
    Dec 12, 2018 at 3:40
  • 1
    $\begingroup$ If the keys are generated uniformly random, then such $f$ almost impossible. For the advantage of $\mathcal{A}$, calculating the exact advantage is not an easy task. It should be, however, clear that is must be non-negligible. $\endgroup$
    – kelalaka
    Dec 12, 2018 at 15:12

Your Answer

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

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