블록 암호 Serpent에 대한 다중 선형 공격

홍득조,김동찬,권대성 보안공학연구지원센터(JSE) 2007 보안공학연구논문지 Vol.4 No.4

Serpent는 1998년부터 2000년까지 미국의 NIST에 의해 수행된 AES 공모 사업에서 최종 다섯 후보에 선정되었었던 블록 암호 알고리즘이다. 본 논문에서는 Serpent에 대하여 존재하는 선형근사식들을 지적하고, 이 근사식들을 이용하여 Serpent의 10, 11 라운드가 공격될 수 있음을 보인다. 4096개의 9 라운드 선형근사식들을 이용하면, 본 논문에서 소개되는 공격 알고리즘은 10 라운드 Serpent 서브키의 48비트를 추출할 수 있으며, 11 라운드 Serpent 서브키의 176비트를 추출할 수 있다. 10 라운드에 대한 공격에는 개의 평문과 , 11 라운드에 대한 공격에는 개의 평문이 소요된다. 11 라운드에 대한 공격은 시간복잡도가 높기 떄문에 256비트키에 대해서만 유효하다. 두 공격의 성공확률은 모두 90%이며, 이것은 평문의 양에 따라 조절될 수 있다. Serpent is a block cipher which was selected as one of five AES finalists at AES project performed by NIST. In this paper, we indicate linear approximations in Serpent and attack 10 and 11 rounds of Serpent. Using 4096 linear approximations, our attack algorithm recover 48 subkey bits of 10-round Serpent (with plaintexts) and 176 subkey bits of 11-round Serpent (with plaintexts). The later attack is valid only for 256-bit master keys due to high time complexity. The success rate of both attacks is 90%, which is dependent on the number of plaintexts.

SP F-함수를 갖는 4-브랜치 GFN-2 구조에 대한 기지키 공격

홍득조 한국정보보호학회 2020 정보보호학회논문지 Vol.30 No.5

In this paper, we study known-key distinguishing and partial-collision attacks on GFN-2 structures with SP F-functionsand various block lengths. Firstly, we show the known-key distinguishing attack is possible up to 15 rounds. Secondly, forthe case that the last round function has the shuffle operation, we show that the partial-collision attack is possible up to 14rounds. Finally, for the case that the last round function has no shuffle operation, we show that the partial-collision attacksare possible up to 11 rounds. 본 논문에서는 SP 구조의 F-함수를 가진 4-브랜치 GFN-2 구조에 대한 기지키 구별 공격(Known-KeyDistinguishing Attack) 및 부분 충돌 공격(Partial-Collision Attack)을 연구한다. 첫 번째로, 이 구조에 대해 기지키 구별 공격이 15 라운드까지 가능함이 밝혀진다. 두 번째로, 마지막 라운드에 셔플 연산이 있는 경우, 부분 충돌 공격이 14 라운드까지 가능함이 밝혀진다. 마지막으로, 마지막 라운드에 셔플 연산이 없는 경우, 부분 충돌공격이 15 라운드까지 가능함이 밝혀진다.

6 라운드로 축소된 Sparkle384와 7 라운드로 축소된 Sparkle512에 대한 새로운 구별 공격

홍득조(Deukjo Hong),장동훈(Donghoon Chang) 한국정보보호학회 2023 정보보호학회논문지 Vol.33 No.6

블록암호에 대한 새로운 다중선형공격법

홍득조(Deukjo Hong),성재철(Jaechul Sung),홍석희(Seokhie Hong),이상진(Sangjin Lee) 한국정보보호학회 2007 정보보호학회논문지 Vol.17 No.6

