[an error occurred while processing this directive]Ecrypt II school

Student Presentation Session

Program of the student presentations is as follows:

Hristina Mihajloska, Quasigroups as a Tool for Construction of Optimal S-boxes.
Simona Samardjiska, The Multivariate Probabilistic Encryption Scheme MQQ-ENC
Oleksandr Kazymyrov, Prototype of Russian Hash Function "Stribog"
Emanuele Bellini, Design of an Elastic Block Cipher
Chiara Marcolla, Decoding Techniques for Affine-Variety Codes
Matteo Piva, The Rabin cryptosystem revisited
Pouyan Sepehrdad, Tornado Attack on RC4
George Argyros, Techniques and Tools for practical randomness attacks against PHP applications

Programme

NEW Click on the name of the speaker for abstract of the talks!

Sunday, 27 May 2012
20.00	Registration
20.00	Welcome reception

Monday, 28 May 2012
Algebraic Tools (I)
09:00-10:00	Gröbner Basis - Jean-Charles Faugère Solving polynomial equations is a fundamental problem; one of the most efficient method to solve polynomial systems in finite fields is to compute Gröbner bases. In this talk we review recent result in two directions: Efficient algorithms and linear algebra Efficient algorithms for computing Gröbner bases rely heavily on linear algebra techniques (F₄, F₅, FGLM, ...) . The matrices generated by these algorithms have unusual properties (sparse, almost block triangular, ...). For instance, by taking advantage of the sparsity of multiplication matrices in the classical FGLM algorithm we can design an efficient algorithm to change the ordering of a Gröbner basis. The algorithm is a related to multivariate generalization of the Wiedemann algorithm. Complexity of computing Gröbner bases Little is known about the theoretical and practical complexity of computing Gröbner bases of polynomial systems coming from (crypto) applications. Very often, polynomial systems occurring in applications have some additional structures: symmetries or multihomogeneous algebraic systems . Surprisingly this is the case in many cases in Algebraic Cryptanalysis: for instance the MinRank problem which is at the heart of the security of many multivariate public key cryptosystems such as HFE or the McEliece cryptosystem whose security is based on the hardness of decoding general linear codes are strongly related to multihomogeneous polynomial systems. In this talk we review several recent advances in this area.
10:00-11:00	Gröbner Basis: Selected Applications - Guénaël Renault In this talk, I will present applications of practical and theoretical tools coming from polynomial system solving theory. These applications will be presented in the context of studying algorithms for solving the discrete logarithm problem. Our main aim will be the study of the index calculus algorithm and the elliptic curve discrete logarithm problem.
11:30-12:30	Towards an era of Modern SAT solvers - Laurent Simon The history of SAT solvers is a long experimental and theoretical march from the early 60's. In this talk, we will retrace the history of SAT solvers, from the first, Davis-Putnam 1960 procedure, to the last developments of Modern SAT Solvers (CDCL), including a brief description of ROBDD and Stalmarck-based procedures. We will particularly show how the very recent history of Modern SAT solvers is pushing them towards more and more incompleteness. CDCL solvers are not backtrack search engines anymore.
12:30-15:00	Lunch
Algebraic Tools (II)
15:00-16:00	Many tools with SAT solvers - Laurent Simon Since the breakthroughs of Conflict-Driven Clause Learning algorithms, introduced in 2001, many practical and industrial tools are nowadays based on efficient SAT solvers. We will review some of the classical use of SAT solvers, including a brief description of the successful Lazy SMT framework, and give an intuition of the particular behavior of CDCL solvers on Cryptographic problems. We will also show how SAT solvers can be embedded as Oracles in some very efficient tools. Some new directions of improvements for those solvers, like the possible integration of GF(2) polynomials instead of clauses will be also presented.
16:30-17:30	Sage for Cryptographers - Martin Albrecht Sage is a large international project with the mission statement: "Creating a viable free open source alternative to Magma, Maple, Mathematica and Matlab." In this talk we will give an overview of Sage's capabilities with a particular emphasis on cryptographic applications.

