Chap 2. 관용 암호 방식

목 차 1. 암호의 개념 2. 암호 용어 3. 관용 암호 방식 모델 4. 관용 암호 방식 기술 5. DES (Data Encryption Standard) 6. 3중 DES

1. 암호의 개념 통신 당사자들끼리만 아는 비밀스런 신호나 부호 암호화와 복호화하기 위한 원리, 수단, 방법 등을 취급하는 기술이나 과학 Alice Bob Plaintext attack ? Cryptography 개방통신로

2. 암호 용어 암호해독 암호알고리즘 복호알고리즘 attack 평문 (plaintext) 암호문 (ciphertext) 암호화 키 (public key) 공개키 디렉토리 송신자 수신자 (암호장치) 복호화 키 (secret key)

3. 관용 암호 방식 암호화 키(Encryption key) = 복호화 키(Decryption key) 대칭키 암호 시스템, 단일키 암호 시스템, 관용 암호 방식 암호알고리즘 복호알고리즘 평문 (plaintext) 암호문 (ciphertext) 공용키

DES, RC5, SKIPJACK, IDEA, SEAL, RC4 등 Security 암호 알고리즘의 비도는 키의 비밀성에 의존 장점 다양한 알고리즘 개발, 알고리즘 수행속도 빠르다 단점 키 관리 및 키 분배의 어려움 디지털 서명의 어려움 DES, RC5, SKIPJACK, IDEA, SEAL, RC4 등

3.1 암호시스템의 영역 평문을 암호화하기 위한 연산자의 유형 사용된 키의 수 평문 처리 방법 치환 (Substitution) : 평문의 각 원소를 다른 원소로 사상 전치 (Transpostion) : 평문의 각 원소를 재배열 대부분의 혼합 시스템은 다단계의 치환과 전치사용 사용된 키의 수 관용키 : 송수신자가 같은 키를 사용 공개키 : 송수신자가 다른 키를 사용 평문 처리 방법 블록 암호화 (Block cipher) : 연산을 블럭단위로 처리 스트림 암호화 (Stream cipher) : 입력을 연속적으로 처리

3.2 암호 해독 Cryptanalysis 암호 메시지에 대한 공격의 유형 평문이나 키 또는 이 두 가지를 모두 발견하려는 시도 과정 암호 메시지에 대한 공격의 유형 암호문 단독 공격 (Ciphertext only) 기지 평문 공격 (Known plaintext) 선택 평문 공격 (Chosen plaintext) 선택 암호문 공격 (Chosen ciphertext) 선택 원문 공격 (Chosen text)

4. 관용 암호 방식 기술 평문 메시지의 은닉 방법 Steganograhpy 방법 메시지의 존재 자체를 은폐 암호 방법 다양한 원문의 변환에 의해 외부인이 그 의미를 알지 못하도록 메시지를 변형

4.1 Steganography 특징 예제 메시지의 존재 자체를 은폐 원문내의 단어나 문자를 적당히 배열 함으로써 실제 메시지를 나타냄 예제 문자 마킹 (Character marking) 원문의 문자에 연필로 덧써서 표시를 해 빛을 적당한 각도로 비춰어야만 보임 보이지 않는 잉크 (Invisible ink) 종이에 열이나 화학 처리를 해야만 보이는 잉크를 사용 핀 구멍 (Pin punctures) 빛을 비춰야만 보이는 작은 구멍을 원문에 넣는 방법

Steganography의 장점 Steganography의 단점 타자 수정 리본 (Typewriter correction ribbon) 흑색 리본으로 타자된 줄 사이에 강한 빛에서만 보이는 수정리본을 이용하여 타자하는 방법 Steganography의 장점 비밀통신에 대한 사실이 발견되면 안되는 사용자들에 의해 이용될 수 있다. Steganography의 단점 상대적으로 적은 정보비트를 은닉하는데 많은 오버헤드 요구 방법 노출시 재사용 불가

4.2 치환 기법 4.2.1 시이저 암호법 쥴리어스 시저에 의해 개발 예제 (Key : 3) 암호화 (문자 p를 암호화) 4.2 치환 기법 4.2.1 시이저 암호법 쥴리어스 시저에 의해 개발 예제 (Key : 3) 평문 : meet me after the toga party 암호문 : PHHW PH DIWHU WKH WRJD SDUWD 암호화 (문자 p를 암호화) C = E(p) = (p+3) mod (26) 일반화 : C = E(p) = (p+k) mod (26) 문자 p는 C로 암호화

복호화 단점 p = D(C) = (C -3) mod (26) 일반화 : p = D(C) = (C - k) mod (26) 문자 C는 p로 복호화 단점 암호화 및 해독 알고리즘을 알고 있다. 가능한 키가 25개 뿐이다. Brute-force attack이 가능 평문의 언어를 알고 있으며 쉽게 인식할 수 있다.

