Edition nr 2 December 2006

Welcome to the second edition ofthe Ecrypt newsletter. We wish all of you a merry Christmas and a happy 2007! The next edition of the electronic newsletter will be available in July 2007.

For those readers who are not familiar with the ECRYPT network: ECRYPT stands for European Network of Excellence for Cryptology and it is a 4-year network of excellence funded within the Information Societies Technology (IST) Programme of the European Commission's Sixth Framework Programme (FP6) ECRYPT was launched on February 1st, 2004 and runs for 4.5 years. Its objective is to intensify the collaboration of European researchers in information security and more in particular in cryptology and digital watermarking.

Who is this newsletter for? This newsletter is meant for all partners involved in ECRYPT. But the focused audience is much broader than partners only. A whole research community focusing on cryptography and watermarking will find interesting information in it. This newsletter is particularly of interest to those with intentions of attending ECRYPT workshops and schools.

What can you find in the ECRYPT newsletter? You will be kept up to date on all latest developments within ECRYPT. Interesting documents will be presented as well as short reports on past visits within the network. Upcoming events will be clearly announced. If you missed out of some past events you will be able to read the event report. Eventually, some space will also be devoted to a more elaborate introduction of one of the 32 ECRYPT partners in the section partner of the month.

Coordinators Corner
ECRYPT consists of 32 leading players in the field of cryptography and watermarking. Katholieke Universiteit Leuven takes up the role of project coordinator.

ECRYPT participated in the IST 2006 event held in Helsinki 21-23 November 2006

IST 2006 was organized within the framework of the Finnish Presidency of the European Union by the European Commission's Directorate-General for the Information Society and Media, the Finnish Ministry of Trade and Industry and Tekes, the Finnish Funding Agency for Technology & Innovation.

Approximately 4,500 delegates participated in the event. IST 2006 had one overriding aim: to help achieving Europe's innovative potential in developing and rolling out Information and Communication Technologies (ICTs

The Conference Programme opened with a first day devoted to policy discussions on what governments and public policy can do to help ICT contribute to an innovative Europe, with Days Two and Three were devoted to the Seventh Framework Programme and other topics surrounding European research and innovation. 
Security was one of the spotlights during the IST event. The ECRYPT network had been asked to coordinate one of the Security networking sessions, Crypto: next steps and challenges.

Crypto: next steps and challenges. Organiser: Prof. Bart Preneel (Katholieke Universiteit Leuven, Belgium)

In this session, an industry perspective was offered by Prof. Jacques Stern (ENS, Paris, France) and Prof. Pim Tuyls (Philips Research, the Netherlands).  Prof. Stern discussed crypto in the financial and government sector; he offered a historic perspective and discussed the state of the art in several areas of cryptography. Prof. Tuyls focused on crypto in an industrial and health care environment; he used as example Physically Uncloneable Functions (PUFs) for secure hardware and multi-party computation for a health care environment.  Subsequently Prof. Jean-Jacques Quisquater (Université Catholique de Louvain, Belgium) gave a talk – in collaboration with Prof. Christof Paar (Ruhr-University Bochum, Germany) – on security in embedded systems with as major challenges secure implementations of cryptography and the integration of trusted computing.  Dr. Patrick Bas (CNRS and Institut National Polytechnique de Grenoble, France) discussed the challenge of robust watermarking, the combination of authentication, forensics and steganalysis and the integration of cryptography and watermarking.  Finally Dr. Romain Alléaume (ENST, Paris, France) presented the status of the SECOQ project and discussed the research challenges in quantum cryptography. These challenges include the use of information-theoretic tools from cryptology and the use of new network protocols; he stressed the usefulness of quantum key distribution for closed networks and the importance of a close collaboration with “classical” cryptography.

Subsequently a short panel discussion was held in which the following points were raised.  There are clearly important research challenges in cryptography; better trade-offs need to be developed between long term provable security, low power and low footprint implementations and very high performance.  In addition, there is a need for more advanced techniques in particular those that create an interaction between the physical/paper world and the on-line world (e-voting, PUFs, paper money); complex protocols still present a major challenge for example w.r.t. composability.  In addition, there are still problems with the effective deployment of basic cryptographic techniques; there are in part related to usability and to economic factors.  Secure implementations, that is, implementations resistant against active and passive side channel attacks and against probing attacks is still an active research area.  The area of watermarking and quantum cryptography have made significant progress, but there are still major challenges; some of these can be addressed by a closer collaboration with researchers in cryptography.

