Cryptanalysis of the GOC

Question

The GOC (Générateur d'Octets Chiffrants, Ciphering Byte Generator) is a PseudoRandom Generator that was used during the late 20^th century for content encryption in pre-internet Videotex terminals, mostly in France. One application was encrypting sensitive data (e.g. banking details) while in transit to a Minitel.

The GOC has a 64-bit secret seed/key, a 109-bit state, and at each step produces a "ciphering byte" with 5 pseudorandom bits in the low-order bits (we disregard 2 bits at zero, and a parity bit equal to the XOR of the others).

The GOC is detailed in patent FR2519828 (1982, in French), equivalently US4543559 (long expired). It's in the LeCAM (Lecteur de Carte à Mémoire) Minitel add-on (1987, in French only). In that context the key is computed by a Smart Card, making it essentially random and secret (no related-key attack is possible) w.r.t. an attacker; and the output is used as the keystream of a stream cipher, typically making a large fraction of the GOC output known (e.g. the first 40 outputs).

How would cryptanalysis recover the state (or better the key) in the above context?

Note: I would not ask this if the system was still in use.

---

The state of the GOC is divided into 3 registers $R$ (7×5 bits), $S$ (7×7 bits), $T$ (5×5 bits). In a step of the GOC, each of $R$, $S$ and $T$ evolves independently. It's right-shifted by $k=5$, $7$ or $5$ bits respectively, and $k$ bits enter on the left, computed from the $k$ former right bits and a $k$-bit fixed segment of the same register by a simple function using addition and a modified† modular reduction modulo $2^k-1$. The 5 bit output is formed by a bitwise operation involving 5x5 bits of the state.

Initialization zeroes the states, then for each key byte: it is XORed $k$ of it's bits into a fixed $k$-bit location of each state register and the GOC is stepped as above (with the output ignored).

Further details are in this reference implementation in C. There's an example with three test cases. The first can be found in the patents. Try It Online!

#include <stdint.h>

// state, 109 useful bits 
typedef struct tGOCstate {
    uint64_t R;     // 7*5 bits in the lower 35 bits 
    uint64_t S;     // 7*7 bits in the lower 49 bits 
    uint64_t T;     // 5*5 bits in the lower 25 bits 
    } tGOCstate;
    
// a step, outputs 5 bits
uint8_t GOCstep( tGOCstate *p ) {
    uint64_t a;
  // update R
    a = ((0x1F & p->R) << 1) + (0x1F & (p->R >> 15));
    // next line is equivalent to :  while (a > 31) a -= 31;
    a -= 0x3E & -(a>>6); a -= 0x1F & -(a>>5); a -= 0x1F & -(a>>5);
    p->R = (a << 30) | (p->R>>5);
  // update S
    a = ((0x7F & p->S) << 1) + (0x7F & (p->S >> 7));
    // next line is equivalent to :  while (a > 127) a -= 127;
    a -= 0xFE & -(a>>8); a -= 0x7F & -(a>>7); a -= 0x7F & -(a>>7);
    p->S = (a << 42) | (p->S >> 7);
  // update T
    a = (0x1F & p->T) + (0x1F & (p->T >> 10));
    // next line is equivalent to :  while (a > 31) a -= 31;
    a -= 0x1F & -(a>>5);
    p->T = (a << 20) | (p->T >> 5);
  // produce 5-bit output
    a = p->S >> 35;
    return (uint8_t)(0x1F & (
        (((p->R >> 25) ^ (p->R >> 5)) & ~a) | (((p->T >> 15) ^ p->T) & a)
        ));
}

// GOC key setup
void GOCsetup( tGOCstate* p, const uint8_t iKey[8] ) {
    int j;
    p->R = p->S = p->T = 0;
    for( j=0; j<8; ++j ) {
        uint64_t k = iKey[j];
        p->R ^= (0x1F & k) << 20;
        p->S ^= ((0x0F & k) << 17 ) | (( 0xE0 & k ) << 9 );
        p->T ^= (0xF8 & k) << 12;
        (void) GOCstep( p );
    }
}

#include <stdio.h> // for printf
int main(void) {
    int i,j;
    tGOCstate s;
    const uint8_t cKey[][8] = {
        { 0x15, 0x1F, 0x11, 0xCD, 0x16, 0x58, 0x91, 0xD0 }, // 1982 patent
        { 0x12, 0x34, 0x56, 0x78, 0x90, 0xAB, 0xCD, 0xEF }, // 1988 test vector
        { 0xF4, 0x23, 0x0F, 0x5F, 0xED, 0xBB, 0xB6, 0xDD }, // origin unknown
    };
    for(i=0; i<sizeof(cKey)/sizeof(*cKey); ++i) {
        GOCsetup( &s, cKey[i] );
        for (j=0; j<26; ++j)
            printf(" %02X", GOCstep( &s ) );
        printf("\n");
    }
}
// First 26 output bytes for each of the 3 test keys are
// 13 16 1A 02 1D 12 17 1D 0B 07 1D 18 15 19 1E 11 04 15 02 05 0C 12 1E 02 01 14
// 14 1C 10 18 1C 01 0D 1B 07 1D 13 0B 19 1C 05 02 12 11 0A 16 07 05 1E 18 03 18
// 04 18 12 1F 0E 09 18 15 10 09 16 13 15 07 0B 05 1D 11 08 11 07 15 07 1A 1A 04

Note: in the patent (starting column 6 line 44) and some original implementations, registers $R$, $S$ and $T$ are implemented as $7$, $7$ and $5$ partially used bytes. The patent's RG, SG and TE are the low-order $5$, $7$ and $5$ bits of my wide registers.

---

† The modified modular reduction modulo $2^k-1$ has output in $[1,2^k-1]$, turning $a$ into $(a-1\bmod(2^k-1))+1$, except that $a=0$ is left unchanged. For most keys, the later exception does not occur after key setup. The code shows an implementation technique that's free from secret-dependent timing dependency.

Answer 1

Looking through this, it would appear that key recovery with circa $O(2^{37})$ effort is possible (and state recovery with somewhat less effort). This is unlikely to be the most efficient approach, however here is what I have:

First step, we recover the initial state of the $T$ shift register. This is easy: the about agrees with (T >> 15) ^ p-T) 75% of the time (as it always agrees if the correspond bit in a is set, and half the time if it is cleared); hence, we can just go through all $2^{25}$ initial states, and see which one agrees most often with the output we've seen.

