2009년 3월 30일 (5주차) 유 승 석(aviteria@gmail.com) 상용 관용 암호 방식 2009년 3월 30일 (5주차) 유 승 석(aviteria@gmail.com)

수업 내용 DES DES의 규칙성 DES의 안전성 문제 SEED AES 운용 모드 Questions & Answers

DES

DES 개요 DEA(Data Encryption Algorithm) 대칭키 암호 시스템, 암호화/복호화 키가 동일 IBM의 홀스트 파이스텔에 의해 개발됨, 루시퍼(1975, IBM) 알고리즘의 변형 ATM(Auto Teller Machines), POS(Point of Sale) 단말장치의 PIN 암호화 및 데이터 내용 변조 방지를 위해 사용됨 PIN : Personal Identification Number

DES (Data Encryption Standard) 1차 1973년 NBS(현 NIST의 전신) 공개 모집 NBS(National Bureau of Standards, 미국규격표준국) 2차 1974년 NBS 공개 모집 IBM Tuchman, Meyer 응모 1977년 미연방 표준 암호 알고리즘으로 선정(FIPS PUB 46) 참고사이트 NIST : http://en.wikipedia.org/wiki/National_Institute_of_Standards_and_Technology

DES (계속) 공모 조건 높은 안전성 알고리즘 간단 안전성이 키에만 의존 응용이 다양 제작자 및 사용자 이용 가능 전자장치 간단 제작자의 알고리즘 타당성 검토 협력 수출 가능

DES의 특징 64비트 블록 단위로 암호화 56비트 키(Active Key) + 8비트 패리티체크(Parity Check) 비트 56 비트가 암호화 및 복호화에 사용된다. 16라운드의 치환(P-Box)과 대치(S-Box)를 사용 정보이론의 아버지 클로드 샤논이 제안했던 기술을 구현한 것 참고사이트 http://en.wikipedia.org/wiki/Claude_Shannon http://en.wikipedia.org/wiki/Data_Encryption_Standard

DES 암호화 진행 과정 Overview 1. 평문을 입력 64비트 2. 초기전치(재배열) 3. 좌우 분리 32비트씩 3. 좌우 분리 32비트씩 4. Feistel 연산 5. 원래의 키로부터 만들어 낸 키 6. 초기전치의 역전치(거꾸로) 7. 암호문 비트

DES 암호화 진행 과정 Overview

DES 암호화 과정 Overview - 초기전치 IP (initial permutation) 1) 평문을 64비트씩 자른다. 64비트 자른 평문을 이라고 하자. 평문 M은 초기치환 IP를 거쳐 으로 바뀐다. IP는 1번 자리에 58번째 비트를 놓고, 2번 자리에 50번째 비트를 놓고, 3번 자리에 42번째 비트를 놓는 방식으로 비트열의 자리를 바꾼다. 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

DES 암호화 과정 Overview - 16라운드의 함수계산(치환) 2) IP(M)은 좌우 각각 32비트씩 와 로 나누어 1라운드 암호화 과정에 들어간다. 와 를 가지고 다음 단계의 , 을 만든다. 이다. 3) 2라운드의 왼쪽 32비트 은 오른쪽 32비트 를 그대로 쓴다. 2라운드의 오른쪽 32비트 은 를 연산틀에 넣어서 처리한 다음 그 값과 을 XOR연산한다. 한 라운드를 넘기는 과정마다 암호키 열 이 차례대로 작용한다.

DES 암호화 과정 Overview -역전치IP–1(inverse of initial permutation) 역치환 40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25

DES의 f 함수 E : Expansion(확대전치E) XOR 연산 P-box(평형전치P) S-box 비트 확장표를 이용하여 32 비트를 48 비트로 확장 XOR 연산 키 스케줄러에서 생성된 라운드 별 Subkey와 XOR 연산 P-box(평형전치P) 선형전치표 S-box DES의 안전성에 중요한 역할 8 개의 비선형 함수로 구성됨 48 비트를 다시 32 비트로 변환

DES의 f 함수 확대전치 E

DES의 f 함수 평형전치 P

DES의 f 함수 S-Box

DES의 f 함수 S-Box 예

The Key-schedule of DES 키계열 생성 알고리즘 키 스케줄러라 불리움 Subkey 16 개 생성 K1, K2, K3, …, K16 과정 64비트 키 데이터 입력 선택치환 PC1 : Permuted Choice1 8bit 패리티 체크 비트 제거  56 bit 생성 28비트 씩 양분 라운드 별 지정된 수 만큼 좌측 시프트 PC2 : Permuted Choice2 48 비트의 라운드 키 생성됨 16라운드(회) 반복

