[Side Channel] 암호 알고리즘 AES CPA 공격

글을 읽기 전, AES CPA 공격을 위해 AES 암호 알고리즘의 구조는 이미 알고 있어야 한다.

본문은 AES 암호 알고리즘의 구조를 설명하는 것이 아닌, 암호 알고리즘을 Correlation Power Analysis 공격을 통해 추출하는 글이다.

 

AES 구조에 관한 레퍼런스 자료 - https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.197.pdf

CPA 에 관한 레퍼런스 자료 - https://www.iacr.org/archive/ches2004/31560016/31560016.pdf

---

Outline

우리는 2가지의 정보를 알고 있다고 가정한다.

1. 암호 알고리즘 연산의 전력을 측정한 파형

2. 암호 알고리즘의 입력값

 

 

부채널은 데이터를 어떻게 다루냐도 매우 중요하다.

자료를 해석할 수 있는 능력이 되게 중요하다. 그중 파형의 자료형또한 중요한데 현재 4바이트 단위로 끊어져 나와있고

앞 2바이트가 대부분 비는 것을 보아 Little Endian으로 추정해본다.

파형 헤더에 따라 파형을 읽었다. SPA를 통해 라운드 반복 연산을 확인해보자.

 

다음 입력에 대한 파형을 올렸을 때 정렬 여부도 따져봐야한다. 각각 다른 입력에 대한 전력 파형을 겹쳐서 파형이 정렬되었는지 확인도 해야한다.

정렬이 된 파형

아래는 정렬이 되지 않은 예시다

정렬이 되지 않은 파형

---

CPA

이제 AES 마스터키를 추출해보자.

 

AES 구조에 따라 0라운드 AddRoundKey 과정에서 MasterKey가 평문과 XOR 되는 것을 확인할 수 있었다.

그 이후 바로 1라운드 SubBytes 과정을 연산한다. 

 

우리는 평문을 알고 있다. 평문에 어떤 키가 더해지는지를 알고 싶은거다. 

평문의 첫 번째 바이트를 알고 있고 0라운드를 거치면 MasterKey의 첫 번째 바이트와 XOR되는 사실도 알고 있다.

결국 평문 각각의 바이트에는 0부터 255(0x00-0xff)개의 값중 한 값이 무조건 XOR된다.

 

또한 그 값(중간 값)은 1라운드의 SubBytes를 거칠 예정이다. 우리는 중간 값을 예측할 수 있다. 

 

중간 값 타깃은 1라운드 SubBytes를 거친 이후로 한다.

-> 타깃 Sbox[Plaintext^Key], Key -> 0 1 2 ... 255

Plaintext ^ AddRoundKey의 값을 예측해도 충분히 CPA가 가능하다.

하지만, SubBytes를 거치고 가는 가장 큰 이유는 AddRoundKey만 거칠 경우 중간 값이 크게 변하지 않는다.

중간 값의 변화가 크다는 것은 해밍웨이트의 변화 또한 크다는 것을 의미한다.

 

만약 첫번째 바이트 평문이 0xA0이고 키가 0x22일 경우 AddRoundKey를 거치면 0x82이라는 결과가 나온다. 

-> 0xA0에서 0x82로 값이 바뀌었음에도 불구하고 해밍웨이트의 변화는 없다. 따라서 전력 소비가 변한 시점을 알기 어렵다. 해밍웨이트의 변화가 조금 있었다고 해도 보통은 노이즈에 의해 구분이 어렵다.

하지만 SubBytes를 거칠 경우 0xA0이 0x13이 된다.

-> 해밍웨이트의 변화는 2에서 4이므로 다른 중간값까지 모이면 전력 소비가 구분될 것이다. 

AES Sbox

 

 

측정된 파형 개수 = 입력된 평문의 개수 (16바이트)

1. 모든 파형의 동일구간 계측된 전력량 (측정된 파형 개수 만큼)

2. 추측 키를 바꿔가며 예측하는 1라운드 SubBytes 이후 중간값의 해밍웨이트 (입력 평문의 개수 만큼)

키를 0부터 255까지 바꿔가며 상관계수를 구한다.

 

만약 측정된 파형 중 우리가 예측한 중간 값이 파형 구간에서 나올 경우 소비 전력에 맞추어 높은 상관계수를 보일 가능성이 크다.

 

실제로 CPA 공격을 실행하면 노이즈가 많이 없을 경우 아래와 같이 1에 근접한 상관계수를 보여준다.

1 Round SubBytes Attack

실제로 CPA로 추출한 마스터키는 실제 AES 연산에 사용된 마스터키임을 알 수 있다.

Correlation Trace

상관계수 파형(Correlation Trace)를 띄워보면 다음과 같다.

 

기존 AES 전력파형과 같이 띄워보았다. 1라운드 Sbox를 거친 이후니 파형 상에서도 Peak가 띄는 부분이 해당 중간 값을 연산한 파트라고 볼 수 있다.

 

AES CPA에 대한 중간값 타깃과 해밍웨이트 구하는 코드는 다음과 같다.

for(i = 0 ; i < 16 ; i++) {
	...
 	for(key = 0 ; key < 256 ; key++) {
    ...
    
    iv = Sbox[PT[j][i] ^ key];

    hw_iv = 0;
    for (k = 0; k < 8; k++) hw_iv += ((iv >> k) & 1);
    ...
    }
	...
}