해쉬 알고리즘.

Slides:



Advertisements
Similar presentations
10-7 부동소수점 (Floating-Point) 계산  컴퓨터에서 숫자를 표기하는 방법  가수 (Fraction) : 부호화된 고정소수점 숫자 지수 (Exponent) : 소수점의 위치를 표시 ( 예 )10 진수 를 표기하면 Fraction Exponent.
Advertisements

최성락 최인석 나주한. 특징 : 공개키 n, g 를 사용하여 키 분배가 가능. (g 는 Zn 의 primitive element) Discrete logarithm 에 기반. 두 명 이상의 경우에도 적용가능. 키 교환 없이도.
6 장. printf 와 scanf 함수에 대한 고찰 printf 함수 이야기 printf 는 문자열을 출력하는 함수이다. – 예제 printf1.c 참조 printf 는 특수 문자 출력이 가능하다. 특수 문자의 미 \a 경고음 소리 발생 \b 백스페이스 (backspace)
1 Chap 7. 암호 알고리즘. 2 목 차목 차 1. MD5 메시지 다이제스트 알고리즘 2. 안전한 해쉬 알고리즘 3. 국제 데이터 암호 알고리즘 (IDEA) 4. SKIPJACK 5. LUC 공개키 암호.
I. 프로젝트 동기 II. 프로젝트 목표 III. 파일시스템 IV. 암호화 및 복호화 V. 인터페이스 VI. FBR READ/WRITE VII. 프로그램 흐름도 VIII. 미 구현 사항 IX. 프로젝트 기대효과 X. 프로그램 요구사항 및 팀원 역할분담 XI. 시연 XII.
Format String Attack! 포맷 스트링 공격 경일대학교 사이버보안학과 학년 남주호.
컴퓨터와 인터넷.
SQL Injection Member 최병희, 김상우, 조용준, 유창열.
제 8장 메시지 인증 코드 메시지가 보낸 그대로 왔는가?.
인공지능실험실 석사 2학기 이희재 TCP/IP Socket Programming… 제 11장 프로세스간 통신 인공지능실험실 석사 2학기 이희재
9장. C 언어의 핵심! 함수. 9장. C 언어의 핵심! 함수 9-1 함수의 정의와 선언 main 함수 다시 보기 : 함수의 기본 형태 { } 그림 9-1.
I부 암호.
Chapter 3 Symmetric Key Crypto
연결리스트(linked list).
제 9 장 구조체와 공용체.
제12장 해쉬 알고리즘 12.1 MD Seure Hash Algorithm (SHA) 12.3 RIPEMD-160
컴퓨터 프로그래밍 기초 [Final] 기말고사
1. 정보보호 개론(2).
제13장 전자서명과 인증 프로토콜 Digital Signatures and Authentication Protocols
윤성우의 열혈 C 프로그래밍 윤성우 저 열혈강의 C 프로그래밍 개정판 Chapter 12. 포인터의 이해.
File Depender 중간 발표.
공개키 암호화 프로그래밍 전자상거래보안.
CHAPTER 02 OpenCV 개요 PART 01 영상 처리 개요 및 OpenCV 소개.
제10장 메시지 인증과 해쉬 함수 Message Authentication and Hash Functions
11장. 포인터 01_ 포인터의 기본 02_ 포인터와 Const.
SqlParameter 클래스 선문 비트 18기 발표자 : 박성한.
Error Detection and Correction
멀티미디어 시스템 (아날로그 이미지,신호를 디지털로 변환 방법) 이름 : 김대진 학번 :
9장. 디지털 증거의 무결성 유지.
Chap 4. 공개키 암호.
10 장 데이터 링크 제어(Data Link Control)
11장. 1차원 배열.
Method & library.
JA A V W. 03.
프로그래밍 개요
웹어플리케이션보안 암호프로그래밍, crypto-js
Java의 정석 제 5 장 배 열 Java 정석 남궁성 강의 의
자바스크립트 암호 프로그래밍 Javascript Cryptography Programming
제11장 해쉬 알고리즘 The Hash Algorithm
HTTP 프로토콜의 요청과 응답 동작을 이해한다. 서블릿 및 JSP 를 알아보고 역할을 이해한다.
전자서명의 형태 수기서명 디지털서명. 전자서명의 형태 수기서명 디지털서명 전자서명의 필요성.
Term Projects 다음에 주어진 2개중에서 한 개를 선택하여 문제를 해결하시오. 기한: 중간 보고서: 5/30 (5)
Chapter6 : JVM과 메모리 6.1 JVM의 구조와 메모리 모델 6.2 프로그램 실행과 메모리 6.3 객체생성과 메모리
연산자 (Operator).
USN(Ubiquitous Sensor Network)
(c) Byoungcheon Lee, Joongbu Univ.
아두이노 매트릭스 코딩 매트릭스 기본 명령어 실습 01차시 ㈜헬로앱스 김영준.
16 장 네트워크 보안 : 방화벽과 VPN 16.1 개요 16.2 기밀성 16.3 전자 서명 16.4 인터넷 보안
1. 2진 시스템.
10 장 데이터 링크 제어(Data Link Control)
10 장 데이터 링크 제어(Data Link Control)
컴퓨터 계측 및 실습 디지털 출력 영남대학교 기계공학부.
계산기.
VHDL를 이용한 DES 설계 정보통신컴퓨터공학부 5조 김인옥, 백미숙
SSL, Secure Socket Layer
Canary value 스택 가드(Stack Guard).
에어 PHP 입문.
4장. 데이터 표현 방식의 이해. 4장. 데이터 표현 방식의 이해 4-1 컴퓨터의 데이터 표현 진법에 대한 이해 n 진수 표현 방식 : n개의 문자를 이용해서 데이터를 표현 그림 4-1.
오라클 11g 보안.
논리회로 설계 및 실험 4주차.
9 장 오류 검출 및 오류 정정 9.1 오류 종류 9.2 검출 9.3 오류 정정 9.4 요약.
시리얼 UART 정리 정보통신•컴퓨터 공학부 송명규
9 브라우저 객체 모델.
(c) Byoungcheon Lee, Joongbu Univ.
제 4 장 Record.
 6장. SQL 쿼리.
