일반화된 Feistel 구조에 대한 중간 일치 공격

성재철(Jaechul Sung) 한국정보보호학회 2017 정보보호학회논문지 Vol.27 No.6

블록 암호 설계에서 Feistel 구조는 가장 널리 사용되는 구조 중의 하나이다. 또한 Feisel 구조를 확장하여 일반화한 Feistel 구조 역시 블록 암호 뿐 아니라 해쉬 함수에서도 널리 사용되는 구조이다. Feistel 구조의 구조적 안전성에 대한 다양한 분석 및 많은 연구가 진행되었다. 이 중 최근 Feistel 구조에 대한 중간 일치 공격은 Feistel 구조의 구조적 안전성을 가장 효과적으로 분석하는 방법 중 하나이다. 본 논문에서는 일반화된 Feistel 구조에 대한 중간 일치 공격에 대한 안전성을 분석한다. Feistel Networks are one of the most well-known schemes to design block ciphers. Generalized Feistel Networks are used to construct only block ciphers but also hash functions. Many generic attacks on Feistel schemes have been studied. Among these attacks, recently proposed meet-in-the-middle attacks are one of the most effective attacks. In this paper, we analyze the security of meet-in-the-middle attacks on generalized Feistel Networks.

가변 라운드 수를 갖는 블록 암호에 대한 차분 연관 암호 공격

성재철(Jaechul Sung),김종성(Jongsung Kim),이창훈(Changhoon Lee) 한국정보보호학회 2005 정보보호학회논문지 Vol.14 No.1

연관 암호 공격은 키의 길이에 따라 가변 라운드 수를 갖는 블록 암호알고리즘의 키 스케쥴의 약점을 이용한 공격으로 2002년 Hongjun Wu에 의해 소개되었다. 이 공격은 두 개의 서로 다른 키 길이에 대해 각기 다른 라운드 수를 갖는 두 암호에서 사용되는 키 쌍이 유사-동치키일 경우에 적용되는 공격이다. 본 논문에서는 이러한 연관 암호 공격을 블록 암호알고리즘의 가장 강력한 공격 방법인 차분 공격과 결합한 차분 연관 암호 공격의 개념을 제시한다. 차분연관 암호 공격은 기존의 연관 암호 공격에서 라운드 수의 차이가 커짐에 따라 공격 적용의 어려움을 극복한 방법이다. 이 공격법을 이용하여 블록 암호알고리즘 ARIA v.0.9와 SC2000을 분석한다. 또한, 차분 공격 뿐 아니라 선형공격, 고계 차분 공격 등과 같은 기존의 블록 암호알고리즘 공격들과 연관 암호 공격이 결합 가능함을 이용하여, 가변 라운드 수를 갖는 블록 암호알고리즘인 SAFER++와 CAST-128을 분석한다. Related-Cipher attack was introduced by Hongjun Wu in 2002. We can consider related ciphers as block ciphers with the same round function but different round number and their key schedules do not depend on the total round number. This attack can be applied to block ciphers when one uses some semi-equivalent keys in related ciphers. In this paper we introduce differential related-cipher attacks on block ciphers, which combine related-cipher attacks with differential cryptanalysis. We apply this attack to the block cipher ARIA and SC2000. Furthermore, related-cipher attack can be combined with other block cipher attacks such as linear cryptanalysis, higher-order differential cryptanalysis, and so on. In this point of view we also analyze some other block ciphers which use flexible number of rounds, SAFER++ and CAST-128.

소프트웨어 구현에 적합한 스트림 암호의 대수적 공격에 대한 안전성

성재철(Jaechul Sung),문덕재(Dukjae Moon),임흥수(Hung-su Im),지성택(Seongtaek Chee),이상진(Sangjin Lee) 한국정보보호학회 2005 정보보호학회논문지 Vol.14 No.1

