KR101601684B1

KR101601684B1 - 부채널 공격에 대응하는 대칭키 암호 알고리즘 구현 방법

Info

Publication number: KR101601684B1
Application number: KR1020110047064A
Authority: KR
Inventors: 최두호; 최용제; 강유성; 김주한; 김태성; 오경희
Original assignee: 한국전자통신연구원
Priority date: 2011-05-18
Filing date: 2011-05-18
Publication date: 2016-03-09
Anticipated expiration: 2031-05-18
Also published as: US20120294439A1; US8488781B2; KR20120129045A

Abstract

본 발명은 어파인 변환 테이블을 저장하는 단계, 마스킹 인버젼 테이블을 저장하는 단계 및 어파인 변환 테이블과 마스킹 인버젼 테이블을 이용하여 마스킹 S-box를 계산하는 단계를 포함하는 것을 특징으로 한다.

Description

부채널 공격에 대응하는 대칭키 암호 알고리즘 구현 방법{METHOD FOR IMPLEMENTING SYMMETRIC KEY ENCRYPTION ALGORITHM AGAINST POWER ANALYSIS ATTACKS}

본 발명은 전력분석공격에 대응하는 방법에 관한 것으로서, 더욱 상세하게는 전력분석공격의 대응법을 적용하여 대칭키 암호 알고리즘 구현시 발생하는 메모리와 수행시간을 감소시키기 위한 부채널 공격에 대응하는 대칭키 암호 알고리즘 구현 방법에 관한 것이다.

일반적으로, 대칭키 암호 알고리즘은 블록 암호 알고리즘이라고도 하는데, 일정 단위 블록의 데이터를 동일한 키로 암호화 및 복호화하며, 강도 높은 암호화를 위하여 다중 모드 동작으로 운용된다.

전력/전자파 부채널 공격은 대칭키 암호 알고리즘에 대한 강력한 공격 기법 중의 하나로, 보안 제품에 대한 커다란 위협 요소가 되고 있다.

전력/전자파 부채널 공격은 암호 알고리즘 구동시 발생하는 전자기파나 소비되는 전력을 수집하여 이를 통계적인 분석을 통해 암호 알고리즘의 비밀정보 예를 들어, 키정보를 분석해 내는 공격 방법이다.

이에 대칭키 암호 알고리즘에서는 이러한 전력/전자파 부채널 분석 공격을 막기 위해, 다양한 방지 기법이 제시되고 있다.

이 중, 마스킹 기법은 암호 알고리즘 레벨에서 부채널 공격을 방지하는 대표적인 방법이다. 마스킹 기법은 원래의 암호화되어야 하는 데이터들에 랜덤한 데이터를 더하거나, XOR하여 암호연산의 중간값을 예측할 수 없게 함으로써, 수집된 전력파형이나 전자기파 데이터의 통계적인 분석이 어렵게 하는 방법이다.

상기한 기술구성은 본 발명의 이해를 돕기 위한 배경기술로서, 본 발명이 속하는 기술분야에서 널리 알려진 종래기술을 의미하는 것은 아니다.

종래에는 대칭키 암호 알고리즘에서 비선형 함수로 S-box를 사용하고 있다.

이와 같이, 부채널 공격 방지를 위해 마스킹 방법에 의한 대칭키 암호 알고리즘을 구현할 경우, 마스킹 S-box 테이블 생성을 위한 메모리가 추가적으로 소모되고, 더욱이 라운드별로 마스킹 연산을 수행해야 되므로, 수행시간이 추가적으로 증가하게 되는 문제점이 있었다.

본 발명은 전술한 문제점을 개선하기 위해 창안된 것으로서, 마스킹 인버젼 테이블(masked inversion table)과 어파인 변환 테이블(affine map table)을 미리 생성 및 저장하여 이를 통해 마스킹 S-box(masked S-box)를 계산하도록 함으로써, 메모리 소모량과 수행시간을 감소시킬 수 있도록 한 부채널 공격에 대응하는 대칭키 암호 알고리즘의 구현 방법을 제공하는데 그 목적이 있다.

본 발명의 일 측면에 따른 부채널 공격에 대응하는 대칭키 암호 알고리즘의 구현 방법은 어파인 변환 테이블을 생성하여 저장하는 단계; 마스킹 인버젼 테이블을 생성하여 저장하는 단계; 및 상기 어파인 변환 테이블과 상기 마스킹 인버젼 테이블을 이용하여 마스킹 S-box를 계산하는 단계를 포함하는 것을 특징으로 한다.

본 발명에서, 상기 마스킹 인버젼 테이블을 생성하여 저장하는 단계는