버스와 메모리 전송 버스 시스템 레지스터와 레지스터들 사이의 정보 전송을 위한 경로
7 생성자 함수.
6 객체.
ARP.
Presentation transcript:

해쉬 알고리즘

해쉬 함수의 구성 원리 MD5 메시지 다이제스트 알고리즘 안전한 해쉬 알고리즘(SHA-1) RIPEMD-160 HMAC

해쉬함수의 구성원리 CV0 = IV = 초기 n 비트 값 CVi = f(CVi-1, Yi-1) 1 ≤ i ≤ L H(M) = CVL 해쉬 함수의 입력값은 Y0, ..., YL-1 블록들로 구성된 메시지 M

1. MD5 메시지 다이제스트 알고리즘 MIT의 Ron Rivest에 의해 개발됨 RFC1321 MD5 로직 입력 : 임의의 길이의 메시지 출력 : 128비트 메시지 다이제스트 입력처리 : 512비트 블록단위로 처리 5단계로 구성

L*512 bits = N * 32 bits K bits Message 512 512 512 512 Y0 Y1 Yq YL-1 Mess. Length (K mod 2^64) Padding (1 to 512 bits) L*512 bits = N * 32 bits K bits Message 100…0 512 512 512 512 Y0 Y1 Yq YL-1 512 512 512 512 HMD5 HMD5 HMD5 HMD5 128 IV 128 128 128 CV1 CVq CVL-1 Digest

단계1 : 패딩 비트의 부가 단계2 : 메시지 길이의 부가 단계3 : MD 버퍼의 초기화 하나의 ‘1’비트 뒤에 필요한 개수의 ‘0’ 비트들을 붙여서 구성 단계2 : 메시지 길이의 부가 512비트의 정수배가 되도록 메시지 길이 구성 단계3 : MD 버퍼의 초기화 Little endian 형태로 4개의 레지스터에 1부터 값을 초기화 A=67452301 <= 워드 A : 01 23 45 67 (낮은 주소 바이트 위치에 있는 워드의 LSB 형태로 저장) 단계4 : 512 비트(16단어) 블록의 메시지 처리 4개의 라운드로 구성된 압축함수 모듈 통과

