Computer Security Ch7: Random Number Generator Howon Kim 2017.4
Agenda Random Number Generation 2
핵심정리 난수혹은의사난수생성은많은암호함수에서필요로함 필수조건 생성되는수의스트림이예상할수없는수
7.1 의사난수생성의원리 난수 특정한배열순서나규칙을가지지않는연속적인임의의수 의사난수 (Pseudo random number) 컴퓨터에의해서만들어지는난수, 매우긴주기를가지고있는숫자열 임의성 균일분포 수열의비트분포가균일, 0 과 1 의출현빈도가거의동일해야함 독립성 수열의어느부분수열도다른부분수열로부터추정될수없음 비예측성 수열의잇따른다음수의순서에대해예측이불가능해야함
7.1 의사난수생성의원리 TRNG(True Random Number Generator : 진난수생성기 ) 실제적으로랜덤한소스를입력으로사용 키보드입력타이밍패턴및마우스움직임 디스크의전기적활동, 시스템클럭의순간값 PRNG(Pseudo Random Number Generator : 의사난수발생기 ) 고정값 seed 를입력받아결정적알고리즘을사용하여출력비트열생성 제한이없는비트열생성하는데사용 알고리즘과시드를알고있는공격자는비트열재생성가능 PRF(Pseudo Random Function : 의사난수함수 ) 고정된길이의의사난수비트열을생산하는데사용
7.1 의사난수생성의원리 난수와의사난수생성기 Source of true randomness seed seed Contextspecific values Conversion to binary Deterministic algorithm Deterministic algorithm Random Bit stream Pseudorandom Bit stream Pseudorandom Value TRNG PRNG PRF
7.1 의사난수생성의원리 PRNG 요구사항 Seed 를알지못하는공격자가의사난수열을결정할수가없어야함 임의성 (Randomness) 생성된비트스트림이결정적일지라도랜덤하게보여야함 균일성 난수또는의사난수비트열의생성에있어서 0 과 1 은거의동일하게존재 확장성 비트열이랜덤하면무작위로추출된어떤비트열도랜덤해야함 일관성 생성기의동작은초기값전반에대해일관되어야함
7.1 의사난수생성의원리 PRNG 요구사항 ( 계속 ) 비예측성 (Unpredictability) 수열의잇따른다음수의순서에대해예측이불가능해야함 전방향비예측성 이전비트들에대한정보가있다고하더라도다음출력비트는예측할수없어야함 후방향비예측성 Entropy source 생성된어떠한값의정보를통해서도 seed 를결정할수없어야함 시드요구사항 (Seed Requirements) Seed는예측불가능해야함 Seed는난수또는의사난수이어야함 TRNG에의해 seed생성 SP800-90 에서권고 True random number generator (TRNG) seed Pseudorandom number generator (PRNG) Pseudorandom Bit stream
7.1 의사난수생성의원리 알고리즘설계 특정목적을위한알고리즘 의사난수비트스트림생성을목적으로특정하고유일하게설계된알고리즘 다양한 PRNG 응용에사용 기존의암호알고리즘에기반을둔알고리즘 암호알고리즘은입력을난수로만드는효과가있음 대칭블록암호 : 7.3절 비대칭암호 : 10장 해쉬함수와메시지인증코드 : 12장
7.2 의사난수생성기 선형합동생성기 (Linear congruential generator) Lehmer에의해처음제안된알고리즘혹은 Park-Miller Random Number Generator라고함선형합동방법 m is prime number or power of prime number. m>0 0<a<m 0 c<m 0 X0<m 법 (modulus) 승수 (multiplier) 증분 (increment) 초기치혹은 seed X0 m a c Xn+1 = (axn+c)mod m a, c 및 m 값의선정은좋은난수생성기의개발에중요 난수생성기의평가기준 T1 : 난수생성함수는최대생성주기를가져야한다. 즉, 함수는반복되기전에 0 과 m 사이의모든값을생성해야한다. T2 : 생성된수열은랜덤하게보여야한다. T3 : 함수는 32 비트연산을효율적으로수행해야한다.
7.2 의사난수생성기 생성된수의노출가능성 공격자가선형합동알고리즘사용과파라미터를알경우, 알고리즘에의해생성된수를하나만알아도나머지수를모두알수있게됨 선형합동알고리즘의사용여부를안다면, 생성된수의순서만으로도파라미터를알아낼수있음 해결방법 내부시스템클럭사용 매번 ( 현재의클럭값 mod m) 을새로운 seed 로하여생성 현재클럭값을난수에더하여 mod m 의값을사용
7.2 의사난수생성기 Blum Blum Shub 생성기 개발자들의이름에서유래 [BLUM86] 어떠한특정목적의알고리즘에서도암호학적강도를증명하는가장강력하게통용되는수단 암호학적으로안전한의사난수비트생성기로불림 CSPRBG : Cryptographically Secure Pseudo Random Bit Generator Iterative equation 에서 least significant bit 사용 Is unpredictable given any run of bits Slow, since very large numbers must be used Two slow for cipher use, good for key generation. n 의소인수분해문제에대한어려움에기반 n 이주어졌을때, n 의두소수인수 p 와 q 를알아야함 p q 3(mod 4) n = p q X0 = S 2 mod n for i = 1 to Xi = (Xi-1) 2 mod n Bi = Xi mod 2 gcd(n, s)=1, s 선정 ( 서로소 )
7.2 의사난수생성기 BBS 생성기의연산예 n = 192648 = 383 503 seed s = 101355 i X i B i 0 20749 1 143135 1 2 177671 1 3 97048 0 4 89992 0 5 174051 1 6 80649 1 7 45663 1 8 69442 0 9 186894 0 I X i B i 11 137922 0 12 123175 1 13 8630 0 14 114386 0 15 14863 1 16 133015 1 17 106065 1 18 45870 0 19 137171 1 20 48060 0 10 177046 0
Using Block Ciphers as PRNGs for cryptographic applications, we can use a block cipher to generate random numbers It is used for creating session keys from master key Counter Mode X i = E Km [i] A counter with period N provides input to the encryption logic For example, if 56-bit DES keys are to be produced, then a counter with period 2 56 can be used. After each key is produced, the counter is incremented by one. Thus, the pseudorandom numbers produced < Pseudorandom Number Generation from a counter> 14
ANSI X9.17 PRG Input: Keys: Output: Two pseudorandom inputs drive the generator. One is a 64-bit representation of the current date and time, which is updated on each number generation. The other is a 64-bit seed value; this is initialized to some arbitrary value and is updated during the generation process. The generator makes use of three triple DES encryption modules All three make use of the same pair of 56-bit keys, which must be kept secret and are used only for pseudorandom number generation. The output consists of a 64-bit pseudorandom number and a 64- bit seed value. 15
ANSI X9.17 PRG DTi : current Data & Time V i : seed value R i : Pseudorandom number (output) K 1,K 2 : DES Keys (in this example, Triple-DES keys) 1. Compute I = DES K (DT i ) 2. Output R i =DES K (I xor V i ) 64 bits Update the seed Vi to V i+1 =DES K (Ri xor I) EDE Triple DES(Enc-Dec-Enc.) X9.17 will be improved by using AES! 16
7.3 블록암호를사용한의사난수생성 PRNG 성능실험 Key : cfb0ef3108d49cc4562d5810b0a9af60 V : 4c89af496176b728ed1e2ea8ba27f5a4 OFB 를이용한 PRNG 의결과예 CTR 을이용한 PRNG 의결과예 Output Block Fraction of One Bit Fraction of Bits that Match with Preceding Block Output Block Fraction of One Bit Fraction of Bits that Match with Preceding Block 1786f4c7ff6e291dbdfdd90ec3453176 0.57-5e17b22b14677a4d66890f87565eae64 0.51 0.52 fd18284ac82251dfb3aa62c326cd46cc 0.47 0.54 c8e545198a758ef5dd86b41946389bd5 0.50 0.44 fe7bae0e23019542962e2c52d215a2e3 0.47 0.48 14fdf5ec99469598ae0379492803accd 0.49 0.52 6aeca972e5a3ef17bd1a1b775fc8b929 0.57 0.48 f7e97badf359d128f00d9b4ae323bd64 0.55 0.45 1786f4c7ff6e291dbdfdd90ec3453176 0.57-60809669a3e092a01b463472fdcae420 0.41 0.41 d4e6e170b46b0573eedf88ee39bff33d 0.59 0.45 5f8fcfc5deca18ea246785d7fabc76f8 0.59 0.52 90e63ed27bb07868c753545bdd57ee28 0.53 0.52 0125856fdf4a17f747c7833695c52235 0.50 0.47 f4be2d179b0f2548fd748c8fc7c81990 0.51 0.48 1151fc48f90eebac658a3911515c3c66 0.47 0.45
7.6 진난수생성기 엔트로피소스 진난수생성기는임의성을만들기위해비결정적소스사용 예측불가능한자연계의처리과정들을측정하는방법사용 전리방사선의펄스탐지기, 가스방전광, 누전축전기 인텔 [JUN99] 사용되지않는저항기들사이에서측정된전압을증폭시켜열잡음을샘플링하는상업화된칩개발 임의성의소스후보 [RFC 4086] 음향 / 영상입력 실세계의아날로그소스를디지털화하는입력들을가지고작동 디스크드라이브 환경에따라회전속도가랜덤하게변동되는것을측정
Natural Random Noise best source is natural randomness in real world find a regular but random event and monitor do generally need special h/w to do this eg. radiation counters, radio noise, audio noise, thermal noise in diodes, leaky capacitors, mercury discharge tubes etc starting to see such h/w in new CPU's problems of bias or uneven distribution in signal have to compensate for this when sample and use best to only use a few noisiest bits from each sample 19
7.6 진난수생성기 편향 (skew) deskewing 기법 ( 편향보정기법 ) 0 또는 1 중한쪽으로편향된출력물이생성될가능성존재 이를감소시키거나없애기위한기법 해쉬함수를이용 (MD5, SHA-1 등 ) 운영체제는난수를생성하는내장형메커니즘제공 리눅스는 4 개의엔트로피소스 ( 키보드, 마우스, 디스크 I/O 연산, 특정인터럽트 ) 를사용하여버퍼풀입력 / 저장하고, 이중일정수를선택하여 SHA-1 해쉬함수로연산함
Next We will study more on Number Theory 21
Q&A 22