https://www.cryptomuseum.com/crypto/philips/px1000/nsa.htm#stef bg image(../../../) [wheel] [twitter_lo] [youtube_pl] [search] Homepage [ ] Crypto Index [Search] Click for homepage Glossary _ Enigma Hagelin EMU Fialka Rotor Text Lite Pin-wheel Voice Philips Data Hand NSA OTP EMU - PX-1000 Mixers Phones _ Bulk PX-1000Cr algorithm FILL _ Codebooks _ Algorithms Deliberate weakening of a cryptographic algorithm by the NSA Cryptanalysis [down] [down] Countries PX-1000 was a handheld message terminal, also known as a pocket DDR telex, developed in 1980 by Text Lite in Amsterdam (Netherlands) and Germany sold worldwide by Philips and others. Some versions of it had Switzerland built-in encryption capability. In the initial version, the DES UK algorithm was used, but this was later replaced by another algorithm USA at the request of the US National Security Agency (NSA). USSR Yugoslavia Apparently, the NSA was not too happy with the fact [down] [down] that DES, which was considered a strong encryption Philips Manufacturers algorithm at the time, was available to the general PX-1000Cr with ANT public. At the request of the NSA, Philips took the NSA-supplied Aristo DES-based machines off the market ^1 and had the encryption Ascom algorithm replaced by an alternative one that was algorithm, now AT&T supplied by the NSA. broken. BBC [busted] Bosch Although it was suggested that the alternative Compumatica algorithm was similar in strength to DES, this does Crypto AG not make much sense. It seems far more likely, that Datotek it was deliberately weakened. Such weakening is Fox-IT commonly known as a backdoor. ^2 GD Gemalto The rather obscure relation between Philips and the NSA has been the Gretag subject of discussion for some time, for example in Marcel Metze's Harris article Ingelijfd door de NSA (Embedded in the NSA) of January 2014 HELL [1]. In this article, Metze explains how a Philips engineer first ITT visited the NSA in 1977. A few years later, Philips was allowed to Lorenz implemented the NSA's highly secret SAVILLE encryption algorithm in Lugagne their forthcoming cryptophones Spendex 40 and Spendex 50 (DBT). MEL Mils In the past, the DES implementation of the initial PX-1000 version Motorola has been analysed and inspected for 'backdoors', and was found to be Mykotronx correct [2]. As the later PX-1000Cr - with the alternative NSA Nokia algorithm - was freely available on the market and its firmware was OMI not protected in any way, a Crypto Museum team has now disassembled Omnisec and inspected the NSA algorithm. Philips PTT The PX-1000 was available worldwide for several years from big R&S companies like Philips, Siemens, Alcatel and Ericsson, and was used Racal by prominent people such as Nelson Mandela and to some extent by the RanData Dutch Government's Foreign Office. In this light, it would be very Raytheon interesting to know to what security risks the people or RCA organisations involved may have been exposed to. Safenet Siemens More about the PX-1000 STK Tadiran _ Tait 1. This was done by selling the entire stock of 12,000 units to the Telefunken Americans for NLG 16.6 million. Telsy 2. Technically speaking, a deliberate weakening is not a backdoor, Teltron but since it is applied to provide unauthorised access, we will Thales use that popular expression in this context. Transvertex TST Ultra Electronics _ Zellweger Index OTHER _ Spy radio _ Burst encoders Intercept * The DES algorithm Covert * The NSA algorithm Radio * Impact on Nelson Mandela PC * NSA algorithm broken by Stef Telex Telephones _ People Introduction Agencies _ Manufacturers _ DONATE The first PX-1000 units appeared on the market in 1980, a year after Publications its development by Text Lite in Amsterdam (Netherlands). From the Standards outset, the PX-1000 was capable of sending and receiving messages in For sale encrypted form, using the Data Encryption Standard (DES) [3] as Kits obtained from the American Bureau of Standards (now: NIST). When Shop Philips started selling the PX-1000 in 1983, the NSA intervened and News persuaded Philips to replace DES by an alternative NSA-supplied Events algorithm. Wanted Contact [px1000_memory_map] About us Links 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). Download the ROMs _ The DES algorithm _ _ In 2014, Bachelor student Ben Brucker 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 Brucker'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 L[7]-L[10] are rotated left by 2 positions (ROL 2) before they are XOR-ed with bytes L[0]-L[3]. 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. [px1000_nsa_flow] The (P) block in the feedback loop consists of a set of 4 different nibble permutations (p[0]-p[3]), 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 keystream 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: [px1000_lfs] _ 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 for 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 Nelson Mandela potential target of the NSA, especially since they on the day of were suspected from having strong connections with is release left-wing and even communist regimes. from prison in 1990 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. 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 _ Analysis of the NSA algorithm _ _ _ 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. Naturally we made an appointment, and when he visited Crypto Museum a couple of weeks later, he was able to show us the results of his research. With just 17 characters of ciphertext, he can fully recover the encryption key and break any PX-1000Cr message that was sent on that key, in just 4 seconds on a regular laptop in a single thread. On 15 February 2022, the break was fully described in edition 21 of the magazine Proof-of-Concept or Get The Fuck Out (PoC||GTFO) [8], with additional notes on Stef's personal blog the following day [9]. In his break, Stef makes extensive use of Z3, an efficient SMT solver, developed at Microsoft Research in 2007 [10]. Z3 is capable of many things, including solving algebraic functions [11][12]. More precisely, he used claripy [13] -- a wrapper around Z3 -- by the angr project [14]. Although it is still unclear which method the NSA used at the time to break the cipher, it is clear that it is much weaker than DES. Solving a PX-1000Cr message in just 4 seconds on a modern laptop with just 17 characters of ciphertext, is quite impressive. Especially if you realise that good old DES cannot be broken with the same method. Here are Stef's publications on this topic: a. Stefan Marsiske, NSA's Backdoor of the PX1000-Cr PoC||GTFO magazine 21:12, 15 February 2022. pp. 59-66. b. Stef, A historical NSA backdoor First introduction. Camp++ 0x7e5, 26-29 August 2021. YouTube, 10 October 2021. Presentation slides (off-site). c. Stef's personal blog, pocorgtfo 21:12 apocrypha 16 February 2022. d. Stef's PX-1000 repository on GitHub All the tools, scripts and data used for the attack. e. Reconstructed PX-1000Cr algorithm in C The reverse-engineered PX-1000Cr algorithm in the C programming language. f. Final attack code This is the final attack code that was used to achieve the break. And here are some reactions from the hacker community: * Various members, NSA's Backdoor of the PX1000-Cr Hacker News, 17 February 2022. _ Documentation _ _ A. ROM dumps of PX-1000 (DES) and PX-1000Cr (NSA) Crypto Museum, February 2014. B. Hitachi, HD6303RP microprocessor datasheet Date unknown. _ References _ _ 1. Marcel Metze, Ingelijfd door de NSA De Groene Amsterdammer. 29 January 2014. Embedded in the NSA (Dutch). 2. Ben Brucker, 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, A historical NSA backdoor First introduction. Camp++ 0x7e5, 26-29 August 2021. YouTube, 10 October 2021. Presentation slides (off-site). 8. Stefan Marsiske, NSA's Backdoor of the PX1000-Cr PoC||GTFO magazine 21:12, 15 February 2022. pp. 59-66. 9. Stef's personal blog, pocorgtfo 21:12 apocrypha 16 February 2022. 10. Leonardo de Moura, Nikolaj Bjorner (2008), Z3: An Efficient SMT Solver LNCS, volume 4963. DOI 10.1007/978-3-540-78800-3_24. ISBN 978-3-540-78799-0. 11. Wikipedia, Z3 Theorem Prover Retrieved 16 February 2022. 12. GitHub, Z3Prover Retrieved 16 February 2022. 13. Github, claripy wrapper around Z3 Visited 17 February 2022. 14. Angr Project Visited 17 February 2022. _ Further information _ _ * Main PX-1000 page * About the NSA * About TEXT TELL * Other Philips cryptographic devices * Other cipher machines _ 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: Thursday, 17 February 2022 - 16:31 CET. _ Click for homepage