Mixing Cipher Lower Bounds

Question

Let Z be a cipher system consisting of three m-sequence linear feedback shift registers (LFSR) of length 128 bits each which are assumed to be not cryptographically secure and the registers are seeded with IID variables. Lets identify the registers as S for select register, C for the ciphertext register, and D as the decoy register. The enciphering system works as follows:

The output bits of S control the select line of a two input multiplexer with one input being the XOR of the message bits with register C(call these the ciphertext bits as is the usual custom) and the other input being the bits of D, the decoy register.It is assumed that the message bits are held in a buffer until they are selected for output but register C is continually clocked even if it is not selected, so C is constantly losing information ,likewise with register D. So the output of the multiplexer is a pseudorandom mixture of ciphertext bits with decoy bits. In order for the adversary to recover the message he/she must first separate the ciphertext bits from the decoy bits. Of course this is not a very efficient way to encrypt information because by adding decoy bits to the ciphertext bits effectively doubles your information traffic, but let's say we don't care about efficiency. How could an adversary separate the ciphertext bits from the decoy bits in polynomial time, neither bitstream gives any information about the other and nothing about the select bits S.

Answer 1

The design you described is very close to Geffe generator - it consists of three LFSRs L1, L2, L3 and the output bit is either the output of L2 or L3 depending on the value of the output bit of L1. Essentially, the output filter function is $F(x1, x2, x3) = (x1\wedge x2) \vee (\neg x1 \wedge x3)$.

A classical way of attacking Geffe generator is the correlation attack - Google search for "Geffe generator attack" yields a number of relevant results. It looks like this type of attack would be also applicable to your case. Another potential attack avenue would be algebraic attacks - output bits are quadratic function of the variables of the internal state, so it might be possible to do linearization attack if you observe enough bits of the output or you have additional data about the content of the registers (e.g. you know decoy bits).

In cryptanalysis, the devil is really in the details, so without posting a full description of the algorithm and a reference implementation, it's difficult to say much more than I already wrote above. This should be a good starting point though.

One more remark regarding attack complexities - while I don't think there is a polynomial time attack on a generator you describe, what we care in practice is concrete (not asymptotic) complexity of the attack. If one can show an attack that has smaller complexity than the best generic attack, it is considered a break of the algorithm.