정보보안 강의자료 ( 2016년 1학기 ) 윤 정 오 정 보 통 신 공 학 과

정보사회 (-세상의 변화-) 돈은 사회의 변화추세가 어디로 가는지를 나타내는 지표 탈 산업 사회화의 추세 정보통신 기술의 발달 디지털과 사이버 세계의 새로운 지식산업이 높은 부가가치 창출 탈 산업 사회화의 추세 물적 자원시대에서 지식기반 자원시대로 전환 컴퓨터와 통신기술의 발달로 사회생활 양식의 변화 정보통신 기술의 발달 정보 유통에 필요한 비용을 현저하게 낮추어 비약적인 생산성 향상 지식과 정보량의 폭발적 증가 2020년 2배/73일 2050년 현재 지식의 1%만 사용 세계화의 진전 세계적 대응이 불가피(판매/지식확산/이익, 경쟁/질병/환경)

지식사회 혁명 거대한 새로운 변화의 물결 지식 혁명 디지털 혁명 기술정보 혁명 인터넷 혁명 .com ism(닷컴이즘)  지식과 정보의 활용을 극대화하고 체계적으로 관리하지 않는 조직은 생존 불가

지식사회 의식의 혁명 지식사회 특질 사고, 행동, 의식의 혁명 필요 인터넷을 이용한 빛의 속도로 상거래 부가가치 재료의 변화 지역적/시간적 한계극복 글로벌 네트워크를 통한 실시간 거래 정보의 획득, 판단, 행동의 속도혁신이 성공 요인 사고, 행동, 의식의 혁명 필요 인터넷을 이용한 빛의 속도로 상거래 (CALS: Commerce At Light Speed)

인터넷 상거래 특성

1. 서론 컴퓨터 보안 (Computer security) 컴퓨터에 저장된 파일 및 통신망 유통정보를 보호하기 위해 도구 필요 공용시스템의 경우(시분할 시스템) 데이터 네트워크를 통해서 접근하는 시스템 컴퓨터 보안 (Computer security) 데이터를 보호하고 해커를 막기 위한 도구의 집합을 총칭

네트워크 보안 (Network security) 분산 시스템의 등장 사용자와 컴퓨터간의 데이터전송을 위한 네트워크 및 통신시설의 이용 네트워크 보안 (Network security) 전송중인 자료를 보호 인터네트워크 보안 (Internetwork security) 상호연결된 네트워크 집합을 보호

정보 보안 (Information Security) 컴퓨터 보안 (Computer Security) 네트워크 보안 (Network Security) 인터네트워크 보안 (Internetwork security) 인터넷 보안 (Internet Security) 보안 정보보호

1.1 보안 공격, 서비스 및 기법 보안 공격 (Security Attack) 조직에 의하여 소유된 정보의 안전성을 위태롭게 하는 어떠한 행위 보안 메커니즘 (Security Mechanism) 보안 공격을 예방, 탐지, 복구하기 위하여 설계된 메커니즘 보안 서비스 (Security Service) 조직의 데이터 처리 시스템과 정보의 전송에 대한 안전성을 수행하기 위한 서비스

1.2 보안 공격 A B 보안 공격 (Security Attack) 보안 공격의 유형(그림 1.1) 조직의 정보보호를 저해하는 제반행위 보안 공격의 유형(그림 1.1) 방해 (Interruption) 시스템의 일부가 파괴되거나 사용할 수 없는 경우로 가용성에 대한 공격 A B

A A B C B C 가로채기 (Interception) 불법수정 (Modification) 비인가자들의 불법적인 접근에 의한 신뢰성에 대한 공격 A B C 불법수정 (Modification) 비인가자들의 불법적인 접근 뿐만 아니라 불법적인 변경에 의한 무결성에 대한 공격 A B C

위조 (Fabrication) 비인가자들의 시스템에 대한 위조물 삽입에 의한 인증에 대한 공격 A B C

자연적 위협 요소 고의적 위협 요소 자연적 재앙, 에러 및 손실, 정보관리 부실 네트워크 장애, 시스템 장애 내부의 적, 컴퓨터 해킹, 위장(Masquerade) 메시지 순서 변조 (Modification of Message Sequence) 정보 변조 (Modification of Information) 서비스 거부 (Denial of Service), 부인 (Repudiation) 정보노출 (Leakage of Information) 신분 레이블 변조 (Modification of Identification Label)

그림 1.2 보안에 대한 적극적 및 소극적 네트워크 위협

소극적 공격 (passive attack) 가로채기 도청 트래픽 분석: 송수신자 신분, 통신시간 , 주기관찰 변화가 없으므로 검출 곤란 검출보다 예방 필요 적극적 공격 (active attack) 방해: 가용성 침해 불법적 수정: 무결성 침해 재전송 : 데이터 단위 수동적 획득 -> 다시 전송 서비스 부인 (서비스 거부 공격) : 특정 목표물을 대상으로 무력화, 성능저하 유발 예방하기가 대단히 어려움: 모든 자원과 시간 보호불가능 예방, 탐지, 복구 필요

1.3 보안 서비스 보안 서비스 (Security Service) 보안 서비스의 종류 조직의 데이터 처리 시스템 및 정보 전송에 대한 보안을 강화하기 위한 제반 서비스 보안 서비스의 종류 기밀성 서비스 (confidentiality, 비밀성, 비밀유지) 합법적인 실체만 읽을 수 있도록 보호하는 서비스 메시지 내용 공개, 트래픽 흐름 분석, 도청으로부터 전송 메시지 보호 접속 구간 기밀성, 내용 기밀성, 메시지 흐름 기밀성 암호 알고리즘 이용

무결성 서비스 (integrity, 온전성) 합법적인 실체만 수정할 수 있도록 보호하는 서비스 연결형 무결성 서비스, 비연결형 무결성 서비스 연결형 : 메시지 스트림을 대상, 불법변경 보호와 서비스 부인 방지 비연결형 : 개인 메시지들만을 대상, 불법변경 보호 해쉬 함수, 디지털 서명, 암호 알고리즘 이용 인증 서비스 (authentication, 보증) 정보 및 시스템의 자원을 사용하는 정당한 사용자임을 확인할 수 있도록 보호하는 서비스 연결된 송수신자 확인, 제 3자의 위장 확인 발신처 인증, 메시지 인증, 실체 인증

부인봉쇄 서비스 (non-repudiation, 부인방지) 송수신자가 송수신 사실에 대한 부인을 하지 못하게 하는 것 송신자 부인 봉쇄, 수신자 부인봉쇄, 배달증명, 의뢰증명 접근 제어 서비스 (access control, 접근통제) 사용자가 시스템 혹은 특정 자원에 접근 하고자 할 때 인가 받은 사용자만 접근을 허락하도록 제어하는 서비스 가용성 서비스 (availability) 컴퓨터 시스템이 인가 당사자가 필요로 할 때 이용할 수 있게 보호하는 서비스

1.4 네트워크 보안 모델(그림 1.3)

그림1.4 네트워크 접근 보안모델 1차 방어: gatekeeper function 패스워드 기반 로그인 절차: 사용자 인증, 접근 통제 감독 및 심사 구조: 웜, 바이러스 등의 검출과 거부 2차 방어: monitoring function 원하지 않는 침입자를 검출하기 위한 내부적 보안 제어 내부적 활동을 감독 침입자 존재 발견을 위한 저장된 정보의 분석

