Beyond the Finite Variant Property: Extending Symbolic Diffie-Hellman Group Models
Sofia Giampietro, Ralf Sasse, David Basin · 2026
Read Beyond the Finite Variant Property: Extending Symbolic Diffie-Hellman Group Models by Sofia Giampietro, Ralf Sasse, David Basin (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-21910.txt.
Introduction
Sofia Giampietro, Ralf Sasse, and David Basin work on the tools that check cryptographic protocols for flaws. Diffie-Hellman groups sit at the heart of secure key exchange, and symbolic verifiers model them to prove protocols safe. But the tools support only some of the math these groups allow.
In particular, they lack support for exponent addition. The reason is deep: the tools reason by unification, and unification becomes undecidable in the full theory of Diffie-Hellman operators. The team's 2026 preprint pushes beyond the finite variant property, a limit that has bounded what verifiers can handle. Extending these models would let automated checkers cover more real protocols, including ones whose security rests on the missing operations.
Catalog record
| CREATOR | Sofia Giampietro, Ralf Sasse, David Basin |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 26 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-21910
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Beyond the Finite Variant Property: Extending Symbolic Diffie-Hellman Group Models Sofia Giampietro, Ralf Sasse, David Basin Abstract Diffie-Hellman groups are commonly used in cryptographic protocols. While most state-of-the-art, symbolic protocol verifiers support them to some degree, they do not support all mathematical operations possible in these groups. In particular, they lack support for exponent addition, as these tools reason about terms using unification, which is undecidable in the theory describing all Diffie-Hellman operators. In this paper we approximate such a theory and propose a semi-decision procedure to determine whether a protocol, which may use all operations in such groups, satisfies user-defined properties. We implement this approach by extending the Tamarin prover to support the full Diffie-Hellman theory, including group element multiplication and hence addition of exponents. This is the first time a state-of-the-art tool can model and reason about such protocols. We illustrate our approach’s effectiveness with different case studies: ElGamal encryption and MQV. Using Tamarin, we prove security properties of ElGamal, and we rediscover known attacks on MQV. I Introduction Diffie-Hellman groups and their algebraic properties are the basis of many key exchange protocols, signature schemes, and symmetric encryption schemes. Diffie-Hellman groups are cyclic groups, defined by a group operation \cdot:G\times G\rightarrow G and a generator g . For a natural number n , we define g^{n} to denote g\cdot...\cdot g applied n times. 1 1 1 For some groups (notably elliptic curves) it is common to denote the group operation with the addition sign +:G\times G\rightarrow G and to denote the n -fold addition g+..+g by ng . In this paper, we will use the multiplicative notation and hence call this operation ‘multiplication’. Note that this operation is generally different from the usual multiplication (of natural numbers) between exponents. By the definition of the group operators, (g^{a})^{b}=g^{ab} and g^{a}\cdot g^{b}=g^{a+b} . Diffie-Hellman groups must furthermore satisfy the following property: finding a from g^{a} must be computationally hard. Examples of such groups are some modular arithmetic groups and some elliptic curves. Given the widespread use of Diffie-Hellman groups in security protocols, there has been considerable effort to support these group operations in automatic protocol verification tools. Most state-of-the-art tools (Tamarin, ProVerif, Maude-NPA, etc.) can model Diffie-Hellman groups in some way. However, their models are restricted: they support exponentiation and multiplication of exponents, but none can model the multiplication of group elements and hence the addition of exponents. Several challenges make modelling Diffie-Hellman group multiplication with these tools difficult. These tools operate in the symbolic model of cryptography, using equational theories to represent cryptographic primitives. Moreover, they rely on unification in their proof search. When the multiplication of group elements is considered, the exponents in Diffie-Hellman groups form a field. First, it is not straightforward to describe a field by an equational theory and hence any approach taken will use an equational theory that approximates fields. Second, to be practically useful, such an approximation must include associativity and commutativity of both the addition and the multiplication operator, and distributivity of multiplication over addition. Unfortunately, this interaction between distributivity and associativity makes unification both undecidable and infinitary [ diophantine ] . Namely, the unification problem may have as a solution an infinite set of most general unifiers. So even if we had an algorithm enumerating all unifiers, this would be impractical for automated tools that use unification. In this paper, we provide a semi-decision procedure for determining whether a protocol model that uses the full Diffie-Hellman group structure satisfies a given property, for a class of user-defined properties. Our approach does not rely on direct unification. Our starting point takes as inspiration results from Dougherty and Guttman [ dougherty , Dougherty14Decidability ] , who proposed a rewrite system containing both distributivity and associativity that closely approximates fields in the following sense: any theorem that can be proven using this rewrite system (henceforth called \mathit{DH} ) holds in all Diffie-Hellman group structures. Conversely, any equation that holds in infinitely many Diffie-Hellman structures is a theorem of the \mathit{DH} rewrite system. Dougherty and Guttman showed how this system can be used to prove the security of a restricted class of protocols. In our work, we target a wider class of protocols, and show how to integrate this approach into the Tamarin prover [ Tamarin ] . To the best of our knowledge, this is the first time an automated verification tool succeeds in analyzing protocols based on this mathematical structure. We restrict our results to protocols and properties that satisfy the following two conditions. C1 We assume that all terms that represent group elements belong to the same group. In other words, we assume there is a fixed group generator g , and all group elements are of the form g^{e} for some exponent e (possibly containing the addition operator). C2 Our approach is applicable to security properties that contain terms whose subterms do not cancel each other out. For example, this holds for any term that does not contain the + or \cdot operator. Since most protocols require parties to use a common fixed group, C1 is a modest restriction. The assumption C2 concerns the properties covered. In particular, it excludes making security verdicts about a term that can cancel itself out, i.e., which can be reduced to 1 or 0 . It does not exclude the other terms in the protocol canceling out. If a term can reduce to 1 or 0 , then it is likely that it will not satisfy many basic security properties (e.g. secrecy). Hence we expect that in most cases, either we find an attack for the property, or the protocol’s design and the property specification provide sufficient conditions to guarantee the non-cancellation assumption where necessary. The main idea of our approach is to first work with sub-terms in a simplified equational theory that does not contain the group multiplication, which allows us to use Tamarin’s current unification algorithm. In particular, to determine whether a target term is constructible, we first determine (via unification) whether its subterms are deducible. Since we assume they do not cancel each other out, if there is one such subterm that cannot be deduced, then we can already conclude that the target term cannot be constructed. If all subterms can be deduced, we then determine whether they can be combined, possibly using the group multiplication, to construct the target term. To do so, following [ Dougherty14Decidability ] , we interpret the symbolic terms as algebraic objects and use algebraic methods, e.g., Gauss elimination. Effectively, we replace the unification problem for terms containing the group operation with a system of algebraic equations. We implement this approach by modifying Tamarin’s constraint solving algorithm, and we show that the resulting constraint solving relation obtained is still sound and (under the non-cancellation property) also complete, in the sense that if Tamarin returns an attack with respect to a given property, then there is actually a protocol execution that violates the property and if Tamarin declares the protocol secure, then there is no execution violating the property. This holds within our symbolic model, i.e., our extension of Tamarin will find attacks that exploit particular properties of particular groups, rather only properties that can be described by