Chap 4. 대칭 키 알고리즘 CS&AI Labs 7월 20일 신승목

Presentation on theme: "Chap 4. 대칭 키 알고리즘 CS&AI Labs 7월 20일 신승목"— Presentation transcript:

1 Chap 4. 대칭 키 알고리즘 CS&AI Labs 7월 20일 신승목
앞에서 발표했던 DES 알고리즘에 이어서 3-DES와 기타 대칭 키 알고리즘에 대해서 발표하겠습니다.

2 Contents 3-DES 개발 배경 및 구조 다양한 대칭 키 블록 암호기 대칭 키 스트림 암호기의 구조와 특징
차례는 다음과 같습니다. 먼저 3-DES가 개발되게 된 배경, 그리고 간략한 구조에 대해서 설명하고 3-DES이후에 나온 대칭 키 알고리즘에 대해서 소개를 하겠습니다.

3 4.1 3중 DES DES의 brute-force 공격에 대한 잠재적인 취약성 => 대안책 필요
Blowfish RC5 AES 기존의 소프트웨어와 장비에 암호화 강화 DES + 다중키 => 다중 암호화 => Triple DES 흔히 Triple DES라고 불리는 이 알고리즘이 나오게 된 배경은 기존의 DES 알고리즘이 전사적 공격에 대한 잠재적인 취약성을 드러냈기 때문입니다. 컴퓨터의 발전이 아직 더뎠던 19세기 중 후반에 DES 알고리즘을 모든 키 대입에 의해 공격하는 데에는 앞에서 보셨듯이, 대략 오래 걸립니다.. 수치적으로 봐도.. 한번의 암호화가 1마이크로 세컨에 이루어진다고 치면, 56비트 키로 암호화된 암호문을 해독하는데는, 1142년이 걸립니다. 그러나 요즘 컴퓨터 성능이 좀 좋아져서 1마이크로 세컨에 백만번의 암, 복호화가 가능하다고 하면 10시간 정도만 투자하면 56비트 키로 암호화된 중요 정보들을 해독가능합니다. 그래서, DES를 보완하고자 개발된 것이, Triple DES입니다. 그 외에도 Blowfish, RC5, AES등 많은 알고리즘이 개발되었습니다.

4 4.1 2중 DES 2중 DES C=EK2[EK1[P]] P=DK1[DK2[C]]
일단 3-DES를 보시기 전에 거쳐야 할 것이 왜 하필이면 Triple DES이냐 하는 점입니다.. 단순히 두 번 암호화 해서 키의 크기를 2배로 늘리는 것으로도 안전성을 늘릴 수 있다고 생각 할 수 있는데, 왜 굳이 3번이나 암,복호화를 수행하는 과정을 만들었나 하는 것을 먼저 보아야 할것입니다. 앞에서 말했듯이 2중 DES 56비트 키 K1, K2를 이용하여 두번 암, 복호화를 거치게 되면 키 길이가 두배로 늘어나기 때문에 전사적 공격에 대해서 안전성도 두배로 증가합니다. P=DK1[DK2[C]]

5 4.1 2중 DES 중간 결과에 의한 공격 X=EK1[P]=DK2[C]
평문 P를 2^56개의 가능한 모든 키 K1으로 암호한 다음 결과를 테이블로 저장 암호문 C를 키 K2의 가능한 모든 2^56개의 값으로 복호화 그러나, 2중 DES에 대해서, meet in the middle attack이란 공격방법이 개발 되었는데, 이것은 두개의 키중 K1으로 평문을 암호화한 결과와 K2로 암호문을 복호화한 결과가 같은 점이 존재한다는 점에 착안한 것입니다. Meet in the middle attack의해 2중 DES의 안전성은 다시 2의 56승으로 DES와 같아집니다.

