AES에 대한 DPA 대응방안 개선

장화선*, 김광조*

*한국정보통신대학원대학교, 국제정보보호기술연구소

Improved Countermeasure for DPA on AES

Hwasun Chang*, Kwangjo Kim*

*International Research center for Information Security(IRIS)

Information and Communications Univ.(ICU)

요   약

본 논문에서는 AES에 대한 부채널 공격의 일종인 Differential Power Attack(DPA)과 그 대응방안들을 살펴보고, 그 중 저가 스마트카드에 적합한 고정 마스크 방법의 개선된 방안을 제안한다. 제안된 방법은 메모리 사용량과 xor 연산 량에서 기존 방법에 비해 유리하다.

Ⅰ. 서론

부채널 공격은 암복호화 연산 중 외부로 유출되는 전력 소모 및 전자기파 정보를 분석하거나 계산 시간과 오류 생성 등을 통하여 암호화키를 알아내는 방법이다. 부채널 공격의 일종인 Differential Power Attack(DPA)은 전력 소모를 이용하는 공격으로 P. Kocher에 의해 Crypto □99에서 발표되었고 그 이후로 많은 대응방안들이 연구되었다.[1] 대응방안들은 칩의 설계에 반영하는 방법과 프로그램에 적용하는 방안으로 나눌 수 있다. T. Messerges는 FSE 2000에서 AES 후보 알고리즘들을 전력 분석 공격에서 보호하기 위해 마스크를 이용하는 방법을 제안하였다.[2] 하지만 이 방법에 따르면 매 암복호화마다 마스크를 난수로 생성하고 생성된 마스크에 따라 S-box를 다시 계산해야 했기 때문에 많은 RAM을 필요로 하고 연산량도 많다는 문제가 있었다. 한편 C. Clavier는 CHES 2000에서 하드웨어적인 대응방안이 있는 경우에도 DPA가 가능함을 보여 소프트웨어적인 대응방안의 필요성을 강조하였다.[3] K. Itoh는 ICICS 2001에서 고정된 마스크에 의한 대응방안을 제안하였고 이 방법은 RAM 사용량과 연산량 측면에서 이전 방법에 비해 유리하였다.[4] 이 방법은 저가 스마트카드에 적합한 것으로 볼 수 있다. 하지만 마스크를 고정된 몇 개의 값 중에 선택함으로써 안전성이 떨어지는 문제가 있었다. M. Akkar는 CHES 2001에서 Multiplicative mask를 사용하는 방법을 제안하였는데 이 방법은 S-box를 다시 계산할 필요가 없었다. 이에 따라 메모리 사용량과 연산량의 문제를 해결할 수 있었다.[5] 하지만 J. Golic에 의해 Multiplicative mask가 0에 대해 문제가 있음이 밝혀졌고 이후 몇 가지 대안이 제시되었지만 S-box를 다시 계산하여야 하는 등 메모리 사용량과 연산량이 다시 증가하는 문제가 있었고 안전성도 보장할 수 없었다.[6][7] 결국 매 암복호화마다 라운드별로 다른 마스크를 생성하고 이에 따라 S-box를 다시 계산하는 방법이 가장 안전하다고 볼 수 있지만 이 방법은 메모리 사용량과 연산량이 많아서 스마트카드 같이 자원이 한정된 환경에 적용하기는 어렵다.

본 논문에서는 제안된 방법 중 어느 정도의 안전성을 가지면서 저가 스마트카드에 적합한 고정 마스크 방법을 개선하여 더 적은 메모리와 연산량으로 DPA에 대응할 수 있는 방법을 제안한다. 본론에서는 1절에서 AES 알고리즘을 살펴보고, 2절에서는 DPA에 대해 정리한다. 3절에서는 마스크에 의한 대응방안을 살펴보고 4절에서는 고정 마스크 방법에 대해 알아본다. 5절에서는 Multiplicative mask 방법과 문제점을 알아보고 6절에서는 개선된 방안을 제안한 후 7절에서 제안한 방법의 안전성을 살펴본다.

II. 본론

1. AES

