유한체 $F{_p}{^{k}}$에서 효율적으로 제곱근을 구하는 알고리즘들

한동국,최두호,김호원,임종인,Han, Dong-Guk,Choi, Doo-Ho,Kim, Ho-Won,Lim, Jong-In 한국정보보호학회 2008 정보보호학회논문지 Vol.18 No.a6

본 논문에서는 확장체 $F{_p}{^{k}}$(k 홀수) 에서 효율적으로 제곱근을 구하는 방법을 제안한다. 제곱근을 구하는 알고리즘은 표수 p의 조건에 따라서 여러 가지 방법들이 제안되었다. 특히, 알고리즘을 구성하는 중심 되는 연산 중의 하나가 지수승연산이다. 본 연구에서는 기존의 제곱근을 구하는 알고리즘에 사용되는 지수승의 지수들이 표수 p을 활용한 p-진법으로 표현할 경우, 특별한 형태의 주기성을 가지는 표현으로 나타내어짐을 증명하고, 이것을 활용해 기존의 알고리즘들을 효율적으로 계선하는 방법을 제안한다. 본 논문에서 제안한 방법은 표수 p의 조건에 의존하지 않고, 지수승 기반의 기존의 모든 제곱근 알고리즘에 적용 가능하다는 장점을 가지고 있다. 지금까지 알려진 바로는, 본 논문이 처음으로 Tonelli-Shanks 알고리즘을 효율적으로 개선하였으며, $p{\equiv}1$ (mod 16) 인 경우 60% 이상의 효율성 증대가 있었다. 다른 제곱근 알고리즘에 적용한 결과들도 비교표들을 이용해 언급되어 있으며, 기존의 방법들에 비해 상당히 효율적임을 나타내고 있다. In this paper we study exponentiation in finite fields $F{_p}{^{k}}$(k is odd) with very special exponents such as they occur in algorithms for computing square roots. Our algorithmic approach improves the corresponding exponentiation independent of the characteristic of $F{_p}{^{k}}$. To the best of our knowledge, it is the first major improvement to the Tonelli-Shanks algorithm, for example, the number of multiplications can be reduced to at least 60% on average when $p{\equiv}1$ (mod 16). Several numerical examples are given that show the speed-up of the proposed methods.

XTR 버전의 개인식별 프로토콜을 이용해 블랙메일링을 막는 실질적인 방법

한동국(Dong-Guk Han),박혜영(Hye-Young Park),박영호(Young-Ho Park),김창한(Chang-Han Kim),임종인(Jong-In Lim) 한국정보보호학회 2002 정보보호학회논문지 Vol.12 No.1

단순전력분석에 안전한 Signed Left-to-Right 리코딩 방법

한동국(Dong-Guk Han),김성경(Sung-kyoung Kim),김태현(Tae Hyun Kim),김호원(Ho Won Kim),임종인(Jongin Lim) 한국정보보호학회 2007 정보보호학회논문지 Vol.17 No.1

본 논문에서는 주어진 기수 r 표현법을 SPA에 안전하게 리코딩 하는 방법을 제안한다. 제안된 알고리즘들은 기존의 것들과는 달리, Left-to-Right 리코딩이 가능하도록 구성되어져 있기 때문에 최상위 비트부터 스캔하면서 스칼라 곱셈을 계산하는 알고리즘과 연동이 되어 질 경우, 추가 메모리 없이 쉽게 구현된다는 장점이 있다. 따라서 Left-to-Right 리코딩기법들은 메모리의 제약을 받는 장비인 스마트 카드, 센서 노드에 적합하다. This paper proposed recoding methods for a radix- r representation of the secret scalar which are resistant to SPA. Unlike existing recoding method, these recoding methods are left-to-right so they can be interleaved with a left-to-right scalar multiplication, removing the need to store both the scalar and its recoding. Hence, these left-to-right methods are suitable for implementing on memory limited devices such as smart cards and sensor nodes

랜덤한 덧셈-뺄셈 체인에 대한 부채널 공격

한동국(Dong-Guk Han),장남수(Nam-Su Chang),장상운(Sang-Woon Jang),임종인(Jongin Lim) 한국정보보호학회 2004 정보보호학회논문지 Vol.14 No.5

