2020 암호경진대회 4번 문제 풀이 (1)

출처 : cryptocontest.kr/

Home - SEC연구소 | 암호분석경진대회

문제 해결을 위한 첨부파일이 있지만 용량 문제로 업로드 하지 않았습니다. SEC 연구소 홈페이지에서 다운 받아주세요.

또한 문제에 문제 해결을 위한 오픈 소스가 올라와있지만, 구 버전 matlab이라 최신 버전 matlab에서 호환 되지 않는 점 참고 바랍니다. (저는 그냥 python으로 직접 짜서 풀었습니다. 이 문제도 변수 이름 등을 너무 중구난방으로 잡아서 정리가 된 후 깃헙에 올리도록 하겠습니다.)

 

여름 동안 머리를 싸매고 풀었던 4번 부채널분석문제입니다. 

문제 해결을 위해 첨부파일을 풀면 hwp.encrypted 파일과 PowerConsumption.csv 파일을 얻을 수 있습니다. 

이 친구들을 이용해 부채널 분석으로 암호화된 hwp 파일을 풀어봅시다.

(문제를 잘 읽어보면 이 한글 파일을 복호화하면 문제가 또 나온다고 합니다. 이것도 풀어야합니다.)

 

1. 문제 접근

우선 부채널 분석이 무엇인지 알아야합니다. 부채널 분석이란, 암호화 알고리즘에 사용된 수학적인 취약점이 아닌, 전력 소비량, 소리 측정 등 물리적인 특성을 이용한 공격 방법입니다.

 

부채널 분석 중 전력 소비량을 이용하는 방법으로는 DPA (Differential Power Analysis, 차분 전력 분석),

CPA (Correlation Power Analysis, 상관 전력 분석)가 있습니다. 우리는 그 중 CPA를 이용할 것입니다. 

 

CPA와 관련된 논문은 아래와 같습니다. (문제에 나온 논문입니다.)

 

31560016.pdf

0.35MB

논문의 내용 중 문제 풀이에 필요한 부분을 살펴보겠습니다.

(논문 전체 내용을 다 설명하기에는 길어서 생략하겠습니다.)

 

논문에서 필요한 부분을 살펴보면, 우선 Hamming Weight라는 개념이 나옵니다.

Hamming Weight란, 단순히 어떤 데이터의 bit 중 1의 개수를 의미합니다. 

그리고 Hamming Distance란 R->D로 데이터가 변경되었을 때 바뀐 bit의 개수를 의미합니다. 

식으로는 Hamming distance = H( D ^ R) 을 이용하면 됩니다. (H : Hamming weight)

xor 연산에서 같은 bit 위치의 값이 동일하면 0 다르면 1이므로 위 식은 금방 이해되실 겁니다.

 

그 다음으로 상관계수 식입니다. 사용되는 상관계수 식은 다음과 같습니다. (Pearson 상관계수 사용)

우선 상관계수의 수학적 정의는 두 변수 사이의 통계적 관계를 표현하기 위한 상관 관계 정도입니다. ±1에 가까울 수록 상관관계가 강한 것이고 0에 가까울 수록 상관관계가 적은 것입니다.

 

pearson상관계수의 일반적인 형태는 아래와 같습니다.

이제 다시 위의 상관계수 식을 살펴보면 W와 H의 상관관계를 나타냈음을 짐작할 수 있습니다. 또한 실제 피어슨 상관계수 식에 전력 모델과 Hamming distance 모델을 대입한 결과가 위와 같으므로 위 식을 이용합시다.

식에 사용된 변수에 대해 살펴봅시다.

$N$ : 필요한 sample의 개수, 즉, AES 암호화에 사용된 블럭 개수 1025개 ( i : 0~1024 )

$W_i$ : i 번째 전력 파형, 즉 i 번째 20000개의 전력 파형 

$H_{i,R}$ : 메시지 $M_i$ 와 reference $R$ 사이의 Hamming distance, 즉, 주어진 암호문을 R이라 생각하고, 해당 블럭을 어느 정도 연산 (복호화) 하였을 때의 Hamming Weight

 

정리가 잘 안 되어있지만, 위 상관계수 식을 표현하면 다음과 같습니다. 