The Key-schedule of DES 키 스케줄러에서 Subkey 16 개 생성( K1, K2, K3, …, K16 ) 64비트 키 데이터 입력 키전치 PC-1 Permuted Choice1 8bit 패리티 체크 비트 제거  56 bit 생성 28비트 씩 양분( C0, D0, … ) 라운드 별 지정된 수 만큼 좌측 시프트(LS1, LS2, …), 표4-8 축약전치 PC-2 PC2 : Permuted Choice2 48 비트의 라운드 키 생성됨 위의 과정들을 16라운드(회) 반복

The Key-schedule of DES 키전치 PC-1 8 16 24 32 40 48 56 64 제거

The Key-schedule of DES 축약전치 PC-2 9 18 22 25 35 43 54 제거

The Key-schedule of DES 키 스케쥴러 LS

DES 복호화 과정 암호문CIP역라운드IP–1평문M

DES 암호의 규칙성 보수 특성

취약 키 취약키로 평문을 암호화하고 다시 한 번 암호화하면 평문이 나타남 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 F E F E F E F E F E F E F E F E 1 F 1 F 1 F 1 F 0 E 0 E 0 E 0 E E 0 E 0 E 0 E 0 F 1 F 1 F 1 F 1

유사 취약 키 취약키와 상당히 비슷한 특성을 갖는 키 조합 0 1 F E 0 1 F E 0 1 F E 0 1 F E 1 F E 0 1 F E 0 0 E F 1 0 E F 1 E 0 1 F E 0 1 F F 1 0 E F 1 0 E 0 1 E 0 0 1 E 0 0 1 F 1 0 1 F 1 E 0 0 1 E 0 0 1 F 1 0 1 F 1 0 1 1 F F E 1 F F E 0 E F E 0 E F E F E 1 F F E 1 F F E 0 E F E 0 E 0 1 1 F 0 1 1 F 0 1 0 E 0 1 0 E 1 F 0 1 1 F 0 1 0 E 0 1 0 E 0 1 E 0 F E E 0 F E F 1 F E F 1 F E F E E 0 F E E 0 F E F 1 F E F 1 취약키와 상당히 비슷한 특성을 갖는 키 조합

DES의 안전성 문제 1975년 DES 알고리즘 발표 뒤 두가지 문제점이 제기됨 DES의 소모적 공격 키의 길이가 짧다 S-Box의 트랩도어나 의도적인 약점이 포함되어 있을 수 있다. DES의 소모적 공격 암호기에 평문을 입력시켜 모든 키를 차례로 사용하면서 원하는 암호문이 출력될 때 까지 반복 여러 개를 만들어 동시에 공격하면 시간 단축

DES의 안전성 문제 1998년 미국 RSA사에서 DES 해독 1997년 3-DES(Triple DES, 트리플 DES) 로 보완 DES를 사용하는 세 번의 암호화 2002년 AES(Advanced Encryption Standard)로 데체됨

DES (계속) 2중 DES 1비트 증가 효과

DES (계속) 3중 DES 강한 암호 가능 키의 길이가 2배 확대된 효과

참고자료 DES supplementary material details the various tables referenced in the Data Encryption Standard (DES) block cipher. http://en.wikipedia.org/wiki/DES_supplementary_material

SEED

SEED 개요 전자상거래, 금융, 무선통신 등에서 전송되는 개인정보와 같은 중요한 정보를 보호하기 위해 1999년 2월 한국정보보호진흥원과 국내 암호전문가들이 순수 국내기술로 개발 128비트 블록암호알고리즘 128비트 key 사용 1999년 9월 정보통신단체표준(TTA)으로 제정 2005년에는 국제 표준화 기구인 ISO/IEC 국제 블록암호알고리즘 표준으로 제정됨 참고사이트 http://www.kisa.or.kr/kisa/seed/jsp/seed_1010.jsp

SEED 암호화 과정

SEED의 f 함수 f 함수의 입력 값 64비트 REi  32비트 X, Y 로 분리 64비트 암호화 보조키 Ki+1  32비트 KK0, KK1 으로 분리

SEED의 G 함수 S-Box 치환 Bit-wise 연산 G함수의 입력 32비트를 4개의 8비트 블록 X3X2X1X0 으로 분할한 후 S-Box S2S1S2S1 에 입력 S2(X3), S1(X2), S2(X1), S1(X0) 를 출력함 Bit-wise 연산

SEED의 G 함수 & : bit-wise AND

SEED의 S–Box SEED의 안전성을 결정하는 중요한 요소 8비트가 입력, 8비트가 출력되는 치환과정 미분해독기법(differential cryptanalysis)및 선형해독기법(linear cryptanalysis) 특성이 가장 우수한 n=247, 251을 선택하여 전단사 함수 Xn 을 적용함 GF(28)을 이용  Z256 = { 0, 1, 2, … , 255 }