Okeya-Sakurai는 타원곡선 암호시스템에 대한 부채널 공격의 대응방법으로 소개된 Oswald-Aigner의 랜덤한 덧셈-뺼셈 체인(Randomized Automaton 1, 2) 대응방법 [18]이 SPA 공격에 취약함을 보였다. 그러나 본 논문에서는 Okeya-Sakurai의 공격 알고리즘 [15,16]에 두 가지 잠재된 문제가 있음을 보인다. 그리고 두 가지 문제점에 대한 해결책을 제시하고 [15,16,19]와는 다른 새로운 효율적인 공격 알고리즘을 제안한다. 표준에 제안되어 있는 163비트 비밀키를 사용하는 알고리즘에 본 논문의 분석방법을 적용해 구현한 결과, 단순한 형태의 랜덤한 덧셈-뺄셈 체인(Randomized Automaton 1)에서는 20개의 AD수열로 대략 94%의 확률로 공격이 성공하며 30개의 AD수열로는 대략 99%의 확률로 공격이 성공한다. 또한, 복잡한 형태(Randomized Automaton 2)에서는 40개의 AD수열로 94%의 확률로 70개의 AD수열로는 99%로의 확률로 공격이 성공한다. In [15,16], Okeya and Sakurai showed that the randomized addition-subtraction chains countermeasures [18] are vulnerable to SPA attack. In this paper, we show that Okeya and Sakurai’s attack algorithm [15,16] has two latent problems which need to be considered. We further propose new powerful concrete attack algorithms which are different from [15,16,19]. From our implementation results for standard 163-bit keys, the success probability for the simple version with 20 AD sequences is about 94% and with 30 AD sequences is about 99%. Also, the success probability for the complex version with 40 AD sequences is about 94% and with 70 AD sequences is about 99%.

마스킹 테이블을 사용하지 않는 AES, ARIA, SEED S-box의 전력 분석 대응 기법

한동국(Dong-Guk Han),김희석(HeeSeok Kim),송호근(Ho-geun Song),이호상(Ho-sang Lee),홍석희(Seokhie Hong) 한국정보보호학회 2011 정보보호학회논문지 Vol.21 No.2

전력 분석 공격이 소개되면서 다양한 대응법들이 제안되었고 그러한 대응법들 중 블록 암호의 경우, 암/복호화 연산도중 중간 값이 전력 측정에 의해 드러나지 않도록 하는 마스킹 기법이 잘 알려져 있다. 블록 암호의 마스킹 기법은 비선형 연산에 대한 비용이 가장 크며, 따라서 AES, ARIA, SEED의 경우 S-box에 대한 대응법을 효율적으로 설계해야만 한다. 하지만 기존의 AES, ARIA, SEED의 S-box에 대한 대응 방법은 마스킹 S-box 테이블을 사용하는 방법으로 하나의 S-box당 256 bytes의 RAM을 필수적으로 사용한다. 하지만 가용 RAM의 크기가 크지 않은 경량보안 디바이스에 이러한 기존의 대응법은 사용이 부적합하다. 본 논문에서는 이러한 단점을 보완하기 위해 마스킹 S-box 테이블을 사용하지 않는 새로운 대응법을 제안한다. 본 논문에서 제안하는 새로운 대응 기법은 비용이 적은 ROM을 활용, RAM의 사용량을 줄일 뿐 아니라 마스킹 S-box 테이블 생성 시간을 소요하지 않으므로 축소 라운드 마스킹 기법 적용 시 고속화도 가능하다. In the recent years, power analysis attacks were widely investigated, and so various countermeasures have been proposed. In the case of block ciphers, masking methods that blind the intermediate values in the en/decryption computations are well-known among these countermeasures. But the cost of non-linear part is extremely high in the masking method of block cipher, and so the countermeasure for S-box must be efficiently constructed in the case of AES, ARIA and SEED. Existing countermeasures for S-box use the masked S-box table to require 256 bytes RAM corresponding to one S-box. But, the usage of the these countermeasures is not adequate in the lightweight security devices having the small size of RAM. In this paper, we propose the new countermeasure not using the masked S-box table to make up for this weak point. Also, the new countermeasure reduces time-complexity as well as the usage of RAM because this does not consume the time for generating masked S-box table.

유한체 F<SUB>p<SUP>k</SUP></SUB>에서 효율적으로 제곱근을 구하는 알고리즘들

한동국(Dong-Guk Han),최두호(Doo Ho Choi),김호원(Howon Kim),임종인(Jongin Lim) 한국정보보호학회 2008 정보보호학회논문지 Vol.18 No.a6

