오랜만에 블로그를 써본다.
지난해 화이트햇을 마치고 BoB의 보안제품개발 트랙에 붙어서 프로젝트가 끝난뒤 정보보안 스타트업에 취직하게되어서 직무를 준비하는 과정에 대해서 써볼 예정이다. 많은 양은 쓰지 못하겠지만 직무를 준비하면서 써보겠다.
먼저 내 직무는 암호 모듈 개발자로 C를 이용한 암호 라이브러리나 하드웨어 모듈을 만들게 될 예정이다. 그에 따라 준비하기위해서 기초적인 암호 알고리즘을 작성해볼것이고 더 나아가 KCMVP에 대해 분석해보며 정리할 예정이다.
이번 글에서는 DES에 대해 작성해 보겠다. 개발에 앞서 면접을 볼때 paper만 보고도 암호 알고리즘을 작성할 줄 알아야한다고 해서 최대한 인터넷에 있는 코드들은 보지 않고 paper만 보고 작성해보고자 했다. 보통의 유명한 암호화 알고리즘인 DES, AES, RSA, ECC등은 NIST의 표준이기에 구글에 검색해보면 NIST사이트에 표준이 있기에 DES 표준을 보면서 개발해 보았다.
DES는 1977년 만들어진 블록 암호화 알고리즘으로 64bit의 키와 64bit의 블록을 가지고 암-복호화를 한다.
KEY 생성 및 스케줄링
64bit KEY 생성
키값은 윈도우나 리눅스의 난수 생성 함수를 통해 64bit는 생성하면 된다.
KEY 스케줄링
64bit 키를 스케줄링을 통해 16개의 48bit sub key를 생성하는 과정이다.
순서는 아래와 같다.
- 정해진 테이블을 이용한 PC-1함수를 통해 64bit를 56bit로 치환한다.
- 바뀐 56bit를 왼쪽, 오른쪽 28bit로 나눈다. (shift 혹은 & 연산)
3. 각 R과 L을 정해진 테이블대로 Left로 shift 해준다.
4. 1번과 같이 L, R을 합친뒤(56bit) PC2를 통해 48bit로 치환하여 서브키를 생성한다. - 3~4번을 16번 반복하면서 48bit round key를 16개 생성한다.
ENC, DEC
암복호화는 대칭키 암호화 알고리즘으로 혼돈, 확산을 응용해 알기 어렵게 하는것이다.
암호화 순서는 아래 글과 사진으로 설명한다.
- input을 64bit 블록 단위로 나눈다.
- 블록을 IP를 통해 테이블 치환을 한다.
- L, R 32bit씩 나눈다.
4. R을 f(R)을 통해 혼돈과 확산시킨다.
5. 4번의 결과로 나온 R을 L과 xor한다.
6. 5번 결과값을 R에 넣는다.
7. 초기 R값을 L에 넣어 R과 L값을 swap한다.
8. 위 4~7번을 16번의 라운드를 거친다. - 마지막 라운드의 결과는 R과 L을 swap하지 않고 64bit(output)로 합친다.
- output을 IIP를 통해 역치환을 한다.
위 암호화 라운드를 표현한 그림
아래는 암호화 라운드 내부의 f()함수가 어떤 작동을 하는지에 대한 그림이다.
순서대로 설명하겠다.
1. R(Half Block)을 Expansion 테이블을 사용하여 48bit로 확장한다.
2. key 스케줄링을 통해 만들었던 서브키(round key)를 확장한 R과 xor한다.
3. 2번의 결과 값을 6bit 8개로 나누어서 S-box를 이용해 32bit로 축소 시킨다.
4. 3번의 결과 값을 주어진 P 테이블을 이용해 치환한다.
암호화 내부 f함수의 동작도
위와 같은 동작을 구현하면 64bit블록을 암호화 구현할 수 있다.
코드는 아래와 같다.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>
#include <windows.h>
#include <bcrypt.h>
#pragma comment(lib, "bcrypt.lib")
/*
* DES는 미국에서 1977년 발표된 대칭키를 사용하는 블록 암호화 알고리즘이다.
* DES는 키 길이가 64bit이며, 블록의 크기도 64bit이다.
* 암호화 과정은 다음과 같다.
* RNG를 통해 64bit 키를 생성한뒤 키 스케줄링을 통해 16개의 서브키를 생성한다.
* 만든 16개의 서브키를 사용하여 64bit의 평문을 16라운드에 걸쳐 암호화한다.
* 혼돈과 확산 개념을 사용하여 암호화를 거치며 최종적으로 64bit 암호문을 생성한다.
*/
const int message_initial_permutation[64] = {
58, 50, 42, 34, 26, 18, 10, 02,
60, 52, 44, 36, 28, 20, 12, 04,
62, 54, 46, 38, 30, 22, 14, 06,
64, 56, 48, 40, 32, 24, 16, 8,
57, 49, 41, 33, 25, 17, 9, 01,
59, 51, 43, 35, 27, 19, 11, 03,
61, 53, 45, 37, 29, 21, 13, 05,
63, 55, 47, 39, 31, 23, 15, 07
};
const int inverse_message_final_permutation[64] = {
40, 8, 48, 16, 56, 24, 64, 32,
39, 07, 47, 15, 55, 23, 63, 31,
38, 06, 46, 14, 54, 22, 62, 30,
37, 05, 45, 13, 53, 21, 61, 29,
36, 04, 44, 12, 52, 20, 60, 28,
35, 03, 43, 11, 51, 19, 59, 27,
34, 02, 42, 10, 50, 18, 58, 26,
33, 01, 41, 9, 49, 17, 57, 25
};
const int expansion_p_box[48] = {
32, 01, 02, 03, 04, 05,
04, 05, 06, 07, 8, 9,
8, 9, 10, 11, 12, 13,
12, 13, 14, 15, 16, 17,
16, 17, 18, 19, 20, 21,
20, 21, 22, 23, 24, 25,
24, 25, 26, 27, 28, 29,
28, 29, 30, 31, 32, 01
};
const int straight_p_box[32] = {
16, 07, 20, 21,
29, 12, 28, 17,
01, 15, 23, 26,
05, 18, 31, 10,
02, 8, 24, 14,
32, 27, 03, 9,
19, 13, 30, 06,
22, 11, 04, 25
};
const int left_shift[16] = {
1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
};
const int S1[4][16] = { 14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,
0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,
4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,
15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13
};
const int S2[4][16] = { 15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10,
3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5,
0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15,
13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9
};
const int S3[4][16] = { 10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8,
13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1,
13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7,
1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12
};
const int S4[4][16] = { 7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15,
13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9,
10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4,
3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14
};
const int S5[4][16] = { 2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9,
14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6,
4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14,
11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3
};
const int S6[4][16] = { 12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11,
10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8,
9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6,
4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13
};
const int S7[4][16] = { 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1,
13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6,
1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2,
6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12
};
const int S8[4][16] = { 13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7,
1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2,
7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8,
2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11
};
const int permuted_choice1[56] = {
57, 49, 41, 33, 25, 17, 9,
01, 58, 50, 42, 34, 26, 18,
10, 02, 59, 51, 43, 35, 27,
19, 11, 03, 60, 52, 44, 36,
63, 55, 47, 39, 31, 23, 15,
07, 62, 54, 46, 38, 30, 22,
14, 06, 61, 53, 45, 37, 29,
21, 13, 05, 28, 20, 12, 04
};
const int permuted_choice2[48] = {
14, 17, 11, 24, 01, 05,
03, 28, 15, 06, 21, 10,
23, 19, 12, 04, 26, 8,
16, 07, 27, 20, 13, 02,
41, 52, 31 ,37, 47, 55,
30, 40, 51, 45, 33, 48,
44, 49, 39, 56, 34, 53,
46, 42, 50, 36, 29, 32
};
// char 2byte, int 4byte
// 16bit * 4 , 32bit * 2
// DES는 64bit 블록 암호화 구현
// key 생성 함수 windows.h에 있는 BCryptGenRandom 함수 사용
uint64_t Key_Generation() {
uint64_t key = 0;
// BCryptGenRandom 함수 호출로 암호학적으로 안전한 난수 생성
if (BCryptGenRandom(NULL, (PUCHAR)&key, sizeof(key), BCRYPT_USE_SYSTEM_PREFERRED_RNG) != 0) {
fprintf(stderr, "Error generating random bytes\n");
exit(EXIT_FAILURE);
}
return key;
}
// 치환 함수(분석 필요)
uint64_t Permuter_Choice(uint64_t var, const int pc[], int number) {
int a;
uint64_t numb = 0x00;
uint64_t aft_ch = 0x00;
for (a = 0; a < number; a++) {
numb = var >> ((number + 8) - pc[a]);
if (number == 56) // 64->56(pc1)
{
numb = numb << (number + 7);
numb = numb >> (a + 8); 56비트를 만들기 위해서는 8을 더해줌
aft_ch = (aft_ch | numb);
}
else // number = 48 // 56->48(pc2)
{
numb = var >> ((number + 8) - pc[a]);
numb = numb << (number + 15);
numb = numb >> (a + 16);
aft_ch = (aft_ch | numb);
}
}
return aft_ch;
}
// 32비트를 p_box를 가지고 48비트로 확장 (분석 필요)
uint64_t Expansion_Bit(uint32_t R) {
uint64_t res = 0;
for (int i = 0; i < 48; i++) {
res |= (uint64_t)((R >> (32 - expansion_p_box[i])) & 1) << (47 - i);
}
return res;
}
// 32비트를 n만큼 왼쪽으로 회전
uint32_t Rotation(uint32_t num, unsigned int n) {
return (((num << n) & 0xffffffff) | (num >> (28 - n)));
}
// key를 가지고 16개의 subkey를 생성
void Key_Schedule(uint64_t key, uint64_t* sub_key) {
uint64_t tmp = 0;
uint32_t C = 0, D = 0;
tmp = Permuter_Choice(key, permuted_choice1, 56);
C = tmp >> 28;
D = (tmp << 28) >> 28;
for (int i = 0; i < 16; i++) {
C = Rotation(C, left_shift[i]);
D = Rotation(D, left_shift[i]);
tmp = (uint64_t)C << 28;
tmp |= (uint64_t)D;
*(sub_key + i) = Permuter_Choice(tmp, permuted_choice2, 48);
}
}
// 16round를 거치면서 48bit을 32bit으로 축소하는 S-Box
uint32_t S_Box(uint64_t num) {
//num 은 48 bit니까 S_box 들어가기전 6비트 8개로 쪼개줘야함
uint8_t rows[8], cols[8];
uint32_t res = 0x00;
for (int i = 7; i >= 0; i--) {
rows[i] = num & 0b00100001;
rows[i] = (rows[i] & 0b00000001) | (rows[i] >> 4);
cols[i] = (num & 0b00011110) >> 1;
num = num >> 6;
}
//S-Box를 3차원으로 만들고 이것도 for문으로 변경
res |= S8[rows[7]][cols[7]];
res |= (uint32_t)S7[rows[6]][cols[6]] << 4;
res |= (uint32_t)S6[rows[5]][cols[5]] << 8;
res |= (uint32_t)S5[rows[4]][cols[4]] << 12;
res |= (uint32_t)S4[rows[3]][cols[3]] << 16;
res |= (uint32_t)S3[rows[2]][cols[2]] << 20;
res |= (uint32_t)S2[rows[1]][cols[1]] << 24;
res |= (uint32_t)S1[rows[0]][cols[0]] << 28;
return res;
}
//
// Enc에서 input을 message_initial_permutation를 사용하여 테이블로 치환
uint64_t Initial_Permuter(uint64_t plain_text) {
uint64_t aftpt = 0;
for (int i = 0; i < 64; i++) {
aftpt <<= 1;
aftpt |= (plain_text >> (64 - message_initial_permutation[i])) & 0x0000000000000001;
}
return aftpt;
}
// Enc에서 16-round를 끝내고 최종 치환
uint64_t Inverse_Initial_Permuter(uint64_t cipher_text) {
uint64_t aftct = 0;
for (int i = 0; i < 64; i++) {
aftct |= ((cipher_text >> (64 - inverse_message_final_permutation[i])) & 0x01) << (63 - i);
}
return aftct;
}
// Enc 라운드내 함수의 치환함수
uint32_t Primitive(uint32_t num) {
uint32_t res = 0;
for (int i = 0; i < 32; i++) {
res = res | ((num >> (32 - straight_p_box[i])) & 0x01) << (31 - i);
}
return res;
}
void Enc(uint64_t* plain_text, uint64_t* cipher_text, uint64_t key) {
uint64_t tmp = 0x00;
uint64_t sub_key[16];
uint64_t output = 0;
uint32_t R_tmp = 0, swap_tmp = 0;
// key값을 가지고 subkey 생성
Key_Schedule(key, sub_key);
for (int i = 0; i < 16; i++) {
printf("subkey[%d] : %llx\n", i, sub_key[i]);
}
// plain_text를 Initial Permutation(message_initial_permutation을 테이블로 치환)
tmp = Initial_Permuter(*plain_text);
printf("Initial Permutation : %llx\n", tmp);
// 치환한 값을 32bit R, L로 나누기
uint32_t L = 0, R = 0;
// 치환한 값을 32bit R, L로 나누기
L = tmp >> 32;
R = tmp & 0x00000000FFFFFFFF;
printf("L : %x\n", L);
printf("R : %x\n", R);
//16라운드 반복
for (int i = 0; i < 16; i++) {
R_tmp = R;
/*** f() 시작 ***/
//32bit R을 48bit으로 확장
output = Expansion_Bit(R);
// 48bit로 확장된 R과 subkey[i]를 xor연산
output ^= sub_key[i];
// S-Box로 32bit으로 축소
R = S_Box(output);
// 단순 치환 P-Box
R = Primitive(R);
/**** f() 끝 ***/
// L과 xor연산
R ^= L;
// L, R swap
L = R_tmp;
}
// 마지막 16라운드에는 swap을 복원
swap_tmp = R;
R = L;
L = swap_tmp;
// R과 L을 합치고 최종 치환
tmp = ((uint64_t)L << 32) | (uint64_t)R;
*cipher_text = Inverse_Initial_Permuter(tmp);
}
void Dec(uint64_t* cipher_text, uint64_t* plain_text, uint64_t key) {
uint64_t tmp = 0x00;
uint64_t sub_key[16];
uint64_t output = 0;
uint32_t R_tmp = 0, swap_tmp = 0;
// key값을 가지고 subkey 생성
Key_Schedule(key, sub_key);
// plain_text를 Initial Permutation(message_initial_permutation을 테이블로 치환)
tmp = Initial_Permuter(*cipher_text);
// 치환한 값을 32bit R, L로 나누기
uint32_t L = 0, R = 0;
// 치환한 값을 32bit R, L로 나누기
L = tmp >> 32;
R = tmp & 0x00000000FFFFFFFF;
//16라운드 반복 (Enc와는 Reverse 라운드)
for (int i = 15; i >= 0; i--) {
R_tmp = R;
/*** f() 시작 ***/
//32bit R을 48bit으로 확장
output = Expansion_Bit(R);
// 48bit로 확장된 R과 subkey[i]를 xor연산
output ^= sub_key[i];
// S-Box로 32bit으로 축소
R = S_Box(output);
// 단순 치환 P-Box
R = Primitive(R);
/**** f() 끝 ***/
// L과 xor연산
R ^= L;
// L, R swap
L = R_tmp;
}
// 마지막 16라운드에는 swap을 복원
swap_tmp = R;
R = L;
L = swap_tmp;
// R과 L을 합치고 최종 치환
tmp = ((uint64_t)L << 32) | (uint64_t)R;
*plain_text = Inverse_Initial_Permuter(tmp);
}
int main()
{
// Key 생성
//uint64_t key = 0x02468ace13579bdf;
uint64_t key = Key_Generation();
// 평문
uint64_t plain_text = 0x0123456789abcdef;
// 암호문
uint64_t cipher_text = 0;
// 복호문
uint64_t decrypt_text = 0;
printf("Plain Text : %llx\n", plain_text);
printf("Key : %llx\n", key);
// 암호화
Enc(&plain_text, &cipher_text, key);
printf("Cipher Text : %llx\n", cipher_text);
//복호화
Dec(&cipher_text, &decrypt_text, key);
printf("Decrypt Text : %llx\n", decrypt_text);
}지금은 블록 암호화 개념을 이해하고 구현만하느라 코드에서 최적화 및 가독성이 좋지 않다.
이 코드는 그냥 재미삼아 보면 좋을것이다. 조금더 최적화를 진행해보고 다음은 LEA를 구현해볼 예정이다. 그후에는 KCMVP에 대해 서술해 보겠다.
The day⋯ is doomed⋯. Thanks to⋯ the Rowdyruff Boys⋯.