4.2.2 단일 치환 암호법 각 문자에 26자의 치환 가능 단점 시이저 암호의 키 공간을 급격히 증가 시이지 암호 : 25 단일 치환 암호법 : 26! 단점 출현 빈도수를 이용해 평문 유추가능 ex) 영어 문장에는 t, e, a, h 등이 많이 나타남 암호문에서도 그에 상응하는 문자가 같은 빈도로 나타남

4.2.3 다중 문자 치환 암호 기법 2자기씩 암호화 playfair 알고리즘은 5 * 5 행렬에 기초 키워드가 monarchy인 행렬 키워드 중복 문자를 제외하고 좌에서 우로, 상에서 하로 문자를 채운다. I와 J는 한 문자로 취급

암호화 방법 반복되는 평문은 X와 같은 채움문자로 분리 balloon : ba lx lo on 같은 행에 두문자가 있을 경우 우측에 있는 문자와 치환 ar은 RM으로 치환 같은 열에 두문자가 있을 경우 바로 밑에 문자와 치환 mu는 CM으로 치환 그 외에 평문자쌍는 대각선에 위치한 문자와 치환 hs는 BP로, ea는 IM(또는 JM)

특징 단점 monoalphabetic 암호기법의 진보된 방법 알파벳은 26 가지 2중자는 26 * 26 = 676 가지 2중자의 빈도수 분석은 어려움 1, 2차 대전중 미국, 영국 육군에서 사용 단점 평문의 원래 구조가 많이 드러남 수백자의 암호문자로 구조를 알 수 있다. 암호기법은 평문보다 평평한 분포가 가짐. 하지만 해독가에겐 해용한 구조를 가짐 그림 2.6 문자 출현의 상대 분표도 참조

4.2.4 다중 단일 문자 치환 암호화 단순 단일 문자 치환 방법을 개량 다중 단일 문자 치환 암호방법의 공통점 하나의 단일 문자 치환 규칙 집합을 사용 주어진 변환에 사용될 규칙은 키에 의해 결정 Vigenere 방법 (표 2.4 참조) 키워드 : deceptive 평문 : We are discovered save yourself” 키 : d e c e p t i v e d e c e p t i v e d e c e p t i v e 평문 : w e a r e d I s c o v e r e d s a v e y o u r s e l f 암호문 : ZICVTWQNGRZGVTMAVZHCQYGLMGJ

특징 단점 평문자에 대한 암호문자가 유일한 키워드에 각 문자에 대하여 여러 개 존재 문자 빈도수에 대한 정보가 불분명해짐다 평문 구조에 대한 정보가 모두 은폐되지는 않는다. 단일 문자나 Vigenere로 암호화 되었는지 아는 것은 쉽다. 빈도수에 따라 키워드의 길이를 유추가능 (3이나 9로 유추가능) 암호문에서 “VTW”이 나타남

4. 3 전치기법 평문자의 순서를 바꿈 rail fenec 기법 깊이 : 2 평문 : meet me after the toga party mematrhtgpry etefeteoaat 암호문 : mematrhtgpryetefeteoaat

4. 3 전치기법 사각형 행렬 사용 전치 암호기법은 두 단계 이상의 전치를 행함으로써 더 안전성을 높일 수 있다. 키 : 4 3 1 2 5 6 7 평문 : a t t a c k p o s t p o n e d u n t i l t w o a m x y z 암호화 : TTNAAPTMTSUOAODWCOIXKNIYPETZ 전치 암호기법은 두 단계 이상의 전치를 행함으로써 더 안전성을 높일 수 있다.

4.4 회전자 기계 다단계 암호화의 원리를 적용(그림 2.7 참조, P44) 특징 회전자 기계의 강도는 다중 실린더에 기인 독립적으로 회전하는 실린더 집합으로 사용 각 실린더는 26개의 입력핀과 출력핀 가지고 있음 단일 실린더 한 문자때에는 단일 문자 치환 암호 26개이 평문자를 사용한 후에는 실린더가 초기의 위치로 와서 격국 주기가 26인 다중 단일 문자 치환 세 개의 실린더일 경우 26 * 26 * 26 = 17,576가지의 알다른 알파벳 치환을 가짐 회전자 기계의 강도는 다중 실린더에 기인

5. DES (Data Encryption Standard) 특징 IBM에서 Lucifer System을 개선하여 만듬 1997년 미 상무성의 국립 표준국(NBS)에서 표준 암호 알고리즘으로 채택 64비트 블럭 암호 알고리즘 56비트 키를 사용 64비트 중 8비트는 parity check로 사용 기본 구조 round 수 : 16 round 복호화는 암호화의 역순 최근에는 DES암호화를 세 개의 키로 세 번 반복함으로써 암호의 강도를 높인 Triple-DES를 사용