Second step, we recover the initial state of the $R$ shift register. This is a bit more complex computationally, however it ought to be well within out budget. We know a bit of (R >> 25) ^ (R >> 5) 25% of the time (if the known output bit disagrees with the known $T$ output, we know that bit must have come from the $R$ register. We can go through all $2^{35}$ initial states of $R$, and reject any that predicts an output contrary to what we know.

Third step, we recover the initial state of the $S$ shift register. To start with, we note that we know half the bits of the 5 bit value S >> 35 (if the $T$ and $R$ outputs are different, we know which one S >> 35 selected). Hence, we can go through the first 6 outputs (which would give us 15 or so bits of the $S$ shift register at that state - note that it doesn't xor in anything into those places). Then, we can search over the remaining 34 or so bits and see which ones predict the known outputs in the future. And, the $S$ update function is reversible; we can easily step it backwards to recover the initial state.

That gives us full state recovery with circa $O(2^{36})$ effort.

Now, to convert that into key recovery, I note that:

• The initial state of the $R$ register depends on only 40 bits of the key (the 5 lsbits of each key byte)

• The initial state of the $T$ register depends on only 40 bits of the key (the 5 msbits of each key byte)

So, scan through all $2^{35}$ possible 5 lsbit key values for the key schedule of $R$ for the first 7 key bytes (and note that the last key byte affects only 5 bits of $R$, hence we can quickly reject values of the first 7 bytes that don't work), and list which keys give us the observed $R$ initial state (and the list is expected to have around $2^5$ elements).

Scan through all $2^{35}$ possible 5 msbit key values for the key schedule of $T$ for the first 7 byyte bytes (and note that the last key byte affects only 5 bits of $T$, hence we can quickly reject values of the first 7 bytes that don't work), and list which keys give us the observed $T$ initial state (and the list is expected to have around $2^{15}$ elements).

For those pairs of keys that are compatible (that is, they have common values for the 2 middle bits of each key byte), combine them and run them through the $S$ key setup, and see if it gives us the observed $S$ initial state.