본 논문에서는 확장체 Fp<SUP>k</SUP>(k 홀수) 에서 효율적으로 제곱근을 구하는 방법을 제안한다. 제곱근을 구하는 알고리즘은 표수 p의 조건에 따라서 여러 가지 방법들이 제안되었다. 특히, 알고리즘을 구성하는 중심 되는 연산 중의 하나가 지수승 연산이다. 본 연구에서는 기존의 제곱근을 구하는 알고리즘에 사용되는 지수승의 지수들이 표수 p을 활용한 p-진법으로 표현할 경우, 특별한 형태의 주기성을 가지는 표현으로 나타내어짐을 증명하고, 이것을 활용해 기존의 알고리즘들을 효율적으로 계선하는 방법을 제안한다. 본 논문에서 제안한 방법은 표수 p의 조건에 의존하지 않고, 지수승 기반의 기존의 모든 제곱근 알고리즘에 적용 가능하다는 장점을 가지고 있다. 지금까지 알려진 바로는, 본 논문이 처음으로 Tonelli-Shanks 알고리즘을 효율적으로 개선하였으며, p ≡1 (mode 16)인 경우 60% 이상의 효율성 증대가 있었다. 다른 제곱근 알고리즘에 적용한 결과들도 비교표들을 이용해 언급되어 있으며, 기존의 방법들에 비해 상당히 효율적임을 나타내고 있다. In this paper we study exponentiation in finite fields Fp<SUP>k</SUP>(k is odd) with very special exponents such as they occur in algorithms for computing square roots. Our algorithmic approach improves the corresponding exponentiation independent of the characteristic of Fp<SUP>k</SUP>. To the best of our knowledge, it is the first major improvement to the Tonelli-Shanks algorithm, for example, the number of multiplications can be reduced to at least 60% on average when p≡1(mod 16). Several numerical examples are given that show the speed-up of the proposed methods.

유한체 $GF(2^n)$에서 낮은 공간복잡도를 가지는 새로운 다중 분할 카라슈바 방법의 병렬 처리 곱셈기

장남수,한동국,정석원,김창한,Chang Nam-Su,Han Dong-Guk,Jung Seok-Won,Kim Chang Han 대한전자공학회 2004 電子工學會論文誌-SC (System and control) Vol.41 No.1

유한체 $GF(2^n)$에서 두 원소의 곱셈을 수행하는 공간 복잡도가 낮은 병렬 처리 곱셈기의 구현에 있어서 divide-and-conquer 방법은 유용하게 사용된다. 이를 이용한 가장 널리 알려진 알고리듬으로는 카라슈바 (Karatsuba-Ofman) 알고리듬과 다중 분할 카라슈바(Multi-Segment Karatsuba) 알고리듬이 있다. Leo ne은 카라슈바 알고리듬의 최적화된 반복 횟수를 제안하였고, Ernst는 다중 분할 카라슈바 방법을 이용한 일반적이고 확장 가능한 유한체 곱셈기를 제안하였다. 본 논문에서는 Ernst가 제시한 다중 분할 카라슈바 병렬 처리 곱셈기의 복잡도를 제시한다. 또한 기존 방법의 병렬 처리 곱셈기와 시간 복잡도는 같지만 공간 복잡도는 낮은 새로운 다중 분할 카라슈바 방법의 병렬 처리 곱셈기를 제안하며 그에 따른 최적화된 반복 횟수를 제안한다. 나아가서 제안하는 곱셈기가 몇몇 유한체에서 카라슈바 방법의 병렬 처리 곱셈기 보다 공간 복잡도에서 효과적임을 제시한다. The divide-and-conquer method is efficiently used in parallel multiplier over finite field $GF(2^n)$. Leone Proposed optimal stop condition for iteration of Karatsuba-Ofman algerian(KOA). Ernst et al. suggested Multi-Segment Karatsuba(MSK) method. In this paper, we analyze the complexity of a parallel MSK multiplier based on the method. We propose a new parallel MSK multiplier whose space complexity is same to each other. Additionally, we propose optimal stop condition for iteration of the new MSK method. In some finite fields, our proposed multiplier is more efficient than the KOA.

효과적인 비프로파일링 분석을 수행하기 위한 ML-based SCA 모델 설계 방안

