암호-5장. 해시함수 및 기타 ㅎㅎ 정보보호 기능의 가장 핵심적 기술인 암호를 다룬다. 흥미로운 암호의 역사를 소개하고, 고전적인 암호체계로부터 현대적인 디지털 암호체계에 이르는 기술의 발전을 살펴보고 현대의 고급 암호분석 기법을 소개한다. 한빛미디어(주)

학습목표 5장. 해시함수 및 기타 암호학적 해시함수와 TIGER 해시를 설명한다. HMAC, 스팸 방지등 해시함수의 용도를 알아본다. 샤미르의 비밀공유체계, 난수, 정보은닉 등 흥미로운 암호 관련 주제를 설명한다

해시함수 동기 Section 01 해시함수란 앨리스가 M에 서명한다고 가정 만약 M이 크면 [M]앨리스 을 계산 비용 큼 앨리스는 M과 S = [M]앨리스 를 밥에게 전송 밥은 M = {S}앨리스 을 확인 참고사항: S 만 전송하면 괜찮은가? 만약 M이 크면 [M]앨리스 을 계산 비용 큼 앨리스가 M 보다 훨씬 적은 h(M)에 서명하다고 가정 앨리스는 M 과 S = [h(M)]앨리스 를 밥에게 전송 밥은 h(M) = {S}앨리스

암호 해시 함수 h(x) 는 다음을 제공해야 함 암호학적 해시함수 압축 (Compression)  출력길이가 작아야 함 효율성 (Efficiency)  어떤 x에 대해서도 h(x) 를 계산하기가 쉬워야 함 단방향 (One-way)  주어진 y값에 대해 h(x)=y를 만족하는 x 값을 찾는 것이 어려워야 함 약한 충돌 방지 (Weak collision resistance)  주어진 x와 h(x)에 대해 h(y) = h(x)를 만족하는 y  x 를 찾기 어려워야 함 강한 충돌 방지 (Strong collision resistance)  h(x) = h(y) 를 만족하면서 x  y 인 어떤 x와 y도 찾기 어려워야 함 많은 충돌들이 존재하지만, 찾기가 어려워함 함

한 방에 있는 사람들 중에 2명 또는 그 이상이 같은 생일일 확률이 ½보다 크기 위해서는 얼마나 많은 사람들이 있어야 하나? 생일 문제 한 방에 있는 사람들 중에 2명 또는 그 이상이 같은 생일일 확률이 ½보다 크기 위해서는 얼마나 많은 사람들이 있어야 하나? 1  365/365  364/365   (365N+1)/365 위의 값이 ½과 같기 위해서는: N = 23

Cyclic Redundancy Check (CRC) 근본적으로 CRC는 긴 나눗셈 문제의 나머지 전송 오류 탐지에 유용 비 암호 해시 (3) Cyclic Redundancy Check (CRC) 근본적으로 CRC는 긴 나눗셈 문제의 나머지 전송 오류 탐지에 유용 그러나 충돌을 만들기는 쉬움. CRC 는 가끔 암호 응용 분야(WEP)에 사용되고 있으나 이는 잘못된 것임.

많은 다른 해시들이 있지만 MD5와 SHA-1 이 가장 널리 사용 인기 있는 암호 해시들 MD5  리베스트가 발명 128 bit output Note: MD5 collision recently found SHA-1  미 정부 표준 (MD5와 유사) 180 비트 출력 많은 다른 해시들이 있지만 MD5와 SHA-1 이 가장 널리 사용 해시는 블록내의 해싱 메시지에 적용

요구되는 특성: 쇄도효과 (avalanche effect) 암호 해시 설계 요구되는 특성: 쇄도효과 (avalanche effect) 입력의 1 비트의 변경이 출력 비트의 절반에 영향을 주어야 함 암호 해시 함수들은 수 회전들로 구성 보안과 속도를 요구 몇 회전 후에는 쇄도 효과가 나타나야 함 그러나 회전들은 단순해야 함 블록 암호 설계와 유사

“빠르고 강하다” 선도 암호학자  앤더슨과 엘리 비햄 설계 기준 Section 04 Tiger 해시 안전성 64-비트 프로세스에서 가장 효율적 MD5 나 SHA-1 를 쉽게 대체 가능

