Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. EPFL thesis
  4. Algebraic Cryptanalysis of Deterministic Symmetric Encryption
 
doctoral thesis

Algebraic Cryptanalysis of Deterministic Symmetric Encryption

Sušil, Petr  
2015

Deterministic symmetric encryption is widely used in many cryptographic applications. The security of deterministic block and stream ciphers is evaluated using cryptanalysis. Cryptanalysis is divided into two main categories: statistical cryptanalysis and algebraic cryptanalysis. Statistical cryptanalysis is a powerful tool for evaluating the security but it often requires a large number of plaintext/ciphertext pairs which is not always available in real life scenario. Algebraic cryptanalysis requires a smaller number of plaintext/ciphertext pairs but the attacks are often underestimated compared to statistical methods. In algebraic cryptanalysis, we consider a polynomial system representing the cipher and a solution of this system reveals the secret key used in the encryption. The contribution of this thesis is twofold. Firstly, we evaluate the performance of existing algebraic techniques with respect to number of plaintext/ciphertext pairs and their selection. We introduce a new strategy for selection of samples. We build this strategy based on cube attacks, which is a well-known technique in algebraic cryptanalysis. We use cube attacks as a fast heuristic to determine sets of plaintexts for which standard algebraic methods, such as Groebner basis techniques or SAT solvers, are more efficient. Secondly, we develop a~new technique for algebraic cryptanalysis which allows us to speed-up existing Groebner basis techniques. This is achieved by efficient finding special polynomials called mutants. Using these mutants in Groebner basis computations and SAT solvers reduces the computational cost to solve the system. Hence, both our methods are designed as tools for building polynomial system representing a cipher. Both tools can be combined and they lead to a significant speedup, even for very simple algebraic solvers.

  • Files
  • Details
  • Metrics
Type
doctoral thesis
DOI
10.5075/epfl-thesis-6651
Author(s)
Sušil, Petr  
Advisors
Vaudenay, Serge  
Jury

Prof. Mark Pauly (président) ; Prof. Serge Vaudenay (directeur de thèse) ; Prof. Arjen Lenstra, Prof. Jintai Ding, Prof. Nicolas Courtois (rapporteurs)

Date Issued

2015

Publisher

EPFL

Publisher place

Lausanne

Public defense year

2015-08-28

Thesis number

6651

Total of pages

138

Subjects

algebraic cryptanalysis

•

symmetric encryption

•

KATAN

•

LBlock

•

SIMON

•

cube attacks

•

selection of samples

EPFL units
LASEC  
Faculty
IC  
School
ISC  
Doctoral School
EDIC  
Available on Infoscience
August 19, 2015
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/117127
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés