AES

준문서 : FIPS-197.

<Advanced Encryption Standard>를 줄인 말이다. 한국어로 번역하면 '고급 암호화 표준'이다. 대칭키를 쓰는 블럭 암호이다. 높은 안전성과 속도로 인해 인기를 얻어 전 세계적으로 랜섬웨어에많이 사용되고 있다.

현재 AES는 DES(데이터 암호화 표준)의 뒤를 이을 AES(고급 암호화 표준)라는 이름을 걸고 NIST가 주최한 공모전에서 채택된 Rijndael(레인달) 알고리즘을 가리킨다. 엄밀하게는 Rijndael 알고리즘의 여러 가능성 중, 암호화 블럭의 크기가 128비트이며 암호화 키의 길이가 128, 192, 256비트인 세 가지 종류가 AES 표준으로 지정되었다. 각각 AES-128, AES-192, AES-256으로 불린다.

AES이전 NIST는 1977년에 DES를 표준으로 지정하였고 DES는 오랫동안 암호화의 표준으로 잘 사용되었다. 그러나 1990년대에 기술의 발전으로 56비트 키를 쓰는 DES가 더 이상 안전하지 않게 되었고[1], DES를 3번 사용하는 3-DES와 같은 방법도 사용되기는 하였으나 여러 문제로 인해 새로운 암호화 표준을 지정할 필요가 있었다.

NIST는 1997년 1월에 AES라는 이름의 표준을 제정할 것을 발표하였고, 1997년 9월부터 암호화 알고리즘의 공모를 받기 시작했다. 조건은 128비트 블록 암호이며, 128, 192, 256비트 길이의 키를 지원할 것이었다. 총 15개의 후보 알고리즘은 1998년 8월 20일의 첫번째 AES 후보 학술대회(First Advanced Encryption Standard Candidate Conference)와 1999년 3월의 두번째 학회를 거치며 5개로 추려졌다. MARS, RC6, Rijndael, Serpent, Twofish 알고리즘이 살아남아 2000년 4월의 세번째 학회에서 다루어졌다. 결국 안전성, 유연성, 성능 등을 잘 만족하는 Rijndael 알고리즘이 최종적으로 채택되었고, NIST는 2001년 11월 26일에 Rijndael 알고리즘[2]을 FIPS 197, AES라는 이름으로 표준으로 발표하였다.

대칭형, 블럭 암호화 알고리즘이다. 대칭형 암호화 알고리즘 중 가장 유명하다.

암호화 키는 128, 192, 256의 세 가지 중 하나가 될 수 있으며, 각각 AES-128, AES-192, AES-256으로 불린다. 암호화 키의 길이에 따라 실행하는 라운드의 수가 다른데, 각각 10, 12, 14 라운드를 실행한다.

S-Box를 간단히 설명하자면 입력 데이터를 지정된 숫자로 바꿔서 암호를 깨기 어렵게 만드는 기법이다. AES는 이걸 창조롭게 재발명하여 암호화 속도를 높이고 싶으면 S-Box를 메모리에 박아놓고, 프로그램 메모리 양을 줄이려면 실행시 S-Box를 연산으로 구해내는 기법을 사용했다.

AES의 과정을 쉽게 설명하고 보여주는 동영상. 아래의 내용이 너무 복잡하다면 영상과 같이 보자.

Rijndael(레인달)이 AES로 채택되었으므로 아래는 Rjindael 알고리즘에 대한 설명이기도 하다.
아래 설명에서 블럭 크기인 128비트와, 키 길이인 128, 192, 256비트를 헷갈리지 않도록 주의하자.

Rijndael 알고리즘은 크게 보아 네 단계로 이루어진다.

위에서 언급한 것처럼 key schedule, 키 스케줄이라고도 부른다. 하나의 주 암호화 키로부터 많은 라운드 키들을 만들어 낸다. 주 키의 길이에 따라 총 라운드 수가 달라지므로, 만들어야 할 라운드 키의 갯수도 다르다. AES-128, 192, 256에 따라 각각 11개, 13개, 15개의 라운드 키를 만든다.

Rijndael 알고리즘은 라운드 키를 만들 때 32비트=4바이트=워드씩, 연속적으로 만든다. AES는 세 버전 모두 128비트의 블록 사이즈를 사용하므로, 하나의 라운드 키는 이 4바이트 워드를 네 개 뭉쳐서 만든다.[3] 그러므로 AES-128, 192, 256 버전은 각각 44, 52, 60개의 4바이트 워드를 만들어야 한다.