6 4.2 3중 DES 3키에 의한 3중 DES 3단계 암호화 과정을 이용 기지 평문 공격의 복잡도 문제점 2^112
현실성 없는 공격법 => 공격 불가능 문제점 56*3 = 168 비트의 키를 사용 사실상 사용하기가 어려움 그래서, 다음으로 개선을 거쳐 나온 것이 3개의 키를 사용하는 Triple DES입니다. 복잡도는 2의 112승으로 높아졌고, 현실적인 공격방법을 거의 찾을 수 없었지만, 문제는 168비트의 키를 사용하기위한 시스템의 오버헤드가 너무 커서 사실상 사용할 수가 없었습니다.

7 4.2 3중 DES 2키에 의한 3중 DES 그래서, 다시 개선을 거쳐 나온 것이 우리가 현재 사용하는 2키에 의한 Triple DES입니다. 그림을 보시면, 평문이 먼저 K1으로 암호화 되고, 다시 K2로 복호화 됩니다. 그 복호화 된 결과를 다시 K1으로 암호화 하여 최종 암호화 결과를 보여줍니다. 복호화 과정은 그 과정의 reverse가 되겠습니다.

8 4.2 3중 DES OORS 90 1979년 Tuchman 에 의해 제안
키 관리 표준 ANS X9.17과 ISO 8732에 의해 채택 현재까지 실용적인 암호 분석 공격이 없음 Coppersmith Brute-force 공격 : 2^112 = 5*10^33 차수로 가능 차분 암호 해독은 단일 DES와 비교하여 10^52이 넘는 지수적인 복잡도를 가짐 장래의 성공적인 공격 가능 유형 Merkle & Hellman OORS 90 1979년 Tuchman에 의해 제안 되었으며, ANS X9.17 과 ISO 8732 표준안으로 채택되어, 사용되고 있으며 현재까지 실용적인 암호 분석 공격이 없는 것으로 알려져있습니다. Merkle과 Hellman에 의해 제안된 공격유형이 제시 되긴 했지만, 선택 평문- 암호문 공격 방식으로 제안된, 이 공격이 의미를 가지려면, 2의 56승개의 평문과 그에 매치되는 암호문이 요구 되기 때문에 현실적으로 어렵다고 여겨지고 있습니다.

9 4.4 Blowfish Bruce Schneier에 의해 개발된 대칭 블록 암호 방식 특성
빠른 속도 : 32비트 마이크로 프로세스에서 1 바이트 당 18클럭 사이클의 속도로 암호화 간결성 : 5K 이내의 메모리에서도 실행가능 단순성 : 간단한 구조로 구현이 쉽고 알고리즘의 강도 결정이 용이함 보안의 가변성 : 키의 길이는 가변적이며 448비트만큼 길어질 수 있어 높은 속도와 보안성 사이의 균형이 가능 64비트 블록의 평문을 암호화 Blowfish 알고리즘은 1993년 Bruce Schneier에 의해 개발된 대칭키 블록 암호 방식입니다. Blowfish의 특징으로 들자면, 기존의 DES보다 간단한 연산을 사용하기 때문에 빠른 속도로 작동합니다. 연산이 간단한 만큼, 많은 저장공간이 필요하지 않아.. 5K이내의 메모리에서도 실행가능합니다. 또한 키의 크기가 32비트에서 448비트까지 선택이 가능하기 때문에 선택적으로 안전성을 높이거나 낮출 수 있습니다.

10 4.4 Blowfish 키 사이즈 : 32비트에서 448비트 범위 생성 키는 K-배열에 저장 서브키는 P-배열에 저장
18개의 32비트 서브키 32비트 엔트리를 갖는 4개의 8*32 S박스 생성 키는 K-배열에 저장 K1, K2, …, Kj 1<= j <= 14 서브키는 P-배열에 저장 P1, P2, …, P18

