|
|
|
|
|
|
|
EMU Text Lite Philips NSA ← PX-1000
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
|
|
|
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
|
 |
-
This was done by selling the entire stock of 12,000 units to the Americans
for NLG 16.6 million.
-
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
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
|
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
|
|
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.
|
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.
|
|
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 keystream bit for every encrypted
character. Moreover, the first character in the cipher text is an
encrypted fixed character.
|
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:
|
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
|
|
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.
|
|
|
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
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
|
- Marcel Metze, Ingelijfd door de NSA
De Groene Amsterdammer. 29 January 2014. Embedded in the NSA (Dutch).
- 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).
- Wikipedia, Data Encryption Standard
Retrieved January 2016.
- Wikipedia, Nelson Mandela
Retrieved November 2013.
- 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.
- Argos, Philips, TextLite en Amerikaanse Spionage
NPO Radio 1 broadcast, Saturday 20 April 2019, 14:00-15:00 (Dutch).
- Stefan Marsiske, Breaking the PX-1000Cr
Crypto Museum, 16 February 2022.
|
|
|
|
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.
|
|
|
|
|
