Homepage
Crypto
Index
Glossary
Enigma
Hagelin
Fialka
Nema
Voice
Hand
OTP
EMU
Mixers
Phones
FILL
Codebooks
Algorithms
USA
USSR
UK
Yugoslavia
Ascom
AT&T
Bosch
Datotek
Gretag
HELL
ITT
Motorola
Mils
OMI
Philips
Racal
Siemens
STK
Tadiran
Telsy
Teltron
Transvertex
TST
Spy radio
Burst encoders
Intercept
Covert
Radio
PC
Telex
People
Agencies
Manufacturers
• • • Donate • • •
Kits
Shop
News
Events
Wanted
Contact
About
Links
   Click for homepage
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, developed 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

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 visits 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 the past, 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.

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.

 More about the PX-1000

  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.

Index
The DES algorithm
The first PX-1000 units appeared on the market in 1980, a year after the device was developed by Text Lite BV 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) [4] as obtained from the American Bureau of Standards (now: NIST). When Philips was selling the PX-1000 in 1983, the NSA intervened and asked them to replace DES by an alternative 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 0xFFF).

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

 Download the ROMs
 Download the 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 right by 2 positions (ROR 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 bits to one output bit. It is implemented as a compact lookup table.


The (P) block in the feedback loop consists of a set of 4 different nibble permutations (p1-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 crypto text 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.

Conclusions
Although we are still in the early stages of our research, we may already conclude that the cryptographic algorithm used in the PX-1000Cr is substantially weaker than the DES algorithm of the other PX-1000 versions.

To be continued...

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 for Operation Vula: the secret communication between the anti-apartheids movement in Europe and dissident Nelson Mandela [5] (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 from 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 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 [6]. 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

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. Crypto Museum, ROM dumps of PX-1000 and PX-1000Cr
    February 2014.

  4. Wikipedia, Data Encryption Standard
    Retrieved January 2016.

  5. Wikipedia, Nelson Mandela
    Retrieved November 2013.

  6. 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.
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: Sunday, 20 November 2016 - 17:40 CET.
Click for homepage