NIST goes public to keep federal secrets

| GCN STAFFFor more than two decades, the Data Encryption Standard and its cousin, Triple DES, have encrypted millions of government, commercial and personal messages.But when the National Institute of Standards and Technology gave DES a routine five-year checkup in 1996, the venerable standard showed its age.'It became pretty clear DES wasn't going to be standing forever,' said Edward A. Roback, chief of NIST's Computer Security Division.Advanced computing power made the relatively weak 56-bit key vulnerable. Triple DES' 168-bit key had an effective strength of just 112 bits under some kinds of attack, said William E. Burr, the division's manager of security technology.That's still pretty strong encryption, but Triple DES is awkward to use.'DES was never the most efficient beast to start with, especially implemented in software,' because the algorithm was designed to work through hardware, Roback said.'Software DES was tolerable, Triple DES is intolerable,' he said. 'We thought we could surely do better than Triple DES, if not on security then at least in speed and performance.'The NIST staff was cautious, however, about embarking on a search for a new encryption standard. DES had drawn considerable public criticism when the government adopted it in 1977. Originally developed by IBM Corp., DES was taken in-house by the National Security Agency for fine-tuning. Its 64-bit key was shortened to 56 bits, and suspicion arose that it had been fitted with a back door.The fears abated, but by 1996 NIST was embroiled in controversy about Clipper chip key escrow. The Clinton administration had proposed that the government hold keys to strong encryption products.A new standard needed to be chosen as publicly as possible to inspire confidence.'We worked really hard to consider the public perception of what we were doing,' said James Foti, a NIST mathematician.The cryptography industry, which had mistrusted the government's handling of DES, joined enthusiastically in selecting a new Advanced Encryption Standard. NIST received more than 1,400 pages of comment and analysis during the public evaluation periods.'A lot of those pages were from the best people in the field,' Burr said. 'It was assistance you couldn't buy,' Roback added.After choosing the Rijndael algorithm as the new standard last October, the NIST team received the Public Policy Award from RSA Security Inc. of Bedford, Mass., which had previously criticized government crypto policy and was itself an unsuccessful contender in the selection.When NIST solicited suggestions for the requirements for a new standard algorithm in January 1997, the team settled in for a long haul.'There is no quick way to prove an algorithm is secure,' Burr said. 'You have to give [hackers] a chance to try to break it.'By September 1997, the requirements were set. The new algorithm had to be royalty-free and support at least 128-, 192- and 256-bit keys with a 128-bit block. There were few algorithms using the larger block size'DES was just 56 bits'and that fact pushed the cryptographic envelope.Despite the fact that the winner would have to give the algorithm away for free, NIST received 21 submissions.'We had a very hectic summer of 1998,' Roback said.Of the 21 submissions, 15 met minimum requirements and were presented at a conference in August 1998. One was shot down in about five minutes by cryptographers in the audience, but at the end of the day the others were still standing to undergo further public analysis.Public comment ended in May 1999. The NIST team spent that summer evaluating the analysis. Submissions fell into three groups, Roback said: really good ones, those that were secure but had performance problems, 'and ones that were easy to grade' because they failed.By September 1999 the field had been whittled down to five finalists:A second workshop in April of last year brought the developers together with a critical audience.'We were getting down to the wire,' Roback said. 'In the end, we felt that all of them provided good security.'Rijndael was judged the most flexible performer over a range of platforms and implementations. It was the best performer in some areas, and 'it didn't have any places where it was particularly slow,' Burr said.The selection was announced last October. Rijndael became the proposed Federal Information Processing Standard in February. After any changes following the public comment period on the proposed FIPS, it will go to Commerce Secretary Donald Evans for approval.Major changes seem unlikely, Foti said, and any alterations will be 'mostly editorial in nature.'The race to have AES products evaluated has already begun.Vendors 'all want to be first,' Roback said. 'It's a change from the early 1990s and the crypto escapades' with the Clipper chip.Government agencies already are phasing out DES for anything except legacy systems. NIST intends AES to last at least 20 years, but for the foreseeable future it will coexist with Triple DES, and products using both standards will remain approved for government use.