The project involves work at (A) the theoretical design and analysis level and (B) work on protecting an actual implementation (side-channel countermeasures, runtime verification).
-
Step 1-A: Choice of security model (Lead: URJC, contributors: FAU, UM)
Starting out with established security models for AGKE, adequate adaptations for a post-quantum scenario are to be explored. In particular, we have to decide to what extent superposition should be allowed in communication channels, random oracle access, and adversarial tools, e.g., to reveal session keys. For authentication, we want to focus on the prominent scenarios where either a (quantum-safe) public-key infrastructure can be put into place or passwords are used. The exact formulation of the security model has to take into account the needs of property identification, so that runtime verification can later be applied meaningfully.
URJC will contribute the necessary expertise on security models for AGKE, FAU will ensure an adequate modeling of quantum capabilities, and UM will ensure that relevant properties can at least in principle be monitored at runtime in a software implementation. Goal of this step is to find a model which affords reasonably strong provable security guarantees in a post-quantum era, but at the same time is not overly generous with adversarial tools: It must still be feasible to design practical AGKE solutions in the suggested framework -- strong security guarantees which cannot be achieved with realistic resources, are not particularly helpful.
Risk 1: Critical part of the formalized security guarantees is not enforceable through property monitoring when implemented in software.
Mitigation: Regular consultation with PPD’s team in the exact formulation of the security model.
Risk 2: In an effort to capture a large class of attacks, adversarial capabilities can be modeled as too comprehensive, allowing capabilities which are far exceeding current technological reality. This may result in a situation, where no efficient quantum-safe AGKE solutions exist within the constructed framework.
Mitigation: By specializing the considered framework to the 2-party case only, a plausibility check with existing 2-party protocol proposals in the literature should be possible. We can check that it is at least plausible to prove an established 2-party solution as secure in such a restricted model (possibly with some minor adaptations to take care of technicalities like session identifiers.) In addition, we plan to establish a protocol compiler to lift a 2-party quantum-safe solution to a group solution. Even though such a “compiled” solution would likely be quite far from optimal in terms of efficiency, it would establish a very helpful baseline for quantum-safe AGKE.
Deliverable (D1): A formal security model for quantum-safe AGKE, along with a foundation for a suitable specification language to capture relevant AGKE properties for runtime verification.
-
Step 1-B: Implementation security of cryptographic primitives (Lead: STU, contributors: FAU)
To actually deploy an AGKE solution, it will be essential to have basic building blocks (like signature schemes) available which can effectively be protected against implementation-level attacks. For this project, the main primitives of interest are hash-based signatures, and encryption and signature solutions derived from code-based or lattice-based constructions. One of the team members is currently involved in the design of a code-based 2-party key establishment, known as CAKE (“[No Title]” 2017). Thanks to the work in a prior NATO SPS project, we expect that we will be able to establish implementation guidelines for protecting at least one of the promising candidate primitives against typical side-channel attacks. If side-channel protection against a particular primitive should turn out to be infeasible (respectively too costly), we would in the remainder of the project focus on an alternative mathematical platform.
Risk: If none of the promising cryptographic primitives affords efficient side-channel protection, the applicability of our quantum-safe AGKEs will be rather limited. Essentially, any settings where an adversary has physical access to a device participating in protocol runs become problematic.
Mitigation: There are at least two, conceptually different platforms, and with hash-based signatures there is a third platform to address authentication questions. The risk that none of these approaches can be implemented securely seems low. in particular, for code-based solutions we know from our results in a prior NATO SPS project that effective side-channel protection is feasible.(Chen et al. 2016).
Deliverable (D2): Implementation guidelines for side-channel resistant quantum-safe signing and for realizing basic operations as occurring in a quantum-safe 2-party key establishment (e.g., with a key encapsulation mechanism).
-
Step 2-A: Identify candidate protocol (Lead: URJC, contributors: FAU)
Based on the security framework developed in Step 1-A, provably secure protocols for quantum-safe AGKE are to be developed. From the results in in Step 1-A, generic constructions with protocol compilers are expected to be feasible, but in addition to this, dedicated designs with low communication complexity and/or optimized computational cost will be explored. Password-based and signature-based authentication are to be considered. To meet practical needs, we plan for hybrid solutions to be developed, which offer strong guarantees as long as at least one hardness assumption remains valid. A typical constellation would be a Computational or Decisional Diffie-Hellman assumption, which is combined with a Ring Learning With Errors assumption.
Risk: Authentication cost in protocols that authenticate with a public-key infrastructure will be very high, when using available quantum-safe signatures.
Mitigation: We anticipate that the number of signatures can be reduced by designing protocols in such a way that local views on session transcripts are signed at a late stage. However, in the worst case, one could consider a “pre-quantum” signature and exploit forward secrecy to nonetheless ensure secrecy of session keys. However, this would be somewhat cumbersome to handle for a public-key infrastructure, as in a post-quantum era signature keys would then have to be replaced (too) often.
Deliverable (D3): A complete design for a quantum-safe AGKE protocol, including security analysis with strong provable guarantees.
-
Step 2-B: Identify protocol-level security mechanisms (Lead: UM, contributor: STU, FAU, URJC)
Based on the work in Step 1-A and in coordination with the work in Step 2-A, techniques are to be developed to translate relevant security checks and properties into a suitable specification language. Then techniques are to be developed to compile these properties into monitors, either directly or by going through an intermediate language. Potential conflicts in combining countermeasures for side-channels (from Step 1-B) with techniques for runtime verification are to be explored.
Risk: Protocol details become available too late, because of slow progress in Step 2-A.
Mitigation: Already in Step 1-A, generic constructions for a quantum-safe solution with a protocol compiler are explored. The security-critical properties of an optimized AGKE construction and of a “compiled” protocol solution can be expected to be very similar. Thus, Step 2-B could still be started, and “catching up” with a delayed Step 2-A would most likely be feasible.
Deliverable (D4): Guidelines for securing an implementation of a quantum-safe AGKE against a substantial class of implementation-level attacks on a relevant target platform.
-
Step 3-A: Protocol and parameter optimization (Lead: FAU, contributor: STU, URJC)
To deploy an AGKE solution, the specific implementation parameters have to be fixed (key sizes, acceptable overhead cost for implementation-level protection). The exact choices will depend on the best state-of-the-art attacks (e.g., information-set-decoding when dealing with typical constructions from code-based cryptography) and on the security analysis (to be provided in Step 2-A). Understanding the potential of state-of-the-art attacks against the underlying hardness assumptions is to some extent a matter of theoretical analysis, but requires also experimental work, as available theoretical analyses of such attacks tend to be of asymptotic nature.
Risk: Implementing state-of-the-art attacks is a non-trivial effort, and running meaningful test cases can be quite time and resource consuming.
Mitigation: Only two types of assumptions are likely to be used, and we have experts for both types of assumptions in the project team. One the team members has hands-on experience with large-scale cryptanalytic calculations, and we have multiple teams in the project with substantial implementation experience. Thus we are confident that with the requested equipment all necessary calculations can be carried out in due time.
Deliverable (D5): A quantum-safe AGKE protocol where all parameter choices are fully specified for relevant security levels. Parameter recommendations must be derived from theoretical results or/and validated through experimental data.
-
Step 3-B: Deploy implementation-level security mechanisms (Lead: UM, contributor: FAU, STU)
Based on the guidelines and recommendations from Steps 2-B and 3-A, a quantum-safe AGKE is to be implemented and tested, including security mechanisms on the implementation level. To realize runtime verification of pertinent properties, monitors are deployed with the protocol using a minimally intrusive approach to keep overheads low. Rigorous testing will take place to ensure correct and robust implementation.
Risk: Despite parameter optimization, it may happen that the overhead cost resulting from runtime verification or side-channel protection comes with a serious performance loss.
Mitigation: If performance loss is severe, the number of properties verified at runtime can be reduced or/and side-channel countermeasures can be scaled back/removed. From a security point of view this is not desirable, but the resulting trade-off between efficiency and security would still be expected to offer a much higher security level than an unprotected implementation.
Deliverable (D6): A fully operational quantum-safe AGKE, including protection against implementation-level attacks.