2022. 8. 3. 14:31ㆍ22-여름방학/암호학
블록 암호
AES
1. 들어가며
-AES(Advanced Encryption Standard)
- 연산 능령의 향상으로 DES가 더 이상 안전하지 않게 되자, 2001년에 새롭게 표준으로 선정된 블록 암호 알고리즘이다.
- 전세계에서 암호 알고리즘을 공모받고, 전문가들의 심사를 거쳐 그 중에서 가장 뛰어난 알고리즘을 선정했다.
- 당시 공모에 제안된 21개의 암호 알고리즘들 중, 보안성, 효율성, 하드웨어 이식의 적합성, 유연성 등을 고려하여 심사한 결과, Vincent Rijmen, Joan Daemen이 제안한 Rijndael 구조가 채택되었다.
- AES는 이러한 세계적인 논의를 거쳐 결정된 표준이었으므로, 미국 정보당국이 백도어를 설치했을 것이란 의심을 피해갈 수 있었다.
- 표준으로 선정된 이후부터 지금까지, AES에는 기밀성을 위협하는 치명적인 취약점이 발견되지 않았다.
- CPU 제조사들이 AES 연산을 위한 명령어를 따로 정의해 주어서 암호화, 복호화의 성능도 뛰어나다. 이런 이유로 현대에는 대칭키 암호 알고리즘을 사용할 때, 일반적으로 AES가 사용된다.
-> AES의 설계 원리를 이해하려면 갈루아 필드(Galois Field)를 비롯하여 체(Field)와 군(Group)에 대한 이해가 필요하다.
2. AES
1. SPN(Substitution Permutation Network)
- AES는 SPN이라는 암호 구조를 사용한다.
- SPN은 곱 암호의 일종으로, S-Box를 사용하는 치환(Substitution)과 P-Box를 사용하는 순열(Permutation)을 여러 라운드에 걸쳐 반복한다.
- 라운드마다 입력 전체에 라운드 함수를 적용한다.
- 같은 수의 라운드를 사용할 때 SPN이 페이스텔 구조에 비해 두 배의 암호학적 안전성을 갖는다.
2. AES 구조
- AES는 라운드마다 128비트 크기의 블록을 암호화하는 블록 암호이다.
- 키의 길이는 128, 192, 256비트 중 하나를 선택할 수 있고, 라운드 수는 키의 길이에 따라 10, 12, 14로 결정된다.
- 키의 길이가 128비트이면 AES-128, 192비트이면 AES-192, 256비트이면 AES-256이라고 부른다.
- AES는 암호화를 할 때, 가장 먼저 각 블록을 4행 4열의 상태 배열(State)로 재구성한다.
- State의 각 칸에는 8비트(1바이트)가 저장된다.
- 재구성된 입력에 대해 AddRoundKey 함수를 적용하고, 마지막 라운드 전까지 매 라운드마다 SubBytes, ShiftRows, MixColumns, AddRoundKey 함수를 반복하여 적용한다. 마지막 라운드에서는 MixColumns를 제외한 나머지 함수들만 적용한다.
- AES의 라운드 함수들은 역함수가 존재하기 때문에, 역함수를 이용하여 AES 복호화가 이루어진다.
3. AES 라운드 함수
-SubBytes
- SubBytes는 State의 각 바이트를 S-Box를 참조하여 치환하는 함수이다.
- 바이트의 상위 4비트가 행을, 하위 4비트가 열을 결정한다.
-ShiftRows
- ShiftRows는 State의 각 행을 구성하는 바이트들을 쉬프트하는 함수이다.
- 4가지 함수 중에서 유일하게 순열의 역할을 수행한다.
-MixColumns
- 열 단위로 치환을 수행하는 함수이다.
- 이 치환은 갈루아 필드 내에서의 행렬 연산으로 구해진다.
-AddRoundKey
- 키 생성 함수(Key Schedule)로 생성된 라운드 키의 state를 각 바이트별로 XOR한다.
- 복호화할 때는 XOR의 성질을 이용하여 동일한 키를 state에 XOR한다.
4. Key Schedule(키 생성 함수)
키 생성 함수는 입력된 키로부터 각 라운드에 쓰일 라운드 키를 생성한다.
첫번째 AddRoundKey에서는 입력된 키를 그대로 사용하기 때문에 W(0), W(1), W(2), W(3)은 입력된 키의 각 열들과 같다. W(i)>=4는 W(i-1)에 RotWord, SubWord, Rcon을 적용하고 이를 W(i-4)와 XOR하여 생성한다.
-RotWord
- 열을 위로 한 번 회전시킨다.
-SubWord
- SubBytes에서 사용한 것과 동일한 S-Box를 사용하여 각 바이트를 치환한다.
-Rcon
- R=[~,~,~...]인 R에 대해, W(i)의 최상위 바이트를 R[(i/4)-1]과 XOR한다.
3. 마치며
AES의 구조와 전 과정을 살펴보았다.
알고리즘을 통째로 암기하기보다는 구조와 특징을 이해하는 게 더 좋다.
-퀴즈
Q1. (1)
Q2. (2)
DES
1. 들어가며
-DES(Data Encryption Standard)
- DES는 미국의 국가 안보국(NSA)에서 IBM의 루시퍼 알고리즘을 개량하여 만든 대칭키 암호이다.
- DES는 루시퍼에서 128비트 키를 사용했던 것과 달리 키 길이를 56비트로 줄였고, 내부에서 사용하는 알고리즘도 일부 변경하였다.
- 미국 국립표준기술연구소(NIST)는 DES를 1976년부터 2002년까지 표준 블록 암호로 인정했다.
- 현대에는 DES에 대한 공격 기법이 많이 연구되어 DES를 더이상 블록 암호의 표준으로 사용하지 않는다.
- 8바이트(64비트)를 한 블록으로 하는 블록 암호이며, 전체 구조는 아래의 그림과 같이 초기 순열(Initial Permutation, IP), 최종 순열(Final Permutation, FP), 페이스텔(Feistel) 구조의 16 라운드, 그리고 각 라운드에 사용되는 48비트의 키를 생성하는 키 생성 함수(Key Generation)로 구성되어 있다.
2. DES의 원리
1. 순열과 치환, 그리고 곱 암호
- DES는 혼돈 성질을 만족하기 위해 치환(Substitution)을, 확산 성질을 만족하기 위해 순열(Permutation)을 사용한다.
- 치환과 순열을 여러 번 교차해서 반복 적용하면 혼돈과 확산의 성질을 모두 만족하게 된다.
- 이런 특성을 이용하여 치환이나 순열 같은 단순한 연산들로 한 라운드를 구성하고, 각 라운드를 여러 번 반복하여 암호학적 안전성을 확보하는 암호를 곱 암호(Product Cipher)라고 한다.
-> DES는 여러 라운드에 걸쳐 치환과 순열을 반복하는 곱 암호의 일종이다.
2. 페이스텔 구조
DES에서 라운드 함수를 적용하는 전체 과정은 페이스텔(Feistel) 구조를 이루고 있다.
-페이스텔 구조를 따르는 DES
- 입력으로 들어온 블록을 동일한 길이의 왼쪽 블록 L과 오른쪽 블록 R으로 나눈다.
- 각 라운드마다 오른쪽 블록은 다음 라운드의 왼쪽 블록으로 입력된다.
- 왼쪽 블록은 오른쪽 블록에 라운드 함수 F를 적용한 결과와 xor되어 다음 라운드의 오른쪽 블록으로 입력된다.
↓
-페이스텔 암호의 특징
- 페이스텔 구조를 사용하면 F가 복호화 과정에서 ⊕로 상쇄되므로 역함수가 존재하지 않아도 된다.
- 암호화와 복호화의 구조가 동일하므로, 암호화에 사용한 라운드 키를 역순으로 입력하면 복호화가 이뤄진다.
- 오른쪽 블록은 다음 라운드의 왼쪽 블록으로 어떠한 처리도 없이 입력된다.
- 비페이스텔 암호와 같은 안전성을 갖기 위해 두 배 정도 라운드를 사용해야 한다.
3. DES의 과정
1. Step1 & Step3. 초기 순열과 최종 순열
- DES는 시작할 때 초기 순열(Initial Permutation, IP)을, 마지막에는 최종 순열(Final Permutation, FP)을 수행한다.
- 정해진 테이블을 이용하여 64비트 입력을 비트 단위로 전치한다.
- 테이블의 n번째 값이 m일 때, 출력의 n번째 비트는 입력의 m번째 비트가 된다.
- 초기 순열과 최종 순열은 각각 초기 순열 테이블(Initial Permutation Table, IPT)과 최종 순열 테이블(Final Permutation Table,FPT)을 이용한다.
- 초기 순열과 최종 순열은 서로 역관계에 있다.
- 임의의 64비트 데이터에 초기 순열을 적용하고, 최종 순열을 적용하면 입력 값이 그대로 출력된다.
2. Step2. 라운드 함수
- 라운드 함수 F에는 오른쪽 블록만 입력되므로, 입력의 길이는 32비트이다.
- 라운드 함수는 확장 순열(Expansion P-Box), 라운드 키 결합(XOR), 치환 테이블(S-Box) 그리고 고정 순열(Straight P-Box)로 이루어져 있다.
3. Step2.1. 확장 순열과 라운드 키 결합
-확장 순열
- 확장 순열(Expansion P-Box)은 입력을 비트 단위로 전치하는 동시에, 전체 길이를 48비트로 확장한다.
- 이 과정에서 32비트의 입력값을 4비트씩 8개의 부분으로 나누고, 테이블을 참조하여 각각을 6비트로 확장한다.
- 이 과정은 테이블만 다를 뿐, 초기 순열, 최종 순열과 같은 방식으로 이루어진다.
-라운드 키 결합
- 라운드 키 결합은 확장 순열로 나온 출력을 라운드 키K와 xor 하는 것이다.
4. Step2.2. S-Box와 고정 순열
-S-Box
- S-Box(Substitution-Box)는 라운드 키 결합에서 출력된 48비트 결과 값을 32비트로 축소한다.
- 4개의 행과 16개의 열로 이루어진 표를 사용하는데, 표의 각 값은 4비트로 표현되는 수이다.
-고정 순열
- S-Box로 길이를 축소하고 나면, 고정 순열(Straight P-Box)로 다시 비트 단위 전치가 이뤄진다.
5. 키 생성 함수(Key Scheduling)
-키 생성 함수
- 키 생성 함수는 64비트의 입력을 받아 각 라운드에 필요한 48비트 라운드 키를 생성하는 함수이다.
- 이 함수는 패리티 비트 제거(Parity Bit Drop), 쉬프트(Shift), 압축 순열(Compression P-Box)로 구성되어 있다.
-패리티 비트 제거(Parity Bit Drop)
- 패리티 비트 제거는 입력에서 패리티 비트를 제거하고, 남은 56비트에 순열을 적용하는 과정이다.
- DES의 비밀키에서 각 바이트의 가장 오른쪽 비트는 자신이 속한 바이트의 나머지 7비트에 대한 홀수 패리티 비트(Odd Parity Bit)이다.
- 홀수 패리티 비트란 한 바이트를 이진수로 표현했을 때, 1의 개수가 홀수가 되도록 덧붙인 비트를 말한다.
- 패리티 비트는 통신 중에 비트 반전이 일어나지 않았음을 보증하는 역할을 한다. 홀수 패리티 비트를 사용하여 통신할 때, 수신한 바이트 중 1의 갯수가 짝수인 바이트가 있다면 그 바이트에서 임의의 비트에 반전이 일어났음을 수신자가 알 수 있다.
- 이를 확인한 수신자는 손상되지 않은 데이터를 얻기 위해 재전송을 요구할 수 있다.
-쉬프트(Shift)
- 입력을 왼쪽 28비트와 오른쪽 28비트로 나누어 각각을 1비트나 2비트만큼 왼쪽으로 순환 쉬프트(Cyclic Shift)하는 과정이다.
- 1,2,9,16 라운드에서는 1비트만틈, 나머지 라운드에서는 2비트만큼 쉬프트한다.
-압축 순열(Compression P-Box)
- 압축 순열은 56비트의 입력을 48비트 길이로 압축하는 과정이다.
- 수행 방법은 위에서 설명한 순열들과 같다.
4. DES의 응용
1. 다중 DES
- 다중 DES는 서로 다른 키를 사용하는 DES모듈을 여러 개 이어붙여서 DES의 약점을 보완한 암호 시스템이다.
- DES들 두 겹으로 사용하는 이중 DES(2-DES)는 112비트의 키를, 삼중 DES(3-DES)는 168비트의 키를 사용한다.
- 이중 DES나 삼중 DES는 늘어난 키 길이 만큼 단일 DES보다 안전할 것 같지만, 중간 일치 공격으로 인해 안전성을 획기적으로 높이지는 못한다.
- 이중 DES는 단일 DES와 비슷한 안전성을 갖고 있으며, 삼중 DES는 키 길이를 2배로 늘리는 효과밖에 얻지 못한다.
2. 중간 일치 공격
중간 일치 공격은 어떤 평문 p와 p를 암호화한 암호문 c를 알 수 있을 때 수행할 수 있는 공격이다.
5. 마치며
-퀴즈
Q1. 16
Q2. 56
Q3. X
운영모드
1. 들어가며
일반적으로 사용되는 평문의 길이는 AES나 DES와 같은 블록 암호가 한 번에 처리할 수 있는 블록의 길이들을 넘는 경우가 대부분이다.
운영 모드(Mode of Operation)는 블록 암호로 이러한 다양한 크기의 데이터를 처리할 수 있도록 고안된 블록 암호의 사용 방법이다.
운영 모드에는 여러 종류가 있으며, 블록 암호를 사용하는 서비스는 각각의 장단점을 고려하여 운영 모드를 선택한다.
-> 평문을 블록 단위로 만드는 데 사용하는 패딩(Padding)과 블록 암호의 대표적인 운영모드인 ECB, CBC, CTR에 대해 알아보자
2. 패딩
1. 비트 패딩
- 패딩
- 블록 암호는 블록 단위로 암호화를 하므로 입력의 길이가 정확하게 블록 크기의 배수가 되어야 하지만, 일반적으로 평문의 크기는 블록 크기의 배수가 되지 않는다.
- 이런 문제를 해결하기 위해 평문에 데이터를 붙여서 평문의 크기가 블록 크기의 배수가 되도록 만드는 과정을 패딩(padding)이라고 한다.
- 그러나, 패딩된 암호문을 복호화할 때는 복호화된 평문에서 패딩을 제거해야 원래의 평문을 얻을 수 있다. 따라서 패딩된 암호문의 수신자는 어떤 패딩이 적용됐는지 알아야 암호문을 제대로 복호화할 수 있다.
- 패딩 기법에는 비트 패딩(Bit Padding), 바이트 패딩(Byte Padding), PKCS#7 패딩이 있다.
-비트 패딩
- 비트 패딩(Bit Padding)은 마지막 블록에서 평문이 채우지 못하는 비트 중 최상위 비트를 1로 설정하고, 나머지는 모두 0으로 채우는 패딩 기법이다.
- 수신자는 평문의 마지막 비트부터 처음으로 값이 1인 비트가 나올 때까지를 패딩으로 인식할 수 있고, 이를 제거하여 평문을 복구할 수 있다.
- 그런데 이 방법은 평문의 크기가 정확히 블록 크기의 배수일 때, 수신자가 메세지의 일부를 패딩으로 오인하게 되는 문제가 있다. 이를 막기 위해 비트 패딩을 적용할 때는 평문의 크기가 블록 크기의 배수이면, 패딩으로 한 블록을 추가한다.
-바이트 패딩: ANSI X.923+
- 바이트 패딩은 바이트 단위로 패딩을 수행하는 패딩 기법이다.
- 바이트 패딩 중 ASNI X.923은 마지막 블록의 남는 바이트를 임의의 값(일반적으로 0)으로 채우고, 마지막 바이트에 패딩의 길이를 기록하는 기법이다.
- ANSI X.923은 비트 패딩과 마찬가지로 평문의 크기가 블록 크기의 배수일 때, 수신자가 평문을 패딩으로 오인할 수 있다. 따라서 평문의 크기가 블록 크기의 배수일 때는 마지막에 한 블록을 패딩으로 추가한다.
-바이트 패딩: PKCS#7
- PKCS는 공개키 암호의 표준 문서로서, 그중 7번째 문서인 PKCS#7은 AES와 같은 블록 암호의 패딩 기법을 제시한다.
- PKCS#7에 소개된 패딩 기법은 추가할 패딩의 바이트 크기로 마지막 블록을 채우는 패딩 기법이다.
3. 운영모드
1. ECB 모드
- ECB 모드
- ECB 모드는 가장 간단한 운영모드로, 블록들은 모두 같은 키로 암호화된다.
- ECB 모드에서는 각 블록이 독립적으로 암호화되므로 여러 블록을 병렬적으로 암호화할 수 있다는 장점이 있다.
- 그러나 ECB는 다른 운영모드에 비해 암호학적 안전성이 부족하다는 단점이 있다.
- ECB 모드의 취약점
- ECB 모드를 사용하면, 같은 블록은 같은 암호문으로 암호화된다.
- 이 특징을 이용하면 공격자는 암호문에서 평문의 정보를 습득하거나, 리플레이 공격(replay attack)을 수행하는 것이 가능해진다.
-약한 혼돈 성질
이미지 한 픽셀을 한 블록으로 하여 ECB 암호화하면 같은 픽셀들은 모두 같은 픽셀로 암호화되므로, 원본 이미지의 패턴이 암호화된 이미지에도 그대로 나타난다. 이는 암호문으로부터 평문의 정보를 유추하기 어려워야 한다는 혼돈 성질이 약함을 의미한다.
2. 재전송 공격
어떤 데이터를 재전송하여 시스템이 의도치 않은 행동을 하게 하는 것을 재전송 공격이라도 한다.
3. CBC 모드
- 어떤 블록을 암호화하기 전에, 이 블록을 직전 블록의 암호문과 XOR한다.
- CBC 모드는 한 블록을 암호화할 때 직전 블록의 암호화 결과를 사용하므로 여러 블록을 병렬적으로 암호화할 수 없다.
- 그러나 복호화의 경우, 모든 암호문 블록을 알고 있으므로 병렬적으로 처리할 수 있다.
- CBC 모드는 재전송 공격에 강인하며, 높은 혼돈성을 가지고 있어서 블록 암호의 운영 모드로 널리 사용되고 있다.
4. CBC Bit-Flipping Attack
공격자가 초기 벡터를 원하는 값으로 조작하여 복호화된 평문의 첫 번째 블록을 조작하는 공격을 CBC Bit-Flipping Attack이라고 한다.
5. CRT 모드
- CRT 모드는 블록 암호에 nonce와 평문 블록의 인덱스를 결합한 값을 입력한다.
- 암호문은 블록 암호의 출력과 평문 블록을 XOR하여 생성한다.
- CRT 모드는 블록을 순서대로 암복호화하지 않아도 되므로 병렬로 암복호화할 수 있으며, 구현이 간단하다.
3. 마치며
-퀴즈
Q1. X
Q2. X
Q3. O
Q4. X