보안 서비스 설계 보안을 위한 모든 기술의 2가지 요소 일반 모델로부터 특정 보안 서비스 설계의 기본 사항 보안을 위한 암호화 또는 특정 코드의 추가 암호화 키와 같은 어떤 비밀 정보 일반 모델로부터 특정 보안 서비스 설계의 기본 사항 보안 관련 변환 알고리즘의 설계 공격자가 변환을 파악할 수 없는 것이어야 함 변환 알고리즘과 병용될 비밀 정보의 생성 비밀정보의 분배 및 공유 방법의 개발 특정 보안 서비스를 위한 보안 알고리즘 및 비밀정보를 사용할 통신주체간의 프로토콜 지정

2.1 관용암호 모델 평문(Plaintext): 이해하기 쉬운 일반 메시지 암호문(Ciphertext): 이해할 수 없도록 변형된 메시지 암호화 과정: 특정한 방식의 알고리즘에 비밀 유지되는 키를 적용하여 알기 쉬운 평문을 알 수 없는 암호문으로 변환 동일한 메시지도 키에 따라서 알고리즘의 변환 결과가 다르게 출현 관용암호방식의 안전성 특징 암호 알고리즘은 키 없이 암호문 자체만으로 해독 불가하도록 강도 유지 안전성은 알고리즘 자체의 비밀성이 아니라 키의 비밀성에 의존 암호문과 암복호 알고리즘이 알려져도 메시지의 해독은 불가하다고 가정 키만을 비밀 유지 필요

그림 2.1 관용암호방식의 단순 모델 장점 단점 암호 알고리즘을 비밀유지 할 필요가 없으므로 저가의 칩으로 개발 유용 DES, RC5, SKIPJACK, IDEA, SEAL, RC4, SEED, AES 등 다양한 알고리즘 개발 알고리즘 수행속도 빠르다 단점 키 관리 및 키 분배와 디지털 서명의 어려움

그림2.2 관용암호 시스템의 모델 평문 메시지: X= [X1, X2, …, Xm] 암복호화 키: K= [K1, K2, …, Kj] 암호문: Y= Y1, Y2, …, Ym] 암호화: Y= EK(X) 복호화: X= DK(Y) 공격자는 암호문에 대응하는 평문을 알기 위하여 예측평문을 생성하거나 키를 찾아내어 복호를 시도 암호알고리즘 복호알고리즘 attack 암호해독 공격 평문( X) 평문(X) 암호문(Y) 송신자 수신자 복호화 키(K) 암호화 키(K)

2.1.1 암호학 암호: 통신 당사자들끼리만 아는 비밀스런 신호나 부호 암호화와 복호화하기 위한 원리, 수단, 방법 등을 취급하는 기술이나 과학 암호시스템 3가지 영역 평문을 암호화하기 위한 연산자의 유형 치환(置換, Substitution) : 평문의 각 원소를 다른 원소로 사상 전치(轉置, Transposition) : 평문의 각 원소를 재배열 사용된 키의 수 관용키 : single-key, symmetric, secret-key; 송수신자가 같은 키를 사용 공개키 : two-key, asymmetric, public-key; 송수신자가 다른 키를 사용 평문 처리 방법 블록 암호화 (Block cipher) : 연산을 블록 단위로 처리 스트림 암호화 (Stream cipher) : 입력을 연속적으로 처리

2.1.2 암호 해독 Cryptanalysis Brute-Force Attack 안전성 평문이나 키 또는 이 두 가지를 모두 발견하려는 시도 과정 Brute-Force Attack 가능한 모든 경우의 수를 시도(전사적 탐색, 전사 공격) Probable-Word Attack 안전성 무조건 절대 안전성 비용과 시간이 충분하여도 복호하기가 불가능 계산상 안전성 해독 비용이 복호된 정보의 가치를 초과 해독시간이 정보의 유효한 수명주기를 초과

암호 메시지에 대한 공격의 유형 암호문 단독 공격 (Ciphertext only) 암호 알고리즘, 해독할 암호문 기지 평문 공격 (Known plaintext) 하나 또는 그 이상의 알고 있는 평문에 대한 암호문을 인지 선택 평문 공격 (Chosen plaintext) 해독자가 선택한 평문 메시지와 해당 암호문을 인지 선택 암호문 공격 (Chosen ciphertext) 해독자가 선택한 암호문과 해독된 평문을 인지 선택 원문 공격 (Chosen text)

표2.2 모든 키 탐색을 위해 요구되는 평균시간 32 232 = 4.3 x 109 231 s = 35.8분 2.15 ms 키 크기(비트) 가능한 키의 수 s당 1 암호화 s당 106 암호화 32 232 = 4.3 x 109 231 s = 35.8분 2.15 ms 56 256 = 7.2 x 1016 255 s = 1142년 10.01 h 128 2128 = 3.4 x 1038 2127 s = 5.4 X 1024년 5.4 x 1018년 26문자 permutation 26 ! = 4 X 1026 2 X 1026 s = 6.4 X 1012년 6.4 x 106년

2.2 Steganograhpy 보안기술의 범주 평문 메시지의 은닉 방법 특징 보안(Security): 정보를 보호하는 방법 첩보(Intelligence): 정보를 탐지하는 방법 평문 메시지의 은닉 방법 Steganograhpy 방법 메시지의 존재 자체를 은폐 cryptography 방법 다양한 원문의 변환에 의해 외부인이 그 의미를 알지 못하도록 메시지를 변형 특징 원문내의 단어나 문자를 적절히 발췌하여 조합배열 함으로써 실제 메시지를 나타냄

사용 예 문자 마킹 (Character marking) 보이지 않는 잉크 (Invisible ink) 원문의 문자에 연필로 덧써서 표시를 빛을 적당한 각도로 비추어야만 보임 보이지 않는 잉크 (Invisible ink) 종이에 열이나 화학 처리를 해야만 보이는 잉크를 사용 핀 구멍 (Pin punctures) 빛을 비춰야만 보이는 작은 구멍을 원문에 넣는 방법 타자 수정 리본 (Typewriter correction ribbon) 흑색 리본으로 타자된 줄 사이에 강한 빛에서만 보이는 수정리본을 이용하여 타자하는 방법

그림 2.3 형사 모스를 위한 수수께끼 (출처: Silent World of Nicholas Quinn, by Colin Dextor) 3rd March Dear George, Greetings to all at Oxford. Many thinks for your letter and for the Summer examination package. All Entry Forms and Fees Forms should be ready for final despatch to the Syndicate by Friday. 20th or the very latest, I'm told, by the 21st. Admin has improved here, though there's room for improvement still; just give us all two or three more years and we'll really show you! Please don't let these wretched 16+ proposals destroy your basic O and A pattern. Certainly this sort of change, if implemented immediately, would bring chaos. Sincerely yours,

Steganography의 장점 Steganography의 단점 비밀통신에 대한 사실이 발견되면 안 되는 사용자들에 의해 이용 암호화의 경우의 문제점 암호화 한다는 사실이 통신 메시지가 중요하거나 비밀임을 암시 즉, 암호화는 송수신자간에 무언가 감출게 있다고 생각하게 함 Steganography의 단점 상대적으로 적은 정보비트를 은닉하는데 많은 오버헤드 요구 방법 노출시 재사용 불가 (키를 적용하는 기법을 추가하여 단점 극복) (메시지를 먼저 암호화 한 후에 Steganography을 이용하여 은닉가능)

2.3 고전적 암호기법 2.3.1 치환기법 평문의 문자를 다른 문자나 숫자 또는 기호로 대체 시키는 방법 간단한 치환 암호기법 쥴리어스 시저에 의해 개발(Ceaser Cipher, 시이저 암호법) 예제 (Key: 3) 평문 : meet me after the toga party 암호문 : PHHW PH DIWHU WKH WRJD SDUWB 암호화 (문자 p를 암호화) 문자 P를 C로 암호화 C = E ( P ) = (P+3) mod (26) P = D ( C ) = (C – 3) mod (26)