본 연구와 관련된 부분을 중심으로 AES를 살펴본다. AES에서는 상태(State)라 불리는 중간 값에 여러 가지 변환을 적용한다. 상태는 바이트의 직사각형 배열로 나타낼 수 있다. 암호 키도 마찬가지 형태로 나타낸다. 배열의 행수는 4이며 열 수는 데이터의 경우 Nb, 키의 경우 Nk로 나타낸다. 라운드 수 Nr은 키 길이에 따라 표 1과 같이 결정된다.

표 : 키 길이와 라운드 수의 관계

	키 길이 (Nk)	블록 크기 (Nb)	라운드 수 (Nr)
AES-128	4	4	10
AES-192	6	4	12
AES-256	8	4	14

AES는 첫 라운드 키 더하기, Nr-1번의 라운드, 최종 라운드로 구성된다. Nr-1번의 라운드 중 한 라운드와 최종 라운드를 의사(Pseudo) C 코드로 나타내면 다음과 같다.

Round (State, RoundKey)

{

ByteSub (State) ;

ShiftRow (State) ;

MixColumn (State) ;

AddRoundKey (State, RoundKey) ;

}

FinalRound (State, RoundKey)

{

ByteSub (State) ;

ShiftRow (State) ;

AddRoundKey (State, RoundKey) ;

}

ByteSub 변환은 상태의 각 바이트에 독립적으로 비선형 바이트 치환을 행하는 것이다. ShiftRow 변환은 상태의 각 행을 정해진 수만큼 쉬프트 하는 것이다. MixColumn 변환은 상태의 각 열을 GF(28)에서의 다항식으로 간주하여 다음으로 주어지는 c(x)를 곱한 후 x4+1에 대해 모듈러 연산을 한 결과이다.

c(x) = '03'x3 + '01'x2 + '01'x + '02'

AddRoundKey 변환에서는 Exclusive-OR를 사용하여 라운드 키를 상태에 적용한다.

각 라운드 키는 키 스케쥴에 의해 암호화키로부터 만들어진다. 키 스케줄은 키 확장과 라운드 키 선택으로 이루어진다. 확장된 키는 4바이트 워드의 선형 배열로 생각할 수 있으며 W[Nb*(Nr+1)]로 나타낼 수 있다. Nk가 6이하인 경우의 키 확장은 다음과 같은 의사 C 코드로 나타낼 수 있다.

KeyExpansion(byte Key[4*Nk], word W[Nb*Nr+1)])

{

for(i=0; i<Nk; i++)

W[i] = (Key[4*i], Key[4*i+1], Key[4*i+2], Key[4*i+3]);

for(i=Nk; i<Nb*(Nr+1); i++)

{

temp = W[i-1];

if(i%Nk == 0)

temp = SubByte(RotByte(temp)) ^ Rcon[i/Nk];

W[i] = W[i-Nk]^temp;

}

}

2. Differential Power Analysis(DPA)

DPA는 반도체 칩에서 데이터 값이 0인 경우와 1인 경우에 소모 전력에서 차이가 있는 점을 이용한다. 구체적인 적용 절차는 다음과 같다.

a. n번(예를 들면 1000) 동일한 키를 이용하여 임의로 생성된 데이터를 암호화한다. 암호화 수행 중 처음부터 첫라운드에 해당하는 소모전력 곡선을 저장한다. 입력 데이터를 I1,..., In이라 하고 소모전력 곡선을 C1,..., Cn이라 한다.

b. 암호화 연산의 중간 계산 값 중 평문(또는 암호문)과 암호화 키의 일부분에만 의존하는 값을 선택한다. 예를 들면 AES 암호화 첫 라운드에서 첫 ByteSub의 출력 중 첫번째 비트를 선택할 수 있다. 공격자는 이에 해당하는 암호화 키 8비트를 가정한다. 가정한 키 값을 이용하여 각 평문에 대해 선택한 중간 값이 0으로 계산되는지 1인지를 확인하고 그 값에 따라 전력소모 곡선을 두 그룹으로 나눈다.