주 키의 길이를 32비트로 나눈 것을 N이라 하자. 즉 주 키가 N워드이다. 예를 들어 AES-192라면 N=6일 것이다. 그리고 필요한 총 4R개의 워드 중 i번째, W(i)를 생각하자.
그렇다면 가능성은 두 가지이다.

즉 첫 N개의 워드는 주 키를 순서대로 그대로 가져다 쓴다. 그 다음부터는 이전 워드에 RotWord, SubWord한 것, N칸 이전의 워드, Rcon(i/N) 3개를 XOR한 값으로 정해진다.
다만 N > 6, i % N = 4인 특수한 경우에는 위의 식과 약간 다른 W(i) = W(N-i) XOR SubWord(W(i-1))로 계산해야 한다. AES 표준에는 N이 6보다 큰 경우가 N=8인 AES-256 밖에 없다.

RotWord는 4바이트 워드를 바이트 단위로 한 칸 민(shift/rotate) 것이다. 즉 RotWord([89 ab cd ef]) = [ab cd ef 89]이다.
SubWord는 바이트 단위로 아래에 서술할 SubBytes를 실행하는 함수이다. 위의 예를 사용하면 SubWord([ab cd ef 89]) = [62 bd df a7]이 될 것이다.

키를 더더욱 알기 어렵게 하기 위해 섞어주는 상수이다. 이름은 round constant이지만, 이 라운드는 AES의 큰 흐름에서 말하는 라운드와 다르다! 그 라운드는 4개의 워드를 만들때마다(즉 128비트마다) 바뀌지만, 이 round constant는 N개의 워드를 만들때마다 다음 값으로 바뀐다. 즉 W(i)를 구할 때에는 rcon(i/N)을 쓴다. 역시 4바이트 워드이며 값은 다음과 같이 주어진다.

즉 아랫쪽 3바이트는 항상 0이며, 첫번째 바이트는 2배 하거나 2배 한 이후 0x11B와 XOR한 것이다. 계산해보면 첫번째 바이트는 0x01, 02, 04, 08, 10, 20, 40, 80, 1B, 36, ... 으로 주어진다.
Rcon은 N개의 워드를 만들때마다 바뀌므로, 필요한 라운드 키의 갯수와는 다르다. 필요한 워드 수가 각각 44, 52, 60인 AES-128, 192, 256은 각각 4, 6, 8로 나누어보면 10, 8, 7번째까지의 Rcon이 필요함을 알 수 있다. AES-128의 경우 44라운드가 필요한데 10개의 Rcon만 쓰이는 이유는 첫 N개의 워드는 주 키를 그대로 가져다 쓰기 때문이다.

SubBytes 단계에서는 128비트블럭 안의 16바이트를 바이트 단위로 쪼개, 각 바이트마다 다른 내용으로 치환한다. 이때 미리 주어진 Rijndael S-Box (Substitution Box)를 사용한다.

아래의 표가 S-Box이다.

맨 왼쪽 열이 높은 4비트, 맨 윗쪽 행이 낮은 4비트이다. 예를 들어, 0x4C는 40과 0C가 만나는 칸의 0x29가 된다.

Inverse SubBytes. SubBytes와 같지만 복호화를 할 때의 단계이다. 당연히 S-Box를 뒤집은 Inv S-Box를 쓴다.

SubBytes에서와 마찬가지로, 0x29를 복호화 하면 0x4C가 된다.

ShiftRows 단계에서는 128비트=16바이트 블럭을 4x4 바이트 행렬로 보고 각 행마다 왼쪽으로 민(shift/rotate)다. ShiftRows처럼 열을 서로 섞어주는 단계가 없다면 각각의 열이 서로 따로 따로 암호화되어, 4개의 블럭 암호화를 실행한 것과 마찬가지가 되어 좋지 않다.
16바이트를 행 우선으로 아래의 표처럼 배열한 다음, 두번째 줄은 왼쪽으로 한 칸, 세번째 줄은 두 칸, 네번째 줄은 세 칸 만큼 민다. 첫번째 줄은 변화가 없다.
즉 아래의 128비트 블럭은

SubBytes를 실행한 후에는 이렇게 된다.

AES의 경우는 128비트 블럭만을 사용하지만, 더 큰 블럭을 갖는 Rijndael 알고리즘에서는 열의 수가 달라지며 미는 바이트의 수도 달라진다.

Inverse Shift Rows. 역시 복호화 할 때 필요한 단계이다.
4x4 행렬을 만든 후 두 번째 줄은 왼쪽으로 3번, 세 번째 줄은 2번, 네 번째 줄은 1번 민다.

마찬가지로 4x4 행렬을 만든 뒤, 이번에는 열 단위에서 섞어주는 단계이다. 식은 보기 편하게 다음처럼 행렬로 주어진다.

