A Country of Which Nothing is Known but the Name.

If you came here via a search engine, you were probably looking for Pierre Cartier's wonderful mini-biography of the mathematician Alexander Grothendieck - from which I shamelessly stole the title. Please go straight there. Otherwise...

“And so no one, except for two people, enters the top floor of the Aedificium. ...”

The abbot smiled. “No one should. No one can. No one, even if he wished, would succeed. The library defends itself, immeasurable as the truth it houses, deceitful as the falsehood it preserves. A spiritual labyrinth, it is also a terrestrial labyrinth. You might enter and you might not emerge. And having said this, I would like you to conform to the rules of the abbey.”

“But you have not dismissed the possibility that Adelmo fell from one of the windows of the library. And how can I study his death if I do not see the place where the story of his death may have begun?”

“Brother William,” the abbot said, in a conciliatory tone; “a man who described my horse Brunellus without seeing him, and the death of Adelmo though knowing virtually nothing of it, will have no difficulty studying places to which he does not have access.”

Umberto Eco, "Name of the Rose"

In 1979, the American journalist Howard Morland fought - and won - a lengthy court battle for the right to publish a magazine article, "The H-Bomb Secret: To Know How is to Ask Why." Morland's objective was to infer and publish the basic facts of the famous Teller-Ulam hydrogen bomb design, drawing solely from unclassified sources.

Even a lackluster student of the 20th century ought to feel a little surprised: the article was indeed printed, and Morland even escaped with his life! Why the inquisitors relaxed their grip and turned the man loose, I cannot say. Perhaps his model of the H-Bomb's inner workings was sufficiently wrong, and was thought to be useful as disinformation. If this was indeed so, I should hope that what follows is equally wrong - and, like Morland, I will be permitted to continue sharing my crackpot ruminations with you, dear reader. Otherwise, to the gasenwagen I shall go, where I might perhaps meet with some of you!

So, dear inquisitor: nothing found below came from anywhere other than deathly-boring, public documents, placed on the Net by American public officials, merchants, and military historians.

While we're on the subject of disinformation: I find it intriguing that the supposed Snowden leak appears to consist entirely of minor operational details - of surveillance programs which have been known to the public, under various names, for some years! And likewise, neither the fact of the NSA supplying the world with diddled crypto - nor that of the American software industry's collusion with the agency really qualifies as "news."

So what would qualify as a genuinely-newsworthy NSA leak? Why, naturally, the crown jewels! These would conceivably be: facts - or at least, solid clues - shedding light on two great mysteries:

  1. What weaknesses in commonly-used ciphers, unknown to the public, are known to the world's favorite spy agency?
  2. What proprietary ciphers does the U.S. government reserve for its own use? And how do these differ from ciphers available to the public?

The "armchair general" community's endless speculations, well-founded and otherwise, seem to focus entirely on the first conundrum. Yet the second strikes me as considerably more interesting.

The NSA publishes two official lists of cryptographic algorithms approved for use by U.S. government employees, known as "Suite A" and "Suite B." Suite A consists of "classified algorithms that will not be released." Suite B contains well-known public favorites, ones commonly regarded as strong - such as AES.

All that is publicly known of Suite A ciphers is their names; a tantalizing "WinAmp Playlist" of monikers such as ACCORDION, BATON, JOSEKI, SAVILLE, SHILLELAGH, and a number of others.1 Truly, "a country of which nothing is known but the name!" Clearly it is impossible to learn anything meaningful regarding these marvels of mathematical engineering, without stealing national secrets and paying the price. Or is it?

The traditional "folk" explanation for the existence of Suite A is that the NSA (and the NATO military establishment it is part of) has advanced many decades beyond the public state of the cryptographic art2, and knows of certain weaknesses in popular cipher systems (including those found in Suite B.) The implication is that Suite A ciphers lack these weaknesses, and are therefore considered fit to protect the most valuable national secrets.

The folk explanation is simple and convenient, but the facts - as revealed by perfectly ordinary public (rather than leaked, or "leaked") documents 3, simply do not add up. Consider the case of the ViaSat KG-200 Inline Media Encyptor, "designed to conveniently fit between your computer’s motherboard and hard drive. In the event that a classified computer is lost, stolen, or tampered with, its hard drive remains encrypted so no classified information is compromised." 4 Notice anything peculiar? The cipher used in the KG-200 is: AES-256. Plain old AES, aka Rijndael, known to every computer programmer on the planet. Turns out that AES is approved for "Top Secret" use. ViaSat's other disk encryption products also rely on AES.

