Pasar al contenido principal

FORMAL ANALYSIS AND VERIFICATION OF POST-QUANTUM CRYPTOGRAPHIC PROTOCOLS

PCI2020-120708-2

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos Programación Conjunta Internacional
Año convocatoria 2020
Plan Estatal 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSITAT POLITÈCNICA DE VALÈNCIA

Resultados relacionados

Resultados totales (Incluyendo duplicados): 7
Encontrada(s) 1 página(s)

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

An Efficient Canonical Narrowing Implementation with Irreducibility and SMT Constraints for Generic Symbolic Protocol Analysis

  • López-Rueda, Raúl|||0000-0002-2550-8041
  • Escobar Román, Santiago|||0000-0002-3550-4781
  • Sapiña-Sanchis, Julia|||0000-0003-2994-6986
[EN] Narrowing and unification are very useful tools for symbolic analysis of rewrite theories, and thus for any model that can be specified in that way. A very clear example of their application is the field of formal cryptographic protocol analysis, which is why narrowing and unification are used in tools such as Maude-NPA, Tamarin and Akiss. In this work we present the implementation of a canonical narrowing algorithm, which improves the standard narrowing algorithm, extended to be able to process rewrite theories with conditional rules. The conditions of the rules will contain SMT constraints, which will be carried throughout the execution of the algorithm to determine if the solutions have associated satisfiable or unsatisfiable constraints, and in the latter case, discard them., This work has been partially supported by the EC H2020-EU grant agreement No. 952215 (TAILOR) , by the grant PID2021-122830OB-C42 funded by MCIN/AEI/10.13039/501100011033 and ERDF A way of making Europe, by the grant CIPROM/2022/6 funded by Generalitat Valenciana, and by the grant PCI2020-120708-2 funded by MICIN/AEI/10.13039/501100011033 and by the European Union NextGenerationEU/PRTR. Raul Lopez has been supported by the grant FPI-2022- S2-49802 funded by Universitat Politecnica de Valencia.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Contribución de congreso (ConferenceOutput)

Protocol Dialects as Formal Patterns

  • Galán, D.
  • Meadows, C.
  • Meseguer, J.
  • García-Valero, Víctor|||0000-0003-0681-1130
  • Escobar Román, Santiago|||0000-0002-3550-4781
[EN] A protocol dialect is a lightweight method to obfuscate the communication exchanges between legitimate protocol users to make it hard for malicious users to interact with legitimate ones. So far, dialects have been based on a single obfuscation transformation, which we call a lingo. In this work dialects are generalized to become protocol and lingo generic. In this way they can be composed with other dialects for greater security. We present a formal semantics of dialects as formal patterns, i.e., as protocol transformations formalized in rewriting logic. We also present several attacker models and explain how our generalized notion of dialect can be used to harden dialects against such attackers., S. Escobar and V. Garcia have been partially supported by the grant PID2021-122830OB-C42 funded by MCIN/AEI/10.13039/501100011033 and ERDF A way of making Europe, by the grant CIPROM/2022/6 funded by Generalitat Valenciana, and by the grant PCI2020-120708-2 funded by MICIN/AEI/10.13039/501100011033 and by the European Union NextGenerationEU/PRTR. D. Galan, V. Garcia, C. Meadows, and J. Meseguer have been partially supported by ONR Code 311.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Formal Analysis of Post-Quantum Hybrid Key Exchange SSH Transport Layer Protocol

  • Tran, Duong Dinh
  • Ogata, Kazuhiro
  • Akleylek, Sedat
  • Otmani, Ayoub
  • Escobar Román, Santiago|||0000-0002-3550-4781
[EN] Facing the quantum attack threat, a quantum-resistant version of the SSH Transport Layer protocol has been proposed and been standardized by an IETF working group. This standardization process has been motivated by the fact that if practical quantum computers become available, classical key exchange algorithms used today will no longer be safe because their security can be efficiently broken by Shor's algorithm running on a quantum computer. In this paper, we construct a symbolic model of the proposed protocol, specify it in the specification language CafeOBJ, and conduct a formal analysis of the claimed security properties with the employment of a formal method tool called Invariant Proof Score Generator (IPSG). Three security properties are formally verified with respect to an unbounded number of protocol participants and protocol executions by employing IPSG to produce their formal proofs, the so- called proof scores in CafeOBJ. With another property, namely authentication, we find a counterexample against it, and then we propose to slightly revise the protocol. With the improved version, we formally verify that the authentication property is enjoyed, while the three properties remain secure. To model the presence of malicious participants, we extend the Dolev-Yao intruder, which is the standard intruder model used in security protocol analysis/verification, because the availability assumption of large-scale quantum computers gives the attacker some new capabilities. Under our threat model, the intruder is given capabilities of fully controlling the network as the Dolev-Yao intruder, and additionally breaking ECDH's security as well as compromising secrets., The work of Duong Dinh Tran and Kazuhiro Ogata was supported by the JST SICORP, Japan, under Grant JPMJSC20C2. The work of Santiago Escobar was supported in part by the MCIN/AEI/10.13039/501100011033 and ERDF A way of making Europe under Grant PID2021-122830OB-C42, in part by the Generalitat Valenciana under Grant CIPROM/2022/6, in part by the MICIN/AEI/10.13039/501100011033 under Grant PCI2020-120708-2, and in part by the European Union NextGenerationEU/PRTR. The work of Sedat Akleylek was supported in part by TUBITAK under Grant 121R006. The work of Ayoub Otmani was supported in part by the FAVPQC Project funded by CNRS, and in part by the Agence Nationale de la Recherche (ANR) within France 2030 Program under Grant ANR-22-PETQ-0008 PQ-TLS.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Formalization and analysis of the post-quantum signature scheme FALCON with Maude

  • García-Valero, Víctor|||0000-0003-0681-1130
  • Escobar Román, Santiago|||0000-0002-3550-4781
  • Ogata, Kazuhiro
