What does that mean, that A5/1 is clocked?

Question

What does that mean, that A5/1 is clocked? What happens if the clocking bit agrees with the majority bit?

kelalaka · Accepted Answer · 2021-05-19T22:08:14.990

5

The clock term comes from electronic engineering; in each clock, the cells of LFSRs ( flip-flops) are clocked and the data moves. In the shift registers, the data moves from one to another in one direction. As we can see from the below, each flip-flop has a clock input where each has the same clock.

In the LFSRs ( Linear Feedback Shift Register) there is also the feedback that is calculated from the selected tap point is fed the beginning.

Normally LFSR's are clocked for each clock so that new feedback is calculated and the LFSR is shifted so that new output is formed. If you don't clock, then no new feedback is calculated and no shifting occurs, too. The old output is still active. To achieve this in electronics the clock is also controlled by logic. In programing that is way easier (see bottom).

Consider the first LFSR ( index names are free to choose and it is reflected)

When clocked it will become;

See that the data of the cells are shifted to the right and the new value to the left is feedback values calculated from the active taps.

A5/1, which is terribly broken, has three LFSR where each of them has clocking bits, (8,10,10) shown orange on Wikipedia's image. At each clock, the majority is formed from those values.

The majority of the $n$ binary variable means the most occurring value. For three bits, just count the number of ones $c$ if $c > 1$ then the majority is *one ( i.e. number of ones > number of zeros) and the majority bit is $1$, otherwise the majority bit is $0$.

If the majority bit matches the LFSR's clocking bit, then the LFSR is clocked otherwise not clocked.

A simple code can be described for each LFSR as

majority = (L1[8] AND L2[10]) xor (L1[8] AND L3[10]) XOR (L2[10] AND L3[10])
def clockLFSR1(majority):
    if L[8] == majority:
        self.applyClock()
def clockLFSR2(majority):
    if L[10] == majority:
        self.applyClock()
def clockLFSR3(majority):
    if L[10] == majority:
        self.applyClock()

edited May 19 '21 at 22:08

answered May 14 '21 at 22:26

kelalaka

48,443
11
116
196

I think the term "clocked" comes from electronic engineering, since LFSRs tend to be designed to be implemented as physical circuits. You may want to point that out. – forest May 14 '21 at 22:49
@forest yes, it comes from that, I'll thanks. – kelalaka May 14 '21 at 22:49
That has put your recent LFSR-picture-generating tool to the acid test. A conclusion is that for practical parameters, the text is a bit small to be readable. – fgrieu May 15 '21 at 12:23
@fgrieu yes, the font size was an issue, Tikz/Latex, I think this is the solution \scaleto{x_0}{20pt}. I'm on it. I'm also considering animation, too. – kelalaka May 15 '21 at 12:25
@fgrieu I've handled it, the next is the feedback than animation... – kelalaka May 15 '21 at 14:29
I understand first example with white blocks. Clock is just one step in LFSR. "LFSR where each of them has clocking bits" - why do we need any cloking bits if in example above it cloks anyway, step by step? "If the majority bit matches the LFSR's clocking bit" - what is majority bit, where it is and with what it has to match? "otherwise not clocked" - still I don't know what it means. If we not clock LFSR it won't do anything, cipher stops. It could be clocking constantly, until we stop it. – Tom May 19 '21 at 07:33
@Tom clock is the part of modern electronics to control the circuit. You may consider it just advancing the LFSR one step. Regular stepped animation is here. Regular clocked LFSR's are insecure so people found new ideas. This is one of them. The majority bit is the majority of the 3 bits. It can be calculated as the first line of the sample code. – kelalaka May 19 '21 at 08:32
Still I have no idea how to check "if L[8] == majority". Let's say L[8] = 1. Then the condition is met or not? – Tom May 19 '21 at 15:59
Finally, after watching this: https://www.youtube.com/watch?v=LgZAI3DdUA4, I think I understand it. If we got 001, then the last LFSR is not clocked, if we got 110, again, then last LFSR is not clocked. If we got 101, then middle one is not clocked, with 010 again middle one is not clocked. And so on. Kind of tricky to explain wihout example. – Tom May 19 '21 at 16:08
The majority of $n$ binary variable means the most occurring value. Nothing special. – kelalaka May 19 '21 at 17:10

What does that mean, that A5/1 is clocked?

1 Answers1