Click for homepage
EMU
Burst
Algo
Nokia
Philips
  
← UA-8295
  
SBT algorithm
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.
Firmware
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).

Which version?
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

EPROMs
Labels at the bottom of the EPROMs
Two replacements ROMs as supplied by the NSA
Two replacement ROMs
A
×
A
1 / 4
EPROMs
A
2 / 4
Labels at the bottom of the EPROMs
A
3 / 4
Two replacements ROMs as supplied by the NSA
A
4 / 4
Two replacement ROMs

Memory map
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.


Algorithm
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.

Key generation
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:

  1. 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.

  2. 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'.

  3. 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).

  4. 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.

  5. 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).

  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.

  7. 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.

  8. 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
                         -----  -----                       -----  -----
    

  9. 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.

  10. 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

  11. 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.
Initialisation
t.b.a.

Working example
t.b.a.

Customisation
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).

  1. 7 mask bits
    Seven bits of the MASK (used in the initialisation of the cryptographic algorithm) can be specified by the customer.

  2. Input buffer permutation
    A fixed permutation on the 64 bits of the input buffer can be made unique to the customer.

  3. Unique S-Boxes
    Each of the 16 S-Boxes (each translating a nibble) can be made unique to the customer.

  4. Fixed byte permutation
    The fixed byte permutation (step 6) can be made unique to the customer.
Download
References
  1. Cees Jansen, The algorithm of the UA-8295 and UA-8296
    28 May 2021.

  2. Description of the SBT algorithm
    NSA, internal document. Undated.

  3. Wikipedia, Linear-feedback shift register
    Visited January 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: Tuesday 04 January 2022. Last changed: Tuesday, 02 April 2024 - 12:54 CET.
Click for homepage