상의 곱셈 역함수에 대한 인버젼 테이블을 저장하고, 상기 인버젼 테이블을 출력 마스킹 값과 XOR하여 생성하는 것을 특징으로 한다.

본 발명의 상기 어파인 변환 테이블을 생성하여 저장하는 단계는 수학식

을 사용하여 상기 어파인 변환 테이블을 생성하고, 상기 어파인 변환 테이블은

상의 어파인 변환

와,

,

및

의 어파인 변환 테이블인 것을 특징으로 한다.

본 발명의 상기 어파인 변환 테이블과 상기 마스킹 인버젼 테이블을 이용하여 마스킹 S-box를 연산하는 단계에서, 상기 마스킹 S-box는 상기 어파인 변환 테이블과 상기 마스킹 인버젼 테이블을 이용하여 매 라운드의 각 S-box 마다 선택된 입력 마스킹값

과 출력 마스킹값

에 대해 수학식

에 따라 연산하여 상기 마스킹 S-box는

과

을 만족하는 것을 특징으로 한다.

본 발명의 상기 어파인 변환 테이블과 상기 마스킹 인버젼 테이블을 이용하여 마스킹 S-box를 계산하는 단계는 매 라운드마다 상기 어파인 변환 테이블과 상기 마스킹 인버젼 테이블을 공통으로 사용하는 것을 특징으로 한다.

본 발명은 마스킹 인버젼 테이블과 어파인 변환 테이블을 미리 생성 및 저장하여 이를 통해 마스킹 S-box를 계산하도록 함으로써, 메모리 소모량과 수행시간을 감소시킬 수 있도록 한다.

도 1 은 일반적인 ARIA 전체 구조를 도시한 도면이다.
도 2 는 본 발명의 일 실시예에 따른 부채널 공격에 대응하는 대칭키 암호 알고리즘의 구현 장치의 블럭 구성도이다.
도 3 은 본 발명의 일 실시예에 따른 부채널 공격에 대응하는 대칭키 암호 알고리즘의 구현 방법의 순서도이다.
도 4 는 도 3 의 마스킹 인버젼 테이블을 도시한 도면이다.
도 5 는 도 3 의 A 어파인 변환 테이블을 도시한 도면이다.
도 6 은 도 3 의 A^-1 어파인 변환 테이블을 도시한 도면이다.
도 7 은 도 3 의 D 어파인 변환 테이블을 도시한 도면이다.
도 8 은 도 3 의 D^-1 어파인 변환 테이블을 도시한 도면이다.

이하에서는 본 발명의 일 실시예에 따른 부채널 공격에 대응하는 대칭키 암호 알고리즘의 구현 방법을 첨부된 도면들을 참조하여 상세하게 설명한다. 이러한 과정에서 도면에 도시된 선들의 두께나 구성요소의 크기 등은 설명의 명료성과 편의상 과장되게 도시되어 있을 수 있다. 또한 후술되는 용어들은 본 발명에서의 기능을 고려하여 정의된 용어들로써, 이는 사용자, 운용자의 의도 또는 관례에 따라 달라질 수 있다. 그러므로 이러한 용어들에 대한 정의는 본 명세서 전반에 걸친 내용을 토대로 내려져야할 것이다.

도 1 은 일반적인 ARIA 전체 구조를 도시한 도면이다.

일반적인 ARIA(Academy Research Institute Agency)는 치환 계층과 확산 계층 및 키 에디션으로 라운드 함수를 구성한다.

기본 구조는 ISPN 구조(Involutional Substitution Permutation Networks)이며, 입출력 크기는 128 비트이다. 키 크기는 128 / 192 / 256 비트이며, 라운드 키 크기는 128 비트이며, 라운드 수는 키 크기에 따라 12 / 14 / 16 라운드이다.

도 1 에서 치환계층은 두 개의 S-box와 이 두 개의 S-box를 역치환한 S-box를 포함하여 4 개의 S-box(

)를 사용한다.

S-box(

) 는

과

의 어파인 변환(affine transform) 형태로 연산을 수행한다.

이러한 2개의 S-box(

) 는 그 역치환한 2개의 S-box(

)를 이용하여 ARIA 의 라운드 함수 중 치환계층을 구성한다.

한편, ARIA의 확산 계층은 하기한 바와 같이, 16 x 16 이진 행렬로 구성되어 입력 16 바이트(

)에 대한 출력 16 바이트(

)의 값을 행렬 곱셈을 통하여 연산한다.