a0 * [2 3 1 1] = r0
a1 * [1 2 3 1] = r1
a2 * [1 1 2 3] = r2
a3 * [3 1 1 2] = r3

여기서 r값들을 구하려면, 이런 식으로 해야한다.

r0 = (a0 * 2) + (a1 * 3) + (a2 * 1) + (a3 * 1).
r1 = (a0 * 1) + (a1 * 2) + (a2 * 3) + (a3 * 1).
r2 = (a0 * 1) + (a1 * 1) + (a2 * 2) + (a3 * 3).
r3 = (a0 * 3) + (a1 * 1) + (a2 * 1) + (a3 * 2).

다만 이때 덧셈은 평범한 덧셈이 아니며, XOR을 사용해야 한다. 마찬가지로 곱셈도 덧셈이 XOR인 것에 맞게 계산해 줄 필요가 있다. 만약 더하다가 OverFlow가 발생하면 0x1b와 XOR을 해 주면 된다

C언어로 표현하면 이렇게 된다.

typedef unsigned char byte;
void rijndael_mixcolumn (byte * data, size_t data_len) {
	if ((data_len % 4) != 0)
		return;

	for (size_t i = 0 ; i < data_len ; i += 4) {
		byte copy_arr [4], res [4];

		memcpy (copy_arr, data + i, 4);

		res [0] = (data [0 + i] << 1) ^ (0x1B & ((byte) ((signed char) data [0 + i] >> 7)));
		res [1] = (data [1 + i] << 1) ^ (0x1B & ((byte) ((signed char) data [1 + i] >> 7)));
		res [2] = (data [2 + i] << 1) ^ (0x1B & ((byte) ((signed char) data [2 + i] >> 7)));
		res [3] = (data [3 + i] << 1) ^ (0x1B & ((byte) ((signed char) data [3 + i] >> 7)));

		data [0 + i] = res [0] ^ copy_arr [3] ^ copy_arr [2] ^ res [1] ^ copy_arr [1];
		data [1 + i] = res [1] ^ copy_arr [0] ^ copy_arr [3] ^ res [2] ^ copy_arr [2];
		data [2 + i] = res [2] ^ copy_arr [1] ^ copy_arr [0] ^ res [3] ^ copy_arr [3];
		data [3 + i] = res [3] ^ copy_arr [2] ^ copy_arr [1] ^ res [0] ^ copy_arr [0];
	}
}

이 과정을 미리 계산해서 Table-lookup에 저장해 놓고 계산하는 방법도 있으며, 모든 AES 최적화에는 이러한 Table-lookup방식을 적용한다.[4]

마지막 라운드에서는 MixColumns가 없다는 걸 잊지 말자.

Inverse Mix Columns. 역시 복호화 할때 사용한다.

a0 * [14 11 13 9] = r0
a1 * [9 14 11 13] = r1
a2 * [13 9 14 11] = r2
a3 * [11 13 9 14] = r3

드디어 KeyExpansion 단계에서 만든 라운드 키를 쓸 때가 되었다.
128비트 블럭에 128비트 라운드 키(네 워드를 이어붙여 만든)를 XOR한다.
XOR의 특성 때문에, AddRoundKey 단계는 복호화하는 데 굳이 별도의 역 공식이 필요하지 않고, 같은 라운드 키로 XOR을 한 번 더 하기만 하면 복호화가 된다.

AddRoundKey는 0라운드, 1~(9,11,13), (10,12,14) 라운드에서 실행하므로, 위에서 언급했듯 총 (11, 13, 15)개의 라운드 키가 필요하다.

BASE64는 바이트 열을 인코딩하는 방식의 하나일 뿐이므로 본래 AES 암호화 알고리즘과는 관련이 없다. 그러나 AES 암호화의 결과는 NULL 바이트를 포함하는 이진 데이터이기 때문에, C를 비롯한 여러 언어에서는 암호화의 결과에 BASE64 인코딩을 해서 나온 문자열을 다루는 것이 더 편할 수 있다.

AES가 블럭 암호화 알고리즘인 만큼 다른 모든 블럭 암호화 알고리즘처럼 패딩(padding)하여 블럭의 빈 자리를 채울 필요가 있다. 일반적으로 PKCS#5와 PKCS#7에 정의된 패딩 알고리즘이 널리 사용된다.
PKCS#7 패딩 알고리즘은 블럭의 크기가 k바이트(k는 1~255)일 때 패딩하고자 하는 데이터의 바이트 단위 길이가 k의 배수가 되는데 필요한 나머지 바이트 개수를 n이라 하면 n이라는 값을 n개 덧붙인다. 단, 바이트 단위 길이가 딱 k의 배수이더라도 k라는 값을 k개 덧붙인다.[5]