( W_H : $W_i$ * $H_{i,R}$, np : numpy )

def corr(W,H):  
    N=1025 # AES 블럭 :1025개
    W_H=[0]*1025
    for i in range(1025):
        W_H[i]=W[i]*(H[i])
    sum_WH=sum(W_H)
    
    g=np.array(W)
    h=np.array(H)
    return (N*sum_WH-sum(W)*sum(H))/(((N*sum(g**2)-(sum(W))**2)**0.5)*((N*sum(h**2)-sum(H)**2)**0.5))

문제에서 주어진 마지막 라운드 키(hex)는 다음과 같습니다. ( * : 모르는 값 )

$$\mathbf{K} = \left[\begin{array} {rrrr} 22 & E9 & * & * \\ E5 & * & * & 9B \\ * & * & 5B & * \\ * & 4C & 2C & * \end{array}\right] $$

 

또한, 주어진 전력파형이 7,8 라운드의 연산의 전력소비량이므로 attack point 와 AES 암호화 과정을 나타내면 다음과 같습니다.

위의 8라운드가 끝난 지점이 attack point가 되는 이유는, 주어진 전력 파형이 7,8 라운드 연산에 사용된 전력소비량이고,그렇다면 8라운드의 전력소비량과 attack point까지 복호화를 진행하였을 때의 HW (Hamming weight) 값 사이의 상관계수를 구했을 때 어떤 특정 값에서 뾰족하게 튀어나올 것입니다. 

하지만 우리는 아직 9라운드 키도 모르고 9라운드까지 복호화하였을 때 message가 뭔지도 모릅니다. 그렇다면 9라운드 키를 구하는 것이 관건입니다.

 

이제 문제를 제대로 풀어봅시다.

2. 문제 풀이

(문제 풀이는 AES의 기본 구조에 대해서는 생략하겠습니다.)

우선 9라운드 키를 구하기 전에 10라운드부터 뚫어야 CPA를 9라운드 키에 대해 적용하든말든 합니다.

10라운드부터 알 수 있는 값부터 뚫어봅시다. AES가 블록암호임을 이용하여 각 블록(16byte)별로 알 수 있는 것은 주황색, 모르는 것은 파란색으로 칠하면 다음과 같습니다.

 

(1) 주어진 마지막 라운드 키 이용하여 add_round 진행

(2) inverse shift row 진행, inverse subbyte 진행

(3) 9라운드의 inverse mixcolumn 진행 

 

뭔가 (3) 과정에서 건너뛴것 같습니다. 9라운드의 라운드키를 모르는데 어떻게 add round를 넘어갔느냐 할 수 있지만 다음과 같은 방법으로 add round와 mix column 순서를 바꿀 수 있습니다.

 

암호문을 C, 9라운드의 라운드키를 K라 하면 다음과 같습니다.

Inv_MixColumn ( C ^ K ) = Inv_MixColumn(C) ^ Inv_MixColumn(K)

이는 행렬의 곱 성질을 이용한 것입니다. ( A*(B+C) = AB+AC )

XOR 연산은 선형성이 유지되므로 위 식을 만족합니다. 

 

이제 우리가 구해야할 것은 9라운드의 라운드 키에 Inv mix column을 취한 값이 됩니다. 즉 아래와 같은 과정을 거쳐야 하는 것이지요. (subbyte와 shiftrow는 순서가 바뀌어도 결과가 동일하므로 편한 순서로 하면 됩니다.)

위 (2) 에서 mixcolumn을 취하기 위해서는 행렬의 열을 통째로 알아하기 때문에 우리는 (3) 과 같은 그림을 얻을 수 있습니다. subbyte, shiftrow는 AES 알고리즘에 의해 그냥 계산할 수 있으므로 이제 attack point에 도달할 수 있게 되었습니다!

 

우리는 9라운드의 라운드 키를 찾기 위해 (3)의 주황색 부분에 대해 256^4 가지를 조사할 수도 있지만 그것보다는 1byte씩 조사를 하는 경우가

더 시간이 적게 들기 때문에 (4 * 256) 1byte 단위로 CPA를 실행합니다.

 

우선 (3)의 주황색 부분의 첫 번째 부분 (맨 위)에 대해 해당 byte에 0~255를 add round를 진행 후, subbyte, shiftrow를 진행하여 8라운드 전력부분과 CPA를 실행합니다.

