Algorithmic Algebraic Techniques and their Application to Block Cipher Cryptanalysis. / Albrecht, Martin.

2010. 176 p.

Research output: ThesisDoctoral Thesis

Unpublished

Standard

Harvard

APA

Vancouver

Author

BibTeX

@phdthesis{f08c313d609c4284acf29091effcab6f,
title = "Algorithmic Algebraic Techniques and their Application to Block Cipher Cryptanalysis",
abstract = "In Part I we present and discuss implementations of both well-known and novel algorithms for fundamental problems of linear algebra over the field with two elements (F2). In particular, we present the best known implementations for matrix-matrix multiplication and matrix decomposition for dense matrices over F2. These implementations are based on novel variants of the {"}M4RM{"} multiplication algorithm and the M4RI elimination algorithm.In Part II we discuss Gr{\"o}bner basis algorithms. No algorithm discussed in this part is new. However, we are not aware of any other treatment of either the matrix-F5 or the F4-style F5 in the English speaking literature which covers these algorithms in such detail. Furthermore, we provide reference implementations for all algorithms discussed in this part.In Part III we apply algebraic techniques to the cryptanalysis of block ciphers. The key contributions of this part are novel ways of utilising algebraic techniques in cryptanalysis. In particular, we combine algebraic techniques with linear, differential and higher-order differential cryptanalysis. These hybrid approaches allow us to push the respective cryptanalytical technique further in most cases. We also explicitly shift the focus from solving polynomial systems of equations to computing features about block ciphers which can then be used in other attacks. Finally, we propose a new family of problems - denoted {"}Max-PoSSo{"} in this thesis - which model polynomial system solving with noise. We also propose an algorithm for solving these problems, based on Integer Programming, and apply this algorithm to the so-called {"}Cold Boot{"} problem.",
keywords = "commutative algebra, cryptography, cryptology, cryptanalysis, linear algebra, F5, block cipher, differential cryptanalysis, integral cryptanalysis, Gr{\"o}bner basis, multivariate polynomial",
author = "Martin Albrecht",
year = "2010",
language = "English",

}

RIS

TY - THES

T1 - Algorithmic Algebraic Techniques and their Application to Block Cipher Cryptanalysis

AU - Albrecht, Martin

PY - 2010

Y1 - 2010

N2 - In Part I we present and discuss implementations of both well-known and novel algorithms for fundamental problems of linear algebra over the field with two elements (F2). In particular, we present the best known implementations for matrix-matrix multiplication and matrix decomposition for dense matrices over F2. These implementations are based on novel variants of the "M4RM" multiplication algorithm and the M4RI elimination algorithm.In Part II we discuss Gröbner basis algorithms. No algorithm discussed in this part is new. However, we are not aware of any other treatment of either the matrix-F5 or the F4-style F5 in the English speaking literature which covers these algorithms in such detail. Furthermore, we provide reference implementations for all algorithms discussed in this part.In Part III we apply algebraic techniques to the cryptanalysis of block ciphers. The key contributions of this part are novel ways of utilising algebraic techniques in cryptanalysis. In particular, we combine algebraic techniques with linear, differential and higher-order differential cryptanalysis. These hybrid approaches allow us to push the respective cryptanalytical technique further in most cases. We also explicitly shift the focus from solving polynomial systems of equations to computing features about block ciphers which can then be used in other attacks. Finally, we propose a new family of problems - denoted "Max-PoSSo" in this thesis - which model polynomial system solving with noise. We also propose an algorithm for solving these problems, based on Integer Programming, and apply this algorithm to the so-called "Cold Boot" problem.

AB - In Part I we present and discuss implementations of both well-known and novel algorithms for fundamental problems of linear algebra over the field with two elements (F2). In particular, we present the best known implementations for matrix-matrix multiplication and matrix decomposition for dense matrices over F2. These implementations are based on novel variants of the "M4RM" multiplication algorithm and the M4RI elimination algorithm.In Part II we discuss Gröbner basis algorithms. No algorithm discussed in this part is new. However, we are not aware of any other treatment of either the matrix-F5 or the F4-style F5 in the English speaking literature which covers these algorithms in such detail. Furthermore, we provide reference implementations for all algorithms discussed in this part.In Part III we apply algebraic techniques to the cryptanalysis of block ciphers. The key contributions of this part are novel ways of utilising algebraic techniques in cryptanalysis. In particular, we combine algebraic techniques with linear, differential and higher-order differential cryptanalysis. These hybrid approaches allow us to push the respective cryptanalytical technique further in most cases. We also explicitly shift the focus from solving polynomial systems of equations to computing features about block ciphers which can then be used in other attacks. Finally, we propose a new family of problems - denoted "Max-PoSSo" in this thesis - which model polynomial system solving with noise. We also propose an algorithm for solving these problems, based on Integer Programming, and apply this algorithm to the so-called "Cold Boot" problem.

KW - commutative algebra

KW - cryptography

KW - cryptology

KW - cryptanalysis

KW - linear algebra

KW - F5

KW - block cipher

KW - differential cryptanalysis

KW - integral cryptanalysis

KW - Gröbner basis

KW - multivariate polynomial

M3 - Doctoral Thesis

ER -