블록암호에 대한 대수적 암호분석

Abstract

대수적 암호분석은 암호 알고리즘의 구성 함수에 대한 입출력 변수와 이들의 관계식으로부터 대수 방정식들을 유도하고, 이 대수 방정식들의 해를 구함으로써 공격하는 암호분석법이다. 대수적 공격을 적용하기 위한 문제는 크게 두 가지로 생각할 수 있다. 하나는 암호 알고리즘을 완전하게 표현할 수 있는 대수적 방정식을 찾는 문제이고, 다른 하나는 대수적 방정식을 효율적으로 계산하여 해를 찾는 문제이다. 본 논문에서는 다양한 비교 관점을 제공할 수 있는 두 개의 블록암호 AES와 KASUMI에 대한 대수적 암호분석을 시도한다. AES와 KASUMI는 구조적인 차이, 입출력 크기와 라운드 키의 크기 차이, S-box의 대수적 차수의 차이, 키 확장 알고리즘의 차이, 모델링 방법의 차이 등에서 비교 관점을 제공해 줄 수 있다. 각 블록암호 알고리즘에 대한 다양한 관점의 $GF(2)$ 상의 대수 방정식 유도 결과와 유도된 전체 방정식의 규모를 제시한다. 또한 알려진 해법들을 이용하여 대수 방정식들을 실험한 결과를 제시한다. 실험은 Gr\"oebner basis를 구하는 문제에 기반한 해법들인 Singular, Macaulay 2, PolyBori를 이용하였다.; Algebraic cryptanalysis of block ciphers has been received much attention by cryptanalysts as a different generic approach from already existing statistical methods. Most of all the statistical methods, such as DC and LC, have in common, which is an attempt to distinguish a cipher from a truly random permutation by measuring a non-random behavior from an output of the cipher. However, algebraic cryptanalysis is the most direct method to recover a secret key by solving a system of equations. Given a particular block cipher, this attack consists of two steps as follows; one must building a system of equations that are true with probability 1 and then one must solve the system of equations to get the solution which is the secret key of the ciphers. In this paper, we show how to build a system of algebraic equations over $GF(2)$ rather than over $GF(2^(n))$. We have builded some systems of algebraic equations over $GF(2^(n))$ for representing ciphers such as AES-128, KASUMI, and small scaled those ciphers. And, we have tried to solve the systems of equations by using to compute the Gr\"oebner basis. The computations have been conducted by using the computer algebra packages, such as the Singular, Macaulay 2 and PolyBori. As a result, the experiments could not be reached any successful algebraic cryptanalysis for a full-round. However, we show some of the successful results, which are the cases where we have reached to get a solution to a number of small scaled ciphers.