SEED의 S–Box

SEED의 S–Box S-Box

SEED – S1 Box 변환표

SEED – S2 Box 변환표

SEED – 보조키 생성 알고리즘 128비트의 키는 네 개의 32비트 블록으로 나누어져 키 생성 알고리즘에 입력됨(A,B,C,D)

SEED – 보조키 생성 알고리즘

SEED – 보조키 생성 알고리즘 키 생성 상수

SEED 참고자료 KISA SEED/ARIA 블록암호알고리즘 SEED 알고리즘 상세 명세서 SEED 개발 및 분석 보고서 http://www.kisa.or.kr/kisa/seed/jsp/seed_1010.jsp SEED 알고리즘 상세 명세서 http://www.kisa.or.kr/kisa/seed/down/SEED_Specification_korean.pdf SEED 개발 및 분석 보고서 http://www.kisa.or.kr/kisa/seed/down/SEED_Self_Evaluation-Korean.pdf

[참고] ARIA 블록암호알고리즘 ARIA는 경량 환경 및 하드웨어에서의 효율성 향상을 위해 개발된 블록 암호 알고리즘 블록 크기 : 128비트 키 크기 : 128/192/256비트 (AES와 동일 규격) 라운드 수 : 12/14/16 (키 크기에 따라 결정됨) ARIA가 사용하는 대부분의 연산은 XOR과 같은 단순한 바이트 단위 연산으로 구성됨 2004년에 국가표준기본법에 의거, 지식경제부에 의하여 국가표준(KS)으로 지정

[참고] ARIA 블록암호알고리즘 안정성과 효율성 ARIA 소스코드 국가정보원에서는 C와 JAVA로 작성된 ARIA 소스코드를 제공하고 있음 http://www.kecs.go.kr/pw_certified/aria_open.jsp

[참고] ARIA 블록암호알고리즘 참고사이트 KISA : http://www.kisa.or.kr/kisa/seed/jsp/seed_5010.jsp IT보안인증사무국http://www.kecs.go.kr/pw_certified/aria_open.jsp

Advanced Encryption Standard AES Advanced Encryption Standard

AES의 공모 DES에 대한 여러 공격 방법들의 발표로 인해 새로운 표준암호 알고리즘의 필요성 대두 56-bit DES key : exhaustive key search feasible 64-bit DES block (and Triple DES) : MAC(Message Authentication Code) weakness 미국의 NIST는 1998년 AES 알고리즘을 공모 Round 1(1998. 8 – 1999. 4) : CAST-256, CRYPTON, DEAL, DFC, E2, FROG, HPC, LOKI97, MAGENTA, MARS, RC6, Rijndael, SAFER+, Serpent, Twofish Round 2(1999. 8 – 2000. 5): MARS, RC6, Rijndael, Serpent, Twofish 2000년 10월 2일 AES 알고리즘 선정 발표 Rijndael (Submitted by Joan Daeman and Vincent Rijman) 2001년 11월 FIPS-197로 등록

AES의 특징 입력 평문의 길이는 128비트로 고정 사용하는 암호화 키의 길이는 128, 192, 256비트 중 하나를 선택할 수 있음 참고) Rijndel 알고리즘은 키의 길이와 입력 평문의 길이를 128, 192, 256 비트 중 선택 가능 지금까지 알려진 모든 공격법에 대해 안전하도록 설계됨 모든 플랫폼에서 속도와 code compactness 면에서 효율적 Design simplicity Suited for Smart cards

AES의 개요 평문을 128비트 단위로 나누어 암호화, 복호화를 수행 각각의 128비트를 4x4 행렬로 표현하여 연산을 수행함 Input / output : sequence of 128 bits(block) 각각의 128비트를 4x4 행렬로 표현하여 연산을 수행함 암호화 키 Cipher key : sequence of 128, 192, 256 bits

AES의 개요 State 4x4행렬로 표현 암호화, 복호화 과정의 중간 단계 결과물 (4, Nb)의 이차원 행렬로 표현

AES의 개요 AES의 기본 연산은 Byte 단위로 수행 각 바이트를 유한체 GF(28)위의 다항식으로 표현하여 연산을 수행한다.

AES의 덧셈(Addition) GF(28)에서의 두 원소의 덧셈은 각 계수를 (mod 2)상에서 더한 결과

AES의 곱셈(Multiplication) GF(28)에서의 곱셈은 mod 8차 기약다항식 상에서의 곱셈 기약 다항식(irreducible polynomial) : 1과 자기 자신만을 인수로 갖는 다항식 AES에서 사용하는 기약 다항식

