Keynote Speeches
 Keynote Speech I
Title: Sound and Fine-grain Specification of Cryptographic Tasks
Speaker: Juan Garay - AT&T Labs - Research (www.research.att.com)
Abstract: In recent years there has been an interest in the design of cryptographic protocols satisfying strong security properties, such as (preservation of security under) concurrency and non-malleability. The Universal Composability (UC) framework of Canetti fulfills that interest, by guaranteeing that if a protocol is able to emulate an ideal specification of the task (called a "functionality" in the framework -- e.g., signature, public-key encryption, zero-knowledge proof, etc.), then those properties are achieved. However, while the traditional (non-UC) security notions of many tasks have been studied for a while and are well understood, their UC formulation does not seem to be an easy task, as demonstrated by the coexistence of complex, multiple functionalities for the same task as well as by their "unstable" nature.

In this talk, we propose a general methodology for the translation of the traditional, game-based security definitions to their UC counterpart, which besides the sound specification of cryptographic tasks, allows for the easy identification of relations between functionalities, as well as the "debugging" of existing ones. Instrumental in our methodology is the new notion of a "canonical functionality class" for a cryptographic task which is endowed with a bounded semilattice structure. This structure allows the grading of functionalities according to the level of security they offer as well as their natural joining, enabling the modular combination of security properties.

This is joint work with Aggelos Kiayias and Hong-Sheng Zhou (UConn).

 Keynote Speech II
Title: Cryptanalysis on MACs
Speaker: Xiaoyun Wang - Tsinghua / Shandong University, China
Abstract: We explore the first distinguishing attack on HMAC/NMAC-MD5 without the related-key settings by detecting an inner near-collision in the first iteration. The attack needs 2^97 queries, with success probability 0.87, while the previous distinguishing attack on HMAC-MD5 reduced to 33 rounds takes 2^126.1 messages with success rate 0.92. Furthermore, we give the distinguishing and partial key recovery attacks on MD5-MAC, which can recover one 128-bit subkey with 2^97 queries.

Recently, this attack is extended to a new distinguisher which works for secret-prefix MAC with length prepended to the message before hashing. We introduce new techniques to detect an inner near-collision in the first round by birthday attack. Once the inner near-collision is identified, we can recognize the instantiated MAC from MAC with a random function. The complexity for distinguishing such a MAC with 43-step reduced SHA-1 needs 2^124.5 queries. For MAC with 61-step SHA-1, the complexity is up to 2^154.5 queries. The success probability of these attacks is 0.70.

Moreover, these attacks are applicable to distinguishing and forgery attacks on other MACs, such as MAC construction ALRED and its AES-based instance ALPHA-MAC.