m=(m0 , m1) Feistel 암호 블럭의 크기는 짝수(2n) 평문 m을 크기가 n인 두 블럭으로 나눔 암호화 라운드 1 :U0=(m0,m1) ==> U1=(m1,m2) 라운드 i :Ui-1(m i-1,mi) ==> Ui=(mi,mi+1) 라운드 h :Uh-1=(mh-1,mh) => Uh=(mh,m h+1) 여기서 mi+1=mi-1 + fki(mi)

NDS와 LUCIFER NDS(New Data Seal) 1975년 Feistel에 의해 설계 블럭크기:128비트 두개의 s-box이용(4비트 -> 4비트변환) LUCIFER 암호 1973년 IBM의 Host Feistel DES의 원형 평문및 암호문의 블럭사이즈:128비트 암호화 과정:16단계

DES의 역사 전용 암호시스템 : 타 그룹간의 통신에 불리==> 데이터 암호화 표준이 필요 전용 암호시스템 : 타 그룹간의 통신에 불리==> 데이터 암호화 표준이 필요 공개암호 표준: 미국 연방 정부가 움직임 표준화 검토(1972),적합한 암호 알고리즘 조사 1973년 5월:암호방식 공모(1차) 1974년 8월: 2차 공모==>IBM이 요건을 갖춤 ==>NBS가 요건을 NSP에 의뢰

조사에 대한 요구 1. It must provide a high level of security. 2. It must be completely specified and easy to understand. 3. The security provided by the algorithm must not be based on the secrecy of the algorithm. 4. It must be all users and suppliers.

조사에 대한 요구 (계속) 5. It must be adaptable for use in diverse applications. 6. It must be economical to implement in electronic devices and be efficient to use. 7. It must be amenable to validation. 8. It must be exportable.

DES의 역사(계속) 1975년~1977:일반 comment,계약 체결 1977:NBS(NIST)가 DES를 표준 암호 알고리즘으로 채택 U.S.banks have been adopted DES NBS postponed guarantee term of DES from till 1988 to till 1993 NSA proposed CCEP(Commercial COMSEC Endorsement Program;상용 통신 안전 보증 계획)instead of DES U.S. bank expect to continue the use of DES

Li = Ri-1 Ri = Li-1 XOR f (Ri-1, Ki) 5.1 DES DES의 기본 구조 (데이타 암호화부) 입 력 K1 K2 : 초기 치환 L0 L1 L2 R0 R1 R2 f R16 L16 역초기 치환 출 력 K16 Li = Ri-1 Ri = Li-1 XOR f (Ri-1, Ki)

초기 치환 IP 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7

. . . . f함수의 구성도 확장전치 (비트 선택표 ) 48bit K (48bit) S1 S2 S8 S7 P R(32bit) 확장전치 (비트 선택표 ) 48bit K (48bit) S1 S2 S8 S7 . . . . P 32 bit S-box table

치환 P 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 비트 선택표 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1

S-box Table S1 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 예) 1 0 1 1 0 1 ------ 6비트 입력 행 (3행) 열 (6열) 10진수 ‘1’를 4비트로 출력 : 0 0 0 1

DES의 기본 구조 (키 생성부) : 키 c0 c1 c2 c15 d0 d1 d2 d15 K1 K2 K16 선택 치환 선택치환2 좌측 시프트 c1 c2 c15 d0 d1 d2 d15 선택치환2 K1 K2 K16 :

선택 치환 - 1 57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19 11 3 60 52 44 36 63 55 47 39 31 23 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4 선택 치환 - 2 14 17 11 24 1 5 3 28 15 6 21 10 23 19 2 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 38 44 49 39 56 34 53 46 42 50 36 29 32

쉬프트 스케줄 라운드 수 좌측 쉬프트 수 1 1 2 1 3 2 4 2 5 2 6 2 7 2 8 2 9 1 10 2 11 2 12 2 13 2 14 2 15 2 16 1

DES는 강한 쇄도 효과(Avalanche Effet)를 갖는다. DES에 관한 우려사항 알고리즘의 성질을 이용한 암호 해독의 가능성 예) s - box의 약점에 대한 공격 가능성 주장 제기됨 그러나, 약점을 발견한 사람은 현재 존재 하지 않음 키 길이에 관한 우려 Key Serarch Machine ( 기지 평문 공격 ) Cost Expected search Time $ 100,000 35hours $1,000,000 3.5hours $10,000,000 21minutes

