0
$\begingroup$

Suppose Alice and Bob share two $n$-bit shared keys, $k_1$ and $k_2$, and decide to send multiple $n$-bit messages to each other. The encryption scheme they use simply sends $c_i = (k_1 + i k_2) \oplus m_i$, where $m_i$ is the $i$th plaintext. Here, the addition and multiplication are both done modulo $2^n$.

Clearly, they can send at least two $n$-bit messages with perfect secrecy, since $k_1 + k_2$ and $k_1 + 2 k_2$ will be independent and have equal probability being each possible $n$-length bitstring. Once they send three, though, we can start learning some information about the plaintexts. For example, $k_1 + k_2$ and $k_1 + 3 k_2$ will always have the last bit, so $c_1$ and $c_3$ will share the same last bit if and only if $m_1$ and $m_3$ did. Still, though, even in this case we still wouldn't know what the last bit of the messages was.

My question is, at what point does it become feasible to figure out the entire message (i.e. how many messages do Alice and Bob need to send before an adversary with relative ease can figure out large portions of the message)? And at this point, what is an algorithm that would recover the plaintexts? We can assume that the messages are patterned, e.g. in the English language, so if we can reduce this problem to one where crib-dragging/frequency analysis/etc. can be applied, that would work!

Improve this question
$\endgroup$
5
  • $\begingroup$ The answer depends tremendously on what we assumes is known about the $m_i$. For example, if we assume two consecutive $m_i$ (and their location) are known, we trivially get $k_1$ and $k_2$. $\endgroup$
    – fgrieu ♦
    Mar 1, 2021 at 4:08
  • $\begingroup$ I see. I’m interested in the general case where the $m_i$ could be anything, really. The only assumption I’m willing to make is that it is in a language that has noticeable patterns in syntax, etc. (like English) Is it not feasible to crack without further assumptions? $\endgroup$
    – paulinho
    Mar 1, 2021 at 5:31
  • $\begingroup$ Another thing I am noticing here is that when $i$ is a power of two like $i = 2^m$, the lower $m$ bits of $k_1 + i k_2$ will always be the lower $m$ bits of $k_1$. We can find known message with known repeated bits which can also be applied in case. $\endgroup$
    – Manish Adhikari
    Mar 1, 2021 at 10:18
  • $\begingroup$ This can be easily extended into any form of the form $i=2^m*r$ with odd r. This reveals quite a lot $\endgroup$
    – Manish Adhikari
    Mar 1, 2021 at 10:20
  • $\begingroup$ @ManishAdhikari Yes, good observation. But we would need quite a few messages to be sent. Even to be able to remove the XOR mask on the last byte would require $256$ messages to be sent. Even after that, just knowing what two messages XOR'ed with each other are for the last byte is not sufficient to do any sort of crib dragging unfortunately :( $\endgroup$
    – paulinho
    Mar 1, 2021 at 21:49

2 Answers 2

Reset to default
1
$\begingroup$

For a frequency-style solution, we can guess the least significant bytes of $k_1, k_2$, decrypt the least significant byte of each block, and check the frequency (e.g. space should be the most often). Then repeat with the previous byte, etc.

The scheme is bad in that it reduces to schemes mod $2^N$ for any $N < n$.

Improve this answer
$\endgroup$
0
$\begingroup$

I would suggest to try an SMT-solver (e.g. z3) on a few blocks, with constraint on messages like the most significant bit of each byte equal to 1 (printable). The carry propagation should constraint the keys. For modeling, $i$ is known, so addition of $ik_2$ reduces to addition of several shifts of $k_2$.

Improve this answer
$\endgroup$

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.