So, what products are advertised as including Suite A ciphers? It appears that the latter are found exclusively in equipment intended to secure voice and data traffic in the field. SAVILLE, for instance, is thought to have made its appearance in army field radios as early as the late Vietnam War era. It - along with some other Suite A ciphers - was shared with NATO members, including the UK and Norway, and was put to use in their own radio systems. BATON, a somewhat newer cipher, was - and continues to be - used in field radio equipment, such as the "Project-25" walkie-talkie issued to many public servants. 5 Other Suite A stream ciphers appear to serve similar purposes. VALLOR, for example, is said to be used in securing TTY broadcasts to submarines. 6 American military satellite uplinks are also known to use Suite A ciphers.

There is an apparent contradiction: if AES is judged fit to secure the hard disks of top bureaucrats, why is it placed only in radio sets issued to policemen, while those given to soldiers feature Suite A ciphers? The folk explanation would hold that Suite A algorithms are thought to be stronger. But if anything, a soldier's field radio is rather more likely than a policeman's walkie-talkie to fall into the hands of a hostile reverse-engineer. Military equipment is routinely taken as spoils, and often finds its way to the highest bidder.

One interesting clue is that U.S. military personnel are never permitted to generate their own cipher keys. The latter are always generated at an NSA facility, and are delivered to soldiers inside a "key fill device". At one point these made use of paper tape; now they live in a Windows CE (!) palmtop.

By my reckoning, a most logical way to generate keys for military field radios would be a portable hardware entropy source, which would be plugged into a gang of radios connected together for synchronization inside a shielded enclosure. Standing in a commander's tent. But instead, they choose to fly keys across the ocean... What might be the reason for taking this risk?

In his encyclopedic work, "Applied Cryptography" (1996) Bruce Schneier mentions "GOST", a Soviet block cipher having a curious design detail. The GOST specification did not specify a fixed set of values for the cipher's S-boxes. From this, one could infer that certain GOST users (perhaps the less loyal among the Warsaw Pact nations) were given weakened S-boxes so that they could be spied upon at the KGB's leisure. This, however, is a rather ham-handed approach to back-dooring a cipher, and American mathematicians surely conceived of something more subtle.

Some ciphers are known to possess "weak keys" - that is to say, a certain subset of the possible keyspace will result in ciphertext which can be cracked with considerably less effort than using plain brute force. Let's carry on with the "folk theory" and assume that NSA experts know of a class of weak AES keys, while having crafted Suite A algorithms which have strictly "linear" keyspaces. Yet AES is approved for certain "Top Secret" applications not involving radio communication. Given that all such applications use NSA-supplied key material, they would surely take care to supply only strong keys - or else, in the "KGB scenario," could easily supply weak keys to any public servant suspected of disloyalty. Which would leave the purpose of Suite A a mystery. The folk theory holds that NSA engages in mere "security by obscurity," hiding the proprietary ciphers in an effort to keep the public from discovering weaknesses. This sounds reasonable until you consider the official seal of approval on AES for "Top Secret" disks; while military radios are required to use Suite A ciphers.

So here comes the crackpot hypothesis, which resolves the apparent contradiction:

Suite A ciphers slowly leak keys.

NATO military doctrine famously allowed for the possibility that Soviet forces would overrun Western Europe, making liberal use of captured supplies of every kind. Even though such an invasion never took place, quite a few examples of American cipher equipment have been taken as spoils by various armies. Consider, for instance, the famous USS Pueblo: an American spy vessel taken prisoner by North Korea in 1968 - with a complete set of cipher machines, which the crew did not have a chance to throw overboard. Or the countless radios captured in Vietnam. 7

My theory: cryptographic equipment used by NATO armies leaks key bits into ciphertext. Slowly and subtly. Such that routine key swaps, at the rate supplied by the high command, prevent an enemy from gathering a complete key, even if he knew how. But if said enemy were to capture (and perhaps clone) NATO equipment, and take to using Suite A ciphers himself, he would begin to leak secrets meaningfully and continuously. It is also conceivable that NSA can supply keys which result in varying leakage rates, as appropriate to a particular military situation. And it is by no means certain that countries other than the U.S. possess the secret of extracting "dripping" keys.

  1. Interestingly, Wikipedia once featured considerably more discussion of the Suite A ciphers. Said discussion has mostly - but as you can see, not entirely - vanished. I imagine the remainder will probably disappear at some point. 
  2. This belief is not entirely unfounded
  3. Documents have been known to lie. But in this case we speak of spec sheets published by U.S. military contractors, and they - and the official statute regarding the suitability of AES for "Top Secret" use - would have to agree on the same lie. A difficult, though admittedly not impossible feat. 
  4. The fact of nothing remotely like the KG-200, despite the simplicity of the concept, being available to the public at large - at any price - should not be regarded as an accident. 
  5. See pg. 31 of the Daniels Electronics, Ltd. "P25 Radio Systems Training Guide." SAVILLE and BATON are valid algorithm identifiers, along with AES. The latter, interestingly, is the only cipher included in P25 devices issued to police agencies.
  6. Is VALLOR simply a proprietary moniker for the traditional One Time Pad? I know of no reason why a submarine commander would use anything else. 
  7. The timing does seem to coincide rather closely with the introduction of SAVILLE. 