Yq CVq 128 32 A B C D 512 F, T[1…16], X[i] 16steps A B C D G, T[17…32], X[p2i] 16steps A B C D H, T[33…48], X[p3i] 16steps A B C D I, T[49…64], X[p4i] 16steps + + + + Addition is mod 2^32 CVq+1

단계5 : 출력 입력 : 128비트 버퍼 값 ABCD 각 라운드 : 사인함수로 구성되는 T[1..64]의 ¼ 사용 T의 i번째 요소는 2^32 * abs(sin(i))의 정수부분과 일치하는 값 i는 라디안 Abs(sin(i)) : 0과 1사이의 값 T의 각 요소는 32비트 정수 테이블은 사인함수 이용 네번째 라운드의 출력은 첫번째 라운드의 입력이었던 CVq와 더해져서 CVq+1생성 단계5 : 출력

CV = IV CVq+1 = SUM32(CVq, RFI[Yq,RFH[Yq,RFG[Yq,RFF[Yq,CVq]]]]) MD5의 과정요약 CV = IV CVq+1 = SUM32(CVq, RFI[Yq,RFH[Yq,RFG[Yq,RFF[Yq,CVq]]]]) MD = CVL IV : 3단계에서 정의된 ABCD 초기 버퍼값 Yq : 메시지의 q번째 512비트 블록 L : 메시지의 블록수 CVq : 메시지의 q번째 블록과 함께 처리되는 체인변수 RFx : 기약 논리 함수 x를 사용하는 라운드 함수 MD : 최종 메시지 다이제스트 값 SUM32 : 입력 쌍의 각 단어에 제각기 수행되는 법 2^32 덧셈

MD5 압축 함수 각 단계의 형식은 다음과 같다 a <- b + ((a + g(b,c,d) + X[k] + T[i]) <<< s) a,b,c,d : 버퍼의 4단어, 단계에 따라 상이한 순서로 되어있음 g : 기약함수 F,G,H,I 중의 하나 <<< s : s 비트에 의한 32비트 매개변수의 순환좌측쉬프트 X[k] : 메시지의 q번째 512비트 블록 중에서 k번째 32비트단어 T[i] : 매트릭스 T에서 i번째 32비트 단어 + : 법 2^32 덧셈

A B C D + g X[k] + T[i] + + A B C D 라운드 기약함수 g g(b,c,d) 1 F(b,c,d) (bc)(bc) 2 G(b,c,d) (bd)(cd) 3 H(b,c,d) bcd 4 I(b,c,d) c(bd) A B C D + g X[k] + T[i] + CLSs + A B C D

MD4 MD4는 MD5의 이전버전 MD4의 목적 Ron Rivest가 1990년 10월 개발 RFC 1320 안전성 : 해쉬코드에 대한 일반적인 요구사항 속도 : 빠른 시행에 적합 -> 32비트 구조로 연산 단순성과 간결성 : 프로그램과 표현이 단순 Little-endian구조의 선호

MD4 vs MD5 라운드 덧셈 논리함수 이전 단계와의 연결 MD4 : 16단계의 3라운드 MD5 : 16단계의 4라운드 MD5는 64단계의 각각에 다른 덧셈 상수 T[I]사용 논리함수 MD4 : 각라운드에 한번씩 3개의 기약 함수 사용 MD5 : 각 라운드에서 한번씩 4개의 기약 논리 함수 사용 이전 단계와의 연결 MD5 : 이전 단계의 결과의 데이터 이용 =>더 큰 쇄도효과

2. 안전한 해쉬 알고리즘(SHA) Secure Hash Algorithm NIST에서 개발 1993년 FIPS PUB 180 (Federal Information Processing Standard)로 공포 1995년 FIPS PUB 180-1 개정 버전 발행(SHA-1) SHA는 MD4 알고리즘에 기반을 두고 유사하게 설계

SHA-1 논리 최대 264비트 미만의 길이 메시지 입력 512비트의 블록 단위로 처리 160비트 메시지 다이제스트 출력 512비트 메시지 블록 단위, 160비트 해쉬코드, 체인변수를 갖고 MD5와 유사한 처리 과정을 수행 단계 1 : 패딩 비트의 부가 단계 2 : 메시지 길이의 부가 단계 3 : MD 버퍼의 초기화(big endian 형태 저장) A=67452301 <= 워드 A : 67 45 23 01