인증 (HMAC) 메시지 무결성 (HMAC) 메시지 지문 데이터 변조 탐지 전자서명 효율성 Section 06 해시 용도 인증 (HMAC) 메시지 무결성 (HMAC) 메시지 지문 데이터 변조 탐지 전자서명 효율성 대칭키 암호가 할 수 있는 어떤 것도 가능

상호 입찰금이 비밀로 지키질 것을 신뢰하지 못함. 온라인 입찰 앨리스, 밥, 찰리가 입찰자라 하자. 앨리스는 A, 밥은 B, 찰리는 C 금액으로 입찰 상호 입찰금이 비밀로 지키질 것을 신뢰하지 못함. 앨리스, 밥, 찰리는 해시 h(A), h(B), h(C)를 제출 모든 해시는 온라인 상에 게시 그리고 A, B, C 를 공개 해시는 입찰금을 공개하지 않음.(단방향) 해시 전송후는 입찰금을 변경할 수 없음.

Section 07기타 암호 관련 주제- 비밀 공유 샤미르의 비밀 공유 두 점이 한 선을 결정 (X0,Y0): 앨리스 (X1,Y1): 밥 앨리스와 밥은 비밀 S를 찾기 위해 서로 협조해야만 함 실수보다 이산수로 작업 m  n 경우 “n 중의 m” 체계를 만들기 용이 Y (X1,Y1) (X0,Y0) (0,S) X 2 중의 2

샤미르의 비밀 공유 Y X 3 중에 2 비밀 공유 (X0,Y0) : 앨리스 (X1,Y1) : 밥 (X2,Y2) : 찰리 세 사람 중 두 사람만 협조하면 비밀 S를 찾을 수 있다. 한 사람이 S를 찾을 수는 없다. “3 중에 2” 체계 Y (X0,Y0) (X1,Y1) (X2,Y2) (0,S) X 3 중에 2

샤미르의 비밀 공유 Y X 3 out of 3 비밀 공유 (X0,Y0) : 앨리스 (X1,Y1) : 밥 (X2,Y2) : 찰리 3 점이 포물선을 결정 비밀 S를 찾기 위해서는 세명이 모두 협조 “3 중에 3” 체계 “4 중에 3” 체계를 만들 수 있나? Y (X0,Y0) (X1,Y1) (X2,Y2) (0,S) X 3 out of 3

키를 저장하는 FBI를 신뢰할 수가 없는 것이 문제 이 경우 비밀 공유 체계를 사용 정보공유의 예 조건부 키  키가 어떤 곳에 저장된다는 가정 키는 법원의 명령에 의해 사용될 수 있다 키를 저장하는 FBI를 신뢰할 수가 없는 것이 문제 이 경우 비밀 공유 체계를 사용 세 개의 정부 기관이 있다고 하면 키를 사용하기 위해 적어도 두 개 기관이 협조하도록 할 수 있다

키 K를 복구하기 위해서는 3개의 기관 중 2개 이상이 협조해야만 한다. 정보공유의 예제 대칭키: K Point (X0,Y0) : FBI Point (X1,Y1) : DoJ Point (X2,Y2) : DoC 키 K를 복구하기 위해서는 3개의 기관 중 2개 이상이 협조해야만 한다. 한 개의 기관은 K를 복구할 수 없다. Y (X0,Y0) (X1,Y1) (X2,Y2) (0,K) X

난수들은 시뮬레이션, 통계 등의 응용 분야에서도 사용. 그러나 이 때는 “통계적” 난수들이 통상 사용됨. 난수는 키를 생산하기 위해 사용되었다 대칭키 RSA: 소수들 디피-헬먼: 비밀 값 임시로 사용될 때 난수가 사용 가끔은 순서대로 하는 것이 괜찮을 때가 있음. 또 다른 경우는 임시로 사용되는 수가 난수일 필요가 있음. 난수들은 시뮬레이션, 통계 등의 응용 분야에서도 사용. 그러나 이 때는 “통계적” 난수들이 통상 사용됨.

프로그램은 카드를 섞는 행위인 셔플을 완전히 무작위로 하지 않음. 참가자는 실시간에 셔플을 알 수 있음! 나쁜 난수의 예제 텍사스 홀뎀 포커의 온라인 버전 ASF 소프트사 가상 카드를 섞기 위해 난수 사용 프로그램은 카드를 섞는 행위인 셔플을 완전히 무작위로 하지 않음. 참가자는 실시간에 셔플을 알 수 있음! < 손에 쥔 카드 > < 테이블 위에 놓인 카드 >