11 4.4 Blowfish P-배열과 S-박스 생성 법
우선 P-배열과 4개의 S-박스를 차례로 상수 phi의 소수부 비트를 이용하여 초기화함. 그러므로 phi의 소수부의 맨 왼쪽 32비트 부터 계속 P1, P2, …, P18이 됨. 필요 시 K-배열의 워드를 재 사용하여 P-배열과 K-배열을 비트 단위 XOR 연산을 수행 P1= P1 XOR K1, P2= P2 XOR K2 … 현재의 P-배열과 S-배열을 이용하여 모두 0인 64비트 블록을 암호화, P1과 P2를 암호문으로 대체 현재의 P-배열과 S-배열을 이용하여 단계 3)의 결과를 암호화하고 P3와 P4를 암호문으로 대체 이 과정을 계속하여 P의 모든 요소와 S의 모든 요소를 차례로 매 단계마다 계속 변하는 Blowfish 알고리즘의 결과를 이용하여 갱신

12 이 그림은 blowfish의 작동을 간단히 그림으로 나타낸 것인데, 간단히 설명하자면,
먼저 64비트의 평문이 두개의 32비트 LE0과 RE0으로 나뉩니다. 그 다음, 앞에서 생성된 P-배열과 LE0과 XOR 연산을 하여 RE1이 생성되고, LE0과 P-배열의 결과인 RE1이 F박스를 거쳐서 나온 결과와 RE0과 XOR연산을 거쳐 LE1이 생성됩니다. 이 과정을 16라운드를 거쳐서 최종적으로 나온 LE17과 RE17이 합쳐져서 암호문을 생성하게됩니다.

13 F박스의 과정을 보시면, F박스 안에는 4개의 S박스가 구성되어져 있고, 앞에서 온 32비트의 연산결과가, 8비트 씩 나뉘어, S박스 연산을 거쳐서 오른쪽으로 가게 됩니다.

14 4.4 Blowfish 최종적인 S와 P를 생성키 위해서 Blowfish 암호 알고리즘이 총 521회 필요
비밀키가 자주 바뀌는 응용에는 적합하지 않음 빠른 실행을 위해서는 P와 S-배열은 알고리즘이 사용될 때마다 키로부터 유도하기 보다는 테이블에 저장 소요되는 메모리는 4K 바이트가 넘는다. Blowfish는 메모리 용량이 제한된 스마트카드와 같은 응용에는 적합하지 않음

15 암호화 및 복호화 기본연산 알고리즘 덧셈 : 2^32을 법으로 하는 연산 비트 XOR 연산 for i = 1 to 16 do
REi = LEi Pi; LEi = F[REi] REi-1; LE17 = RE P18 ; RE17 = LE P17;

16 4.4 Blowfish 논의 사항 Blowfish의 특성 암호해독이 매우 어려움 데이터 양쪽 모두에 대해서 연산이 수행됨
서브키와 S 박스들이 Blowfish 자신의 반복 적용에 의해 생성 데이터 양쪽 모두에 대해서 연산이 수행됨 고전 Feistel 암호와의 차이점 실행속도가 매우 빠름 Blowfish는 아마도 이 강의자료에 소개된 관용알고리즘 중에서는 가장 안전한 것일 겁니다. 왜냐하면, Blowfish의 경우 서브 키와 S박스들이 Blowfish 자신의 반복 적용에 의해 생성되기 때문에 비트 열이 토막으로 잘려서 암호해독이 매우 어렵습니다. 그리고 고전적인 Feistel 암호방식이 데이터의 한쪽 반에만 연산이 수행되는 것과 비교해서, 데이터의 양쪽에 모두 연산이 수행되기 때문에, 훨씬 해독이 어렵습니다. 또한 미리 P배열과 S박스를 저장시켜놓고 연산만을 처리하는 방식이기 때문에 실행 속도가 매우 빠릅니다. 그러나 P배열과 S박스를 미리 저장시켜놓기 때문에 많은 저장공간이 필요하여, 메모리 용량이 제한된 소형 매체에서는 사용이 불가능 합니다.

17 4.5 RC5 Ron Rivest에 의해 개발된 대칭 암호 알고리즘
RSA 데이터 보안회사의 BSAFE, JSAFE, S/MAIL등에 사용 다음으로 보실 것이 1994년 Ron Rivest에 의해 개발된 대칭키 알고리즘 RC5입니다.

