On Random Number Generation for Kernel Applications

• Autorzy: Abhishek Kunal , Dharma Prakash Raj E.George

Identyfikatory

DOI

10.3233/FI-222111

• Języki publikacji: EN

Abstrakty

EN

An operating system kernel uses cryptographically secure pseudorandom number generator (CSPRNG) for creating address space layout randomization (ASLR) offsets to protect memory addresses of processes from exploitation, storing users' passwords securely and creating cryptographic keys. However, at present, popular kernel CSPRNGs such as Yarrow, Fortuna and /dev/(u)random which are used by MacOS/iOS/FreeBSD, Windows and Linux/Android kernels respectively lack the very crucial property of non-reproducibility of their generated bitstreams which is used to nullify the scope of predicting the bitstream. This paper proposes a CSPRNG called Cryptographically Secure Pseudorandom Number Generator for Kernel Applications (KCS-PRNG) which generates non-reproducible bitstreams. The proposed KCS-PRNG presents an efficient design uniquely configured with two new non-standard and verified elliptic curves and clock-controlled Linear Feedback Shift Registers (LFSRs) and a novel method to consistently generate non-reproducible random bitstreams of arbitrary lengths. The generated bitstreams are statistically indistinguishable from true random bitstreams and provably secure, resilient to important attacks, exhibits backward and forward secrecy, exhibits exponential linear complexity, large period and huge key space.

Słowa kluczowe

EN

CSPRNG; elliptic curve; Kernel Applications; LFSR; Random Number Generator

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: Vol. 185, nr 4
• Strony: 285--311
• Opis fizyczny: Bibliogr. 45 poz., rys. tab.

Twórcy

autor

Abhishek Kunal

• Society for Electronic Transactions and Security (SETS), Chennai, India.

autor

Dharma Prakash Raj E.George

• School of Computer Sciences, Engineering and Applications, Bharathidasan University, Tiruchirappalli, India.

Bibliografia