(주어진 전력파형이 20000point 이므로 10000point 정도 돌리시면 됩니다. 저는 넉넉하게 11000point 정도 잡고 돌렸습니다.)

 

그리하면 위와 같이 149만 툭 튀어나오는 것을 알 수 있습니다.

(식 세우기에 따라 -1에 가까운 값이 나올 수도 있습니다.)

(참고 : 컴파일러는 spyder, PC는 RAM 8GB, CPU i3를 이용했을 때 149라는 하나의 값을 얻기 위해 약 1시간 정도 소요되었습니다. 친구의 최신형 맥북 pro로 돌려보니 약 40분 정도 걸렸던것 같습니다. 나도 맥북 사고 싶다.)

 

이제 이 과정을 나머지 주황색 byte에 대해 진행하면 다음과 같습니다.

이제 구한 값에 다시 MixColumn을 취하면 우리가 처음 구하고자 했던 9라운드의 라운드 키의 첫번째 열을 얻을 수 있습니다. (hex)

이로써 9라운드의 키의 첫번 째 열을 구하였습니다. 이제 키 스케쥴링을 이용하여 10라운드키와 9라운드키의 관계를 알아봅시다.

10라운드와 9라운드키를 키스케쥴링을 통해 위와 같이 얻을 수 있습니다. 이제 9라운드 키의 두번째 열 위와 같은 방식으로 똑같이 구할 수 있습니다.

그러하면 다음과 같은 결과를 얻을 수 있습니다.

이제 여기서 9라운드 키의 세번째 열을 구하려고 하면 안 됩니다. 구한 10라운드키의 일부를 이용해 복호화 과정을 진행하여 9라운드의 mixcolumn 과정에서 세번 째 또는 네번 째 열을 알아야하지만 계산하면 다음과 같습니다. (M,N은 무시하셔도 됩니다.)

3번째 열이든 4번째 열이든 한 줄 통째로 알 수 있는 부분이 더 이상 없습니다. 4번째 열이 그나마 2칸이 비워져있지만 이를 CPA를 적용하기 위해서는 256^2 번을 해야됩니다. 

(256가지에 대해 전수조사 하는데도 1시간 정도 걸리는데 256시간을 돌릴 순 없겠죠? 처음에는 256시간 돌릴까도 생각했지만 다른 방법이 있었습니다!)

 

10라운드 키와 9라운드 키의 키 스케쥴링 관계를 이용하면 변수 2개를 이용하여 최종적으로 구하면 되는 9라운드 키를 구할 수 있습니다.

10라운드 키의 구하지 못한 부분에 x,y 변수를 이용하여 계산하면 위와 같습니다. 이제 이걸 사용해야하는데 문제에 힌트가 주어져있습니다. 

한글파일은 Compound File Binary Format이므로 최초 8 bytes는 ‘D0 CF 11 E0 A1 B1 1A E1’이다.

참고사항의 내용 중 hwp파일의 file header signature가 주어져 있습니다. (물론 구글에 쳐도 나옵니다.)

위 파일이 CBC 모드로 암호화 되어있으므로 첫 IV={0,0,...,0} 입니다. 그러므로 암호문의 첫 블럭의 최초 8byte값을 256^2 가지의 (x , y)에 대해 복호화하면 header signature와 일치하는 (x, y)가 나오게 되고 그것이 10라운드 키의

x, y 값이 됩니다. 직접 구해보면 하나밖에 안 나오므로 한 가지 경우에 대해서만 복호화를 진행하면 다음과 같습니다.

 

이제 마스터키를 구했으므로 문제를 다 풀었습니다! 

실제 복호화한 파일은 다음과 같습니다. (글씨체와 굵기는 제가 읽기 편하도록 바꾸었습니다.)

 

4번 결과.hwp

0.03MB

다음 포스팅에서 위 복호화한 한글파일의 문제를 풀어보도록 하겠습니다.

3. 추가 내용

문제의 마지막에 이런 내용이 있습니다.

