|
|
|
|
|
|
|
EMU Burst Algo Nokia Philips ← UA-8295
Weakened algorithm for UA-8295/00 short-burst terminal
- under construction
This page describes a weak encryption algorithm that was provided in 1984 by
the US National Security Agency (NSA),
for use with the Philips UA-8295/00 short-burst terminal (SBT).
The SBT was originally developed by Nokia
as the DA-8520 — in Finland known as the
m/90 SANLA — and used the
DES encryption algorithm in OFB mode. At the time, DES was considered
a strong encryption algorithm that was difficult to break.
The alternative NSA-supplied algorithm was deliberately weakened to allow
the NSA to break it more easily. This is known as a
backdoor.
The NSA asked Philips to add
the Nokia device to its product portfolio
and supply it worldwide, presenting the NSA-supplied algorithm as
'stronger-than-DES'. During the course of 1985, the alternative algorithm —
within NSA known as the SBT algorithm — was presented to Philips
for evaluation.
After approval it was silently released with new devices, using the
existing model number UA-8295/00. On startup, the NSA-variant
shows the same version number: E22444.
|
UNDER CONSTRUCTION —
This page is currently under construction and is incomplete.
Whilst we are researching the NSA-supplied SBT algorith, new
information will be added to this page as and when it becomes available.
This page is subject to change without prior notice. If you want to
contribute to it, please feel free to contact us.
The firmware of the Philips UA-8295/00 (or in fact the
Nokia DA-8520),
is held in two socketed 27C64 EPROMs of 8kB each, marked IC24 and IC18.
These are the two EPROMs that are closest to the front edge of the case.
In the image below, these two ICs are shown in red. IC24 is mapped in the
lower address space 0x0000-0x1FFF, whilst IC18 is mapped just above it at
0x2000-0x3FFF.
In addition to this, an extra EPROM with the texts for the on-screen
operating instructions (IC15) is mapped in the address space 0x4000-0x5FFF.
This ROM is identical for all versions of the terminal.
Furthermore, 8kB of battery-backed SRAM is mapped to the address space
0x0000-0x1FFF. This is the part that holds the messages, the key
and the configurable settings.
Note that the device has two 80C31 microcontrollers, each of which
has its own firmware. The main one is located at the right and
controls the user interface and the encryption/decryption of the
messages. This is the part that is further described below.
The other one (yellow) is located at the left and controls the radio modem.
Its firmware is stored in a single 8kB EPROM (IC03).
|
From the outside it is almost impossible to tell which version of
the firmware is present in a UA-8295/00 as the model number is unchanged.
Furthermore the user interfaces are identical,
as are the version numbers that are presented on the
display at startup: VE22444.
And although the two algorithms are completely different, the checksums
of the EPROMs are identical as well.
The alternative version with the SBT algorithm was supplied by NSA
as a drop-in replacement
for the original EPROMs.
Apparently, the NSA had disassembled the original code, isolated the
parts that were related to DES, and replaced only that part of the code
by the SBT algorithm. As the SBT code is shorter than the DES code,
the remaining ROM space is filled with 'fudge bytes' that are choosen in
such a way that the checksums of the ROMs are the same as with the
DES version.
The only way to discriminate the devices is to enter a known
15-character key and observe the 4-character check group that is
calculated from that. These are different for each version.
When we enter the key AAAAAAAAAAAAAAA (15 × the letter 'A'),
the check groups for the two versions are:
Original Nokia version (DES): KPOD
NSA version (SBT): JJDI
|
Below is the memory map of the 80C31 microcontroller. This controller
has 128 bytes of internal RAM and can address up to 64kB of external
RAM and up to 64kB of external ROM. In this case, the external
RAM is provided by a Toshiba TC5565 which offers 8kB of
battery-backed SRAM.
The firmware is stored in three 27C64 EPROMs with a total space of
24kB. The lower 16kB of this (IC24, 18) holds the actual firmware,
whilst the upper 8kB is filled with the text for the on-screen manual.
The latter is identical for all versions of the terminal. When using
the SBT-algorithm, only the bottom 16kB has to be altered, which
requires only EPROMs IC24 and IC18 to be replaced.
|
|
The description below is largely based on an internal NSA document [2]
and the personal notes of Cees Jansen [1], the former cryptographer of
Philips Usfa who evaluated the implementation back in 1985.
|
The key is generated in 64-bit blocks (8 bytes). It is then used, one byte
at a time, to encrypt or decrypt the input text, one byte at a time.
After all 8 key bytes have been used, another 64-bit key block is generated.
The entire process comprises 11 steps that are further explained below.
In the description of the steps, the bits are numbered 1-64 from left to right
(rather than 0-63 from right to left),
whereas the individual bytes and nibbles taken from the intermediate results
are treated as data words of which the least significant bit (LSB) is at the
right. This may lead to some confusion.
The algorithm consists of the following steps:
|
- Initial FILL
The 64 bits of a user-defined secret key are loaded into a 64-bit
Linear-feedback shift register (LFSR) [3]. This is known as the
initial FILL. The 64-bit fill register is now stepped 64 times
according to the primitive polynomal 1 + x32 + x63 .
The result is kept for the next round.
It is also used as the input to the non-linear portion of the key generator.
- Fixed bit permutation
The bits of the FILL are now permuted into FILL' according to the table below.
bit 1 -> 10 60 55 08 33 41 32 21
24 06 52 36 26 15 64 47
11 30 34 22 49 42 04 62
43 12 25 58 18 01 35 54
19 40 63 29 50 09 46 05
03 37 53 23 61 44 14 31
38 57 07 56 13 27 20 48
28 51 39 02 59 16 17 45 <- bit 64
A few examples: After the permutation, bit 1 of the FILL becomes bit 10 of
FILL', bit 2 becomes bit 60 and bit 64 of the FILL becomes bit 45 of FILL'.
- Input to box permutation
The output from the previous stage — the fixed bit permutation, or FILL' —
forms the input to the next stage: the box permutation (4). When the
algorithm runs, steps (4) to
(11) are repeated 8 times. This is known as a round or rank.
Before each additional rank, the value of step (3) is replaced by
the result of the previous rank (11).
- Box permutation
For the box permutation, the 64 bits of the previous result (3) are
divided into nibbles. The box permutation is then applied to each nibble
in the following order:
15 16 13 14 11 12 9 10 07 08 05 06 03 04 01 02
t.b.a.
- Input to fixed byte permutation
The output of the previous stage (4) consists of 16 nibbles, which
are then treated as 8 bytes that are used as the input to the next stage
(6).
- Fixed byte permutation
The 8 bytes from the previous stage are now permuted as follows:
input: 1 2 3 4 5 6 7 8
output: 6 1 8 2 4 7 3 5
This means that byte 1 becomes byte 2, byte 2 becomes byte 4, etc.,
until finally, byte 8 becomes byte 3.
- Input to the nibble switch
The 8 output bytes from the previous stage are then treated as 16 nibbles
(or more precisely: as 8 nibble pairs) and used as the input
to the next stage: the nibble switch.
- Nibble switch
In this stage, the two nibbles of each byte are swapped (or not)
according to the 8 bits of a control word Nr which is derived
from the cryptovariable. The nibbles of a byte are only swapped, if the
corresponding bit of the control word is '1'. For example:
if bit 1 of the control word is 0, the nibbles of byte 1 are not swapped.
control Nr: 01100011
input: 1a 1b 2a 2b 3a 3b 4a 4b 5a 5b 6a 6b 7a 7b 8a 8b
output: 1a 1b 2b 2a 3b 3a 4a 4b 5a 5b 6a 6b 7b 7a 8b 8a
----- ----- ----- -----
- Input to S-Boxes
The 16 nibbles of the 64-bit output from the previous stage, is
used as the nibble-wise input to the S-Boxes.
- S-Boxes
Each of the nibbles from the previous stage is now passed through a
lookup table that is different for each nibble. For example: if the
first nibble has the hex-value 0x5 , it will be translated to 0xA .
The result of this example is highlighed in red in the table below.
nibble position (from previous result)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
-----------------------------------------------
0 | 1 8 5 9 B 3 4 7 2 7 B D 1 8 F 4
1 | 5 D 2 7 A E 9 F 4 D 7 2 8 B A F
n 2 | 4 7 1 6 E D 8 0 5 6 9 C E 3 8 A
i 3 | 6 E 4 D 0 9 5 C C 8 5 9 A E D 1
b 4 | C 5 D B 9 1 0 A 9 A A E 7 D 3 B
b 5 | A 0 E F D 4 6 8 B 3 1 7 4 A 0 2
l 6 | 9 B 0 4 3 8 A 1 7 0 F 3 9 4 E 8
e 7 | F 1 9 C 2 6 E B 8 4 6 1 D F 2 0
8 | 3 2 F 0 6 A B 9 F 5 2 4 6 9 C D
v 9 | E 3 B 8 C 0 2 D E F C 8 3 0 6 5
a A | 8 C 6 2 F F 7 5 D 2 4 0 B C 9 6
l B | 0 1 C E 7 5 F 3 A E D F 5 6 1 C
u C | D F 3 A 8 2 1 E 3 A E 6 F 5 4 7
e D | 7 4 A 1 5 F 3 2 1 C 8 A 0 7 B 3
E | 2 9 7 3 4 C D 6 0 B 3 5 2 1 7 9
F | B 6 8 5 1 7 C 4 6 9 0 B C 2 5 E
- Key output
For the first 7 ranks, the 16 nibbles from the previous stage (10)
are used as the input for the next rank. They are treated as 64 bits
that replace the value of stage (3). After the 8th and final rank,
the output from stage (10) is treated as 8 bytes of key, that are
used to encrypt or decrypt text.
Once all 8 key bytes are used, the algorithm is run again to
generate the next 8 key bytes, and so on, until the entire
text is encrypted or decrypted.
|
|
According to the original description of the algorithm [2], it could
easily be tailored to the customer's requirements. The following
changes could be specified by the customer, without affecting the
(in)security of the algorithm (i.e. the NSA's ability to break it).
|
- 7 mask bits
Seven bits of the MASK (used in the initialisation of the cryptographic
algorithm) can be specified by the customer.
- Input buffer permutation
A fixed permutation on the 64 bits of the input buffer can be made unique
to the customer.
- Unique S-Boxes
Each of the 16 S-Boxes (each translating a nibble) can be made unique
to the customer.
- Fixed byte permutation
The fixed byte permutation (step 6) can be made unique to the customer.
|
|
|
|
Any links shown in red are currently unavailable.
If you like the information on this website, why not make a donation?
© Crypto Museum. Created: Tuesday 04 January 2022. Last changed: Tuesday, 02 April 2024 - 12:54 CET.
|
 |
|
|
|
