I부 암호.

Presentation on theme: "I부 암호."— Presentation transcript:

1 I부 암호

2 대칭키 암호 3장

3 대칭키 암호 분류 스트림 암호  일회성 암호 형태 블록 암호  코드북 개념 형태 키가 상대적으로 짧다.
키가 긴 키스트림으로 쭉 뻗는다. 그리고 키스트림은 일회성 암호 키 같이 사용된다. 블록 암호  코드북 개념 형태 블록암호 키가 한 권의 코드북을 결정한다. 각 키가 다른 코드북을 결정한다. 혼돈과 확산 모두가 적용된다.

4 3장. 대칭키 암호 스트림 암호

5 STREAM 암호 1 Stream 암호 2 RC4 알고리즘

6 Stream 암호 일반 블럭 암호 스트림 암호 평문: M=m1m2m3… 암호문: C= EK(m1) EK(m2) EK(m3)…
알고리즘 n 비트 평문 암호문 m 비트 키 평문: M=m1m2m3… 암호문: C= EZ1(m1) EZ2(m2) EZ3(m3)… 초기값 이진 키수열 이진 평문 수열 일반 블럭 암호 스트림 암호

7 Stream 암호 평 문 암호문 키계열 키계열 암호문 평 문 송신자 키계열 평문 M 암호문 C 수신자

8 Stream 암호

9 Stream 암호 송수신자간에 사전에 공유된 비밀키(secret key)와 현재의 스트림 암호시스템상태(initial state)로부터 도출되는 키 수열(key steam)이 평문과 결합되어 암호문을 생성 키 수열의 길이는 평문의 길이와 동일하고 단 한번만 사용됨 예 : I LOVE YOU 메시지 -> 키 -> (eXclusive OR) 암호문 -> 활용 : 블럭암호에 비해서 빠르게 운영 이동통신에서 전송되는 data의 암호화에 사용

10 Stream 암호 키 스트림 주기 주기적 (periodic) 스트림 암호 : 키 스트림이 어떤 주기를 갖고 반복
비주기적 스트림 암호 : 키가 반복 없이 표현되는 일회용 패드(one-time pad)방식 평문과 키의 관계 동기식 스트림 암호(Synchronous Stream Cipher) 암호문을 복호화하여 평문을 찾을때 키 스트림과 암호문 사이에 동기가 필요 키 스트림이 평문과 관계없이 생성되므로 암호문과 암호문에 들어있는 키 스트림이 독립적이어서 정보유출의 가능성이 적다 선형 귀한 치환 레지스터(Linear Feedback Shift Register)

11 Stream 암호 평문과 키의 관계 자기 동기식 스트림 암호(Self-Synchronous Stream Cipher)
키 스트림이 평문과 암호문과 관계를 갖는다. 키 스트림은 평문 또는 암호문으로 부터 함수 관계에 의해 생성 전송 중 암호문의 비트가 손실 또는 변경되더라도 그 오류의 영향이 유한하게 된다. 오류 정정의 기능을 포함 가능 키 스트림과 암호문의 종속성으로 인해 해독하기 쉽다. 암호문 귀한자동키 (Feedback autokey)암호시스템 동기식 스트림 암호 시스템에 자기동기식 스트림암호의 장점을 결합하여 사용가능

12 Stream 암호 스트림 암호 시스템의 장점과 사용 군사 및 외교용으로 널리 사용 이동통신 환경에서 구현이 용이
안전성을 수학적으로 엄밀하게 분석 가능 이동통신 등의 무선 통신 데이터 보호에 적합 종류 RC4 SEAL

13 RC4 알고리즘 1987년 Rivest에 의해 설계된 가변 키 길이 지원 원래는 미공개
1994년 인터넷 뉴스그룹에 익명으로 공개된 알고리즘 Netscape Navigator의 데이타 보호용으로 사용되고 있으며, 다른 인터넷 응용들에서도 널리 사용되는 스트림 암호이다.

14 스트림 암호 스트림 암호는 과거에 많이 활용 스트림 암호의 미래? H/W에서 효율적 음성 암호화 위해서 속도 요구 등.
오늘날, 프로세스의 속도 증가로 S/W 기반 암호도 충분한 속도 가능 스트림 암호의 미래? 샤미르: “스트림 암호의 사망”논문발표