그러나, 전력분석공격이 제시됨으로써, 여러 가지 대응법이 소개되었는 바, 마스킹 기법은 원래의 암호화되어야 하는 데이터들에 랜덤한 데이터를 더하거나, XOR하여 암호연산의 중간값을 예측할 수 없도록 하는 기법이다.

그러나, 마스킹 기법은 매 라운드 마다 마스킹 S-box를 연산하여야 하므로, 메모리와 수행시간이 크게 증가하게 되었다.

일반적으로, 대칭키 알고리즘에서는 비선형 함수를 위해 사용되는 S-box가 상기한 바와 같이, 이진필드

상의 함수로 구성되는 바, 대부분 수학식 1과 같은 형태로 분해가 가능하다. 여기서, 수학식 1 은 대칭키 암호의 S-box 함수 구성 원리를 나타낸다.

여기서,

는

상의 곱셈 역함수를 의미하며,

는

상의 어파인 변환을 의미한다.

대칭 알고리즘에서 사용하는 S-box가 2개 이상일 경우에도 곱셈 역함수

와 또 다른 어파인 변환과 상수 XOR 로 분해가 가능하다.

예를 들어, ARIA의 경우, 상기한 바와 같이 2개의 S-box(

)와 S-box 역함수(

)를 사용하는데, 각각의 S-box는 하기의 수학식 2와 같이 표현될 수 있다.

여기서,

값은 아래의 수학식 3 내지 6과 같다.

그러나, 대부분 소프트웨어로 대칭키 암호를 구현할 경우, 이러한 곱셈 역함수

연산과 어파인 변환 연산이 시간 복잡도가 높은 연산이기 때문에, S-box 함수 자체를 테이블 형태로 저장하고, 이를 룩-업(Look-up) 하는 방식으로 구현 효율성을 높인다.

그리고, 부채널 대응을 위해 마스킹 기법을 적용할 경우, 각각의 S-box 마다(128비트 대칭키에 8비트 Sbox의 경우, 16개),

(

은 입력 마스킹 값과 출력 마스킹 값)인 값이 매 라운드마다 필요한다.

이를 위해, 위 수식을 만족하는 마스킹 S-box 테이블들을 생성해 놓아야 하며, 이를 위해 많은 연산시간과 추가 메모리가 필요하게 된다.

도 2 는 본 발명의 일 실시예에 따른 부채널 공격에 대응하는 대칭키 암호 알고리즘의 구현 장치의 블럭 구성도이고, 도 3 은 본 발명의 일 실시예에 따른 부채널 공격에 대응하는 대칭키 암호 알고리즘의 구현 방법의 순서도이며, 도 4 는 도 3 의 마스킹 인버젼 테이블을 도시한 도면이며, 도 5 는 도 3 의 A 어파인 변환 테이블을 도시한 도면이며, 도 6 은 도 3 의 A^-1 어파인 변환 테이블을 도시한 도면이며, 도 7 은 도 3 의 D 어파인 변환 테이블을 도시한 도면이며, 도 8 은 도 3 의 D^-1 어파인 변환 테이블을 도시한 도면이다.

도 2 를 참조하면, 본 발명의 일 실시예에 따른 부채널 공격에 대응하는 대칭키 암호 알고리즘의 구현 장치는 ARIA의 매 라운드 마다 구비되어 비선형 함수 S-box를 이용하여 입력값을 치환하여 결과값을 확산 계층(Diffusion layer)로 전달하는 치환 계층(Substitution layer), 및 치환 계층에서 마스킹 S-box를 연산할 수 있도록 인버젼 테이블(Inversion table)과, 어파인 변환 테이블(Affine transform table) 및 마스킹 인버젼 테이블(Masked inversion table)을 저장하는 메모리부(10)를 포함한다. 메모리부(10)는 롬(Read Only Memory)이 채용될 수 있다.

인버젼 테이블과 어파인 변환 테이블 및 마스킹 인버젼 테이블은 기 저장되어 매 라운드마다 각 치환 계층에서 공통적으로 사용된다.

이를 위해, 메모리부(10)는 곱셈역함수

에 대한 인버젼 테이블을 저장하고, 어파인 변환을 위해 어파인 변환 테이블을 저장한다.

또한, 곱셈역함수

를 이용하여 생성된 마스킹 인버젼 테이블을 저장한다.

이후, 상기한 인버젼 테이블, 어파인 변환 테이블 및 마스킹 인버젼 테이블을 이용하여 매 라운드의 각 S-box 마다 선택된 입력 마스킹값과 출력 마스킹값(

)에 대해 마스킹 S-box를 연산한다.

이하, 도 3 내지 도 8 을 참조하여 상세하게 설명한다.