본 논문에서는 최근 제안된 소프트웨어 구현에 적합한 (블록 단위) 스트림 암호인 HELIX, SCREAM, MUGI, PANAMA 알고리즘들의 대수적 공격에 대한 안전성을 분석한다. 대수적 공격은 알려진 입출력 쌍을 가지고 내부 알고리즘의 기본 대수 방정식을 이용하는 방법으로, 과포화된 다변수 연립 방정식을 통하여 변수의 값을 얻고 이를 이용하여 키를 복구해내는 방법이다. 이 분석법은 초기 대수적 특성을 지닌 블록 암호의 분석에 적용되었으나, 이후 블록 암호보다는 스트림 암호의 분석에 보다 용이하게 적용되었다. 그러나 일반적인 알고리즘을 이 분석법을 그대로 적용하기에는 많은 어려움이 존재한다. 따라서 본 논문에서는 최근 제안된 워드 단위의 소프트웨어 구현에 적합한 스트림 암호의 각 알고리즘에 대해 대수적 방정식과 변수의 수를 비교 및 분석함으로써 각 알고리즘의 대수적 공격에 대한 내성을 살펴본다. 또한 이러한 분석을 통해 대수적 공격에 안전한 소프트웨어 구현에 적합한 스트림 암호의 설계 시 고려해야 할 세 가지 설계 고려사항을 제시한다. In this paper we consider the security of recently proposed software-oriented stream cipher HELIX, SCREAM, MUGI, and PANAMA against algebraic attacks. Algebraic attack is a key recovery attack by solving an over-defined system of multi-variate equations with input-output pairs of an algorithm. The attack was firstly applied to block ciphers with some algebraic properties and then it has been more usefully applied to stream ciphers. However, it is difficult to obtain over-defined algebraic equations for a given cryptosystem in general. Here we analyze recently proposed software-oriented stream ciphers by constructing a system of equations for each cipher. Furthermore we propose three design considerations of software-oriented stream ciphers.

On the Optimal Key Size of the Even-Mansour Cipher in the Random Function Oracle Model

성재철(Jaechul Sung) 한국정보보호학회 2007 정보보호학회논문지 Vol.17 No.3

본 논문은 Even-Mansour 암호에 대해 안전성 약화 없이 키 사이즈를 줄이는 방법에 대해 다룬다. Even과 Mansour는 랜덤 순열 모델에서 랜덤 순열 P와 두 개의 키를 이용하여 평문 M을 암호화하는 기법(C = k₂? P(M ? k₁))을 제안하였다. ASIACRYPT 2004에서 Gentry와 Ramzen은 4 라운드의 Feistel 구조를 이용하여 Even-Mansour 모델의 랜덤 순열을 랜덤 함수로 대치한 새로운 모델을 제안하고 안전성을 증명하였다. 본 논문에서는 Gentry-Ramzen 모델에 필요한 키사이를 반으로 줄이는 방법을 살펴보고 제안한 방법에 대한 안전성을 랜덤 함수 모델에서 증명한다. We describe the problem of reducing the key material in the Even-Mansour cipher without security degradation. Even and Mansour proposed a block cipher based on XORing secret key material just prior to and after applying random oracle permutation P such that C = k₂? P(M ? k₁). Recently, Gentry and Ramzan showed that this scheme in the random permutation oracle can be replaced by the four-round Feistel network construction in the random function oracle and also proved that their scheme is super-pseudorandom. In this paper we reduce the key size from 2n to n, which is the optimal key size of Even-Mansour cipher in the random function oracle model and also give almost the same level of security.

Skipjack 구조에 대한 DC 및 LC의 안전성 증명

성재철(Jaechul Sung),이상진(Sangjin Lee),김종수(Jongsu Kim),임종인(Jongin Lim) 한국정보보호학회 2000 정보보호학회논문지 Vol.10 No.1