4개의 각 라운드는 f1, f2, f3, f4로 표현되는 4가지의 기약 논리함수 사용 80개의 덧셈 상수 사용(4가지의 숫자) 단계 4 : 1개의 블록(512비트-16워드) 처리 20단계의 4라운드 처리로 구성 4개의 각 라운드는 f1, f2, f3, f4로 표현되는 4가지의 기약 논리함수 사용 80개의 덧셈 상수 사용(4가지의 숫자) 0 <= t <= 19 Kt=5A827999 20 <= t <= 39 Kt=6ED9EBA1 40 <= t <= 59 Kt=8F1BBCDC 60 <= t <= 79 Kt=CA62C1D6 마지막 단계의 출력에 CVq를 더하여 CVq+1을 생성

SHA-1 압축함수 단계 5 : 출력 SHA-1의 전체 처리과정 A<-(E+f(t,B,C,D)+S5(A)+Wt) CV0 =IV CVq+1 = SUM32(CVq, ABCDEq) MD= CVL SHA-1 압축함수 A<-(E+f(t,B,C,D)+S5(A)+Wt) B<-A C<-S30(B) D<-C E<-D

SHA-1 처리 기본동작

80워드 입력 계열의 생성

SHA-1과 MD5의 차이점 특성 MD5 SHA-1 다이제스트 길이 처리의 기본단위 처리 단계수 최대 메시지 크기 기약 논리 함수 덧셈 상수 128비트 512비트 64(16*4) 무한대 4 64 160비트 80(20*4) 264

3. RIPEMD-160 유럽의 RIPE(RACE Integrity Primitives Evaluation)프로젝트의 일환으로 개발[DOBB96b, BOSS97] MD4, MD5에 대한 공격을 부분적으로 성공한 팀이 RIPEMD 128비트 버전 개발 RIPE일원이 아닌 H.Dobbertin이 RIPEMD, MD4, MD5의 허점 발견 RIPE 멤버와 H.Dobbertin 공동으로 RIPEMD 보완 개발 입출력 길이 입력 : 임의의 길이의 메시지를 512비트 블록 단위로 처리 출력 : 160비트

RIPEMD-160 논리 수행단계 단계 1 : 패딩비트 부가 메시지는 비트의 길이가 512를 법으로 하여 448과 합동이 되도록 패딩 패딩은 항상 부가, 패딩비트수 : 1-512비트, One-Zero-Leading방식 단계 2 : 메시지 길이 부가 원래 메시지의 길이 계산 64비트 블록에 길이 정보 부가, 부호없는 정수형 Little-Endian 구칙을 따름

단계 3 : MD 버퍼의 초기화 단계 4 : 512비트 블록 메시지 처리 160비트 버퍼는 해쉬의 중간결과와 최종 결과를 저장 5개의 32비트 레지스터(A,B,C,D,E) 각 레지스터들은 고정된 값으로 초기화 A=67452301(SHA-1에서 사용된 값과 동일) 단계 4 : 512비트 블록 메시지 처리 16단계로 되어 있는 10라운드의 처리 10라운드는 두개의 5라운드로 나뉘어 병렬처리 각 라운드는 각각의 f1,f2,f3,f4,f5 기약 논리함수 사용 각 라운드는 서로 다른 9가지(0의 값 포함)의 덧셈상수(K1)사용 좌,우 5번째 라운드에서 CVq+1을 생성하기 위해 모듈러 232덧셈수행 단계 5 : 출력 – 160비트 메시지 다이제스트 생성

단일 512비트 블록 처리

기본동작 메시지Xi (0<=i<=15) 상수 Ki rol10:10bit회전

MD5, SHA-1, RIPEMD-160비교

해쉬함수 성능비교 알고리즘 Mbps Md5 26 SHA-1 48 RIPEMD-160 31 850-MHz Celeron에서 C++ 코딩 경우 알고리즘 Mbps Md5 26 SHA-1 48 RIPEMD-160 31