일반화 단점 암호화 복호화 암호화 및 해독 알고리즘이 단순하다. 단순 대치이므로 문자 출현 빈도수에 의한 복호가 용이하다. C = E(P) = (P + k) mod (26) 복호화 P = D(C) = (C - k) mod (26) 단점 암호화 및 해독 알고리즘이 단순하다. 단순 대치이므로 문자 출현 빈도수에 의한 복호가 용이하다. 한 키가 25개 뿐이다. Brute-force attack이 가능 (시도해야 할 키의 개수가 많도록 응용 필요) 평문의 언어를 알고 있으며 쉽게 인식할 수 있다. (평문 유형을 알 수 없도록 암호화 이전에 압축하여 인식을 어렵계 변환)

단일문자 치환 암호기법(Monoalphabetic Ciphers)의 단점 문자 출현 빈도수를 이용해 평문 유추가능 사례 암호문: UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWTMXUZUHSX EPTEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ 암호문 문자의 출현 100분율 P 13.33 Z 11.67 S 8.33 U 8.33 O 7.50 M 6.67 H 5.83 D 5.00 E 5.00 V 4.17 X 4.17 F 3.33 W 3.33 Q 2.50 T 2.50 A 1.67 B 1.67 G 1.67 Y 1.67 I 0.83 J 0.83 C 0.00 K 0.00 L 0.00 N 0.00 R 0.00

암호문에서도 일반적 평문에 대응하는 문자가 같은 빈도로 나타남 일반적 평문의 츌현율 1 문자 출현율: { e, t, r, n, i, o, a, s } 2문자 출현율: th 등이 많이 나타남 암호문에서도 일반적 평문에 대응하는 문자가 같은 빈도로 나타남

1문자 대응 2문자 대응 암호문에 ZWP에 평문 3중자 "the"로 해독 암호문자 S, U, O, M 및 H가 모두 상대적으로 높은 빈도 수를 갖으며 아마도 평문자 집합 r, n, i, o, a, s 중의 하나에 각각 해당 가정 최저 빈도 수를 갖는 문자 A, B, G, Y, I, J는 아마도 평문자 집합 w, v, b, k, x, q, j ,z 에 포함 가정 2문자 대응 암호문에서 가장 빈도 높은 2중자는 ZW로서 3 번 출현 평문에서 가장 빈도 높은 2중자는 th 암호문 2중자 ZW 를 th에 대응 암호문에 ZWP에 평문 3중자 "the"로 해독 (1문자 빈도율에서 P는 e에 해당 (3중자 빈도율에서 the와 대응)

direct contacts have been made with political UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ t a e e te a that e e a a VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX e t ta t ha e ee a e th t a EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ e e e tat e the t 지금까지 4문자만 확인됐지만 벌써 메시지를 조금은 찾아냈다. 빈도수를 계속 분석하고 시행착오를 거듭하면 해답획득 가능. 단어 사이의 공백을 추가한 완전한 평문은 다음과 같다. it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the viet cong in moscow

2.3.1 다중 문자 치환 암호 기법 (Multiple-letter encryption, Polygram substitution) 2자씩 암호화 playfair 알고리즘은 5 * 5 행렬에 기초 영국 Wheatstone 개발 1985년 친구인 playfair가 발표 키워드가 monarchy인 행렬 M O N A R C H Y B D E F G I/J K L P Q S T U V W X Z 키워드 중복 문자를 제외하고 좌에서 우로, 상에서 하로 문자채움 I와 J는 한 문자로 취급

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

특징 단점 monoalphabetic 암호기법의 진보된 방법 2중자의 빈도수 분석은 1중자보다 어려움 알파벳은 26 가지 2중자는 26 * 26 = 676 가지 2중자의 빈도수 분석은 1중자보다 어려움 1차대전 중 영국 육군 야전 표준 시스템 사용 2차 대전 중 미국 육군 및 연합군에서 사용 단점 평문의 원래 구조가 많이 드러남 수백자의 암호문자로 구조를 알 수 있다. 암호기법은 평문보다 일정한 분포를 갖지만 해독이 용이함.

Hill 암호 1929년 미국 수학교수 Laster Hill 제안 n-gram 치환 암호방식 M = 3일 경우 암호문 치환 C1 = (k11 p1 + k12 p2 + k13 p3 ) mod 26 C2 = (k21 p1 + k22 p2 + k23 p3 ) mod 26 C3 = (k31 p1 + k32 p2 + k33 p3 ) mod 26 C: 암호문 P: 평문 k: 키

암호문 형식을 열 벡터와 행렬로 표현 암호화 사례 평문: PAYMOREMONEY 암호 키 C1 k11 k12 k13 P1 C2 = k21 k22 k23 P2 C3 k31 k32 k33 P3 17 17 5 K = 21 18 21 2 2 19

암호문 계산 평문을 숫자변환 PAYMOREMONEY: P 15, A  0, Y  24, … … 숫자 대입 암호문 치환 K(15 0 24) + (375 819 486) mod 26 = (11 13 18) = LNS C1 = 17 x 15 + 17 x 0 + 5 x 24 = 375 mod 26 = 14 … …11 C2 = 21 x 15 + 18 x 0 + 21 x 24 = 819 mod 26 = 31 … …13 C3 = 2 x 15 + 2 x 0 + 19 x 24 = 486 mod 26 = 18 … …18 C1 k11 k12 k13 P1 C2 = k21 k22 k23 P2 C3 k31 k32 k33 P3 C1 17 17 5 15 C2 = 21 18 21 0 mod 26  C3 2 2 19 24 11 13 18 L N S

복호문 계산 암호문 계산 형식 C = EK(P) = KP에서 평문 P = DK(C) = K-1C = K-1KP = P; 여기서, K-1는 역행열:; K-1K = I 역행렬 계산 P1 4 9 15 11 P2 = 15 17 6 13 mod 26  P3 24 0 7 18 15 24 P A Y 17 17 15 4 9 15 443 442 442 1 0 0 21 18 2 15 17 6 = 858 495 780 mod 26  0 1 0 2 2 19 24 0 7 494 52 365 0 0 1

다중 단일 문자 치환 암호화(Polyalphabetic cipher, 다표식 대치 암호) 다중대치를 통하여 고정키 단일 문자 치환 방법을 개량 다중 단일 문자 치환 암호방법의 공통점 하나의 단일 문자 치환 규칙 집합을 사용 주어진 변환에 사용될 규칙은 키에 의해 결정 Vigenere 방법(1523-1596, 프랑스) 키워드 : 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 암호문:ZICVTWQNGRZGVTWAVZHCQYGLMGJ

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

키워드의 변형 사용 키워드와 평문을 연결하여 키로 사용 키 : 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 평문 : 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 암호문: ZICVTWQNGKZEIIGASXSTSLVVWLA 암호 해독상 취약점 키와 평문이 동일한 문자 빈도분포를 갖기 때문에 통계적 기법을 해독에 사용 가능

통계적 해독을 방지하기 위해 키워드를 평문과 같은 길이로 사용 1918년 Gilbert Vernam이라는 AT&T기술자에 의해 소개 문자 대신 2진 자료로 작동 Ci = pi  ki pi = 평문의 i 번째 비트, ki = 키의 i 번째 비트, Ci = 암호문의 i 번째 비트  = 배타적 논리합(XOR) 연산 암호문은 평문과 키를 비트 방식의 XOR 연산을 수행하여 생성 복호문은 XOR의 속성상 해독 역시 같은 비트 방식으로 연산 pi = Ci  ki 이 방식의 본체는 키 생성 방법 Vernam은 키를 반복케 하는 순환 테이프의 사용을 제안 비록 이 시스템이 긴 키의 사용으로 암호 해독을 지극히 난해하게 했지만, 충분한 암호문, 기지 또는 추정의 메시지 열의 사용, 또는 둘 다에 의해 파괴될 수 있다. 미 육군 통신대 장교 Joseph Mauborgne는 메시지와 정확히 같은 길이이고 반복되지 않는 랜덤 키 사용을 제안 일회용 키(one-time pad) 이 방법의 실질적인 문제는 송수신자가 모두 이 랜덤 키를 보유하고 보호 Vernam 암호 기법은 다른 기법보다 탁월한 아이디어지만 거의 사용하기 어려움.

2.3.2 전치기법(Transposition Techniques) 평문자나 비트의 순서를 절차에 따라 위치를 재조정 rail fence 기법(단순한 전치 암호방식) 깊이 : 2 평문 : meet me after the toga party 암호문 : mematrhtgpryetefeteoaat 동일한 문자의 출현주기 문제점 mematrhtgpry etefeteoaat

복잡한 전치기법 row by row write / column by column read (key order) 메시지를 행렬의 행 순서로 쓰고 열 순서로 판독 row by row write / column by column read (key order) n x m 행렬로 평문구성 키 : 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 문자가 바뀌는 일정한 주기 발견

평문 메시지의 문자들을 그 위치를 나타내는 숫자로 표시하면; 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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 2728 첫 번째 전치 후의 결과 031017 24 04 11 18 25 02 09 16 23 01 08 15 22 05 1219 26 0613 20 270714 21 28 규칙적인 구조 발견 (4문자씩 증가순서) 동일한 방식의 2차적 전치후의 결과 17 09 05 2724 16 12 0710 02 22 20 03 25 15 13 04 23 19 14 1101 26 21180806 28 규칙적인 구조가 파괴되었고 더욱 해독하기 어렵다. 다중단계 재 암호화 두 단계 이상의 다중전치와 치환을 하는 것은 일정한 주기를 회피하고 암호문 해독을 더욱 어렵게 만드는 효과

2.3.3 회전자 기계(Rotor Machine) 다중단계 재암호화의 원리를 적용 특징 독립적으로 회전 순환하는 실린더 집합으로 사용 각 실린더는 26개의 입력핀과 출력핀 보유 주기가 26인 다중 단일문자 치환 (26주기 polyalphabetic substitution) 저/ 중/ 고속의 3단계 실린더로 구성하여 다중 치환방식을 수행

그림 2.8 번호 연결 회로를 갖는 3-실린더 회전자 기계

회전자 기계의 암호화 안전성은 다중 실린더에 기인 3 개의 실린더일 경우 26 * 26 * 26 = 17,576가지의 다른 알파벳 치환 회전자 기계의 원리는 과거 DES와 같은 암호 방식의 발전 방향을 암시 사용 예(2차 세계대전 사용) 영국: Typex 미국: Sigaba(M-134) 독일: Enigma 일본: Purple

3.1 단순 DES[Simplified Data Encryption Standard] 알고리즘 8비트 평문, 10비트 키 8비트 암호문 생성 초기순열(IP) 순열, 치환 이용 fk 순열 함수 SW 역 순열(IP-1) 암호문 IP-1(fk2(SW(fk1(IP(평문))))) 복호문 IP-1(fk1(SW(fk2(IP(암호문)))))

그림 3.2 S-DES를 위한 키 생성 암호문 복호문 K1 = P8(Shift(P10(key))) IP-1(fk2(SW(fk1(IP(평문))))) 복호문 IP-1(fk1(SW(fk2(IP(암호문))))) K1 = P8(Shift(P10(key))) K2 = P8(Shift(Shift(P10(key)))

3.1.2 S-DES 키의 생성(1/3) 예 제 10 비트 key = ( 1 0 1 0 0 0 0 0 1 0 ) 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 3 5 2 7 4 10 1 9 8 6 1 2 3 4 5 6 7 8 9 0 예 제 10 비트 key = ( 1 0 1 0 0 0 0 0 1 0 ) P10(key) = ( 1 0 0 0 0 0 1 1 0 0 )

(2/3) K1 = P8(Shift(P10(key))) (Shift(P10(key))): LS-1[키의1st 5비트] & LS-1[키의 2nd 5비트] 첫 번째 다섯 비트와 두 번째 다섯 비트 좌로 순환 이동(1트 좌측 순환이동) P10 =( k3, k5, k2, k7, k4, k10, k1, k9, k8, k6 ) Shift =( k5, k2, k7, k4, k3, k1, k9, k8, k6, k10 ) 예제) P10 = ( 1 0 0 0 0 0 1 1 0 0 ) LS-1 = ( 0 0 0 0 1 1 1 0 0 0 ) 1 2 3 4 5 6 7 8 9 0

(3/3) K1 = P8(Shift(P10(key))) = P8(LS-1) P8(LS-1) = P8( 0 0 0 0 1 1 1 0 0 0 ) 10 비트에서 8비트 선택 치환 K1 = ( 1 0 1 0 0 1 0 0 ) 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( 0 0 1 0 0 0 0 0 1 1 ) K2 = ( 0 1 0 0 0 0 1 1 )

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

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

(2/4) 8비트 서브키 K1 XOR S-Box n k p 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

(3/4) 예제) P = (0100 0111) 이라면 S0: 행 00, 열 10 ; 1/4 요소  행, 2/3 요소  열 S0 = 11, S1 = 11 이 된다. (치환 효과)

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