다중선형공격은 선형공격을 강화하기 위한 방법으로 연구되어왔다. 본 논문에서는 다중선형공격에 관한 최신 이론인 Biryukov의 공격 알고리즘이 비선형 키스케줄을 가진 블록암호에 적용이 어려움을 지적하고, 새로운 다중선형공격법을 제안한다. 작은 블록암호에 대한 실험을 통하여 새로운 다중선형공격법에 관한 이론이 실제로도 매우 잘 적용될 수 있음이 보여진다. Multiple linear cryptanalysis has been researched as a method building up the linear attack strength. We indicate that the lastest linear attack algorithm using multiple approximations, which was proposed by Biryukov et al. is hardly applicable to block ciphers with highly nonlinear key schedule, and propose a new multiple linear attack algorithm. Simulation of the new attack algorithm with a small block cipher shows that theory fot the new multiple linear cryptanalysis works well in practice.

해쉬함수 ARIRANG의 축소된 단계에 대한 역상공격

홍득조(Deukjo Hong),김우환(Woo-Hwan Kim),구본욱(Bonwook Koo) 한국정보보호학회 2009 정보보호학회논문지 Vol.19 No.5

본 논문에서는 SHA-3의 1 라운드 후보로 제안된 알고리즘인 ARIRANG의 단계수가 축소된 버전들에 대한 역상공격을 소개한다. 이 공격은 단계 1부터 단계 33까지의 ARIRANG-256 및 ARIRANG-512의 33단계 OFF(Original FeedForward1) 버전의 역상을 찾아내며, 단계 1부터 단계 34까지의 ARIRANG-256 및 ARIRANG-512의 31단계 MFF(Middle Feed-Forward1) 버전의 역상을 찾아낸다. 공격 복잡도는 ARIRANG-256에 대해서 약 2<SUP>241</SUP>이고 ARIRANG-512에 대해서 약 2<SUP>481</SUP>이다. The hash function ARIRANG is one of the 1st round SHA-3 candidates. In this paper, we present preimage attacks on ARIRANG with step-reduced compression functions. Our attack finds a preimage of the 33-step OFF(Original FeedForward1) variants of ARIRANG, and a preimage of the 31-step MFF (Middle FeedForward1) variants of ARIRANG. Its time complexity is about 2<SUP>241</SUP> for ARIRANG-256 and 2<SUP>481</SUP> for ARIRANG-512, respectively.

경량 블록암호 알고리즘 설계 연구 동향

홍득조(Deukjo Hong) 한국정보보호학회 2020 情報保護學會誌 Vol.30 No.3

하드웨어 및 소프트웨어의 최적화는 제품의 성능 및 기능 향상, 개발 비용 최소화 등에 직접적인 영향을 미치는 매우 중요한 요소이다. 이러한 필요성에 따라, 암호학자들은 경량 암호 알고리즘을 가용 자원이 제한된 다양한 환경에서 효율적으로 구현 및 동작할 수 있는 암호 알고리즘으로 정의하고, 그것에 맞는 다양한 설계 방법들이 연구해왔다. 본고에서는 경량 블록암호 알고리즘 설계 연구 동향을 소개하고, 향후 전망에 대해 논의한다.

ARIRANG, HAS-160, PKC98-Hash의 축소된 단계들에 대한 역상공격

홍득조(Deukjo Hong),구본욱(Bonwook Koo),김우환(Woo-Hwan Kim),권대성(Daesung Kwon) 한국정보보호학회 2010 정보보호학회논문지 Vol.20 No.2

본 논문에서는 ARIRANG, HAS-160, PKC98-Hash의 단계-축소 버전에 대한 역상공격 결과를 소개한다. 이 공격에는 Aoki와 Sasaki가 SHA-0와 SHA-1의 단계-축소 버전을 공격하는데 이용한 chunk 검색 방법이 응용되었다. 본 논문에서 소개하는 공격 알고리즘들은 각각 ARIRANG, HAS-160, PKC98-Hash의 35단계, 65단계, 80단계에 대하여 전수조사보다 빠른시간내에 역상을 찾는다. In this paper, we present the preimage attacks on step-reduced ARIRANG, HAS-I60, and PKC9S-Hash. We applied Aoki and Sasaki's chunk serach method which they have used in the attack on SHA-O and SHA-I. Our attacks find the preimages of 35-step ARIRANG, 65-step HAS-l60, and 80-step PKC9S-Hash. Our results are the best preimage attacks for ARIRANG and HAS-160, and the first preimage attack for PKC9S-Hash faster than exhaustive search.