[EN] Digital signatures ensure the authenticity and integrity of digital assets, vital properties for any secure communication. The National Institute of Standards and Technologies launched the Post-Quantum Cryptography project to standardise new algorithms and protocols that are secure against quantum attackers. The post-quantum signature scheme FALCON was one of the finalists. We present a continuation of the first steps towards the formal specification and analysis, in the high-performance language Maude, of signature schemes. We have adapted and improved a previous framework, originally aimed to formally specify and analyse post-quantum key encapsulation mechanisms. As a use case of the new framework, we specify an executable symbolic model of FALCON. On the symbolic model, we verify termination and fairness using LTL formulas with Maude's model checker. Furthermore, authentication, integrity and non-repudiation are analysed through invariant analysis. Integrity and non-repudiation hold, meanwhile, authentication does not hold in our symbolic model., star Santiago Escobar and Victor Garcia have been partially supported by the grant PID2021-122830OB-C42 funded by MCIN/AEI/10.13039/501100011033 and ERDF A way of making Europe, by the grant CIPROM/2022/6 funded by Generalitat Valenciana, by INCIBE's Chair funded by the EU-NextGenerationEU through the Spanish government's Plan de Recuperacion, Transformacion y Resiliencia, and by the grant PCI2020-120708-2 funded by MICIN/AEI/10.13039/501100011033 and by the European Union NextGenerationEU/PRTR. Kazuhiro Ogata has been partially supported by JSPS KAKENHI Grant Number 24KK0185.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Modeling and verification of the post-quantum key encapsulation mechanism KYBER using Maude

  • García-Valero, Víctor|||0000-0003-0681-1130
  • Escobar Román, Santiago|||0000-0002-3550-4781
  • Ogata, Kazuhiro
[EN] Communication and information technologies shape the world¿s systems of today, and those systems shape the society we live in. The security of those systems relay on mathematical problems hard to solve for classical computers, that is, the available current computers. Recent advances in quantum computing threat the security of our systems and the communications we use. In order to face the threat, multiple solutions and protocols have been proposed. Kyber is one of them, specifically it is a key encapsulation mechanism that bases its security in the learning with errors problem over module lattices. This master¿s thesis focuses on the analysis of Kyber to check its security under Dolev-Yao adversary assumptions. For that matter, we first learn about the current state of the solutions proposed against the threat quantum adversaries suppose and study how Kyber works. We then construct in the system-specification language Maude, a symbolic model to represent the behaviour of Kyber in a network. On this model we conduct reachability analysis with the search command and find that a Man-In-The-Middle attack is present. Then we use the Maude LTL logical model checker to extend the analysis of the system with proving if a liveness and a security property hold.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Modelling and verification of post-quantum key encapsulation mechanisms using Maude

  • García-Valero, Víctor|||0000-0003-0681-1130
  • Escobar Román, Santiago|||0000-0002-3550-4781
  • Ogata, Kazuhiro
  • Akleylek, Sedat
  • Otmani, Ayoub
[EN] Communication and information technologies shape the world's systems of today, and those systems shape our society. The security of those systems relies on mathematical problems that are hard to solve for classical computers, that is, the available current computers. Recent advances in quantum computing threaten the security of our systems and the communications we use. In order to face this threat, multiple solutions and protocols have been proposed in the Post-Quantum Cryptography project carried on by the National Institute of Standards and Technologies. The presented work focuses on defining a formal framework in Maude for the security analysis of different postquantum key encapsulation mechanisms under assumptions given under the DolevYao model. Through the use of our framework, we construct a symbolic model to represent the behaviour of each of the participants of the protocol in a network. We then conduct reachability analysis and find a man-in-the-middle attack in each of them and a design vulnerability in Bit Flipping Key Encapsulation. For both cases, we provide some insights on possible solutions. Then, we use the Maude Linear Temporal Logic model checker to extend the analysis of the symbolic system regarding security, liveness and fairness properties. Liveness and fairness properties hold while the security property does not due to the man-in-the-middle attack and the design vulnerability in Bit Flipping Key Encapsulation., Victor Garcia and Santiago Escobar were supported by the grant PID2021-122830OB-C42 funded by MCIN/AEI/10.13039/501100011033 and ERDF A way of making Europe and by the grant PCI2020-120708-2 funded by MICIN/AEI/10.13039/501100011033 and by the European Union NextGenerationEU/PRTR. Kazuhiro Ogata was supported by JST SICORP Grant Number JPMJSC20C2, Japan. Sedat Akleylek was supported by TUBITAK under Grant No. 121R006. Ayoub Otmani was supported by FAVPQC project funded by CNRS and by the grant ANR-22-PETQ-0008 PQ-TLS funded by Agence Nationale de la Recherche (ANR) within France 2030 program. There was no additional external funding received for this study. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.
Docta Complutense
Publicación Contribución de congreso (ConferenceOutput)

Equational Unification and Matching, and Symbolic Reachability Analysis in Maude 3.2 (System Description)

  • Durán, Francisco
  • Eker, Steven
  • Escobar, Santiago
  • Martí Oliet, Narciso
  • Meseguer, José
  • Rubio Cuéllar, Rubén Rafael
  • Talcott, Carolyn
Equational unification and matching are fundamental mechanisms in many automated deduction applications. Supporting them efficiently for as wide as possible a class of equational theories, and in a typed manner supporting type hierarchies, benefits many applications; but this is both challenging and nontrivial. We present Maude 3.2’s efficient support of these features as well as of symbolic reachability analysis of infinite-state concurrent systems based on them.