4.1. 블록암호
“블록암호”는 입력과 출력이 고정된 크기의 블록으로 정의되는 암호 시스템입니다.
블록암호는 1949년 샤논이 발표한 혼돈과 확산이론을 기반으로 설계 할 수 있다고 밝혀졌습니다.
“혼돈”(Confusion)이론은 암호문의 통계적 자료가 평문의 통계적 자료에 어떤 영향을 받는지
판단하기 어려운 정도를 계산하는 이론입니다.
직관적으로 평문에서 값이 하나 바뀌었을 때 암호문에 어떤 변화가 오는지
예측하기 어렵게 하기 위한 이론이라 볼 수 있습니다.
“확산”(Diffusion)이론은 평문이 암호문에 어떤 영향을 주는지 판단하기 어려운 정도를 계산하는 이론입니다.
직관적으로 평문의 각 요소들이 암호문을 생성할 때, 모든 암호문의 각 요소에 고르게 간섭하여 영향 여부를
예측하기 어렵게 하기 위한 이론이라 볼 수 있습니다.
블록암호의 한계점으로는 블록단위의 계산으로 이루어지기 떄문에 블록의 크기가 중요한 요소가 된다는 것과
오류가 날 경우 블록단위의 큰 “오류전파”가 생겨 구체적인 오류파악이나 수정등이 어려울 수 있습니다.
오늘날 가장 보편적인 블록암호로는
1). “페이스텔”(Feistel)구조로 알려진 DES, 다중 DES, SEED, LOKI, CAST등이 있습니다.
2). “SPN”구조로 잘 알려진 AES, SAFER, IDEA, SHARK, SHYPTON, Rijndeal 등이 있습니다.
4.2. DES
“DES”(Data Encryption Standard)는 대표적인 페이스텔방식의 블록암호로 처음 IBM사에서
“루시퍼”(Lucifer)암호 시스템을 수정, 보완하여 1976년 DES로 처음 공개되었습니다.
DES의 알고리즘이 “페이스텔”(Horst Feistel)에 의해 고안되었다 하여,
“페이스텔 네트워크” , “페이스텔 구조” , “페이스텔 암호”등으로 다양하게 표현됩니다.
페이스텔방식 암호들을 “라운드”(Round 또는 회전)를 자주 사용하여 암호화를 진행합니다.
DES는 16라운드를 진행하며, DES의 구조는 다음과 같습니다.
1). 64비트 기준 평문블록을 “초기치환”(Initial Permutation 또는 IP)을 진행합니다.
초기치환은 단순 치환암호방식으로 변환합니다.
2). 초기치환 된 암호를 좌측 절반과 우측 절반으로 나누어 각 \(L_0, R_0\)로 두고
라운드를 16번 진행하여 \(L_{16}\)과 \(R_{16}\)을 생성합니다.
임의의 한 라운드에서 \(L_i , R_i , K_{i+1}\) 를 가지고 \(L_{i+1} , R_{i+1}\) 을 만드는 과정은 다음과 같습니다.
\(L_{i+1} = R_i\) 이고, \(R_{i+1} = L_i ⊕ F( R_i , K_{i+1} )\) 입니다.
( \(K_i\) 는 “서브키”로 라운드 개수만큼, 즉, 16개 있지만 초기 \(K\)에서 생성되는 구조를 주로 응용해서 사용합니다. )
3). 좌측에 \(R_{16}\) 과 우측에 \(L_{16}\)을 두고 붙여서 “역치환”(\(IP^{-1}\))을 진행하여 암호화를 완료합니다.
이 때, 2)의 \(F( R, K )\)는 “라운드 함수”로 위의 \(F( R_i , K_{i+1} )\) 는 \(P( f( E( R_i ) , K_{i+1} ) )\) 를 나타냅니다.
\(P\)는 단순 치환함수이고, \(f\)는 \(S\)함수( \(S-box\) )이고, \(E\)는 확장 치환함수 입니다.
\(E\)는 출력 값을 확장하기 위해 일부 입력 값을 중복하여 값을 늘리면서
늘려진 값들에 의해 치환효과까지 가지는 함수입니다.
그렇다면, \(E( R_i )\)는 원래의 비트보다 늘어나게 되는데 사실, \(K_{i+1}\)도 늘어난 비트와 같은 크기입니다.
이 둘을 \(f\)가 받아 다시 원래의 비트 크기로 돌리는데,
예를 들어 64비트에서 \(R\)은 32비트이고
\(E\)는 확장치환에 의해 48비트로 ( 오른쪽 두개를 왼쪽에 다시 적는 것으로 ) 정의한다면,
\(K\)는 48비트가 됩니다. 또한 \(f\)는 48을 받아 32로 되돌리는 방식을 사용합니다.
\(f\)는 늘린 비트를 받아 비트의 약수 \(i\)개에 해당하는 \(S_i\)함수에 각 라인마다 입력하여
\(S_i\)가 입력크기보다 적은 출력크기의 값을 주면 \(f\)가 이들을 다시 합쳐주는 역할을 수행합니다.
예시 에서 \(f\)는 48 = 6 * 8 이므로 8개의 \(S\)함수를 가지고,
각 \(S\)함수는 4 * 1의 출력을 주어 \(f\)가 총 4 * 8의 결과를 받는 함수가 됩니다.
( 실제 64비트 DES의 \(S\)함수는 6비트 입력에 4비트 출력인데 \(6\)비트\(\{x_1, x_2, x_3, x_4, x_5, x_6\}\)에서
\([x_1 x_6]\) 행으로 나머지\([x_2 x_3 x_4 x_5]\)를 열로 \(S\)함수 표에 대입하여 4비트 값을 받아오는 방식을 사용합니다. )
추가로 서브키 \(K_i\) 생성은 초기 \(K\) 를 받았다고 할 때,
\(PC-1\) : ( 입력크기 ) -> ( 입력비트의 절반 ) , ( 입력비트의 절반 ) 과
\(PC-2\) : ( 입력크기 ) -> ( 동일한 입력크기 ) -> ( \(K_i\)의 크기는 \(R\)의 크기와 같아야 하므로 \(R\)의 크기 ) 와
\(LS_i\) : ( \(x_{i-1}\) ) -> ( \(x_i\) ) ( \(x_i\)는 특정 값, \(LS\)는 좌측 시프트 함수입니다. ) 가 정의될 때,
\(PC-2( LS_i( PC-1( K )\)의 좌측 출력 값 \() ,\) \(LS_i( PC-1( K )\)의 우측 출력 값 \() )\) 이 \(K_i\) 로 정의 됩니다.
4.3. DES 해독 및 응용
위의 내용으로 DES는 16라운드로 암호화를 진행하였지만,
16보다 더하거나 덜 하여도 암호화 과정 상에는 문제가 없습니다.
DES는 확산이론적으로 안전하다고 평가받고 또한, “쇄도효과”(Avalanche Effect)가 뛰어난 암호알고리즘 입니다.
쇄도효과는 입력 값인 평문과 결과 값인 암호문 간에 같은 위치의 두 값씩 서로 얼마나 바뀌었는지를 나타냅니다.
( DES\(_{64}\)에서 평균 32비트의 각 입 출력 값이 다르다고( 바뀐다고 ) 합니다. )
하지만, DES또한 전사공격에 취약하다고 알려져 보완된 알고리즘들이 많이 생겨났습니다.
그리고, DES설계상 “취약열쇠”(Weak Key)나 “준취약열쇠”(Semi-Weak Key)가 존재하여
이를 유념하고 사용해야 합니다.
대표적인 DES 해독 방법으로 차분공격이 있습니다. (차분공격은 1.3절에 정의 되어 있습니다.)
이 해독 방법의 특징은 16라운드 이하의 구조에서 의미가 있으며,
“입력차이블록”(Input XOR) 과 “출력차이블록”(Output XOR)을 찾고,
두 차이블록과 \(C\)와 \(S\)함수만으로 가능한 경우의 수 에서 해를 찾아내는 방식입니다.
“3중 DES”(Triple DES)는 DES의 보안을 강화하기 위해 DES알고리즘을 반복 사용하여 암호화하는 방식입니다.
이 때, 암호화를 세 번하는 것이 아닌,
1). \(K-1\)으로 암호화 -> \(K-2\)로 복호화 -> \(K-3\)로 암호화 ; 또는
2). \(K-1\)으로 복호화 -> \(K-2\)로 암호화 -> \(K-3\)로 복호화 ; 방식으로
섞어서 사용하여 해독의 난이도를 더 올렸고, ( 이 들을 “DES-EDE3″라고도 표현합니다. )
이 중 1)에서 \(K-1 = K-3\) 인 방식을 “DES-EDE2″로 표현하고 사용되기도 합니다.
위의 차분공격은 3-라운드 DES에서도 유사하게 사용할 수 있습니다.
다음은 DES 알고리즘의 규칙성에 대해 분석한 내용입니다.
먼저, 초기치환 IP의 분석내용은 다음과 같습니다.
64비트 입력 블록이 존재 할 때, 수정 치환 M-IP 는 같은 크기로 단순 치환을 적용하는 함수가 정의 될 때,
M-IP의 정의역 원소 \(m_i : i = (i_5 , i_4 , i_3 , i_2 , i_1 , i_0)\)( 6자리 이진 수 )와
치역원소 \(p_j : j = (j_5 , j_4 , j_3 , j_2 , j_1 , j_0)\)( 6자리 이진 수 )가 정의 될 때,
정의역원소 \(m_i\)에 대해 치역 \(p_j\) 는 \( j = ( j_5 , j_4 , j_3 , j_2 , j_1 , j_0 ) = ( \bar{i_0} , i_2 , i_1 , \bar{i_5} , \bar{i_4} , \bar{i_3} )\) 가 성립하고
즉, \(p_j = m_{ ( \bar{i_0} , i_2 , i_1 , \bar{i_5} , \bar{i_4} , \bar{i_3} ) }\) 가 됩니다.
(\(\bar{i}\) 는 \(i\)의 보수 입니다.)
다음으로 확장치환 E의 분석내용은 다음과 같습니다.
확장 치환 E는 32비트 입력블록을 48비트 출력블록으로 치환하는 함수입니다.
이때, 입력 블록 \(R = (r_0, r_1, \ldots, r_{31})\) 과 출력블록 \(E(R) = (x_0, x_1, \ldots, x_{48})\) 의 관계는 다음과 같습니다.
\(x_{6i+j} = r_{(4i+j-1)mod32} : ( i = 0, 1, \ldots , 7 ∧ j = 0, 1, \ldots , 5)\)다음으로 S-함수의 분석내용은 다음과 같습니다.
S-함수 \(f\)가 존재 할 때, \(f(E(R) ⊕ K)\) 출력사이즈를 줄여서 결과를 도출해냅니다.
\(f\)의 입력은 즉, \(E(R) ⊕ K\)는 대부분이 유추가 가능하지만, \(f\)함수의 S-box는 함수 값의 규칙이 무작위 적으로
결론으로 다음 세 가지를 도출 해낼 수 있습니다.
1). S-함수는 비선형 함수입니다.
2). 각 입력 비트는 최소 2개의 출력비트에 영향을 줍니다.
3). 출력비트의 0과 1의 비율은 입력비트가 정적일수록 균일해집니다.
국내 블록암호표준으로 사용되는 “SEED”암호는
한국정보보호진흥원(KISA)이 1998년에 처음 고안하여 당해 12월 발표된 암호입니다.
SEED암호는 DES가 64비트로 설계가 되어 전사공격에 있어 약한 단점을 128비트 구조로 설계하여
문제를 해결하려 했던 방식입니다. ( 즉, DES의 128비트 버전입니다. )
따라서, 페이스텔이고, \(L\)과 \(R\)이 64비트, \(K\)도 64비트입니다.
SEED의 한 라운드는 다음과 같습니다.
\(L_{n+1} = L_n = L_{n-1} ⊕ F( R_{n-1} )\) 이고, \(R_{n-1} = R_n\) , \(R_{n+1} = R_n ⊕ F( L_n )\) 입니다.
이 때, \(F\)는 회전열쇠 \(K_i\)를 사용한 \(S\)함수와 \(G\)함수의 합성함수입니다.
( \(G\)는 각 자리의 \(LS( X )\)한 값을 \(⊕\)곱 하는 함수입니다. )
그렇다면, 회전열쇠 K는 어떻게 구하는 것일까요?
SEED암호의 회전열쇠 생성 알고리즘은 다음의 순서를 따릅니다.
먼저, \(KC_i = int(\frac{\sqrt{5} – 1}{2} * 2^{32})\) , \(KC_i = KC_{i-1} << 1 : ( 1 ≤ i ≤ 16 )\)로 상수 값들을 정의합니다.
( \(n << k\)은 \(n\)을 \(k\)번 좌측 비트 시프트 연산 한 결과입니다. )
(시프트 연산의 경우 PL의 C/C++ 파트에 자세하게 설명되어 있습니다. )
1). 128비트의 열쇠를 32비트 단위로 \(( A, B, C, D )\)로 분할 합니다.
2). \(K_{(i,0)} = G( A + C – KC_{i-1})\) , \(K_{(i,1)} = G( B – D + KC_{i-1})\) 을 계산하여 \(i\)라운드 열쇠를 생성합니다.
3). 위 2)의 계산을 진행하면 \(( A, B, C, D )\)의 나열을
\(i\)가 홀수일 때는 \(( E, F, C, D ) : ( [A:B] >> 8 = [E:F] )\)로 바꾸고 2)를 진행했다가
\(i\)가 짝수일 때는 \(( A, B, E, F ) : ( [C:D] << 8 = [E:F] )\)로 바꾸어 진행합니다.
4). 위의 내용을 \(i = 16\)까지 진행하고 SEED암호에 사용합니다.
4.4. 블록암호 모드
평문의 길이가 블록암호의 블록크기보다 클 경우에는
블록암호를 어떻게 적용할지에 대해 상황에 따라 적절한, 효율적인 운영방식들을 사용할 것입니다.
해당 운영방식을 “블록암호 모드”라고 표현합니다. 다음은 5가지 블록암호 모드를 나열한 것입니다.
1). “ECB”(Electric CodeBook 또는 전자 부호책) 모드 :
ECB모드는 평문블록을 그대로 블록 크기대로 잘라서 각 블록을 그대로 암호문으로 치환한 것 입니다.
물론 구현 하기도 쉽고 연산함수를 사용하지 않고 테이블(코드북)만을 참고해서 일대일 대응시키면 되지만,
그만큼 취약한 방법이기도 합니다. (모든 블록이 각자 독립적으로 암호문이 되는 방법이기도 합니다.)
또한, 블록간의 간섭이 없는 특징 때문에, 해독이 아닌 변조에도 취약하여 인증기법을 추가로 사용해야 합니다.
2). “CBC”(Cipher Block Chaining 또는 암호 블록 연쇄)모드 :
CBC모드는 암호문블록을 체이닝하여 블록 간의 간섭이 생기도록 하는 방법입니다.
처음 평문을 암호화하는 작업에서 옆의 암호화된 블록과 \(⊕\) 연산 한 후 암호화를 진행하는 방식으로
암호문블록을 체이닝합니다. 이 때, 제일 처음의 평문은 \(⊕\) 연산 할 암호문블록이 없는 데,
“초기화 벡터”(Initialization Vector)를 대상으로 사용하여 \(⊕\) 연산을 시도합니다.
( 이 때, 초기화벡터는 서로 미리 약속이 되있어야 합니다. )
복호화는 역으로 암호문을 복호화하고 옆의 체이닝된 암호문블록과 \(⊕\) 연산하면 평문을 구할 수 있습니다.
만약 암호문이 도중에 어떤 한 블록이 변조된다면,
영향을 받는 블록은 직접적으로 변환되는 대상과 1차로 간접적으로 변환에 사용된 대상 두 개가
영향을 받아 변조지점을 특정 할 수 있게 됩니다.
3). “CFB”(Cipher FeedBack 또는 암호 피드백) 모드 :
CFB모드는 위의 두 모드와는 다르게 평문블록과 암호문블록을 \(⊕\) 연산한 것을 바로 암호문블록으로 사용합니다.
그리고 또 다른 부분은 옆의 암호문블록을 “사용할 때 암호화를 하여” 사용합니다.
즉, 옆의 암호문블록을 암호화하여 평문과 \(⊕\) 연산한 것이 암호문블록이 됩니다.
그래서 복호화는 암호화 과정과 완전히 같습니다.
해당 모드방식은 “재전송 공격”(Replay Attack)이 가능합니다.
평문과 암호문 간의 함수가 \(⊕\) 연산 하나이기에 재전송 공격을 시도한다면, ( 암호문을 갑자기 가로채고 변조한다면, )
바뀌는 지점의 공격자 암호문 및 평문은 에러가 나지만 바뀌고 난 뒤 공격자 암호문 및 평문은 정상 동작하게 되어
결과적으로 변조를 할 수 있게 됩니다.
4). “OFB”(Output FeedBack 또는 출력 피드백) 모드 :
OFB모드는 CFB와 마찬가지로 평문과 암호문간의 함수가 \(⊕\) 연산 하나인건 같으나, \(⊕\) 연산 대상이 조금 다릅니다.
기존의 \(⊕\) 연산 대상은 옆 암호문블록을 암호화해서 사용했지만,
OFB는 초기화벡터로부터 암호화를 연속하여 나온 결과들을 \(⊕\) 연산 대상으로 사용합니다.
즉, 암호문과 평문간에는 \(⊕\) 연산 하나 관계이고, \(⊕\) 연산 대상과는 독립인 관계가 됩니다.
이 모드 역시 복호화는 암호화 과정과 완전히 같습니다.
이 모드의 특징으로 \(⊕\) 연산대상과 블록이 독립이기에 기존의 순차적인 계산을 하지 않아도 되고
모든 대상들을 초기화벡터와 암호화 재귀방식으로 미리 다 구한 후
각 암호문을 병렬로 대입하여 처리 할 수 있습니다.
5). “CTR”(CounTeR 또는 카운터) 모드 :
CTR모드는 OFB와 마찬가지로 암호문과 평문간에는 \(⊕\) 연산 하나 관계이고, \(⊕\) 연산 대상과는 독립인 관계입니다.
하지만, \(⊕\) 연산 대상은 초기화벡터와 암호화 재귀방식이 아닌 비표 \(+\) 카운터로 된 CTR\( + i\)를
각 한 번 암호화하여 사용합니다.
비표는 임의의 문자열이고, 암호화 재귀방식의 횟수가 카운터의 \(+1\) 횟수가 되어 CTR + \(i\) ( \(i\)는 더한 횟수 )를 구성하고
암호화 한 것을 대상으로 사용합니다.
OFB와 유사하게 비표 \(+\) 카운터의 CTR\( + i\) 들을 각 암호화 하여 미리 구한 후
각 암호문을 병렬로 대입하여 처리할 수 있습니다