; 1970년대/80년대 --- low computing power 90년대 --- high computing power Brute force Attack ; 1970년대/80년대 --- low computing power 90년대 --- high computing power 미국 수출 허용 기준인 40비트의 키 : Michael Wienerd의 key search machine으로 0.2초만에 해독 가능 Key size Number of One Encryption 106 Encryption Alternative Keys per micro sec per micro sec 32bits 223 = 4.3 * 109 35.8 minutes 2.15ms 56bits 256 = 7.2 * 1016 1142years 10.01h 128bits 2128 = 3.4 * 1038 1024years 5.4 * 1018 years

5.2 DES의 공격 방법 공격 방법 차분 암호 해독 (Differential Cryptanalysis) 선형 암호 해독 (Linear Cryptanalysis) 247 기지 평문으로 해독가능 기지 평문이 선택 평문보다 구하기 쉽기만 DES공격으로서의 선형 암호 해독은 가능성이 없다. 선형 암호 해독의 타당성의 주장이 약하다.

5.3 DES 작동 모드

ECB (Electronic Codebook) 모드의 특징 평문은 64비트씩 처리 마지막 비트가 64비트 미만이면 나머지 비트를 채운 후 진행 동일한 블록이 입력되면 암호문도 같다. --> 해독될 위험성이 있다. 중요 데이타가 같은 위치에 있을 때 취약블럭이 상호 결합하지 않음 => 연속적인 블럭 암호화법 ; Chaining 기법

... ... ECB (Electronic Codebook) 모드 PN CN K P1 C1 K P2 C2 K 복호화 CN PN 암호화 DES 암호화 PN CN K DES 암호화 P1 C1 K DES 암호화 P2 C2 K ... 복호화 DES 복호화 CN PN K DES 복호화 C1 P1 K DES 복호화 C2 P2 K ...

CBC (Cipher Block Chaining) 모드의 특징 하나의 암호화 스텝의 출력을 사용하여 다음 입력으로 수정 각각의 암호 블럭은 서로 영향을 받음 선행하는 평문 블럭 전체에 좌우됨 Cn : 모든 평문 블럭 P1, P2, ..., Pn의 함수 암호화 : Cn=Ek(Pn+C n-1) 복호화 : Qn=Dk (Cn) + C n-1 =Pn Padding Self-Recovering 기능

... ... CBC (Cipher Block Chaining) 모드 P1 C1 K  P2 C2 K  PN CN K  암호화 DES 암호화 P1 C1 K  DES 암호화 P2 C2 K  DES 암호화 PN CN K  C N-1 ... 복호화 CN DES 복호화 C1 P1 K  DES 복호화 C2 P2 K  ... K DES 복호화  C N-1 PN

CBC 그림참조 레지스터 레지스터  E D  P P 1 64 64 1

CFB (Cipher Feedback) 모드의 특징 문자의 길이 : m(1<m<64) 암호화 하기 위한 m비트 : DES 출력의 m비트 DES 알고리즘이 회선 양단에서 암호화로서 사용 Shift Register : 매번 새로운 비트로 교체 암호문은 선행하는 평문 모두의 함수

... ... CFB (Cipher Feedback) 모드 암호화 K  P1 C1 P2 C2 PN CN CN-1 복호화 K 64비트 레지스터 DES 암호화 선택 j 비트 K  P1 C1 P2 C2 PN CN ... CN-1 복호화 64비트 레지스터 DES 복호화 선택 j 비트 K  P1 C1 P2 C2 PN CN ... CN-1

CFB 그림 참조 레지스터 E 선택  P 레지스터 D 선택  P 1 2 ... 8 9 1

OFB (Output Feedback) 모드의 특징 CBC, CFB의 Error Extention에 대한 응용 Vernam type 키 스트림 : 주기성이 있음 Feedback의 출발 위치를 제외하고는 CFB와 유사

... ... OFB (Output Feedback) 모드 암호화 ON-1 K  PN CN K K P1  C1 P2  64비트 레지스터 64비트 레지스터 ... 64비트 레지스터 DES 암호화 선택 j 비트 K  PN CN K K DES 암호화 DES 암호화 선택 j 비트 선택 j 비트 P1  C1 P2  C2 복호화 64비트 레지스터 DES 복호화 선택 j 비트 K  P1 C1 P2 C2 PN CN ... ON-1

OFB 참조 그림 레지스터 D 선택  P E 1

6. 3중 DES DES의 brute-force공격에 대한 취약성을 보완 3중 DES 새로운 알고리즘 개발 : IDEA (Chap. 7) DES의 응용 : 3중 DES, 2중 DES 3중 DES 2개의 키를 사용 암호화 : 암호화, 복호화, 암호화 복호화 : 복호화, 암호화, 복호화 brute-force 공격 : 2112

암호화, 복호화 과정 암호화 E D K1 K2 P C B A 복호화 D C K1 K2 P A B