15 3장. 대칭키 암호 블록 암호

16 Simplified DES 3.1 S-DES 개요 3.2 S-DES 키의 생성 3.3 S-DES 암호 알고리즘

17 3.1 S-DES 개요 (1/2) 알고리즘 8비트 평문, 10비트 키 8비트 암호문 생성 알고리즘 구성 초기순열(IP)
순열, 치환 이용 fk 순열 함수 SW 역 순열(IP-1) 암호문 IP-1(fk2(SW(fk1(IP(평문))))) 복호문 IP-1(fk1(SW(fk2(IP(암호문)))))

18 3.1 S-DES 개요 (2/2)

19 3.2 S-DES 키의 생성 (1/4) K1 = P8(Shift(P10(key)))
K2 = P8(Shift(Shift(P10(key))) S-DES를 위한 키 생성

20 3.2 S-DES 키의 생성 (2/4) 키생성 K1 = P8(Shift(P10(key)))
10 비트 키 = (k1, k2, k3, k4, k5, k6, k7, k8, k9, k10) P10 순열 = (k3, k5, k2, k7, k4, k10, k1, k9, k8, k6) P10 예 제 10 bit key = ( ) P10(key) = ( )

21 3.2 S-DES 키의 생성 (3/4) 키 생성 K1 = P8 ( Shift ( P10 ( key )))
(Shift(P10(key))): LS-1[키의1st 5비트] & LS-1[키의 2nd 5비트] 앞 다섯 비트와 뒤 다섯 비트 좌로 순환 이동(1bit 좌측 순환이동) P10 =( k3, k5, k2, k7, k4, k10, k1, k9, k8, k6 ) Shift =( k5, k2, k7, k4, k3, k1, k9, k8, k6, k10 ) 예제) P10 = ( ) LS-1 = ( )

22 3.2 S-DES 키의 생성 (4/4) 키생성 K1 = P8(Shift(P10(key))) = P8(LS-1)
P8(LS-1) = P8( ) 10 비트에서 8비트 선택 치환 K1 = ( ) K2 = P8(Shift(Shift(P10(key)))) = P8(Shift(LS-1)) = P8(LS-2) LS-2 = Shift(LS-1) : LS-1의 결과에 2비트 좌측 순환 이동 K2 = P8(LS-2) = P8( ) = ( )

23 3.3 S-DES 암호 알고리즘 X = ( 1 0 1 1 0 0 1 1 ) IP(X) = ( 0 0 1 1 1 1 0 1 )
초기 및 최종 순열 함수 입력: 8비트 블록 평문 초기순열(IP) IP-1(IP(X)) = X 예제) X = ( ) IP(X) = ( ) IP-1(IP(X)) = ( ) 최종 순열

24 함수 fk (1/4) 순열, 치환 함수 조합 L( Left )  왼쪽 4비트 R( Right )  오른쪽 4비트
fk( L, R ) = (L  F( R, SK ), R ) F 함수(확장 순열) n n3 4 2 1 n4 평문 R: (n1, n2, n3, n4)

25 함수 fk (2/4) 8비트 서브키 K1 = (k11, k12, k13, k14, k15, k16, k17, k18)
XOR 연산 S-Box n k 13 14 17 18 2 4 3 1 11 12 15 16 p 0,0 1,0 0,1 1,1 0,2 1,2 0,3 1,3

26 함수 fk (3/4) 예제) P = ( ) 이라면 S0: 행 00, 열 10 ; 1,4 요소  행, 2,3 요소  열 S1: 행 01, 열 11 ; 5,8 요소  행, 6,7 요소  열 S0 = 11, S1 = 11 이 된다. (치환 효과) 결과값 1111

27 함수 fk (4/4) P4 순열 P4출력은 함수 F의 출력이 된다. 스위치 함수(SW) fk는 왼쪽 4비트만 변경
두 번째 fk에서는 K2만 다름

