Accelerated implementation for testing IID assumption of NIST SP 800-90B using GPU

Yewon Kim; Yongjin Yeom

doi:10.7717/peerj-cs.404

Accelerated implementation for testing IID assumption of NIST SP 800-90B using GPU

PeerJ Comput Sci. 2021 Mar 8:7:e404. doi: 10.7717/peerj-cs.404. eCollection 2021.

Authors

Yewon Kim¹, Yongjin Yeom^{1

2}

Affiliations

¹ Department of Financial Information Security, Kookmin University, Seoul, South Korea.
² Department of Information Security, Cryptology, and Mathematics, Kookmin University, Seoul, South Korea.

Abstract

In cryptosystems and cryptographic modules, insufficient entropy of the noise sources that serve as the input into random number generator (RNG) may cause serious damage, such as compromising private keys. Therefore, it is necessary to estimate the entropy of the noise source as precisely as possible. The National Institute of Standards and Technology (NIST) published a standard document known as Special Publication (SP) 800-90B, which describes the method for estimating the entropy of the noise source that is the input into an RNG. The NIST offers two programs for running the entropy estimation process of SP 800-90B, which are written in Python and C++. The running time for estimating the entropy is more than one hour for each noise source. An RNG tends to use several noise sources in each operating system supported, and the noise sources are affected by the environment. Therefore, the NIST program should be run several times to analyze the security of RNG. The NIST estimation runtimes are a burden for developers as well as evaluators working for the Cryptographic Module Validation Program. In this study, we propose a GPU-based parallel implementation of the most time-consuming part of the entropy estimation, namely the independent and identically distributed (IID) assumption testing process. To achieve maximal GPU performance, we propose a scalable method that adjusts the optimal size of the global memory allocations depending on GPU capability and balances the workload between streaming multiprocessors. Our GPU-based implementation excluded one statistical test, which is not suitable for GPU implementation. We propose a hybrid CPU/GPU implementation that consists of our GPU-based program and the excluded statistical test that runs using OpenMP. The experimental results demonstrate that our method is about 3 to 25 times faster than that of the NIST package.

Keywords: Entropy estimator; GPU computing; NIST SP 800-90B; Parallel processing; Random Number Generator.

Grants and funding

This work was supported by an Institute for Information & Communications Technology Promotion (IITP) grant funded by the Korean Government (MSIT) (No. 2014-6-00908, Research on the Security of Random Number Generators and Embedded Devices). The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.