Review of the
Santa Barbara, CA, USA
August 17-21, 2003
Review by Richard Schroeppel
September 15, 2003
"Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Grobner Bases", by Antoine Joux and Jean-Charles Faugere, presents more efficient algorithms for computing Grobner bases. They find that HFE cryptosystems generate systems of quadratic equations that are easier to solve than random systems of the same size, and conclude that HFE-based systems can be cryptanalyzed in polynomial time when the degree of the secret polynomial is fixed. Although the security estimates for HFE must be revised downward, repair may be possible by increasing parameter sizes.
The first invited talk was "Cryptographic Assumptions and Challenges" by Moni Naor. The security of common cryptographic primitives rests on the assumed difficulty of various hard problems. Naor presents a new scheme for classifying these cryptographic assumptions, based on the difficulty of falsification. He examines the logic of challenge problems, and the costs of checking solutions to challenges. He proposes several meta-problems, such as constructing a competitive block cipher based on an efficiently falsifiable assumption.
"A Polynomial Time Algorithm for the Braid Diffie-Hellman Conjugacy Problem", by Jung Hee Cheon and Byungheup Jun, develops an attack on the straightforward braid-group key exchange. Their new algorithm begins by converting the braid problem into a linear algebra problem, using the Lawrence-Krammer representation of the braid group. They simplify the linear algebra problem, and apply Gaussian elimination, eventually recovering a pseudo-key, equivalent to Alice's secret key. The complexity is O(N^14) for braid-index N. The attack is based on the group structure, and fails against some braid group key agreement methods that depart from the group structure.
"Cryptanalysis of SAFER++", by Alex Biryukov, Christophe De Canniere, and Gustaf Dellkrantz, presents several attacks. The best result breaks 5.5 rounds of SAFER++. (The actual cipher is 7 rounds.) The attacks use either multisets (like the Square attack), or a nice application of Wagner's boomerang. The attacks take advantage of some algebraic properties of the SAFER sboxes. A three-round version of the multiset attack is practical, and was implemented and tested.
"Primality Proving via One Round in ECPP and One Iteration in AKS", by Qi Cheng, is another improvment on the polynomial-time prime proving algorithm discovered last year by Agrawal, Kayal, and Saxena. The key idea: Berrizbeita discovered a subset of cheaply-provable primes. Cheng has expanded the subset. A general B-bit prime can be proven in heuristic time roughly O(B^4), by using one round of Elliptic Curve Prime Proving to reduce the general prime to a cheaply-provable prime. The new algorithms are still less efficient than existing heuristic probable-prime tests, but a remarkable amount of progress has been made in the year since AKS was discovered.
"Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication", by Elad Barkan, Eli Biham, and Nathan Keller, introduces several new attacks against cell phone ciphers and protocols. The attacks are very practical, with simulations taking less than a second on one PC. Once again, the risks of non-publicly- vetted encryption are apparent.
The Rump Session talk "Analysis of an electronic voting system", by Yoshi Kohno, Adam Stubblefield, Avi Rubin, and Dan Wallach, sketched out some problems with Diebold voting machines. The audience reaction ranged from incredulity to wild laughter. Details of the analysis are available at http://avirubin.com/vote.