The 18th Annual Cryptology Conference (CRYPTO '98) was held at its traditional location, the University of California at Santa Barbara, on August 23-27, 1998. The conference is sponsored by the International Association for Cryptologic Research (IACR), in cooperation with the IEEE Computer Society Technical Committee on Security and Privacy, and the Computer Science Department at the University of California, Santa Barbara (UCSB.)
Andrew Klapper (University of Kentucky, USA) served as the General Chair. Hugo Krawczyk (Technion, Israel and IBM Research, USA) served as the Program Chair.
This year, the ever popular conference attracted over 500 participants. The conference is a truly international event, with participants traveling from at least 31 countries spread around the globe: Argentina, Australia, Belgium, Brazil, Canada, China, Czech Republic, Denmark, Egypt, Estonia, Finland, France, Germany, Israel, Italy, Japan, Korea, the Netherlands, Norway, Peru, Romania, Saudi Arabia, Singapore, Slovak Republic, South Korea, Sweden, Switzerland, Taiwan, Turkey, United Kingdom, and the United States.
The proceedings are available from the publisher, Springer-Verlag: Advances in Cryptology - CRYPTO '98, Hugo Krawczyk (Ed.), Lecture Notes in Computer Science, Volume 1462, Springer-Verlag, 517 pages, 1998, ISBN 3-540-64892-5. See http://www.springer.de for further information.
The program consisted of the formal paper presentations, as well as three invited talks, an evening rump session with short, informal presentations, and an IACR business meeting. Since the formal papers can be found in the proceedings, this report focuses on selected paper presentations and the other events.
SELECTED PAPER PRESENTATIONS
*** Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1, Daniel Bleichenbacher (Bell Laboratories, Lucent Technologies, USA.) SSL Broken? RSA Flawed? Not exactly, but some implementations of SSL and similar protocols may be susceptible to an attack because of how they use the popular RSA algorithm. Daniel Bleichenbacher described this common method of using RSA that is implemented in many protocolsa method widely known and long standardized in RSAs Public Key Cryptographic Standards (PKCS) #1. The critical observation he makes is that the probability a random message is accepted by a recipient as PKCS #1 compliant is NOT vanishingly small. This property allows an attacker to use the message recipient as an oracle, and to deduce an RSA-protected message using a large, but not necessarily infeasible, number of trials.
Bleichenbacher described his chosen ciphertext attack using three phases: blinding, slow phase, and fast phase. In the blinding phase, the attacker submits randomly chosen values until the recipient confirms that the pseudo-message is PKCS #1 conforming (e.g. by NOT returning an error). Note, the blinding phase is not necessary when the recipient is performing decryption. Next, in the slow phase, the attacker tries to find the smallest value, s, for which the chosen ciphertext, cs^e mod n is PKCS #1 conforming. Each successively smaller value for s narrows the interval over which the RSA-protected message must be. Finally, in the fast phase, only one interval remains, and the value s is increased and various pseudo-messages of the form cs^e mod n are attempted until only one possible value of the sought after message could result.
The attack is particularly effective against implementations of the widely used SSL protocol, thus attracting significant attention earlier this year. The attack requires on the order of a million trials, however, and is therefore only applicable to cases with the recipient implementation automatically responds to an error (i.e. NOT e-mail). Of particular note, Bleichenbacher initially only disclosed this attack to RSADSI and major SSL vendors, allowing them to change their implementations and begin deploying the fix before the general public was even aware of the vulnerability. Countermeasures to the Bleichenbacher attack include supplying additional integrity checking of the RSA-protected message, providing less information upon error conditions and/or to begin using PKCS #1 v2 which specifies a less susceptible scheme based on Optimal Asymmetric Encryption Padding.
*** A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack, Victor Shoup (IBM Zurich Research Lab, Switzerland) and Ronald Cramer (ETH Zurich, Switzerland.) Bleichenbacher's widely publicized chosen ciphertext attack on SSL emphasizes the necessity of having a practical, provably secure public key cryptosystem. Past work in this area has included provably secure schemes that are impractical, and practical schemes that conjecture security, but not provably so. For instance, the Optimal Asymmetric Encryption Padding (OAEP) scheme proposed for RSA appears to thwart Bleichenbachers and others chosen ciphertext attacks, but OAEP is not provably secure. Cramer and Shoup answer the call by describing a practical public key cryptosystem that is secure against chosen ciphertext attacks.
The Cramer-Shoup public key encryption system proves that its security against adaptive chosen ciphertext attack relies on the hardness of the Diffie-Hellman decision problem. Since the hardness of the Diffie-Hellman decision problem is recognized as intractable, Cramer-Shoup resistance to adaptive chosen ciphertext attack is shown to be similarly intractable. The efficiency of the scheme is about twice the cost of an ElGamal implementation. IBM already plans to use Cramer-Shoup in its products although efficiency costs and licensing issues may slow wider use of this scheme in the marketplace.
*** Identity Escrow, Joe Kilian (NEC Research Institute, USA) and Erez Petrank (IBM Haifa Research Lab, Israel.) Advances in technology have increased our use of identification-based access procedures for facilities such as toll highways and parking garages. However, applications such as these that frequently expose the users identity raise a genuine concern about the erosion of our privacy. The other end of spectrum, an environment that provides completely anonymity, may also be undesirable for our society. Might we miss an opportunity to identify a hit-and-run drunk driver who used our toll highway? Or not be able to identify someone who was in a parking garage at the time of a murder? Kilian and Petrank offer a compromise between complete anonymity and the need to know identity in extreme cases--identity escrow.
An identity escrow system consists of four parties: (1) the user; (2) the issuer, who issues certificates allowing service; (3) the verifier, who verifies the identity process and the escrow proof; and (4) the escrow agent, the identity recoverer in emergency situations. To implement identity escrow, Kilian and Petrank offer schemes based on RSA and ElGamal group signature schemes. Similar to conventional key escrow schemes, the escrow agent is a trusted third party accessed only in emergencies. Unlike conventional key escrow schemes, however, the nature of the problem allows the escrow agent to be excluded from the initialization and normal operations of the identification system.
*** Fast RSA-type Cryptosystem Modulo (p^k)q, Tsuyoshi Takagi (NTT Software Laboratories, Japan.) Although the RSA cryptosystem is one of the most practical public key cryptosystems used today, the performance of its private key operations makes it extremely slow in computationally-limited devices such as smart cards. Thus, cryptographers have continually pursued various methods to speed up these operations without compromising the RSA cryptosystems security. Takagi presents a significant performance improvement for RSA private key operations.
Conventionally, the RSA modulus is determined as the product of two primes (n=pq). Takagi, however, suggests constructing the modulus as the product of a prime and a prime power, n=(p^k)q. Using Takagi's technique, operations using the public modulus and public exponent proceed normally. Operations using the private key, however, take advantage of the Chinese remainder theorem and can be sped up significantly. The advantage occurs because, for the same relative size n, smaller p and q values can be used, allowing modular exponentiations with smaller moduli and exponents. For a 768-bit modulus of the form n=(p^2)q, with 256-bit primes p and q, private key operations are about three times faster than conventional RSA cryptosystems.
Since the primes used are smaller, the obvious disadvantage of Takagis technique is increased susceptibility to factoring. At this time, however, for primes of at least 256 bits there are no known algorithms better than the number field sieve for finding the primes of the composite number (p^2)q.
ADVANCES IN SYMMETRIC CRYPTANALYSIS
Many new results in block cipher cryptanalysis and design have been presented this year, no doubt inspired by the Advanced Encryption Standard effort. At CRYPTO '98, there were five such presentations during the regular sessions, and the announcement of substantial new results during the rump session. By contrast, there was only one such presentation last year. There was a single new result on hash functions.
*** From Differential Cryptanalysis to Ciphertext-Only Attacks, Alex Biryukov and Eyal Kushilevitz (Technion, Israel.) The authors show that non-random plaintexts, such as blocks of ASCII-encoded English, are much more likely than random plaintexts to contain differences that can be used in differential cryptanalysis. They study the distribution of differences in ASCII English blocks, and use their result to construct ciphertext-only attacks on MADRYGA and a four round version of RC5.
*** Generalized Birthday Attacks on Unbalanced Feistel Networks, Charanjit S. Julta (IBM T.J. Watson Research Center, USA.) Julta's work generalizes birthday attacks on Luby-Rackoff ciphers to include the expanding unbalanced Feistel networks, that is, Luby-Rackoff ciphers with different sizes of left and right data halves, in which the random function takes its input from the smaller half. He bounds the number of chosen plaintexts needed to distinguish such a cipher from a random permutation.
*** Quadratic Relation of S-box and Its Application to the Linear Attack of Full Round DES, Takeshi Shimoyama (TAO, Japan) and Toshinobu Kaneko (Science University of Tokyo, Japan.) The authors used Grobner bases to obtain quadratic relations of the DES S-boxes, and found a quadratic equation for S5 that could be used to improve the multiple approximations method of Kaliski and Robshaw. Though their attack reduces the amount of known plaintext by only 26%, it shows a useful new method for attacking ciphers.
*** Cryptanalysis of Block Ciphers with Probabilistic Non-linear Relations of Low Degree Thomas Jakobsen. He applies a new result in coding theory (Sudan's algorithm for decoding Reed-Solomon codes beyond the error-correction diameter) to the cryptanalysis of block ciphers. His attack provides a way to attack ciphers whose round functions are approximately given by low-degree polynomials, improving on earlier work (Jakobsen and Knudsen's interpolation attack) which cryptanalyzes ciphers with round functions that are exactly given by low-degree polynomials. The use of low-degree round functions is motivated by their resistance to differential cryptanalysis, but Jakobsen's attack shows that these round functions are weak in their own way.
*** Differential Collisions in SHA-0, Florent Chabaud and Antoine Joux (Centre d'Electronique de l'Armement, France). The authors show how to find collisions in the initial version of the SHA hash function with complexity 2^61, a factor of 2^19 less work than the "birthday paradox" attack. Their attack does not work on SHA-1, the revised version of SHA, suggesting that the unexplained change in the US standard hash function was a correction of this weakness. Their attack is related to the differential cryptanalysis of block ciphers, and capitalizes on a lack of diffusion in SHA-0.
CRYPTOGRAPHY AND THE INTERNET
Steve Bellovin (AT&T Labs Research, USA) presented an invited lecture on the implementation and use of cryptography within Internet protocols. A full paper on the topic appears in the proceedings. A copy of his slides as well as other interesting information on network security, cryptography, etc., can be found on his Web page at http://www.rsearch.att.com/~smb.
Bellovin credited the current use of cryptography in protocols such as PGP, S/MIME, SSL, IPSec, and SET to faster CPU speeds that make the overhead of cryptography tolerable. He reviewed the current uses and limitation of cryptography in each of these protocols. PGP and S/MIME are both popular secure email protocols advancing in the IETF standards process, but still hampered by the lack of a widespread public key infrastructure (PKI). SSL is a general purpose mechanism mostly used for Web browser to server protection; it does have a PKI, but facilities for checking certificates are limited and rarely used by users; the dual of the email problem. IPSec is a network layer protocol that protects all transport protocols and application protocols that use transport protocols; IPSec protection can be applied to a user, a host or an entire network, but is currently being deployed and used mostly to protect firewall-to-firewall and remote-user-to-firewall communications; potential future use in end-systems will increase the need for an accompanying PKI. Finally, SET is a secure payment protocol allowing digitally signed orders among multiple parties consumers, banks, and merchants ostensibly eliminating the need to transmit credit cards numbers, though, Bellovin points out that, credit card numbers are still required as indices into databases.
Bellovin described three areas requiring further work. There is still a need for increased cryptography speed, especially of public key operations in servers handling many clients, and of keyed integrity check algorithms such as those used in IPSec. There is also a strong need for secure routing protocols. It is not clear how to use cryptography to protect routing information, and while there has been some work in this area, the ideal solution requires extensive use of digital signatures, which would be prohibitively expensive. Finally, an interesting research area is providing cryptographic security for multicast communications, which, despite several proposals, has proven difficult possibly due to the many different uses and trust models associated with multicast sessions.
Bellovin indicated that yet another area requiring work is the assignment of real world semantics to public key certificates. Also, of great importance and difficulty is the area of cryptographic engineering, which involves the difference between an academic paper that says encrypt a message M from A to B with a shared key K, and an implementation specification that says use a specific cipher, block size, mode of operation, IV, and key length in a specific interchange of messages. Secure protocols must handle secure negotiation of ciphers and their attributes. Security requirements can often be in conflict. Bellovin noted operational considerations produce challenges, citing examples with securing the Domain Name System (DNS) and with IPSec. He also expressed a need for more verification of cryptographic protocols and mechanisms used in the Internet, noting that, while verifying crypto protocols is hard enough, verifying real-world standards is much harder because of non-cryptographic features.
In closing, Bellovin emphasized that cryptography cannot solve all of the Internet's security problems, the Internet suffers from a lot of bad cryptography, and the user interface to cryptography in software is often lacking.
AES SPECIAL REPORT
Miles Smid (National Institute of Standards and technology, USA) presented a Special Report on the First AES Conference, which was held in Ventura, CA the week preceding CRYPTO '98. Smid reviewed the AES process, spoke about the conference, and outlined remaining plans. The conference was the first in a planned series of three conferences to be held to help NIST determine which algorithm to select for the AES. The conference gave attendees a first look at each of the candidate algorithms: LOKI97, RUNDAEL, CAST-256, DEAL, FROG, DFC, MAGENTA, E2, CRYPTON, HPC, MARCS, RC6, SAFER+, TWOFISH, and SERPENT. Smid invited formal comments on the algorithms, including how well they meet the NIST criteria, any related intellectual property issues, cross-cutting analysis of multiple algorithms, and overall recommendations, including underlying rationale for such recommendations. Comments should be submitted via email to aesfirstround@nist.gov. The Second AES Conference will be held in Rome, Italy on March 22-23, 1999. Additional information about the AES process, including the information on the candidate algorithms and the official schedule, can be found at http://www.nist.gov/aes.
During his special report, Smid provided some humor with his simple management strategy for developing AES.
DES to AES in Seven Easy Steps: 1. Convince NIST management that DES is no longer fully secure; 2. Convince NIST management that 3DES is not good enough to be AES; 3. Challenge the world's best cryptographers to give you algorithms; 4. Challenge world's best cryptographers to cryptanalysis the algorithms (doing that today!); 5. Avoid getting arrested for violating export laws; 6. Pray for consensus; and 7. If all else fails define AES = DES.
The CRYPTO '98 audience expressed it's admiration and appreciation to Smid for providing an open, international process for submitting and considering candidate algorithms.
In response to a question from John Gilmore (Electronic Frontier Foundation, USA) regarding the role of NSA in this process, Smid answered that he has advised NSA of what he is doing, that NSA is supportive of the process, and that contrary to any news reports, NSA has not tried to set the schedule or stop the effort. He also indicated that NSA has agreed to look at the five finalists, he hopes they all will be acceptable to NSA, and he would be uncomfortable if an algorithm is not acceptable to NSA.
IACR DISTINGUISHED LECTURE
*** Michael Rabin (Harvard University, USA and Hebrew University, Israel.) Proof of Plaintext Knowledge and (Deniable) Authentication. Rabin presented new results not represented by the extended abstract contained in the conference proceedings.
Encryption with proof of plaintext knowledge prevents captured ciphertext attacks, such as Bleichenbacher's attack on the SSL protocol using PKCS #1. Rabin presented an enhancement to a generic (semantically secure) public key encryption method, that provides it with a proof of plaintext knowledge (and retains its semantic security).
Deniable authentication enables Alice to authenticate a message to Bob in such a way that Bob cannot convince Carol that Alice ever authenticatted that message; Alice can deny to Carol that she ever saw the message. An example of where this is useful would be if Alice and Carol were buyers, and Bob were a seller. Alice can use deniable authentication on her offers to Bob in such a way that Bob cannot use them to bargain with Carol. Rabin presented an efficient way to do deniable authentication with provable security.
RUMP SESSION
The rump session is an informal session of impromptu talks, including recent technical results and possibly also presentations on politics, history, standards, and humor. The session was organized and moderated by Stuart Haber (Surety Technologies, USA.) This year, the rump session was unusually serious in nature, with most, if not all of the talks, very technical in nature. There were a large number of talks on attacks and cryptanalysis, as well as many talks on new schemes and ciphers. A few of the notable presentations on recent results in cryptanalysis are described here.
*** Adi Shamir, Alex Biryukov, and Eli Biham, presented Impossible Differential Attacks, Miss-in-the-middle Attacks on IDEA, and Impossible Cryptanalysis of SKIPJACK, respectively. This new approach to differential cryptanalysis uses "impossible differentials", that is, differentials which cannot appear in a plaintext/ciphertext pair, to eliminate keys from consideration and thus find the correct key. Such differentials can be found by finding differentials for the first half and the second half of a cipher that "miss in the middle", since their values do not match up. Biham used this new technique to break a 31-round version of the recently declassified SKIPJACK cipher (which is only one round away from the complete 32 round cipher). Check http://www.cs.technion.ac.il/~biham/Reports/SkipJack/ for a forthcoming report on this exciting result.
*** The Electronic Frontier Foundation's DES search engine was described by John Gilmore and Paul Kocher. The $210,000 machine, which heats up the room it runs in to 150 degrees Fahrenheit, can find DES keys in about three days. Ron Rivest, representing RSADSI, presented Gilmore with the $10,000 prize for their prompt solution. Matt Blaze was also on hand to give a much more modest prize to the winners of his DES challenge: find matching pairs of plaintext and ciphertext numbers, consisting of nothing but repeated digits. More information is available online at http://www.eff.org/descracker/.
*** An effort to build a machine that implements Hellman's time-memory tradeoff against DES was announced by Tsutomu Matsumoto. Information will become available at http://members.aol.com/pinebook as the project develops. IACR BUSINESS MEETING
The International Association for Cryptologic Research (IACR) is a non-profit scientific organization whose purpose is to further international research in cryptology and related fields. The main activities of the IACR include: running the two annual conferences -- CRYPTO, EUROCRYPT, and, beginning in 2000, ASIACRYPT; publishing the Journal of Cryptology; and publishing a semi-annual newsletter. Additional information about the IACR and its activities are available via the Web at http://www.iacr.org.
The IACR conducts an open business meeting at the CRYPTO conference. Of particular note during this business meeting:
*** The IACR newsletter is in the process of being changed over to a primarily electronic publication.
*** The 1998 election of new officers and 3 (out of 9) directors is underway.
*** The University of Calfornia at Santa Barbara (UCSB) has been contracted to function as the IACR Secretariat providing administrative and membership services for the IACR.
*** Efforts are underway to deal with the huge backlog of both submitted and accepted papers for the Journal of Cryptology.
*** Most notably, an electronic version of the IACR conference proceedings will soon be available. A CDROM will be published containing: all the CRYPTO and EUROCRYPT proceedings from 1981-19997 (32 volumes), including the UCSB Tech Report from 1981, the 1982 proceedings which were not published by Springer, and the 1986 pre-proceedings; a cumulative author index for all 1,275 papers; a keyword index; and a search capability via Java Applet. An accompanying book will contain title pages, the author index, listing of the program comittees, etc. The CDROM and book will be published by Springer as Volume 1440 in the LNCS series. It is expected to be available by the end of the year.