AN UPDATED CRYPTANALYSIS ON THE BFHP-DLP SIGNING SCHEME
Article Sidebar
Main Article Content
Abstract
The concept of public-key cryptography introduced the notion of a digital signature scheme. In the era of online and digital communications, a signature scheme that works perfectly to achieve the goals of cryptography- confidentiality, authentication, data integrity, and non-repudiation, is urgently needed. However, every cryptosystem, including a digital signature scheme requires a well-defined difficult mathematical problem as its fundamental security strength, as demonstrated by the Diffie-Hellman key exchange with its discrete logarithm problem (DLP). Another problem called BFHP used by the AAβ-encryption scheme, has also withstood any destructive cryptanalysis since the scheme was introduced in 2013. Later, a digital signature scheme was introduced that combines both BFHP and DLP as difficult mathematical problems. Mathematical cryptanalysis was also performed against this scheme to test its security strength. This paper presents new cryptanalysis of the signing scheme. While the previous cryptanalysis focused only on BFHP, the obtained new results showed some improvement by scrutinizing the other difficult mathematical problem, DLP. In addition, several potential attacks on the future implementation by introducing side-channel and man-in-the-middle attacks against the scheme also will be discussed in this work. The countermeasures for each attack to enable the best-practice implementation of the scheme are also presented.
Downloads
Article Details
Transfer of Copyrights
- In the event of publication of the manuscript entitled [INSERT MANUSCRIPT TITLE AND REF NO.] in the Malaysian Journal of Science, I hereby transfer copyrights of the manuscript title, abstract and contents to the Malaysian Journal of Science and the Faculty of Science, University of Malaya (as the publisher) for the full legal term of copyright and any renewals thereof throughout the world in any format, and any media for communication.
Conditions of Publication
- I hereby state that this manuscript to be published is an original work, unpublished in any form prior and I have obtained the necessary permission for the reproduction (or am the owner) of any images, illustrations, tables, charts, figures, maps, photographs and other visual materials of whom the copyrights is owned by a third party.
- This manuscript contains no statements that are contradictory to the relevant local and international laws or that infringes on the rights of others.
- I agree to indemnify the Malaysian Journal of Science and the Faculty of Science, University of Malaya (as the publisher) in the event of any claims that arise in regards to the above conditions and assume full liability on the published manuscript.
Reviewer’s Responsibilities
- Reviewers must treat the manuscripts received for reviewing process as confidential. It must not be shown or discussed with others without the authorization from the editor of MJS.
- Reviewers assigned must not have conflicts of interest with respect to the original work, the authors of the article or the research funding.
- Reviewers should judge or evaluate the manuscripts objective as possible. The feedback from the reviewers should be express clearly with supporting arguments.
- If the assigned reviewer considers themselves not able to complete the review of the manuscript, they must communicate with the editor, so that the manuscript could be sent to another suitable reviewer.
Copyright: Rights of the Author(s)
- Effective 2007, it will become the policy of the Malaysian Journal of Science (published by the Faculty of Science, University of Malaya) to obtain copyrights of all manuscripts published. This is to facilitate:
(a) Protection against copyright infringement of the manuscript through copyright breaches or piracy.
(b) Timely handling of reproduction requests from authorized third parties that are addressed directly to the Faculty of Science, University of Malaya. - As the author, you may publish the fore-mentioned manuscript, whole or any part thereof, provided acknowledgement regarding copyright notice and reference to first publication in the Malaysian Journal of Science and Faculty of Science, University of Malaya (as the publishers) are given.
You may produce copies of your manuscript, whole or any part thereof, for teaching purposes or to be provided, on individual basis, to fellow researchers. - You may include the fore-mentioned manuscript, whole or any part thereof, electronically on a secure network at your affiliated institution, provided acknowledgement regarding copyright notice and reference to first publication in the Malaysian Journal of Science and Faculty of Science, University of Malaya (as the publishers) are given.
- You may include the fore-mentioned manuscript, whole or any part thereof, on the World Wide Web, provided acknowledgement regarding copyright notice and reference to first publication in the Malaysian Journal of Science and Faculty of Science, University of Malaya (as the publishers) are given.
- In the event that your manuscript, whole or any part thereof, has been requested to be reproduced, for any purpose or in any form approved by the Malaysian Journal of Science and Faculty of Science, University of Malaya (as the publishers), you will be informed. It is requested that any changes to your contact details (especially e-mail addresses) are made known.
Copyright: Role and responsibility of the Author(s)
- In the event of the manuscript to be published in the Malaysian Journal of Science contains materials copyrighted to others prior, it is the responsibility of current author(s) to obtain written permission from the copyright owner or owners.
- This written permission should be submitted with the proof-copy of the manuscript to be published in the Malaysian Journal of Science
References
Abd Ghafar, A. H., & Ariffin, M. R. K (2014). Timing Attack Analysis on AA_β β Cryptosystem. Journal of Computer and Communications, 2(4), 1-9.
Abd Ghafar, A. H., & Ariffin, M. R. K. (2016). SPA on Rabin variant with public key $$ N= p^2 q2q $$ N= p 2 q . Journal of Cryptographic Engineering, 6(4), 339-346.
Abd Ghafar, A. H., & Ariffin, M. R. K. (2019). A New Signing Scheme Based on BFHP and DLP. International Journal of Cryptology Research, 9(2), 31-44.
Adnan, S. F. S., Isa, M. A. M., & Hashim, H. (2016). Implementation of the Aa-Beta (AAβ) lightweight asymmetric encryption scheme on an embedded system device. Advanced Science Letters, 22(10), 2910-2913.
Alam, K., Alam, K. R., Faruq, O., & Morimoto, Y. (2016, January). A comparison between RSA and ElGamal based untraceable blind signature schemes. In 2016 International Conference on Networking Systems and Security (NSysS) (pp. 1-4). IEEE.
Ariffin, M. R. K., Asbullah, M. A., Abu, N. A., & Mahad, Z. (2013). A New Efficient Asymmetric Cryptosystem Based on the Integer Factorization Problem of N= p^2 q (N= p^{2} q ). Malaysian Journal of Mathematical Sciences, 7, 19-37.
Bao, F., Deng, R. H., Han, Y., Jeng, A., Narasimhalu, A. D., & Ngair, T. (1997, April). Breaking public key cryptosystems on tamper resistant devices in the presence of transient faults. In International Workshop on Security Protocols (pp. 115-124). Springer, Berlin, Heidelberg.
Barker, E., & Dang, Q. (2015). NIST special publication 800–57 part 3: Application-specific key management guidance. NIST Special Publication, 800, 57.
Boudot, F., Gaudry, P., Guillevic, A., Heninger, N., Thomé, E., & Zimmermann, P. (2020, August). Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment. In Annual International Cryptology Conference (pp. 62-91). Springer, Cham.
Diffie, Whitfield, and Martin Hellman. "New directions in cryptography." IEEE transactions on Information Theory 22.6 (1976): 644-654.
ElGamal, T. (1985). A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE transactions on information theory, 31(4), 469-472.
Ergezer, S., Kinkelin, H., & Rezabek, F. (2020). A Survey on Threshold Signature Schemes. Network, 49.
Fleischhacker, N., Jager, T., & Schröder, D. (2019). On tight security proofs for Schnorr signatures. Journal of Cryptology, 32(2), 566-599.
Fuchsbauer, G., Plouviez, A., & Seurin, Y. (2020, May). Blind Schnorr signatures and signed ElGamal encryption in the algebraic group model. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 63-95). Springer, Cham.
Gennaro, R., & Goldfeder, S. (2018, October). Fast multiparty threshold ECDSA with fast trustless setup. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security (pp. 1179-1194).
Goldwasser, S., Micali, S., & Rivest, R. L. (1988). A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on computing, 17(2), 281-308.
Guo, L., & Lan, C. (2020, December). A New Signature Based on Blockchain. In 2020 International Conference on Intelligent Computing, Automation and Systems (ICICAS) (pp. 349-353). IEEE.
Herrmann, M., & May, A. (2008, December). Solving linear equations modulo divisors: On factoring given any bits. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 406-424). Springer, Berlin, Heidelberg.
Hoffstein, J., Pipher, J., Silverman, J. H., & Silverman, J. H. (2008). An introduction to mathematical cryptography (Vol. 1). New York: Springer.
Islamidina, A. D. P., Sudarsono, A., & Dutono, T. (2019, September). Security System for Data Location of Travelling User using RSA based on Group Signature. In 2019 International Electronics Symposium (IES) (pp. 88-93). IEEE.
Jin, W. T., Kamarulhaili, H., Said, M. R. M., Ariffin, M. R. K., Asbullah, M. A., Abu, N. A., ... & Jahani, S. (2013). On the Hastad’s Attack to LUC4, 6 Cryptosystem and compared with Other RSA-Type Cryptosystem. Malaysian Journal of Mathematical Sciences, 7, 1-17.
Joux, A. (2013, August). A new index calculus algorithm with complexity $$ l (1/4+ o (1)) $$ in small characteristic. In International Conference on Selected Areas in Cryptography (pp. 355-379). Springer, Berlin, Heidelberg.
Karatsuba, A. (1963). Multiplication of multidigit numbers on automata. In Soviet physics doklady (Vol. 7, pp. 595-596).
Kim, S., Kim, J., Cheon, J. H., & Ju, S. H. (2011). Threshold signature schemes for ElGamal variants. Computer Standards & Interfaces, 33(4), 432-437.
Kocher, P. C. (1996, August). Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In Annual International Cryptology Conference (pp. 104-113). Springer, Berlin, Heidelberg.
Kravitz, D. W. (1993). Digital signature algorithm. US Patent, 5(231), 668.
Lenstra, A. K., Lenstra, H. W., Manasse, M. S., & Pollard, J. M. (1993). The number field sieve. In The development of the number field sieve (pp. 11-42). Springer, Berlin, Heidelberg.
Montgomery, P. L. (1985). Modular multiplication without trial division. Mathematics of computation, 44(170), 519-521.
Moriarty, K., Kaliski, B., Jonsson, J., & Rusch, A. (2016). PKCS# 1: RSA cryptography specifications version 2.2. Internet Engineering Task Force, Request for Comments, 8017.
Nick, J., Ruffing, T., & Seurin, Y. (2020). MuSig2: Simple Two-Round Schnorr Multi-Signatures. Cryptology ePrint Archive, Report 2020/1261, 2020. https://eprint. iacr. org/2020/1261.
Paar, C., & Pelzl, J. (2009). Understanding cryptography: a textbook for students and practitioners. Springer Science & Business Media.
Pomerance, C. (1984, April). The quadratic sieve factoring algorithm. In Workshop on the Theory and Application of of Cryptographic Techniques (pp. 169-182). Springer, Berlin, Heidelberg.
Pornin, T. (2013). Deterministic usage of the digital signature algorithm (DSA) and elliptic curve digital signature algorithm (ECDSA). Internet Engineering Task Force RFC, 6979, 1-79.
Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120-126.
Sarbini, I. N., Jin, W. T., Feng, K. L., Othman, M., Said, M. R. M., & Hung, Y. P. Garbage-man-in-the-middle (type 2) Attack on the Lucas Based El-Gamal Cryptosystem in the Elliptic Curve Group Over Finite Field. In Cryptology and Information Security Conference 2018 (p. 35).
Schnorr, C. P. (1991). Efficient signature generation by smart cards. Journal of cryptology, 4(3), 161-174.
Seurin, Y. (2012, April). On the exact security of Schnorr-type signatures in the random oracle model. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 554-571). Springer, Berlin, Heidelberg.
Smith, P. J., & Lennon, M. J. (1993, May). LUC: A New Public Key System. In SEC (pp. 103-117).
Stathakopoulou, C., & Cachin, C. (2017). Threshold signatures for blockchain systems. Swiss Federal Institute of Technology.
Wong, T. J., Said, M. R. M., Othman, M., & Koo, L. F. (2015, May). On the common modulus attack into the LUC4, 6 cryptosystem. In AIP Conference Proceedings (Vol. 1660, No. 1, p. 090052). AIP Publishing LLC.