평가 참고사항 :
- 본 문제는 ⓵파일 복호화 단계와 ⓶복호화된 파일 내의 시험문제인 공개키 암호(전자서명) 해독 단계의 두 단계로 구성되며 각각의 배점은 ⓵단계(75점), ⓶단계(25점)이다.
- 본 문제의 ⓵단계 해결 시, 상관전력분석과 대칭키 암호키 전수조사를 함께 수행해야 할 수 있다. 암호키를 찾은 동점자 발생 시, [(전력분석에 사용한 키 전수조사 범위) * 1,025 * 20,000 + (대칭키 암호키 전수조사 범위)] 의 수치가 작은 제출자에게 가점을 부여할 예정이다. (상관전력분석과 대칭키 암호키 전수조사 중 사용하지 않는 방법이 있다면 그 방법은 전수조사 범위를 1로 계산)

한 마디로 CPA는 적게, 대칭키 전수조사는 많이 하라는 말입니다. 실제로 CPA의 경우 위 사양의 PC에서 1byte 값을 찾는데 256가지의 조사로 약 1시간이 소요되지만, 대칭키 전수조사의 경우, 위와 같이 256^2 가지에 대해 조사하면 1분

정도면 충분했습니다.

 

이제 위 조건을 만족하도록 식을 짜봅시다.

식은 위에서 변수 2개 x,y를 잡은 것과 유사하게 진행하면 됩니다. 

CPA 과정에서 9라운드 키의 두번 째열을 찾지 않았다고 가정하고 계산하면 다음과 같습니다.

CPA를 4번 진행 후, 한 줄을 통으로 변수로 잡으면 키스케쥴링에 의해 w 값을 나머지 변수 3개에 대해 계산할 수 있습니다. 그렇다면 이제 변수에 대해 9라운드 두번 째 열까지 계산한 것이 되므로 나머지 변수 2개 ( 위의 10라운드 키의 x,y 부분 ) 까지 합쳐 총 256^5 가지 경우에 대해 대칭키 암호키 전수조사를 시행할 수 있습니다. 

 

마찬가지로 CPA를 5번 진행 후 같은 과정을 반복, 6번 진행 후 반복 등으로 위 주어진 식을 언제 가장 적은 값으로 만족하는 지 계산하면 다음과 같습니다.

이로써 위 조건을 만족시키는 것은 CPA를 5번 시행했을 때임을 알 수 있습니다. 

결과적으로 마스터키도 찾고, 언제 가장 빠를지도 찾았습니다!

4. 후기

 5번은 다른 친구가 맡아서 하였고 (물론 끝이 없는 문제라 4번을 해결하고 제출 직전까지 같이 생각했다.) 4번은 제가 맡아서 했습니다. AES도 뭔지 알고, CPA가 무엇인지도 알고 있었지만, 직접 코드를 짜고, 논문을 이해하고 하다보니 생각보다 시간이 아주 많이 걸렸습니다. (논문 이해하는데 1주일 가까이 걸린 것 같다.) 또한 CPA 를 실행하는데 1byte 당 1시간이나 걸리고, 중간에 키스케쥴링 계산을 잘못하는 과정도 몇 번 있었기에 아주 힘든 문제였습니다. 하지만 이번 문제를 풀면서 CPA에 대해 한 층 더 알게 되었고, 주어진 matlab 라이브러리가 아닌 python을 이용하여 모든 코드를 다 구현한 것은 정말 큰 경험이었습니다.  (코드를 좀 정리하여 제출한 답안과 함께 깃헙에 올리도록 하겠습니다.) 

 이 문제를 통해 정말 값진 것들을 얻었습니다. 몇 주 동안 안 되던 것을 해결했을 때 그 쾌감, 나도 할 수 있다는 자신감을 얻었습니다. 저 스스로에게 자랑스러워질 수 있었던 시간이었습니다. 

 또한 위 문제 풀이로 부채널분석 시상식에서 최우수상을 수상하여 많은 교수님들과 기업 관계자분들 앞에서 문제 풀이의 기회가 있었지만, 마침 그 때 학교 시험이 있어 5번 문제를 맡은 친구에게 속성으로 가르쳐 대신 발표를 보냈었습니다. (갤럭시 버즈 줬다는데 너무 아쉽다....) 여러 난관과 에피소드가 있었지만 저에게는 아주 의미 깊은 문제였습니다!