Tuesday, 29 May 2012
Block Cipher Tools (I)
09:00-10:00	Block Cipher Cryptanalysis: Analyzing Sboxes - Gregor Leander In this lecture I will deal with the most important cryptographic criteria of Sboxes. After defining algebraic degree, non-linearity, differential uniformity and others I will focus on the algorithms to compute those and point out re-lations to coding theory. In the second part, I will be dealing with the notion of equivalence of Sboxes and in particular show how the most general notion of equivalence relates to equivalence of certain codes. This in turn allows to use known algorithms to check for this type of equivalence.
10:00-11:00	Block Cipher Cryptanalysis: Basic and Advanced Techniques (Part I) - Andrey Bogdanov Block ciphers are the essential building blocks of today's cryptography. The bulk parts of encryption and message authentication in the field are performed using block ciphers in some mode of operation. Moreover, unkeyed hash functions often base their designs on block cipher components. In this unit, consisting of two lectures (Part I and Part II), we will give a brief overview of attacks used to evaluate and cryptanalyze modern block ciphers accompanied by a more detailed insight into two state-of-the-art cryptanalytic techniques including meet-in-the-middle attacks using initial structures and linear cryptanalysis using approximations of correlation zero.
11:30-12:30	Block Cipher Cryptanalysis: Basic and Advanced Techniques (Part II) - Andrey Bogdanov
12:30-15:00	Lunch
Block Cipher Tools (II)
15:00-16:00	Mixed Integer Programming: Algorithms and Applications - Julia Borghoff Mixed integer linear programming (MIP) allows modeling of constrained optimization problem containing continuous and integer variables. In general mixed integer programming problems are difficult problems. However, MIP is extensively used in many industrial applications such as scheduling problems etc. meaning that there is a great interest in the development of efficient solvers. The existence of many good solvers makes MIPs interesting to cryptographers. The question we are asking is how can we use MIPs in cryptanalysis, what are the strengths and weaknesses of this approach. In this talk we will consider mixed integer programming and some basic algorithms in order to get a feeling how a specific problem should be modeled in order to be solvable. In the second part of the talk we will apply MIPs to cryptanalysis. Similar to algebraic attacks we use the description of a cryptographic primitive as a Boolean equation system as a starting point. We will focus on modeling a cryptographic problem as a MIP which includes tasks like converting Boolean equations into a set on real-valued inequalities, finding a suitable objective function etc. We will also discuss advantages and drawbacks of MIPs in cryptanalysis.
16:30-17:30	Cryptanalysis of Symmetric-Key Primitives: Automated Techniques + Presentation of the Tools for Cryptography website - Nicky Mouha So far, automated techniques have been largely unsuccessful in analyzing symmetric-key primitives. As stated by Martin Albrecht at last year's summer school: "Not a single proper block cipher has been broken using pure algebraic techniques faster than with other techniques." In this lecture, we investigate why such techniques have failed, and how we can avoid these problems. More specifically, this lecture focuses on Mixed-Integer Linear Programming (MILP) and SAT solvers, and shows how to apply them to the successful analysis of block ciphers and hash functions. In order to do this, we employ state-of-the-art techniques, that have either been published very recently, or will be introduced for the first time in this lecture. Furthermore, we also promote the ECRYPT II Tools for Cryptography initiative

Wednesday, 30 May 2012
Hardware/Software Tools
09:00-10:00	How Can I Run a Side-Channel Attack in Practice? Based on the true stories - Amir Moradi Having a successful side-channel attack practically running on a cryptographic device is always a challenging task. Difficulties and practical issues may prevent reaching a successful point. Although there exists no ready-to-use applications or tools to blindly month a side-channel attack, this talk provides some hints when dealing with such attacks especially power analysis. The points which are addressed by the talk are mainly experience-base while the appropriate solutions are scientifically confirmed. Two case studies, which are practical side-channel attacks on real-world devices, are used during the talk in order to clearly show the problems and the possible solutions.
10:00-11:00	Problem-Adapted, High-Performance Computation Platforms for Cryptanalysis - When Generic Is Not Good Enough - Ralf Zimmerman Cryptographic algorithms are a central building block of virtually every security systems. To estimate the actual security level of a crypto scheme, the best known attacks to the underlying problem are evaluated. As cryptanalytical methods constantly evolve with reduced complexity boundaries (i.e., memory and time complexity), attacks previously regarded as infeasible may come into reach of current technology. Special-purpose hardware for cryptanalysis -- or supercomputers to break a certain target -- hold the promise of a (dramatically) better cost-performance ratio compared to standard CPU implementations, and thus play an important role in the estimation of the security level. During this talk, we will take a look at different special-purpose platforms usable for modern cryptanalysis and gain an understanding of the capabilities and drawbacks, as well as of the problems we encounter when comparing implemented attacks on different technologies. In the end, we will discuss about suitable combinations.
11:30-13:00	Student Session
13:00-15:00	Lunch
15:00-20:00	Free Afternoon
20:00	Banquet

