Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

In Encryption Schemes for Computer Confidentiality, Pless describes how to use the J-K flip flop as a nonlinear combiner for linear feedback shift registers. This generator was broken because the J-K flip flops are not correlation immune but my question concerns the basic nonlinearity of the J-K function itself: how do you measure its nonlinearity? For instance we know that Boolean functions with maximum nonlinearity are the bent functions, which have the farthest distance to all affine functions. Then we have the linear functions like XOR, so where would the J-K flip flop fit into this spectrum?

share|improve this question

1 Answer 1

up vote 2 down vote accepted
+100

There's no way to reduce the J-K flip-flop to a boolean function, much less a 2-input boolean function. The J-K flip-flop is a 3-input block with a clock input in addition to inputs $J$ and $K$. Its output(s) is/are not a boolean function of these inputs, because past output(s) matters to future output(s).

If we want to model a J-K flip-flop using boolean functions, we can do this in several ways, including two identical 3-input functions $Q(I,B,C)=(I\cdot B\cdot C)|\bar B$, where $I$ is $J$ for one function and $K$ for the other, $B$ is the output of the other function, and $C$ is the clock, as per this schematic:

J-K flip-flop

Knowing the initial state $Q$, and the inputs $J$, $K$, $C$, this allows predicting future $Q$, except for some inputs where $C$ changes near-simultaneously with either $J$ or $K$.


The article considers a J-K flip-flop with single output, sharing its clock input (made implicit) with the sources feeding its other two explicit inputs $J$ and $K$. The model given is:

The state (noted $R_n$ in the article) of the output $Q$ of the J-K flip-flop at a certain clock period $n$ is $$R_{n+1}=((J\oplus \bar K)\cdot R_n)\oplus J$$ (as can be deduced from any proper model of the J-K flip-flop, including the above model as two boolean functions). And thus, in a modern exposition, anything using the J-K flip-flop in this clock configuration can be readily expressed in the framework of Non-Linear Feedback Shift Registers.


In the shared clock configuration of the article, the J-K flip-flop's feedback function given above is a 3-input, 1-output boolean function $F(J,K,R)=((J\oplus \bar K)\cdot R)\oplus J$, where the additional input $R$ is the previous output. The truth table for $F$ can be condensed from the normal $2^3$ entries to $$\begin{align*} J&K&F\\ 0&0&R&\text{ unchanged}\\ 0&1&0&\text{ clear}\\ 1&0&1&\text{ set}\\ 1&1&\bar R&\text{ toggle}\\ \end{align*}$$

This function $F$ is balanced (that is, half of the $2^3$ outputs are 1), and $F(J,K,R)\oplus R$ is also balanced. $F$ is non-linear w.r.t. each of its inputs (that is, the XOR of the output with any input is not a function of the other inputs).

$F$ is not correlation-immune: the output is biased towards $J$, and towards $\bar K$. This indeed allows an attack in the context of combining LFSRs, but replacing $F$ with any 3-input boolean function can't improve this; enumerating the 256 such functions, we would find some issue with the output (ordered from worst to least):

  • severely biased (that's why we want $F$ balanced);
  • severely correlated to the previous output (that's why we want $F(J,K,R)\oplus R$ balanced);
  • equal within polarity and a clock delay to one of the two inputs, which (being a LFSR) is efficiently predictable using the Berlekampf-Massey algorithm;
  • equal within polarity and a clock delay to the XOR of the two inputs, which is efficiently predictable by the same method, because the XOR of the outputs of any two LFSRs is identical to the output of another LFSR of size at most equal to the sum of the sizes of the two LFSRs;
  • just as correlated with the inputs as in the J-K flipflop case.

Note: I'm not familiar with the definition of bent and semi-bent functions, and won't attempt to classify where $F$ belongs, but that should be trivial from the definition of bent and semi-bent, whatever that is.

Note: The J-K flip-flop seems to be one of the simplest two-inputs combiner with memory worth consideration in the framework studied by Frederik Armknecht and Matthias Krause in Algebraic Attacks on Combiners with Memory (Crypto 2003).

share|improve this answer
    
OK < thanks for the info, this is interesting. According to some papers I've read bent functions have to have an even number of variables, so according to your analysis, the flip flop can't have the same nonlinearity as the bent functions. I will wait for more answers here, hopefully someone will enlighten us. –  William Hird Apr 25 at 8:36
    
So let me ask this question: if the J-K flip flop was correlation-immune, it could be considered a strong cryptographic combining function? –  William Hird Apr 25 at 15:16
    
@WilliamHird, I think you might have a misconception. It sounds like you want to design a secure stream cipher, and your approach is to try to find a function that in isolation has some combinatorial properties. This has two problems: (1) to design a secure stream cipher, you need to look holistically at the entire design; you can't just pick out one component/function used in the stream cipher and say that "since it has properties X,Y,Z, the cipher is secure"; (2) designing secure ciphers is very hard, and you're unlikely to do better than existing state-of-the-art schemes. –  D.W. Apr 25 at 20:16
2  
@DW , Yes I am aware of how hard it is, but I like the challenge. But now that I am retired, its either design something new or watch "Gilligan's Island" re-runs. Oh, and by the way, if I were you, I wouldn't bet against me ;-) –  William Hird Apr 26 at 1:01
    
@grieu, Nice work, answer accepted. You are the "hardest working man in cryptography ! –  William Hird Apr 26 at 1:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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