|
|
|
|
|
|
|
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 Philips – DES 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.
|
|
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].
|
|
|
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
|
- Crypto Museum, PX-1000
22 April 2011.
- Crypto Museum, Description of the PC-1000Cr algorithm
15 January 2016.
- Stefan Marsiske, NSA's Backdoor of the PX1000-Cr
PoC||GTFO magazine 21:12, 15 February 2022. pp. 59-66.
- Stef's personal blog, pocorgtfo 21:12 apocrypha
16 February 2022.
- 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.
- Wikipedia, Z3 Theorem Prover
Retrieved 16 February 2022.
- GitHub, Z3Prover
Retrieved 16 February 2022.
- Github, claripy wrapper around Z3
Visited 17 February 2022.
- Angr Project
Visited 17 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: Wednesday 16 February 2022. Last changed: Thursday, 24 March 2022 - 10:00 CET.
|
 |
|
|
|
