~stef/blog/

A few days after sharing this solution with the fine cryptomuseum people, I got a hint. The taps for the LSFRs are much less complicated than thought, and they're hiding in plain sight. Remember this line from the loop updating the 16 byte LFSR block (page 62, first code example, line 5):

acc ^= lfsr[i] & lookupTable[(round_counter+i)%16];

Well this lookupTable is the taps of the four LFSRs, only the taps are bit-sliced just like the LFSRs themselves. The only magic was that the round_counter starts from 0x1f, thus the 15th byte was the first to process for extracting the taps. The following function from the lfsr32.py script takes care of extracting the nth LFSR taps:

taps = (
   0x06, 0x0B, 0x0A, 0x78, 0x0C, 0xE0, 0x29, 0x7B,
   0xCF, 0xC3, 0x4B, 0x2B, 0xCC, 0x82, 0x60, 0x80)

def extract(taps, i):
    # left to right
    tr = [''.join(str((taps[j] >> b) & 1) for j in range(16)) for b in range(8)]
    # horizontal bottoms-up lines appended
    return (tr[(i*2)+1]+tr[(i*2)])

for i in range(4):
  print(extract(taps, i))

Running the above code, results in these left-zero-padded results:

32 bit: 11100001111101000100001111110000  e1f443f0
31 bit: 01111011101110001000100010001000  7bb88888
29 bit: 00010111000100100001000100000000  17121100
27 bit: 00000100110011010001010111101010  04cd15ea

Each of these tap configurations create LFSRs that are of maximum cycle size. Implementations of these are included in the lfsr.c file.

I do not know if the NSA did have a SAT solver like z3 back in 1983, but the fact that I can recover a key 40 years later within 4 seconds on a laptop CPU in a single thread - while I am far from being able to do so for the same if DES would be used -, lets me conclude that the PX1000cr algorithm is indeed a confirmed backdoor.

As noted above though, the equation system that needs to be solved is quite huge (about 20 something megabytes when printed out as ASCII text), it is safe to assume that the NSA needed much more efficient ways in the 80ies to break this algorithm.

A very simple and cheap attack which also amortizes the costs of the algebraic attack is based on the fact that the first and last character and the top bits in between leak the keystream. This makes it almost trivial to detect key reuse. And this being a stream cipher key reuse is catastrophic in cryptographic sense, a good example of this is the Venona project and Julius and Ethel Rosenberg's fate. We can say that the NSA has for decades worked on recovering plaintext from two-timepads, but in the Venona this was more difficult as they didn't know which two messages were sharing the same key. With the PX1k this is much more trivial. For Venona it's a solid bet that the NSA built a lot of HW that recovers plaintext from two plaintexts xor-ed together. This means they only need to use the more expensive algebraic or other attacks for cryptograms with unique keys. I believe this is an important insight, there's not just one backdoor here, but multiple ones that work together.

Also notable is that this backdoor is definitely predating the NOBUS - nobody but us - policy. I heard that other intelligence services did notice the change of algorithm in the PX1000 and also had done their own analysis.