3.1.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의 다항식 함수gi 암호 알고리즘은 10개의 미지수를 갖는 8개의 비선형 방정식 알고리즘에서 각각의 순열과 합 연산은 선형 사상 S박스를 통하여 비선형성을 도출 선형 사상을 비선형 사상으로 변경함으로써 암호해독을 난해하게 하는 효과

3.1.5 DES와의 관계 IP-1 · fK16 · SW · fK15 · SW · … … · SW · fK1 IP IP-1 · fk2 · SW · fk1 · IP (평문) 10비트 키에서 2개의 8-비트 서브키 생성 F 함수는 4비트 연산 4행 4열로 구성된 2개의 S 박스 사용 DES는 64-비트 블록단위로 16단계 처리 IP-1 · fK16 · SW · fK15 · SW · … … · SW · fK1 IP 키 56비트에서 16개의 48-비트 서브키 생성 F함수는 32비트 연산 4행 16열로 구성된 8개의 S박스 사용

3.2 블록 암호 기법의 원리 3.2.1 스트림 암호와 블록 암호 기법 스트림 암호 블록 암호 3.2 블록 암호 기법의 원리 3.2.1 스트림 암호와 블록 암호 기법 스트림 암호 한번에 1비트 혹은 1 바이트 Vigenere 암호, Vernam 암호 블록 암호 평문 블록 전체(64비트 – 전형적) 다양한 작동모드 사용 스트림 방식에 비해 응용 범위 넓음 대부분 네트워크 기반 관용 암호 방식에 사용 본 교재는 블록 암호 방식에 초점

3.2.2 Feistel 암호 구조의 유도 n비트 블록처리: n비트 평문을 입력으로 n비트 암호문 출력 역으로 n 비트 암호문 입력에 대해 n비트 평문 출력(역의 성립: reversible, 비단수형: nonsingular) 2n 가지의 서로 다른 블록 존재 가능 그림 3.4 n 비트-n 비트 블록치환( n=4 인 경우) 4비트입력으로 16개 값 중 하나 선택하고 , 내부 치환에 의하여 16개 출력 값 중 하나 대응하여 4비트 출력

