Randomness Testing Methods for TRNG Circuits over Embedded Security Systems

Abstract

임베디드 시스템 상에서, RFID나 USN과 같은 환경에서 암호 알고리즘은 정보 보호에 핵심적인 역할을 한다. 암호 알고리즘을 실행시키는 데 필요한 기본 요소는 키(Key)이다. 키는 정보를 암호화 복호화 시키는 데 반드시 필요한 요소이지만, 이 키가 외부 침입자에 알려질 경우에는 모든 정보가 외부로 노출되기 때문에 키가 외부에 알려지지 않도록 하는 것 또한 중요하다. 보안을 위해서 사용되는 방법이 키 값을 랜덤 수열로 정의하는 것이다. 여러 의사 랜덤 수 생성 알고리즘이 있지만, 키 값으로 사용하기 위해서는 순수 랜덤 수 생성기를 통해 생성된 순수 랜덤 수열이 필요하고, 이에 순수 랜덤 수 생성기에 대한 연구가 활발히 진행되고 있다. 랜덤 수 생성기의 검증이란 랜덤 생성기를 통해 생성된 수열의 randomness (랜덤성)을 검증하는 것이다. 랜덤 수 생성기를 검증하는 방법으로는, NIST (National Institute of Standards and Technology)에서 1994년과 2000년도에 발표한 [3과 4]에서 소개한 4가지 검증 방법과, 2001년에 발표한 [5]에서 소개한 16가지 검증 방법이 있다. 암호 알고리즘을 기반으로 하는 의사 랜덤 수 생성기 (PRNG, Pseudo-Random Number Generator)의 randomness를 판단하는 검증 방법을 제시하고 있기 때문에, 이 검증 방법으로 순수 랜덤 수 생성기(TRNG, True Random Number Generator)의 randomness를 판단하는 데에는 부족함이 있다. 이 논문에서는 의사 랜덤 수 생성기와 순수 랜덤 수 생성기를 구별 할 수 있고, 나아가 순수 랜덤 수 생성기의 randomness를 판별해 낼 수 있는 검증 방법을 제시하고자 한다. 순수 랜덤 수와 의사 랜덤 수의 가장 큰 차이점인 주기성을 근사 주기 (Approximate Period)를 통하여 접근하였다. 기존의 랜덤 수 생성기가 정확한 주기 (Exact Period)에 기반하여 주기성을 측정하였고, 그 때 사용된 패턴들의 길이는 8 비트로 실험에 사용되는 랜덤 수열의 길이보다 매우 짧았다. 이 논문에서는 일정 비트의 오차 내에서 존재하는 비교적 긴 길이의 근사 주기를 측정하여 의사 랜덤 수 생성기의 주기성을 밝혀낼 수 있는 알고리즘을 연구하였다. 근사 주기의 척도인 해밍 거리 (Hamming Distance)와 편집 거리 (Edit Distance)를 이용하여 의사 랜덤 수 생성기와 순수 랜덤 수 생성기의 근사 주기를 측정할 수 있는 알고리즘과 실험 결과를 제시하였다.; In embedded systems, RFID (Radio Frequency IDentification) and USN (Ubiquitous Sensor Networks), cryptographic algorithms take a major roll of security. Key management is the essential part of encryption and decryption in cryptographic algorithms. A Key should be kept in secret because the information is no longer safe when key is open to public. To keep the information safely and to strengthen the security, keys are used as random sequence generated random numbers. There are many kinds of random number generators, but to use the number as a key, true random number generators are recommended. Testing a random number generator is to test randomness of a random sequence generated by random number generator. NIST (National Institute of Standardization and Technology) have released several test suites for random number generators: four testing schemes are introduced in [3 and 4] in 1994 and 2000, and sixteen testing schemes are provided in [5] published in 2001. Since they are intended for testing randomness of pseudorandom number generators based on cryptographic algorithms, these testing schemes are not helpful on testing randomness of true random number generators. Furthermore, these cannot differentiate pseudorandom and true random number generators. In this thesis, new randomness testing schemes are proposed to test randomness of true random number generators and to differentiate pseudorandom and true random number generators. The main idea of proposed testing schemes are using approximate periods, since periodicity is the major difference between pseudorandom and true random number generators. Previous randomness test suites are only concerned on the exact pattern matching or exact period, and they used patterns of lengths less than or equal to 8-bits, which is considerably short. Proposed algorithms will contain patterns of lengths longer than 8-bits and will measure periodicities based on approximated periods. This thesis contains the algorithms to measure the approximate period of pseudorandom and true number generators based on the hamming and edit distance functions. Moreover, the experimental results on true random number generators and cryptographic algorithms AES and DES are presented.