Visits Reports
ECRYPT stimulates short visits to, from, and within ECRYPT to promote integration. The main purpose of these exchanges is not educational: both the visitor and the host have a considerable knowledge in the technical field discussed during the visit. You can read the reports of the most recent visits below.

Are you an ECRYPT partner and want to host a visitor? Apply for funding here.

ENS hosts Damien Stehlé (University of Sydney, Australia)
Visit duration: 2-15 May 2006

Damien Stehlé worked on lattice reduction algorithms with Phong Nguyen and Nicolas Gama. Lattice reduction is the most popular technique in public-key cryptanalysis (WG2). We discussed potential extensions to the recent work done by Gama, Howgrave-Graham, Koy and Nguyen, which was published at CRYPTO 2006 (title "Rankin's Constant and Blockwise Reduction"). Nguyen and Stehle worked on a long journal version of the work "Low-Dimensional Lattice Reduction Revisited" (published at the ANTS-VI conference), which we submitted to the "ACM Transactions on Algorithms" journal at the end of the visit. Nguyen and Stehle also started to work on a journal version of the work "Floating-Point LLL Revisited" (published at the EUROCRYPT 2005 conference): the title will be "An LLL Algorithm with Quadratic Complexity".

ENS hosts Eike Kiltz (CWI, Amsterdam, The Netherlands)
The visit took place in May 2006

Eike Kiltz visited the crypto team at ENS from May 15th to May 21st 2006 to work with Michel Abdalla and Gregory Neven on generalizations and extensions of the concept of hierarchical identity-based encryption. During this visit, two research directions were explored: identity-based encryption with wildcard key derivation (WKD-IBE) and set-based encryption. In WKD-IBE, more general key delegation patterns are allowed by associating secret keys with vectors of identity strings, where entries can be left blank using a wildcard. Such keys can then be used to derive keys for any pattern that replaces wildcards with concrete identity strings. In set-based encryption, identities are seen as unordered sets of bit strings rather than vectors. Key derivation allows anyone who knows a key corresponding to a given set to derive keys for any superset of that set (i.e., you can always add elements to the set to which your key is associated). A ciphertext encrypted for a given set can only be decrypted by someone having a key for at least one of its subsets. This research has already led to a joint paper which was submitted to PKC 2006. In addition to the collaborative work, Eike also gave a talk on chosen-ciphertext security based on tag-based encryption as part of the cryptography seminar.

IAIK hosts Yossi Oren (Weizmann Institute, Israel)
Visit duration: 28-31 August 2006

In the last week of August 2006 Yossi Oren (Weizmann Institute, Israel) visited the Institute for Applied Information Processing and Communications (IAIK) of Graz University of Technology. Yossi is a Master Student of Adi Shamir and he is working on power analysis attacks on UHF RFID tags. His work has received a lot of attention after Adi Shamir announced the first successful attacks at RSA conference 2006. During the visit at IAIK, Yossi gave three presentations: "Remote Power Analysis of RFID Tags", "Remote Power Analysis of RFID Tags - Toys, Tools and Techniques", and "How not to Protect PCs from Power Analysis". Furthermore, he was working together with members of the Side-Channel Analysis Lab at IAIK to perform attacks on UHF and on HF RFID tags. It was possible to successfully combine the UHF experience of Yossi and the HF experience of IAIK. Due to this success, there is the plan to continue working together in this field.

University of Salerno hosts Moti Yung (Columbia University, NY - USA)
Visit duration: 4 – 12 September 2006

