Student Presentation Session
Program of the student presentations is as follows: Hristina Mihajloska, Quasigroups as a Tool for Construction of Optimal Sboxes.
 Simona Samardjiska, The Multivariate Probabilistic Encryption Scheme MQQENC
 Oleksandr Kazymyrov, Prototype of Russian Hash Function "Stribog"
 Emanuele Bellini, Design of an Elastic Block Cipher
 Chiara Marcolla, Decoding Techniques for AffineVariety 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
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:0010:00 
Gröbner Basis  JeanCharles 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:


10:0011: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:3012: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, DavisPutnam 1960 procedure, to the last developments of Modern SAT Solvers (CDCL), including a brief description of ROBDD and Stalmarckbased 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:3015:00 
Lunch 

Algebraic Tools (II)  
15:0016:00 
Many tools with SAT solvers  Laurent Simon
Since the breakthroughs of ConflictDriven 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:3017: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:0010: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, nonlinearity, differential uniformity and others I will focus on the algorithms to compute those and point out relations 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:0011: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 stateoftheart cryptanalytic techniques including meetinthemiddle attacks using initial structures and linear cryptanalysis using approximations of correlation zero. 

11:3012:30 
Block Cipher Cryptanalysis: Basic and Advanced Techniques (Part II)  Andrey Bogdanov 

12:3015:00 
Lunch 

Block Cipher Tools (II)  
15:0016: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 realvalued inequalities, finding a suitable objective function etc. We will also discuss advantages and drawbacks of MIPs in cryptanalysis. 

16:3017:30 
Cryptanalysis of SymmetricKey Primitives: Automated Techniques
+ Presentation of the Tools for Cryptography website  Nicky Mouha So far, automated techniques have been largely unsuccessful in analyzing symmetrickey 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 MixedInteger 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 stateoftheart 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:0010:00 
Having a successful sidechannel 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 readytouse applications or tools to blindly month a sidechannel attack, this talk provides some hints when dealing with such attacks especially power analysis. The points which are addressed by the talk are mainly experiencebase while the appropriate solutions are scientifically confirmed. Two case studies, which are practical sidechannel attacks on realworld devices, are used during the talk in order to clearly show the problems and the possible solutions. 

10:0011:00 
ProblemAdapted, HighPerformance 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. Specialpurpose hardware for cryptanalysis  or supercomputers to break a certain target  hold the promise of a (dramatically) better costperformance 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 specialpurpose 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:3013:00 
Student Session 

13:0015:00 
Lunch 

15:0020:00 
Free Afternoon  
20:00 
Banquet 
Thursday, 31 May 2012  
Hash Function Tools  
09:0010: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 meetinthemiddle attacks, multicollision 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:0011:00 
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 3round trails below a given weight. This allows us to prove bounds on the weight of 6round differential trails. 

11:3012: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 lowweight codewords in a code. We describe this link, survey the literature and the tools used, and give examples.  
12:3015:00 
Lunch 

Coding Theory Tools  
15:0016:00 
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 SHA1 and the recent attacks on SHA256. In this talk, we will review current techniques and discuss their limitations when applied to SHA256. Due to the more complex structure of SHA2 (compared to MD5 or SHA1) several new problems arise. We show how to overcome these difficulties and present the first results (regarding the collision resistance of SHA256) since the beginning of the NIST SHA3 competition. We show how to extend the previously best known collision attacks on SHA256 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 RIPMD128, leading to attacks on up to 48 (out of 64) steps of the hash function significantly improving upon previous results. 

16:3017: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 HowgraveGraham and Joux at Eurocrypt 2010. In simplifed terms, this technique can be stated as the following "GrowandCut" paradigm:

Friday, 1 June 2012  
Linear Algebra  
09:0010: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:0011: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, forkjoin model and dataflow model. We will compare these frameworks, illustrated by some wellknown 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:3012:30 
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:3015:00 
Lunch 