There is good reason to believe the weaknesses introduced by the NSA with the PX1000-cr algorithm were introduced as part of a series of multiple backdoors that cooperate together [2][3].

The equation system to be solved is rather huge (~20 megabytes when shown as ASCII text), therefore it is logical to assume the NSA required more efficient techniques to break it in the 1980s.

The fact that the first and last character, as well as the top bits in between, leak the keystream makes for an easy and cheap attack that amortizes the algebraic attack costs. Detection of key re-use is therefore trivial.

And since this is a stream cipher key reuse, it is cryptographically disastrous; an excellent illustration of this is the Venona project [1].The NSA has spent decades trying to recover plaintext from two-timepads, but in the Venona case they did not know which two messages shared the same key. This is significantly simpler with the PX1000-cr.

For Venona, it is a safe guess that the NSA developed a significant amount of HW capable of recovering plaintext from two plaintexts that have been XOR-ed together. This implies they may employ more costly algebraic or other attacks only on cryptograms with unique keys. This, I feel, is a critical insight: there is not a single backdoor here, but numerous ones that cooperate.

[1] https://en.wikipedia.org/wiki/Venona_project

[2] https://www.alchemistowl.org/pocorgtfo/pocorgtfo21.pdf

[3] https://www.ctrlc.hu/~stef/blog/posts/pocorgtfo_21_12_apocry...