• [1] Koc¸ C¸ K. About cryptographic engineering. In: Cryptographic engineering, pp. 1-4. Springer, 2009. doi:10.1007/978-0-387-71817-0_1.
• [2] Marco-Gisbert H, Ripoll Ripoll I. Address space layout randomization next generation. Applied Sciences, 2019. 9(14):2928. doi:10.3390/app9142928.
• [3] Tanenbaum AS, Woodhull AS. Operating Systems Design and Implementation (3rd Edition) (Prentice Hall Software Series). Prentice Hall, 2006. ISBN:0131429388.
• [4] Dodis Y, Shamir A, Stephens-Davidowitz N, Wichs D. How to eat your entropy and have it too: Optimal recovery strategies for compromised RNGs. Algorithmica, 2017. 79(4):1196-1232. doi:10.1007/978-3-662-44381-1 3.
• [5] Dörre F, Klebanov V. Pseudo-random number generator verification: A case study. In: VSSTE. Springer, 2015 pp. 61-72. doi:10.1007/978-3-319-29613-5_4.
• 6] Alhadawi HS, Zolkipli MF, Ismail SM, Lambi´c D. Designing a pseudorandom bit generator based on LFSRs and a discrete chaotic map. Cryptologia, 2019. 43(3):190-211. doi:10.1080/01611194.2018.1548390.
• [7] Anandakumar NN, Sanadhya SK, Hashmi MS. FPGA-based true random number generation using programmable delays in oscillator-rings. IEEE Transactions on Circuits and Systems II: Express Briefs, 2019. 67(3):570-574. doi:10.1109/TCSII.2019.2919891.
• [8] Silberschatz A. Instructor’s Manual to Accompany: Operating System Concepts. 2015.
• [9] Schneier B. Applied cryptography: protocols, algorithms, and source code in C. john wiley & sons, Second edition, 2007.
• [10] Viega J. Practical random number generation in software. In: 19th Annual Computer Security Applications Conference, 2003. Proceedings. IEEE, 2003 pp. 129-140.
• [11] Dodis Y, Pointcheval D, Ruhault S, Vergniaud D, Wichs D. Security analysis of pseudo-random number generators with input: /dev/random is not robust. In: Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security. 2013 pp. 647-658. doi:10.1145/2508859.2516653.
• [12] Kelsey J, Schneier B, Ferguson N. Yarrow-160: Notes on the design and analysis of the yarrow cryptographic pseudorandom number generator. In: International Workshop on Selected Areas in Cryptography. Springer, 1999 pp. 13-33. doi:10.1007/3-540-46513-8_2.
• [13] Ferguson N, Schneier B, Kohno T. Cryptography engineering: design principles and practical applications. John Wiley & Sons, 2011. ISBN-10:0470474246, 13:978-0470474242.
• [14] McEvoy R, Curran J, Cotter P, Murphy C. Fortuna: cryptographically secure pseudo-random number generation in software and hardware. In: 2006 IET Irish Signals and Systems Conference. IET, 2006 pp. 457-462. ISBN-0-86341-665-9.
• [15] Gong G, Lam CC. Linear recursive sequences over elliptic curves. In: Sequences and their applications, pp. 182-196. Springer, 2002. doi:10.1007/978-1-4471-0673-9_13.
• [16] Kerry CF, Gallagher PD. Digital signature standard (DSS). FIPS PUB, 2013. pp. 186-4.
• [17] Brainpool E. Brainpool Standard Curves and Curve Generation, 2005.
• [18] Bernstein DJ, Chou T, Chuengsatiansup C, H¨ulsing A, Lambooij E, Lange T, Niederhagen R, Vredendaal Cv. How to Manipulate Curve Standards: A White Paper for the Black Hat http://bada55. cr. yp. to. In: International Conference on Research in Security Standardisation. Springer, 2015 pp. 109-139. doi:10.1007/978-3-319-27152-1_6.
• [19] Mukhopadhyay S, Sarkar P. Application of LFSRs for parallel sequence generation in cryptologic algorithms. In: International Conference on Computational Science and Its Applications. Springer, 2006 pp. 436-445. doi:10.1007/11751595_47.
• [20] Rajski J, Tyszer J. Primitive polynomials over GF (2) of degree up to 660 with uniformly distributed coefficients. Journal of Electronic testing, 2003. 19(6):645-657. doi:10.1023/A:1027422805851.
• [21] Menezes AJ, Van Oorschot PC, Vanstone SA. Handbook of applied cryptography. CRC press, 2018. ISBN-0-8493-8523-7.
• [22] Teo SG. Analysis of nonlinear sequences and streamciphers. Ph.D. thesis, Queensland University of Technology, 2013.
• [23] L’ecuyer P, Simard R. TestU01: AC library for empirical testing of random number generators. ACM Transactions on Mathematical Software (TOMS), 2007. 33(4):1-40. doi:10.1145/1268776.1268777.
• [24] L’Ecuyer P, Simard R. TestU01: A Software Library in ANSI C for Empirical Testing of Random Number Generators–Users Guide, Compact Version. 2013. doi:10.1145/1268776.1268777.
• [25] Walker J. ENT: a pseudorandom number sequence test program. Software and documentation available at/www. fourmilab. ch/random/S, 2008.
• [26] II E, Sym D. ECRYPT II. 2010.
• [27] Klein A. Cross layer attacks and how to use them (for dns cache poisoning, device tracking and more). In: 2021 IEEE Symposium on Security and Privacy (SP). IEEE, 2021 pp. 1179-1196. doi:10.1109/SP40001.2021.00054.
• [28] Bassham III LE, Rukhin AL, Soto J, Nechvatal JR, Smid ME, Barker EB, Leigh SD, Levenson M, Vangel M, Banks DL, et al. Sp 800-22 rev. 1a. a statistical test suite for random and pseudorandom number generators for cryptographic applications, 2010.
• [29] Marsaglia G. DIEHARD Test suite. 1998. 8(01):2014. Online:http://www.stat.fsu.edu/pub/diehard/.Lastevisited.
• [30] Bhattacharjee K, Maity K, Das S. A search for good pseudo-random number generators: Survey and empirical studies. 2018. arXiv preprint arXiv:1811.04035.
• [31] Lavasani A, Eghlidos T. Practical next bit test for evaluating pseudorandom sequences. 2009. ID:37894176.
• [32] GG Rose AG, Xiao L. Cryptographically secure pseudo-random number generator, U.S. Patent, 2011.
• [33] Kelsey J, Schneier B, Wagner D, Hall C. Cryptanalytic attacks on pseudorandom numer generators. In: International workshop on fast software encryption. Springer, 1998 pp. 168-188. doi:10.1007/3-540-69710-1 12.
• [34] Bernstein DJ, Lange T, et al. SafeCurves: choosing safe curves for elliptic curve cryptography. 2014. 9. URL https://safecurves.cr.yp.to.Citationsinthisdocument.
• [35] Shumow D, Ferguson N. On the possibility of a back door in the NIST SP800-90 Dual Ec Prng. In: Proc. Crypto, volume 7. 2007 .
• [36] Hales TC. The NSA back door to NIST. Notices of the AMS, 2013. 61(2):190-192. doi:10.1090/NOTI1078.
• [37] Bernstein DJ, Lange T. Security dangers of the NIST curves. In: Invited talk, International State of the Art Cryptography Workshop, Athens, Greece. 2013.
• [38] Konstantinou E, Kontogeorgis A, Stamatiou YC, Zaroliagis C. On the efficient generation of prime-order elliptic curves. Journal of cryptology, 2010. 23(3):477-503. doi:10.1007/s00145-009-9037-2. [39] Menezes AJ, Okamoto T, Vanstone SA. Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Transactions on information Theory, 1993. 39(5):1639-1646. doi:10.1109/18.259647.
• [40] Cheng Q. Hard problems of algebraic geometry codes. IEEE Transactions on Information Theory, 2008. 54(1):402-406.
• [41] Bos JW, Costello C, Longa P, Naehrig M. Selecting elliptic curves for cryptography: an efficiency and security analysis. Journal of Cryptographic Engineering, 2016. 6(4):259-286. doi:10.1007/s13389-015-0097-y.
• [42] Smart NP. The discrete logarithm problem on elliptic curves of trace one. Journal of cryptology, 1999. 12(3):193-196. doi:10.1007/s001459900052.
• [43] Koblitz N, Menezes A, Vanstone S. Guide to elliptic curve cryptography. 2004. doi:10.1007/b97644.
• [44] Abhishek K, Raj EGDP. Computation of Trusted Short Weierstrass Elliptic Curves for Cryptography. Cybernetics and Information Technologies, 2021. 21(2):70-88. doi:10.2478/cait-2021-0020.
• [45] Röck A. Pseudorandom number generators for cryptographic applications. 2005. doi:10.1007/0-387-23483-7_330.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)