SeoulTech UCS Lab 2014-1 st 현대암호학 제 8 장일방향해시함수 박종혁교수 Tel: 970-6702 Email: jhpark1@seoultech.ac.kr
1절일방향해시함수 2절일방향해시함수의응용예 3절일방향해시함수의예 4절일방향해시함수 SHA-1 5절일방향해시함수 SHA-512 6절일방향해시함수에대한공격 7절일방향해시함수로해결할수없는문제 2
제 1 절일방향해시함수 1.1 파일의진위 1.2 일방향해시함수란? 1.3 일방향해시함수의성질 1.4 해시함수관련용어 3
1.1 파일의진위 어제저장한파일과오늘의파일비교 밤새맬로리가파일을변경했는지어떤지를조사하고싶다 무결성 (integrity) 파일이변경되지않았음 4
파일의무결성을조사하고싶다 5
파일전체를안전한장소에보존해두고, 나중에비교하는방법 6
파일의지문 범죄수사에서지문을채취하는것과마찬가지로앨리스가만든파일의 지문 을채취할수는없을까? 파일전체를비교하는대신에작은지문만을비교하는것만으로도무결성을확인할수있다면매우편리 7
파일을비교하는대신에해시값을비교하는방법 8
1.2 일방향해시함수란? 일방향해시함수는바로파일의지문을채취하는기술 일방향해시함수가만들어내는 해시값 은메시지의지문에해당 9
일방향함수의예 입력 : 임의의숫자 처리 : 입력되는숫자를 23 으로나누는메커니즘 출력 : 그몫을소수로표시했을때소숫점이하 7 자리부터 10 자리까지 4 자리숫자 10
실제적용 입력 : 345689 처리 : 345689 를 23 으로나누어보자 출력 : 7391 몫은 15029.95652173913043 이므로 7 자리부터 10 자리의수는 7391 11
일방향해시함수 일방향해시함수 (one-way hash function) 입력과출력이각각 1개씩있다. 입력은메시지 (message) 출력은해시값 (hash value) 일방향해시함수는메시지를기초로해서해시값을계산 12
일방향해시함수는메시지를기초로해서해시값을계산 13
일정한크기의출력 해시값의길이는메시지의길이와는관계가없다. 메시지가 1비트라도, 1메가바이트라도, 100기가바이트라도일방향해시함수는고정된길이의해시값을출력 예 : SHA-1의출력은항상 160비트 (20바이트) 14
해시값은항상고정길이 15
1.3 일방향해시함수의성질 임의의길이메시지로부터고정길이의해시값을계산한다 해시값을고속으로계산할수있다 메시지가다르면해시값도다르다 일방향성을갖는다 16
고정길이의출력 어떠한크기의메시지라도크기에관계없이입력으로사용할수있어야한다 어떤길이의메시지를입력으로주더라도일방향해시함수는짧은해시값을생성 17
빠른계산속도 해시값계산은고속이어야한다 메시지가길어지면해시값을구하는시간이길어지는것은어쩔수없다 현실적인시간내에계산할수없다면소용이없다 18
메시지가다르면해시값도다르다 메시지가 1 비트라도변화하면해시값은매우높은확률로다른값이돼야한다 19
메시지가 1 비트만달라도다른해시값이된다 20
해시함수의충돌 충돌 (collision) 2 개의다른메시지가같은해시값을갖는것 충돌내성 (collision resistance) 충돌을발견하는것이어려운성질 21
일방향해시함수의충돌내성 22
충돌내성 약한충돌내성 어느메시지의해시값이주어졌을때, 그해시값과같은해시값을갖는다른메시지를발견해내는것이매우곤란한성질 강한충돌내성 해시값이일치할것같은, 다른 2 개의메시지를발견해내는것이매우곤란한성질 23
일방향성을갖는다 해시값으로부터메시지를역산할수없다는성질 메시지로부터해시값을계산하는것은간단히할수있다 해시값으로부터메시지를계산하는것은불가능해야한다 24
일방향해시함수의일방향성 25
1.4 해시함수관련용어 일방향해시함수 메시지다이제스트함수 (message digest function), 메시지요약함수 암호적해시함수 일방향해시함수의입력이되는메시지 프리 이미지 (pre-image) 해시값은 메시지다이제스트 (message digest) 핑거프린트 (fingerprint) 무결성 완전성 보전성 26
제 2 절일방향해시함수의응용예 2.1 소프트웨어의변경검출 2.2 패스워드를기초로한암호화 2.3 메시지인증코드 2.4 디지털서명 2.5 의사난수생성기 2.6 일회용패스워드 27
2.1 소프트웨어의변경검출 자신이입수한소프트웨어가변경되었는지를확인하기위해일방향해시함수를사용 28
소프트웨어개정검출을위해일방향해시함수를사용 29
2.2 패스워드를기초로한암호화 패스워드를기초로한암호화 (password based encryption; PBE) 에서사용 PBE 에서는패스워드와솔트를섞은결과의해시값을구해그것을암호화키로사용 패스워드사전공격 (dictionary attack) 방어 30
2.3 메시지인증코드 송신자와수신자만이공유하고있는키 와 메시지 를혼합해서그해시값을계산한값 통신중의오류나수정그리고 가장 을검출가능 SSL/TLS에서이용 31
2.4 디지털서명 현실사회의서명 ( 사인 ) 이나날인에해당하는온라인상의서명 처리시간단축을위해일방향해시함수를사용해서메시지의해시값을일단구하고, 그해시값에대해디지털서명을수행 32
2.5 의사난수생성기 암호기술에필요한난수 과거의난수열로부터미래의난수열을예측하는것은사실상불가능 이라는성질이필요 그예측불가능성을보증하기위해일방향해시함수의일방향성을이용 33
2.6 일회용패스워드 원타임패스워드 (one-time password) 정당한클라이언트인지아닌지를서버가인증할때에사용 일방향해시함수를써서통신경로상에흐르는패스워드를 1 회 (one-time) 만사용하도록고안 패스워드가도청되어도악용될위험성이없다 34
제 3 절일방향해시함수의예 3.1 MD4와 MD5 3.2 SHA-1, SHA-256, SHA-384, SHA-512 3.3 RIPEMD-160 3.4 SHA(Advanced Hash Standard) 와 SHA-3 35
3.1 MD4 와 MD5 MD4 Rivest 가 1990 년에만든일방향해시함수 128 비트의해시값 Dobbertin 에의해충돌발견방법이고안 현재는안전하지않다 36
3.1 MD4 와 MD5 MD5 Rivest 가 1991 년에만든일방향해시함수 128 비트의해시값 암호해독에취약함을보여주는여러가지암호해독방법들이개발 MD5 가완전히뚫린것은아니지만, MD5 내부구조의일부에대한공격방법이몇개발견 사용을권장하지않는다 37
3.2 SHA-1, SHA-256, SHA-384, SHA-512 SHA-1 NIST(National Institute of Standards and Technology) 에서제작 160 비트의해시값 SHA 1993 년에미국의연방정보처리표준 SHA-1 1995 년에발표된개정판 메시지길이상한 : 2 64 비트미만 큰값이므로현실적인적용에는문제가없음 38
SHA-2 SHA-256: 256 비트의해시값 메시지의길이상한 2 64 비트미만 SHA-384: 384 비트의해시값 메시지의길이상한 2 128 비트미만 SHA-512: 512 비트의해시값 메시지의길이상한 2 128 비트미만 39
3.3 RIPEMD-160 RIPEMD-160 1996 년에 Hans Dobbertin, Antoon Bosselaers, Bart Preneel 이제작 160 비트의해시값 European Union RIPE 프로젝트로만들어진 RIPEMD 함수의개정판 40
3.4 SHA(Advanced Hash Standard) 와 SHA-3 NIST 는 SHA-1 을대체하는차세대일방향해시함수로 SHA-3 제정 SHA-3 은 AES 와같은방식으로표준화 41
제 4 절일방향해시함수 SHA-1 패딩 W 0 ~ W 79 계산 블록처리 단계 1 처리 42
일방향해시함수 SHA-1 의개요 43
패딩 메시지뒤에여분의데이터를부가하여메시지의길이가 512 비트의정수배가되도록하는것 44
패딩의예 입력 : Hello. (6 바이트 (48 비트 )) 의메시지 ASCⅡ 코드로부호화하여 2 진수로표현하면 H e l l o. 01001000 01100101 01101100 01101100 01101111 0011110 여기에 1 을붙인다 01001000 01100101 01101100 01101100 01101111 00101110 1 45
패딩의예 46
0 의추가 01001000 01100101 01101100 01101100 01101111 00101110 10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 47
길이정보추가 데이터길이 : 48 비트를 2 진수로표현하면 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00110000 이것을마지막에추가 01001000 01100101 01101100 01101100 01101111 00101110 10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00110000 48
W 0 ~ W 79 의계산 입력블록 512 비트마다 32 비트 80 개의값 (W 0 ~ W 79 ) 을계산 입력블록 512 비트를 32 비트 16 개로분할하여 W 0 ~ W 15 로이름을붙인다 W 16 부터 W 79 는아래와같이계산 W 16 = (W 0 W 2 W 8 W 13 ) 을 1 비트회전 W t = (W t-16 W t-14 W t-8 W t-3 ) 을 1 비트회전, t=17~79 49
1 비트회전한모양 50
입력블록 512 비트로부터 80 개의 32 비트값 (W 0 ~ W 79 ) 생성 51
블록처리 입력블록에대해 80 단계씩의처리를행한다 입력블록의정보를기초로내부상태 (160 비트 ) 를변화 52
입력블록 512 비트를 160 비트의내부상태에섞기 (80 단계 ) 53
1 단계처리 54
제 5 절일방향해시함수 SHA-512 패딩비트붙이기 길이붙이기 MD 버퍼초기화 1024- 비트 (128- 워드 ) 블록메시지처리 출력 55
SHA-512 를이용한메시지다이제스트생성 56
1024 비트한개에대한 SHA-512 처리 57
제 6 절일방향해시함수에대한공격 6.1 전사공격 ( 공격스토리 1) 6.2 전사공격 ( 공격스토리 2) 58
6.1 전사공격 ( 공격스토리 1) 일방향해시함수의 약한충돌내성 을깨고자하는공격 예 : 맬로리는앨리스의컴퓨터에서계약서파일을발견하고, 그안의 앨리스의지불금액은백만원으로한다. 부분을, 앨리스의지불금액은일억원으로한다. 로바꾸고싶다 59
공격스토리 1 문서의의미를바꾸지않고얼마만큼파일을수정할수있을까 를생각 동일한내용을다른형태로표현 앨리스의지불금액은일억원 ( 一億원 ) 으로한다. 앨리스의지불금액은일억원 ( 壹億원 ) 으로한다. 앨리스의지불금액은 100000000 원으로한다. 앨리스의지불금액은 \100000000 으로한다. 앨리스의지불금액은, 일억원 ( 一億원 ) 으로한다. 앨리스가지불하는금액은일억원으로한다. 앨리스는일억원을지불하는것으로한다. 대금으로서, 앨리스는일억원을지불한다. 60
공격스토리 1 일억원지불의계약서 를기계적으로대량작성 그중에앨리스가만든오리지널 백만원계약서 와같은해시값을생성하는것을발견할때까지작성한다 발견한새로운계약서로교환 61
6.2 전사공격 ( 공격스토리 2) 강한충돌내성 을깨고자하는공격 맬로리는해시값이같은값을갖는 백만원계약서 와 일억원계약서 를미리만들어둔다 맬로리는시치미를떼고 백만원계약서 를앨리스에게건네주고, 해시값을계산시킨다 맬로리는스토리 1 과마찬가지로 백만원계약서 와 일억원계약서 를살짝바꾼다. 62
생일공격 (birthday attack) N 명중적어도 2 명의생일이일치할확률이 2 분의 1 이상이되도록하기위해서는 N 은최저몇명이면될까? 답 : 놀랍게도 N = 23 이다 단 23 명만있으면 2 분의 1 이상의확률로적어도 2 명의생일이일치한다. 63
이유 어느특정일을정하고 2 명이그날태어날 가능성은확실히높지않다. 그러나 1 년의어느날이라도상관없으므로 2 명이같은날태어날 가능성은의외로높다. 64
스토리 2 의 생일공격 1) 맬로리는백만원계약서를 N개작성 2) 맬로리는일억원계약서를 N개작성 3) 맬로리는 (1) 의해시값 N개와 (2) 의해시값 N개를비교해서 일치하는것이있는지찾는다 4) 일치하는것이발견되면그백만원계약서와일억원계약서 를가지고앨리스를속이러간다 65
N 의크기 문제가되는것은 N 의크기이다 N 이작으면맬로리는감쪽같이생일공격에성공할수있다 N 이크면시간도메모리양도많이필요해지기때문에생일공격은어려워진다 N 은해시값의비트길이에의존 66
스토리비교 스토리 1 앨리스가백만원계약서를만들었기때문에해시값은고정되어있다. 맬로리는그해시값과같은메시지를발견해내는약한충돌내성을공격하는것 67
스토리비교 스토리 2 맬로리가 2 개의계약서를만드는것이므로해시값은뭐라도상관없다 백만원계약서와일억원계약서의해시값이같기만하면된다. 68
제 7 절일방향해시함수로해결할수없는문제 일방향해시함수는 조작또는변경 을검출할수있지만, 거짓행세 검출은못한다 인증 : 이파일이정말로앨리스가작성한것인지를확인하는것 인증을수행하기위한기술 메시지인증코드 디지털서명 69
Q & A 70
Thank You! 71