난수발생기가 생성하는 난수는 현대 암호 시스템과 암호모듈에서 사용하는 암호키와 같은 보안 매개변수를 구성하는 주요 요소이다. 난수발생기는 결정론적 알고리즘으로 구성되어 있으므로, 난수발생기가 예측 가능한 잡음원을 입력받아 생성한 난수는 예측될 가능성이 커진다. 잡음원으로부터 충분하지 않은 ...
난수발생기가 생성하는 난수는 현대 암호 시스템과 암호모듈에서 사용하는 암호키와 같은 보안 매개변수를 구성하는 주요 요소이다. 난수발생기는 결정론적 알고리즘으로 구성되어 있으므로, 난수발생기가 예측 가능한 잡음원을 입력받아 생성한 난수는 예측될 가능성이 커진다. 잡음원으로부터 충분하지 않은 엔트로피를 수집함으로 인해 난수가 예측되어 암호 시스템의 안전성이 저하된 연구 결과는 충분히 존재한다. 그러므로 난수발생기는 입력으로 사용하는 잡음원의 엔트로피를 가능한 한 정확하게 추정해야 하고, 잡음원으로부터 충분한 엔트로피를 수집해야 한다. 또한, 기계적 또는 환경적 변화로 인해 잡음원으로부터 엔트로피를 수집하지 못하게 되는 경우를 고려하여 난수발생기는 한 가지 이상의 잡음원을 입력으로 사용한다. 지터 잡음원은 CPU의 고해상도 타이머를 이용하여 측정한 명령어 집합의 실행 시간의 변동성에 기반을 둔다. 지터 잡음원을 난수발생기의 입력으로 사용하는 사례가 많아지고 있다. 대표적인 사용처는 Google이 2016년부터 개발하고 있으며 현재 상용화를 준비하고 있는 퓨시아 운영체제와 그 기반인 지르콘커널의 난수발생기이다. 또한, 운영체제별 잡음원의 수집 방법에 관한 국내 TTA 표준문서가 2020년에 개정되면서 윈도우와 리눅스 운영체제에서 수집할 수 있는 잡음원에 지터 잡음원이 추가되었다. 지터 잡음원에 대한 활용도가 높아지지만, 사용되고 있는 지터 잡음원에 대한 안전성을 분석하는 연구가 부족하다. 따라서 본 논문에서는 지터 잡음원에 중점을 두고 퓨시아 운영체제와 지르콘 커널의 난수발생기에 대한 안전성을 분석하고, 취약점을 이용한 공격 시나리오를 제시한다. 또한, 다양한 환경에서 엔트로피를 제공할 수 있는 지터 잡음원을 설계하고 확률론적 모델을 제시한다. 그리고 다양한 환경에서 설계한 지터 잡음원에 대한 최소 엔트로피와 효율성을 정량화한다. 컴퓨터 그래픽과 이미지 처리를 가속화하기 위해 설계된 GPU가 일반 계산에 사용할 수 있게 되면서 GPU를 암호학적으로 활용하는 연구가 진행되고 있다. 본 논문에서는 격자 기반 양자 내성 암호와 잡음원의 엔트로피 평가 방법에 대해 CUDA를 사용하여 GPU에서 병렬 고속화하는 방법을 연구한다. 격자 기반 양자 내성 암호인 FrodoKEM은 미국 NIST가 진행하고 있는 양자 내성 암호 표준화 공모사업의 3라운드에서 대체 후보로 선정되었으며, 다양한 환경에서 성능과 구현 기법에 대한 분석이 필요하다. 또한, 독일 BSI가 2020년에 개정한 암호학적 메커니즘 기술 지침에 따르면 양자 내성 암호로 FrodoKEM을 사용하는 것이 권장된다. 따라서 본 논문에서는 FrodoKEM을 구성하는 주요 요소가 GPU에서 병렬 고속화되기에 적절한지에 대해 분석한다. 난수발생기의 안전성을 분석할 때 입력인 잡음원에 대한 엔트로피를 추정해야 한다. 미국 NIST의 SP 800-90B 표준문서에 작성된 엔트로피 추정 방법이 대표적으로 사용된다. 또한, NIST는 하나의 잡음원에 대해 SP 800-90B의 방법으로 엔트로피를 추정하는 프로그램을 제공한다. 하지만, 엔트로피를 정확하게 추정하기 위해 잡음원이 IID인지를 판별하는 과정인 IID 테스트가 프로그램 동작 시간의 95% 이상을 차지한다. 난수발생기의 안전성을 분석하는 데에 효율성을 높이기 위해, 본 논문에서는 CUDA를 사용하여 GPU에서 IID 테스트를 병렬 고속화하는 방법을 제안한다.
난수발생기가 생성하는 난수는 현대 암호 시스템과 암호모듈에서 사용하는 암호키와 같은 보안 매개변수를 구성하는 주요 요소이다. 난수발생기는 결정론적 알고리즘으로 구성되어 있으므로, 난수발생기가 예측 가능한 잡음원을 입력받아 생성한 난수는 예측될 가능성이 커진다. 잡음원으로부터 충분하지 않은 엔트로피를 수집함으로 인해 난수가 예측되어 암호 시스템의 안전성이 저하된 연구 결과는 충분히 존재한다. 그러므로 난수발생기는 입력으로 사용하는 잡음원의 엔트로피를 가능한 한 정확하게 추정해야 하고, 잡음원으로부터 충분한 엔트로피를 수집해야 한다. 또한, 기계적 또는 환경적 변화로 인해 잡음원으로부터 엔트로피를 수집하지 못하게 되는 경우를 고려하여 난수발생기는 한 가지 이상의 잡음원을 입력으로 사용한다. 지터 잡음원은 CPU의 고해상도 타이머를 이용하여 측정한 명령어 집합의 실행 시간의 변동성에 기반을 둔다. 지터 잡음원을 난수발생기의 입력으로 사용하는 사례가 많아지고 있다. 대표적인 사용처는 Google이 2016년부터 개발하고 있으며 현재 상용화를 준비하고 있는 퓨시아 운영체제와 그 기반인 지르콘 커널의 난수발생기이다. 또한, 운영체제별 잡음원의 수집 방법에 관한 국내 TTA 표준문서가 2020년에 개정되면서 윈도우와 리눅스 운영체제에서 수집할 수 있는 잡음원에 지터 잡음원이 추가되었다. 지터 잡음원에 대한 활용도가 높아지지만, 사용되고 있는 지터 잡음원에 대한 안전성을 분석하는 연구가 부족하다. 따라서 본 논문에서는 지터 잡음원에 중점을 두고 퓨시아 운영체제와 지르콘 커널의 난수발생기에 대한 안전성을 분석하고, 취약점을 이용한 공격 시나리오를 제시한다. 또한, 다양한 환경에서 엔트로피를 제공할 수 있는 지터 잡음원을 설계하고 확률론적 모델을 제시한다. 그리고 다양한 환경에서 설계한 지터 잡음원에 대한 최소 엔트로피와 효율성을 정량화한다. 컴퓨터 그래픽과 이미지 처리를 가속화하기 위해 설계된 GPU가 일반 계산에 사용할 수 있게 되면서 GPU를 암호학적으로 활용하는 연구가 진행되고 있다. 본 논문에서는 격자 기반 양자 내성 암호와 잡음원의 엔트로피 평가 방법에 대해 CUDA를 사용하여 GPU에서 병렬 고속화하는 방법을 연구한다. 격자 기반 양자 내성 암호인 FrodoKEM은 미국 NIST가 진행하고 있는 양자 내성 암호 표준화 공모사업의 3라운드에서 대체 후보로 선정되었으며, 다양한 환경에서 성능과 구현 기법에 대한 분석이 필요하다. 또한, 독일 BSI가 2020년에 개정한 암호학적 메커니즘 기술 지침에 따르면 양자 내성 암호로 FrodoKEM을 사용하는 것이 권장된다. 따라서 본 논문에서는 FrodoKEM을 구성하는 주요 요소가 GPU에서 병렬 고속화되기에 적절한지에 대해 분석한다. 난수발생기의 안전성을 분석할 때 입력인 잡음원에 대한 엔트로피를 추정해야 한다. 미국 NIST의 SP 800-90B 표준문서에 작성된 엔트로피 추정 방법이 대표적으로 사용된다. 또한, NIST는 하나의 잡음원에 대해 SP 800-90B의 방법으로 엔트로피를 추정하는 프로그램을 제공한다. 하지만, 엔트로피를 정확하게 추정하기 위해 잡음원이 IID인지를 판별하는 과정인 IID 테스트가 프로그램 동작 시간의 95% 이상을 차지한다. 난수발생기의 안전성을 분석하는 데에 효율성을 높이기 위해, 본 논문에서는 CUDA를 사용하여 GPU에서 IID 테스트를 병렬 고속화하는 방법을 제안한다.
Random numbers generated by a random number generator are the main components of security parameters such as encryption keys used in modern cryptographic systems and cryptographic modules. The random number generator is composed of deterministic algorithms. And hence the probability of predicting ra...
Random numbers generated by a random number generator are the main components of security parameters such as encryption keys used in modern cryptographic systems and cryptographic modules. The random number generator is composed of deterministic algorithms. And hence the probability of predicting random numbers generated by the random number generator increases when input a predicable noise source. There are enough research results in which random numbers are predicted due to the collection of insufficient entropy from the noise source and so the security of cryptographic systems is lowered. Therefore, the random number generator should estimate the entropy of the noise source used as an input as accurately as possible and collect sufficient entropy from the noise source. In addition, the random number generator uses one or more noise sources as input, considering the case where entropy cannot be collected from the noise source due to mechanical or environmental change. A jitter noise source is based on the variability in the execution time of the instruction set as measured using the high-resolution timer of the CPU. There are increasing the use-cases of the jitter noise source as the input of the random number generator. A typical use-case is the random number generator of the Fuchsia operating system and the Zircon kernel, which Google has been developing since 2016 and currently preparing for commercialization. In addition, when the domestic TTA standard document for the collection method of noise sources on each operating system was revised in 2020, the jitter noise source was added to the noise sources that can be collected in Windows and Linux operating systems. Although the application of jitter noise sources is increasing, research on the security of the jitter noise sources in use is lacking. Therefore, this paper analyzes the security of the random number generator of the Fuchsia operating system and Zircon kernel, focusing on the jitter noise source, and presents an attack scenario using the vulnerability. In addition, we design jitter noise sources that can provide entropy in various environments, and give a stochastic model. And we quantify the min-entropy and efficiency for the jitter noise source designed in multiple environments. As GPUs designed to accelerate computer graphics and image processing can be used for general computation, research is underway to utilize GPUs cryptographically. In this paper, we study methods for parallel implementation on GPU using CUDA for lattice-based post-quantum cryptography and entropy estimation of the noise source. FrodoKEM, lattice-based post-quantum cryptography, was selected as an alternate candidate on the third round of the post-quantum cryptography standardization project conducted by NIST in the United States. It is necessary to analyze performance and implementation techniques in various environments. In addition, the use of FrodoKEM as post-quantum cryptography is recommended according to the Cryptographic Mechanism Technical Guidelines revised in 2020 by BSI in Germany. Therefore, this paper analyzes whether the main elements constituting FrodoKEM are suitable for parallel implementation on GPU. When analyzing the security of the random number generator, it is necessary to estimate the entropy for the input noise source. The entropy estimation method written in the SP 800-90B standard document of NIST in the US is typically used. In addition, NIST provides a program for estimating entropy with the method of SP 800-90B for one noise source. However, to accurately estimate entropy, the IID test, which is the process of determining whether the noise source is an IID, occupies more than 95% of the operation time of the program. In order to increase the efficiency in analyzing the security of the random number generator, we propose a parallel implementation of the IID test on GPU using CUDA.
Random numbers generated by a random number generator are the main components of security parameters such as encryption keys used in modern cryptographic systems and cryptographic modules. The random number generator is composed of deterministic algorithms. And hence the probability of predicting random numbers generated by the random number generator increases when input a predicable noise source. There are enough research results in which random numbers are predicted due to the collection of insufficient entropy from the noise source and so the security of cryptographic systems is lowered. Therefore, the random number generator should estimate the entropy of the noise source used as an input as accurately as possible and collect sufficient entropy from the noise source. In addition, the random number generator uses one or more noise sources as input, considering the case where entropy cannot be collected from the noise source due to mechanical or environmental change. A jitter noise source is based on the variability in the execution time of the instruction set as measured using the high-resolution timer of the CPU. There are increasing the use-cases of the jitter noise source as the input of the random number generator. A typical use-case is the random number generator of the Fuchsia operating system and the Zircon kernel, which Google has been developing since 2016 and currently preparing for commercialization. In addition, when the domestic TTA standard document for the collection method of noise sources on each operating system was revised in 2020, the jitter noise source was added to the noise sources that can be collected in Windows and Linux operating systems. Although the application of jitter noise sources is increasing, research on the security of the jitter noise sources in use is lacking. Therefore, this paper analyzes the security of the random number generator of the Fuchsia operating system and Zircon kernel, focusing on the jitter noise source, and presents an attack scenario using the vulnerability. In addition, we design jitter noise sources that can provide entropy in various environments, and give a stochastic model. And we quantify the min-entropy and efficiency for the jitter noise source designed in multiple environments. As GPUs designed to accelerate computer graphics and image processing can be used for general computation, research is underway to utilize GPUs cryptographically. In this paper, we study methods for parallel implementation on GPU using CUDA for lattice-based post-quantum cryptography and entropy estimation of the noise source. FrodoKEM, lattice-based post-quantum cryptography, was selected as an alternate candidate on the third round of the post-quantum cryptography standardization project conducted by NIST in the United States. It is necessary to analyze performance and implementation techniques in various environments. In addition, the use of FrodoKEM as post-quantum cryptography is recommended according to the Cryptographic Mechanism Technical Guidelines revised in 2020 by BSI in Germany. Therefore, this paper analyzes whether the main elements constituting FrodoKEM are suitable for parallel implementation on GPU. When analyzing the security of the random number generator, it is necessary to estimate the entropy for the input noise source. The entropy estimation method written in the SP 800-90B standard document of NIST in the US is typically used. In addition, NIST provides a program for estimating entropy with the method of SP 800-90B for one noise source. However, to accurately estimate entropy, the IID test, which is the process of determining whether the noise source is an IID, occupies more than 95% of the operation time of the program. In order to increase the efficiency in analyzing the security of the random number generator, we propose a parallel implementation of the IID test on GPU using CUDA.
주제어
#난수발생기 잡음원 지터 잡음원 Fuchsia Zircon 안전성 평가 GPU CUDA 양자내성암호 엔트로피 추정
학위논문 정보
저자
김예원
학위수여기관
국민대학교 일반대학원
학위구분
국내박사
학과
정보융합보안전공
지도교수
염용진
발행연도
2022
총페이지
xi, 138
키워드
난수발생기 잡음원 지터 잡음원 Fuchsia Zircon 안전성 평가 GPU CUDA 양자내성암호 엔트로피 추정
※ AI-Helper는 부적절한 답변을 할 수 있습니다.