# Mixing Cipher Lower Bounds

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.

• What is this adversary assumed to know? E.g. cipher-text only? Known plain text? Are they assumed to know the tap bits (but not the initial state)? The question is under-specified. In any event, the L in LFSR tends to break any such scheme in the end, which isn't to say that a break is trivial. Jun 17, 2019 at 12:14
• @JohnColeman: The adversary knows all the taps and structure of all three LFSR's, except the initial key which I have already stated are assumed to be iid variables. The adversary has to sort the ciphertext bits from the decoy bits in order to recover the ciphertext,, so this sorting algorithm would be a lower bound for recovering the message. Jun 17, 2019 at 17:03
• It might be beneficial to give a description of the scheme in mathematical notation rather than english prose. You can use mathjax/latex to format your posts. Jun 25, 2019 at 17:47
• @EllaRose: If I had any idea on how to use Latex , I would already be using it. I'm assuming everyone here can understand English and is familiar with the basics of stream ciphers, if anyone doesn't understand any or all parts of the question I would be happy to answer all comers. Jun 26, 2019 at 13:59
• @EllaRose: Are you going to take a shot at answering this ? :-) Jun 26, 2019 at 16:48

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.

• Sorry, but my cipher has nothing in common with the Geffe generator. My cipher is not a "generator", I think you missed the whole concept of my construction, but thanks for writing something , I was getting "lonely" having no responses to my question :-( Jul 1, 2019 at 15:56
• @WilliamHird $x1 = S$, $x2 = P \oplus C$, $x3 = D$. Jul 2, 2019 at 8:43
• @A.Hersean; L is for the way you look at me, O is for the only one I see, V is very extraordinary, …… Does your meaningless comment at least have a catchy melody to go with it ? LOL Jul 2, 2019 at 10:04
• @WilliamHird This means that you did not understand what a Geffe generator is, but you still commented that your proposal has nothing to do with it? Then you continue on with a passive-aggressive comment? This behavior will not get you far into getting answers to your questions. If you were honest with what you understand, people here would be happy to help you understand more. Jul 2, 2019 at 11:56
• Again, I have no idea what you are talking about, I know exactly how the Geffe Generator works and how it was broken by Seigenthaler, I read the paper. If you want to step up and answer my question with a real answer, please do so. Jul 2, 2019 at 12:44