c. 각 전력소모 곡선 그룹에 대해 평균을 취하여 평균 전력소모 곡선을 구한다. 두 평균 전력 소모 곡선의 차이를 나타내는 곡선을 계산한다. 키 값을 바르게 추측했다면 이 곡선에서 큰 스파이크를 볼 수 있다.

d. 위의 과정을 남은 열다섯 ByteSub에 적용하여 전체 키 값을 알아낸다.

이 같은 방법을 적용하기 위해서는 키의 일부를 안다고 했을 때 알고리즘 계산 중간에 나타나는 값이 서로 다른 두 입력 값에 대해 같은 값을 갖는지 다른 값을 갖는지 결정할 수 있으면 된다.

3. 마스크 방법

T. Messerges에 의해 제안된 방법이다. 입력되는 평문과 각 라운드 키는 라운드별 바이트별로 생성된 난수와 xor된다. 그리고 S-box는 들어온 데이터에 포함된 마스크를 제거하고 임의로 생성된 마스크가 적용되도록 변환된다. 이와 같이 라운드별 바이트별로 다른 마스크를 사용하여 암복호화 중 어떤 값도 평문과 키의 일부분에 의해 값이 결정되지 않도록 하여 DPA를 적용할 수 없도록 하였다. 하지만 이 방법은 스마트카드 같은 장치에 얼마 없는 RAM을 많이 사용하고 계산량도 많아서 실제 적용에는 문제가 있다. 그림 1은 이 방법의 전체적인 구성을 보여준다.

그림 : 마스크 방법

4. 고정 마스크 방법

일정 수의 고정된 마스크를 미리 만들어 놓고 암호화를 시작할 때 임의로 하나를 선택한다. 고정된 마스크는 ROM에 저장되는데 필요한 용량을 줄이기 위해 라운드에 모두 같은 마스크를 적용할 수 있다. 메모리 량을 더 줄이기 위해 16바이트 모두에 같은 마스크를 사용할 수도 있다. 그림2는 이 방법의 전체적인 구성을 보여준다.

그림 : 고정 마스크 방법

5. 곱셈 마스크 방법

이 방법은 곱셈 마스크와 이진 덧셈 마스크를 사용한다. 처음에는 덧셈 마스크를 사용하다가 S-box에 있는 GF(256)에서의 곱셈에 대한 역원을 구하기 전에 곱셈 마스크로 변환하고 이후에 다시 덧셈 마스크로 바꾼다. 이 방법에 의하면 S-box를 다시 계산할 필요가 없고 RAM에 저장할 필요도 없다. 그림 3은 마스크가 없을 때와 있을 때 라운드 구성을 나타내며 그림 4는 마스크가 없을 때와 있을 때 S-box계산 과정을 나타낸다.

그림 : 마스크가 없을 때와 있을 때의 라운드 구성

그림 4: 마스크가 없을 때와 있을 때의 S-box 계산

그림 5는 덧셈 마스크와 곱셈 마스크 사이의 변환과정을 보여준다.

그림 5: 덧셈 마스크와 곱셈 마스크 사이의 변환

하지만 Golic은 CHES 2002에서 이 방법이 DPA에 취약함을 보였다. 위의 그림에서 Ai,j(i: 라운드 번호, j: 블럭에서의 위치)가 0이면 역원을 구하기 전과 후에 마스크에 상관없이 마스크된 값이 0이라는 것을 알 수 있다. 해당 데이터와 키 값이 동일한 경우 Ai,j는 0이 되고 DPA공격을 받게 된다. 입력 값과 키 일부에 의해 값이 정해지는 중간 값을 알기 때문에 DPA가 가능한 것이다. 더욱이 Ai,j가 0인 경우 두 곳에서 0이 나타나게 되며 이 때문에 DPA에 더욱 취약하게 된다. 구체적인 공격 방법은 다음과 같다. Ai,j가 0이라고 가정하고 키 한 바이트를 가정한다. 계산에 의해 전력소모 곡선을 Ai,j가 0인 그룹과 아닌 그룹으로 나눈다. 각 그룹의 평균 전력 소모 곡선을 구한 후 두 곡선의 차이를 구한다. 차이 곡선에서 스파이크를 발견할 수 있으면 키를 바르게 추측한 것이다.

