Testing pseudorandom number sensors built in smart cards
DOI:
https://doi.org/10.18372/2310-5461.47.14934Keywords:
Smart cards, algorithms, multidimensional statistics, random sequences, s-chains, cryptography, pseudorandom sequence, statistical testingAbstract
This article explores randomness and how general purpose computers generate it. It also discusses the security requirements that a pseudo-random number generator must satisfy for use in cryptographic applications. And also special attention is paid to the known and new methods of testing random bit sequences. Analyzing the effectiveness of pseudo-random sequence generators is a pressing problem for smart cards when using more advanced methods of encryption and information protection. The available methods show low flexibility and versatility in the means of finding hidden patterns in data. To solve this problem, it is proposed to use algorithms based on multivariate statistics. These algorithms combine all the advantages of statistical methods and are the only alternative for analyzing short and medium-length sequences. The paper considers the scheme of operation of pseudo-random number generators in limited devices. The main requirements for modern smart cards are highlighted. A criterion for checking the randomness of bit sequences of small length (up to 100 bits) is proposed. This approach is appropriate for testing a lightweight pseudo-random number generator in devices with certain resource constraints. The paper presents the compatible distributions of the number of 2-strings and the number of 3-strings of a fixed form of a random bit sequence, which make it possible to carry out a statistical analysis of local sections of this sequence. A possible application of the obtained formulas can be to test the hypothesis of the randomness of the arrangement of zeros and ones in a (0, 1) -sequence of finite length. Research has shown that even with limited resources and a limited entropy environment like a smart card, good quality pseudo-random sequences can be created that can satisfy all the requirements for pseudo-random number generators, even those used for general purpose computers. In the work, the set of statistical tests was expanded to include other tests that are not included in the statistical set of NIST tests, and to analyze the work of the proposed algorithms. The paper presents algorithms for testing a pseudo-random sequence using multivariate statistics to illustrate their possible application in a smart card environment.
References
Овчинников А. И. Тестирование датчиков случайных чисел, встроенных в смарт-карты. Наука, техника и образование. 2014. № 2.
Rankl W., Effing W. Smart Card Handbook. New York, NY, USA: John Wiley & Sons, Inc., 2003. (eng)
Akram R. N, Markantonakis K., Mayes K. Pseudorandom Number Generation in Smart Cards: An Implementation, Performance and Randomness Analysis. 2012 5th International Conference on New Technologies, Mobility and Security (NTMS). 2012. 10.1109/NTMS.2012.6208760. (eng)
Koning Gans G., Hoepman J.-H., Garcia F. D. A Practical Attack on the MIFARE Classic. CARDIS ’08: Proceedings of the 8th IFIP WG 8.8/11.2 international conference on Smart Card Research and Advanced Applications. Springer. 2008. pp. 267–282. (eng)
Garcia D., Koning Gans G., Muijrers R., Rossum P., Verdult R., Schreur R. W., Jacobs B. Dismantling MIFARE Classic,” in ESORICS, 2008, pp. 97–114. (eng)
Nohl K., Evans D., Starbug S., Plotz H. “Reverse-Engineering a ¨ Cryptographic RFID Tag,” in SS’08: Proceedings of the 17th conference on Security symposium. Berkeley, CA, USA: USENIX Association, 2008, pp. 185–193. (eng)
Garcia D., Rossum P., Verdult R., Schreur R. W. “Wirelessly Pickpocketing a Mifare Classic Card,” in SP ’09: Proceedings of the 2009 30th IEEE Symposium on Security and Privacy. Washington, DC, USA: IEEE Computer Society, 2009, pp. 3–15. (eng)
Trichina E., Bucci M., Seta D., Luzzi R. “Supplemental Cryptographic Hardware for Smart Cards,” IEEE Micro, vol. 21, no. 6, 2001. pp. 26–35 (eng)
Bucci M., Germani L., Luzzi R., Trifiletti A., Varanonuovo M. “A High-Speed Oscillator-Based Truly Random Number Source for Cryptographic Applications on a Smart Card IC,” IEEE Trans. Comput., vol. 52, no. 4, 2003. pp. 403–409. (eng)
Hambardzumyan E., Kim Y.-S., Karpinskyy B., “Fast Digital TRNG Based on Metastable Ring Oscillator,” in Cryptographic Hardware and Embedded Systems – CHES 2008, ser. LNCS, E. Oswald and P. Rohatgi, Eds. Springer, August 2008, vol. 5154, pp. 164–180. (eng)
Biham E., Shamir A. “Differential Fault Analysis of Secret Key Cryptosystems,” in CRYPTO ’97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology. London, UK: Springer, 1997, pp. 513–525. (eng)
Boneh D., DeMillo R. A., Lipton R. J. “On the Importance of Checking Cryptographic Protocols for Faults,” in EUROCRYPT’97: Proceedings of the 16th annual international conference on Theory and application of cryptographic techniques. Springer, 1997, pp. 37–51 (eng)
Common “Criteria for Information Technology Security Evaluation”, Part 1: Introduction and general model, Part 2: Security functional requirements, Part 3: Security assurance requirements, Common Criteria Std. Version 3.1, August 2006. [Online]. Available: http: //www.common criteriaportal.org /thecc.html (eng)
“BSI AIS 31: Functionality classes and evaluation methodology for deterministic random number generators,” Certification body of the BSI as part of the certification scheme version 2, 2001. [Online]. Available: https://www.bsi.bund.de/cae/ servlet/contentblob/ 478130/ publicationFile/30547/ais31epdf. (eng)
FIPS 140-2: Security Requirements for Cryptographic Modules. National Institute of Standards and Technology. Washington, DC. 2001. (eng)
Kocher P., Jaffe J., Jun B., “Differential Power Analysis,” Lecture Notes in Computer Science, vol. 1666, 1999. pp. 388–397. (eng)
Chari S., Rao J. R., Rohatgi P. “Template Attacks,” in CHES ’02: Revised Papers from the 4th International Workshop on Cryptographic Hardware and Embedded Systems. London, UK: Springer-Verlag, 2003, pp. 13–28. (eng)
Chari S., Diluoffo V. V., Karger P. A., Palmer E. R., Rabin T., Rao J. R., Rohatgi P., Scherzer H., Steiner M., Toll D. C. “Designing a Side Channel Resistant Random Number Generator,” in Smart Card Research and Advanced Application, 9th IFIP WG 8.8/11.2 International Conference, CARDIS 2010, D. Gollmann, J.-L. Lanet, and J. IguchiCartigny, Eds. Springer, April 2010, pp. 49–64. (eng)
“BSI AIS 20: Functionality classes and evaluation methodology for deterministic random number generators,” Tech. Rep. version 2, December, 1999. [Online]. Available: https://www.bsi.bund.de/cae/ servlet/contentblob/478152/publicationFile/30552/ais20e pdf.pdf (eng)
NIST Special Publication 800-57, Elaine Barker, William Barker, William Burr, William Polk, and Miles Smid «Recommendation for Key Management – Part 1: General (Revision 3)», July 2012 (eng)
NIST Special Publication 800-90A, Elaine Barker, John Kelsey, «Recommendation for Random Number Generation Using Deterministic Random Bit Generators», January 2012. (eng)
“ISO/IEC 18031: Information Technology-Security Techniques-Random bit generation,” International Organization for Standardization and International Electrotechnical Commission, vol. iso 18031, 2005. (eng)
Mayes K., Markantonakis K. “Smart Cards” Tokens, Security and Applications. Springer, 2008. (eng)
Akram R. N., Markantonakis K., Mayes K. “A Paradigm Shift in Smart Card Ownership Model,” in Proceedings of the 2010 International Conference on Computational Science and Its Applications (ICCSA 2010), B. O. Apduhan, O. Gervasi, A. Iglesias, D. Taniar, and M. Gavrilova, Eds. Fukuoka, Japan: IEEE Computer Society, 2010. pp. 191–200(eng)
Кнут Д. Искусство программирования, том 2. Получисленные методы / Д. Кнут. М.: Изд. дом «Вильяме», 2007.
Brown R. Dieharder: A Random Number Test Suite. [Online]. Available: http://www.phy. duke.edu/~rgb/ General/dieharder.php (eng)
Security Requirements For Cryptographic Modules. [Online]. Available: http://csrc. nist.gov/ publications/fips /fips140-2/fips1402.pdf. (eng)
Popereshnyak S., Dimitrov G. “The Testing of Pseudorandom Sequences using Multidimensional Statistics” Proceedings of the 1st International Workshop on Digital Content & Smart Multimedia (DCSMart 2019) (Lviv, Ukraine, December 23-25), 2019. р. 151-161 (eng)
Masol V., Popereshnyak S. Statistical analysis of local sections of bits sequence”s. Journal of Automation and Information Sciences. 2019. Vol. 51. p. 31-45. DOI: 10.1615/JAutomatInf Scien.v51.i10.30 (eng)
Masol V., Popereshnyak S. Checking the Randomness of Bits Disposition in Local Segments of the (0, 1)-Sequence. Cybernetics and Systems Analysis. 2020. Vol. 56(3). P. 1-8. DOI: 10.1007/s10559-020-00267-0 (eng)
Pоpereshnyаk S. The technique for testing short sequences as a component of cryptography on the Internet of Things. CEUR-WS.org/vol/ 2516/paper 11 (eng).