This entry was written by Stanislav , posted on Wednesday October 16 2013 , filed under Cryptography, Distractions, Hot Air, Mathematics, ModestProposal, SoftwareArchaeology . Bookmark the permalink . Post a comment below or leave a trackback: Trackback URL.

7 Responses to “A Country of Which Nothing is Known but the Name.”

  • Daniel Muir says:

    A very, very interesting theory. However, as an armchair general myself, I feel I must advance an alternate explanation - code standardization. I am not crypotologist, but one of the major points and focuses of NATO as an organization is the standardization of military codes, ammunition, communications equipment, etc, so that all the member states of the defensive alliance can cooperate at a very close level. All their equipment - from the average rifle round upwards - 'talks to' each other, using a set of ordinances (public and classified) called STANAGs (Standardization Agreements).

    As such, I would suggest the idea that Suite A keys are not used because they are stronger encryption-wise, nor that they even necessarily leak information (although some codes and code generators might just do that - it's a nifty idea!), but rather because they are unique, obscure, and more importantly, they are standardized across all of NATO. A French radio using SAVILLE can receive a message from an American radio using SAVILLE, for instance. As for why I would suggest the reason as to why they have not simply moved to AES, it is most likely because AES is far younger than any of the codes they have been using, is commonly known (and so anyone who can find the passphrase automatically knows what format it should be in - who knows what exotic passphrase-juggling you might have to do in some high echelon military enciphering code), and so most of the Suite A crypto is both grandfathered in and kept because it is obscure as a result.

    That, and can you imagine the difficulty of getting every NATO member state to completely change their encryption all at once purely because the US secret service is using AES? 😉

  • Handle says:

    A fun theory, but the truth is much more banal and mundane and mostly related to intellectual property claims, proprietary information, and the need for standardization and interoperability, especially as we move to the Joint Information Environment construct. Daniel Muir is on the right track. Old NATO standards last forever and die hard.

    Suite A is just 'legacy' and an All-Suite-B world is the long-term goal for IA (which is why the effort team is called Suite A/B/I). That's why they're both good for TS+. All the Harris field radios (about a million of them I think) have finally all gone B within the past few years.

    We can talk more in person during the next meet up.

    • Stanislav says:

      Dear Handle,

      Seeing you comment on this piece is a pleasant surprise. But I'd hate to see you called on your boss's carpet; we all have to eat, after all.

      Yet another thought: if the U.S. government were to publish Suite A, it could score some very cheap "PR" points with private-sector cryptographers, among whom its reputation as "an honest broker" is perhaps at an all-time low.


      • Handle says:

        The first thing I try to learn is what won't bother my boss!

        There is, alas, still far too much A in the world to take advantage of the PR opportunity until it all depreciates. Also, the ownership of A is ... not perfectly unified yet. One day the PR will come, and by then few will remember or care.

        The Navy ... ugh. Do you know how long it takes just to update the fleet? Some systems are so hard to touch and change that they basically ... don't. They just let it work the way it was launched and wait until the vessel is decommissioned. Ships last ... a long time! You'd be appalled at what runs a submarine.

  • mysterian says:

    The ISS comm links on the American side are triple-DES encrypted although they may have switched over the AES by now (which Orion will be using). All the keys are NSA generated. On the Russian side the links are not encrypted at all.

  • Ajinkya says:

    Indeed Bing directed me here when I was looking for Pierre Cartier’s wonderful mini-biography of the mathematician Alexander Grothendieck

  • Josh Scholar says:

    I like it, but my first thought was:
    the top secret algorithms are probably WEAKER because they're older, and THAT'S why they're top secret. Security through obscurity.

    And they're still used through bureaucratic momentum and incompetence.

    I always remember Richard Feynman's stories about army safes during WWII that held top secret documents that had never had their combinations changed from the factory default - and that the army's response to him pointing out that most desks and safes hadn't had their combinations set was to circulate a memo saying that Richard Feynman was to be kept away from all desks.

Leave a Reply

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre lang="" line="" escaped="" highlight="">

MANDATORY: Please prove that you are human:

48 xor 116 = ?

What is the serial baud rate of the FG device ?

Answer the riddle correctly before clicking "Submit", or comment will NOT appear! Not in moderation queue, NOWHERE!