BOGI 전략으로 설계된 블록 암호의 차분 공격에 대한 안전성 분석

이상협,김성겸,홍득조,성재철,홍석희 한국정보보호학회 2019 정보보호학회논문지 Vol.29 No.6

The upper bound of differential characteristic probability is mainly used to determine the number of rounds whenconstructing a block cipher. As the number of rounds affects the performance of block cipher, it is critical to evaluate thetight upper bound in the constructing process. In order to calculate the upper bound of differential characteristic probability,the previous searching methods for minimum number of active S-boxes constructed constraint equations for non-linearoperations and linear operations, independently. However, in the case of BOGI design strategy, where linear operation isdependent on non-linear operation, the previous methods may present the less tight upper bound. In this paper, we exploitthe properties of BOGI strategy to propose a new method to evaluate a tighter upper bound of differential characteristicprobability than previous ones. Additionally, we mathematically proved the validity of our method. Our proposed method wasapplied to GIFT-64 and GIFT-128, which are based on BOGI strategy, and the upper bounds of differential characteristicprobability were derived until 9 round. Previously, the upper bounds of differential characteristic probability for 7-round GIFT-64 and 9-round GIFT-128 were 2^-18.395 and 2^-26.885 , respectively, while we show that the upper bounds ofdifferential characteristic probability are more tight as 2^-19.81 and 2^-28.3 , respectively. 블록 암호를 설계할 때, 설계자는 주로 차분 특성 확률의 상한을 이용하여 라운드 수를 결정한다. 라운드 수는 블록 암호의 성능에 영향을 미치므로, 더 적은 라운드를 갖기 위해 차분 특성 확률의 상한을 정밀하게 계산하는 것이중요하다. 이전까지의 활성 S-box의 최소 개수를 탐색하는 방법들은 비선형 연산과 선형 연산을 각각 제약식으로 구성하여 차분 특성 확률의 상한을 계산하였다. 하지만 선형 연산이 비선형 연산에 의존적으로 선택되는 BOGI 설계전략(Bad-Output Good-Input Design Strategy)의 경우 이전 탐색방법으로 구한 상한은 정밀하지 않을 수 있다. 본 논문에서는 BOGI 전략의 성질을 이용하여 기존의 방법보다 더 정밀한 차분 특성 확률의 상한을 구하는 새로운방법을 제안한다. 그리고 이 방법을 이용하여 구한 상한의 타당성을 수학적으로 증명한다. 제안한 방법을 BOGI가사용된 GIFT-64와 GIFT-128에 각각 적용하여 9라운드까지 차분 특성 확률의 상한을 탐색하였다. GIFT-64의 7라운드와 GIFT-128의 9라운드에 대해 기존의 방법을 적용하면 차분 특성 확률의 상한이 각각 2^-18.395와 2^-26.885이었으나, 제안한 방법을 적용하면 각각 2^-19.81 과 2^-28.3으로 더 정밀하게 계산된다.

GPGPU 기술을 활용한 차분 확률의 통계적 분석

조은지,김성겸,홍득조,성재철,홍석희 한국정보보호학회 2019 정보보호학회논문지 Vol.29 No.3