Thursday, 31 May 2012
Hash Function Tools
09:00-10:00	Basic Tools for Hash Function Cryptanalysis - Bart Preneel This talk starts with an overview of attacks on hash functions including (2nd) preimage attacks and collisions attacks; we also consider memoryless variants and variants for multiple targets (time/memory tradeoffs). Next we discuss attacks on the chaining mode of hash functions, such as meet-in-the-middle attacks, multi-collision attacks, long message attacks and herding attacks. We conclude by discussing attacks on hash functions based on block ciphers and hash functions based on permutations.
10:00-11:00	A Tool for Studying Differential and Linear Propagation in Keccak-f-Joan Daemen KeccakTools is a set of C++ classes aimed at assisting the analysis and efficient implementation of Keccak. It has support for a wide range of functions, from the investigation of differential and linear propagation and the generation of equations for algebraic attacks to the automated generation of optimized code. In the talk I will particularly address our approach to obtain lower bounds on the weight of differential trails using the classes available in KeccakTools. In this approach, we exhaustively generate all 3-round trails below a given weight. This allows us to prove bounds on the weight of 6-round differential trails.
11:30-12:30	Using Coding Theory for Hash Function and Block Cipher Cryptanalysis - Christian Rechberger Finding differential characteristics/trails/paths as needed for differential cryptanalysis of hash functions and ciphers can be linked to a problem in coding theory: finding low-weight codewords in a code. We describe this link, survey the literature and the tools used, and give examples.
12:30-15:00	Lunch
Coding Theory Tools
15:00-16:00	A Tool for Differential Cryptanalysis of ARX Based Hash Functions-Florian Mendel In this talk, we discuss how to construct complex differential characteristics in ARX based hash functions. Note that such characteristics are an important part of many collision attacks including the attacks on SHA-1 and the recent attacks on SHA-256. In this talk, we will review current techniques and discuss their limitations when applied to SHA-256. Due to the more complex structure of SHA-2 (compared to MD5 or SHA-1) several new problems arise. We show how to overcome these difficulties and present the first results (regarding the collision resistance of SHA-256) since the beginning of the NIST SHA-3 competition. We show how to extend the previously best known collision attacks on SHA-256 compression function from 24 to 32 (out of 64) steps and present a collision attack for 27 steps of the hash function. All attacks are of practical complexity. Then, we show that the same techniques/tools can be used to attack simpler hash functions like RIPMD-128, leading to attacks on up to 48 (out of 64) steps of the hash function significantly improving upon previous results.
16:30-17:30	Grow and cut: Using Representations in Cryptanalysis Application: An Improved Generic Decoding Algorithm - Alexander Meurer In this talk, we will introduce a powerful combinatorial technique introduced by Howgrave-Graham and Joux at Eurocrypt 2010. In simplifed terms, this technique can be stated as the following "Grow-and-Cut" paradigm: Start from a search space H that contains a unique solution N Expand H into a larger space H in a way that introduces r many equivalent representations N1, ... , Nr of the original soultion N Cut down H and focus only on a 1/r-fraction in order to find at least one copy Ni with constant probability The main technical issue of this approach is then to find an efficient procedure that allows to compute a 1/r-fraction of H without doing the complete expansion of H beforehand. We will exemplarily apply this technique to the well-known subset-sum problem and the bounded distance decoding problem for random binary linear codes. In both cases, the technique yields the asymptotically fastest algorithms to date. We conclude by highlighting further applications (like an improved combinatorial attack for NTRU cryptosystem).

Friday, 1 June 2012
Linear Algebra
09:00-10:00	Linear Algebra I - Clément Pernet This talk is about a collection of algorithmic and implementation techniques that we found of prime importance when dealing with the computation of triangular matrix decompositions and other normal forms arising in exact linear algebra. After setting algorithmic relations between most common gaussian elimination based matrix factorizations and normal forms, we will propose a set of reductions between all these computations justified by time and space complexity analysis.
10:00-11:00	Linear Algebra II - Clément Pernet We will give an overview of the various frameworks for parallel programming with application from intensive exact linear algebra in mind: parallel loops, fork-join model and data-flow model. We will compare these frameworks, illustrated by some well-known languages, such as OpenMP, Cilk, IntelTBB or Kaapi, from the point of view of the language, the ability to express parallelism and the runtime efficiency.
11:30-12:30	Algorithms & Techniques for Dense Linear Algebra over Small Finite Fields - Martin Albrecht In this talk we will review known techniques for realising efficient linear algebra over small finite fields. In particular, we will focus on GF(2), GF(2^e) as well as GF(p) and GF(p^k) for very small primes. Where applicable we will also discuss available software packages realising these techniques.
12:30-15:00	Lunch