3.2.3 Feistel 암호 방식 두 개 이상의 기본 암호 연속적 수행(치환, 순열 번갈아 수행) 확산과 혼돈 Shannon Claude Shannon 소개(SHAN49) 통계적 분석에 기초한 암호 해독 방지 Shannon “매우 이상적인 암호는 암호문에 대한 모든 통계적 정보가 사용된 키와 독립적이어야 한다.” 확산(diffusion) 평문의 통계적 구조가 암호문에 광범위하게 분산(평문과 암호문 관계 복잡) 각 평문 숫자가 다수의 암호문 숫자 값에 영향 yn = mn+i (mod 26) ; M = m1, m2, m3, … :문자 메시지 혼돈(confusion) 암호문의 통계적 구조와 암호 키 값 사이의 관계 복잡 키를 이용한 암호문 생성 방법 복잡( 키 추론 어려움)

Feistel 암호 구조 처리구조 그림 3.5 고전 Feistel 구조 하나의 반복 구조 길이 2w 비트인 평문 블록(L0, R0) 분할 처리 K로부터 유도된 n개의 키(Ki) 사용 n회의 동일한 반복 구조 실행 그림 3.5 고전 Feistel 구조 하나의 반복 구조 오른 쪽 반 R0에 반복 함수 F 적용 반복 서브키 K1 적용(K  Ki) 왼쪽 반 L0와 XOR(치환 작용) 좌우 양쪽 결과를 교환(순열 작용)

설계 특성 블록 크기(64비트) 큰 블록은 보안 강화하지만 암/복호 속도는 저하 암/복호 속도를 고려 64비트 일반적 키 크기(128비트) 큰 키는 보안 강화 하지만 암/복호 속도는 저하 암/복호 속도를 고려하여 128비트 일반적(64비트 이하는 해독 용이) 반복 수 다중 반복과정은 보안성 강화 16회 반복이 일반적 서브키 생성 알고리즘 서브키 생성 방법이 복잡할수록 강력 반복함수 적용되는 반복함수가 복잡할수록 강력

Feistel 복호 알고리즘 암호화 마지막 반복 복호화 과정 암호화과정의 역 순서 처리 첫 반복 LE16 = RE15 RE16 = LE15  F(RE15, K16) 복호화 과정 암호화과정의 역 순서 처리 첫 반복 LD1 = RD0 = LE16 = RE15 RD1 = LD0  F(RD0, K16) = RE16  F(RE15, K16) = [LE15  F(RE15, K16)]  F(RE15, K16) = LE15

암호화 마지막 반복 암호 알고리즘의 i 번째 반복 과정은 LE16 = RE15 RE16 = LE15  F(RE15, K16) LEi = REi-1 REi = LEi-1  F(REi-1, KI) 역으로 정리하면 REi-1 = LEi LEi-1 = REi  F(REi-1, Ki) = REi  F(LEi, Ki) 복호화 그림에서 ( i-1 ) 번째 복호결과를 만들기 위한 ( i )번째 입력형식 증명

3.3 DES (Data Encryption Standard) 특징 1977년 미 상무성의 국립 표준국(National Bureau of Standards)에서 연방 정보처리 표준 채택 46(FIPS PUB46) 64비트 블럭 암호 알고리즘 56비트 키를 사용 64비트 중 8비트는 parity check로 사용 기본 구조 round 수 : 16 round 복호화는 암호화의 역순 최근에는 DES암호화를 세 개의 키로 세 번 반복함으로써 암호의 강도를 높인 Triple-DES를 사용 치환과 전치 혼합방법, 블럭 암호, 관용암호방식

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

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

3.3.1 DES 암호화 DES의 알고리즘의 일반적 모형 처리 단계 평문: 64bit 키: 56bit + 8bit(패리티) 초기순열 단계(IP) 16라운드 반복 좌우 교환단계 역초기순열 단계(IP-1)

초기순열 단계 순열 X = IP(M) 64비트 평문 메시지 M M1 M2 M3 M4 M5 M6 M7 M8

표 3.2 DES의 순열 표 (b) 역초기 순열 IP-1 (64  64) (d) 순열함수(32  32) (a) 초기 순열 IP (64  64) © 확장순열(32  48) (b) 역초기 순열 IP-1 (64  64) (d) 순열함수(32  32)

DES의 기본 구조 (단일 반복 과정)

f 함수의 구성도 8개의 S-box로 구성 각 S-box는 6비트 입력, 4비트 출력 생성

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 예) 0 1 1 0 1 1 ------ 6비트 입력 행 (1행) 열 (13열) ‘011011’를 4비트로 출력 : “0 1 0 1”

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

DES 키의 단계별 계산표 순열선택1 (PC-1) 57 49 41 33 25 17 9 1 58 50 42 34 26 18 64 56 C0, D0 : 각 28비트 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 (PC-2) 56->48 48비트 키 출력 생성 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

Key 쉬프트 스케줄 라운드 수 좌측 쉬프트 수 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

3.3.1 DES 복호화 서브키 역순 사용 암호화와 같은 알고리즘 사용 Feistel 구조

3.3.3 쇄도 효과(Avalanche Effect) 평문이나 키의 작은 변화가 암호문에 대하여 중요한 변화 발생

3.4 DES의 강점 3.4.1 56 비트 키 사용에 대한 우려 미 정부의 채택 이후 DES의 보안 수준에 대한 우려가 지속. 3.4.1 56 비트 키 사용에 대한 우려 미 정부의 채택 이후 DES의 보안 수준에 대한 우려가 지속. 알고리즘의 성질을 이용한 암호 해독의 가능성 예) s - box의 약점에 대한 공격 가능성 주장 제기됨 그러나, 약점을 발견한 사람은 현재 존재 하지 않음 키 길이에 관한 우려 Key Search Machine ( 기지 평문 공격 ) Cost Expected search Time $ 100,000 35 hours $1,000,000 3.5 hours $10,000,000 21 minutes

Key size Number of One Encryption 106 Encryption 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

3.4.2 DES 알고리즘의 성질에 대한 우려 DES 알고리즘 자체 성질을 이용한 해독 가능성 8개의 치환 표 또는 S-box 전체 알고리즘에 대한 설계기준이 공개된 적이 없다. S-box의 약점에 대해 알고 있는 공격자가 해독할 수 있게 설계 됐을 가능성에 대한 의혹 제기 수년간 S-box의 수많은 정규성과 예측 못할 동작이 발견 그럼에도 S-box에 대하여 치명적인 약점을 발견한 사람은(적어도 그러한 발견이 공개된 적은)아직까지 없다.

3.5 차분 및 선형 암호 해독 3.5.1 차분 암호 해독 (Differential Cryptanalysis) DES에 적용해서 널리 알려짐 255 미만의 복잡도로 DES를 해독 247의 선택평문을 가지고 247 차수로 DES를 해독 3.5.2 선형 암호 해독 (Linear Cryptanalysis) 247 기지 평문으로 해독가능 기지 평문이 선택 평문보다 구하기 쉽지만 DES공격으로서의 선형 암호 해독은 가능성이 없다. 선형 암호 해독의 타당성 주장이 약하다.

3.6 블록 암호의 운용 모드

3.6.1 전자 코드북(ECB) 하나의 64비트 평문 단위로 처리 마지막 비트가 64비트 미만이면 나머지 비트를 채운 후 진행 각 64비트 평문에 대응하는 64비트 암호문 코드 북 유사 마지막 비트가 64비트 미만이면 나머지 비트를 채운 후 진행 동일한 블록이 입력되면 암호문도 동일 안전성 저해 요소 메시지가 긴 경우는 동일한 블록이 출현할 확률 증가 메시지가 항상 정규화 된 어떤 필드로 시작되는 경우는 해독위험

ECB (Electronic Codebook) 모드

