Abstract
In spite of strong mathematical foundations of cryptographic algorithms, the practical implementations of cryptographic protocols continue to fail. Insufficient entropy, faulty library implementation, API misuse do not only jeopardize the security of cryptographic keys, but also lead to distinct patterns that can result in keys’ origin attribution. In this work, we examined attribution of cryptographic keys based on their moduli. We analyzed over 6.5 million keys generated by 43 cryptographic libraries versions on 20 Linux OS versions released over the past 8 years. We showed that with only a few moduli characteristics, we can accurately (with 75% accuracy) attribute an individual key to the originating library. Depending on the library, our approach is sensitive enough to pinpoint the corresponding major, minor, and build release of several libraries that generated an individual key with an accuracy of 81%–98%. We further explore attribution of SSH keys collected from publicly facing IPv4 addresses showing that our approach is able to differentiate individual libraries of RSA keys with 95% accuracy.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
For example, setting last bit to 1 ensures that the number is odd.
- 2.
We refer to library version using a conventional notation of software versioning where each version is represented by major.minor[.build[.patch]].
- 3.
References
Acar, Y., et al.: Comparing the usability of cryptographic apis. In: 2017 IEEE Symposium on Security and Privacy (SP), pp. 154–171 (2017)
Acer, M.E., et al.: Where the wild warnings are: Root causes of chrome https certificate errors. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, pp. 1407–1420. ACM, New York (2017)
Aly, M.: Survey on multiclass classification methods. Neural Netw. 19, 1–9 (2005)
Barker, E., Chen, L., Roginsky, A., Vassilev, A., Davis, R., Simon, S.: Recommendation for pair-wise key establishment using integer factorization cryptography. Tech. rep., National Institute of Standards and Technology, Gaithersburg (2019). DOI: https://doi.org/10.6028/NIST.SP.800-56Br2,https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Br2.pdf
Bassham, L.E., et al.: Sp 800–22 rev. 1a. a statistical test suite for random and pseudorandom number generators for cryptographic applications. Tech. rep., Gaithersburg (2010)
Bayes, T.: LII. an essay towards solving a problem in the doctrine of chances. by the late rev. Mr. Bayes, FRS communicated by Mr. price, in a letter to john canton, AMFR S. Philos. Trans. R. Soc. Lond. 53, 370–418 (1763)
Breiman, L., Friedman, J.H., Stone, C.J., Olshen, R.A.: Classification and Regression Trees. Wadsworth International Group, Franklin (1984)
Costin, A., Zaddach, J., Francillon, A., Balzarotti, D.: A large-scale analysis of the security of embedded firmwares. In: Proceedings of the 23rd USENIX Conference on Security Symposium, SEC 2014, pp. 95–110. USENIX Association, Berkeley (2014)
Cox, D.R., Snell, E.J.: Analysis of Binary Data, vol. 32. CRC Press, Boca Raton (1989)
Durumeric, Z., Kasten, J., Bailey, M., Halderman, J.A.: Analysis of the https certificate ecosystem. In: Proceedings of the 2013 Conference on Internet Measurement Conference, IMC 2013, pp. 291–304. ACM, New York (2013)
Durumeric, Z., et al.: The matter of heartbleed. In: Proceedings of the 2014 Conference on Internet Measurement Conference, IMC 2014, pp. 475–488. ACM, New York (2014)
Egele, M., Brumley, D., Fratantonio, Y., Kruegel, C.: An empirical study of cryptographic misuse in android applications. In: Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security, CCS 2013, pp. 73–84. Association for Computing Machinery, New York (2013)
Everspaugh, A., Zhai, Y., Jellinek, R., Ristenpart, T., Swift, M.: Not-so-random numbers in virtualized linux and the whirlwind rng. In: 2014 IEEE Symposium on Security and Privacy, pp. 559–574, May 2014
Faugère, J.-C., Marinier, R., Renault, G.: Implicit factoring with shared most significant and middle bits. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 70–87. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13013-7_5
Fernando, D.W., Komninos, N., Chen, T.: A study on the evolution of ransomware detection using machine learning and deep learning techniques. IoT 1(2), 551–604 (2020)
Gasser, O., Holz, R., Carle, G.: A deeper understanding of SSH: Results from internet-wide scans. In: 2014 IEEE Network Operations and Management Symposium (NOMS), pp. 1–9, May 2014
Hastings, M., Fried, J., Heninger, N.: Weak keys remain widespread in network devices. In: Proceedings of the 2016 Internet Measurement Conference, IMC 2016, pp. 49–63. ACM, New York (2016)
Heninger, N., Durumeric, Z., Wustrow, E., Halderman, J.A.: Mining your PS and QS: detection of widespread weak keys in network devices. In: Proceedings of 21st USENIX Security Symposium (USENIX Security 12), pp. 205–220. USENIX, Bellevue (2012)
Ho, T.K.: Random decision forests. In: Proceedings of 3rd International Conference on Document Analysis and Recognition, vol. 1, pp. 278–282. IEEE (1995)
Hurley-Smith, D., Hernandez-Castro, J.: Great expectations: a critique of current approaches to random number generation testing & certification. In: Cremers, C., Lehmann, A. (eds.) Sec. Standardisation Res., pp. 143–163. Springer International Publishing, Cham (2018)
IETF: Brotli compressed data format. https://tools.ietf.org/html/rfc7932
Lachenbruch, P.A., Goldstein, M.: Discriminant analysis. Biometrics 69–85 (1979)
Lazar, D., Chen, H., Wang, X., Zeldovich, N.: Why does cryptographic software fail? a case study and open problems. In: Proceedings of 5th Asia-Pacific Workshop on Systems, APSys 2014. Association for Computing Machinery, New York (2014)
Lenstra, A.K., Hughes, J.P., Augier, M., Bos, J.W., Kleinjung, T., Wachter, C.: Ron was wrong, whit is right. IACR Cryptol. ePrint Arch. 2012, 64 (2012)
Leurent, G., Peyrin, T.: Sha-1 is a shambles: First chosen-prefix collision on sha-1 and application to the PGP web of trust. In: 29th USENIX Security Symposium (USENIX Security 20), pp. 1839–1856. USENIX Association, August 2020. https://www.usenix.org/conference/usenixsecurity20/presentation/leurent
Li, J., Lin, Z., Caballero, J., Zhang, Y., Gu, D.: K-hunt: pinpointing insecure cryptographic keys from execution traces. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS 2018, pp. 412–425. ACM, New York (2018)
Li, Y., Zhang, Y., Li, J., Gu, D.: iCryptoTracer: dynamic analysis on misuse of cryptography functions in iOS applications. In: Au, M.H., Carminati, B., Kuo, C.-C.J. (eds.) NSS 2014. LNCS, vol. 8792, pp. 349–362. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-11698-3_27
McCulloch, W.S., Pitts, W.: A logical calculus of the ideas immanent in nervous activity. Bull. Math. Biophys. 5(4), 115–133 (1943)
Muslukhov, I., Boshmaf, Y., Beznosov, K.: Source attribution of cryptographic api misuse in android applications. In: Proceedings of the 2018 on Asia Conference on Computer and Communications Security, ASIACCS 2018, pp. 133–146. Association for Computing Machinery, New York (2018)
Nadi, S., Krüger, S., Mezini, M., Bodden, E.: Jumping through hoops: why do java developers struggle with cryptography apis? In: Proceedings of the 38th International Conference on Software Engineering, ICSE 2016, pp. 935–946. Association for Computing Machinery, New York (2016)
Nemec, M., Klinec, D., Svenda, P., Sekan, P., Matyas, V.: Measuring popularity of cryptographic libraries in internet-wide scans. In: Proceedings of the 33rd Annual Computer Security Applications Conference, ACSAC 2017, pp. 162–175. ACM, New York (2017)
OpenSSL: Bn_generate_prime (2021). https://www.openssl.org/docs/man1.1.1/man3/BN_generate_prime.html
Piccolboni, L., Di Guglielmo, G., Carloni, L.P., Sethumadhavan, S.: Crylogger: Detecting crypto misuses dynamically. In: Proceedings of the IEEE Symposium on Security and Privacy (S&P). IEEE (2021)
Python: The Lempel–Ziv–Markov chain (LZMA) compression algorithm. https://docs.python.org/3/library/lzma.html
Rahaman, S., et al.: Cryptoguard: high precision detection of cryptographic vulnerabilities in massive-sized java projects. In: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, CCS 2019, pp. 2455–2472. Association for Computing Machinery, New York (2019)
Seznec, A., Sendrier, N.: Havege: a user-level software heuristic for generating empirically strong random numbers. ACM Trans. Model. Comput. Simul. 13(4), 334–346 (2003)
Svenda, P., et al.: The million-key question—investigating the origins of RSA public keys. In: Proceedings of 25th USENIX Security Symposium (USENIX Security 16), pp. 893–910. USENIX Association, Austin, August 2016
ubld.it: TrueRNG. https://hackaday.io/project/630-truerng
Yilek, S., Rescorla, E., Shacham, H., Enright, B., Savage, S.: When private keys are public: results from the 2008 debian openssl vulnerability. In: Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement, IMC 2009, pp. 15–27. Association for Computing Machinery, New York (2009)
Yutaka, N.: NeuG: a true random number generator implementation. Tech. rep. (2015)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
9 Appendix
9 Appendix
See Table 10.
Rights and permissions
Copyright information
© 2021 ICST Institute for Computer Sciences, Social Informatics and Telecommunications Engineering
About this paper
Cite this paper
Branca, E., Abazari, F., Carranza, R.R., Stakhanova, N. (2021). Origin Attribution of RSA Public Keys. In: Garcia-Alfaro, J., Li, S., Poovendran, R., Debar, H., Yung, M. (eds) Security and Privacy in Communication Networks. SecureComm 2021. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, vol 398. Springer, Cham. https://doi.org/10.1007/978-3-030-90019-9_19
Download citation
DOI: https://doi.org/10.1007/978-3-030-90019-9_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-90018-2
Online ISBN: 978-3-030-90019-9
eBook Packages: Computer ScienceComputer Science (R0)