SeoulTech UCS Lab 제 13 장 난수 박종혁교수 Tel: 970-6702 Email: jhpark1@seoultech.ac.kr
1 절난수가사용되는암호기술 2 절난수의성질 3 절의사난수생성기 4 절구체적의사난수생성기 5 절의사난수생성기에대한공격 2
제 1 절난수가사용되는암호기술 1.1 난수의용도 3
1.1 난수의용도 키생성 대칭암호나메시지인증코드 키쌍생성 공개키암호나디지털서명 초기화벡터 (IV) 생성 블록암호모드인 CBC, CFB, OFB 비표 (nonce) 생성 재전송공격방지나블록암호의 CTR 모드 솔트생성 패스워드를기초로한암호화 (PBE) 일회용패드 패딩에사용되는열을생성 4
난수의용도 아무리강한암호알고리즘이라도키가공격자에게알려져버리면아무의미가없다 난수를사용해서키를만들어, 공격자에게키를간파당하지않도록하는것 난수를사용하는목적이간파당하지않도록하기위한것 5
제 2 절난수의성질 2.1 난수의성질분류 2.2 무작위성 2.3 예측불가능성 2.4 재현불가능성 6
2.1 난수의성질분류 무작위성 통계적인편중이없이수열이무작위로되어있는성질 예측불가능성 과거의수열로부터다음수를예측할수없다는성질 재현불가능성 같은수열을재현할수없다는성질. 재현하기위해서는수열그자체를보존해야만하는성질 7
난수의분류 무작위성 예측 불가능성 재현 불가능성 약한의사난수 무작위성만갖는다 암호기술에 사용할수없다 강한의사난수 진정한난수 예측불가능성도갖는다재현불가능성도갖는다 암호기술에 사용할수있다 8
난수의성질 9
2.2 무작위성 아무렇게 로보이는성질 의사난수열의통계적인성질을조사해서치우침이없도록하는성질 난수검정 의사난수열의무작위성을조사하는것 암호기술에사용하는난수는무작위성을가지고있는것만으로는불충분 약한의사난수 무작위성만을갖는의사난수 10
2.3 예측불가능성 공격자에게간파당하지않는다는예측불가능성이필요 과거에출력한의사난수열이공격자에게알려져도다음에출력하는의사난수를공격자는알아맞힐수없다는성질 알고리즘은공격자에게알려져있다고가정하고종자를사용 종자 (seed): 공격자에게비밀 11
강한의사난수 약한의사난수 무작위성만을갖는의사난수 강한의사난수 예측불가능성을갖는의사난수 예측불가능성을가지면당연히무작위성을가짐 12
2.4 재현불가능성 한난수열이주어졌을때동일한수열을재현할수없는성질 재현하기위해서는그난수열자체를보존해두는것이외에방법이없는성질 소프트웨어만으로는재현불가능성을갖는난수열생성불가 소프트웨어는의사난수열만생성가능 소프트웨어가돌아가는컴퓨터가유한의내부상태밖에없기때문 13
주기 소프트웨어가생성하는수열은언젠가는반복 반복이다시시작할때가지의수열의길이를주기 (period) 라고함 주기를갖는수열은재현불가능하지않음 14
재현불가능한난수생성 재현불가능한물리현상으로부터정보를취득 예 주위의온도나소리의변화 사용자의마우스위치정보 키스트록입력시간간격 방사선관측기의출력 다양한하드웨어로부터얻어진정보 15
재현불가능한난수 진성난수 (Real Random Number): 재현불가능한난수 위의 3 가지성질을모두가진다 무작위성 예측불가능성 재현불가능성 예 : 동전던지기결과로얻어지는비트 앞 : 0 뒤 : 1 16
제 3 절의사난수생성기 3.1 의사난수생성기의구조 17
난수생성기와의사난수생성기 난수생성기 (random number generator; RNG) 하드웨어로생성 의사난수생성기 (pseudo random number generator; PRNG) 소프트웨어로생성 주기성을가짐 18
3.1 의사난수생성기의구조 내부상태 종자 (seed) 19
의사난수생성기의구조 20
의사난수생성기의내부상태 의사난수생성기가관리하고있는메모리값 의사난수생성기는메모리의값 ( 내부상태 ) 을기초로해서계산을수행 그계산결과를의사난수로서출력 다음의사난수의요구에대비해서, 자신의내부상태를변화 21
의사난수생성알고리즘 의사난수생성알고리즘은다음 2 가지기능을합한것 의사난수를계산하는방법 내부상태를변화시키는방법 22
의사난수생성기의 종자 의사난수생성기의내부상태초기화에필요 랜덤한비트열 종자는자신만의비밀로유지 23
암호키와의사난수종자 24
제 4 절구체적의사난수생성기 4.1 무작위방법 4.2 선형합동법 4.3 일방향해시함수를사용하는방법 4.4 암호를사용하는방법 4.5 ANSI X9.17 25
4.1 무작위방법 긴주기 : 암호기술에서사용하는난수는예측불가능성을가져야하므로주기가짧아서는안됨 복잡한알고리즘보다는명확한알고리즘 프로그래머가자세한내용을이해할수없는알고리즘으로생성한난수는예측불가능성을갖는지어떤지평가를할수없음 26
4.2 선형합동법 선형합동법 (linear congruential method) 일반적으로가장많이사용되는의사난수생성기 암호기술에사용하면안됨 현재의사난수의값을 A 배하고 C 를더한다음, M 으로나눈나머지를다음의사난수로선택 27
선형합동법계산방법 R 0 생성 : 최초의사난수 R 0 = (A 종자 + C) mod M A, C, M 은정수이고, A 와 C 는 M 보다도작은수 R 1 생성 : R 1 = (A R 0 + C) mod M R n+1 생성 R n+1 = (A R n + C) mod M n=2, 3 28
선형합동법에의한의사난수생성기 29
선형합동법예 A = 3 C = 0 M = 7 R 0 = (A 종자 + C) mod M = (3 6 + 0) mod 7 = 18 mod 7 = 4 R 1 = (A R 0 + C) mod M = (3 4 + 0) mod 7 = 12 mod 7 = 5 30
선형합동법예 R 2 = (A R 1 + C) mod M = (3 5 + 0) mod 7 = 15 mod 7 = 1 R 3 = (A R 2 + C) mod M = (3 1 + 0) mod 7 = 3 mod 7 = 3 반복해서 4, 5, 1, 3, 2, 6, 4, 5, 1, 3, 2, 6, 생성 이경우 4, 5, 1, 3, 2, 6 이라는 6 개숫자의반복이되므로주기는 6 31
선형합동법다른예 의사난수의값은 M 으로나눈나머지므로, 반드시 0 부터 M-1 의범위 A 와 C 와 M 의값에따라다른주기를가짐 예 : A=6, C=0, M=7, 종자 = 6 인경우 의사난수열은 1, 6, 1, 6, 1, 6, 주기는 2 32
A 값별의사난수 A 값변화에따른의사난수열 A = 0 인경우 : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ( 주기는 1) A = 1 인경우 : 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, ( 주기는 1) A = 2 인경우 : 5, 3, 6, 5, 3, 6, 5, 3, 6, 5, ( 주기는 3) A = 3 인경우 : 4, 5, 1, 3, 2, 6, 4, 5, 1, 3, ( 주기는 6) A = 4 인경우 : 3, 5, 6, 3, 5, 6, 3, 5, 6, 3, ( 주기는 3) A = 5 인경우 : 2, 3, 1, 5, 4, 6, 2, 3, 1, 5, ( 주기는 6) A = 6 인경우 : 1, 6, 1, 6, 1, 6, 1, 6, 1, 6, ( 주기는 2) 33
선형합동법의단점 선형합동법은 예측불가능성 이없다 선형합동법을암호기술에사용해서는절대로안됨 예 : 선형합동법을사용하는함수 C 라이브러리함수 rand Java 의 java.util.random 클래스 이들을암호기술에서사용해서는안됨 34
선형합동법의예측불가능성테스트 공격자가 A=3, C=0, M=7 이라는값을알고있다고가정 공격자가생성된의사난수를 1 개라도손에넣는다면그다음에생성되는의사난수를예측하는것이가능 입수한의사난수 R 을이용다음을계산 (A R + C) mod M = (3 R + 0) mod 7 35
4.3 일방향해시함수를사용하는방법 일방향해시함수 ( 예를들면 SHA-1) 를사용해서예측불가능성을갖는의사난수열 ( 강한의사난수 ) 을생성하는의사난수생성기를만들수있다 일방향해시함수의일방형성이의사난수생성기의예측불가능성을보장 36
절차 1) 의사난수의종자를사용해서내부상태 ( 카운터 ) 를초기화 2) 일방향해시함수를사용해서카운터의해시값생성 3) 그해시값을의사난수로서출력 4) 카운터를 1 증가 5) 필요한만큼의의사난수가얻어질때까지 (2)~(4) 를반복 37
일방향해시함수를사용한의사난수생성기 38
잘못만들어진의사난수생성기 다음과같이생성했다고해보자 1) 의사난수의종자를사용해서내부상태를초기화한다. 2) 일방향해시함수를사용해서내부상태의해시값을얻는 다. 3) 해시값을의사난수로서출력한다. 4) 그해시값을새로운내부상태로한다. 5) 필요한만큼의의사난수가얻어질때까지 (2)~(4) 를반복 한다. 39
잘못만들어진의사난수생성기 40
왜예측불가능성이없나? 마지막에출력한의사난수의해시값을취해서다음의사난수를생성하므로예측불가능성을갖지않는다. 예측불가능성을갖기위해서는일방향해시함수의일방향성을사용하는것이포인트 41
4.4 암호를사용하는방법 암호를사용해서 강한의사난수 를생성하는의사난수생성기를만들수있다 AES 와같은대칭암호나 RSA 와같은공개키암호중어느것을사용해도무방 암호의기밀성이의사난수생성기의예측불가능성을보장 42
암호를사용한의사난수생성절차 1) 내부상태 ( 카운터 ) 를초기화 2) 키를사용해서카운터를암호화 3) 그암호문을의사난수로서출력 4) 카운터를 1 증가 5) 필요한만큼의의사난수가얻어질때까지 (2)~(4) 를반복 43
암호를사용한의사난수생성기 44
4.5 ANSI X9.17 암호소프트웨어 PGP 에서사용하는의사난수생성기 ANSI X9.17 ANSI X9.31 45
ANSI X9.17 의사난수생성절차 1) 내부상태를초기화 2) 현재시각을암호화 3) 내부상태와암호화된현재시각을 XOR 4) 절차 (3) 의결과를암호화 5) 절차 (4) 의결과를의사난수로서출력 6) 절차 (4) 의출력과암호화된현재시각을 XOR 7) 절차 (6) 의결과를암호화 8) 절차 (7) 의결과를새로운내부상태로설정 9) 절차 (2)~(8) 을필요한만큼의의사난수가얻어질때까지반 복 46
ANSI X9.17 방법의사난수생성기 47
왜내부상태추측을못하나? 공격자는의사난수로부터역산해서 내부상태와암호화된현재시각의 XOR 을간파할수없다 이유 : 간파하기위해서는암호를해독해야만한다 공격자는지금까지출력된의사난수열로부터의사난수생성기의내부상태를추측못한다 48
제 5 절의사난수생성기에대한공격 5.1 종자에대한공격 5.2 랜덤풀에대한공격 49
5.1 종자에대한공격 종자의중요성 : 의사난수의 종자 는암호의 키 에필적 종자가공격자에게노출되면, 그의사난수생성기가생성한모든의사난수열은공격자에게노출 종자선택 : 재현불가능성을갖는 진정한난수 선택 50
5.2 랜덤풀에대한공격 랜덤풀 : 종자로사용할랜덤비트열을사전에만들어비축해놓은파일 암호소프트웨어가의사난수종자가필요할경우필요한만큼의랜덤한비트열을꺼내서사용 랜덤풀자체는특별한정보를가지지않지만유익한정보저장을위해필요하므로잘지켜야함 51
Q & A 52
Thank You! 53