본 논문에서는 Skipjack의 변환규칙 A와 같은 반복적인 구조에 대한 차분 특성 및 선형 근사식의 확률의 상한 값을 제시하고 이를 증명한다. 즉 라운드 함수에 대한 확률의 최대 값이 p이면 15라운드 후에 p⁴이 됨을 보인다. 따라서 본 논문에서 고려한 구조는 현재까지 DC 및 LC에 대한 안전성을 증명할 수 있는 구조인 Feistel 구조 및 MISTY 구조와 더불어 블록 암호의 설계 방법에 대한 다양성을 제공한다. In this paper we introduce a structure of block cipher which is an iterated cipher by the rule A of Skipjack and show this structure is provably resistant against differential or linear attacks. It is the main result of this paper that the upper bound of r-round(r≥15) differential(or linear hull) is p⁴ if the maximum differential(or linear approximation) probability of a round function is p. We can consider this structure as a generalized Feistel structure. Therefore we can apply this structure to block ciphers and give the provable security against differential attack or linear attack with some upper bounds.

7-라운드 SEED에 대한 향상된 차분 공격

성재철(Jaechul Sung) 한국정보보호학회 2010 정보보호학회논문지 Vol.20 No.4

블록 암호알고리즘 SEED 국내 TTA(정보통신기술협회)와 더불어 국제 ISO/IEC 표준으로 사용되고 있는 128비트 입출력을 갖는 국내에서 개발된 알고리즘이다. SEED 개발 이후 현재까지 알려진 가장 좋은 공격 방법은 2002년 Yanami 등이 제안한 차분 분석 방법이다. 이 공격 방법은 확률 2?¹²⁴의 6-라운드 차분 특성을 이용하여, 7-라운드 SEED를 2¹²?의 데이터 복잡도로 분석하였다. 본 논문에서는 확률 2?¹¹?의 새로운 6-라운드 새로운 차분 특성을 제시하고, 이를 이용하여 7-라운드 SEED를 2¹¹³의 데이터 복잡도로 공격할 수 있음을 보인다. Block Cipher SEED which was developed by KISA are not only Korea national standard algorithm of TTA but also one of standard 128-bit block ciphers of ISO/IEC. Since SEED had been developed, many analyses were tried but there was no distinguishing cryptanalysis except the 7-round differential attack in 2002. The attack used the 6-round differential characteristic with probability 2?¹²⁴ and analyzed the 7-round SEED with 2¹²? chosen plaintexts. In this paper, we propose a new 6-round differential characteristic with probability 2?¹¹? and analyze the 7-round SEED with 2¹¹³ chosen plaintexts.

연관키 공격에 안전한 의사난수 치환 및 함수 패밀리

김종성(Jongsung Kim),성재철(Jaechul Sung),은희천(Hichun Eun) 한국정보보호학회 2007 정보보호학회논문지 Vol.17 No.5

본 논문에서는 강력한 의사난수 함수 관점에서 안전한 tweakable 전단사 함수 패밀리를 이용하여 연관키에 안전한 전단사 함수 패밀리를 설계할 수 있음을 보인다. 이를 이용하여 현재까지 알려진 것 중에 가장 빠르면서 연관키 공격에 안전한 전단사 함수 패밀리를 구성한다. 또한, 의사난수 함수 관점에서 안전한 적당한 유형의 함수 패밀리를 이용하여 연관키 공격에 안전한 전단사 함수 패밀리를 구성할 수 있음을 보인다. 이는 기존의 안전성이 증명된 MAC 알고리즘을 이용하면 연관키 공격에 안전한 스킴을 구성할 수 있음을 나타낸다. 끝으로, 본 논문에서는 연관키 공격에 대한 여러 안전성 개념(indistinguishability, non-malleability)을 정의하고, 그들 사이의 관계를 살펴본다. In this paper, we observe that secure tweakable permutation families in the sense of strong pseudorandom permutation (SPRP) can be transformed to secure permutation families in the sense of SPRP against related-key attacks (SPRP-RKA). This fact allows us to construct a secure SPRP-RKA which is the most efficient to date. We also observe that secure function families of a certain form in the sense of a pseudorandom function (PRF) can be transformed to secure permutation families in the sense of PRP-RKA. We can exploit it to get various secure constructions against related-key attacks from known MAC algorithms. Furthermore, we define other security notions for related-key attacks, namely indistinguishability and non-malleability, and look into the relations between the security notions for related-key attacks. We show that secure tweakable permutation families in the sense of indistinguishability (resp. non-malleability) can be transformed to secure permutation families in the sense of indistinguishability (resp. non-malleability) against related-key attacks.

