Kim Yewon, Yeom Yongjin
Department of Financial Information Security, Kookmin University, Seoul, South Korea.
Department of Information Security, Cryptology, and Mathematics, Kookmin University, Seoul, South Korea.
PeerJ Comput Sci. 2021 Mar 8;7:e404. doi: 10.7717/peerj-cs.404. eCollection 2021.
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.
在密码系统和加密模块中，作为随机数生成器（RNG）输入的噪声源熵不足可能会造成严重损害，例如危及私钥安全。因此，有必要尽可能精确地估计噪声源的熵。美国国家标准与技术研究院（NIST）发布了一份名为《特殊出版物》（SP）800-90B的标准文档，其中描述了估计作为RNG输入的噪声源熵的方法。NIST提供了两个用于运行SP 800-90B熵估计过程的程序，它们分别用Python和C++编写。对于每个噪声源，估计熵的运行时间超过一小时。在每个支持的操作系统中，RNG往往会使用多个噪声源，并且噪声源会受到环境影响。因此，应多次运行NIST程序以分析RNG的安全性。NIST估计运行时间对开发者以及参与加密模块验证计划的评估人员来说都是一项负担。在本研究中，我们提出了一种基于GPU的并行实现方法，用于熵估计中最耗时的部分，即独立同分布（IID）假设检验过程。为了实现最大的GPU性能，我们提出了一种可扩展的方法，该方法根据GPU能力调整全局内存分配的最佳大小，并在流多处理器之间平衡工作负载。我们基于GPU的实现排除了一项不适合GPU实现的统计测试。我们提出了一种CPU/GPU混合实现方法，它由我们基于GPU的程序和使用OpenMP运行的被排除的统计测试组成。实验结果表明，我们的方法比NIST软件包快约3至25倍。