Moti Yung, a well-known and distinguished researcher in the area of Cryptology, has visited the Universita' di Salerno during the month of September 2006 for about one week. Moti is a long-time collaborator of the Crypto group in Salerno with the first joint publication dating back to more than 15 years ago. During this visit has interacted with several members of the departiment on common research interests. Specifically, we have discussed the recent developments in the theory of Zero Knowledge in the Bare Public Key Model. Indeed recently it has become evident that Internet-based applications require, at least, a notion of security that is preserved under concurrent composition. This has motivated a line of research that tries to construct efficient Concurrent Zero Knowledge. Even though constant-round concurrent zero-knowledge arguments are known for the Bare Public Key model, these construction cannot be deemed practical. The question of unconditionally secure protocol that remain secure even if concurrently executed was also discussed and we noticed that very few results on this important area (as opposed to the computational case) are known. The discussion touched upon Non-Interactive Zero Knowledge.

KULeuven hosts Thomas Shrimpton ( Portland State University, OR, USA)
Visit duration: 11– 15 September 2006

The premier goal of a cryptographic hash function is collision-resistance. In the light of recent collision attacks on popular hash functions however, it makes sense to have a closer look at alternative (and possibly easier to achieve) security properties that may suffice for certain applications. Seven such properties were formally defined by Rogaway and Shrimpton at FSE'04, including collision-resistance and three variants of each of preimage and second-preimage resistance.

Most practical hash functions used today employ the Merkle-Damgard iteration to transform a (fixed input length) compression function into a hash function for arbitrary-length messages. The main design rationale behind it is that the iterated hash function inherits the collision-resistance of the underlying compression function. No such guarantees are known for the other six security properties however. We decided to invite an expert on the matter, Tom Shrimpton, for a week of joint research in sunny Leuven (no kidding) to clear up these issues.

We soon found that of the seven security properties put forward by Rogaway-Shrimpton, the Merkle-Damgard iteration only preserves two. Moreover, of the multitude of alternative iterations proposed in the literature, we couldn't find any that preserves all seven notions. This led us to the design of a new iteration called Randomized Mask-then-Compress (RMC) that is the first to provably preserve all seven notions. It is a seeded (i.e., randomized) iteration that, quite controversially, employs a random oracle to generate mask values and padding bits. This random oracle is only called a logarithmic number of times however, and has a short input length. For example, to hash a message of 264 bits, RMC needs about 56 calls to a random oracle with a 500-bit input, which could be instantiated using a block cipher like AES. More details on our results can be found in report STVL4-KUL14-RMC-1.0 on the ECRYPT-STVL archive.

UNIGE hosts Mariam E. Haroutunian (Institute for Informatics and Automation
Problems of the Armenian National Academy of Sciences, Armenia)
Visit duration: 25 September – 1 October 2006

Mariam E. Haroutunian (Institute for Informatics and Automation Problems of the Armenian National Academy of Sciences, Armenia) visited University of Geneva in the last week of September 2006. She gave the talk "On broadcast data hiding" during a seminar of Computer Science Department. M. Haroutunian is one of the leading researchers in the field of information-theoretic analysis of digital data-hiding and watermarking. Besides the joint work on the information-theoretic analysis of error exponents of the geometrically-robust structured data-hiding codes, a number of achievments have been reported in the perceptually-robust hashing for authentication, reversibility analysis of digital data-hiding and security leackage characterization of binning codes. On top of that Mariam has participated to WaCha2006 workshop organized by ECRYPT in conjuction with the ACM Multimedia and Security Workshop in Geneva. The future plans concern preparation of several joint papers and contribution to the preparation of the special issue of EURASIP Journal on Information Security dedicated to the robust visual hashing.

IBM hosts Dan Dobre (TU Darmstadt, Germany)
Visit duration: 3 days in early October 2006

IBM hosted Dan Dobre of TU Darmstadt for a 3-day research visit in early October 2006. The goal of the visit was to engage in a collaboration on latency-efficient atomic broadcast protocols in distributed systems. Such protocols disseminate a sequence of messages in a group of n nodes linked by an asynchronous network, despite the actions of some nodes that may be faulty or misbehave in arbitrary ways. The collaboration has led to a series of improvements to the state of the art, in particular, for protocols that generate only O(n) messages during failure-free executions. These results are currently being submitted to a conference. The common interest in the topic had been identified before, at a seminar in Schloss Dagstuhl with the title "From Security to Dependability". Dan Dobre is a graduate student at the Department of Computer Science at TU Darmstadt (Germany).