28 3.4 S-DES의 분석 Brute-force 공격 가능 10비트 키 210= 1024 기지 평문/암호문 쌍
평문: ( p1, p2, p3, p4, p5, p6, p7, p8) 출력 암호문: ( c1, c2, c3, c4, c5, c6, c7, c8 ) 미지의 키: (k1, k2, k3, k4, k5, k6, k7, k8, k9, k10) 기지 평문 공격: 각 ci는 pj와 kj의 다항식 함수햐 알고리즘은 10개의 미지수를 갖는 8개의 비선형 방정식 알고리즘에서 각각의 순열과 합 연산은 선형 사상 S박스를 통하여 비선형성을 도출 선형 사상 비선형 사상: 암호해독을 난해하게 하는 효과

29 Data Encryption Standard
DES: 1970년대 개발 IBM Lucifer 암호를 기반 미 정부 표준 DES 개발은 논쟁이 있었음 NSA 가 비밀리에 관련되었음 설계과정이 비공개 128bit 에서 64bit로 키 길이가 줄었음 Lucifer 알고리즘의 교묘한 변경

30 DES DES는 페이스텔 암호 각 회전은 단순 안전성은 주로 “S-box들”에 의존 64 비트 블록 길이 56 비트 키 길이
16 회전 각 회전에서 48 비트의 보조키 사용 각 회전은 단순 안전성은 주로 “S-box들”에 의존 각 S-boxe들은 6비트를 4비트로 매핑

31 DES의 한 회전 L R expand shift key S-boxes compress 28 48 32 Ki P box 

32 DES 확장 순열 입력 32 비트 출력 48 비트

33 DES S-box 8 “교환 박스” 또는 S-박스 각 S-박스는 6 비트를 4 비트로 매핑 1번 S-박스 입력 비트(0,5)
 입력 비트 (1,2,3,4) | 00 | 01 | 10 | 11 |

34 DES P-box 입력 32 비트 출력 32 비트

35 DES 보조키 56 비트 DES 키: 0,1,2,…,55 좌 반쪽 키 비트: LK 우 반쪽 키 비트: RK
우 반쪽 키 비트: RK

36 DES 보조키 i=1,2,. . .,16 번째 회전에서 LK = (LK를 ri 만큼 왼쪽으로 회전 이동)
RK = (RK를 ri 만큼 왼쪽으로 회전 이동) 보조키 Ki의 왼쪽 절반이 LK 비트 보조키 Ki의 오른쪽 절반이 RK 비트

37 DES 보조키 회전 1, 2, 9, 16에서 ri 는 1, 나머지 회전 ri 는 2
각 회전 LK의 비트 8,17,21,24 생략 각 회전 RK의 비트 6, 9,14, 25 생략 압축 순열은 56 bits of LK 와 RK의 56 비트에서 48 비트 보조키 Ki 생산 위 키 스케줄은 보조키를 생산

38 DES 마지막 최초 회전 전의 최초 순열 P 마지막 회전 후에 반씩을 교환
마지막 순열(P의 역)을 (R16,L16)에 적용함으로 암호문 생산 위 작업은 보안과는 무관

39 DES의 안전성 DES의 안전성은 다수의 S-box에 의존 30년간의 강도 높은 분석으로 “백도어”가 없음을 밝혀 냈음
오늘날 공격은 전수키 조사를 사용 피할 수 없는 결론 DES 설계자들은 그들이 무엇을 하고 있는지를 알고 있었다. DES 설계자들은 그들의 시대를 앞서가고 있었다.

40 블록 암호 표기 P = 평문 블록 C = 암호문 블록 암호문 C를 얻기 위해 키 K로 P를 암호화
C = E(P, K) 평문 P를 얻기 위해 키 K로 C를 복호화 P = D(C, K) 아래 사항을 주의 P = D(E(P, K), K) 그리고 C = E(D(C, K), K)

41 삼중 DES 현재, 56 비트DES 키는 너무 작다 하지만 DES가 도처에서 사용중: 어떻게 해야 하나?
C = E(D(E(P,K1),K2),K1) P = D(E(D(C,K1),K2),K1) 왜 2개 키로 암호화-복호화-암호화(EDE) 하는가? 단독 DES와 호환성: E(D(E(P,K),K),K) = E(P,K) 그리고 112 비트면 안전성을 위해 충분