4. HMAC(Hashed-MAC) 대칭 블록 암호에 기반한 MAC계산 FIPS PUB 113 (데이터인증) 암호 해쉬 함수가 대칭 블록 암호보다 빠름 암호 해쉬 함수에 대한 라이브러리 코드의 입수 용이 암호 해쉬 함수에 대한 수출 제한 없음 MD5와 같은 해쉬 함수는 비밀키에 의존하지 않음 => 비밀키를 기존의 해쉬 알고리즘에 결합 HMAC : RFC 2104, IP보안을 위한 MAC의무 구현사항 선정(SSL에서 사용)

HMAC 설계 목표 가용한 해쉬 함수를 변경 없이 사용 가능해야 함 해쉬 함수는 소프트웨어로 구현 가능, 무상입수 용이 내장 해쉬 함수 교체 용이(해쉬함수의 블랙 박스화) 성능 저하 없이 해쉬 함수의 원래 성능 계속 유지 간단한 방법으로 키 조작 인증 메커니즘의 암호학적 분석 이해가능

HMAC 구조 00110110을 b/8번 반복 01011010을 b/8번 반복

처리과정 b비트 스트링 K+ 생성 : 비밀키 K의 왼쪽에 0을 첨가 b비트 블록 Si를 생성 : K+ 와 ipad를 XOR M을 Si 에 추가 : Msg1=[Si||M] 3단계의 Msg1에 해쉬를 적용 b비트 블록 S0를 생성 : K+ 와 opad를 XOR 단계 4에서 만들어진 해쉬함수 적용결과에 S0를 추가 6단계의 결과에 해쉬함수를 다시 적용 HMACK(M)=H[(K+ XOR opad)||H(K+ XOR ipad)||M]]

HMAC의 안전성 공격 시나리오 : 공격자는 해쉬 알고리즘과 디폴트 IV를 알고 있음. 그러나 K(비밀키)를 모르기 떄문에 메시지와 코드의 짝을 생성할 수 없음. ->128비트 길이의 해쉬코드 공격을 위해서는 동일한 키로 생성된 264의 블록(273 bit)을 필요로 함 250,000년 동안 키의 변경없이 연속적인 메시지 스트림 조사 속도가 중요한 경우, 내장 해쉬함수로 SHA-1나 RIPEMD160 보다 MD5 사용이 바람직 함.

디지털 서명 & 인증 프로토콜

목 차 1. 디지털 서명 개요 2. 직접적 디지털 서명 3. 중재된 디지털 서명

암호학적 점검값의 기본 사용 예 K1 EK2[M || CK1(M)] M M C || E D 비교 C K2 K2 CK1(M)

1. 디지털 서명 적용 예 전자식 자금 전달의 경우 주식 매매 요청의 경우 디지털 서명 해결책 수신자 : 1. 전달된 자금의 양을 증가 2. 송신자로부터 해당 금액이 왔다고 주장 주식 매매 요청의 경우 송신자 : 1. 단말기를 통해 주식 매매 요청 2. 주식 값이 하락 3. 자신이 요청을 한 적이 없다고 주장 송신자와 수신자의 완벽한 신뢰가 없는 상황에서 인증 이상의 어떤 것이 필요 디지털 서명 해결책

1. 디지털 서명 배경 정의 목적 1) 종이 문서 사회에서 정보화 사회로의 진전으로 다양한 서비스 요구 1) 종이 문서 사회에서 정보화 사회로의 진전으로 다양한 서비스 요구 2) 데이타 무결성 및 사용자 인증 서비스가 필수적 정의 공개키 암호화를 사용하여 구현하며, 보낸 사람과 메시지를 연결하는 방법을 제공하고, 구매 시 사이버 스페이스에서 서명하는 것이다. 목적 신뢰성 확보 ( 내용의 위·변조 및 신분 확인에 사용)

디지털 서명 특징 손으로 쓴 서명과 유사 해당 서명의 저자, 날짜와 시간의 확인 가능 서명할 당시의 내용을 인증 가능 분쟁시 제 3자가 확인 가능

디지털 서명 특징 위조불가(Unforgeable) : 서명자만이 서명문 생성 가능 서명자 인증(Authentic) : 서명문의 서명자를 확인 가능 재사용 불가(Not reusable) : 서명문의 서명은 다른 문서의 서명으로 사용 불가능 변경 불가(Unalterable) : 서명된 문서의 내용 변경 불가능 부인 불가(Nonrepudiation) : 서명자는 후에 서명한 사실을 부인 불가능

