Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
This is just a curious question, and it probably doesn't belong here anyway, and I'm just being bold asking it here.
80-bit used to be considered an adequate level of security, Skipjack and SHA1 were designed to be 80-bit-secure. But why 80 bits? Isn't 96 bits better because it's a multiple of 32 and gives a higher margin?
Does the choice of 80 bits have anything to do with the fact that the 8087 processor has a 80-bit floating-point register as part of the design?
Coprocessors are designed for improved performance in a certain case, and in the case of fixed-width mathematics, I do not believe you would see a performance increase.
I am quite sure that 80-bits is simply because it is 10, 8-bit words, and not that it is targeting the 80-bit registers in a FPU. Primarily, it would be inconvenient to use an FPU for this case due to the instruction layout. In the case of Skipjack or a Feistel network in general, I do not know of any easy way to do the block swap without pulling the words out of the FPU back to the CPU to do the swap because the FPU hardware is designed around mantissa functions, not shifts and XORs. You could use the FPU for intermediate storage, but because the x87 (this is particular case that is very x86 specific), you pull the 10-byte sequence from the stack, which would be more of a cost than just keeping it all in the integer unit.
Another note of security margins and Skipjack, it was designed for a minimally viable VLSI implementation. If you were going to put something on an IC circa 1996, you'd probably lean toward 80-bits over 88 or 96, or larger. MPEG-1, 2, 4 etc all had choices that were sub-optimal mathematically but the decoder ICs needed to be viable as a VLSI implementation. At meetings, this is always a constraint that comes up. At NIST 8114, we've had the discussions but I've never seen these discussions formalized. In power constrained computing, such as passively powered RFID, I still make engineering choices that are sub-optimal as far as ideal cryptography because bits cost money to make, power to use, and I don't have the luxury of increasing IC costs or power consumption. Encryption often takes a backseat to economics in the same way that security does to convenience.
The original SHA-1 and Skipjack specifications did not provide a justification for using a 80-bit key size, so we can only speculate about the reasons. However, it is important to understand that from a historical basis, an 80-bit key was considered adequate (barely) to be secure against exhaustive search for a few decades. It was clear that a 64-bit key size was not adequate, and a 128-bit keylength was more than needed. My own speculation is that 80 bits were chosen based on a calculation and extrapolation about how long a key was needed, to ensure a reasonable level of security against exhaustive keysearch for the next few decades.
The independent review of Skipjack is consistent with this viewpoint. Their executive summary states:
Under an assumption that the cost of processing power is halved every eighteen months, it will be 36 years before the cost of breaking SKIPJACK by exhaustive search will be equal to the cost of breaking DES today. Thus, there is no significant risk that SKIPJACK will be broken by exhaustive search in the next 30-40 years.
Source: SKIPJACK Review: Interim Report. Ernest F. Brickell, Dorothy E. Denning, Stephen T. Kent, David P. Maher, Walter Tuchman. July 28, 1993.
Why not a longer key? Well, there are two reasons:
A longer key (or security to greater than $2^{80}$ level) would leave you with a slower algorithm. For instance, SHA-1 would have been a lot slower if it had been designed to provide a 128-bit level of security, rather than a 80-bit level. Moreover, performance was a big deal at the time -- much more so than today. Developers routinely shied away from using cryptography because of fears over its performance impact. So, choosing an unnecessarily long keylength would have made the algorithm even slower, possibly leading to even less use of cryptography, which overall might have been worse for security. As a 80-bit level was considered adequate, there were good reasons not to make the algorithm slower than needed by seeking a longer key.
In the particular case of Skipjack, it also seems likely to me that the NSA did not choose a longer key length to avoid contributing to the spread of strong encryption. Remember that Skipjack was designed during the height of the crypto wars, when the NSA's policy was to limit spread of strong cryptography. Also, Skipjack was designed to be part of the Clipper key escrow initiative. I imagine the NSA expected that the Skipjack algorithm would become public, and they didn't want to share their best, strongest encryption technology with the world. Skipjack's design is interesting in that its key length is "baked into" the design of the cipher: it isn't obvious how to increase its key length, without losing its security properties, and multiple aspects of the cipher (the key length, the number of rounds, etc.) all appear to have been chosen carefully to provide exactly a $2^{80}$ level of security -- no more, and no less. So, the NSA might have chosen a 80-bit key as a key length that is adequate to support the purposes of the Clipper key escrow initiative (or to support commercial purposes), while at the same time being no longer than necessary (to avoid contributing to the proliferation of cryptography among the enemies they wanted to spy on).
Finally, I would like to point out that the conclusion of approximately 80-bit keys being (barely) adequate was by no means out of the mainstream. At the time, I think a 80-bit level of security was viewed by many as sufficient and a reasonable engineering choice. For instance, an analysis done Lenstra and Verheul about 10 years later recommended symmetric keys of 86 bits and hash functions of 172 bits, to achieve security until 2020; this was often summarized as 80 bits is about a sweet spot. See Selecting Cryptographic Key Sizes, Arjen K. Lenstra and Eric R. Verheul, J. Cryptology, vol 14, 2001, pp.255-293.
Skipjack rotates the text being encrypted by 16 bits each step, and cycles though the key 16 bits at a time. If the key length were not a multiple of 16, that would complicate software implementations. If the key length were a multiple of 64, every word of key would be used only when acting on a particular word in the block being encrypted. If the key were an odd multiple of 32 bits, then within each 32 bits of key, the first half would be used only with the first and third 16-bit chunks of each block, while the second half would be used only with the second and fourth.
Thus, reasonable choices for key length would be 48, 80, 112, or 144. Of those, 80 was considered the most practical. A key length of 48 would have been too short. While a 64-bit key might have been considered "enough" for the time, using a key that was exactly 64 bits would expose severe structural weaknesses. That leaves 80 bits as the smallest (and thus most convenient) key that would meet all requirements.
To get 80 bit security for a Hash function, you need a hash with output bitlength 160 bits due to the birthday problem and collision resistance. Note that $160=5\times 32.$
So, the 80 bits was convenient as security level for Hashes since they then equalled the existing idea of 80 bits as being a good security level for symmetric key at that time. The fact that AES was already 128 bits was due to inbuilt extra margins to survive well into the future.