6. 제안하는 방법

고정 마스크 방법을 더욱 간단하게 할 수 있다. 평문이 들어왔을 때 전체 바이트에 동일한 마스크를 적용하고 입력 마스크와 출력 마스크가 동일한 S-box를 사용하면 그림 6과 같이 된다. 이렇게 하면 필요한 메모리는 각 마스크마다 초기 마스크를 위해 1 바이트, 최종 마스크를 위해 1 바이트, 변환된 S-box를 위해 256바이트 총 258바이트이다. 또 각 라운드 키에 마스크를 적용하는 연산이 없어진다. 이 방법은 기존 고정 마스크 방법 중 가장 간단한 방법과 비교하면 다음과 같다. 가장 간단한 방법은 첫 라운드 키를 위한 마스크 1 바이트, 중간 라운드 키를 위한 마스크 1 바이트, 최종 라운드 키를 위한 마스크 1 바이트, 총 3 바이트가 마스크 저장을 위해 필요하다. S-box 저장에 필요한 메모리는 제안된 방법과 같다. 연산량 측면에서는 각 라운드 키마다 마스크와 xor를 해야하기 때문에 AES-128의 경우 11곳에서 xor를 수행하게 되고 총 연산수는 11 x 16 = 176이다. 반면 개선된 방법은 처음에 한 번, 마지막에 한번, 11 x 2 = 32번의 xor만이 필요하다.

그림 6: 제안하는 개선된 고정 마스크 방법

7. 제안한 방법의 DPA에 대한 안전성

개선된 방법은 평문이 들어오면 미리 저장된 마스크 중 임의로 한 마스크를 택해 바로 평문값을 변경한다. 마스크가 임의로 선택되기 때문에 공격자는 평문이 어떤 값으로 바뀌었는지 알 수 없게 된다. 2차 DPA에 의한 공격이 발표되기는 했으나 2차 DPA는 내부 구현을 알아야 적용할 수 있기 때문에 실제로 사용하기는 쉽지 않다. 마스크된 값은 마지막에 가서야 원래의 값으로 환원되기 때문에 암호문에서 거슬러 올라가는 공격도 불가능하다.

Ⅲ. 결론

본 논문에서는 저가 스마트카드에 적합한 고정 마스크 방법의 개선 방안을 제안하였다. 제안한 방법을 AES-128을 기준으로 기존 방법과 비교하면 다음과 같다.

표 : 기존 방법과 제안한 방법과의 비교

	기존 방법	제안한 방법
마스크 저장을 위한 메모리 사용량	3바이트	1바이트
마스크 적용을 위한 xor 횟수	176회	32회

참고문헌

[1] P. Kocher, J. Jaffe, and B. Jun, "Differential Power Analysis", Advances in Cryptology - Crypto '99, LNCS 1666, pp. 388-397, 1999

[2] T. Messerges, "Securing the AES Finalists Against Power Analysis Attacks", FSE 2000, LNCS 1978, pp. 150-164, 2001

[3] C. Clavier, J. Coron, and N. Dabbous, "Differential Power Analysis in the Presence of Hardware Countermeasures", CHES 2000, LNCS 1965, pp. 252-263, 2000

[4] K. Itoh, M. Takenaka, and N. Torii, "DPA Countermeasure Based on the Masking Method", ICICS 2001, LNCS 2288, pp. 440-456, 2002

[5] M. Akkar and C. Giraud, "An Implementation of DES and AES, Secure against Some Attacks", CHES 2001, LNCS 2162, pp. 309-318, 2001

[6] J. Golic and C. Tymen, "Multiplicative Masking and Power Analysis of AES", CHES 2002, LNCS 2523, pp. 198-212, 2003

[7] E. Trichina, D. Seta, and L. Germani, "Simplified Adaptive Multiplicative Masking for AES", CHES 2002, LNCS 2523, pp. 187-197, 2003