Click for homepage
EMU
Text Lite
Philips
NSA
  
← PX-1000
  
PX-1000Cr algorithm
Deliberate weakening of a cryptographic algorithm by the NSA

PX-1000 was a handheld message terminal, also known as a pocket telex, introduced in 1980 by Text Lite in Amsterdam (Netherlands) and sold worldwide by Philips and others. Some versions of it had built-in encryption capability. In the initial version, the DES algorithm was used, but this was later replaced by another algorithm at the request of the US National Security Agency (NSA).

Apparently, the NSA was not too happy with the fact that DES, which was considered a strong encryption algorithm at the time, was available to the general public. At the request of the NSA, Philips took the DES-based machines off the market 1 and had the algorithm replaced by an alternative one that was supplied by the NSA.

Although it was suggested that the alternative algorithm was similar in strength to DES, this does not make much sense. It seems far more likely, that it was deliberately weakened. Such weakening is commonly known as a backdoor. 2
  
Philips PX-1000Cr with NSA-supplied encryption algorithm, now broken.

The rather obscure relation between Philips and the NSA has been the subject of discussion for some time, for example in Marcel Metze's article Ingelijfd door de NSA (Embedded in the NSA) of January 2014 [1]. In this article, Metze explains how a Philips engineer first visited the NSA in 1977. A few years later, Philips was allowed to implemented the NSA's highly secret SAVILLE encryption algorithm in their forthcoming cryptophones Spendex 40 and Spendex 50 (DBT).

In July 2014, the DES implementation of the initial PX-1000 version has been analysed and inspected for 'backdoors', and was found to be correct [2]. As the later PX-1000Cr - with the alternative NSA algorithm - was freely available on the market and its firmware was not protected in any way, a Crypto Museum team has now disassembled and inspected the NSA algorithm. In February 2022, Hacker Stefan Marsiske managed to break it and demonstrate its weakness.

The PX-1000 was available worldwide for several years from big companies like Philips, Siemens, Alcatel and Ericsson, and was used by prominent people such as Nelson Mandela and to some extent by the Dutch Government's Foreign Office. In this light, it would be very interesting to know to what security risks the people or organisations involved may have been exposed to.

 More about the PX-1000
 Breaking the PX-1000Cr

  1. This was done by selling the entire stock of 12,000 units to the Americans for NLG 16.6 million.
  2. Technically speaking, a deliberate weakening is not a backdoor, but since it is applied to provide unauthorised access, we will use that popular expression in this context.

DES algorithm
NSA algorithm
Nelson Mandela
Broken by Stef
  
Introduction
The first PX-1000 units appeared on the market in 1980, a year after its development by Text Lite in Amsterdam (Netherlands). From the outset, the PX-1000 was capable of sending and receiving messages in encrypted form, using the Data Encryption Standard (DES) [3] as obtained from the American Bureau of Standards (now: NIST). When Philips started selling the PX-1000 in 1983, the NSA intervened and persuaded Philips to replace DES by an alternative NSA-supplied algorithm.


The diagram above shows the memory map of the PX-1000, which consists of 64 KB of address space, divided over 4 sections of 16KB each (numbered 0-3). Section (0) contains the internal registers, a small amount of RAM and the external 4KB RAM. Sections (1) and (2) are used for the keyboard and the display respectively. The actual firmware is stored in a ROM or EPROM that is mapped in the upper 8KB of the address space of section (3) (addresses 0xE000 to 0xFFFF).

For analysis by researchers, Crypto Museum has removed the ROMs (with the firmware) from both the original PX-1000 with DES, and the PX-1000Cr with the alternative algorithm from the NSA, and made them publicly available for download, so that they can be disassembled and inspected.

 Download the ROMs


The DES algorithm
In 2014, Bachelor student Ben Brücker investigated both algorithms, using ROM dumps of the two PX-1000 variants, as supplied by Crypto Museum [A]. In his Bachelor Thesis [2], he scrutinised the original DES implementation and came to the conclusion that it has been implemented correctly. Furthermore, he roughly described the PC-1000Cr algorithm and concluded that it is a stream cipher, but that further research is needed to determine its strength or weakness.

 Download Ben Brücker's Bachelor Thesis


The NSA algorithm
Based on the earlier research and persistent rumours of a possible backdoor in the NSA-supplied algorithm, a Crypto Museum team consisting of Cees Janssen, Paul Reuvers and Marc Simons, has now started to isolate the algorithm from the code and analyse its properties. Their preliminary findings are reported below. Please note that this page will be updated as the research continues.

General description
The PX-1000Cr cryptographic algorithm is a stream cipher with cipher feedback (CFB). The driving function is the 16-byte array (L), that implements four different Linear Feedback Shift Registers (LFSRs) of lengths 27, 29, 31 and 32 bits. Bytes L7-L10 are rotated left by 2 positions (ROL 2) before they are XOR-ed with bytes L0-L3. The block denoted by (F) consists of a set of 8 nonlinear functions of 6 input bits to one output bit, implemented as a compact lookup table.


