Published January 1, 2020
| Version v1
Publication
Open
Kleptographic Attack on Elliptic Curve Based Cryptographic Protocols
- 1. National University of Sciences and Technology
- 2. Prince Sultan University
- 3. Bahauddin Zakariya University
Description
Kleptography is the study of pilfering secure data secretly and subliminally. The concept of inserting backdoors was introduced two decades ago by Young and Yung. However, still it is a serious threat for modern cryptography. Different studies have proved that exploiting implementation errors of cryptographic algorithms needs less effort as compared to attacking its mathematical structure. Inserting the backdoor modifies the standard method of generating public and private key pairs in such away that the public information is meaningful for the attacker. This paper presents the kleptographic attack on cryptographic algorithm based on Elliptic curves. We show the technique of implementing backdoor against Edwards-curve Digital Signature Algorithm, Elliptic curve Diffie-Hellman key exchange scheme, Elliptic curve Digital Signature Algorithm, Elliptic curve Integrated Encryption Scheme, Elliptic curve ElGamal Encryption and Elliptic curve Qu-Vanstone implicit certificate scheme. In practical approach, backdoors are inserted in such a way that their identification is impossible by analyzing the output of an algorithm. Detection of kleptographic implementation is a complex task and very few studies can be found in this direction. We have explored the possibility of detection of malicious code inside the Elliptic curve based algorithms by using the idea of running time analysis. We have shown that by implementing strong Secretly Embedded Trapdoor with Universal Protection (SETUP) attack against Elliptic curve based algorithms, one can detect the presence of backdoor by analyzing the time difference in execution of an honest vs malicious version of code. We also modified the backdoor insertion mechanism in Edwards-curve Digital Signature Algorithm that results in negligible time difference making it impossible for the user to detect backdoor presence.
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
تصوير السرقة هو دراسة سرقة البيانات الآمنة سراً وبشكل لا شعوري. تم تقديم مفهوم إدخال الأبواب الخلفية قبل عقدين من قبل يونغ ويونغ. ومع ذلك، لا يزال يشكل تهديدًا خطيرًا للتشفير الحديث. أثبتت دراسات مختلفة أن استغلال أخطاء تنفيذ خوارزميات التشفير يحتاج إلى جهد أقل مقارنة بمهاجمة هيكلها الرياضي. يؤدي إدخال الباب الخلفي إلى تعديل الطريقة القياسية لتوليد أزواج المفاتيح العامة والخاصة بحيث تكون المعلومات العامة ذات مغزى للمهاجم. تعرض هذه الورقة هجوم السرقة على خوارزمية التشفير بناءً على المنحنيات الإهليلجية. نعرض تقنية تنفيذ الباب الخلفي مقابل خوارزمية التوقيع الرقمي لمنحنى إدواردز، ومخطط تبادل مفاتيح المنحنى الإهليلجي Diffie - Hellman، وخوارزمية التوقيع الرقمي للمنحنى الإهليلجي، ومخطط التشفير المتكامل للمنحنى الإهليلجي، وتشفير ElGamal للمنحنى الإهليلجي، ومخطط الشهادة الضمنية Qu - Vanstone للمنحنى الإهليلجي. في النهج العملي، يتم إدخال الأبواب الخلفية بطريقة تجعل تحديدها مستحيلاً من خلال تحليل مخرجات الخوارزمية. يعد الكشف عن تنفيذ تصوير السرقة مهمة معقدة ويمكن العثور على عدد قليل جدًا من الدراسات في هذا الاتجاه. لقد استكشفنا إمكانية اكتشاف التعليمات البرمجية الضارة داخل الخوارزميات القائمة على المنحنى الإهليلجي باستخدام فكرة تحليل وقت التشغيل. لقد أظهرنا أنه من خلال تنفيذ هجوم Trapdoor مضمن سرًا مع الحماية الشاملة (الإعداد) ضد الخوارزميات القائمة على المنحنى الإهليلجي، يمكن للمرء اكتشاف وجود الباب الخلفي من خلال تحليل فارق التوقيت في تنفيذ نسخة صادقة مقابل ضارة من التعليمات البرمجية. قمنا أيضًا بتعديل آلية إدخال الباب الخلفي في خوارزمية التوقيع الرقمي لمنحنى إدواردز التي تؤدي إلى اختلاف ضئيل في الوقت مما يجعل من المستحيل على المستخدم اكتشاف وجود الباب الخلفي.Translated Description (French)
La kleptographie est l'étude du vol de données sécurisées secrètement et subliminalement. Le concept d'insertion de portes dérobées a été introduit il y a deux décennies par Young et Yung. Cependant, c'est toujours une menace sérieuse pour la cryptographie moderne. Différentes études ont prouvé que l'exploitation des erreurs de mise en œuvre des algorithmes cryptographiques nécessite moins d'efforts que l'attaque de sa structure mathématique. L'insertion de la porte dérobée modifie la méthode standard de génération de paires de clés publiques et privées de telle sorte que les informations publiques sont significatives pour l'attaquant. Cet article présente l'attaque kleptographique sur l'algorithme cryptographique basé sur les courbes elliptiques. Nous montrons la technique de mise en œuvre de backdoor contre l'algorithme de signature numérique à courbe d'Edwards, le schéma d'échange de clés Diffie-Hellman à courbe elliptique, l'algorithme de signature numérique à courbe elliptique, le schéma de cryptage intégré à courbe elliptique, le cryptage ElGamal à courbe elliptique et le schéma de certificat implicite Qu-Vanstone à courbe elliptique. Dans une approche pratique, les portes dérobées sont insérées de telle sorte que leur identification est impossible en analysant la sortie d'un algorithme. La détection de la mise en œuvre kleptographique est une tâche complexe et très peu d'études peuvent être trouvées dans cette direction. Nous avons exploré la possibilité de détection de code malveillant à l'intérieur des algorithmes basés sur la courbe elliptique en utilisant l'idée de l'analyse du temps d'exécution. Nous avons montré qu'en mettant en œuvre une forte attaque Secretly Embedded Trapdoor with Universal Protection (SETUP) contre les algorithmes basés sur la courbe elliptique, on peut détecter la présence de backdoor en analysant le décalage horaire dans l'exécution d'une version honnête vs malveillante du code. Nous avons également modifié le mécanisme d'insertion de la porte dérobée dans l'algorithme de signature numérique à courbe d'Edwards, ce qui entraîne une différence de temps négligeable rendant impossible la détection de la présence de la porte dérobée par l'utilisateur.Translated Description (Spanish)
La cleptografía es el estudio del robo de datos seguros de forma secreta y subliminal. El concepto de insertar puertas traseras fue introducido hace dos décadas por Young y Yung. Sin embargo, sigue siendo una grave amenaza para la criptografía moderna. Diferentes estudios han demostrado que explotar los errores de implementación de los algoritmos criptográficos requiere menos esfuerzo en comparación con atacar su estructura matemática. La inserción de la puerta trasera modifica el método estándar de generación de pares de claves públicas y privadas de tal manera que la información pública sea significativa para el atacante. Este artículo presenta el ataque cleptográfico al algoritmo criptográfico basado en curvas elípticas. Mostramos la técnica de implementación de puerta trasera contra el algoritmo de firma digital de la curva de Edwards, el esquema de intercambio de claves Diffie-Hellman de la curva elíptica, el algoritmo de firma digital de la curva elíptica, el esquema de cifrado integrado de la curva elíptica, el cifrado ElGamal de la curva elíptica y el esquema de certificado implícito Qu-Vanstone de la curva elíptica. En el enfoque práctico, las puertas traseras se insertan de tal manera que su identificación es imposible mediante el análisis de la salida de un algoritmo. La detección de la implementación cleptográfica es una tarea compleja y se pueden encontrar muy pocos estudios en esta dirección. Hemos explorado la posibilidad de detectar código malicioso dentro de los algoritmos basados en la curva elíptica utilizando la idea del análisis de tiempo de ejecución. Hemos demostrado que al implementar un fuerte ataque Secretly Embedded Trapdoor con Universal Protection (SETUP) contra algoritmos basados en curvas elípticas, se puede detectar la presencia de backdoor analizando la diferencia de tiempo en la ejecución de una versión de código honesta frente a una versión maliciosa. También modificamos el mecanismo de inserción de la puerta trasera en el algoritmo de firma digital de la curva de Edwards que da como resultado una diferencia de tiempo insignificante, lo que hace imposible que el usuario detecte la presencia de la puerta trasera.Files
09151933.pdf.pdf
Files
(245 Bytes)
| Name | Size | Download all |
|---|---|---|
|
md5:0e5a21c5b796c5248a2eaeb022855600
|
245 Bytes | Preview Download |
Additional details
Additional titles
- Translated title (Arabic)
- هجوم كليبتوغرافي على بروتوكولات التشفير القائمة على المنحنى الإهليلجي
- Translated title (French)
- Attaque Kleptographique sur les Protocoles Cryptographiques Basés sur la Courbe Elliptique
- Translated title (Spanish)
- Ataque cleptográfico a protocolos criptográficos basados en curvas elípticas
Identifiers
- Other
- https://openalex.org/W3045738293
- DOI
- 10.1109/access.2020.3012823
References
- https://openalex.org/W1065290369
- https://openalex.org/W1480384237
- https://openalex.org/W1484363069
- https://openalex.org/W1499713421
- https://openalex.org/W1505760520
- https://openalex.org/W1521222412
- https://openalex.org/W1565174412
- https://openalex.org/W1575827919
- https://openalex.org/W1585524716
- https://openalex.org/W1860384618
- https://openalex.org/W1909991939
- https://openalex.org/W1927099252
- https://openalex.org/W2003736153
- https://openalex.org/W2017779503
- https://openalex.org/W2037107113
- https://openalex.org/W2050511336
- https://openalex.org/W2069900560
- https://openalex.org/W2129719496
- https://openalex.org/W2142489669
- https://openalex.org/W2343831954
- https://openalex.org/W2480544355
- https://openalex.org/W2507130841
- https://openalex.org/W2597323412
- https://openalex.org/W2949224125
- https://openalex.org/W2973121696
- https://openalex.org/W3014197012