먼저, 도 4 에 도시된 바와 같이, 메모리부(10)에

상의 곱셈역함수

에 대한 인버젼 테이블을 저장한다(S10).

다음으로, 도 5 내지 도 8 에 도시된 바와 같이, A 와 A^-1 , D 및 D^-1 과 같은 어파인 변환에 대한 어파인 변환 테이블을 생성하여 저장한다(S20).

다음으로, 마스킹 인버젼 테이블을 저장한다(S30).

마스킹 인버젼 테이블을 저장하기 위해서는, 하기의 수학식 7을 사용하여 생성한다.

여기서, 마스킹 인버젼 테이블은

상의

에 대한 인버젼 테이블과 출력 마스킹 값을 XOR하여 생성된다.

마지막으로, 어파인 변환 테이블 및 마스킹 인버젼 테이블을 이용하여 매 라운드의 각 S-box 마다 선택된 입력 마스킹값

과 출력 마스킹값

에 대해 하기의 수학식 8과 같이 마스킹 S-box를 연산한다(S40).

여기서, S-box 는

,

이다.

상기한 바와 같이, 연산을 하면, 마스킹 S-box의 결과는 아래의 수학식 9의 값이 된다.

따라서,

,

을 만족하게 된다.

이에 따라, 매 라운드의 각 마스킹 S-box를 위해 마스킹 S-box 테이블을 생성하는데 소모되는 메모리와 수행 시간을 감소시킬 수 있어 효율적인 부채널 공격 방지 알고리즘을 구현할 수 있다.

참고로, 본 실시예에서는 국내 표준 대칭키 암호 알고리즘의 하나인 ARIA 알고리즘을 예시로 하여 설명하였으나, 본 발명의 기술적 범위는 이에 한정되지 않고, 2개 이상의 S-box를 사용하는 암호 알고리즘 일 예로, AES(Advanced Encryption Standard) 등에도 적용될 수 있다.

본 발명은 도면에 도시된 실시예를 참고로 하여 설명되었으나, 이는 예시적인 것에 불과하며 당해 기술이 속하는 기술분야에서 통상의 지식을 가진 자라면 이로부터 다양한 변형 및 균등한 타 실시예가 가능하다는 점을 이해할 것이다. 따라서, 본 발명의 진정한 기술적 보호범위는 아래의 특허청구범위에 의하여 정해져야할 것이다.

10: 메모리부

Claims

어파인 변환 테이블을 생성하여 저장하는 단계;
마스킹 인버젼 테이블을 생성하여 저장하는 단계; 및
상기 어파인 변환 테이블과 상기 마스킹 인버젼 테이블을 이용하여 마스킹 S-box를 계산하는 단계를 포함하는 부채널 공격에 대응하는 대칭키 암호 알고리즘의 구현 방법.
제 1 항에 있어서, 상기 마스킹 인버젼 테이블을 생성하여 저장하는 단계는

상의 곱셈 역함수에 대한 인버젼 테이블과 출력 마스킹 값을 XOR하여 생성하는 것을 특징으로 하는 부채널 공격에 대응하는 대칭키 암호 알고리즘의 구현 방법.
제 1 항에 있어서, 상기 어파인 변환 테이블을 생성하여 저장하는 단계는
수학식
을 사용하여 상기 어파인 변환 테이블을 생성하고, 상기 어파인 변환 테이블은
상의 어파인 변환 A 와, A, D 및 D^-1의 어파인 변환 테이블인 것을 특징으로 하는 부채널 공격에 대응하는 대칭키 암호 알고리즘의 구현 방법.
제 1 항에 있어서, 상기 어파인 변환 테이블과 상기 마스킹 인버젼 테이블을 이용하여 마스킹 S-box를 연산하는 단계에서,
상기 마스킹 S-box는 상기 어파인 변환 테이블과 상기 마스킹 인버젼 테이블을 이용하여 매 라운드의 각 S-box 마다 선택된 입력 마스킹값
과 출력 마스킹값
에 대해 수학식

에 따라 연산하여 상기 마스킹 S-box는
과
을 만족하는 것을 특징으로 하는 부채널 공격에 대응하는 대칭키 암호 알고리즘의 구현 방법.
제 1 항에 있어서, 상기 어파인 변환 테이블과 상기 마스킹 인버젼 테이블을 이용하여 마스킹 S-box를 계산하는 단계는
매 라운드마다 상기 어파인 변환 테이블과 상기 마스킹 인버젼 테이블을 공통으로 사용하는 것을 특징으로 하는 부채널 공격에 대응하는 대칭키 암호 알고리즘의 구현 방법.