18 4.5 RC5 특성 하드웨어 및 소프트웨어의 적합성 : 마이크로프로세서에서 일반적으로 사용되는 기본 연산만 사용
빠른 속도 : 단어 단위로 처리, 기본 연산은 한번에 데이터 단어 전체를 처리 다른 단어 길이 프로세서에의 적응성 : 단어 당 비트수를 매개변수로 이용, 매개변수가 다르면 다른 알고리즘이 됨 반복 수의 가변성 가변 길이의 키 단순성 : 구현이 쉽고 알고리즘의 강도 결정이 용이 낮은 메모리 요구량 : 스마트 카드나 기타 한정된 메모리를 사용하는 장치에 적당 높은 보안성 : 적당한 매개변수로 높은 보안성 제공 데이터 의존적인 순환 이동 : 데이터 양에 따라 결정되는 회전 이동을 채용=> 암호 해독에 대한 알고리즘의 강도를 높여 줌 특성으로는 다음과 같습니다.

19 4.5 RC5 RC5 매개변수 w : 단어의 비트 수, 16, 32, 64 r : 반복횟수, 0,1,…,255
b : 비밀 키 K 내의 8비트 바이트수 0,1,…,255 특정버전 : RC5-w/r/b RC5-32/12/6 32비트 단어(64비트 블록 처리) 12회 반복의 암호 및 복호 처리 16바이트 키(128비트)

20 4.5 RC5 키 확장과정

21 RC5의 암호화는 세 개의 기본 연산에 의해 이루어집니다.
2의 w승을 법으로 수행되는 덧셈과 비트 XOR연산, 그리고 좌측 순환 이동이 있습니다. Blowfish와 같이 평문을 두 개의 32비트 A와 B로 나누어서, 앞에서 만들어진 S배열과 덧셈연산이 이루어지고, 그 결과는 각각 LE0와 RE0로 나옵니다. LE1은 RE0과 LE0의 XOR연산을 거쳐 RE0을 기준으로 한 쉬프트 연산을 거쳐 나옵니다. RE1은 방금 나온 LE1과 RE0을 XOR연산하고, LE1기준으로 쉬프트 연산을 거침으로써, RE1이 나옵니다. 이 과정을 사용자가 원하는 라운드 수만큼 거치면, 원하는 암호문이 나오게 됩니다.

22 4.5 RC5 암호화 LE0 = A + S[0] ; RE0 = B + S[1]; For i = 1 to r do
LE i = ((LE i-1  1 RE i )  RE i-1 -1) + S[2 i]; RE i = ((RE i-1 -  1 LE i )  LE i-1 -1) + S[2 i+1];

23 DES challenge DES Challenge 일자 해독시간 수상자 비고 I 1997년1월 96일 R.Verser
-DESHALL 팀구성 -인터넷의 위력 입증 -약 24.6%의 키 공간 조사 II 1998년1월 41일 Distributed.Net -약 22,000명 참여 -약 50,000 CPU 링크 II-2 1998년7월 56시간 EFF -DES Cracker 라는 칩사용($250,000) -초당 880억개의 키를 조사하는 속도 III 1999년1월 22시간 15분 & Distrubuted.Net -Deep Crack 사용 -약 10만대의 PC 이용 -초당 2,450억개의 키 조사속도 다음으로 볼 알고리즘은 AES 즉 , Advanced Encryption Standart입니다. NIST, 즉, National Institute of Standards and Technology 미국 표준 기술 연구소는 DES알고리즘을 표준으로 정하고 사용한 이후로 병렬 컴퓨팅이 확산되고, DES를 해독하는데에 걸리는 시간이 하루 이하의 시간으로 단축 됨으로써 기존의 DES를 대체할 새로운 알고리즘을 공모하게 됩니다. 앞에서 살펴본 트리플 데스가 있긴 하지만, 느린 속도와 64비트의 고정된 블록 크기로 더 이상 완벽한 안전성을 보장해줄수 없다는 의견이 제기되어 장기적 으로 사용하기에는 무리라는 결론이 났습니다. 새로운 알고리즘 공모에는 일반적인 요구사항이외에 추가 요구사항으로 블록 크기를 128비트 이상 지원해야한다는 부분이 추가 되었습니다.

