Home > Mobile >  In Briceno et al.'s A5/2 implementation, they delay a LSFR cycle without running a clock cycle
In Briceno et al.'s A5/2 implementation, they delay a LSFR cycle without running a clock cycle

Time:12-05

Here is a piece of code taken from the seminal "A Pedagogical Implementation of the GSM A5/1 and A5/2 "Voice Privacy" Encryption Algorithms" by Marc Briceno, Ian Goldberg, and David Wagner:

typedef unsigned char byte;
typedef unsigned long word;
typedef word bit;
...
word R1, R2, R3;
#ifdef A5_2
word R4;
#endif /* A5_2 */
...
/* Generate an output bit from the current state.
 * You grab a bit from each register via the output generation taps;
 * then you XOR the resulting three bits.  For A5/2, in addition to
 * the top bit of each of R1,R2,R3, also XOR in a majority function
 * of three particular bits of the register (one of them complemented)
 * to make it non-linear.  Also, for A5/2, delay the output by one
 * clock cycle for some reason. */
bit getbit() {
        bit topbits = (((R1 >> 18) ^ (R2 >> 21) ^ (R3 >> 22)) & 0x01);
#ifndef A5_2
        return topbits;
#else /* A5_2 */
        static bit delaybit = 0;
        bit nowbit = delaybit;
        delaybit = (
            topbits
            ^ majority(R1&0x8000, (~R1)&0x4000, R1&0x1000)
            ^ majority((~R2)&0x10000, R2&0x2000, R2&0x200)
            ^ majority(R3&0x40000, R3&0x10000, (~R3)&0x2000)
            );
        return nowbit;
#endif /* A5_2 */
}

I have been poking around this implementation for a few days now, and I understand what's going on in terms of where the data goes and where it came from (and what purpose it serves in the algorithm).

The only thing I'm not understanding is /*Also, for A5/2, delay the output by one clock cycle for some reason. */.

I don't see how

static bit delaybit = 0;
bit nowbit = delaybit;
delaybit = (...);
return nowbit;

gives a "delayed" output.

ie. how is delaybit delayed at all? Why did we generate delaybit at all if we are returning nowbit Elsewhere in the code, the notion of delay makes sense as the registers (R1, R2, and R3) are clocked with dedicated clocking functions. I don't see the purpose of nowbit and delayedbit as two separate entities in this function.

Wouldn't we just need one variable? By mixing it in one clock cycle late, we would be performing a delay.

Is there an issue with my understanding? Or perhaps with the code? This is a widely disseminated file, so I would expect to find a public record of such issues with the code if there were any.

CodePudding user response:

The "trick" is here:

static bit delaybit = 0;

A static variable keeps its value between calls. First time it is set to 0, and that value is returned. Then the next value is calculated, to be returned by a future call.

A bit too cute, in my opinion.

  • Related