[참고] 다항식의 연산 방법 http://math.kongju.ac.kr/mathcom/poly/poly1.htm

AES 암호화 과정

AES 암호화 과정 KeyExpansion using Rijndael's key schedule Initial Round AddRoundKey Rounds SubBytes : a non-linear substitution step where each byte is replaced with another according to a lookup table. ShiftRows : a transposition step where each row of the state is shifted cyclically a certain number of steps. MixColumns : a mixing operation which operates on the columns of the state, combining the four bytes in each column AddRoundKey : each byte of the state is combined with the round key; each round key is derived from the cipher key using a key schedule. Final Round (no MixColumns) SubBytes ShiftRows

The number of Rounds (Nr) 사용하는 암호화 키(Nk)의 길이에 따라 암호 및 복호화 과정에 필요한 라운드 수는 다르다.

AES의 암호화 과정

Round Transformation 4개의 다른 transformation으로 구성 ※ 마지막 라운드에는 MixColumn 단계가 없음

Pseudo Code for the AES cipher

SubBytes step ShiftRows step MixColumns step AddRoundKey step

SubByte( ) Transformation Non-linear byte substitution 바이트 단위로 invertible한 S-box에 적용 S-Box는 두 가지 변환으로 구성

SubByte( ) Transformation S[02], 02 = x

SubByte( ) Transformation

SubByte( ) Transformation

SubByte( ) Transformation Example

SubBytes step ShiftRows step MixColumns step AddRoundKey step

ShiftRow( ) Transformation(1/2) State의 각 행을 왼쪽으로 cyclic shift 0 행 : - 1 행 : 1 byte 2 행 : 2 byte 3 행 : 3 byte

ShiftRow() Transformation(2/2)

ShiftRow() Transformation Example

SubBytes step ShiftRows step MixColumns step AddRoundKey step

MixColumn() Transformation(1/2)

MixColumn() transformation(2/2)

MixColumn() transformation Example

SubBytes step ShiftRows step MixColumns step AddRoundKey step

AddRoundKey() Transformation 라운드 키는 각 state에 bitwise XOR로 적용 Cipher key로부터 키 스케줄러를 이용하여 라운드 키 생성 라운드 키의 길이 = 블록 길이 Nb

AddRoundKey() Transformation - Example

AES 복호화 과정

AES의 복호화 과정

Inverse Cipher

InvSubByte() Transformation(1/2)

InvSubByte() Transformation(2/2)

InvShiftRow() Transformation

InvMixColumn() Transformation MixColumn에서 사용한 a(x)의 inverse를 곱한다.

KeyExpansion using Rijndael's key schedule

Key Expansion

Psedo code for Key Expansion

Key Expansion

Key Expansion – Example(1/4)

Key Expansion – Example(2/4)

Key Expansion – Example(3/4)

Key Expansion – Example(4/4)

Cipher – Example(1/4)

Cipher – Example(2/4)

Cipher – Example(3/4)

Cipher – Example(4/4)

참고 Advanced Encryption Standard Rijndael S-box Rijndael key schedule http://en.wikipedia.org/wiki/Advanced_Encryption_Standard Rijndael S-box http://en.wikipedia.org/wiki/Rijndael_S-box Rijndael key schedule http://en.wikipedia.org/wiki/Rijndael_key_schedule

운용 모드

블록 암호 방식의 운용 모드 ECB (Electronic Codebook Mode) CBC (Cipher Block Chaining Mode) CFB (Cipher Feed Back Mode) OFB (Output Feed Back Mode)

ECB(Electronic Codebook) 모드 동일한 평문에 대해 동일한 암호문 출력 짧은 길이의 평문 암호화에 사용

CBC(Cipher Block Chaining) 모드

CBC(Cipher Block Chaining) 모드

CBC(Cipher Block Chaining) 모드

CFB(Cipher Feed Back) 모드

CFB(Cipher Feed Back) 모드

CFB(Cipher Feed Back) 모드 특징 동일한 평문 블록에 대해 동일한 암호문이 나 타나지 않도록 함 평문 블럭내에 한 비트 오류가 발생하면 모든 암호문에 영향을 미침 암호문 블럭내에 한 비트 오류가 발생하면 복 호화된 모든 평문에 영향을 미침

OFB(Output Feed Back) 모드

OFB(Output Feed Back) 모드

OFB(Output Feed Back) 모드 ECB 모드의 단점을 개선하고 CBC/CFB 모드의 오류 전파 특성을 제거한 방식 전송 중에 비트 손실이나 삽입에 유의해야 함

Questions & Answers