24 Rijndeal Structure • 블록사이즈 : 128 비트 , 키 사이즈 : 128/192/256 비트
• 구조 : 10 / 12 / 14 라운드의 구조 - Byte 단위의 연산을 이용 - 세개의 layer로 구성 14 Nk=8 12 Nk=6 10 Nk=4 Nb=8 Nb=6 Nb=4 Nr Nr : rounds Nb : block size / 32bit Nk : key size / 32bit ► Linear mixing layer 여러 라운드에 걸친 높은 확산 ShiftRow(state) , MixColumn(state) ► Non-linear Layer S-box의 병렬 적용 ByteSub(state) ► Key Addition Layer 중간 state에 라운드 키의 EXOR AddRoundKey(state)

25 Smplified Rijndael Scheme
암호화 복호화 암호화 과정에서 1회의 순열과 3회의 치환으로 구성된 4단계방식이 10라운드을 거쳐서 암호문을 생성하게됩니다. 이 구조의 두드러진 특징은 Feistel 구조가 아니라는 점입니다. 고전 Feistel구조를 생각해보면 데이터 블록의 절반이 다른 절반을 변환하기 위해 사용되고, 교환 되는 방식이지만, AES는 Feistel구조를 사용하지 않고, 각 라운드에서 순열과 치환이 행하여 지는 방식입니다. 하나하나씩 잠시 살펴보면, 바이트 치환은 블록의 바이트 대 바이트 치환을 수행하기 위해 하나의 S박스를 이용합니다. 행이동은 단순 순열이고 열 혼합은 GF(2의 8승) 산술식을 사용한 치환이고 라운드 키 추가는 현재 블록과 확장된 키의 일부로 단순 비트 단위의 XOR연산입니다.

26 Substitute Bytes Transformation
◈ state 의 각 바이트를 치환 • 각 바이트를 16x16 s-box를 이용하여 치환 • 8비트를 상위 4비트가 행, 하위 4비트가 열로 사용.

27 Shift row Transformation
• 각행을 행의 index 만큼 왼쪽으로 circular shift 함 .

28 Mix Column b0 b1 b2 b3 d0 d1 d2 d3 = a0 a3 a2 a1 a1 a0 a3 a2
c(x)의 최고차항이 4보다 크기때문에 mod m(x) 연산을 해주면 그값은 아래와 같다. c(x)mod m(x)= d(x) = d3x3 +d2x2 +d1x+d0 = c3x3 +c2x2+c6x2 +c1x+c5x+c4 +c0 d0 = a0•b0  a3•b1  a2•b2  a1•b3 d1 = a1•b0  a0•b1  a3•b2  a2• b3 d2 = a2•b0  a1•b1  a0•b2  a3• b3 d3 = a3•b0  a2•b1  a1•b2  a0• b3 위 식을 간단히 하면 아래와 같이 된다. b0 b1 b2 b3 d0 d1 d2 d3 = a0 a3 a2 a1 a1 a0 a3 a2 a2 a1 a0 a3 a3 a2 a1 a0 d0 d1 d2 d3 = b0 b1 b2 b3

29 대칭키 스트림 암호기 메시지를 비트 단위 또는 바이트 단위로 처리하는 방식 의사난수형태의 스트림 키를 평문과
XOR하여 암호문 생성

30

31 4.5 RC4 1987년 Ron Rivest가 고안한 대칭키 스트림 암호기 키 크기 – 가변적(8 ~ 2048 비트)
키 스트림생성 – 인덱스 덧셈과 교환(swap) 구조가 매우 간단하여 쉽게 구현할 수 있습니다. 이 방식은 EPCIS 표준에도 쓰이고 있는 TLS 즉. Transport Layer Security단에서도 사용되고 있고, 무선 랜 프로토콜에도 사용되고 있습니다.

32 암호화는 k값과 평문의 다음 바이트를 XOR 연산하는 것으로 생성됩니다. 복호화는 k값과 암호문의 다음 바이트를 XOR합니다.