3.6.2 암호 블록 연결(CBC) 선행 단계의 암호문 출력이 다음 암호단계의 입력에 XOR 반영됨 동일한 평문 블록이 입력되어도 상이한 암호문 생성효과 암호문: Cn = Ek (C n-1  Pn ) 복호화: Dk (Cn) = Dk [ Ek (C n-1  Pn ) ] = (C n-1  Pn ) Pn = C n-1  Dk (Cn) = C n-1  (C n-1  Pn ) = Pn 첫번째 암호화에 적용할 IV 값은 송수신자가 미리 인지 필요 IV는 키와 동등하게 보호 시작에 ECB 방식으로 암호화하여 전송가능 기밀성 외에 인증목적으로 활용가능 전송상에서 암호문의 결함은 복호화 과정에 오류 발생

CBC (Cipher Block Chaining) 모드

3.6.3 암호 피드백(CFB) DES는 본질적으로 블록 암호 방식 CFB 또는 OFB모드를 사용하여 스트림 암호방식 전환가능 스트림 암호방식은 블록이 64비트 정수배가 되도록 패딩 불필요 CFB는 문자지향 스트림 암호화 형식으로 실시간 작동가능 8-비트 문자 전송경우 8비트 단위로 암호화 전송 암호화 과정(전송단위를 j비트로 가정, 일반적으로 8) 첫번째 암호과정 입력: IV로 초기화된 64비트 이동 레지스터 키를 적용하여 64비트 전체 암호화 좌측 j 비트를 평문의 첫 단위 P1 과 XOR 한 결과가 암호문 C1 암호문 C1 은 다음 단계의 암호화를 위하여 레지스터의 우측에 J비트 입력 전송중의 비트 오류가 전체적으로 전파

J비트 암호 피드백CFB) 모드

3.6.4 출력 피드백(OFB) 전송중의 비트 오류는 해당 암호단위 하나에 제한 CFB보다 메시지 스트림 변조공격에 취약 암호문의 연계성 부족원인 암호문 변조와 오류 검출부를 동시 조작가능(VOYD83) 키 스트림: 주기성이 있음 Feedback의 출발 위치를 제외하고는 CFB와 유사

J비트 출력 피드백(OFB)모드

4.1 3중 DES DES의 brute-force공격에 대한 취약성 보완 필요 새로운 알고리즘 개발 본 장에서 소개될 대칭블록 암호 알고리즘 본 책에서 포함한 기존의 새로운 알고리즘 선택 기준 상당한 암호학적 강도 유지 인터넷 기반 널리 응용 DES 출현이후 개발된 현대 대칭블록 암호기술의 사용 차세대 암호 알고리즘 표준의 공모 AES: Rijndael 채택 기존의 소프트웨어와 장비투자를 보전하기 위해 DES에 다중 키 사용 2중 DES , 3중 DES

4.1.1 2중 DES(EE2, DD2) 2개의 암호화 단계와 2개의 키 사용 E K1 K2 P C X D 암호화 C = EK2[EK1[P]] 복호화 P = DK1[DK2[C]] E K1 K2 P C X D

암호화 강도 56 비트 x 2개의 키 = 112 비트 길이의 키 키 K3존재에 대한 가정 단일 단계로 축소: EK2[EK1[P]] = EK3[P] 중간결과에 의한 공격([DIFI77]에 소개) Meet-in-the-middle Attack DES의 특성 때문이 아니고, 블록 암호화에 대한 공격 중간결과 : if C = EK2[EK1[P]], X = EK1[P] = DK2[C] 기지 평문-암호문 쌍(P, C)에 대한 공격 성공 확률: 256 (단일 DES: 255)

4.1.2 2키에 의한 3중 DES (EDE2, DED2) E D K1 K2 P C B A 중간결과에 대한 공격 대책: 3단계 암호화 [TUCH79] : 2키 3중 암호 방법 제안 암호화 C = EK1[DK2[EK1[P]]] 복호화 P = DK1[EK2[DK1[C]]] E D K1 K2 P C B A

일반 DES에 대안으로 3중 DES 선택: ANS X9.17, ISO 8732 채택 [COPP94]: brute-force 공격: 2112  5 * 1033 3중 DES의 공격유형 Merkle과 Hellman[MERK 81]제안 방식 A = 0의 첫 번째 중간 값(그림 4.1b)을 생성하는 평문 값을 찾은 다음, 2개의 키를 찾기 위해 중간 결과에 의한 공격을 사용 암호해독의 복잡도는 256 현실적으로 256개의 선택 평문-암호문 쌍을 찾는 것은 어려움(선택 평문 공격)

기지 평문 공격은 [OORS 90]에 소개 선택 평문 공격을 개선한 방법이긴 하지만 복잡도는 더 높다 이 공격은 A와 C(그림 4.1b참조)를 알면 문제가 2중 DES에 대한 공격으로 축소 공격자는 2키를 알지 못하는 한 P와 C를 알지라도 A를 알지 못한다 그러나 공격자는 A의 가능한 값을 선택하고, A를 생성하는 기지의 (P, C) 쌍을 탐색 (그림 4.2b참조)

그림 4.2 3중 DES 에 대한 기지평문 공격

4.1.3 3키에 의한 3중 DES (EDE3, DED3) E D K1 K2 K3 P C B A 대안으로 [KALI96]: 3키 3중 DES을 제안 56 x 3 =168비트 길이의 긴 키를 사용하는 단점 C = EK3[DK2[EK1[P]]] P = DK1[EK2[DK3[C]]] PGP, S/MIME, 인터넷 응용에서 사용 E D K1 K2 K3 P C B A

4.2 IDEA(International Data Encryption Alg.) Xuejia Lai, James Massey(스위스 연방 기술연구소) 초기버전 [LAI90], 차분암호공격에 대응 보완 [LAI91, 92]에 기술 DES를 대체하기 위한 관용알고리즘 중의 하나 가장 성공적인 DES의 대체 알고리즘 대부분의 암호 공격으로부터 안전 널리 사용됨 (PGP에 포함) 설계 원리 및 목표 블록암호 : 64비트 블록 / 128 비트 키 강한 강도 쉬운 구현

4.2.1 설계 원리 IDEA의 암호학적 강도 블록 길이 : 64비트 (통계적 분석 방지 가능) 4.2.1 설계 원리 IDEA의 암호학적 강도 블록 길이 : 64비트 (통계적 분석 방지 가능) 키 길이 : 128비트 (전사적 공격에 안전) Confusion (혼돈) 암호문의 통계적 성질과 평문의 통계적 성질의 관계를 난해하게 만드는 성질 IDEA는 세가지 다른 종류의 연산을 사용하여 confusion을 달성 DES에서는 이러한 성질을 XOR 연산과 비선형 s-box에 의존 Diffusion(확산) 각각의 평문 비트와 키 비트는 모든 암호문 비트에 영향을 주어야 한다. 이것은 평문의 통계적 구조를 감출 수 있다. IDEA는 효율적인 확산을 지원한다.

IDEA의 Confusion / Diffusion XOR :  216(mod 65535) 상에서의 덧셈 : 216(mod 65535) 상에서의 곱셈 :  XOR에만 의존하는 DES 보다 암호해독이 어려움 Diffusion 곱셈/덧셈(MA) 구조에 의해 제공 입력 : 평문에서 유추된 두개의 16비트와 키에서 유추된 두개의 16비트 서브키 출력 : 두개의 16비트 결과 효율적인 확산을 위해 8번 반복

그림 4.3 IDEA의 곱셈/덧셈(MA) 구조 F1 F2 Z5 Z6 G1 G2

구현상의 고려사항 소프트웨어와 하드웨어 구현 가능 소프트웨어 구현 설계원칙 하드웨어 구현 설계원칙 소프트웨어: 유연성과 저렴한 비용 장점 하드웨어: VLSI를 통한 고속 실행 소프트웨어 구현 설계원칙 8, 16, 32비트 단위의 서브블록 암호연산 가능 암호연산은 덧셈, 자리이동 등을 사용하여 쉽게 프로그램 가능 하드웨어 구현 설계원칙 키를 적용하여 암호화와 복호화에 동일한 장치를 사용 VLSI 구현의 용이성을 위하여 정규적 2개 기본 모듈 빌딩블록으로 구성

