skip to main content
10.1145/3460120.3485382acmconferencesArticle/Chapter ViewAbstractPublication PagesccsConference Proceedingsconference-collections
research-article
Open access

Morpheus: Bringing The (PKCS) One To Meet the Oracle

Published: 13 November 2021 Publication History

Abstract

This paper focuses on developing an automatic, black-box testing approach called Morpheus to check the non-compliance of libraries implementing PKCS#1-v1.5 signature verification with the PKCS#1-v1.5 standard. Non-compliance can not only make implementations vulnerable to Bleichenbacher-style RSA signature forgery attacks but also can induce interoperability issues. For checking non-compliance, Morpheus adaptively generates interesting test cases and then takes advantage of an oracle, a formally proven correct implementation of PKCS#1-v1.5 signature standard, to detect non-compliance in an implementation under test. We have used Morpheus to test 45 implementations of PKCS#1-v1.5 signature verification and discovered that 6 of them are susceptible to variants of the Bleichenbacher-style low public exponent RSA signature forgery attack, 1 implementation has a buffer overflow, 33 implementations have incompatibility issues, and 8 implementations have minor leniencies. Our findings have been responsibly disclosed and positively acknowledged by the developers.

References

[1]
[n.d.]. BERserk Attack -- Intel Security web Archive. https://web.archive.org/web/20150112153121/http://www.intelsecurity.com/advanced-threat-research/. Accessed: Apr 04, 2021.
[2]
[n.d.]. Censys.io - Attack Surface Scan - Total Visibility Internet-Wide. https://censys.io/certificates. Accessed: Apr 04, 2021.
[3]
[n.d.]. Forge -- A native implementation of TLS in Javascript and tools to write crypto-based and network-heavy webapps. https://github.com/digitalbazaar/forge. Accessed: Apr 04, 2021.
[4]
[n.d.]. hostapd -- IEEE 802.11 AP, IEEE 802.1X/WPA/WPA2/EAP/RADIUS Authenticator. https://w1.fi/hostapd/. Accessed: Apr 04, 2021.
[5]
[n.d.]. ipsec_rsasigkey - generate RSA signature key. https://manpages.debian.org/testing/libreswan/ipsec_rsasigkey.8.en.html. Accessed: Apr 04, 2021.
[6]
[n.d.]. phpseclib -- PHP Secure Communications Library. https://github.com/phpseclib/phpseclib. Accessed: Apr 04, 2021.
[7]
[n.d.]. relic -- Modern cryptographic meta-toolkit with emphasis on efficiency and flexibility. https://github.com/relic-toolkit/relic. Accessed: Apr 04, 2021.
[8]
[n.d.]. wpa_supplicant -- Linux WPA/WPA2/IEEE 802.1X Supplicant. https://w1.fi/wpa_supplicant/. Accessed: Apr 04, 2021.
[9]
[n.d.]. X.660 : Information technology - Procedures for the operation of object identifier registration authorities: General procedures and top arcs of the international object identifier tree. https://www.itu.int/rec/T-REC-X.660. Accessed: Apr 04, 2021.
[10]
[n.d.]. X.690 : Information technology - ASN.1 encoding rules: Specification of Basic Encoding Rules (BER), Canonical Encoding Rules (CER) and Distinguished Encoding Rules (DER). https://www.itu.int/rec/T-REC-X.690/. Accessed: Apr 04, 2021.
[11]
2006. CVE-2006--4340. https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2006--4340. Accessed: Apr 04, 2021.
[12]
2006. CVE-2006--4790. https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2006--4790. Accessed: Apr 04, 2021.
[13]
2013. American Fuzzy Lop. https://lcamtuf.coredump.cx/afl/. Accessed: Apr 04, 2021.
[14]
2021. AFL++ -- The AFL++ fuzzing framework. https://aflplus.plus. Accessed: Apr 04, 2021.
[15]
2021. ClusterFuzz -- Scalable Fuzzing Infrastructure. https://github.com/google/clusterfuzz. Accessed: Apr 04, 2021.
[16]
2021. FuzzBench -- Fuzzer benchmarking as a service. https://github.com/google/fuzzbench. Accessed: Apr 04, 2021.
[17]
2021. Grammar Mutator -- AFL++. https://github.com/AFLplusplus/Grammar-Mutator. Accessed: Apr 04, 2021.
[18]
2021. Honggfuzz -- Security oriented software fuzzer. https://github.com/google/honggfuzz. Accessed: Apr 04, 2021.
[19]
2021. LibFuzzer -- a library for coverage-guided fuzz testing. https://llvm.org/docs/LibFuzzer.html. Accessed: Apr 04, 2021.
[20]
2021. Morpheus -- A PKCS1 signature verification non-compliance checker. https://github.com/Morpheus-Repo/Morpheus.git. Accessed: May 04, 2021.
[21]
2021. OSS-Fuzz -- Continuous Fuzzing for Open Source Software. https://github.com/google/oss-fuzz. Accessed: Apr 04, 2021.
[22]
2021. Peach -- Peach Fuzzer. http://www.peachfuzzer.com/. Accessed: Apr 04, 2021.
[23]
2021. SPIKE -- Fuzzer Automation with SPIKE. https://resources.infosecinstitute.com/topic/fuzzer-automation-with-spike/. Accessed: Apr 04, 2021.
[24]
Alberto Bartoli, Eric Medvet, and Filippo Onesti. 2018. Evil twins and WPA2 Enterprise: A coming security disaster? Computers & Security 74 (2018), 1--11.
[25]
Benjamin Beurdouche, Karthikeyan Bhargavan, Antoine Delignat-Lavaud, Cédric Fournet, Markulf Kohlweiss, Alfredo Pironti, Pierre-Yves Strub, and Jean Karim Zinzindohoue. 2015. A messy state of the union: Taming the composite state machines of TLS. In IEEE Symposium on Security and Privacy.
[26]
Daniel Bleichenbacher. 1998. Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1. In Advances in Cryptology - CRYPTO '98, Hugo Krawczyk (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 1--12.
[27]
Hanno Böck, Juraj Somorovsky, and Craig Young. 2018. Return Of Bleichenbacher's Oracle Threat (ROBOT). In 27th USENIX Security Symposium (USENIX Security 18). USENIX Association, Baltimore, MD, 817--849. https://www.usenix.org/conference/usenixsecurity18/presentation/bock
[28]
George E. P Box. 2005. Statistics for experimenters : design, innovation and discovery (2nd ed. ed.). Wiley-Interscience, Hoboken, N.J.
[29]
Chad Brubaker, Suman Jana, Baishakhi Ray, Sarfraz Khurshid, and Vitaly Shmatikov. 2014. Using frankencerts for automated adversarial testing of certificate validation in SSL/TLS implementations. In 2014 IEEE Symposium on Security and Privacy. IEEE, 114--129.
[30]
Bugzilla. 2014. RSA PKCS#1 signature verification forgery is possible due to too-permissive SignatureAlgorithm parameter parsing. https://bugzilla.mozilla.org/show_bug.cgi?id=1064636. Accessed: Apr 04, 2021.
[31]
Bugzilla. 2014 (accessed Feb 08, 2021). RSA PKCS#1 signature verification forgery is possible due to too-permissive SignatureAlgorithm parameter parsing. https://bugzilla.mozilla.org/show_bug.cgi?id=1064636.
[32]
Sze Yiu Chau, Omar Chowdhury, Endadul Hoque, Huangyi Ge, Aniket Kate, Cristina Nita-Rotaru, and Ninghui Li. 2017. SymCerts: Practical Symbolic Execution for Exposing Noncompliance in X.509 Certificate Validation Implementations. In 2017 IEEE Symposium on Security and Privacy (SP). 503--520. https://doi.org/10.1109/SP.2017.40
[33]
Sze Yiu Chau, Moosa Yahyazadeh, Omar Chowdhury, Aniket Kate, and Ninghui Li. 2019. Analyzing Semantic Correctness with Symbolic Execution: A Case Study on PKCS# 1 v1. 5 Signature Verification. In NDSS.
[34]
The Coq Development Team. 2012. The Coq Reference Manual, version 8.12. Available electronically at https://coq.inria.fr/distrib/current/refman/.
[35]
Siddhartha R. Dalal and Colin L. Mallows. 1998. Factor-Covering Designs for Testing Software. Technometrics 40, 3 (Aug. 1998), 234-243. https://doi.org/10.2307/1271179
[36]
Antoine Delignat-Lavaud, Martín Abadi, Andrew Birrell, Ilya Mironov, Ted Wobber, and Yinglian Xie. 2014. Web PKI: Closing the Gap between Guidelines and Practices. In NDSS. Citeseer.
[37]
D. Eastlake. 2001. RSA/SHA-1 SIGs and RSA KEYs in the Domain Name System (DNS). RFC 3110. https://www.rfc-editor.org/rfc/rfc3110.txt
[38]
H. Finney. 2006. Bleichenbacher's RSA signature forgery based on implementation error. https://mailarchive.ietf.org/arch/msg/openpgp/5rnE9ZRN1AokBVj3VqblGlP63QE/. Accessed: Apr 04, 2021.
[39]
Si Gao, Hua Chen, and Limin Fan. 2013. Padding Oracle Attack on PKCS#1 v1.5: Can Non-standard Implementation Act as a Shelter?. In Cryptology and Network Security. Springer International Publishing, Cham, 39--56.
[40]
Tibor Jager, Saqib A. Kakvi, and Alexander May. 2018. On the Security of the PKCS#1 v1.5 Signature Scheme (CCS '18). Association for Computing Machinery, New York, NY, USA, 1195-1208. https://doi.org/10.1145/3243734.3243798
[41]
Tibor Jager, Sebastian Schinzel, and Juraj Somorovsky. 2012. Bleichenbacher's Attack Strikes again: Breaking PKCS#1 v1.5 in XML Encryption. In Computer Security -- ESORICS 2012, Sara Foresti, Moti Yung, and Fabio Martinelli (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 752--769.
[42]
Simon Josefsson. 2006. [gnutls-dev] Original analysis of signature forgery problem. https://lists.gnupg.org/pipermail/gnutls-dev/2006-September/001240.html. Accessed: Apr 04, 2021.
[43]
Simon Josefsson. 2006 (accessed Feb 08, 2021). [gnutls-dev] Original analysis of signature forgery problem. https://lists.gnupg.org/pipermail/gnutls-dev/2006-September/001240.html.
[44]
Jinho Jung, Stephen Tong, Hong Hu, Jungwon Lim, Yonghwi Jin, and Taesoo Kim. [n.d.]. WINNIE: Fuzzing Windows Applications with Harness Synthesis and Fast Cloning. ([n. d.]).
[45]
Burt Kaliski. 1998. PKCS #1: RSA Encryption Version 1.5. RFC 2313. https://doi.org/10.17487/RFC2313
[46]
Burt Kaliski and Jessica Staddon. 1998. PKCS #1: RSA Cryptography Specifications Version 2.0. RFC 2437. https://doi.org/10.17487/RFC2437
[47]
Burt Kaliski and Jessica Staddon. 2003. RFC3447: Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1. RFC 3447. https://doi.org/10.17487/RFC3447
[48]
Cameron F. Kerry and Charles Romine. 2013. FIPS PUB 186--4 FEDERAL INFORMATION PROCESSING STANDARDS PUBLICATION Digital Signature Standard (DSS).
[49]
George Klees, Andrew Ruef, Benji Cooper, Shiyi Wei, and Michael Hicks. 2018. Evaluating fuzz testing. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. 2123--2138.
[50]
Vlastimil Klíma, Ondrej Pokorný, and Tomá? Rosa. 2003. Attacking RSA-Based Sessions in SSL/TLS. In Cryptographic Hardware and Embedded Systems - CHES 2003, Colin D. Walter, Çetin K. Koç, and Christof Paar (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 426--440.
[51]
D. Richard Kuhn and Raghu N. Kacker. 2011. Combinatorial Testing. https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=910001. Accessed: Apr 04, 2021.
[52]
Ulrich Kühn, Andrei Pyshkin, Erik Tews, and Ralf-Philipp Weinmann. 2008. Variants of Bleichenbacher's Low-Exponent Attack on PKCS#1 RSA Signatures. In Sicherheit 2008: Sicherheit, Schutz und Zuverlässigkeit. Konferenzband der 4. Jahrestagung des Fachbereichs Sicherheit der Gesellschaft für Informatik e.V. (GI), 2.-4. April 2008 im Saarbrücker Schloss.
[53]
Ulrich Kühn, Andrei Pyshkin, Erik Tews, and Ralf-Philipp Weinmann. 2008. Variants of Bleichenbacher's Low-Exponent Attack on PKCS#1 RSA Signatures. In SICHERHEIT 2008 -- Sicherheit, Schutz und Zuverlässigkeit. Beiträge der 4. Jahrestagung des Fachbereichs Sicherheit der Gesellschaft für Informatik e.V. (GI), Ammar Alkassar and Jörg Siekmann (Eds.). Gesellschaft für Informatik e. V., Bonn, 97--109.
[54]
Yuwei Li, Shouling Ji, Yuan Chen, Sizhuang Liang, Wei-Han Lee, Yueyao Chen, Chenyang Lyu, Chunming Wu, Raheem Beyah, Peng Cheng, et al. 2021. Unifuzz: A holistic and pragmatic metrics-driven platform for evaluating fuzzers. In 30th USENIX Security Symposium (USENIX Security 21). USENIX Association.
[55]
Christopher Meyer, Juraj Somorovsky, Eugen Weiss, Jörg Schwenk, Sebastian Schinzel, and Erik Tews. 2014. Revisiting SSL/TLS Implementations: New Bleichenbacher Side Channels and Attacks. In 23rd USENIX Security Symposium (USENIX Security 14). USENIX Association, San Diego, CA, 733-- 748. https://www.usenix.org/conference/usenixsecurity14/technical-sessions/presentation/meyer
[56]
Kathleen Moriarty, Burt Kaliski, Jakob Jonsson, and Andreas Rusch. 2016. PKCS#1: RSA Cryptography Specifications Version 2.2. RFC 8017. https://doi.org/10.17487/RFC8017
[57]
Theofilos Petsios, Adrian Tang, Salvatore Stolfo, Angelos D. Keromytis, and Suman Jana. 2017. NEZHA: Efficient Domain-Independent Differential Testing. In 2017 IEEE Symposium on Security and Privacy (SP). 615--632. https://doi.org/10.1109/SP.2017.27
[58]
Tahina Ramananandro, Antoine Delignat-Lavaud, CÃ?dric Fournet, Nikhil Swamy, Tej Chajed, Nadim Kobeissi, and Jonathan Protzenko. 2019. EverParse: Verified Secure Zero-Copy Parsers for Authenticated Message Formats. In USENIX Security. USENIX. https://www.microsoft.com/en-us/research/publication/everparse/
[59]
E. Ronen, R. Gillham, D. Genkin, A. Shamir, D. Wong, and Y. Yarom. 2019. The 9 Lives of Bleichenbacher's CAT: New Cache ATtacks on TLS Implementations. In 2019 IEEE Symposium on Security and Privacy (SP). 435--452. https://doi.org/10.1109/SP.2019.00062
[60]
Joseph A. Salowey, Sean Turner, and Christopher A. Wood. [n.d.]. TLS 1.3: - One Year Later. https://www.ietf.org/blog/tls13-adoption/. Accessed: Jan 11, 2020.
[61]
George B. Sherwood. 2015. Embedded functions in combinatorial test designs. In Eighth IEEE International Conference on Software Testing, Verification and Validation, ICST 2015 Workshops, Graz, Austria, April 13--17, 2015. IEEE Computer Society, 1--10. https://doi.org/10.1109/ICSTW.2015.7107432
[62]
N. J. A. Sloane. 1993. Covering arrays and intersecting codes. Journal of Combinatorial Designs 1, 1 (1993), 51--63. https://doi.org/10.1002/jcd.3180010106 arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/jcd.3180010106
[63]
Nigel P. Smart. 2015. Cryptography Made Simple (1st ed.). Springer Publishing Company, Incorporated.
[64]
Serge Vaudenay. 2010. A Classical Introduction to Cryptography: Applications for Communications Security (1st ed.). Springer Publishing Company, Incorporated.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
CCS '21: Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security
November 2021
3558 pages
ISBN:9781450384544
DOI:10.1145/3460120
This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 November 2021

Check for updates

Author Tags

  1. PKCS#1 signature verification
  2. adaptive combinatorial testing
  3. non-compliance checking
  4. reference implementation

Qualifiers

  • Research-article

Funding Sources

  • US Department of Defense (DARPA)
  • US National Science Foundation (NSF)
  • GRF matching fund
  • The Chinese University of Hong Kong (CUHK) Project Impact Enhancement Fund

Conference

CCS '21
Sponsor:
CCS '21: 2021 ACM SIGSAC Conference on Computer and Communications Security
November 15 - 19, 2021
Virtual Event, Republic of Korea

Acceptance Rates

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)174
  • Downloads (Last 6 weeks)39
Reflects downloads up to 25 Jan 2025

Other Metrics

Citations

Cited By

View all

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media