최저선: “비밀성을 생산하기 위한 유사-난수 절차들의 사용은 유사-보안을 만드는 결과가 된다” 무작위 S/W를 통한 무작위 결정 S/W는 결정적(deterministic)이므로 외부에서 “무작위” 를 결정해야 함 마우스 이동, 키보드 사용, 네트워크 활동 등 S/W를 통해 양질의 난수 비트를 얻을 수 있음 그러나 이러한 비트의 수는 상당히 제한 최저선: “비밀성을 생산하기 위한 유사-난수 절차들의 사용은 유사-보안을 만드는 결과가 된다”

디지털 워터마킹 스테가노그래피 정보 은닉 예제: “투명” 식별자를 자료에 첨가 음악이나 소프트웨어의 불법 배포를 막기 위해 사용 스테가노그래피 비밀 통로 채널 예제: 자료를 음악이나 이미지에 은닉

워터마크 “마크”를 데이터에 첨가 여러 종류의 워터마크 강하고 투명한 마크- 디지털 음악에 첨가 투명  마크가 미디어 내 인지되지 않은 상태 가시  일급비밀 마크 강한  공격 시에도 읽을 수 있는 상태 약한  공격 시에는 손상 강하고 투명한 마크- 디지털 음악에 첨가 만약 해적 음악이 인터넷에서 출현하면, 근원지를 추적할 수 있다 약하고 투명한 마크- 디지털 음성파일에 첨가 만약 워터마크를 읽을 수 없으면, 수신자는 음성파일이 변경되었음을 알 수 있다 (무결성) 여러 형태의 혼합형들이 사용 될 수 있다 즉, 가시적이며 강하고 투명한 워터 마크

워터마크 예제 (1) 미 지폐에 포함된 워터마크 우측 부분에 이미지 삽입 지폐를 불빛에 보면 삽입 정보를 볼 수 있음.

역사적으로 보면, 스테가노그래피가 암호보다 더 많이 사용 되었음! 헤로도토스에 의하면 (그리스 440BC) 노예의 머리를 면도 메시지를 쓴 후에 머리카락이 자란 후에 메시지 전달을 위해 노예를 보냄 메시지를 읽기 위해 노예 머리를 다시 면도(페르시아의 침공 경고 내용) 역사적으로 보면, 스테가노그래피가 암호보다 더 많이 사용 되었음!

이미지는 다음 칼라를 위해 24비트 사용: RGB 예를 들면 그러나 아래 비트는 중요하지 않음 이미지와 스테가노그래피 8 비트: red, 8 : green, 8 : blue 예를 들면 0x7E 0x52 0x90 : 이 색 0xFE 0x52 0x90 : 이 색 그러나 0xAB 0x33 0xF0 : 이 색 0xAB 0x33 0xF1 : 이 색 아래 비트는 중요하지 않음

우측: 이상한 나라의 앨리스(pdf) 전체 내용이 은닉된 이미지 스테가노그래피 예제 1 좌측: 앨리스의 보통 이미지 우측: 이상한 나라의 앨리스(pdf) 전체 내용이 은닉된 이미지

스테가노그래피가 아닌 예제 소스 내용 Walrus.html

소스 내용 스테가노그래피 예제 2 스테가노그래피 Walrus.html “은닉” 메시지: 110 010 110 011 000 101

어떤 포맷 (jpg, gif, wav, etc.)은 사람이 읽기가 htmal 보다 더욱 어렵다 스테가노그래피 어떤 포맷 (jpg, gif, wav, etc.)은 사람이 읽기가 htmal 보다 더욱 어렵다 중요하지 않은 비트에 정보를 은닉하는 것이 쉽다 중요하지 않은 비트에 저장된 정보는 제거하거나 파괴하기가 쉽다! 강하게 만들려면, 중요한 비트에 정보를 저장해야만 한다. 저장된 정보는 데이터를 손상시키지 말아야 한다! 충돌공격이 역시 주요 관심 사항이다 강한 스테가노그래피는 일반적으로 알고 있는 것 보다 기교가 필요하다