임한섭(Han-Seop Lim),심보연(Bo-Yeon Sim),한재승(JaeSeung Han),김주환(Ju-Hwan Kim),한동국(Dong-Guk Han) 대한전자공학회 2020 대한전자공학회 학술대회 Vol.2020 No.8

SHA-3 최종 라운드 후보 Skein에 대한 부채널 공격 방법

박애선,박종연,한동국,이옥연,Park, Ae-Sun,Park, Jong-Yeon,Han, Dong-Guk,Yi, Ok-Yeon 한국정보처리학회 2012 정보처리학회논문지 C : 정보통신,정보보안 Vol.19 No.3

NIST(National Institute of Standards and Technology)는 SHA-2의 대체 알고리즘 부재로 SHA-3 개발 프로젝트를 진행 되고 있는 중 이다. 2010년 최종 라운드 후보 5개가 발표되었고, SHA-3 최종 라운드 5개의 후보에 대한 부채널 공격 시나리오가 제안되었다. 본 논문에서는 SHA-3 최종 라운드 후보 중 Skein에 대한 부채널 공격 시나리오를 32비트 레지스터를 사용하는 ARM Chip을 이용하여, 8 비트의 블록단위로 Divide and Conquer 분석이 가능함을 실험을 통해 증명한다. 9700개의 파형으로 128비트 키의 모든 비트를 찾을 수 있음을 실험으로 검증하였다. Due to the absence of an alternative algorithm SHA-2, NIST (National Institute of Standards and Technology) is proceeding to development project of SHA-3. NIST announced five candidates of the final round at the end of 2010. Side-channel attack scenarios of five candidates for SHA-3 final round have been proposed. In this paper, we prove the possibility of the analysis against 32-bit modular addition by 8-bit blocks from our experiment on ARM chip board with a register size of 32-bit. In total we required 9700 power traces to successfully recover the 128-bit secret key for the attack against.

효과적인 딥러닝 기반 비프로파일링 부채널 분석 모델 설계방안

한재승(JaeSeung Han),심보연(Bo-Yeon Sim),임한섭(Han-Seop Lim),김주환(Ju-Hwan Kim),한동국(Dong-Guk Han) 한국정보보호학회 2020 정보보호학회논문지 Vol.30 No.6

최근 딥러닝 기반 비프로파일링 부채널 분석이 제안됐다. 딥러닝 기반 비프로파일링 분석은 신경망 모델을 모든 추측키에 대해 학습시킨 뒤, 학습된 정도의 차이를 통해 올바른 비밀키를 찾아내는 기법이다. 이때, 신경망 학습모델 설계에 따라 비프로파일링 분석성능이 크게 달라지기 때문에 올바른 모델 설계의 기준이 필요하다. 본 논문은 학습모델 설계에 사용 가능한 2가지 loss 함수와 8가지 label 기법을 설명하고, 비프로파일링 분석과 소비전력모델 관점에서 각 label 기법의 분석성능을 예측했다. 해밍웨이트 소비전력모델을 가정했을 때의 비프로파일링 분석 특징을 고려해서 One-hot인코딩을 적용하지 않은 HW(Hamming Weight) label과 CO(Correlation Optimization) loss를 적용한 학습모델이 가장 좋은 분석성능을 가질 것으로 예측했다. 그리고 AES-128 1라운드 Subbytes 연산 부분 데이터 집합 3가지에 대해 실제 분석을 수행했다. 제시한 각 label 기법과 loss 함수를 적용한 총 16가지 MLP(Multi-Layer Perceptron)기반 학습모델로 두 데이터 집합을 비프로파일링 분석하여 예측에 대해 검증했다. Recently, a deep learning-based non-profiling side-channel analysis was proposed. The deep learning-based non-profiling analysis is a technique that trains a neural network model for all guessed keys and then finds the correct secret key through the difference in the training metrics. As the performance of non-profiling analysis varies greatly depending on the neural network training model design, a correct model design criterion is required. This paper describes the two types of loss functions and eight labeling methods used in the training model design. It predicts the analysis performance of each labeling method in terms of non-profiling analysis and power consumption model. Considering the characteristics of non-profiling analysis and the HW (Hamming Weight) power consumption model is assumed, we predict that the learning model applying the HW label without One-hot encoding and the Correlation Optimization (CO) loss will have the best analysis performance. And we performed actual analysis on three data sets that are Subbytes operation part of AES-128 1 round. We verified our prediction by non-profiling analyzing two data sets with a total 16 of MLP-based model, which we describe.