Workshops&Schools Reports
ECRYPT organises yearly numerous schools and workshops. These schools and workshops bring many researchers together in Europe and therefore are an excellent means for integration and dissemination. You can read the reports of the most recent workshops and schools below.

Summer School on Zero Knowledge: Foundations and Applications
October 28-November 3, 2006, Bertinoro, Italy
Organizer: University of Salerno (UNISA) on behalf of PROVILAB


The purpose of this school was to give PhD students and others with a general interest in cryptography a deeper understanding of the notion of zero knowledge and of its use in cryptography. The main subjects covered were commitment schemes, interactive witness indistinguishable and zero-knowledge proof systems, proofs of knowledge, round complexity, non-black-box techniques, NIZK and ZAP, malleability and concurrency, secure encryption. The school featured 8 lectures (each 3 hours long) and a student session.

Speakers were Jonathan Katz from University of Maryland (USA), Yehuda Lindell from Bar-Ilan University (ISRAEL) and Giuseppe Persiano from University of Salerno (ITALY) that also was the school director. ECRYPT grants for the participation have been offered to students from non-ECRYPT institutions. We had 38 participants, of which 6 were female, and 23 were from non-ECRYPT institutions. The non-EU countries represented include Australia, Canada, Israel, Kuwait, Turkey, U.S.A.Participants engaged in deep discussions about the topics of the school and this yielded a positive burst of energies.

Workshop on Watermark Security and Benchmarking
(also known as 2nd WAVILA Challenge or WaCHa 06)
September 28, 2006, Geneva, Switzerland
Organizer: University of Geneva and University of Magdeburg on behalf of WAVILA

The workshop focused on the two questions: 1. Is knowledge of the watermarking algorithm useful for watermark removal? 2. How does the output of the optimal watermarking algorithm look like? The first question was aimed on watermark security since some recent analysis seem to point out that if the aim of the attacker is limited to watermark removal, or to make it unreadable to the detector/decoder, knowledge of the watermarking algorithm is of limited, if any, help. The second question was intended to compare different metrics and visualisation techniques for a possible application in a fair watermarking benchmarking for selected application scenarios.

The Programme committee consisted of:

Mauro Barni (National Inter-University Consortium for Telecommunications, Italy)
Patrick Bas (Centre National de la Recherche Scientifi que, France)
Christian Cachin (IBM Research GmbH, Switzerland) Jana Dittmann (Otto-von-Guericke University Magdeburg, Germany)
Andreas Lang (Otto-von-Guericke University Magdeburg, Germany)
Fernando Perez-Gonzalez (University of Vigo, Spain) Sviatoslav Voloshynovskiy (University of Geneva, Switzerland)

Number of participants: 42

Highlights in the programme and results: As highlights of the programme the two invited talks by Scott Craver (Assistant Professor, Department of Electrical and Computer Engineering at Binghamton University, New York, USA) and Teddy Furon (Researcher at the INRIA Institute, Rennes, France) have to be mentioned. While the first invited talk did fit very well into the actual discussion on the results from the first BOWS contest, the second one asked critical questions on the significance of benchmarking results for the real world application. From both invited talks as well as from the presented papers sparked the lively discussions which are the trademark of the WaCha.

Partner of the Month
In every newsletter one of the 32 ECRYPT partners will be put in the spotlight. In this newsletter we focus on RUB, Ruhr-University Bochum in Germany.
Who is involved in ECRYPT at RUB?

There are four groups at the Ruhr University Bochum which are active in ECRYPT. The group of Christof Paar is working on embedded security and is very active in VAMPIRE and to a lesser extent in STVL and AZTEC. Ahmad Sadeghi's group is internationally known for its work in trusted computing and protocols. Their main Virtual Lab is PROVILAB. Jörg Schwenk heads the network and data security group and has a lot of activities in PROVILAB. In Bochum's mathematics department, Roberto Avanzi and Gregor Leander are working in AZTEC and STVL, respectively. All together, there are about 30 full-time researchers working in cryptography and security at RUB.

In which virtual labs is RUB most active?

RUB coordinates the VAMPIRE lab. Since we have a large research group at RUB which works almost solely on VAMPIRE topics, this has arguably be our most active virtual lab.

What did RUB accomplish within ECRYPT?