The (P) block in the feedback loop consists of a set of 4 different nibble permutations (p0-p3), i.e. Boolean functions of 4 bits input and 4 bits output, that are identical for the high and low order 4 bits of a byte. These functions are implemented as compact lookup tables. Block (V) is an 8 byte register (in two parts) in which the secret encryption key is stored. Block (C) is a 4 byte FIFO register that contains the 4 most recent ciphertext bytes, resulting in an error extension of 4 bytes. Note that each byte is rotated left by one position, before shifting place in the FIFO. Register (K) holds the key stream byte, which is added to a plaintext byte to obtain a crypto byte.

Initial state
There is no random fill of any register. Initially the (L) and (C) arrays are filled with secret key bits that are derived from the secret encryption key entered by the user. Because of the 7-bits ASCII format used by the PX-1000, the cipher text reveals one plain key­stream bit for every encrypted character. Moreover, the first character in the cipher text is an encrypted fixed character.

Description of the LFSRs
Below is a more detailed description of the four LFSRs, shown in the diagram above as the (L) array. This bit is difficult to recognise in the disassembled object code, as the four 32-bit registers are organised as eight interleaved 16-bit registers and implemented as 16 bytes. From the disassembled code we were able to reconstruct the LFSRs and their taps as follows:



Conclusions
From the initial analysis, it is clear that the cryptographic algorithm of the PX-1000Cr is substantially weaker than the DES algorithm used in the original PX-1000. We don't know which method the NSA used at the time, but the algorithm has now been broken by Stefan Marsiske, based on the information provided above and a disassembly of the ROM he made with IDA Pro.

 Breaking the NSA algorithm


Impact on Nelson Mandela
The intervention by the NSA took place in 1983. By 1984, revised PX-1000 units with the NSA-supplied cryptographic algorithm were available on the market. In 1986, the PX-1000 was used in Operation Vula: the secret communication between the anti-apartheids movement in Europe and dissident Nelson Mandela [4] (the later President of South Africa) in his Pollsmore prison cell. This way, Mandela's political partly, the ANC, prepared him for his expected release in 1990.

Although there is currently no proof for this, it seems logical to expect that the ANC was a potential target of the NSA, especially since they were suspected of having strong connections with left-wing and even communist regimes.

In this context it would be interesting to know whether the NSA had deliberately weakened the PX-1000's cipher, in order to monitor the ANC's communications. It would also be interesting to know whether the ANC had been using the NSA-weakened version, or instead the original one with the much stronger DES algorithm.
  
Nelson Mandela on the day of is release from prison in 1990

During Mandela's imprisonment, a strong worldwide anti-apartheids movement was led from the UK and The Netherlands. In the Netherlands, the movement was headed by Connie Braam who had recruted an army of volunteers for the underground covert operations in South Africa. As part of these operations, she had been actively looking for suitable communications equipment.

In her book Operatie Vula, Conny Braam explains how one of her people met a guy, by the name of Floris, in a pub in Amsterdam, who allegedly had developed the PX-1000 [5]. From him they learned that the device had been taken off the market as its encryption was too strong. It had been replaced by a calculator but he suggested to find the older version with built-in crypto.

In 1986, the calculator version of the PX-1000 had meanwhile been replaced by the new NSA-weakened PX-1000Cr. Later in her book (p. 86) Braam confirms that Floris had been able to get hold of a couple of the older crypto-capable PX-1000 versions, which indicates that they were aware of the difference between the two versions. We may therefore assume that the anti-apartheid movement used the more secure version of the PX-1000 and had outsmarted the NSA.

 More about operation Vula


NSA algorithm broken by Stef
16 February 2022
Click to see more

In late 2021 Crypto Museum was approached by a gentleman named Stefan Marsiske — Stef for short. Stef had been looking in to the NSA algorithm (PC-1000Cr) for several months and had some interesting information to share. After an initial presentation at Camp++ 0x7e5 in August 2021 [7], in which he had revealed the intermediate results, he had finally reached a breaktrough. Stef is able to retrieve the key and the plaintext, from just 17 characters of ciphertext.

 Read the full story


References
  1. Marcel Metze, Ingelijfd door de NSA
    De Groene Amsterdammer. 29 January 2014. Embedded in the NSA (Dutch).

  2. Ben Brücker, Government intervention on consumer crypto hardware
    A look at the PX-1000 before and after the NSA's involvement.
    July 2014. Bachelor Thesis, Radboud University, Nijmegen (Netherlands).

  3. Wikipedia, Data Encryption Standard
    Retrieved January 2016.

  4. Wikipedia, Nelson Mandela
    Retrieved November 2013.

  5. Conny Braam, Operatie Vula
    1992, Dutch. ISBN 978-9029083362. p. 66.
    Reprinted 2006, Dutch. ISBN 978-9045700465.
    English version 'Operation Vula', April 2005, ISBN 978-1919931708.

  6. Argos, Philips, TextLite en Amerikaanse Spionage
    NPO Radio 1 broadcast, Saturday 20 April 2019, 14:00-15:00 (Dutch).

  7. Stefan Marsiske, Breaking the PX-1000Cr
    Crypto Museum, 16 February 2022.
Further information
Any links shown in red are currently unavailable. If you like the information on this website, why not make a donation?
© Crypto Museum. Created: Thursday 14 January 2016. Last changed: Monday, 23 January 2023 - 10:11 CET.
Click for homepage