Click for homepage
NSA Type 1 cryptographic algorithm

SAVILLE is a cryptographic algorithm, that is widely used by the US Army and by NATO in high level encryption devices. It was developed by the GCHQ in cooperation with the NSA, probably in the late 1960s, and is categorized as an NSA Type 1 encryption product. It's early use in VINSON equipment during the Vietnam War is probably the reason why SAVILLE has become virtually synonymous with VINSON. It is used in many products, including the KY-57, KY-68 and KY-99. SAVILLE keys are loaded into an encryption device by means of a DS-102 compatible key loader.

The cryptographic keys for devices using SAVILLE are generally transferred with a universal key transfer device, such as the KYK-13. The algorithm itself is secret and is often implemented in NSA-developed modules such as Crypris, Windster and INDICTOR (SAVILLE I). Below is a technical description that sheds some light on SAVILLE without revealing the actual algorithm itself [4].

SAVILLE-based products on this website
Secure Telehone Unit STU-I (KY-70)
STU-II narrow-band half-duplex crypto phone
Motorola STU-III/R (STU-II and STU-III compatible)
Wide-band Voice and Data Encryption Unit
Digital Subscriber Voice Terminal
Narrow-band Voice and Data Terminal
Philips Spendex-40 secure telephone for voice, fax and computer
Philips Spendex-50 military secure telephone for voice, fax and computer
KG-84 data encryptor
KIV-7, embeddable KG-84 COMSEC module
STU-II/B narrow-band half-duplex crypto phone
STK/Thales TCE-500 crypto phone
Elcrovox 1-4D narrow band voice and data terminal (STU-II compatible)
UK Lamberton (BID/250)
Motorola Saber hand-held radios with FASCINATOR option
Cougar handheld radio PRM-4515 with VINSON-compatible crypto module
Racal Cougar PRM-4735 body-wearable covert radio with VINSON compatible crypto module
Racal Cougar Digital Voice Encryptor with VINSON-compatible crypto module
Advanced Infosec machine (Motorola)
Advanced INFOSEC machine II
RAILMAN embeddable cryptographic processor with SAVILLE
Harris SIERRA cryptographic engine
Harris SIERRA II cryptographic engine
The SAVILLE Cryptographic Algorithm
Contribution by a former cryptographer [4]

The SAVILLE cryptographic algorithm — these were called crypto logics in the old days — is a stream cipher, widely used in cryptographic equipment used by NATO and by the administrations of NATO-countries. SAVILLE is a joint development of the NSA (US) and GCHQ (UK) and its origin probably dates back to end of the 1960s, beginning of the seventies, considering the early implementations in devices such as the US VINSON (KY-57) and the UK Lamberton (BID/250).

At the time, two teams were formed to develop a new cryptographic algorithm: one at the NSA and one at GCHQ. At GCHQ, WWII cryptanalist Michael Crum 1 was involved in the project. Both teams produced algorithms which were then rigorously analysed by the other agency. In the end, the GCHQ algorithm was accepted as the better one and became known as SAVILLE [5]. In most literature however, SAVILLE is commonly attributed to the NSA.

  1. During WWII, Michael Crum was a cryptanalist at Bletchley Park (BP). In 1942 he was the first at BP to break into the German T-52 Geheimschreiber traffic, which enabled them to reconstruct the machine.

IMPORTANT — This note serves to shed some light on the characteristics of this cipher. It should be clear however, that no secret information is revealed. Rather, information was used from old unclassified documents and websites (many of which are no longer available on the web today).
Stream Cipher
SAVILLE is a stream cipher. More precisely, it is a bit-stream cipher and not a block cipher in some stream cipher mode, like OFB or CFB. SAVILLE has two modes-of-use:

  1. Autonomous mode (KAK)
    One mode is the autonomous mode, denoted by KAK (Key Auto Key, comparable to OFB), where it behaves as an autonomous finite state machine generating a pseudo-random key stream.

  2. Autoclave mode (CTAK)
    A second mode is the autoclave mode denoted by CTAK (Cipher Text Auto Key, comparable to CFB), in which mode there is dependency on the cipher text.
As with most OFB (KAK) stream ciphers, SAVILLE lacks a driving function that guarantees a large minimum period of the keystream, hence, there is a probability of the cipher being in a short cycle. Means exist however, to check and prevent this short cycling.

SAVILLE is based on a nonlinear finite state machine, that has an internal cycle of several tens of iterations per output bit. This accounts for its low performance in many implementations, for example in MOTOROLA's Advanced Infosec Machine (AIM), where SAVILLE is basically a software implementation, running at 3% performance as compared to a standard block cipher. The non­linear part of the finite state machine can be described by a nonlinear feedback shift register (NLFSR) that generates a truncated De Bruijn sequence of maximum linear complexity [6].

