Subject: Electronic CIPHER, Issue 33, August 12, 1999 _/_/_/_/ _/_/_/ _/_/_/_/ _/ _/ _/_/_/_/ _/_/_/_/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/_/_/_/ _/_/_/_/ _/_/ _/_/_/_/ _/ _/ _/ _/ _/ _/ _/ _/ _/_/_/_/ _/_/_/ _/ _/ _/ _/_/_/_/ _/ _/ ==================================================================== Newsletter of the IEEE Computer Society's TC on Security and Privacy Electronic Issue 33 August 12, 1999 Paul Syverson, Editor Bob Bruen, Book Review Editor Hilarie Orman, Assoc. Editor Mary Ellen Zurko, Assoc. Editor Anish Mathuria, Reader's Guide ==================================================================== http://www.itd.nrl.navy.mil/ITD/5540/ieee/cipher/ Contents: [3380 lines total] Letter from the Editor Letter from the TC Chair Twelfth IEEE Computer Security Foundations Workshop o Pointers to program with URLs plus a writeup 2000 IEEE Symposium on Security and Privacy o Initial Call for Papers Security and Privacy News Briefs: o NIST Announces AES Finalists o LISTWATCH: Items from security-related lists, by Mary Ellen Zurko Highlights are from risks, dcsb, cypherpunks, tbtf, and CRYPTO-GRAM. Commentary and Opinion: Book Reviews by Bob Bruen o Kerberos A Network Authentication System by Brian Tung Conference Reports: o Advanced Encryption Standard Candidate Conference (AES2) by Morris Dworkin o IEEE Computer Security Foundations Workshop (CSFW12) by Scott Stoller o Forum for Incident Response and Security Teams (FIRST 99) by Cristina Serban o Workshop on Formal Methods and Security Protocols (FMSP 99) by Nevin Heintze New Interesting Links on the Web: IEEE CS Distinguished Visitors Program New Reports Available via FTP and WWW: Belgian Crypto Policy and Laws Who's Where: recent address changes Calls for Papers Reader's guide to recent security and privacy literature o Conference Papers o Journal and Newsletter articles o Books Calendar List of Computer Security Academic Positions, maintained by Cynthia Irvine Publications for Sale -- S&P and CSFW proceedings available TC officers Information for Subscribers and Contributors ____________________________________________________________________ Letter from the Editor ____________________________________________________________________ Dear Readers, We are pleased to bring you another issue of Cipher. Since the last issue the TC on Security and Privacy has had its Computer Security Foundations Workshop in Mordano, Italy. I would call it a rousing success, but my opinion is perhaps a bit biased. You will find a report of the goings on by Scott Stoller in this issue and a link to the program (including links to download the presented papers) on the Cipher home page. We also have several other conference reports plus our usual features, including the return of Mary Ellen Zurko's Listwatch column. Chuck Pfleeger is stepping down as chair of the TC. Thank you Chuck for a job well done. This issue includes a letter from our new chair, Tom Berson, which includes the resolution of the Oakland/Portland question regarding next year's Security and Privacy Symposium. For those of you who don't know the outcome, I won't spoil the surprise; you'll have to read Tom's letter for this and other TC news. Thanks as always to everyone who contributed. And, as always, if you have any contributions appropriate for the Cipher readership, please send them to us at cipher@itd.nrl.navy.mil. Paul Syverson Editor, Cipher ____________________________________________________________________ Letter from the Technical Committee Chair ____________________________________________________________________ Dear Friends, It was a real cliff-hanger. Those of you who attended our fantastic 20th Symposium on Security and Privacy (S&P) in May know that while that was thought to be our last meeting at the historic Claremont things were beginning to change under foot. The Claremont has new management yet again. The old new management wanted us out; the new new management bought us champagne. The new new management wanted to find a way to keep our meeting at the Claremont, or at least to get us back after one year in Portland. Oh, yes, we had signed a contract to have S&P 2000 in Portland, Oregon. Of course, we had never wanted to leave Oakland in the first place. A straw poll of members taken at the TC meeting confirmed overwhelming support for staying at or returning promptly to the Claremont. I decided that it would cause less disruption to the TC if we simply never went to Portland. There followed an awkward four-way negotiation: the TC (that's us), the IEEE Computer Society (which signs our contracts), the Portland Hilton, and the Claremont. We owe our thanks to everyone who participated in these protracted discussions: the leadership of the TC, the staff at the CS, employees of both the Hilton and the Claremont. Never mind the details; the contracted bottom line is this: S&P 2000, The Claremont, 15-17 May 2000, Hillside $133, Bayview $148 S&P 2001, The Claremont, 14-16 May 2001, Hillside $139, Bayview $155 S&P 2002, The Claremont, 13-15 May 2002, Hillside $153, Bayview $170 Those who work for The G will be happy to know that 10% of rooms will be available at the then prevailing government rate. Book early if you want this. ---------- July 1 was succession day in the TC. Chuck Pfleeger became Past Chair. Thank you Chuck for your stewardship of the TC during the past two years. I became Chair. Mike Reiter, who was elected to the post at the TC meeting in May, became Vice Chair. I am looking forward to working with Mike. I view that an important aspect of my job as TC Chair is to "answer the phone" for the TC, whether the call comes from a member or from outside. Feel free to let me know what is on your mind and to bring to my attention issues which you believe concern the TC. There is one exception to this invitation: I will consider it a tremendous kindness if, during my two-year term as Chair, you never talk to me about moving S&P from Oakland. I'm sure we can find more interesting things to do. Best, --Tom Berson berson@anagram.com ____________________________________________________________________ Twelfth IEEE Computer Security Foundations Workshop ____________________________________________________________________ Writeup is below. Program with URLs for presented papers is on the Cipher Web page. ____________________________________________________________________ 2000 IEEE Symposium on Security and Privacy ____________________________________________________________________ PRELIMINARY CALL FOR PAPERS 2000 IEEE Symposium on Security and Privacy May 14-17, 2000 The Claremont Resort Oakland, California, USA sponsored by IEEE Computer Society Technical Committee on Security and Privacy in cooperation with The International Association for Cryptologic Research (IACR) For twenty years, the IEEE Symposium on Security and Privacy has been the premier forum for the presentation of developments in computer security and electronic privacy, and for bringing together researchers and practitioners in the field. This year we plan to re-establish our emphasis on electronic privacy, while continuing to attract the most significant advances in all areas of computer security. Previously unpublished papers offering novel research contributions in any aspect of computer security or electronic privacy are solicited for submission to the 21st symposium. Papers may represent advances in the theory, design, implementation, analysis, or empirical evaluation of secure systems, either for general use or for specific application domains. Topics of interest include, but are not limited to, the following: Commercial and industrial security Electronic privacy Mobile code and agent security Distributed systems security Network security Anonymity Data integrity Access control and audit Information flow Security verification Viruses and other malicious code Security protocols Authentication Biometrics Smartcards Electronic commerce Intrusion detection Database security Language-based security Denial of service INSTRUCTIONS FOR PAPER SUBMISSIONS Submitted papers must not substantially overlap papers that have been published or that are simultaneously submitted to a journal or a conference with a proceedings. Papers should be at most 15 pages excluding the bibliography and well-marked appendices (using 11-point font, single column format, and reasonable margins on 8.5"x11" or A4 paper), and at most 25 pages total. Committee members are not required to read the appendices, and so the paper should be intelligible without them. Papers should be submitted in a form suitable for anonymous review: remove author names and affiliations from the title page, and avoid explicit self-referencing in the text. To submit a paper, send to reiter@research.bell-labs.com a plain ASCII text email containing the title and abstract of your paper, the authors' names, email and postal addresses, phone and fax numbers, and identification of the contact author. If any bibliographic citations were blinded from the paper for anonymous review, then include the full bibliographic citations in this email message. To the same message, attach your submission (as a MIME attachment) in PDF or portable postscript format. Do not send files formatted for word processing packages (e.g., Microsoft Word or WordPerfect files). Submissions received after the submission deadline or failing to conform to the guidelines above risk rejection without consideration of their merits. Where possible all further communications to authors will be via email. If for some reason you cannot conform to these submission guidelines, please contact the program chair at reiter@research.bell-labs.com. Paper submissions due: October 29, 1999 Acceptance notification: January 17, 2000 PANEL PROPOSALS The conference may include panel sessions addressing topics of interest to the computer security community. Proposals for panels should be no longer than five pages in length and should include possible panelists and an indication of which of those panelists have confirmed participation. Send an email with a MIME attachment containing your panel proposal in PDF or portable postscript format to the program chair at reiter@research.bell-labs.com. Do not send files formatted for word processing packages (e.g., Microsoft Word or WordPerfect files). This email should state that your proposal is for the 2000 IEEE Symposium on Security and Privacy, and should include the proposers' names, email and postal addresses, and phone and fax numbers. Panel proposals due: October 29, 1999 Acceptance notification: January 17, 2000 5-MINUTE TALKS A continuing feature of the symposium will be a session of 5-minute talks, where attendees can present preliminary research results or summaries of works published elsewhere. Printed abstracts of these talks will be distributed at the symposium. Abstracts for 5-minute talks should fit on one 8.5"x11" or A4 page, including the title and all author names and affiliations. Send an email with a MIME attachment containing your abstract in PDF or portable postscript format to the program chair at reiter@research.bell-labs.com. Do not send files formatted for word processing packages (e.g., Microsoft Word or WordPerfect files). This email should state that your abstract is for the session of 5-minute presentations at the 2000 IEEE Symposium on Security and Privacy, and should include the presenter's name, email and postal addresses, and phone and fax numbers. 5-minute abstracts due: March 13, 1999 Acceptance notification: March 31, 1999 General chair: Jonathan Millen (SRI International, USA) Vice chair: Li Gong (Sun Microsystems, USA) Program co-chairs: Michael Reiter (Bell Labs, USA) Roger Needham (Microsoft Research, UK) Treasurer: Brian Loe (Secure Computing Corporation, USA) Program committee: Paul Ammann (George Mason University, USA) Lee Badger (Network Associates, USA) Steven M. Bellovin (AT&T Labs-Research, USA) Dan Boneh (Stanford University, USA) Marc Dacier (IBM Zurich Research Laboratory, Switzerland) Robert Deng (Kent Ridge Digital Labs, Singapore) Ed Felten (Princeton University, USA) Virgil Gligor (University of Maryland, USA) Heather Hinton (Ryerson Polytechnic University, Canada) Audun Jxsang (Norwegian Institute of Science and Technology, Norway) Markus Kuhn (University of Cambridge, UK) Teresa Lunt (Xerox PARC, USA) John McHugh (CERT, USA) Phil Porras (SRI International, USA) Pierangela Samarati (University of Milan, Italy) Paul Syverson (Naval Research Lab, USA) Michael Waidner (IBM Zurich Research Laboratory, Switzerland) ____________________________________________________________________ SECURITY AND PRIVACY NEWS BRIEFS ____________________________________________________________________ _______________________________________________________________________ NIST Announces AES Finalists _______________________________________________________________________ Nearly two years ago NIST solicited candidates for AES, the Advanced Encryption Standard algorithm to serve as a successor to DES. A year ago, 15 candidates were submitted from 12 countries. On August 9, NIST announced the 5 finalists. These are MARS developed by IBM RC6 developed by RSA Labs Rjindael developed by Joan Daemen and Vincent Rijmen Serpent developed by Ross Anderson, Eli Biham, and Lars Knudsen Twofish developed by Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, and Niels Ferguson There is one more conference scheduled for evaluating the finalists next April. (See the writeup of the AES2 conference, which took place this past March, below.) Final determination of the standard is due in the summer of 2001. More on AES can be found at the official Web page http://csrc.nist.gov/encryption/aes/aes_home.htm _______________________________________________________________________ LISTWATCH: items from security-related mailing lists (August 02, 1999) by Mary Ellen Zurko (mzurko@iris.com) _______________________________________________________________________ This issue's highlights are from risks, dcsb, cypherpunks, tbtf, and crypto-gram. It's been stated that people would never tolerate their sneakers blowing up as regularly as their computer crashes. Well maybe not. From an NPR piece on high-tech toilets in Japan (which may have caused several fires): Reporter to woman shopping for toilet: "Are you concerned about the possibility of fires?" Woman (as translated): "No toilet is 100% safe. I am willing to accept some risk." An Asian Technology Information Program (ATIP) report (http://www.atip.or.jp/public/atip.reports.98/atip98.096.html ) states: "A German court recently decided to hold a bank liable for losses in connection with a stolen Eurocheque card in part because the 56-bit encryption protecting the card was considered "out-of-date and not safe enough." Two Canadian ISPs claimed they were subjected to denial of service attacks from the Chinese government because they host a web site for a religious group banned in China (http://www.wired.com/news/news/politics/story/21030.html). Services that provide anonymity unless faced with a subpoena may be relatively easy to crack open. An email article claims that to file a subpoena in a civil suit all you need is to get a lawyer (OK, that takes some money), file a lawsuit, and you have the authority to issue a subpoena (is it really that easy?). These subpoenas typically do not require a judge's OK. AOL and MSN has let users know about pending subpoena's, but it's not part of the terms of service. Yahoo has not. TrustE has been asked why it does not require this as part of its seal (which Yahoo has). TrustE made some standard mouth noises about looking into it. Erik Parker (eparker@mindsec.com) put out a call for reviews of security products for a "security product review section". It could be he's looking for some free labor, or it could be a chance for someone to increase their visibility. The Clinton administration plan for Federal Intrusion Detection Network (Fidnet) has caused some reactions. It calls for one system to monitor activities on nonmilitary Government networks (just which ones is currently unspecified) and a separate system to track networks used in crucial industries like banking, telecommunications and transportation. The plan is to be fully in place by 2003. Critics are concerned with misuse and the opening of new security holes. It's unclear what Fidnet does in the face of encrypted traffic and how information is protected (in fact much of the plan is still vague). The House Appropriations Committee approved a budget for the Justice Department that specifically forbids the FBI to spend any money on Fidnet (http://www.news.com/News/Item/Textonly/0,25,39978,00.html). In a wonderful attempt to coopt the privacy issue, White House national security adviser, Sandy Berger stated "Obviously we are very concerned about protecting privacy rights. But there is also a privacy right in not having hostile entities attack systems." E*Trade states that recent CA legislation (SB 1124) allows them to open accounts with electronic signatures (instead of requiring paper forms), so it plans to do so. Janet Reno has urged the German Justice Minister to ban crypto products on the Internet, including public domain items (http://jya.com/reno-ban.htm). A Risks contributor outlined in detail how he can use ActiveX controls shipped on his HP Pavilion computer that is running Windows 98 to break into it (http://www.tiac.net/users/smiths/acctroj/axcheck.htm). They are marked safe for scripting even though they can launch programs and read and write the registry. ActiveX signature checking happens only on download of the control; there is no related checking on execution. The solution seems to be to use a new feature called HTML applications (or .HTA files). They are locally trusted so do not have to be marked safe for scripting. The House armed services and intelligence committees are warning that widespread use of encryption technology would be "devastating" for US law enforcement and the national security establishment. A year-long study by a senior panel of Defense Department officials recommended an expansion in the role the reserves play in national defense, including the formation of a virtual cyberdefense unit to protect the nation's critical infrastructure. The new reserve cyberdefense unit "would consist of individuals with information technology skills who could perform their duties from dispersed locations rather than working as a single consolidated unit at a specific training center". The suggestions on how to staff this unit seemed less innovative, suggesting exchanging high-tech DoD training for years of service. I'd bet you'd need a pretty good clearance for any really interesting training. Paul L. Hutton ((425) 825-3450 - Voice, (425) 814-4254 - Fax) is looking for a "competent and trustworthy consultant" to reverse engineer and break a PBX encryption protocol as part of his product development efforts. http://privacy.net/analyze/ shows you how much information your web browser gives out about you. It's a pretty thorough job. [Biased editorial comment: So does Mike Reed's Snoop Server. You can find it and pointers to other privacy test sites, including the above at Onion Routing's List of Good Privacy Test Sites . --P.S.] Here's a full excerpt from Keith Dawson's TBTF on the SAFE bill, as Keith can always say it better than I can: ____________ ..Bill to relax crypto exports is gutted It's deja vu all over again Two years ago the most privacy-friendly attempt to relax US crypto export controls, Bob Goodlatte's SAFE bill, was savaged [1] in two House committees and was eventually withdrawn. I wrote at the time: > Justice Department backers have succeeded in shifting the > locus of debate so far in the direction of the Surveillance > Society that you can barely see the US Constitution from here. Goodlatte reintroduced SAFE in the current legislative session and succeeded in signing up a majority of Congress members, 258 in num- ber, to co-sponsor the bill. Perhaps you'd imagine that such support would give the bill an easy ride through Congressional committees? If so you'd be reckoning without the political hypocrisy that spawned the old saying "Pro is to con as progress is to Congress." (Thanks to Mike Barnett for the analogy.) SAFE had en- joyed majority sponsorship in 1997 too. On Wednesday 21 July the House Armed Services Committee voted 47 to 6 to replace the text of the SAFE bill with one drafted by the law- enforcement community [2], and manifesting exactly the opposite ef- fect. Here is the text of the new "unSAFE" bill [3] (PDF format, 47K). Eventually the House Rules Committee will need to decide which version of SAFE, if any, reaches the floor for a vote. Let's do an exercise in political accountability. 17 SAFE co-spon- sors sit on the Armed Services Committee, and 13 of them voted to gut the bill. (Note that even if all SAFE co-sponsors had voted to preserve the original bill, the outcome would have been the same, by a vote of 34 to 19.) I have updated the Congressional Hypocrites page [4], which first spotlighted the 285 politicians who voted cockeyed on matters of Internet pornography, to cast a cold light on the 13 members who both sponsored the SAFE bill and voted last Wednesday to ream it out. They are: * Andrews, Robert E. (D-NJ) [5] Brady, Robert (D-PA) * Chambliss, Saxby (R-GA) [6] Gibbons, Jim (R-NV) * Hansen, James V. (R-UT) [7] Hayes, Robin (D-NC) * Hilleary, Van (R-TN) [8] * Kasich, John R. (R-OH) [9] Kennedy, Patrick J. (D-RI) Maloney, James H. (D-CT) Riley, Bob (R-AL) Ryun, Jim (R-KS) Scarborough, Joe (R-FL) The five members marked with * are two-time losers -- they voted hypocritically on both Internet pornography and crypto export. I have caused their listings on [4] to stand out from the others in such a way as to obscure their party affiliations. On the subject of the Internet, these Congressmen have earned their denomination as charter members of the Hypocrites Party. Why not visit their Web sites [5] - [9] and express your opinion about their votes? It's a pity that we need to single out for special accolades that minority of Congress members who do what they say they are going to do; but such is our system. The four SAFE co-sponsors who voted against gutting the bill are: Bono, Mary (R-CA) [10] Meehan, Martin T. (D-MA) [11] Sanchez, Loretta (D-CA) [12] Smith, Adam (D-WA) [13] Thank you and congratulations, you hardy few, for voting your con- sciences. Why not visit their Web sites [10] - [13] and express your opinion about their votes? [1] http://tbtf.com/archive/1997-09-15.html#s01 [2] http://www.wired.com/news/print_version/politics/ story/20872.html?wnpg=all [3] http://www.house.gov/hasc/openingstatementsandpressreleases/ 106thcongress/99-07-21HR850markup.pdf [4] http://tbtf.com/resource/hypocrites.html [5] http://www.house.gov/andrews/ [6] http://www.house.gov/chambliss/ [7] http://www.house.gov/hansen/ [8] http://www.house.gov/hilleary/ [9] http://www.house.gov/kasich/ [10] http://www.house.gov/bono/ [11] http://www.house.gov/meehan/ [12] http://www.house.gov/sanchez/ [13] http://www.house.gov/adamsmith/ ____________ As part of related discussion of this issue, Dan Geer reminded us all to never, never take the classified briefing. "Once you have had the classified briefing, YOU, the recipient of same, can no longer talk about anything covered in said briefing with anyone not cleared regardless of whether you knew it some other way." Confinity's PayPal is an instant payment service that allows people to exchange money through their Palm organizers using infrared. The software is supposed to be ready for widespread use this fall. An analyst said: "If two people go out for dinner and decide to the split the tab, one person points their palm device at the other persons palm device and it's done. The money is passed. You're basically enabling the person to transmit money, and I think there's a niche for that." There was much speculation on the security challenges here, and Hellman is an investor. Lucky Green's announcement of S/MIME experiments associated with cypherpunks meetings inspired Bob Hettinga to accuse all X.5nn variants of being spawn of the devil and doomed to failure for their assumption of a centralized authority. Surprisingly, the discussion actually went uphill from there, including the actual and current deployment differences between X.5nn (or X.BlahBlah as it was less affectionately called) and PGP. The most striking technical difference is X.509's emphasis on signed certificates vs. PGP's use of signed keys. Having recent experience with implementing PKIX freeware (see our paper on Jonah at Usenix [http://www.usenix.org/events/sec99/]), I agree that the lack of information about keys such as key lifetime can sometimes be problematic. There was also discussion of the difficulty of managing revocation information in the X.5nn framework, and the popularity of S/MIME and X.5nn implementations ("Every man and his hamster are working on X.509 cert handling"). Several people claimed they had found it easy to translate keys from one format to the other in response to the accusation that DNs cause problems when working with X.5nn. The draft the Electronic Communications Bill in the UK would give electronic signatures legal status (http://www.the-times.co.uk/news/pages/tim/99/07/24/ timbizbiz01028.html?999). It would also force companies to register their encryption keys with a third party. The bill also makes it a crime for an employee who is aware of the "decryption notice" submitted by police to leak information about its existence. A Tory spokesman described the legislation as a "dog's breakfast" (because of its length). Rumor has it that travelocity.com's "secure" web server only supports 40 bit encryption, and that they have not responded to the customers who have complained about this weak security. An Federal Trade Commission workshop on the Federal Children's Online Privacy Protection Act caused a spate of privacy-related items. The Washington-based Center for Media Education did a study that involving a random sample of children's sites and the 80 most popular children's commercial Web sites. The random sample showed that while 95% of children's sites collect personally identifiable information, 73% of those post no privacy policies. Less than 6% attempt to get any permission from parents at all, and less than 3% use methods the center said it considers to be acceptable for obtaining verifiable and prior parental consent. 88% of the popular sites collect personal information from children, more than a quarter of those post no privacy policies. Less than 26% attempt to get any kind of parental permission, and not quite 13% use methods for obtaining verifiable, prior parental consent. Before the workshop, the FTC reported that privacy legislation was still unnecessary. A risks reader shared this excerpt from a privacy statement: Children 12 years of age and younger are not permitted to opt in for these future e-mailings because the opt-in software requires users to fill in their age and only users above 12 years of age are able to submit opt-in authorizations. Schneier's Crypto-Gram discussed three sites whose use of SSL is not airtight (onsale, Verisign and Spree), and another which claims to encrypt passwords but doesn't seem to use SSL or any other security protocol at all (BizTravel). The Secure Digital Music Initiative has released version 1.0 of their standard. This technology is supposed to end (or at least severely limit) music piracy (https://www.sdmi.org/dscgi/ds.py/Get/File-592/ pdwg99070802-Specification1.0.PDF). It lacks details but discusses the framework and goals. Systems that manipulate encrypted SDMI music are supposed to obey usage rules. Cryptography is also used for device authentication, which is supposed to stop non-SDMI devices from even downloading SDMI content. Software techniques are familiar from copy protection techniques. Some of the interesting hardware restrictions include degrading music that is played at high speed and limiting the bandwidth of recording music with a microphone and making it monaural. You can copy your music around to (ostensibly your) devices, but you can only have 3 copies "out" at any time. This seems to be an attempt to limit propagation to your two closest friends. Later they hope to implement a watermark that keeps music from being loaded if it has been compressed, as an attack on the MP3 format. This allows legacy CDs to be passed around at MP3 format and played on these devices forever. Saflink has opened what it says is the information technology (IT) industry's first biometrically enabled Web site - http://www.safbank.com. It simulates a typical Internet banking/brokerage site and requires users to present a biometric credential. At a glance, I didn't see any information on how to revoke your credential. There was much discussion about what IETF should do about DES. While it's being deprecated because of its weakness, TLS (the IETF version of SSL) is increasing security by upgrading from 40 bit crypto to DES. Many cypherpunks consider that to be an illusion of security, and worse than no security at all. Off lists, discussion continued at the July IETF meeting. 3DES is perceived as too slow for applications like IPSEC. Attendees were split between choosing an AES finalist, waiting for the AES winner[s], or moving to something else asap. An inordinate amount of cypherpunks bandwidth has been taken up by a gent who has published a book claiming Emily Dickinson encyphered the letters SamB (for Samuel Bowles) into many of her poems. He basically strips the poems of all other letters so that you can see how often those letters are sprinkled across the page. Visual patterns are said to emerge. Jim Gillogly, cypherpunk, seems to have been the first person outside the CIA to crack much of the cypher on a sculpture called Kryptos dedicated there in 1990 (http://www.nytimes.com/library/tech/99/06/biztech/articles/16code.html). ____________________________________________________________________ COMMENTARY AND OPINION ____________________________________________________________________ ____________________________________________________________________ Kerberos A Network Authentication System by Brian Tung. Addison-Wesley 1999. ISBN 0-201-37924-4 LoC TK5105.59.T86 164 pages. Index. Two appendices (Glossary & Annotated Bibliography) $19.95. Reviewed by Robert Bruen, Cipher Book Review Editor bruen@mit.edu ____________________________________________________________________ Kerberos is an important authentication software package developed at MIT, now at version 5. It is freely available over the net, but like most free software support does not come with it. If you want to use it you need to learn enough about it to install, use and maintain it - not to be undertaken lightly. The author, Brian Tung has a web page, The Moron's Guide to Kerberos, which has been available for a few years. There is also MIT's web site, several papers and RFCs but there does not appear to be a book on Kerberos, although most books on computer and network security have at least a section describing it. This book fills the void. The book is short and reads quickly, but there is still lots of information presented. It is a practical book that explains the rationale behind authentication making the distinction between it and authorization and other related security measures, then jumps right into how to use it. There is a brief discussion of the varieties of tickets that a user can get as well as why you need them. It always seems to confuse new users that one needs a ticket just to get the other tickets. There are examples of the important commands such as kinit (initialize user credentials), klist (list credentials) and kdestroy (destroy credentials). Beyond encrypting your telnet session and forwarding tickets, the lucky user is all set. Microsoft has decided to incorporate Kerberos into its products which will spread Kerberos far and wide. Tung briefly covers the interface to 95/NT. Just as briefly, he also covers the Eudora mail program's use of Kerberos. Microsoft still has some catching up to do with Kerberos to put their implementation on the level as the Unix versions, but at least they have started. He covers Windows 2000 at the very end of the book. The third chapter is written for admins: how to get Kerberos, unpack it, check the PGP signature, configure, build and install. For the average sysadmin this part is straight forward, although since the publication of the book, the steps have been modified by MIT, but only slightly. The trickier part is setting up the key distribution center (KDC). Tung points out the necessity of securing the machine that will be the home to the KDC with suggestions on to do it. The configuration files, maintaining principals and cross-realm authentication round out the rest of the chapter. The explanations are straightforward, but there is not much presented to help if something fails, but it all worked when I followed the instructions. The next chapter is about developing applications for Kerberos. It can be ignored unless you are a developer or want to learn more. The chapter is full of code fragments of declarations and function calls with a discussion of each. In addition to the Kerberos API is a short presentation of Generic Security Service API (GSS-API), which can be used by Kerberos, accompanied by code examples. The last several chapters discuss the origins of Kerberos, elementary crypto, more on how authentication works with Kerberos and the differences between version 4 and version 5 - an important topic if you are running version 4. This is small, inexpensive and helpful book that provides a great starting place for Kerberos with pointers to more information. If you are thinking about Kerberos, read this first, then think some more. Chances are improving that you will have to think about Kerberos sometime in the not too distant future. ______________________________________________________________________ Conference Reports ______________________________________________________________________ ______________________________________________________________________ Second Advanced Encryption Standard Candidate Conference (AES2) Rome, Italy March 22-23, 1999 by Morris Dworkin (NIST) ______________________________________________________________________ [This report will also appear in the July-August 1999 Issue of the NIST Journal of Research in HTML and PDF formats --P.S.] 1. Introduction On March 22-23, 1999, nearly two hundred members of the global cryptographic research community gathered in Rome, Italy for the Second Advanced Encryption Standard Candidate Conference (AES2). This report summarizes the conference presentations and accompanying discussions. AES2 was the second of three conferences sponsored by the National Institute of Standards and Technology (NIST) in its effort to develop a new encryption standard for the U.S. Government. There are fifteen candidate algorithms in Round 1 of the analysis period, out of which NIST will select about five finalists in the summer of 1999 for further evaluation in Round 2; the main purpose of the conference was to advise NIST in the selection of these finalists. The goal of this development process is to produce a Federal Information Processing Standard (FIPS) for an Advanced Encryption Standard (AES) specifying an Advanced Encryption Algorithm(s) (AEA), for use by the U.S. Government and, on a voluntary basis, by the private sector. According to NIST's formal call for algorithms, published on September 12, 1997: It is intended that the AES will specify an unclassified, publicly disclosed encryption algorithm available royalty-free worldwide that is capable of protecting sensitive government information well into the next century. [1] NIST requires the AES to be a symmetric key block cipher that (at a minimum) supports a block size of 128 bits and key sizes of 128, 192, and 256 bits. The AES is expected to succeed the Data Encryption Standard (DES), whose 56 bit key is becoming vulnerable to exhaustive search. NIST maintains an AES homepage at http://www.nist.gov/aes; see also [2] for a thorough discussion of the AES development process and a summary of the First AES Candidate Conference, including brief technical descriptions of the fifteen candidate algorithms. 2. Welcome and Overview William Wolfowicz, of the Fondazione Ugo Bordoni, and the European coordinator of the conference, briefly welcomed the participants to the meeting and to Rome. Miles Smid, the Acting Chief of the Computer Security Division of NIST's Information Technology Laboratory, spoke at greater length to open the proceedings. He began by expressing his satisfaction at the turnout (180 registered participants representing at least twenty-three countries) and the number of papers to be presented (twenty-one). He thanked the program committee for their work, and he said that all of the papers submitted to the conference would be available on the AES homepage. Smid then outlined the program. There were three general conference goals: to present Round 1 analysis of the AES candidates, to discuss relevant issues, and, especially, to provide NIST with a clearer understanding of which candidate algorithms should qualify for Round 2 and which should not. The three main issues to be addressed at the conference were security, efficiency, and flexibility; these were the main factors that NIST originally identified for evaluating the algorithms. In the area of security, there were talks on cryptanalysis, power analysis and related attacks, and the concept of ``minimal secure rounds.'' Some of the cryptanalytic attacks were already known, but they had not yet been presented formally at a conference. In the area of efficiency, there were several surveys comparing the candidates on various 8 bit, 32 bit, and 64 bit platforms. Two other issues that probably would be addressed were intellectual property and the possibility of selecting multiple winners for the AES. The conference was organized into seven sessions. On the first day, Sessions 1 and 2 were devoted to surveys; Sessions 3 and 4 covered smart card implementations and related attacks. In addition, Mr. Smid invited the attendees to submit proposals for short talks to give in the evening ``rump session.'' On the second day, cryptanalytic attacks were slated for Session 5, and algorithm observations for Session 6. Session 7 was devoted to algorithm submitter responses and to a discussion of issues, including audience questions. 3. Surveys (I) The chair of Session 1, Tom Berson of Anagram Labs, offered the audience some advice in listening to the upcoming presentations of survey results. He said that the authors would propose some criteria, perhaps explain their relevance, present a table of measurements against the criteria, and perhaps draw conclusions based on the data. He advised the audience to view the talks with an open mind but also with a healthy skepticism, bearing in mind the people who created the data, any agenda they might have, the relevance of their criteria, and any actions they advocated. The first speaker of the session was James Foti, a mathematician with NIST's Security Technology Group. He presented the results of the efficiency testing that NIST, in its formal call for algorithms, had indicated it would perform for Round 1. NIST had specified the following reference configuration: a Pentium Pro, 200 MHz, with 64 MB of RAM, running Windows95, using the ANSI C compiler in the Borland C++ Development Suite 5.0. Foti emphasized that these timings would be only part of the information that NIST would consider in choosing the finalists, and NIST did not necessarily expect its results to be the fastest possible on a 32 bit processor. Another caveat was that NIST used the submitters' C code, which probably varied in the degree of optimization. Foti explained the measurement techniques that NIST used in the timing program and the clock cycle program for its ANSI C testing. Then he presented timings of implementations on the reference configuration for encryption, decryption, and key setups. Only 128 bit keys were considered; larger key sizes would be tested in Round 2. He then compared these results with those of Brian Gladman and those of the Twofish team (which were scheduled to be presented as part of the same panel). Whereas NIST used the optimized code required in the AES submissions, Gladman wrote his own code, and the Twofish team used several sources. Although there were some discrepancies, which he discussed, the bottom line was that the three surveys shared the same set of five fastest algorithms: CRYPTON, MARS, RC6(TM), Rijndael, and Twofish. Also, among the five slowest algorithms in each of the three surveys were DEAL, LOKI97, and MAGENTA. Foti also indicated several other combinations of processors, operating systems, and compilers on which NIST had conducted tests of the submitted ANSI C code. Instead of presenting individual data on these, he presented averages of the results obtained from different compilers on two of the platforms. He also presented some results from NIST's ongoing testing of AES Java(TM) implementations, including static and dynamic memory as well as speed. The fastest algorithms there, in order, were Rijndael, MARS, CRYPTON, LOKI97, CAST256, and Twofish. Foti concluded by noting that similar groupings existed among different implementations of the algorithms on 32 bit processors; NIST would also need to look at performance figures on 8 bit platforms and on 64 bit processors, some of which would be presented later at the conference. For Round 2, NIST planned to test the larger key sizes, and to run the C code on 64 bit processors using compilers that generate 64 bit applications. In addition, NIST is considering the possibility of testing assembly language implementations. Brian Gladman was unable to attend AES2, so instead Berson read excerpts from his paper. Gladman had coded and implemented each of the candidates; the paper was intended to share his experience and to provide fair and accurate comparisons, not only in performance results, but also in the ease of implementation. For example, he discussed the form and character of the specifications, the degree of guidance given for implementation options and optimization opportunities, and the attention to byte order ``endianness.'' Berson recommended the paper. Bruce Schneier of Counterpane Systems spoke next, presenting the joint work of the Twofish team comparing the performance of the candidates in several settings: Pentium Pro/II, Pentium, DEC Alpha, 8 bit smart cards, and hardware. Before presenting their results in those areas, Schneier discussed the effect of larger key sizes on the performance of the candidates. He also offered two opinions on how to best compare and evaluate performance. First, he claimed that the AES would have to perform on all types of processor architectures, and that performance was more important on the ``low end.'' Second, he advocated comparisons in assembly language over C and Java, because applications where speed was important would be coded in assembly language . The first area of comparison was on 32 bit processors, specifically, the Pentium Pro/II and the Pentium. Schneier presented encryption timings and estimates, noting that the performance varied greatly, and that the performance of some algorithms depended heavily on the CPU. In particular, MARS and RC6 performed relatively better on the Pentium Pro/II, whose CPU supports fast 32 bit multiplication and variable bit rotations. For seven of the algorithms, the analysis was extended to include key setup; Rijndael and CRYPTON were the fastest algorithms for small blocks, although all of the speeds settled down pretty quickly. Along the same lines, Schneier compared the suitability of the candidates as hash functions. He presented results based on Biham's ``minimal secure variants'': Twofish and Rijndael became the fastest algorithms, although he did not necessarily endorse Biham's idea. In the area of 64 bit CPUs, the Twofish team estimated the performance of most of the algorithms on the DEC Alpha; the fastest algorithms, in order, were DFC, Rijndael, Twofish, and HPC. In the area of smart cards, the Twofish team concentrated on 8 bit processors. Schneier cautioned against comparing numbers in the various papers because the underlying assumptions varied. He asserted that memory usage was an essential consideration: DFC, E2, MARS, and RC6 could not realistically fit on small smart cards; FROG could not fit on any smart card. In the area of hardware, the Twofish team did not try to count gates; instead, they concentrated on context switching speeds. They cited CRYPTON as the most hardware-friendly algorithm; Rijndael and Twofish were also efficient in hardware. Schneier then summarized the findings for each individual algorithm, and invited the audience to draw its own conclusions. The last speaker of Session 1 was Alan Folmsbee of Sun Microsystems, Inc. There were three main components to his analysis. First, he presented his ``fracstel number,'' a measure he invented to try to normalize the concept of a round, and applied it to each candidate. Second, for each candidate, he determined the minimal number of rounds at which the avalanche was nearly ideal, in his estimation, and then measured the ``excess avalanche.'' Third, he presented some Java timings obtained from submitters' Java code run on a 200MHz UltraSPARC(TM), along with ROM measurements and RAM estimates; the six fastest candidates were MARS, RC6, E2, Serpent, HPC, and CRYPTON. He concluded with a personal recommendation of five finalists based on a weighted average of the rankings of the candidates in his various criteria. They were, in order, RC6, MARS, SAFER+, Serpent, and CRYPTON. 4. Surveys (II) Serge Vaudenay of the Ecole Normale Superieure-Centre National pour la Recherche Scientifique, the first speaker of Session 2, presented the DFC team's report on the candidates. He began with comments on the use of ANSI C in the reference configuration. Some usable instructions were restricted; the standard implementations of seven candidates did not turn out to be portable to SPARC(TM) or Alpha machines; and if a certain conversion was coded carefully, then the candidate unfairly incurred a performance penalty. He agreed with Schneier that it was better to compare the candidates in assembly language than in C. He also claimed that the Pentium Pro was outdated technology and that it would be better to compare the candidates on RISC 64 bit microprocessors like the Alpha. Vaudenay then presented the timing results of two colleagues: Granboulan's work on the Alpha and Noilhan's Java implementations on the UltraSparc-I(TM). On the Alpha, DFC was clearly the fastest algorithm, with HPC second, followed by Rijndael and Twofish, which were slightly faster than CRYPTON and MARS. For Java coding, RC6, Rijndael, MARS, HPC and Serpent were the fastest. In the remainder of the talk, Vaudenay commented on various algorithms against the following criteria: speed, origin of S-boxes, simplicity, portability, and the underlying research. He touted the theoretical design of DFC, which supplements a conservative design with a decorrelation module. He touched on the security of three algorithms: a class of weak keys in CRYPTON--- also noticed by Johan Borst; attacks on DEAL; and a preliminary, theoretical, statistical attack on reduced-round RC6. The four finalists he recommended were DFC, MARS, RC6, and Serpent. Craig Clapp of PictureTel Corporation, the second speaker of the session, considered the parallelism of seven of the candidates at the instruction level. There were two parts to his work: a theoretical analysis of the ``critical path,'' and a practical simulation of the algorithms' performance on a family of machines with a specified instruction set and from one to eight ``execution units.'' The results of the simulation matched the critical path analysis well. For up to three execution units, RC6 was the fastest algorithm; MARS, Rijndael, and Twofish had virtually identical performance. At more than four execution units, Rijndael was the fastest, followed, in order, by CRYPTON, RC6 and Twofish, MARS, E2, and Serpent. Clapp concluded that CRYPTON and Rijndael seemed to be the candidates best able to benefit from increasing instruction-level parallelism. Eli Biham of Technion spoke next on his method of normalizing the speed comparisons of the algorithms for security. His underlying observation was that NIST had not specified a relation between strength and speed, and so there were varying security margins among the candidates. Serpent, for example, with 32 rounds, had a large margin of security, since the designers believed 16 rounds to be secure; other algorithms had smaller margins, adding just a few rounds to the minimal number at which the algorithm was believed secure from attacks stronger than exhaustive search. He proposed a ``fair speed/security'' comparison, in which the algorithms would be evaluated at two passes more than these minimal secure variants. He claimed that under this model, the fastest candidates, in order, were Twofish, Serpent, MARS, Rijndael, and CRYPTON. Here are some of the questions that the audience posed to Biham. Was it fair to add two extra passes since that could represent different margins of security for different algorithms? Biham acknowledged the difficulty, noting that it was impossible to add fractional rounds, and inviting others to vary his scheme. How did he arrive at his estimate that there was an attack on CAST- 256 reduced to 32 rounds? Biham thought there was something to that effect in the CAST-256 submission paper, but he admitted that he could be mistaken; however, he did personally know of attacks that break CAST-256 with more than 20 rounds. Was he thinking of publishing them? Yes, he might, now that he knew that they were the best results. Why did he not perform the adjustments on the best available timings instead of timings that seemed to favor Serpent? Biham responded that he had merely used timings from his own computer; he invited others to base a comparison on Gladman's timings. Did Biham advocate that the number of rounds should be a changeable parameter? Not necessarily, but as it stood, it was like comparing apples with oranges: some algorithms were designed more for speed and others more for security. To close the session, Foti spoke again to report on NIST's Round 1 randomness testing. In addition to performing its own statistical tests, NIST used the Crypt-XB, and DIEHARD statistical packages. He explained how the tests were conducted and presented the empirical results. As expected, output of all of the algorithms looked random; no statistically significant results were discovered. In the future, NIST planned to conduct analysis on the larger key sizes and possibly on reduced round versions. 5. Smart Cards: Implementations and Related Attacks Session 3 consisted of two partial surveys of smart card implementations. Francois Koeune spoke first about the work of the Cryptography Group at the Universite Catholique de Louvain. They performed implementations of E2, RC6, Rijndael, and Twofish on emulators of two different smart cards: the Intel 8051 and the ARM. The former was a basic, low-cost, 8 bit smart card, and the latter was sophisticated and advanced, with a 32 bit processor. Koeune explained some of the implementation decisions; for example, they gave RAM usage priority over speed. E2 performed the slowest and used the most RAM on both smart cards, more than was available on the 8051. Rijndael used the least RAM on both smart cards and also performed the fastest. Twofish was the second fastest on the 8051, and required relatively little RAM on both smart cards, while RC6 was the second fastest on the ARM. Work on MARS and Serpent was in progress. Geoffrey Keating presented a survey of several candidates on the Motorola 6805 series 8 bit architecture, allowing a maximum of 120 bytes of RAM, which he considered to be generous, and 1024 bytes of ROM. He quoted published results for Twofish, and he implemented ``constant-time'' simulations of five other candidates himself; he also looked at E2 and CAST256. He presented and discussed his findings [3], updating those in the published proceedings. Rijndael was the fastest, followed, in order, by Twofish, CRYPTON, Serpent, RC6, and MARS. MARS exceeded available ROM significantly, as would CAST-256; RC6 exceeded RAM limits. Session 4 consisted of three talks on implementation attacks. Before presenting the first paper of the session, Adi Shamir of the Weizmann Institute of Science addressed one of the questions that arose after Biham's talk: should the number of rounds be changeable? Shamir proposed that NIST postpone any changes in the number of rounds of the algorithms until Round 2; then, in consultation with the submitters of the finalists, specify a different number of rounds for each key size. The guideline would be to use a couple of rounds more than the minimal secure rounds for 128 bit keys, to use twice as many rounds for the 256 bit keys, and to use an intermediate number of rounds for 192 bit keys. Shamir then presented his and Biham's paper on power analysis. He stressed the practical importance of implementation attacks, since the eventual AES winner was likely to be very secure against classical attacks. The general idea, due to Kocher [4], was to measure and analyze the power consumption of a smart card to reveal the key. In Shamir's variant, the power consumed by writing subkey bytes into RAM gives a measure of their Hamming weights. In DES, for example, such measurements would yield 96 noisy equations in the 56 bits of the user key, which in principle would be more than sufficient to calculate it. This variant of power analysis was important because it focused directly on the key schedule of a cipher, independent of the plaintext, ciphertext, protocol, and implementation details. Shamir discussed examples of potentially dangerous instructions in the key scheduling of the AES candidates. In the question-and-answer period after the talk, Shamir was asked about the resistance of the AES candidates to the attack; he asserted that a few were vulnerable, but hesitated to assert that any were not vulnerable. Schneier commented that implementation attacks were best resisted at the level of hardware or protocols; Shamir agreed, although the hardware defenses he had seen were problematic too. The next speaker, Joan Daemen of Proton World, presented his and Rijmen's survey of the candidates' resistance to timing attacks, simple power analysis, and differential power analysis. He discussed the impact of various operations in resisting these attacks: storing and loading registers, rotations and shifts, bitwise Boolean operations, and arithmetic operations. He also discussed possible countermeasures. In his conclusion, he classified the candidates in three ways. CAST-256, DFC, E2, HPC, MARS, and RC6 were problematic because they used multiplication and/or variable rotations. FROG, LOKI97, SAFER+, and Twofish were doubtful because they used addition and/or subtraction. CRYPTON, DEAL, MAGENTA, Rijndael, and Serpent were favorable because they did not use arithmetic operations or variable rotations. Pankaj Rohatgi, the last speaker of the session, presented the work of a team of cryptographers, statisticians, hardware experts, and smart card experts at IBM's T.J. Watson Research Center. The main conclusion was that NIST's flexibility criterion for ``secure and efficient'' implementations was very hard to achieve on smart cards because of an inherent susceptibility to physical attacks like Kocher's differential power analysis. For example, the team was able to obtain the whitening subkeys of Twofish using only 50 power samples from a straightforward implementation on a ST16 smart card. Rohatgi estimated that, under their attack model, all the candidates were vulnerable, although some more than others. In particular, FROG and HPC would be the least easy to attack, and that CAST-256, DFC, E2, MARS, and RC6 would be less easy to attack than the remaining eight algorithms. He presented some possible countermeasures and their associated overhead. He recommended that NIST revisit one of their selection criteria: smart card performance should either be dropped, or it should only be compared on power analysis resistant implementations, which would probably require advanced smart card platforms. 6. Rump Session Several attendees gave short talks for the rump session, which was held on the first evening. Smid spoke first on behalf of Don Johnson of Certicom, who could not attend the conference. Johnson contended that the AES ought to specify multiple algorithms in order to ensure its future resiliency: if one algorithm was found to have a fatal flaw, then another one would be readily available. Ross Anderson of Cambridge University spoke about the security of smart card implementations against both invasive and non-invasive attacks. Although hardware protection might be possible, the cryptographic research community was only seeing the tip of the iceberg. He proposed that the AES finalists should be implemented in hardware in order to evaluate their resistance to such attacks. Orr Dunkelman of Technion spoke about the security of Serpent-p and Serpent-p-ns (two variants of Serpent with a weaker linear transformation) against linear cryptanalysis, differential cryptanalysis, and impossible differential cryptanalysis. Ian Harvey of nCipher Corporation Limited presented a class of implementation attack applied to DFC. Kazumaro Aoki of Nippon Telegraph and Telephone (NTT) Laboratories spoke about the performance of E2. He disagreed with NIST's Java test data, asserting that the impact of the NIST API on the encryption performance in NIST's timings was not negligible. He presented new optimization methods for E2, and he presented a performance comparison on a Pentium II in which the five fastest candidates were RC6, Twofish, Rijndael, E2, and MARS. He urged the use of the latest results. Shamir addressed a question that arose during his earlier talk, explaining how the timing of implementation details could impact security. Schneier commented on Biham's idea for minimal secure round variants. He agreed that the notion of a ``conservativeness'' measure was a good one, but both the strength of the valid attacks and the measures of safety needed to be carefully defined. Shiho Moriai of NTT Laboratories presented a measure of the randomness of three structures in the candidates: Feistel structure, MARS-like, and CAST-256-like. Johan Borst of K.U. Leuven spoke on weak keys of CRYPTON, the subject of an official comment that he submitted as an official comment in August, 1998; he also acknowledged later contributions by Vaudenay, Wagner, and their teams. These results made CRYPTON unsuitable for use in hashing. Doug Whiting of Hi/fn, Inc. presented performance comparisons of RC6, Rijndael, Serpent, and Twofish on Merced. Niels Ferguson of Counterpane Systems recommended an emergency mode for AES, in which the number of rounds would double, instead of choosing multiple algorithms. Takeshi Shimoyama of FUJITSU Labs Ltd. spoke about the security of Serpent's S-boxes against higher order differential attacks, disputing the claim in Serpent's documentation that all of its S- boxes have nonlinear order 3. David Wagner of the University of California Berkeley explained how HPC's lossy key- expansion made it easy to find equivalent keys, so that HPC was unsuitable for use in hashing. Ron Rivest of the MIT Laboratory for Computer Science presented a possible alternative key schedule for RC6 that could be calculated forwards and backwards on the fly. He claimed that RC6 was modular in that the key schedule could be considered separately from encryption. Chae Hoon Lim of Future Systems, Inc. presented a hardware architecture design of CRYPTON version 1.0, a revision of the original submission. He discussed the design decisions and results. Schneier spoke against the idea of multiple algorithms in the AES, arguing that it would mean higher costs, especially in hardware, and, in some respects, less security. He would even prefer that Twofish not be chosen at all, rather than having it included in a suite of multiple algorithms. Gary Graunke of Intel spoke on critical path opcode analysis, comparing ideal AES times to observed times. Carl Ellison of Intel presented a humorous new metric for comparing the algorithms. 7. Announcement of the Third AES Conference Before Session 5, Smid thanked the organizers of the Fast Software Encryption Workshop 1999 (FSE6) for allowing NIST to hold the AES conference during the same week at the same venue. He announced that the next AES conference would be coordinated with FSE7 in New York City in April 2000. 8. Cryptanalysis Session 5 was devoted to cryptanalysis of the candidates. Sean Murphy of the University of London presented his and Mirza's paper on two properties of the key schedule of Twofish, focusing on the 128 bit key case. First, not all pre-whitening subkeys could occur. Murphy said that the Twofish team had further results: the distribution of subkeys was slightly less uniform than he predicted in his paper [5]. Second, Twofish could be considered as a collection of 2^64 versions of ``reduced Twofish,'' in which the round functions are fixed by the selection of one of the possible pairs of key-dependent S-boxes. Because the subkey generation of reduced Twofish was unbalanced, guessing the S-boxes would yield an attacker a slight amount of information, contrary to a claim in the Twofish submission. This raised the possibility that the imbalance could be exploited for some key classes, which would constitute a divide-and-conquer attack on those classes. John Kelsey of Counterpane Systems then presented joint work with Schneier and Wagner on weaknesses in the large key size versions of SAFER+. The underlying weakness was the poor key diffusion in the key schedule; in other words, it took several rounds before changing certain key bits would affect the cipher. He described two attacks of academic interest on the 256 bit key version. The first was a meet-in-the-middle attack requiring 2^240 work, 12 x 2^24 bytes of memory, and 3 texts. Besides the poor diffusion, this attack also exploited a property of the linear transformation in the round function. The second was a related-key attack requiring 2^200 work and 3 x 2^32 chosen texts under each of two related keys. Neither attack was practical; nevertheless, Kelsey suggested improvements in the key schedule for the larger key sizes that eliminated the poor key diffusion. Vincent Rijmen of the University of Bergen presented joint work with Knudsen on the security of LOKI97. He explained how certain weaknesses could be exploited in differential and linear attacks. There were several two-round iterative differentials based on the non-invertibility of the S-boxes and the invariance, under modular addition of subkeys, of input pairs that differed only in the most significant bit. The probability of the best 15-round characteristic was 2^-56, and this would be compounded by resynchronization; 2^56 chosen plaintexts should suffice for an attack. The linear attack exploited the correlation of the least significant bits of the inputs and outputs under modular addition, as well as the imbalance in the S-boxes used in the second layer of the round function. The probabilities of the two best 15-round linear approximations that they found were 2^-22 and 2^-29, for 2^-14 and 2^-7 of the keys, respectively. Wagner presented joint work with Ferguson and Schneier on a weak class of keys in FROG. There were two underlying observations. First, FROG's S-boxes and internal wiring depended on the key, so the quality of diffusion did as well. Second, the diffusion was much worse in the reverse direction than in the forward direction. They exploited these properties in a differential attack using 2^36 chosen ciphertexts on 2^-56 of the keyspace. Wagner acknowledged an error in their paper: they had claimed that it would be easy to recover the entire S-box when, in fact, only about half of the S-box yielded easily; however, they still suspected that with more work it would probably be possible to recover the full S-box. He also discussed a dual linear attack. In response to a question from Dianelos Georgoudis, the submitter of FROG, Wagner said that there was probably a quick fix to eliminate this particular weak class, but he would not be confident that there were no other such classes. In the last talk of the session, Biham presented results on MAGENTA that he had written at the first AES conference with several other attendees. They mounted a simple attack exploiting the symmetry of the key schedule. For the 128-bit key version, the attack required 2^64 chosen plaintexts and 2^64 steps of analysis; alternatively, it could be converted to an attack with 233 known plaintexts and 2^97 steps of analysis. The same attacks on the larger key sizes resulted in the same reduction of complexity over exhaustive search. 9. Algorithm Observations Session 6 was devoted to observations on individual algorithms. Jacques Stern of the Ecole Normale Superieure advocated DFC on behalf of its design team. He highlighted the ``provable security'' features, which protected against certain delimited attacks, under the assumption that the subkeys behaved randomly. He also assumed that the conservative design for the confusion permutation protected against other attacks. He backed up both of these assumptions with two specific security ``challenges.'' He also highlighted DFC's performance on 64 bit architectures, which he called ``tomorrow's architecture,'' and on which DFC was the fastest candidate. He explained how candidate comparisons that used the Pentium Pro or ANSI-C unfairly penalized DFC. He cited other implementations to make the case that DFC was not in the trailing group of candidates for speed. He addressed Coppersmith's weak keys: they only occurred with probability 2^-128, and a slight modification in the key schedule would fix the problem. Kazukuni Kobara of IIS Tokyo University presented a very technical paper, ``Pseudorandomness and Maximum Average of Differential Probability of Block Ciphers with SPN-Structures like E2,'' on behalf of Makoto Sugita. The conclusion was that the linear transformation in E2 provided good pseudorandomness and good immunity against differential attacks. James Massey of Cylink Corporation spoke next on the linear transformation of SAFER+. He explained how it provided diffusion that was optimal among a certain class of transformations that lent themselves to fast implementations, called ``multi-dimensional 2-point transform diffusers.'' He also reported that both software and hardware implementations of SAFER+ had been improved significantly; details were available at the SAFER+ Forum at the AES homepage. Scott Contini of RSA Laboratories presented joint work with Yin on the operation of data- dependent rotations, which were used in MARS and RC6. They conducted an extended analysis of how input differences in the rotation amount affected data-dependent rotations. Their results confirmed the intuition that such differences provide a fast avalanche of change. He concluded that MARS and RC6 appeared to resist differential cryptanalysis. Whiting spoke next on behalf of the Twofish team with new findings on the security and efficiency of their algorithm. He began by briefly addressing the two security issues that Murphy had raised in his talk that morning, referring the audience to the paper on their website for a thorough discussion [5]. First, they calculated that the entropy of the whitening subkeys was 117 out of 128 bits, which was even less than Murphy conjectured; however, that was not significant, because only 64 bits were needed to mask the input to the S-boxes in the first round, as in RC6, for example. Second, they empirically estimated from smaller cases that, for a given choice of S- boxes, the entropy of the subkeys was 63.2 bits out of 64 bits. Whiting claimed that this was also not a significant security concern; DES, for example, lost 4 bits of entropy per round in an analogous situation. Whiting then summarized the results in their conference paper. They had empirically verified some uniqueness properties of the Twofish keys; for example, no two distinct user keys produce an identical sequence of subkeys. He also explained the results of their effort to derive an upper bound on the probability of a differential characteristic. But most of his talk focused on implementations of Twofish in various settings. There were speed improvements in the fastest assembly language implementations of Twofish. Whiting also presented results that illustrated the performance flexibility for which Twofish was designed: not only encryption speed versus key setup speed, but also RAM versus key setup speed. There were similar tradeoffs in hardware, including a new hardware implementation that used only 8000 gates. 10. Algorithm Submitter Rebuttals and Discussion Smid moderated Session 7, the last session of the conference. The algorithm submitters sat as a panel; every algorithm except HPC and LOKI97 was represented. Individual submitters had an opportunity to speak for a few minutes, followed by an update from Smid on the intellectual property situation of the algorithms. Then the attendees participated in an open discussion of various issues. Six submitters delivered statements. Massey presented a revised, ``unified'' key schedule for SAFER+ that addressed the weaknesses in the two larger key sizes, while reducing to the original key schedule in the 128 bit case. Klaus Huber of Deutsche Telekom AG spoke on behalf of MAGENTA. He asserted that criticisms of MAGENTA were exaggerated and sometimes incorrect; for example he disputed the assertion in the survey of the candidates by the Twofish team that it would be hard to implement MAGENTA in hardware faster than 180 megabytes per second. He advocated several aspects of MAGENTA. The key schedule weakness could be easily eliminated. MAGENTA was one of the top candidates in memory usage, resistance to implementation attacks, and key setup. It was very fast in hardware, and its software performance could be improved with the use of 16 bit tables. Last, its design was clear and compact. In response to a question from the audience, Huber said he was in the process of selecting one of several possibilities for a new key schedule. Carlisle Adams of Entrust Technologies spoke about CAST-256. He asserted that it appeared to be secure at 48 rounds; the best attacks of which he was aware were on 16 and 20 round versions. He said that some people had suggested that since there were not many results in the area of the first selection criterion, security, the next criteria ought to be comparisons of performance, code size, memory requirements, etc. Adams disagreed: the second criterion also ought to be security, in particular, the security history of any predecessors of the candidates. He traced the six years of history of the three iterations of CAST, none of which had been broken. CAST-256 used the same round function that had already been well studied; the two modifications were the key schedule and the extended Feistel framework. Adams argued that it was much more manageable to evaluate the security of those two modifications than to examine every detail of a brand new cipher. He also discussed the issue of performance. CAST-256 fell quite comfortably in the middle of the pack, only 2 to 5 times worse than the fastest candidates, which would not be noticeable in many common environments. He suggested that in the AES process, solid performance in every environment was desirable. Lim commented on CRYPTON. First, he pointed out that it featured a two step key generation procedure to facilitate low-level implementations: expansion into an extended key, and then the generation of round subkeys. In smart card implementations, the expansion could be performed just once, and the extended key could be stored, making irrelevant a certain power analysis attack. He asserted that several of the survey papers inflated the key setup time for CRYPTON; in fact, it was faster than one encryption in almost every architecture. He urged the use of his figures for comparison. Last, he pointed out that the motivation for Vaudenay's differential and linear attacks had already been considered in the original CRYPTON documentation. A submitter of RC6, Matt Robshaw of RSA Laboratories, spoke next. He wanted to raise the issue of cross-compiler timings; he hoped that there would be a discussion on how to compare the candidates fairly across different compilers. He questioned NIST's Java timings for RC6, and also E2; those of Folmsbee and Vaudenay were more in line with their expectations. He also presented a ranking of the minimal secure variants of the algorithms that was based on NIST's timings, as quoted by Schneier; unlike Biham's ranking, the ``usual suspects'' came out on top. A submitter of E2, Kazuo Ohta of NTT, also questioned NIST's Java timings; he referred the audience to a conference handout for NTT's results. Smid then updated the audience on the intellectual property (IP) statements of the candidates. The IP goal was for AES to be available royalty-free worldwide. Although the submitters had agreed to give up their own IP rights if their algorithm was chosen for the AES, NIST was concerned that submitters whose algorithms were not chosen might claim that a winner infringed their IP. NIST informally polled the submitters on this question; the submitters that agreed to waive their IP rights on the winner without qualification were CAST-256, CRYPTON, DEAL, FROG, LOKI97, Rijndael, Serpent, and Twofish. MAGENTA had not responded until the conference, when Huber said he could not speak for the position of Deutsche Telekom, which held patents on the fast Fourier transform. Smid presented slides with the responses of the other candidates, who had appeared to qualify their responses in some way, for example, by seeking recognition for their ideas. Smid invited the submitters to clarify their responses, and opened the floor for discussion. Someone pointed out that IBM's response appeared to waive the exercise of its MARS patent but not any of IBM's other patents. An attendee from IBM explained that they were concerned that the wording of NIST's poll question could be interpreted to cover any actions of the users of the AES, not just the use of the AES itself; Massey said that Cylink Corporation shared this concern. Other attendees raised the concern of possible IP claims from non-submitters. Smid responded that he was not sure if it was possible to avoid them, beyond trying to conduct a good patent search. Nevertheless, he repeated his request from the first AES conference: any IP claims on any of the candidate algorithms should be brought to NIST's attention. A few other issues were discussed. There was not a clear consensus on whether the AES should specify multiple algorithms. The original idea in Johnson's paper was that diversity increased security; Smid pointed out that multiple algorithms also would be a kind of insurance against IP disputes. Someone suggested that, in light of the threat of implementation attacks, it might be appropriate to have performance diversity in the standard: one algorithm for smart card environments and another for protected environments. This idea met with some objection, however: for example, it might unfairly penalize submitters who had taken the effort to design algorithms with the requisite flexibility. Another attendee recommended that, whether or not multiple algorithms were selected, AES protocols should support an eventual change from 128 bit keys to 192 bit keys; moreover, constant-time implementations across the key sizes would be desirable to minimize the impact of that change. This sparked the observation that, absent a performance penalty for larger key sizes, there was little incentive to use smaller key sizes. The observation that requiring multiple algorithms would increase costs---although not so much in modern toolkits, it was later pointed out---sparked a discussion of whether AES needed to fit at all on low end smart cards. On the one hand, if AES only fit on more sophisticated smart cards, then costs would rise significantly. On the other hand, if the information being protected was valuable enough to require use of the AES, then perhaps the extra cost was appropriate, in which case it would be unfortunate to skew the AES selection towards performance in limited environments. Smid asked for comments on the usefulness of ``provable security'' and ``minimal secure rounds.'' Schneier offered the only response to the former: it was useful and helpful in analysis, but only as good as the underlying assumptions and model. He likened it to the analysis that many teams had provided against certain types of attacks; it increased confidence, but he would not choose a cipher based on that factor alone. The question of ``minimal secure rounds'' attracted more discussion. One attendee believed that the margin of safety was essentially independent of the algorithm design; therefore, NIST, with input from the cryptographic community, ought to give guidance for the margin of safety, to avoid losing otherwise good algorithms. However, it was pointed out that determining the margin of safety for each algorithm was still a problem, especially since the candidates had weathered different levels of analysis. It was suggested that NIST allow round variability within algorithms, since the different key sizes already implied different levels of security. One objection was that not all of the ciphers could easily support round variability. Another caution was that it opened an avenue for insecure implementations in which an attacker could control the number of rounds. A third objection was that, if the AES were broken, the situation would call for analysis, not the hasty solution of, say, doubling the number of rounds. Smid pointed out that it was the cryptographic community that had asked for at least 128 bit and 256 bit key sizes, without giving guidelines on the number of rounds. 11. Future Plans and Closing To close the conference, Smid explained how the AES process would continue and presented the following timetable. The Round 1 comment period would close April 15, 1999 and NIST would post all of the official comments on April 19, 1999. May 15, 1999 would be the deadline for the submitters to propose, if they wished, minor modifications (``tweaks'') to their algorithms. Sometime in the summer of 1999, NIST would announce the finalists, beginning the Round 2 analysis. One month after the announcement would be the deadline for the submission of any updated code, which NIST would then distribute to interested parties. The deadline for papers for the third AES conference would be January 15, 2000; the conference itself would be the week of April 10, 2000. The Round 2 comment period would close May 15, 2000. The draft AES standard, which would contain the winner(s) would be announced for public comment in late summer of 2000. A conference feedback form was distributed to the attendees. It included an informal poll, asking the attendees which five algorithms NIST should select for Round 2, and which algorithms, if any, NIST should definitely not choose for Round 2. Smid said that the results would be posted on the AES homepage. References [1] ``Announcing Request for Candidate Algorithm Nominations for the Advanced Encryption Standard (AES)'', Federal Register, Volume 62, Number 177, September 12, 1997. pp. 48051-48058. [2] ``Conference Report: First Advanced Encryption Standard (AES) Candidate Conference,'' Journal of Research of the National Institute of Standards and Technology, Volume 104, Number 1, January-February 1998, pp. 97-105. [3] G. Keating, ``Performance Analysis of AES Candidates on the 6805 CPU core,'' April 15, 1999, available from http://www.ozemail.com.au/%7Egeoffk/aes-6805/. [4] P. Kocher, J. Jaffe, B. Jun, ``Introduction to Differential Power Analysis and Related Attacks,'' available from http://www.cryptography.com/dpa/technical/. [5] D. Whiting, J. Kelsey, B. Schneier, D. Wagner, N. Ferguson, C. Hall, ``Further Observations on the Key Schedule of Twofish,'' Twofish Technical Report #4, March 16, 1999, available from http://www.counterpane.com/twofish.html. NIST's AES Homepage http://www.nist.gov/aes ________________________ U.S. Government work not protected by copyright. Java and all Java-based marks are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries. All SPARC trademarks are trademarks or registered trademarks of SPARC International, Inc. in the United States and other countries. Products bearing SPARC trademarks are based upon an architecture used by Sun Microsystems, Inc. Mention of commercial products does not constitute endorsement by NIST. ______________________________________________________________________ Twelfth IEEE Computer Security Foundations Workshop (CSFW12) Mordano, Italy June 28-30, 1999 by Scott Stoller (stoller@cs.indiana.edu) ______________________________________________________________________ The 12th IEEE CSFW was held in the delightful Hotel Panazza, in Mordano, Italy, a small town near Imola. The opening comments by Roberto Gorrieri (general chair) and Paul Syverson (program chair) revealed that this was the largest CSFW ever. There were 50 attendees, with 25 from the USA, and 12 from the UK. Ten more people were interested in attending but had to be turned away. The 13th CSFW will be held in Cambridge, England. Details will be available from http://www.csl.sri.com/csfw/ A Formal Framework and Evaluation Method for Network Denial of Service Cathy Meadows. In network denial of service attacks on protocols for establishing authenticated communication channels, the identity of the attacker is generally unknown, because authentication has not been completed. A design technique for making protocols more resistant to such attacks is the use of a sequence of authentication mechanisms, arranged in order of increasing cost (to both parties) and security. Thus, an attacker must be willing to complete the earlier stages of the protocol before it can force a system to expend resources running the later stages of the protocol. Cathy proposed a framework for analyzing such protocols. The framework is based on Gong and Syverson's model of fail-stop protocols. The NRL protocol analyzer was used to formally verify some properties of such protocols. I/O Automaton Models and Proofs of Shared-Key Communications Systems Nancy Lynch The emphasis is on modular reasoning using standard proof techniques, specifically, invariant assertions and simulation relations. To illustrate the approach, I/O-automaton models of private communication channels, key distribution, shared-key cryptography, base-exponent cryptography, and an eavesdropper were developed, and a modular proof was given to show that a straightforward cryptographic protocol implements private communication channels in the presence of an eavesdropper. The modular proof requires finding, for each subprotocol, an invariant characterizing the set of messages that that subprotocol can tolerate being revealed to the eavesdropper. A similar proof involving an active attacker is almost finished. More ambitious future work aims at modular probabilistic reasoning; the central problem there is to show that a small probability of a successful attack on a protocol does not blow up when the protocol is composed with other protocols. John Mitchell pointed out that the invariants sometimes need to be time-dependent; for example, it might be OK to reveal a particular message after (but not before) a certain point in the protocol. Cathy Meadows asked whether this approach can be used to show that similar subprotocols in a protocol suite don't interfere with each other. Nancy replied that it can. Safe Simplifying Transformations for Security Protocols Gavin Lowe (speaker) and Mei Lin Hui The goal is to reduce the cost of model checking by first applying some safe simplifying transformations to the protocol. In this context, "safe" means: if the original protocol is insecure, then so is the transformed protocol. Thus, if the model checker does not find an attack on the simplified protocol, then the original protocol is secure. If the model checker does find an attack on the simplified protocol, then the user must determine by inspection whether the original protocol is vulnerable to an analogous attack, or whether the attack is an artifact of the simplifications. They applied this approach while analyzing the Cybercash and SET protocols. They assume that cryptographic keys are atomic. Someone asked whether this assumption is necessary. Gavin was uncertain whether structured keys could easily be accommodated. Someone asked whether the simplifying transformations are a special case of forward simulations. Gavin said they probably are. Decision Procedures for the Analysis of Cryptographic Protocols by Logics of Belief David Monniaux Decision procedures for BAN-like logics of belief are not new. Mao and Boyd (IEEE CSFW, 1993) describe a tableau-based procedure. Kindred and Wing (USENIX Workshop on Electronic Commerce, 1996) describe a decision procedure that uses forward chaining and backward chaining. David's approach uses only forward chaining. Some automatic transformations of the proof system are used to make all rules suitable for forward chaining. David considered trying to use only backward chaining, but that seemed more difficult. Cathy Meadows asked how decidability of such proof systems relates to undecidability results such as that in the paper by Cervesato et al. (described next). David replied that the undecidability results apply to semantic models of authentication protocols, and there is no good such semantics for belief logics. A Meta-Notation for Protocol Analysis Iliano Cervesato, Nancy Durgin, Pat Lincoln, John Mitchell (speaker), and Andre Scedrov The goal is to find the simplest framework that captures the essential aspects of the Dolev-Yao model of cryptographic protocols. The Dolev-Yao model implies certain assumptions about the adversary, e.g., the adversary cannot gain partial knowledge of a value or perform statistical tests. The framework is designed to facilitate meta-theory. It is also hoped that other researchers will adopt the framework, to help unify work on analysis of cryptographic protocols. The framework is based on multiset rewriting. Generation of fresh values (e.g., nonces) is modeled by existential quantification. Using this framework, they studied how various restrictions on protocols affect the complexity of verification. If the depth of encryptions and the number of fields per message are bounded, and the number of protocol instances and the number of generated nonces are unbounded, then the verification problem is undecidable. If either one of the latter two parameters is bounded, then the verification problem is decidable. There is a typo in the paper: "PSPACE-complete" should be changed to "DEXP-time complete". Mixed Strand Spaces F. Javier Thayer Fabrega, Jonathan Herzog, and Joshua Guttman (speaker) Principals sometimes use multiple protocols with similar message formats and sometimes share keying material among them. This can cause problems. For example, in the Neumann-Stubblebine protocol, the re-authentication protocol introduces a violation of agreement in the authentication protocol. Such problems motivate the study of techniques for proving that different (sub)protocols do not interact in harmful ways. "Mixing conditions" are proposed for this purpose. Mixing conditions are described here in terms of the strand space model, though the idea is fairly model-independent. Mixing conditions are related to the invariants used in Nancy Lynch's approach (described above). Mixing conditions for a protocol P are derived from the correctness proof of P in isolation. If the other protocols used with P satisfy the mixing conditions, then they do not cause P to violate its requirements. Someone asked whether their work considers type-confusion attacks. Joshua said no, but extending it to do so might be possible. Someone asked whether their approach can be used when the correctness requirements include non-repudiation; this might be tricky, because the strand space model distinguishes regular and penetrator strands, and with non-repudiation, this distinction might be blurred. Josh thinks that this is not a problem, because non-repudiation can be expressed as a property of the form "if a bundle contains a strand of the form X, then it also contains a strand of the form Y" (e.g., X involves receipt of evidence that some action occurred, and Y contains such an action), and their approach handles properties of this form. Honest Functions and their Application to the Analysis of Cryptographic Protocols Al Maneki The theory of strand spaces is extended to encompass a broader class of cryptographic protocols. A class of functions, called honest functions, is defined; this class include exclusive-or and exponentiation of integers in a prime number field. Informally, a function f is honest if either (1) f is 1-to-1 and its inverse is not easily computed, or (2) for each y=f(x_1,...,x_n), y has so many pre-images under f that exhaustive search of them is infeasible. Some general theorems are given to facilitate reasoning in the strand space model about protocols that use honest functions. The approach is illustrated by an analysis of Roscoe's version of the TMN protocol. Panel: Formalization and Proof of Secrecy Properties Dennis Volpano (chair), Cathy Meadows, Jon Millen, Martin Abadi, and Riccardo Focardi The first day ended with a panel discussion. Each panelist gave a short presentation before the free-for-all discussion. Dennis Volpano emphasized the importance of considering secrecy of bindings (e.g., of a variable to a value), as opposed to secrecy of values (e.g., private keys). He distinguished three notions of secrecy: Secrecy as a safety property. This notion is used in the Dolev-Yao model and its descendants. It is typically used for expressing secrecy of values. This notion facilitates automated reasoning but does not consider indirect information flow. Unconditional secrecy (non-interference). This approach considers indirect information flow and in some cases can handle probabilistic violations of secrecy, but it does not handle some forms of cryptography (e.g., public-key crypto). Conditional secrecy. In this approach, one shows that obtaining secret information is as difficult as breaking the underlying cryptosystem. Cathy Meadows characterized the Dolev-Yao approach to secrecy as shallow and wide, because the same approach works for a wide variety of properties. In contrast, models of information flow are narrow and deep. Access control is also shallow and wide. Bell and La Padula tried to integrate access control and information flow. That effort foundered on downgrading. This led to notions of intransitive non-interference, and so on. That line of work might be relevant to protocol analysis; for example, it might be possible to analyze subliminal channels in authentication protocols. Jon Millen discussed operating system secrecy vs. protocol secrecy. He expressed an analogy between them by drawing two pyramids: / covert channels \ / cryptanalysis \ / probabilistic models \ / probabilistic models \ / non-interference \ / model checking, inductive proofs \ / access control \ / belief logics \ Non-interference is suitable for proving absence of causal flow of a bit or bits. In protocol analysis, one deals with secrecy of bitstrings large enough to be unguessable, so if those bits appear in two places, causal flow between those places is assumed. This model is attractive because it is simpler, but is it model always adequate for protocol analysis? No: a large bitstring might be compromised through repeated attacks that each obtain partial information. Such attacks are not considered in Dolev-Yao-like models. Martin Abadi advocated expressing secrecy in terms of observational equivalence, as done in the Spi calculus. The Dolev-Yao notion of secrecy is good for expressing secrecy of unguessable values but is not good at expressing secrecy of guessable values (e.g., Booleans). This is a major limitation, because application data, which is what really matters, usually contains guessable values. (One could argue that keeping application data secret is easy if cryptographic keys are kept secret, but it would be nice to prove this.) Secrecy of both kinds of values can be expressed using observational equivalence. Riccardo Focardi described a non-interference-based approach to protocol analysis. The basic idea is to show that the intruder cannot interfere with the protocol. This approach allows general results about non-interference to be used, e.g., results that justify considering only the most powerful intruder. During the free-for-all discussion, John McLean suggested that non-interference is not applied more often to analysis of cryptographic protocols because: (1) we still don't understand the Dolev-Yao model as well as we understand access control, (2) cryptanalytic attacks are probably more important than the information leaks that can be analyzed using non-interference, (3) the theory of non-interference does not handle some forms of cryptography, (4) reasoning about non-interference is difficult, and reasoning about probabilistic non-interference is even more difficult. Martin Abadi said that, if he were deciding how to allocate resources to be spent on verification of a protocol, he would formally state and informally prove the secrecy properties, but he would not spend money on formal verification of them. He would spend that money on formal verification of authenticity properties. Dennis Volpano pointed out that implementations might have information leaks that are not evident in the high-level protocol descriptions commonly used in the protocol analysis community. For example, the possibility of timing attacks on a protocol (or on the underlying cryptosystem) is usually not considered. Jon Millen noted that such analysis would occur at the top level of his pyramid. Authentication via Localized Names Chiara Bodei, Pierpaolo Degano (speaker), Riccardo Focardi and Corrado Priami The goal is to provide a high-level characterization of message authentication and to study how encryption is used to achieve message authentication. The formal framework is a variant of the Spi-calculus in which each sequential process has its own namespace. A Logic for SDSI's Linked Local Name Spaces Joseph Y. Halpern and Ron van der Meyden (speaker) Rivest and Lampson's Simple Distributed Security Infrastructure (SDSI) incorporates linked local namespaces. For example, suppose that in my (local) namespace, "Joe" refers to Joe Halpern (i.e., is bound to Joe Halpern's public key). Then, in my namespace, "Joe's colleagues" refers to the binding of "colleagues" in Joe Halpern's namespace. Bindings are created by issuing certificates. The authors give (1) a semantic characterization of SDSI's name resolution algorithm, (2) a sound and complete axiomatization for proving validity of formulas with respect to that semantics, and (3) a translation of their proof system into Datalog that yields a polynomial-time implementation of the SDSI name resolution algorithm. Martin Abadi had previously proposed a logic for SDSI's local namespaces; however, Abadi's axioms do not correspond to precisely to SDSI's name resolution algorithm. [I missed the session on Interaction and Composition, which contained the next three talks, so I have included abstracts of the papers' abstracts.] Trusted System Construction Colin O'Halloran An important trend is construction of trusted systems from COTS components by encapsulating each component in an appropriate software wrapper. Achieving security without compromising the operational effectiveness of the system is difficult. This work addresses the problem of analyzing such systems to demonstrate that the system is both secure and usable. The proposed approach is illustrated using the X windowing system. Secure Composition of Insecure Components Peter Sewell and Jan Vitek Many contemporary software systems consist of numerous components that interact in intricate ways. Some components are only partially trusted. To ensure security properties of the entire system, components are executed in the context of wrappers that provide fine-grained control over interactions between components. The authors propose a formal model based on the pi-calculus that is suitable for analyzing such systems. Security Function Interactions Pierre Bieber This paper uses a compositional framework to model security architectures involving heterogeneous and distributed security functions. The goal is to assist the ITSEC evaluation of suitability, binding and vulnerability of a set of security functions. The author proposes constraints that security functions should guarantee in order to interact consistently and securely with other functions. These notions are illustrated by studying the interactions of various components of a secure LAN. A Logic-based Knowledge Representation for Authorization with Delegation Ninghui Li, Joan Feigenbaum (speaker), and Benjamin Grosof Trust management systems integrate authentication and access control. Whether this is a good idea is still an open question, according to Joan. Trust management systems, such as KeyNote, are starting to be deployed in commercial systems, but more experience is needed before the benefits of trust management systems can be properly evaluated. Delegation Logic (DL) is proposed to provide a more formal and less ad-hoc foundation for trust management systems. DL can be used to determine whether a request supported by certain credentials should be approved under a certain authorization policy. Logic-programming techniques can be used to automate such authorization decisions. DL treats delegation depth explicitly. This enables expression of policies such as: I give you permission to delegate permission to perform some operation X to anyone you trust, but those principals cannot delegate permission to perform X to other principals. Whether it is useful for a trust management system to support bounded delegation depth greater than one is still an open question, according to Joan. DL supports a general notion of delegation to complex principals; this notion can be used to represent k-out-of-n threshold schemes. DL is based on general ideas from logic programming, so it can cleanly support non-monotonicity (useful for expressing revocation), negation, and prioritized conflict resolution. Joan announced that there is a typo in the paper: on p. 169, column 1, in the numbered list of items, a fifth item was accidentally omitted: 5. Every ground clause that has the form: $$ delegates(A, pred, [params], *, A ,1).$$ Intuitively, this represents the fact that every principal delegates every predicate to itself with depth *. A revised version of the full paper is available from http://www.research.ibm.com/people/g/grosof/papers.html . A Logical Framework for Reasoning on Data Access Control Policies Elisa Bertino, Francesco Buccafuri (speaker), Elena Ferrari, and Pasquale Rullo A logic formalism is proposed for expressing access control policies, e.g., for database security. Authorizations are represented by logic rules. Two forms of negation are distinguished: strong negation, for expressing prohibition (e.g., "Bill is forbidden from accessing that table"), and weak negation, for expressing absence of explicit positive authorization (e.g., "Bill has not explicitly been given permission to access that table"). Priorities can be used to help determine which rules prevail in case of conflicts. Various possible semantics for authorization rules are given, based on semantics of logic programs. Athena: a New Efficient Automatic Checker for Security Protocol Analysis Dawn Xiaodong Song Athena is a tool for automated analysis of security protocols. To verify a property, Athena starts from appropriate states of interest (e.g., states containing a violation of a secrecy requirement) and performs a backward search to determine whether (and, if so, how) the system could have reached such a state. For efficiency, Athena allows states to contain variables; thus, a single "symbolic" state represents a set of concrete states (namely, the states that can be obtained by replacing the variables with type-correct values). In the two aspects just described, Athena is similar to Cathy Meadows' NRL Protocol Analyzer. A significant difference is that Athena is based on the strand space model, and during the backward search, Athena tries to add an entire strand to the state in a single step. Thus, Athena can avoid exploring interleavings of independent events in different strands. This can drastically reduce the number of explored states. Athena embodies a semi-decision procedure; in other words, Athena may diverge. This is unavoidable, given undecidability results such as those in the paper by Cervesato et al. (described above). John Mitchell mentioned that a newer version of the Murphi-based security protocol analyzer by Mitchell, Stern, et al. explores about 500 states when analyzing the Needham-Schroeder-Lowe protocol; the figure of about 500,000 states that appears in Table 1 of this paper is out of date. John said that the most effective optimization they incorporated is forcing alternation between transitions of the intruder and transitions of honest principals. He asked whether Athena exploits a similar optimization. Dawn replied that it is hard to compare the optimizations used in the two systems. Cathy Meadows suggested that it would be interesting to compare Athena's verification of the Needham-Schroeder-Lowe protocol with her analysis of that protocol using the NRL Protocol Analyzer, as described in an ESORICS'96 paper. CVS: A Compiler for the Analysis of Cryptographic Protocols Antonio Durante, Riccardo Focardi, and Roberto Gorrieri (speaker) CVS automatically translates protocols described in VSP, a domain-specific high-level language, into SPA (Security Process Algebra), a CCS-like process algebra. The resulting SPA description of the protocol can be given to the CoSeC tool for verification. (Gavin Lowe developed a similar tool, called Casper, that translates protocols into CSP.) The CoSeC analysis is based on non-interference: it attempts to show that the intruder cannot influence the observable behavior of honest participants in the protocol. If this attempt fails, the user is shown traces in which the honest participants' behavior is influenced by the intruder. The user decides inspection whether those traces represent violations of the protocol's correctness requirements; they are working to automate this step. Using these tools, they found a simple and apparently new attack on the Woo-Lam one-way authentication protocol. Martin Abadi mentioned that it is not clear what that protocol is intended to achieve, hence it is not clear what should be considered an attack. Cathy Meadows suggested that they consider using Millen's language CAPSL (instead of VSP) as an abstract notation for protocols. Process Algebra and Non-Interference Peter Ryan (speaker) and Steve Schneider The information security community has had difficulty giving a precise definition of non-interference, especially for non-deterministic systems. The authors show that non-interference is closely related to equivalence of systems, which is a central concept in the theory of process algebras. Different notions of equivalence lead naturally to different notions of non-interference. Thus, the lack of consensus on the definition of non-interference is closely related to the multiplicity of equivalences in the process-algebra literature. The authors demonstrate a correspondence between some definitions of non-interference and some notions of process equivalence. A benefit of understanding this relationship is that results from the process-algebra community can be exploited, e.g., results regarding composition and unwinding. A process-algebraic proof of completeness of a previously known set of rules for unwinding is given; the process-algebraic proof is cleaner and gives more insight than the original proof. Some ideas are described for generalizing non-interference to handle partial and conditional information flow. John McLean said that the proposed definition of non-interference seems quite natural, and that this was surprising, because the definition is also compositional, and he usually takes compositionality as a sign that a definition does not capture the meaning of non-interference. Peter replied that they could discuss this point in more detail off-line, but in the meantime, John might feel better knowing that their notion of non-interference is not preserved by refinement. What is Intransitive Noninterference? A. W. Roscoe (speaker) and M. H. Goldsmith Intransitive non-interference refers to information flow properties required of systems containing downgraders, in which it may be legitimate for information to flow indirectly between two users but not directly. The concept is illustrated by a secure file system, with a process that can downgrade files from high-security to low-security. Using this example, they show that the standard definition of intransitive non-interference in terms of a purge function is undesirably permissive: it allows the effects of "too many" high-level actions to become visible in the low-level view after a downgrading action. As a remedy, a definition based on determinism is proposed. Roughly, the determinism-based notion of non-interference is as follows: high-level actions are turned into non-deterministic choices, and if the low-level view is deterministic, then there is no information flow from the high level to the low level. This definition can be extended to yield a definition of intransitive non-interference that is not overly permissive. ______________________________________________________________________ The 11th Forum for Incident Response and Security Teams (FIRST 99) Brisbane Australia June 13-18, 1999 by Cristina Serban - AT&T Labs ______________________________________________________________________ The 11th FIRST (Forum for Incident Response and Security Teams) International Conference was held June 13-18 in Brisbane, Australia. [If you are not familiar with FIRST, it is the international organization of CERTs, or Computer Emergency Response Teams, including teams from literally all over the world, representing universities, industry, defense organizations or even whole countries. A lot more info at www.first.org if you are interested.] The 1999 conference had a full day of tutorials, followed by 4 days of paper and panel presentations, with the FIRST annual general meeting in between. Among tutorials, an excellent one on Computer Forensics was offered by our hosts in Brisbane (a group of professors and researchers from the Queensland University of Technology, and members of the Information Warfare and law enforcement). The tutorial presented issues, current methods, and law aspects in computer forensics, concentrating on the practical "what should you do?" part of the story. A very interesting study done by the Information Security Research Center and the Faculty of Law at QUT looked at specific computer crime cases, what computer forensics activity was performed, what evidence was collected, preserved, then brought to court, and what was the outcome of the legal process. There is - at least in Australia - a huge difference in views on evidence admissibility between IT and law. The conclusion of the study was not the usual "we need more legislation" but instead "IT better gets its act together before going to court". The conference had addresses from the Minister of Justice and the Advisor on IT Security Policy, and the keynote speech was given by professor William Caelli (QUT). Consensus: Significant increase in attacks; Cooperation is required for successful defense; CERTs and FIRST role more important into 21st century. Among the topics discussed in papers and panels: -- Outsourcing security services and managing such services (SecureGate Ltd.): According to the presenters' experience, outsourcing security is a real option but security must be managed as a process (both at client and provider), not just as a one-time task. -- Insurability criteria for networks (Cisco): An insurance company needs to assess a network for coverage before establishing premiums and other terms of contracts, but no actuarial tables or other data exist so far. Outside security experts are needed to help determine risks. Given that the major focus for coverage is on revenue lost from system downtime, the paper presented a scale for assessing a network on DoS-related vulnerabilities that are identified within it. Beside exposure to existing vulnerabilities, the habits to stay current on newly discovered vulnerabilities must be taken into account. -- Intrusion Detection Services (IBM Global Services) - Experience from providing real-time intrusion detection as a service was presented. The underlying mechanism used by this service is network monitoring, with the "bad" packets replicated to an analyst / operator for signature categorization, then appropriate action is recommended or taken. Of course, users should have in place protection *and* ID, not just ID to witness intrusion. As an approach to liability, it had been mostly on a best-effort basis, now it is moving toward SLA-like (Service Level Agreement) arrangements. -- Automated incident reporting at CERT/CC (CERT/CC, ISS): At CERT/CC, there is no uniform way to report incidents (reports from teams come in all shapes, languages, and so on). As a result, incident data collection and processing are time-consuming and error-prone. Based on some of the current efforts in the incident reporting space - such as: CIDF (Common Intrusion Detection Framework), IDWG's IDEP (Intrusion Detection Exchange Protocol), AVE (Account Vulnerability Enumeration) project at Mitre for a common vocabulary - the paper proposed a Web-based incident reporting, with automated processing of text incident reports. -- Always-on devices - cable modems and ADSL modems (AT&T): The new high-speed access methods come with risks to users, providers, and the community. The PC's "Network Neighborhood" can extend to the physical neighborhood, and a static IP address *plus* and an always-on device make up a very easy target if additional *individual* protection is not in place at the user's home. Proper planning, provisioning and operation are essential for the provider, while a careful architecture of the service can prevent some (but not all) of the problems. -- Setting up a Policy Certification Authority (CERT-NL, DFN-CERT): This paper presented experiences at DFN and SURFnet in establishing a PCA, an organizational entity that provides third party services to the constituency. Among the good news, it is possible to set up an institutional CA for 10-to-50K users that can do reliable certificates at a cost of 50cents/cert! -- and of course Wietse Venema's (IBM) "Bugs per Amount of Code" paper. There were also a lot of lively discussions during the sessions and outside, several bofs, not to mention many exchanges of real-life experiences and information. Overall, a very good conference for all those involved in incident response security work. ______________________________________________________________________ Workshop on Formal Methods and Security Protocols (FMSP 99) Trento, Italy July 5th, 1999 Nevin Heintze (Bell Labs) ______________________________________________________________________ An electronic version of the proceeding of FMSP'99 (Formal Methods and Security Protocols) is available from http://www.cs.bell-labs.com/who/nch/fmsp99/program.html. It includes links to all presented papers, links to some of the talk slides, and notes on a (lively) panel discussion. 10:15-11:30 Invited Talk * "Formal Analysis of Cryptographic Protocols: A Survey" o C. Meadows (Naval Research Laboratory) 11:30-12:30 Session I * "CAPSL Intermediate Language" o G. Denker and J. Millen (SRI) * "Analyzing a Library of Security Protocols using Casper and FDR" o B. Donovan, P. Norris and G. Lowe (Univ. of Leicester) 12:30-1:30 Lunch 1:30-3:00: Session II * "Undecidability of Bounded Security Protocols" o N. Durgin (Stanford), P. Lincoln (SRI), J. Mitchell (Stanford) and A. Scedrov (U. Penn.) * "Towards the Formal Verification of Ciphers: Logical Cryptanalysis of DES" o F. Massacci and L. Marraro (University of Rome I) * "A Necessarily Parallel Attack" o J. Millen (SRI) 3:30-5:00: Session III * "Efficient Infinite-State Analysis of Security Protocols" o A. Huima (SSH Communications Security) * "A Reduction for Automated Verification of Authentication Protocols" (talk slides) o S. Stoller (Indiana University) * "Analysis of a Fair Exchange Protocol" o V. Shmatikov and J. Mitchell (Stanford) 5:15-5:45: Panel Session ________________________________________________________________________ New Interesting Links on the Web ________________________________________________________________________ o http://www.computer.org/chapter/DVP/toc.htm The IEEE Computer Society's Distinguished Visitors Program. Includes nominations for the program and current DVs. ________________________________________________________________________ New Reports available via FTP and WWW ________________________________________________________________________ o http://www.law.kuleuven.ac.be/icri/papers/ontwerp/digsig/ontwerpdigsig.htm (In French and Dutch) Describes a proposal for law in Belgium, about how recognized certification authorities should function, especially considering the use of digital signatures. o http://www.law.kuleuven.ac.be/icri/papers/ontwerp/bw/bw_ontw.htm (In Dutch) Describes a proposal to change parts of the Belgian Civil Codex that have to do with signatures in general. ________________________________________________________________________ Who's Where: recent address changes ________________________________________________________________________ John Pescatore Research Director Gartner Group Email: network@gartner.com Voice: 203-316-1111 x5755 Fax: 203-316-6598 (fax) Carl E. Landwehr Mitretek Systems, Inc MS Z553 7525 Colshire Drive McLean VA 22102 Phone: (703)610-1576 Fax: (703)610-1603 e-mail: Carl.Landwehr@mitretek.org Bob Blakley Chief Scientist DASCOM Inc. 5515 Plaza Balcones Austin, TX 78731 Voice: +1 512 458-4037 x 5012 Email: blakley@dascom.com _______________________________________________________________________ Calls for Papers ________________________________________________________________________ CONFERENCES Listed earliest deadline first. See also Cipher Calendar. * NORDSEC'99 The fourth Nordic Workshop on Secure IT systems - Encouraging Co-operation, Stockholm, Sweden, November 1-2, 1999. (Submissions due: August 16, 1999) The NORDSEC workshops were started in 1996 with the aim to bring together researchers and practitioners within IT security in the Nordic countries. NORDSEC'99 is organised by the Department of Computer and Systems Sciences, DSV, Stockholm University & the Royal Institute of Technology, the Swedish Defence Materiel Administration and Telia AB. This is the theme our workshop addressed: knowledgeable and maturing use, applications, developments and research of IS/IT security in order to provide individuals, companies & organisations and societies with a reliable, safe and secure, and changing world. A complete list of topics can be found at the workshop's website at www.telia.se/nordsec99. The workshop will consist of paper sessions, panel discussions and invited talks. We also welcome the submission of application-oriented papers focusing on new or difficult problems, pilots, and experiences. Authors are requested to submit an extended abstract (4-5 pages) or a full paper (up to 15 pages) to Dr. Louise Yngstrvm (louise@dsv.su.se) by August 16, 1999. * PKC2000, International Workshop on Practice and Theory in Public Key Cryptography, Melbourne, Australia, January 18-20, 2000. (Submissions due: August 27, 1999) Original research papers pertaining to all aspects of public key encryption and digital signature, as well as associated issues in privacy and security, are solicited. Submissions may present theory, techniques, applications and practical experience. A complete list of topics, along with detailed instructions for authors, is provided on the conference web page at www.pscit.monash.edu.au/pkc2k/. * Foundations of Mobile Computation: A Post-Conference Satellite Workshop of FST & TCS 99, Chennai, India, December 16-17, 1999. (Submissions due September 15, 1999) Additional information at: www.cse.iitd.ernet.in/~mobile99 www.imsc.ernet.in/~fsttcs99 email: mobile99@cse.iitd.ernet.in The workshop will address fundamental principles in the definition, analysis and implementation of languages and models for mobile distributed programming. The theme of the workshop is formal operational foundations of mobile computation, including semantics, equivalences and program logics. Issues include: typing and type safety, security, mobility, architectures and protocols, active networks, proof-carrying code, protocol analysis and verification, concurrent constraint solving, as well as numerous interesting applications such as switchware, programmable hybrid systems, and reactive systems. The aim of the workshop is to introduce operational frameworks to potentially interested researchers (the tutorial aspect) as well as provide a forum for researchers active in the area to report on recent results or ongoing work. * Financial Cryptography `00, Anguilla, BWI, February 21-24, 2000. (Submissions due: September 24, 1999) Original papers are solicited on all aspects of financial data security and digital commerce in general for submission to the Fourth Annual Conference on Financial Cryptography (FC00). Directions for electronic submissions are at www.fc00.cs.uwm.edu/esub.html. Additional information about FC00 may be found at fc00.ai. * 2000 IEEE Symposium on Security and Privacy, Oakland CA, USA, May 14-17, 2000 (Submissions due: October 29, 1999) (See the full CFP above or on the Cipher Web page or at http://www.bell-labs.com/user/reiter/sp2000/index.html). * 9th International World Wide Web Conference (WWW9), May 15-19, 2000. (Submissions due: November 22, 1999) (Workshop and Tutorial proposals due: Sept. 10, 1999) Submission details are available at http://www9.org Topics: E-Commerce, XML, Multimedia, Web Server Performance, Searching and Querying, Protocols, Web Document Management, Java, Web Site Design, Web Security, RDF, Database and Directory Services, Collaboration, Accessibility, Metadata, New Languages Submitted papers should present original reports of substantive new work in areas that can be theoretical (models, analyses, techniques, semantics), empirical (experiments, case studies), or implementation-oriented (new systems, tools, methodologies, user interfaces). Tutorial proposals are desired for both half-day and full-day sessions on topics of current relevance to Web design, services, operation, and use. Subjects of interest include XML, DOM, Multimedia, E-commerce, Java, Dynamic HTML, Security, Accessibility, Graphics and the Web, and other areas expected to be of special interest in spring 2000. WWW9 workshops are intended to provide a forum for highly interactive discussion on focused topics. Workshop proposals should address current web-related issues which can benefit from small-group information exchange and discussion. Attendance at workshops will be limited. * Computers, Freedom, and Privacy. CFP 2000 Challenging the Assumptions, April 4-7, 2000. (Submissions due: October 15, 1999) The theme of the tenth CFP conference is 'Challenging the Assumptions'. After a decade of CFP conferences, it's time to examine what we have learned. At CFP2000 we want to re-examine the assumptions we have been making and consider which ones still make sense as we move forward. Proposals are welcomed on all aspects of computers, freedom, and privacy. We strongly encourage proposals that challenge the future, tackle the hard questions, look at old issues in new ways, articulate and analyze key assumptions, and present complex issues in all their complexity. We are seeking proposals for tutorials, plenary sessions, workshops, and birds-of-a-feather sessions. We are also seeking suggestions for speakers and topics. Sessions should present a wide range of thinking on a topic by including speakers from different viewpoints. Complete submission instructions appear on the CFP2000 web site at http://www.cfp2000.org/submissions/. JOURNALS Special Issues of Journals and Handbooks: listed earliest deadline first. * Computer Communications Journal, special issue on Advances in Research and Application of Network Security, first quarter 2000. Guest Editors: Dr. M. Merabti (John Moores University, UK), Dr. Q. Shi (John Moores University, UK), and Dr. Rolf Oppliger (Swiss Federal Office of information Technology & Systems) (full papers due September 1, 1999) [posted here June 15, 1999]. The special issue aims to publish original research results of both theoretical and practical significance. Topics of interest include, but are not limited to Security architectures and protocols Intrusion detection Authentication and key management Authorisation and access control Secure electronic commerce Privacy and anonymity Mobile code and web security Mobile communication security Security analysis The deadline for receipt of four copies of full manuscripts is September 1, 1999. Please, refer to URL to get further information. ________________________________________________________________________ Reader's Guide to Current Technical Literature in Security and Privacy Part 1: Conference Papers by Anish Mathuria ________________________________________________________________________ * IEEE/IFIP IWQoS '99 - Seventh International Workshop on Quality of Service, London, UK, June 1-4, 1999: [Security-related paper only] o Securing QoS: Threats to RSVP Messages and Their Countermeasures. T.-L. Wu, S. Felix Wu, Z. Fu, H. Huang and F. Gong * WISE1 - IFIP WG 11.8 1st World Conference on Information Security Education, Stockholm, Sweden, June 17-19, 1999: o Incorporating Security Issues Throughout the Computer Science Curriculum. G. White and W. Marti o The Reference Monitor Concept as a Unifying Principle in Computer Security Education. C. Irvine o Personnel Training in the Field of Information Security Maintenance. A. Maljuk and A. Tolstoi o IT related Ethics Education in Southern Africa -- Now and Then. L. Drevin o Data Protection in Healthcare and Welfare - Education of Data Protection Officials in Germany. B. Blobel and P. Pharow o A Mix-Demonstrator for Teaching Security in the Virtual University. U. Jendricke and K. Rannenberg o On the Experience of Creating the Electronic Tutorial "