Is there an algorithm that gives a reasonable chance of decoding the entire ciphertext of this encryption scheme?

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!

• 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$.
– fgrieu
Mar 1 at 4:08
• 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? Mar 1 at 5:31
• 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. Mar 1 at 10:18
• This can be easily extended into any form of the form $i=2^m*r$ with odd r. This reveals quite a lot Mar 1 at 10:20
• @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 :( Mar 1 at 21:49

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$$.
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$$.