4.2.2 IDEA의 암호화 입력: 64비트 평문(64-bit plaintext X) 서브키 생성기로부터 128비트 키 사용(Z1, .., Z52) 출력: 64비트 암호문(Y1, Y2, Y3, Y4 64-bit ciphertext Y) 8라운드 처리(Round 1, …, Round 8) 입력을 4개의 16비트 서브블럭으로 분해(X1, X2, X3, X4) 각 라운드는 4개의 서브 블록을 입력으로 받고, 4개의 16비트 결과물을 생성(W11, W12, W13, W14) 52개의 서브키 생성 초기 128비트 키 Z로부터 16비트 서브키 52개 생성하여 사용

암호화 과정 평문 64비트 블록을 4개의 16비트 서브블록으로 분할입력(x1, x2, x3, x4) 각 라운드에서 6개의 16비트 키를 적용 (z1, z2, … , z6) 8단계 각 라운드에서 6개 16비트 키의 적용 변환 과정 서브 암호화 과정 MA : 곱셈과 덧셈 출력 변환에서 8단계 출력과 4개의 키 적용 (z49, z50, z51, z52) 출력변환의 결과가 64비트 암호문 (y1, y2, y3, y4)

그림4.4 IDEA의 전체 구조

그림 4.5 IDEA 단일 반복과정 4개의 서브키(Z1 ~ Z4) 4개의 입력 블록(X1~X4) 덧셈, 곱셈연산을 이용해서 키와 입력 블록을 조합(변환과정) 조합된 결과를 XOR MA빌딩블록은 확산성질의 효과를 증대(서브 암호화 과정) 두번째와 세번째의 결과 교환(혼돈성질의 증가 및 차분해독에 견딜 수 있는 성질)

그림 4.6 IDEA의 출력 변환단계 그림 4.4에서 9번째 단계의 출력변환 8라운드의 MA과정 결과에서 2번쨰와 3번째 블록의 교환을 환원하는 효과 8라운드의 끝 부분에서 교환을 하지 않은 것과 동일 암호화/복호화가 동일한 구조를 가지기 위함 4개의 서브키 사용

그림 4.7 IDEA 서브키 생성 처음 8개의 서브키는 키로부터 직접 획득 다음부터는 25비트 왼쪽 순환 이동시켜 8개의 서브키 획득

그림 4.8 IDEA 암/복호화

IDEA의 동작 모드 DES와 유사한 4가지 동작 모드 ECB CBC CFB OFB(Output feedback) 64비트의 각 평문 블록이 독립적으로 암호화 작은 블록의 데이터 암호화에 유용 CBC 평문의 다음 64비트와 암호문의 이전 64비트에 대한 XOR 같은 64비트 평문이라도 매번 다른 암호문 생성 CFB 입력은 한번에 J 비트로 처리 J비트 암호문이 다음 암호화에 입력 OFB(Output feedback) 평문과 XOR 되기 이전의 IDEA 출력이 다음 암호화에 입력 잡음이 있는 채널에서의 스트링 전송에 유효

4.3 Blowfish [SCHN93,94] : Bruce Shneier에 의해 개발 특징 빠른속도 : 32비트 마이크로 프로세스에서 1byte당 18클럭 소요 간결성 : 5K 이내의 메모리에서 실행 가능 단순성 : 간단한 구조, 구현 용이, 알고리즘 강도 결정 용이 보안의 가변성 : 키 길이 가변, 32 - 448비트까지 가능, 속도와 보안성 고려 64비트 블록 암호 알고리즘 256개의 32비트 엔트리를 갖는 4개의 S-Box 사용 (S1,0 – S4,255) 최종적인 S-Box 와 서브키 배열 P를 생성하기 위해 알고리즘을 521회 실행 비밀키가 자주 바뀌는 응용에는 부적합 빠른 실행을 위해 서브키 배열 P와 S-Box 배열 S를 저장 메모리 용량이 제한된 스마트카드 등의 응용에는 부적합

암호화 / 복호화

Blowfish 암호화 64비트 평문을 32비트씩 분할(LE0, RE0) 16개 라운드별 저장된 서브키 32비트를 각각 적용(P1, P2, … ,P16) 16번째 라운드 결과에 서브키 P18, P17를 적용한 결과가 암호문

4.3.1 서브키 P 배열과 S박스의 생성 키의 생성 (32비트 키 1개부터 14개까지 가능) K1, K2, … , Kj 1<= j <= 14 서브키는 P 배열에 저장(18개의 32비트) P1, P2, … , P18 256개의 32비트 엔트리를 갖는 4개의 S박스(1024개의 32비트 값 = 4168바이트) S박스1 : S1,0, S1,1, … , S1,255 S박스2 : S2,0, S2,1, … , S2,255 S박스3 : S3,0, S3,1, … , S3,255 S박스4 : S4,0, S4,1, … , S4,255

P배열과 S박스 생성 1. 상수  의 소수부 비트를 이용하여 초기화 P1 = 243F6A88 :  의 소수부 왼쪽부터 첫번째 32비트(16진수) P2 = 85A308D3 : 2번째 32비트 …… S4,254 = 578FDFE3 S4,255 = 3AC372E6 2. 필요시 k배열의 워드를 재사용하여 18개의 P배열 생성 P1 = P1  K1 P2 = P2  K2 … … P14 = P14  K14 P15 = P15  K1 P18 = P18  K4

3. P배열과 S배열을 사용하여 0의 값을 갖는 초기 평문 64비트 블록을 Blowfish 암호화(P1, P2 생성) 4. P1, P2을 입력으로 암호화하여 P3, P4 생성 5. 다음과 같이 계속 진행( 521회 암호화 수행: P배열: 9회, S박스: 512회) P1, P2 = Ep, s[0] P3, P4 = Ep, s[P1  P2] … … … P17, P18 = Ep, s[P15  P16] S1, 0, S1, 1 = Ep, s[P17  P18] S4, 254, S4, 255 = Ep, s[S4, 252  S4, 253]

8비트로 256개 32비트 엔트리 중에 하나 선택 상세 단일 과정 ( F 함수 )

4.3.2 논의사항 Blowfish는 서브키와 S박스 생성을 위하여 자신의 암호과정 적용 4.3.2 논의사항 Blowfish는 서브키와 S박스 생성을 위하여 자신의 암호과정 적용 비트열이 토막으로 잘려 해독을 난해하게 하는 효과 데이터의 양쪽 모두에 대하여 연산 수행 암호학적 강도를 더욱 강화 실행 속도가 매우 빠름 [SCHN93] 설계상의 논의사항 서브키 생성처리에 소요되는 시간 때문에 본래의 키 길이에 대한 전사적 공격보다 난해 함수 F는 우수한 쇄도효과를 일으키는 결과

펜티엄 컴퓨터상의 블록 암호 속도 비교

4.4 RC5 [RIVE94,95]: Ron Rivest에 의해 개발된 대칭 암호 알고리즘 RSA데이터 보안회사의 BSAFE, JSAFE, S/MAIL등의 제품에 채용 특징 하드웨어 및 소프트웨어에의 적합성 마이크로프로세서에서 일반적으로 사용되는 기본 연산만 사용 빠른 속도 간단한 알고리즘을 사용하며, 단어 지향적 (기본 연산은 한번에 데이터 단어 전체를 처리) 다른 단어 길이 프로세서에서의 적응성 단어 당 비트 수는 매개변수이며, 다른 단어 길이는 다른 알고리즘이 됨