SAVILLE uses a secret key of 120 bits length. In those days, key loading devices such as KYK-13, KOI-18, KYX-15 and UP-2001 were used. From the documentation of these devices, one can conclude that an eight-bit error detecting code was used to protect keys against bit-errors and device malfunctioning, and therefore the total key length was specified as 128 bits.

SAVILLE secret key structure

Also an Initial Vector (IV) has to be loaded to achieve cryptographic synchronisation, although the CTAK-mode is self-synchronising, but also gives rise to error extension. The finite state machine can be operated in 4 different configurations, the so called (Invert) Rules of Motion, for various cryptographic purposes. Switching between Rules of Motion during operation of the crypto-logic, had a complex timing and caused serious implementation problems for the developers who had to implement the algorithm, resulting in endless compatibility testing sessions.

Philips Usfa BV
In the Early 1980s, Philips Usfa in Eindhoven (Netherlands) received a first description of SAVILLE, because it was developing its Spendex-40 (narrow-band) and Spendex-50 (wide-band) secure voice equipment. Unlike before with Aroflex, that used a Philips Usfa designed crypto logic, this time it was decided to implement an existing and already NATO-approved crypto logic instead.

Clearly, this had a number of advantages. First of all interoperability with existing NATO equip­ment like the STU II crypto phone and VINSON. Secondly, it was anticipated that NATO approval by SECAN would take much less time, by not having to evaluate the known crypto logic again.

Rumour had it in those days, that there was a third reason. By implementing SAVILLE in a new national development, the Dutch security service NLNCSA would automatically receive all baseline documentation regarding the crypto logic, which would otherwise not be obvious at all.

Still, to Philips Usfa and its cryptography-aware employees it seemed quite peculiar that crypto­graphic equipment using a foreign, NSA-developed crypto logic, was used to protect top secret information. SAVILLE was implemented in hardware, more precisely in circuits comprising a custom gate array and standard integrated circuits, by Philips Usfa in the first half of the 1980s.

This is supported by the fact that a detailed description was not disclosed to Philips' employees until it was certain that the algorithm would be implemented in the new Philips narrowband (Spendex 40) and wideband (Spendex 50) secure voice terminals. The first document was a rather incomplete description, showing only one mode of the algorithm, a one-way function to update key variables, that does not have any critical Rule of Motion timing.

Already from that first document in the early 80s, it was clear to the engineers at Philips, that the structure of the algorithm was ideally suited for parallelization. One of the later documents indeed described a single clock pulse implementation, but that document arrived 5 years later.

Products that use SAVILLE
Below is a non-exhaustive list of devices that are known to support the SAVILLE algorithm.

  1. SAVILLE has algorithm ID 04 [1].

Companies that have implemented SAVILLE
SAVILLE was initially used and implemented exclusively by GCHQ and the NSA. Over the years, some manufacturers in allied countries were allowed to implement SAVILLE in their own devices. The following companies are known to have implemented SAVILLE in one or more products:


CFB   Cipher Feedback
A block cipher mode that enhanced ECB mode by chaining together blocks of cipher text it produces, and operating on plaintext segments of variable length, less than or equal to the block length.
CTAK   Cipher Text Auto-Key
Cryptographic logic that uses previous cipher text to generate a key stream. (Depricated terminology, superceeded by CFB)
ECB   Electronic Codebook
A block cipher mode in which a plaintext block is used directly as input to the encryption algorithm and the resultant output block is used directly as cipher text.
KAK   Key-auto-key
Cryptographic logic using a previous key to produce a key. (Depricated terminology, superceeded by OFB)
NATO   North Atlantic Treaty Organization
 More  Wikipedia  Website
NLNCSA   Netherlands National Communications Security Agency
Dutch: Nationaal Bureau voor de Verbindingsbeveiliging.  More
OFB   Output feedback
a block cipher mode that modifies ECB mode to operate on plaintext segments of variable length lesss than or equal to the block length.
SECAN   Military Committee Communications Security & Evaluation Agency (Washington)
  1. Wikipedia, SAVILLE
    Retrieved December 2011.

  2. L-3 Communications, unityCP leaflet
    Custom ASIC, High Performance Fixed and Programmable Crypto Engine.
    Cleared by DoD for public release under 05-S-1912 on 18 August 2005.
    Communication Systems East. 2 pages, April 2011.

  3. REDCOM, HDX-C Secure Converged Network module
    Retreived from REDCOM website, December 2011.

  4. Anonymous, Former Cryptographer
    Interview at Crypto Museum, December 2011.

  5. Anonymous, Former Security Expert
    Personal correspondence, April 2013.

  6. Wikipedia, De Bruijn sequence
    Retrieved May 2015.
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: Sunday 04 December 2011. Last changed: Wednesday, 12 June 2024 - 22:10 CET.
Click for homepage