42 3DES 왜 C = E(E(P,K),K)가 아닌가 ? 왜 C = E(E(P,K1),K2)가 아닌가 ? 여전히 56 비트 키
현실성이 있는 알려진 평문 공격 모든 가능한 키 K1 에 대해 E(P,K1) 의 선계산 테이블을 작성 (결과 테이블은 256 입력) 그러면 각 가능한 K2 에 대해 D(C,K2)가 테이블 내에 일치하는 요소가 발견될 때까지 계산 일치되는 요소가 발견되면, E(P,K1) = D(C,K2)

43 Advanced Encryption Standard
DES를 대치 AES 경쟁 (90년대 후반) NSA 가 공개적으로 관여 투명한 진행 많은 강력한 알고리즘들이 제안 라인댈(Rijndael) 알고리즘이 선정 “Rain Doll” 또는 “Rhine Doll”로 발음 반복되는 블록 암호 (DES와 동일) 페이스텔 암호가 아님 (DES와 상이)

44 AES 개요 블록 크기: 128, 192 또는 256 비트 키 길이: 128, 192 또는 256 비트 (블록크기와는 독립적)
10 에서 14 회전 (키 길이에 따라) 각 회전은 4개의 함수들을 사용 (3개“계층) ByteSub (비선형 계층) ShiftRow (선형혼합 계층) MixColumn (비선형 계층) AddRoundKey (키추가 계층)

45 AES ByteSub ByteSub는 AES의 “S-box” 두 수학적 연산의 비선형 합성 (그러나 역은 존재)
두 수학적 연산의 비선형 합성 (그러나 역은 존재) 192 비트 블록으로 가정: 4x6 바이트

46 AES “S-box” 입력 뒤의 4 비트 입력 앞의 4비트

47 AES ShiftRow 회전 이동

48 AES MixColumn (거대한) 룩업 테이블로 구축 각 행에 비선형, 역산 연산자 적용

49 AES AddRoundKey 회전키(보조키)는 키 스케줄 알고리즘에 의해 결정 블록과 보조키의 XOR 블록 보조키

50 AES 복호화 복호화를 위해서, 진행 과정은 역산이 가능해야만 함
 는 그 자체가 역산이므로 MixAddRoundKey의 역산 가능 MixColumn은 역산 가능 (역산은 룩업 테이블로 구축됨) ShiftRow의 역산은 쉽게 됨 (cyclic shift 의 다른 방향) ByteSub는 역산 가능 (역산은 룩업 테이블로 구축됨)

51 블록 암호의 다른 종류들 간단히 설명 할 암호… IDEA Blowfish RC6 보다 상세히 설명할 암호… TEA

52 IDEA “제임스 메세이”가 발명 64-비트 블록, 128-비트 키 혼합 모드 연산 다른 수학 연산들 결합
현대 암호의 거인 중 한 명 64-비트 블록, 128-비트 키 혼합 모드 연산 다른 수학 연산들 결합 최초로 이러한 접근 방법을 사용 오늘날 자주 사용되는 방법

53 Blowfish “브루스 쉬네이어”가 발명 64-비트 블록, 키는 448비트까지 변화 가능 페이스텔 암호 형태
Ri = Li1  Ki Li = Ri1  F(Li1  Ki) 회전 함수 F 는 4개의 S-box를 사용 각 S-box는 8 비트를 32 비트로 매핑 키에 의존하는 S-box 키에 의해 S-box들이 결정

54 RC6 “로널드 리베스트”가 발명 변수들 AES 경쟁시 마지막까지 검토된 후보 암호 순환이 테이터에 의존 블록 크기 키 크기
회전의 수 AES 경쟁시 마지막까지 검토된 후보 암호 순환이 테이터에 의존 알고리즘의 한 부분이 자료에 의존하는 것이 다른 알고리즘과 다른 점

55 Tiny Encryption Algorithm
64 비트 블록, 128 비트 키 32-비트 연산 컴퓨터를 가정 회전의 수는 가변적 (32회 정도면 안전) 간단한 회전함수를 사용하므로 상대적으로 많은 회수의 회전 필요

