Declassifying Skipjack

The NSA has declassified Fortezza. Specifically, they declassified
Skipjack (a symmetric block cipher) and KEA (a public-key key-exchange
algorithm). SHA-1 (hash function) and DSA (digital signature
algorithm) are also part of Fortezza, but they were already public. 

They didn't do this to help industry, or to help cryptographers, or to
help anyone. They did it to help themselves; they did it because they had
to cover for a mistake. 

DMS (Defense Messaging System) is a classified system for computer
messaging; e-mail, more or less. DMS uses Fortezza PCMCIA cards for
security. Since some of the Fortezza algorithms were classified, Fortezza
cards have all the physical controls and tamper-resistance features needed
to protect classified algorithms. 

Within the DMS protocols there is no way to have multiple cipher
suites. S/MIME, for example, defines multiple algorithm suites. There is a
flag in the S/MIME message that tells the recipient which algorithms were
used to encrypt that particular message. DMS has no such feature; only the
Fortezza algorithms work in DMS. 

The problem arose because the NSA couldn't install Fortezza cards and
readers fast enough. I don't know if they were too expensive (they are
expensive), if they couldn't ramp production up fast enough, or if
installing the infrastructure (PCMCIA card readers and etc.) was too big a
problem. I'm sure they counted on PCMCIA readers being ubiquitous in
computers. 

Whatever the cause, most people who needed to be on DMS did not have
working hardware. If they could set up an alternate algorithm suite within
DMS, then they could have released a software-only version with
unclassified algorithms: triple-DES, Diffie-Hellman, etc. Each endpoint
would know whether it was communicating with a Fortezza-enabled DMS system
or a software-only DMS system, and the problem would go away. But DMS
could not support this; it's Skipjack/KEA or nothing. So they had to
either turn off encryption, or put the classified algorithms into
software. 

Once you do that, you might as well declassify. The government's public
rationale is simply making a virtue out of necessity. 

So, what's Skipjack? 

Skipjack is a 64-bit symmetric block cipher with an 80-bit key. It was
used in the Clipper program, but it has not built-in key escrow. (Key
escrow was part of the key exchange mechanism, not the data
encryption.) It's a high-risk algorithm, meaning that there was a high
risk of compromise. Hence, the NSA is unlikely to put its most secret (or
clever) design elements in the algorithm. 

Its performance is good. Slower than Blowfish and some of the AES
submissions, it's still about twice as fast as DES on 32-bit
microprocessors. It's fast on smart cards, and efficient in hardware. It
also has no key setup time. If it weren't for the small 80-bit key, I'd
consider Skipjack for my own applications. 

Skipjack is interesting primarily for its design. This is the first
NSA-developed algorithm we've ever seen. Cryptography is an adversarial
science. Someone designs an algorithm; I break it. I design one; someone
else breaks it. This is how we learn. Skipjack is a good target; it is an
algorithm designed using secret methodologies by an organization we
respect. (Think of it as the cryptographic equivalent of a piece of alien
technology.) It's a worthy target. 

Skipjack is an unbalanced Feistel network (specifically, an incomplete
construction), but it is obviously a product of military
cryptography. Academic cryptography is mostly based on Feistel's work in
the mid-1970s at IBM: SP-networks and Feistel networks. Military
cryptography started with rotor machines, and then generalized into shift
registers. The block diagram and description of Skipjack clearly shows its
shift-register roots. I find it fascinating the that the two different
design paths are converging. 

The first thing you notice about Skipjack is its simplicity. There are few
design elements, and after some thought you can point to each one and
explain why it is there. There are no weird constants. There are 32
rounds, and 32 rounds can hide a lot of faults, but the design seems
sound. 

And very fragile. Some algorithms are strong because they are of a strong
type of algorithm. Similar algorithms will also be strong. Skipjack isn't
like that; it's a single strong algorithm around a sea of mediocrity. Make
almost any modification to Skipjack, even a small one, and the result can
be broken. I predict that the most interesting cryptanalysis work will
come cryptanalyzing Skipjack variants. 

People are already attempting to cryptanalyze Skipjack. Mostly we've seen
breaks of modified versions of the algorithm, together with explanations
of why the attack won't work against Skipjack itself. And Skipjack with
fewer rounds can be broken, but that's expected. 

And finally, Skipjack is not a submission to AES. It does not meet the
criteria. AES will be a 128-bit block cipher; Skipjack is a 64-bit
cipher. AES will support key lengths of 128-, 192-, and 256-bits; Skipjack
has an 80-bit key. I believe I can increase Skipjack's block size without
affecting security, but there is no obvious way to increase the key length
of the algorithm. 

Next month: KEA. 

http://csrc.nist.gov/encryption/skipjack-kea.htm 

Source code: ftp://ftp.funet.fi/pub/crypt/cryptography/symmetric/skipjack/