반복수의 가변성 가변길이의 키 단순성 낮은 메모리 요구량 높은 보안성 데이터 의존적인 순환이동 반복 수는 RC5의 두 번째 매개변수, 빠른 속도와 높은 보안 사이 선택 가변길이의 키 키 길이는 RC5의 세 번째 매개변수, 빠른 속도와 높은 보안 사이 선택 단순성 간단한 구조로 구현이 용이, 알고리즘 강도 결정(보안 허점 탐지)이 용이 낮은 메모리 요구량 스마트 카드나 한정된 메모리를 사용하는 장치에 적당 높은 보안성 적당한 매개변수로 높은 보안성을 제공하도록 설계 데이터 의존적인 순환이동 데이터의 양에 따라 결정되는 회전이동을 채용, 알고리즘 강도에 기여

4.4.1 RC5 매개변수 특정 버전: RC5-w/r/b 예: RC5-32/12/16 32비트 단어(64비트 블록 처리) 32비트 단어(64비트 블록 처리) 12회 반복의 암호 및 복호 처리 16 바이트 키(128비트)

4.4.2 키 확장 t 개의 서브키(w비트 단위) 배열 S의 초기화(initialize) 4.4.2 키 확장 t 개의 서브키(w비트 단위) 각 라운드별 2개의 서브키+ 별도 연산적용 2개 (t=2r+2); S[0], S[1], … S[t-1] 배열 S의 초기화(initialize) S[0]=Pw; for I=1 to t-1 do S[I]=Si-1 + Qw; r,w 입력한 고정 의사난수 비트패턴 최종배열 S 생성(convert/mix) ‘b’ byte 키 K[0], …K[b-1]은 ‘c’ word 배열 L[0], …L[c-1]로 변환 (byte  word) L의 내용을 S의 초기화된 값에 적용하는 혼합(Mix)연산 수행(S[0]~S[2r+1])

4.4.3 암호화 기본 연산 평문 2워드를 w비트 레지스터 A와 B에 각각 저장 4.4.3 암호화 기본 연산 평문 2워드를 w비트 레지스터 A와 B에 각각 저장 각 r 반복과정에서 좌우 양쪽 단어의 치환, 순열, 키 의존치환 처리 양쪽 단어는 각 반복시 마다 갱신 DES의 2회 반복 과정이 RC5 1회 해당 덧셈 : + 로 표시, 2w를 법으로한 덧셈 뺄셈 : - 로 표시, 2w를 법으로한 뺄셈 비트 XOR 연산 : 로 표시 좌측순환이동 : 단어 x의 y비트 좌측 순환이동은 x <<< y 로 표시 우측 순환이동 : 단어 x의 y비트 우측 순환이동은 x >>> y 로 표시

암호화 및 복호화

4.4.5 RC5 모드 RC5 블록 암호 모드 : 고정크기 입력블록(2w 비트)를 취하여 키에 의한 변환을 이용한 같은 크기 암호 블록 생성, RC5 ECB 모드 (그림 3.11 운영모드 참조) RC5-CBC 모드 : RC5 CBC 모드 (그림 3.12 참조) RC5-CBC-Pad 모드 : CBC 유형의 알고리즘, 채워지는 바이트 값은 “채움 바이트 수”로 모두 같다. RC5-CTS (Cipher Text Stealing) 모드 : CBC 유형의 알고리즘, 임의 길이 평문을 입력받아 같은 길이의 암호문 생성

4.5 CAST-128 [Adam97a]: Carlisle Adams와 Stafford Tavares에 의해 개발 [Adam97b]: RFC2144에 알고리즘 정의 40~128비트 사이에 8비트씩 증가하는 다양한 크기의 키 사용 16 라운드, 64비트 평문 블록, 64비트 암호문 블록 처리구조 Feistel 구조(그림3.5)와 차이점 각 반복과정에 두개의 서브키 사용 : 32비트 Kmi 와 5비트 Kri 함수 F는 반복과정에 따라 변함, 암호해독의 어려움 증대

기본 연산  덧셈 : + 로 표시, 2w를 법으로한 덧셈 뺄셈 : - 로 표시, 2w를 법으로한 뺄셈 비트 XOR 연산 : 로 표시 좌측 순환 이동 : 단어 x의 y비트 좌측 순환이동은 x <<< y 로 표시 

4.5.1 CAST-128 암호화 두개의 32비트 L0와 R0로 분리 L0  R0 = Plaintext 16회 반복 Li = Ri-1 Ri = Li-1  Fi [Ri-1, Kmi, Kri]; 암호문은 16라운드 출력: R16  L16 F는 (4개의 8*32 S 박스), (왼쪽 순환이동), (3개 그룹의 반복별 함수)로 구성

4.5.2 치환 S 박스 8개의 8*32 S박스 사용 S 박스 1~4: 암복호화에 사용 S 박스 5~8: 서브키 생성에 사용 8비트 입력은 행을 지정하고, 그 행의 32비트 값을 출력

단일 반복 과정(F함수) 반복 1,4,7,10,13,16 반복 2,5,8,11,14 반복 3,6,9,12,15 (159쪽 표 참조)

4.5.4 논의사항 고정된 S박스 사용: 우수한 쇄도효과를 갖도록 비선형적 선택 4.5.4 논의사항 고정된 S박스 사용: 우수한 쇄도효과를 갖도록 비선형적 선택 공격에 저항력 있는 서브키 생성: 비선형적인 S 박스를 이용 F함수는 혼돈, 확산, 쇄도 특성을 갖도록 설계 F함수는 반복에 따라서 다르게 적용

4.6 RC2 [RIVE97]: Ron Rivest에 의해 개발 64비트 평문 블록, 64비트 암호문 블록, 8~1024비트의 키 사용구조 16비트 마이크로 프로세서에서의 실행을 고려 40, 60, 128비트 키 구조를 S/MIME에서 사용 혼합 연산자 사용: 덧셈, XOR, 보수, AND, 왼쪽 순환이동 혼합(mixing round)과 매쉬(mashing round) 두 가지 유형의 총 18회 반복수행 고전적인 Feistel 구조를 사용하지 않음 다른 알고리즘과 비교 어려움.

개선된 대칭 블록 암호의 특징 가변 키 길이 혼합연산자 데이터 의존 회전 이동 키 의존 회전 이동 Blowfish, RC5, CAST-128, RC2 혼합연산자 산술 및 부울 연산자 중 하나 이상 사용, 비 선형성 제공 Triple-DES를 제외한 4장에서 소개된 모든 알고리즘 데이터 의존 회전 이동 회전이동은 서브 키에 의존하지 않고, 움직이는 데이터 블록에 의존 RC5 키 의존 회전 이동 CAST-128

키 의존 S-Box 긴 키 스케줄 알고리즘 가변적 F 함수 가변적 평문/암호문 블록 길이 S-Box의 내용이 키에 의존, 상이한 키는 상이한 S-Box 생성 높은 비선형성 제공, Blowfish에서 채택 긴 키 스케줄 알고리즘 서브키 생성이 단일 암호화 또는 복호화 보다 더 오래 걸림 전사적 공격에 강함, Blowfish에서 채택 가변적 F 함수 반복과정에 따라 변하는 F함수 , CAST-128에서 채택 가변적 평문/암호문 블록 길이 편의성 제공 ( 알고리즘 응용에 맞출 수 있음), RC5에서 채택

가변적 반복 횟수 매 반복 시 양쪽 데이터 절반의 연산 보안성과 실행속도와의 관계 조정 가능, RC5 최소한의 연산 시간 증가로 높은 보안성 획득 IDEA, Blowfish, RC5

주요 대칭 블록암호의 특징