56 TEA 암호화 32개 회전을 가정 (K[0],K[1],K[2],K[3]) = 128 bit key
(L,R) = plaintext (64-bit block) delta = 0x9e3779b9 sum = 0 for i = 1 to 32 sum += delta L += ((R<<4)+K[0])^(R+sum)^((R>>5)+K[1]) R += ((L<<4)+K[2])^(L+sum)^((L>>5)+K[3]) next i ciphertext = (L,R)

57 TEA 복호화 32개 회전을 가정 (K[0],K[1],K[2],K[3]) = 128 bit key
(L,R) = ciphertext (64-bit block) delta = 0x9e3779b9 sum = delta << 5 for i = 1 to 32 R = ((L<<4)+K[2])^(L+sum)^((L>>5)+K[3]) L = ((R<<4)+K[0])^(R+sum)^((R>>5)+K[1]) sum = delta next i plaintext = (L,R)

58 TEA 코멘트 페이스텔 암호 형태 구축하기가 간단하고 쉬우며, 빠르고 작은 메모리를 요구 등 “관련 키” 공격이 가능
 (XOR)대신에 + 와 - 사용 구축하기가 간단하고 쉬우며, 빠르고 작은 메모리를 요구 등 “관련 키” 공격이 가능 확장된 TEA (XTEA)는 관련 키 공격을 제거할 수 있음(약간 더 복잡) 단순화된 TEA (STEA)  암호분석의 예제로 사용, 안전하지 않은 버전

59 3장. 대칭키 암호 블록 암호 운용 모드

60 다수의 블록 다수 블록을 어떻게 암호화 할 수 있는가? 각 블록 마다 새로운 키를 준다? 각 블록을 독립적으로 암호화 한다?
일회성 암호처럼 문제가 있다! 각 블록을 독립적으로 암호화 한다? 앞 블록에 의존하도록 암호화한다? 즉 블록들을 “체인”으로 연결한다? 블록에서 남은 부분은 어떻게 처리하는가?

61 운용 모드 운용모드는 종류가 많으나 여기서는 3종류만 토의 전자 코드북 (ECB) 모드 각 블록을 독립적으로 암호화
한 가지 약점이 있음 암호블록 연결 (CBC) 모드 블록을 체인처럼 함께 연결 ECB 모드 보다 안전, 실질적으로 추가 작업 없음 카운트 (CTR) 모드 스트림 암호처럼 작동 임의 접근에 대중적으로 사용

62 ECB 모드 표기: C=E(P,K) 주어진 평문 P0,P1,…,Pm,… 블록 암호를 사용하는 확실한 방법
암호화 복호화 C0 = E(P0, K), P0 = D(C0, K), C1 = E(P1, K), P1 = D(C1, K), C2 = E(P2, K),… P2 = D(C2, K),… 고정키 K에 대해 코드북 암호의 전자적 버전 각 키에 대해 새로운 코드북

63 ECB 복사-붙여넣기 공격 평문을 아래와 같이 가정 Alice digs Bob. Trudy digs Tom.
64-비트 블록과 8-비트 ASCII를 가정: P0 = “Alice di”, P1 = “gs Bob. ”, P2 = “Trudy di”, P3 = “gs Tom. ” 암호문: C0,C1,C2,C3 트루디가 복사-붙여넣기 공격 시행: C0,C3,C2,C1 복호화는 다음과 같음 Alice digs Tom. Trudy digs Bob.

64 ECB 약점 Pi = Pj 라고 가정 그러면 Ci = Cj ,그리고 트루디가 Pi = Pj임을 알고 있다고 가정

65 앨리스는 ECB 모드를 싫어한다 앨리스의 압축되지 않은 이미지와 ECB모드(TEA)로 암호화한 그림
왜 이런 현상이 일어나는가? 같은 평문 블록  같은 암호문!

