Click for homepage
EMU
Text Lite
Philips
NSA
  
← Algorithm
← PX-1000
  
NSA algorithm broken by Stef
16 February 2022

PX-1000 was a hand-held message terminal with built-in encryption, also known as a pocket telex, introduced in 1983 by Text Lite in Amsterdam (Netherlands) and sold (among others) by Philips. For encryption it used DES, which was considered a strong algorithm at the time. At the request of the NSA – with help from PhilipsDES was replaced by an alternative algorithm that was provided by the NSA and was said to be at least as strong as DES, but probably better. This is known as the PX-1000Cr algorithm. This page describes a successful break of the PX-1000Cr algorithm, and confirms, for the first time, that the NSA algorithm does indeed have a backdoor.

Introduction
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 [3], 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 demonstrate the results of his research. And they were impressive. With just 17 characters of ciphertext, Stef 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 described in edition 21 of the magazine Proof-of-Concept or Get The F*ck Out (PoC||GTFO) [4], with extra remarks on Stef's personal blog the next day [5].
  
Interior of the PX-1000Cr

In his break, Stef makes extensive use of Z3, an efficient SMT solver, developed at Microsoft Research in 2007 [6]. Z3 is capable of many things, including solving algebraic functions [7][8]. More precisely, he used claripy [9] — a wrapper around Z3 — by the angr project [10].

Although we still don't known which method the NSA used in the mid-1980s to break the cipher, it is evident that it is very 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.

 Read the full paper


Publications
  1. Stefan Marsiske, NSA's Backdoor of the PX1000-Cr
    PoC||GTFO magazine 21:12, 15 February 2022. pp. 59-66.

  2. Stef, A historical NSA backdoor
    First introduction. Camp++ 0x7e5, 26-29 August 2021. YouTube, 10 October 2021.
     Presentation slides (off-site).

  3. Stef's personal blog, pocorgtfo 21:12 apocrypha
    16 February 2022.

  4. Stef's PX-1000 repository on GitHub
    All the tools, scripts and data used for the attack.

  5. Reconstructed PX-1000Cr algorithm in C
    The reverse-engineered PX-1000Cr algorithm in the C programming language.

  6. Final attack code
    This is the final attack code that was used to achieve the break.
Media coverage
  1. Various members, NSA's Backdoor of the PX1000-Cr
    Hacker News, 17 February 2022.

  2. Olaf van Miltenburg, Ontwikkelaar kraakt NSA-encryptie van oude pockettelex van Philips
    Tweekers, 18 February 2022.

  3. HABR, NSA backdoor in 1984 pocket telex - history repeats itself (Russian)
    Russian hacker forum, 9 March 2022.

  4. Klaus Schmeh, Wie die NSA ein Verschlüsselungsgerät schwächte
    Cipherbrain blog, 20 March 2022.
Documentation
  1. ROM dumps of PX-1000 (DES) and PX-1000Cr (NSA)
    Crypto Museum, February 2014.

  2. Hitachi, HD6303RP microprocessor datasheet
    Date unknown.
References
  1. Crypto Museum, PX-1000
    22 April 2011.

  2. Crypto Museum, Description of the PC-1000Cr algorithm
    15 January 2016.

  3. Stefan Marsiske, NSA's Backdoor of the PX1000-Cr
    PoC||GTFO magazine 21:12, 15 February 2022. pp. 59-66.

  4. Stef's personal blog, pocorgtfo 21:12 apocrypha
    16 February 2022.

  5. Leonardo de Moura, Nikolaj Bjørner (2008), Z3: An Efficient SMT Solver
    LNCS, volume 4963. DOI 10.1007/978-3-540-78800-3_24. ISBN 978-3-540-78799-0.

  6. Wikipedia, Z3 Theorem Prover
    Retrieved 16 February 2022.

  7. GitHub, Z3Prover
    Retrieved 16 February 2022.

  8. Github, claripy wrapper around Z3
    Visited 17 February 2022.

  9. Angr Project
    Visited 17 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: Wednesday 16 February 2022. Last changed: Thursday, 24 March 2022 - 10:00 CET.
Click for homepage