In this paper, we experimentally verify the expected differential probability under the markov cipher assumption and thedistribution of the differential probability. Firstly, we validate the expected differential probability of 6round-PRESENT of thelightweight block cipher under the markov cipher assumption by analyzing the empirical differential probability. Secondly, wedemonstrate that even though the expected differential probability under the markov cipher assumption seems valid, theempirical distribution does not follow the well-known distribution of the differential probability. The results was deducedfrom the 4round-GIFT. Finally, in order to analyze whether the key-schedule affects the mis-matching phenomenon, wecollect the results while changing the XOR positions of round keys on GIFT. The results show that the key-schedule is notthe only factor to affect the mis-matching phenomenon. Leveraging on GPGPU technology, the data collection process canbe performed about  times faster than using CPU only. 본 논문에서는 마르코프 암호 가정 하에 구한 기대 차분 확률과 차분 확률의 분포를 실험적으로 검증한다. 첫 번째로, 마르코프 암호 가정 하에 구한 기대 차분 확률과 실험을 통해 구한 확률이 일치하는지를 경량 블록암호PRESENT의 6라운드에 적용하여 타당함을 보인다. 두 번째로, 마르코프 암호 가정 하에 구한 기대 차분 확률에 통계적으로 근사하지만, 차분 확률의 알려진 분포를 따르지 않는 경우가 있음을 경량 블록암호 GIFT의 4라운드에 적용하여 실험적으로 보인다. 마지막으로 키 스케줄이 표본 추출 모델을 통한 고정키의 차분 확률의 분포에 영향을 미치는지를 분석하기 위해 GIFT의 라운드 키의 XOR 위치와 개수를 바꾸어 얻은 차분 확률들을 제시한다. 이 결과를통해 표본 추출 가정에 키 스케줄만의 유일한 영향이 아님을 알 수 있다. 통계적 분석을 위한 데이터 수집은GPGPU 기술을 활용하여 CPU만을 이용한 프로그램에 비해 약 배 빠르게 수행할 수 있었다.

비트 순열 기반 블록암호의 비선형 불변 공격저항성 연구

정건상,김성겸,홍득조,성재철,홍석희 한국정보보호학회 2020 정보보호학회논문지 Vol.30 No.3

Nonlinear Invariant Attack is an attack that should be considered when constructing lightweight block ciphers withrelatively simple key schedule. A shortcut to prove a block cipher’s resistance against nonlinear invariant attack is checkingthe smallest dimension of linear layer-invariant linear subspace which contains all known differences between round keys isequal to the block size. In this paper, we presents the following results. We identify the structure and number of optimalbit-permutations which require only one known difference between round keys for a designer to show that the correspondingblock cipher is resistant against nonlinear invariant attack. Moreover, we show that PRESENT-like block ciphers need atleast two known differences between round keys by checking all PRESENT-like bit-permutations. Additionally, we verify that the variants of PRESENT-like bit-permutations requiring the only two known differences between round keys do not conflictwith the resistance against differential attack by comparing the best differential trails. Finally, through the distribution of theinvariant factors of all bit-permutations that maintain BOGI logic with GIFT S-box, GIFT-variant block ciphers require atleast 8 known differences between round keys for the resistance. 비선형 불변 공격은 비교적 간단한 구조의 키 스케줄을 갖는 경량 블록암호에서 필수적으로 고려되어야 할 공격이다. 간단한 구조의 키 스케줄을 갖는 경량 블록암호가 비선형 불변 공격에 저항성을 보이는 방법으로 가장 잘 알려진 것은 라운드 키 간의 차분 중 알려진 것들의 집합에서 선형계층에 대해 불변인 최소의 선형공간의 크기가 블록크기와 같은지를 확인하는 것이다. 본 논문에서는 다음과 같은 연구 결과를 제시한다. 설계자 관점에서 비트 순열을선형계층으로 사용하는 SPN 구조 경량 블록암호는 라운드 키 간의 차분의 종류가 한가지여도 비선형 불변 공격에안전할 수 있음을 증명하고, 그러한 비트 순열의 형태와 개수를 제안한다. 또한, PRESENT 구조 블록암호는 비선형 불변 공격에 저항성을 갖기 위해 적어도 두 종류의 라운드 키 간의 차분이 필요함을 전수조사를 통해 보이며, 두종류의 라운드 키 간의 차분을 필요로 하는 비트 순열을 사용해도 차분 공격에 대한 저항성이 오히려 증가할 수 있음을 보인다. 마지막으로 GIFT의 S-box를 사용하면서 BOGI 설계 논리를 유지하는 모든 비트 순열의 불변 성분분포를 통해, 변형된 GIFT 구조 블록암호는 비선형 불변 공격에 저항성을 갖기 위해 적어도 8종류의 라운드 키 간의 차분이 필요함을 보인다.