We are proud of the establishment of the SHARCS (Special Purpose Hardware for Attacking Cryptographic Systems) workshop series. It took place twice so far, in 2005 in Paris and in 2006 in Cologne. This is an important emerging area within cryptography, and we feel that ECRYPT has done a valuable service to the international cryptographic community by establishing this workshop series. SHARCS 07 is scheduled to run in conjunction with CHES in September, and we expect much interest from the international community. Dissemination of knowledge is also of importance for us. We organized the School on Elliptic Curve Cryptography and are maintaining lounges.

What did RUB gain from being part of the ECRYPT network?

First, like everyone else, we really profit from being part of the network of top cryptography groups in Europe. After three years, there seems to be a real "we" feeling among the ECRYPT partners which makes cooperation and joint research possible. In particular, the possibility to do interdisciplinary work has improved and expanded our research. Second, we think that ECRYPT is an excellent platform for launching new workshop (series) in emerging areas. Our research truly benefited from the SASC, RFIDSec, and SHARCS workshop series.

What are your plans for the future?

We are currently working on strengthening the topic of trusted computing within ECRYPT. In the summer of 2007 we are planning an ECRYPT workshop in this area in Bochum, which will be joint event of PROVILAB and VAMPIRE. We are also getting more involved in the eSTREAM project by focusing on hardware and embedded software implementation.

Event Announcements
  The State of the Art of Stream Ciphers - SASC 2007

Bochum, Germany

  Date: January 31 - February 1, 2007
  url: http://sasc.crypto.rub.de/index.html
  Special WAVILA session on BOWS at SPIE 2007
  Place: San José, USA
  Date: January 31 2007
  url: http://electronicimaging.org/program/07/conferences/index.cfm?fuseaction=6505
  Workshop on Cryptographic Protocols
  Place: Bertinoro, Italy
  Date: March 4-9 2007
  url: Link will soon be announced
  Design Automation and Test in Europe - DATE 2007
1 Day devoted to Cryptographic Hardware
  Place: Nice, France
  Date: April 20 2007
  url: http://www.date-conference.com/
  Algorithm Design School & Hash Functions event
  Place: Samos, Greece
  Date: April, 30 - May 4 2007
url: Link will soon be announced
  Low-Cost and Lattice-Based Cryptology  - LLL+25 2007
  Place: Caen, France
  Date: June 28 - July 1st 2007
url: Link will soon be announced
  SHARCS 2007
  Place: Vienna, Austria
  Date: September 9-10

Breaking SFLASH
by Jacques Stern (ENS)

Cryptanalysis of the SFLASH family of signature schemes
Article by Vivien Dubois (ENS), Pierre-Alain Fouque (ENS), Adi Shamir (Weizmann & ENS), and Jacques Stern (ENS)

SFLASH is a signature scheme which belongs to a family of multivariate schemes called C*- proposed by Patarin et al. in 1998. The SFLASH scheme itself has been designed in 2001 and has been selected in 2003 by the NESSIE European Consortium as the best known solution for implementation on low cost smart cards.

SFLASH is based on the Matsumoto-Imai (MI) scheme. This scheme uses exponentiation in a finite field of dimension n over a (binary) field Fq, and two trapdoor functions that are affine maps. It has been broken by Patarin in 1995. However, based on an idea of Shamir, Patarin et al. proposed to remove a significant number of equations from the public key. This completely avoids the previous attack.

We are able to break all C*- schemes. There are two different cases to consider depending on whether the kernel of the linear map XX+X qθ is nontrivial, where θ is a parameter, which controls the exponent qθ +1 of the MI scheme.

The first method allows to break the scheme when the above kernel is nontrivial, even if a proportion 1-1/gcd(θ,n) of the equations are removed. It can be seen that this proportion is at least 1/2, and close to 1 in some cases.

The second method allows to break the scheme when the above kernel is trivial, if at most one half of the equations are removed.

The attack uses simple linear algebra. It allows to forge a signature for an arbitrary message in a few minutes for practical parameters, using only the public key. The attack has been fully implemented and can break SFLASH v2 which has been accepted by NESSIE, as well as SFLASH v3 which has been also proposed by the designers.

To unsubscribe to the Ecrypt newsletter click here and mention unsubscribe in subject