코드로 표현하자면 다음과 같다.

const k = /* 1 ~ 255 */; // blockSize
const n = k - baseDataLen % k; // padSize == padValue

예를 들어 원문이 아래와 같고, 블럭의 크기가 128비트(16바이트)라 하면,

총 27바이트이므로 16의 배수인 32바이트가 되려면 5바이트가 부족하다.

따라서 바이트 0x05를 5개만큼 뒤에 덧붙여서 아래와 같이 두 블럭을 만든다.

PKCS#5 패딩은 PKCS#7 패딩과 구현 방식이 같지만 블럭의 크기가 8바이트로 고정된 것이다. AES는 128비트(16바이트) 블럭 알고리즘이기 때문에 사실 PKCS#5 패딩을 쓸 일이 없다. 그러나 PKCS#7 패딩과 구현 방식이 같아 보통 같은 구현을 돌려쓰는데다, Java에서 'AES/CBC/PKCS5Padding' 표기법만 허용하고 'AES/CBC/PKCS7Padding' 표기법은 지원하지 않다보니 오히려 AES에 PKCS#5 패딩을 쓰는 것이 맞는 줄 아는 경우가 많다.

미국 정부가 채택하여 기밀문서를 암호화를 했다. 즉, 정부가 믿을 정도라는 것이다. 일단 아직은 AES가 최강의 암호화 알고리즘이고, 키없이 해독하는 것이 거의 불가능하다고 믿어지고 있다. 심지어 다른 최신 cipher와 마찬가지로, known-plaintext 해킹기술로도 해독이 불가능하다고 한다.

소수를 사용한 암호화, ECDLP(Elliptic Curve Discrete Logarithm Problem)의 특성을 이용한 공개키 암호화 방식 등이 양자컴퓨터에 취약할 가능성을 보이지만, SPN(Substitution Permutation Network)을 기반으로 하는 AES의 특성상 상대적으로 양자컴퓨터에 안전하다.

컴퓨팅 기술의 급속한 발전에 따라 현재 권장되는 암호화 수준은 192비트 이상이며 대다수의 금융기관이나 웹사이트들은 256비트 이상의 암호화 체계로 전환했다.

자바 API에 java.security 패키지와, javax.crypto 패키지를 사용하여 AES 암호화를 사용할 수 있다 뭐, 자바는 API자체 크기가 크고 아름다우니. [6]. 여기를 참고하면 된다.

C/C++는 기본 라이브러리에 없다.[7]. 서드 파티 소프트웨어나, 다른 API는 구글에 검색만 해도 다 나오니 필요하면 검색해 보자.

PHP 언어도 지원한다. 자바와 마찬가지로 여기를 참고하면 된다.

C#은 지원한다. System.Security.Cryptography 네임스페이스와 System.Security.Cryptography.Aes 클래스를 사용하면 된다. 설명은 이곳을 참고하면 된다.

Python은 외부 라이브러리를 통해 지원한다. Crypto 모듈에서 지원한다. 이 곳을 참고하자. 약간 개량된 형태의 pycryptodome 모듈 또한 지원한다.

Go 언어는 지원한다. "crypto/aes" 패키지를 이용하면 된다.

Node.js에서는 crypto 모듈을 지원한다. crypto.createCipher 함수를 사용한다.

Assembly 언어의 경우 x86에서는 AES-NI라는, AES 암호화 복호화 연산을 하드웨어 가속할 수 있는 확장 명령어셋을 지원한다. 인텔의 경우 웨스트미어에서 처음 지원했으나 서버용 Xeon과 Core i5 이상에 한정되었으며, 하스웰부터는 Core i3 이상, 스카이레이크부터는 모든 프로세서에서 지원한다. AMD의 경우 불도저 이후의 모든 프로세서에서 지원한다.

또한 x86 기반의 프로세서를 사용하는 환경에서 암호화 기능이 탑재된 소프트웨어를 사용중일 경우 대부분의 경우 AES-NI 인스트럭션을 사용해서 AES를 처리한다.
예를 들어 OpenSSL의 경우 x86 대상인 경우 AES-NI를 사용하여 AES를 처리한다.

Rijndael 알고리즘의 이름은 알고리즘을 만든 두 벨기에 암호학자 빈센트 레이먼(Vincent Rijmen)과 조앤 대먼(Joan Daemen)의 이름에서 따온 것이다.
AES에 대해 설명해주는 만화. 물론 영어다.