66 CBC 모드 C0 = E(IV  P0, K), P0 = IV  D(C0, K), 블록들은 함께 “체인”으로 연결
임의 초기화 벡타 (IV)가 CBC 모드 초기화를 위해 필요 IV 는 임의수 이나 비밀이 필요 없음 암호화 복호화 C0 = E(IV  P0, K), P0 = IV  D(C0, K), C1 = E(C0  P1, K), P1 = C0  D(C1, K), C2 = E(C1  P2, K),… P2 = C1  D(C2, K),…

67 CBC 모드 같은 평문 블록도 다른 암호문 블록을 생산 복사-붙여넣기 공격이 가능하나 더욱 복잡 오류의 영향이 있을 수 있음
만약 C1에 오류가 발생, 오류를 G라 하면 P1  C0  D(G, K), P2  G  D(C2, K) 그러나 P3 = C2  D(C3, K), P4 = C3  D(C4, K),… 자동적으로 오류 수정!

68 앨리스는 CBC 모드를 좋아한다 앨리스의 압축되지 않은 이미지와 ECB모드(TEA)로 암호화한 그림
왜 이런 현상이 발생하는가? 같은 평문이라도 다른 암호문을 생산!

69 카운트 모드 (CTR) CTR는 임의 접근에 많이 사용 블록 암호를 스트림 암호처럼 사용
암호화 복호화 C0 = P0  E(IV, K), P0 = C0  E(IV, K), C1 = P1  E(IV+1, K), P1 = C1  E(IV+1, K), C2 = P2  E(IV+2, K),… P2 = C2  E(IV+2, K),… CBC도 임의 접근을 위해 사용될 수 있다.!!!

70 3장. 대칭키 암호 무결성

71 데이터 무결성 무결성  인가되지 않은 데이터의 수정을 방지 하거나 적어도 탐지 하는 것 예제: 인터넷 은행에서 자금 이동
비밀성은 제공이 용이하나 무결성은 심각 암호화는 비밀성을 제공 암호화 자체만으로 무결성을 확신할 수 없음. (일회성 암호와 ECB 공격을 상기)

72 메시지 인증 코드(MAC) 메시지 인증 코드 (MAC) MAC은 CBC의 나머지로 계산 데이터 무결성을 위해 사용
무결성은 비밀성과 동일하지 않음 MAC은 CBC의 나머지로 계산 Compute CBC 암호화를 계산하여 암호문 블록의 마지막만 저장

73 MAC 계산 MAC 계산 (N 블록으로 가정) C0 = E(IV  P0, K), MAC은 평문과 함께 전송
C1 = E(C0  P1, K), C2 = E(C1  P2, K),… CN1 = E(CN2  PN1, K) = MAC MAC은 평문과 함께 전송 수신자는 같은 방법으로 계산하여 그 결과가 MAC과 일치 여부를 검검 수신자는 키 K 를 알고 있어야 함

74 MAC이 왜 동작되는가? 앨리스가 4개의 평문 블록을 가지고 있다고 가정 앨리스가 다음을 계산
C0 = E(IVP0,K), C1 = E(C0P1,K), C2 = E(C1P2,K), C3 = E(C2P3,K) = MAC 앨리스가 밥에게 IV,P0,P1,P2,P3,MAC을 전송 트루디가 P1을 X로 변경했다고 가정 밥은 다음을 계산 C0 = E(IVP0,K), C1 = E(C0X,K), C2 = E(C1P2,K), C3 = E(C2P3,K) = MAC  MAC 오류가 MAC 속으로 전파 (CBC 복호화와 상이) 키 K를 알지 못하고는 트루디가 MAC을 MAC으로 변경불가

75 비밀성과 무결성 한 키로 암호화하고 다른 키로 MAC 계산 왜 같은 키를 사용하지 않는가?
보안성을 추가할 수가 없음! 한번의 “암호화”로 비밀성과 무결성을 제공하는 것은 연구과제이다.

76 대칭 암호 용어들 비밀성 무결성 (MAC) 인증 프로토콜 (나중에…) 해시 함수로 할 수 있는 어떤 것들 (다음 장에서…)
데이터를 보안성이 없는 채널에서 전송 보안성이 없는 미디어에서 안전하게 저장 무결성 (MAC) 인증 프로토콜 (나중에…) 해시 함수로 할 수 있는 어떤 것들 (다음 장에서…)