디지털 서명 요구 조건 서명은 서명되는 메시지에 의존하는 비트 형태이어야 한다. 서명은 위조와 부인을 방지하기 위해서 송신자에 대한 유일한 어떤 정보를 이용해야만 한다. 디지털 서명을 만들기가 비교적 쉬워야 한다. 디지털 서명을 인식하고 확인하기가 쉬워야 한다. 기존의 디지털 서명에 대한 새로운 메시지를 구성하거나 또는 주어진 메시지에 대한 거짓 디지털 서명을 구성함으로써 디지털 서명을 위조하는 것이 계산적으로 실행 불가능해야 한다. 기억장소에 디지털 서명의 복사본을 유지하는 것이 실용적이어야 한다.

2. 직접적 디지털 서명 오직 통신하는 상대방(출신, 목적지)만을 포함 직접적 디지털 서명 방식 비밀성을 위해 송신자의 개인키를 가지고 전체 메시지를 암호화 송신자의 개인키를 가지고 메시지의 해쉬 코드를 암호화 비밀성을 위해 수신자의 공개키 또는 공유 비밀키를 가지고 서명된 메시지를 암호화

Authentication and signature 메시지 암호화의 기본 사용법 M E D KRa EKRa(M) Authentication and signature KUa

단점 구조의 정당성은 송신자의 개인키에 달려 있음 송신자가 개인키를 분실, 도난 당했다고 주장이 가능 실제로 개인키를 도난 당했을 경우의 대책 미흡 사례 공갈 협박에 의해 개인키를 노출하고 침묵 가능 => 신고 이전까지는 심각한 손상 초래 사고 발생시에 불리할 경우 도난 당했다고 거짓 주장 실제로 자신도 모르는 사이에 도난 당했을 경우 가능성 존재

3. 중재된 디지털 서명 기법 관용 암호 방식(1) 중재자에게 메시지 노출 Alice와 Carol 간에 비밀키 공유 : KCA Carol과 Bob 간에 비밀키 공유 : KCB 2. Verification Carol 1. M || EKCA[IDA || H(M)] 3.EKCB[IDA || M || EKCA[IDA || H(M) || T] Alice Bob

관용 암호 방식(1) Bob은 Alice의 서명을 직접 검사할 수 없음 서명은 분쟁 해결을 위해 존재 Alice와 Bob은 Carol에게 높은 신뢰를 가지고 있어야 함 Carol이 KCA를 노출 시키지 않는다. EKCA [IDA || H(M)] 형태의 거짓 서명을 만들지 않는다. Bob은 서명이 A에 의해서 만들어졌을 때만, carol이 EKCB [IDA || M || EKCA[IDA || H(M) || T]를 보낸다는 것을 신뢰

관용 암호 방식(2) 메시지 비밀 유지 Alice와 Bob이 비밀키를 공유 : KAB Carol Bob Alice 1. IDA || EKAB[M] || EKAC[IDA || H(EKAB[M])] 2. Verification 3.EKCB[IDA || EKAB[M] || EKAC[IDA || H(EKAB[M]), T] Alice Bob Carol

관용 암호 방식(2) 장점 단점 Carol은 메시지 내용을 읽을 수 없다. Carol은 Alice와 Bob의 부정을 막을 수 있다. 단점 Carol은 Alice와 함께 서명된 메시지를 부인할 수 있다. Carol은 Bob과 함께 Alice의 서명을 위조할 수 있다.

공개키 암호 방식 메시지 비밀 유지 관용 암호 방식에서 발생할 수 있는 문제점 해결 가능 Carol Bob Alice 1. IDA || EKRA[ IDA || EKUB(EKRA[M])] 2. Verification 3.EKRC[IDA || EKUB(EKRA[M])], T] Alice Bob Carol

공개키 암호 방식 장점 통신 전에 통신의 상대자간에 공유해야 할 정보가 없다. KRa가 노출되었다고 할지라도 KRC가 노출되지 않았으면 부정확한 날짜가 매겨진 메시지가 보내질 수 없다. Alice로부터 Bob에게 온 메시지의 내용은 Carol과 다른 모든 사람들에게 있어서 비밀이다.