박종혁교수 Tel: 970-6702 Email: jhpark1@snut.ac.kr ac kr
학습목표 디지털데이터는위변조가쉬우므로디지털증거로사용하기위해서는위변조를입증할수단이필요하다. 이런무결성유지를위해필요한수단인전자서명과전자서명의요소인해쉬함수를학습한다. 학습내용 해쉬함수 전자서명 시점확인서비스 디지털증거의인증
1. 해쉬함수 2. 전자서명 3. 시점확인서비스 4. 디지털증거의인증
디지털증거의신뢰성 디지털증거가위조되어법정에제출되는경우 디지털증거가위조되지않았음에도불구하고, 용의자또는피고소인이디지털증거가위조되었을가능성을이유로, 증거효력을무력화시키려하는경우 디지털증거발생 디지털증거수집 디지털증거분석디지털증거변조디지털증거제출 디지털증거무결성보장 증거위조
정의 계산용이성 (Ease of computation) 함수 h 와입력 x 가주어졌을때, h(x) 를계산하는것이용이 압축성 (Compression) : 함수 h는임의의길이입력 x를정의길이가 n( 비트 ) 인출력 h(x) 에대응 10101010101010101010101010101011010101010101001010101010110100100100100101010111010001010111010010000100101110001001000100010 11010010101110100010101000101000101001010101010101010101010100000000000111111101101010110101010101010100101101010101010101011 11110000101010101010100101010101010011101010100110101010101010101010101010101010101010101010010111100001110101110000111010001 10001111001110101011010101010101010101100101000101010100001000101011100010111001010000010100111001010101010101110101010101010 10101010101010101101010101010100101010101011010010010010010101011101000101011101001000010010111000100100010001011010010101110 10001010100010100010100101010101010101010101010000000000011111110110101011010101010101010010110101010101010101111110000101010 10101010010101010101001110101010011010101010101010101010101010101010101010101001011110000111010111000011101000110001111001110 10101101010101010101010110010100010101010000100010101110001011100101000001010011100101010101010111010101010101010101010101010 10110101010101010010101010101101001001001001010101110100010101110100100001001011100010010001000101101001010111010001010100010 10001010010101010101010101010101000000000001111111011010101101010101010101001011010101010101010111111000010101010101010010101 01010100111010101001101010101010101010101010101010101010101010100101111000011101011100001110100011000111100111010101101010101 01010101011001010001010101000010001010111000101110010100000101001110010101010101011101010101010101010101010101010110101010101 01001010101010110100100100100101010111010001010111010010000100101110001001000100010110100101011101000101010001010001010010101 01010101010101010100000000000111111101101010110101010101010100101101010101010101011111100001010101010101001010101010100111010 10100110101010101010101010101010101010101010101010010111100001110101110000111010001100011110011101010110101010101010101011001 010001010101000010001010111000101110010100000101001110010101010101011 0101010101010101010101010101101010101 0101001010101011010101011101110110101010101010010101010101010111 HAS-160, SHA-1 의경우 160 비트출력 1101000101010001010001010010101010101010101010101000000000001111111011
응용 전용해쉬함수의응용분야 데이터 무결성검사 전자서명 인증 난수생성기
필요성 암호학적해쉬함수는왜필요한가? 무결성 악의적인사용자에의한데이터위변조확인 효율성 데이터의거대화방지 전자서명시연산의효율성을증대시킴
분류 키사용유무에따른해쉬함수의분류
성질 안전성측면에서고려되어야할중요한성질 역상저항성 (Preimage Resistance) y 가주어지고, h(x)=y 인 x 를찾는것이어려움 제2 역상저항성 (2 nd-preimage Resistance) 충돌저항성 (Collision Resistance) h(x)=y 인 x 와 y 가주어지고, h(x )=y 인 x ( x) 를찾는것이어려움 h(x)=h(x ) 인 x, x ( x) 를찾는것이어려움
특성 해쉬함수의안전성성질들간의관계 역상저항성! 제 2 역상저항성 제 2 역상저항성! 역상저항성 충돌저항성 제 2 역상저항성 제 2 역상저항성 충돌저항성 역상저항성
생일역설 생일역설 (Birthday paradox) 과해쉬함수의안전성 생일역설 가능한데이터의개수가 2 n 일때, 2 n/2 정도의데이터가있 으면일치하는데이터가존재할확률이 ½ 보다크다. 어느집단에서생일이같은한쌍이상의학생이존재할 확률 (p) 이 0.5 이상이되기위한학생수 (r)? p = 1-1(1-1/n)(1-2/n)... (1-{r-1}/n) When n=365 and r >= 23, p >= 0.5
생일역설 생일역설 (Birthday paradox) 과해쉬함수의안전성 해쉬함수의안전성 해쉬함수의출력길이가 n비트이면, 생일역설에의해그해쉬함수의안전성은 2 n/2 를넘을수없다. MD4, MD5 의경우 : 해쉬함수의출력길이가 128 비트이므 로해쉬함수의안전성은 2 64 HAS-160, SHA-1 의경우 : 해쉬함수의출력길이가 160 비 트이므로해쉬함수의안전성은 2 80 SHA-256 의경우 : 해쉬함수의출력길이가 256비트이므로해쉬함수의안전성은 2 128
MD 구성방법 1989 년 CRYPTO 에서 Merkle 과 Damgard 에의해제안됨 설계논리 고정된입출력크기를갖는함수를이용하여임의의길이 의입력값을다루는해쉬함수를구성하는방법 압축함수 (f) 고정된입출력크기를갖는함수 : 압축함수 (Compression function) m 1 m 2 m l f f f h 0 h l
압축함수 설계논리 해쉬함수의기반이되는압축함수의설계논리에따른분류 MD4. MD5, SHA-1, SHA-2, HAS-160 등과같이순수하게전용해쉬함수해쉬함수로서이용되기위하여설계됨 블록암호 (E ) 기반해쉬함수 블록암호를기반으로역상저항성을만족하도록변형하여 설계됨 (MDC-2, MDC-4, PGV 모델 ) E E
해쉬함수의충돌쌍을효과적으로찾을수있는공격법이개발 표준해쉬함수를만들기위한프로젝트가미국 NIST 에서진행 MD5 에서충돌쌍이발견되어안전성에대한문제가제기 문제원인 : 제 2 역상을발견할수있어야하는데, 충돌쌍을발견하는것과제 2 역상을발견하는것은근본적인차이가있으며, 제 2 역상을효과적으로찾는방법은알려져있지않음 무결성유지를위한 MD5 해쉬함수의사용문제없음 향후 SHA-3 를사용하는것이바람직함 새롭게표준해쉬함수 SHA-3 를개발하고있으며, 안전도에대한기준이 80비트에서 128비트변화
MD 계열 전용해쉬함수설계동향 1989 MD2 1990 MD4, RIPEMD 1991 SHA-0 1992 MD5, HAVAL 1993 SHA-1 1996 RIPEMD-128,160, Tiger 2000 HAS-160,Whirlpool, SHA-256,384,512 2002 SHA-224
분석동향 전용해쉬함수의분석사례 2004 : MD4, MD5, HAVAL, RIPEMD 분석 Wang 2005 : SHA-0, SHA-1 분석 해쉬함수응용환경에대한공격 MD4 와 MD5 기반 HMAC/NMAC 에대한키복구 MD4 와 MD5 기반 APOP 프로토콜에서의키복구공격 But 충돌쌍공격은발견되었지만, 실제응용환경에적용가능한 제 2 역상공격은발견되지않았다.
표준화 NIST 해쉬함수표준공모 다양한 H/W & S/W 환경에서구현가능 (8, 32, 64 비트플랫폼 ) 256 비트이상의메시지입력 224, 256, 384, 512 비트해쉬값생성 해쉬함수후보제출마감 : 2008 년 10 월 31 일 제 1 차후보선정 : 2008 년 12 월 9 일 ( 기본요구사항을만족하는알고리즘선정 ) 제 2 차후보선정 : 2009 년 7 월 24 일 ( 안전성분석을통한알고리즘선정 ) 제 3 차후보선정 : 2010 년 8 월예정 최종알고리즘선정 : 2012 년 2 월예정
수명 HAS-160 / SHA-1 사용기간 SHA-1 은 2010 년이후충돌저항성이만족되어야하는모든응용분야에서사용을금해야한다. 전자서명 / 디지털타임스탬프등등 2010년이후부터는 SHA-2를이용하여야만한다. SHA-1은 2010년이후 HMACs / KDFs / RNGs에서만이용될수있음 HAS-160은현재까지전체라운드에대한충돌쌍공격이알려져있지않음 SHA-1에비하여메시지확산과정이좋음 하지만 2010년이후에는 SHA-2와같이해쉬값의길이가 256비트인국내표준해쉬함수의개발이요구됨
비트스트림복제 (Bit Stream Clone) 방식으로저장매체를전체복사하여하드디스크드라이브이미지를생성한후, 해쉬함수를적용 해쉬및오류검증알고리즘을저장매체와이미지에적용 해쉬알고리즘 (Hash Algorithm) 의특성 원본데이터를 1-bit 만바꿔도해쉬함수의결과값은전혀다른출력값을생성하기때문에, 증거무결성에활용되고있음 오류검증알고리즘의특성 CRC (Cyclic Redundancy Check) : 전송데이터내에에러가있는지를확인하기위한방법중의하나 검증값이불일치하면데이터에오류가존재함 HASH / CRC == 해쉬및오류검증알고리즘을원본 Disk와 Disk Image에적용하여보관한뒤, 법정증거제출시무결성을주장
Disk Imaging Case Info CRC' 64 Sector Of data MD5. ' V = h ( H ) = h ( I ) V ' = h ( H ') = h ( I ')
현재사용되고있는도장이나서명을디지털로실현 ( 사용자인증 + 메시지인증 ) 특징 무결성 (Integrity) : 서명한데이터의전송과정에서변형되지않음 위조불가 (Unforgeable) : 서명자만이서명생성가능 서명자인증 (Authentic) : 서명자를확인가능 재사용불가 (Not Reusable) : 다른문서의서명으로사용불가 변경불가 (Unalterable) : 서명된문서의내용변경불가 부인불가 (Nonrepudiation) : 서명사실부인불가
인감 인감 : 종이문서 + 인감도장날인 전자서명 서명된전자문서 : 전자문서 + 전자서명 종이문서 전자문서 전자서명생성키 전자서명검증키 1999년吉洪 1999년印東전자서명 계약함 계약함인감등록검증키洪吉東 ( 인 ) 등록洪吉東 洪吉東印 정부기관 인감증명서발급 해쉬알고리즘전자서명알고리즘 공인인증기관전자인증서발급 종이문서 1999년 계약함 洪吉東 洪吉東印 인감증명서 洪吉東 비교확인 洪吉東印 전자서명 bc12726da4354 a65b7cd6bc7d9 7d9 전자문서 1999 계약함洪吉東 ( 인 ) 전자서명검증키 전자서명알고리즘 해쉬알고리즘 확인검증
전자서명의동작원리
공개키등록, 유지, 폐기등의관리체계가필요 Issues x.509 certificate signature Public key Pi Private key A's Public key CA How to trust Public key? Encryption and Digital signature With public key
임의의디지털데이터가특정한시점에존재하였으며, 특정시점이후에는데이터의내용이변경되지않았음을증명해주는서비스 디지털데이터와객관적인시각정보를결합한뒤제 3자의전자서명을거쳐시점확인토큰 (Time Stamping Token) 을생성
전자서명과의차이 전자서명 : 누가서명했느냐에초점 시점확인서비스 : 언제서명했느냐에초점 시점확인서비스의주체 시점확인인가자 (Time Stamping Authority, TSA) : 토큰발행 시점확인이용자 : 시점확인요청 시점확인검증자 : 이용자및토큰의유효성검증
시점확인인가자 : 토큰의무결성검증을위해서는신뢰할수있는제 3 의기관 (Third Trusted Party, TTP) 한국정보인증, 코스콤공인인증센터, 금융결제원전자인증센터 시점확인토큰에디지털데이터의존재성과무결성에대한법적효력을명시적으로부여하고있지않음 공인전자서명의경우전자서명법제 3 조 2 항에의거서명자본인추정력과내용의무결성이인정 TTP에의해발급된시점확인토큰이디지털데이터의존재시점과무결성을입증하기위해사용될수있음
증거발생증거수집증거분석증거제출 수사기관 해쉬값전달 해쉬값전달 법원의인증서로전자서명 서명확인해쉬값비교 법원 서명및해쉬값전달 전자증거보관소 서명및해쉬값전달 불일치시증거무결성훼손입증