5
$\begingroup$

The GOC (Générateur d'Octets Chiffrants, Ciphering Byte Generator) is a PseudoRandom Generator that was used during the late 20th 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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ I agree. For key recovery, there's the slight complication that often we can't directly recognize if the $5$, $7$ or $5$ bits entering $R$, $S$ or $T$ during key setup are all zero or all one. Now the meta question: was such weakness intentional? Strong crypto was forbidden in France at the time. $\endgroup$
    – fgrieu
    Sep 4, 2023 at 19:23
  • 1
    $\begingroup$ @fgrieu: was it intentional? Well, I'm not sure - there are aspects that make the search easier, and I have to wonder "why would someone do that?" On the other hand, I've gone through a number of amateur ciphers with far worse weaknesses. Also, wasn't a "64 bit key" a sufficient weakness for the time? $\endgroup$
    – poncho
    Sep 4, 2023 at 19:36
  • $\begingroup$ The time was like 1980-1982. Simple DES was then considered enough for many civilian applications. And there was a law prescribing that authorities can snoop telecom, and (at least a few years later, duno exactly when it was enacted) a regulation telling that for this purpose, civilian crypto must allow decryption with a "test d'arrêt simple" (simple stop test) in at most 2^40 steps. A 40-bit key matched that. I know (for having been coerced to do so) that a backdoor leaking the symmetric key (RSA-encrypted to a key pair given to authorities) was go. Perhaps weak crypto was too. $\endgroup$
    – fgrieu
    Sep 5, 2023 at 11:48
  • $\begingroup$ Chief among "aspects that make the search easier" is constructing output in a way allowing to confirm a guess of T. (((p->T >> 15) ^ (p->R >> 5)) & ~a) | (((p->R >> 25) ^ p->T) & a) would I guess make things considerably more difficult, with no impact whatsoever on performance. I'd be surprised that Louis Guillou (of GC identification scheme and How to Explain Zero-Knowledge Protocols to Your Children fame), one of the stated inventors, would not realize that. I tried to probe him on that circa 2011, but failed. $\endgroup$
    – fgrieu
    Sep 5, 2023 at 12:01
  • $\begingroup$ @fgrieu: this attack would require a moderate amount of known keystream (200-300 bits would be my guess, and the known bits needn't be contiguous). Do you know if, in the scenario that the cipher was originally intended for, that an evesdropper would have that amount of known plaintext available to him? If someone deliberately inserted such a weakness, they would want to make sure that it could be practically used... $\endgroup$
    – poncho
    Sep 5, 2023 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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