블록 암호 SEED에 대한 차분 오류 공격

정기태(Kitae Jeong),성재철(Jaechul Sung),홍석희(Seokhie Hong) 한국정보보호학회 2010 정보보호학회논문지 Vol.20 No.4

차분 오류 공격(DFA)은 블록 암호의 안전성 분석에 널리 사용되는 부채널 공격 기법으로서, 대표적인 블록 암호인 DES, AES, ARIA, SEED 등에 적용되었다. 기제안된 SEED에 대한 DFA는 라운드 16의 입력값에 영구적인 에러를 주입한다는 가정을 이용한다. 본 논문에서는 SEED의 라운드 차분의 특성 분석과 덧셈 차분의 특성을 이용하여 SEED 에 대한 DFA를 제안한다. 본 논문에서 사용하는 공격 가정은 특정 레지스터에 1-비트 오류를 주입한다는 것이다. 이 공격을 이용하여 약 2³² 번의 간단한 산술 연산으로 SEED의 라운드 키 및 마스터 키를 복구할 수 있다. 이는 일반적인 PC에서 수 초 내에 가능함을 의미한다. A differential fault attack(DFA) is one of the most efficient side channel attacks on block ciphers. Almost all block ciphers, such as DES, AES, ARIA, SEED and so on., have been analysed by this attack. In the case of the known DFAs on SEED, the attacker induces permanent faults on a whole left register of round 16. In this paper, we analyse SEED against DFA with differential characteristics and addition-XOR characteristics of the round function of SEED. The fault assumption of our attack is that the attacker induces 1-bit faults on a particular register. By using our attack, we can recover last round keys and the master key with about 2³² simple arithmetic operations. It can be simulated on general PC within about a couple of second.

PKC'98에 제안된 해쉬 함수의 Original Version에 대한 전체 라운드 차분 공격

장동훈(Donghoon Chang),성재철(Jaechul Sung),성수학(Soohak Sung),이상진(Sangjin Lee),임종인(Jongin Lim) 한국정보보호학회 2002 정보보호학회논문지 Vol.12 No.2

Shrinking 생성기와 Self-Shrinking 생성기에 대한 향상된 고속 상관 공격

정기태(Kitae Jeong),성재철(Jaechul Sung),홍석희(Seokhie Hong),이상진(Sangjin Lee),김재헌(Jaeheon Kim),박상우(Sangwoo Park) 한국정보보호학회 2006 정보보호학회논문지 Vol.16 No.2

본 논문에서는 shrinking 생성기와 self-shrinking 생성기에 대한 향상된 고속 상관 공격을 제안한다. 본 논문에서 제안하는 공격은 Zhang 등이 CT-RSA 2005에서 제안한 shrinking 생성기에 대한 고속 상관 공격을 개선한 것으로 shrinking 생성기에서 길이가 61인 생성 LFSR의 초기 상태값을 2<SUP>15.43</SUP> 키스트림 비트와 2<SUP>56.3314</SUP>의 계산 복잡도로 성공 확률 99.9%로 복구할 수 있다. 또한 245.89 키스트림 비트와 2<SUP>112.424</SUP>의 계산 복잡도로 self-shrinking 생성기에서 길이가 2⁴?인 LFSR의 초기 상태값을 성공 확률 99.9%로 복구할 수 있다. In this paper, we propose a fast correlation attack on the shrinking and self-shrinking generator. This attack is an improved algorithm of the fast correlation attack by Zhang et al. at CT-RSA 2005. For the shrinking generator, we recover the initial state of generating LFSR whose length is 61 with 2<SUP>15.43</SUP> keystream bits, the computational complexity of 2<SUP>56.3314</SUP> and success probability 99.9%. We also recover the initial state of generating LFSR whose length is 240 of the self-shrinking generator with 2<SUP>45.89</SUP> keystream bits, the computational complexity of 2<SUP>112.424</SUP> and success probability 99.9%.