안녕하세요. 오늘은 블럭암호, 그중에서도 DES에 대해 공부해보겠습니다.
https://csrc.nist.gov/files/pubs/fips/46-3/final/docs/fips46-3.pdf
위의 페이퍼를 기반으로 작성했고, 이해하는데 도움이 되실거라 생각합니다!
DES 개요
Data Encryption Standard의 약어로 데이터 암호화 표준을 이야기 하는 블럭암호입니다.
1970년대에 개발한 암호로, 한 블럭 단위는 64비트로 지정되어 있습니다.
암호화 키는 64비트(56비트와 패리티비트 8비트)를 이용합니다.
현재는 DES 암호를 깨는 방법이 발견되어 DES를 보안 용도로 사용하기에는 취약하다고 평가받고 있습니다.
DES 원리
간단하게 말하자면 DES는 64비트의 평문 블럭을 입력받은 키 블럭(64비트)로 암호화한 후 64비트의 암호문 블럭을 생성합니다.
대략적인 순서는 다음과 같습니다
- 키스케쥴 : 최초의 64비트의 키블럭을 이리저리 만져서 Key1~Key16 총 16개의 서브키를 생성(각 키는 48비트)
- Intitial Permutation : 최초의 Input Block을 Permutation하고 왼쪽반, 오른쪽 반 두개로 쪼갭니다
- Round 진행 : 총 16라운드를 진행하면서 cipher를 진행합니다. 아까 키스케쥴에서 만든 서브키 16개를 각 라운드마다 하나씩 이용합니다.
- Final Permutation : 16라운드가 끝나면 아까 왼쪽반, 오른쪽 반 나눠졌던것을 합쳐서 최종 Output Block을 만듭니다.
이제 하나하나의 과정을 조금 더 자세히 설명해보겠습니다.
키스케쥴
이 과정은 나중에 기술하는 경우가 많은데 저는 초반에 키스케쥴을 했다고 생각하는게 DES를 좀 더 이해하기가 쉬웠습니다!
KEY(64비트)를 입력받고 Permuted Choice1 테이블(PC1)테이블을 거치면 패리티 비트가 제거되고 왼쪽 C0, 오른쪽 D0 각 28비트씩, 총 56비트가 남게 됩니다. 패리티 비트를 제거하고 필요한 부분만 섞어주는 과정이라고 보시면 되겠습니다!
위에는 Permuted Choice 1 에서 이용하는 테이블로 보시면 총 두 파트로 나눠져 있는게 보입니다. 윗부분은 C0(왼쪽) 생성에 이용되고, 아랫부분은 D0(오른쪽) 생성에 이용됩니다. 64비트 블럭을 Input으로 받으면 8, 16, 24 등 8단위 자리에 있는 비트들이 패리티 비트로 이용되는데요. 보시면 8 배수 단위가 없는 것을 볼 수있습니다.
이렇게 생성된 C0, D0을 각 라운드별로 제시하는 만큼 Left shift 연산을 해줍니다.
Iteration Number 1이 끝나면 C1,D1이 생성되고, 다시 다음 Iteration에 Left shift 연산을 하면 C2, D2가 생성되고..
총 C1~C16, D1~D16을 서브키 K1~K16 생성에 이용하게 됩니다
이제 Permuted Choice(이하 PC2) 테이블을 거치면 서브키가 생성됩니다.
왼쪽 오른쪽으로 나눠진 C,D를 합치고 해당 테이블을 거치면 48비트의 서브키가 생성됩니다.
이렇게 되면 키스케쥴이 끝나게 됩니다
암호화 과정
Input은 한블럭단위, 즉 64비트 입니다.
이 64비트 블럭은 최초로 Initial Permutation(이하 IP)테이블을 거칩니다.
IP 테이블은 64비트를 섞어주는 것이라고 보면 되겠습니다.
IP 테이블을 거치고 난 후 키스케쥴링에서 했던 것이랑 비슷하게 L, R로 각각 32비트씩 나눠지게 됩니다.
오른쪽 부분은 아까 만들었던 서브키와 함께 암호화 함수 F로 들어가게 됩니다.
그리고 해당 결과와 이전 라운드의 L을 XOR한 것이 Rn, Ln은 이전의 Rn-1이 내려오게 됩니다.
위의 표로 과정을 보시면 이해하기 쉽습니다.
이것또한 16라운드를 진행하면서 왼쪽 오른쪽 바뀌고 바뀌고 하는 과정이 진행됩니다.
F함수
암호화 과정에서 사용하는 F함수를 이해해보겠습니다.
F함수는 R과 서브키를 Input으로 받아 32비트를 출력하는 함수입니다.
과정은
- E테이블로 48비트 확장
- 서브키와 XOR 연산
- S-Box(S1~S8) 거치며 48->32비트로 만들기
- Permuation 하기
해당 과정에서 R은 Extenstion(이하 E)테이블을 거칩니다.
E 테이블을 보면 1이나 4 같이 중복되어서 사용되는 것들이 있는게 보입니다.
그래서 E테이블을 거치면 확장이 되게 되는 것이죠
48비트가 된 값과 원래 48비트였던 서브키를 XOR 합니다.
R을 48비트로 만들어야 했던 이유도 서브키와 XOR하기 위해서였다는 것을 알 수 있습니다.
다음으로는 output을 32비트로 만들어야 하니까 아까 늘려놨던 것을 다시 줄이는 과정입니다.
XOR 연산된 48비트의 값을 차례대로 6bit 씩 쪼갭니다.
앞에서부터 순서대로 S1~S8을 거치면 최종 값은 4비트가 나옵니다.
쪼갠 6비트가 100010이면
맨앞과 맨뒤 1,0은 행, 즉 10으로 2를 나타내고
가운데 4자리 0001은 열, 즉 1을 나타냅니다.
해당 방식을 표에 매칭시켜 주면됩니다.
표의 내용을 보면 15 이상되는 수가 없습니다.
이말은 각 숫자를 표현하는데 4비트만 있으면 된다는 소리입니다.
즉, 6*8=48비트 였던 것이 S1~S8을 거치면서 4*8=32비트가 되는 것입니다.
만들어진 32비트를 다시 P테이블을 통해 Permutation 하면 F함수가 끝나고 Output이 생성되게 됩니다.
이 과정 역시 순서를 섞어주는 작업이라고 생각해주시면 되겠습니다.!
Final Permutaion
암호화 과정의 마지막 단계입니다.
라운드가 다 끝나고 나면 최종적으로 R16, L16이 생성되게 됩니다.
(마지막 과정에서 주의할점은 이전에는 왼쪽 오른쪽이 계속 바뀌었는데 여기서는 바뀌지 않아요! 그림참고)
만들어진 R16, L16을 합치면 역시 64비트가 됩니다.
만들어진 64비트의 값을 최초로 썼던 IP 테이블의 인버스 테이블을 거치면 Ouput, 즉 Cipher Block이 생성되게 됩니다.
복호화 과정
암호화 과정을 이해했으면 복호화 과정은 매우 쉽습니다!
암호화 과정과 다를 바가 없거든요!
1. 기본적으로 복호화 과정은 암호화 과정과 동일한 알고리즘을 사용합니다
2. 암호화 과정에 서브키를 k1~k16 이 순서대로 이용했다면 복호화 과정에서는 키를 역순으로 입력받습니다.
3. 초기 전치 과정에서 IP 인버스 테이블을, 최종 전치 과정에서는 IP 테이블을 이용합니다
DES 분석
앞서 언급했듯 DES에는 취약점이 존재하기 때문에 보안을 이유로 단독 이용하는 것은 문제가 있습니다.
DES는 취약키가 4개 존재합니다.
| 0101 0101 0101 0101 | 0000000 0000000 |
| 1F1F 1F1F 0E0E 0E0E | 0000000 FFFFFFF |
| E0E0 E0E0 F1F1 F1F1 | FFFFFFF 0000000 |
| FEFE FEFE FEFE FEFE | FFFFFFF FFFFFFF |
키는 최초에 입력한 Key Block, 오른쪽은 패리티 비트를 제거한 이후의 키 입니다.
DES는 암호화시 XOR연산을 이용합니다.
이 XOR은 연산 특성상 2번 암호화하면 평문이 튀어나온다.
따라서 오른쪽에 있는 키를 사용하게 되면 매우 취약해진다는 단점이 있습니다.
이외에도 준취약키 12개 (Semi-Weak Key), 가능한 준취약키48개가 존재합니다. (아래는 예시)
| 01FE 01FE 01FE 01FE | FE01 FE01 FE01 FE01 |
| 1FE0 1FE0 0EF1 0EF1 | E01F E01F F10E F10E |
| 0EF0 0EF1 01F1 01F1 | E001 E001 F101 F101 |
| 1FFE 1FFE 0EFE 0EFE | FE1F FE1F FE0E FE0E |
| 011F 011F 010E 010E | 1F01 1F01 0E01 0E01 |
| E0FE E0FE F1FE F1FE | FEE0 FEE0 FEF1 FEF1 |
사용가능한 키 2^56 중에서 이 취약키들을 선택할 확률은 (4+12+48)/2^56 = 8.8*10^-16으로 낮은편이긴 하지만
한번 저 키들을 사용하게 되면 너무나도 취약해질 수 있습니다.
DES 공격법
- BruteForce : 답이 나올때까지 계속해서 대입하는 것으로, 일반적으로 취약점을 찾았다고 하면 Brute Force 방법보다 효율적인 방법을 찾았을 때를 말합니다.
- 보수 특성 (Complementation Property) : Key Complement
보수특성이 공부하면서도 정말 신기한 방법이라고 생각했습니다.
해당 방법은 키의 보수를 이용하는 것인데요
평문 P을 키 K로 암호화 했을 때 암호문 C가 나온다고 하면
평문 P의 보수 Comp(P)를 키의 보수 Comp(K)로 암호화 하면 암호문의 보수 comp(C)가 나온다는 것입니다.
공격중 하나의 키가 아니라는 것이 밝혀지면 자연스레 그 키의 보수도 이용할 수 없다는 소리가 됩니다.
따라서 사용 가능한 키의 갯수는 2^56에서 2^55로 절반이나 줄어들게 됩니다.
키가 짧기 때문에 공격에 취약해질 수 있다는 위험성이 발생하게 됩니다.
다중 DES
DES만 사용하기에는 보안의 위험이 있어서 사람들은 DES를 여러번 사용하는 다중 DES을 고려하게 됩니다.
다중 DES는 DES를 여러번 사용하여 56비트의 짧은 키 길이를 보완하는 것이 목적입니다.
2중 DES
56비트 키를 2개 쓰고 DES를 두번 이용하는 방식입니다.
2중 DES는 중간 일치 공격으로 깨는 것이 가능합니다.
Ek1(p)=m=Dk2(c)
즉, 처음 DES 블럭 Encryption 값과 두번째 DES 블럭 Decryption 값이 같음을 비교하면서 키를 찾아나가는 방식을 이용하는 것입니다.
3중 DES
2중 DES를의 취약점을 극복한 것입니다. 56비트 키를 2개 이용합니다.
3DES에서는 첫번째와 세번째 과정의 키가 같습니다. 즉 총 키 2개를 사용하는 것입니다.
과정을 늘리고 키를 2개, 총112비트를 사용하는 것만으로도 보안은 충분히 강력해지기 때문입니다.
만약, 더 강력한 암호가 필요하다고 하면 키를 세개 이용하는 것도 가능하다고 합니다.
암호화 시 : 처음 DES 블럭은 Encryption, 두번째 DES는 Decryption, 세번째 DES는 Encryption
복호화 시 : 처음 DES는 Decryption, 두번째 DES는 Encryption, 세번째 DES는 Decryption
암복호화를 반복하는 이유는 DES와의 호환성을 위해서 입니다.
해당 과정을 통해 2중 DES에서 문제가 되었던 중간 일치 공격에서 벗어날 수 있습니다.
참고
https://csrc.nist.gov/files/pubs/fips/46-3/final/docs/fips46-3.pdf
'보안이론' 카테고리의 다른 글
| [Cryptography] 블럭 암호 운영 모드 ECB, CBC, CFB, OFB, CTR (0) | 2025.02.14 |
|---|---|
| [Cryptography] 블럭암호 AES 원리, 안전성 (0) | 2025.02.14 |
| [Network] Packet Sniffing(스니핑), Spoofing(스푸핑)이란? (0) | 2025.02.12 |
| [Web Hacking] CrossSite Request Forgery(CSRF), 사이트간 요청 위조 (0) | 2025.02.11 |
| [Crypto Hacking] 해시함수와 Hash Collision Attack (0) | 2025.02.10 |