capbtabboxtable[][]

# Methods for Collisions in Some
Algebraic Hash Functions

Simran Tinani This research is supported by armasuisse Science and Technology.

###### Abstract

This paper focuses on devising methods for producing collisions in algebraic
hash functions that may be seen as generalized forms of the well-known Zémor
and Tillich-Zémor hash functions. In contrast to some of the previous
approaches, we attempt to construct collisions in a structured and
deterministic manner by constructing messages with triangular or diagonal
hashes messages. Our method thus provides an alternate deterministic approach
to the method for finding triangular hashes in [14]. We also consider the
generalized Tillich-Zémor hash functions over $\mathbb{F}_{p}^{k}$ for $p\neq
2$, relating the generator matrices to a polynomial recurrence relation, and
derive a closed form for any arbitrary power of the generators. We then
provide conditions for collisions, and a method to maliciously design the
system so as to facilitate easy collisions, in terms of this polynomial
recurrence relation. Our general conclusion is that it is very difficult in
practice to achieve the theoretical collision conditions efficiently, in both
the generalized Zémor and the generalized Tillich-Zémor cases. Therefore,
although the techniques are interesting theoretically, in practice the
collision-resistance of the generalized Zémor functions is reinforced.

##  1 Introduction

Let $\mathcal{A}$ be an alphabet and $\mathcal{A}^{*}$ denote the set of all
finite-length words in $\mathcal{A}$ and $\mathcal{A}^{n}$ denote the set of
all words up to length $n$ in $\mathcal{A}$. A length $n$ hash function, or
compression function, is a map $\mathcal{A}^{*}\rightarrow\mathcal{A}^{n}$
which takes messages of arbitrary length to fixed-length message digests. A
hash function $h:\mathcal{A}^{*}\rightarrow\mathcal{A}^{n}$ is called a
cryptographic hash function if it satisfies the following properties:

  * •

Collision-resistance: it is computationally infeasible to find a pair
$x,x^{\prime}$ of distinct messages such that $h(x)=h(x^{\prime})$.

  * •

Second pre-image resistance: given a message $x$, it is computationally
infeasible to find another message $x^{\prime}\neq x$ such that
$h(x)=h(x^{\prime})$.

  * •

One-wayness: given a hash value $y\in\mathcal{A}^{n}$ it is computationally
infeasible to find a pre-image $x\in\mathcal{A}$ such that $h(x)=y$.

Cryptographic hash functions are also often required to exhibit the avalanche
effect, under which a small modification in the message text causes a big
change in the hash. This prevents the hash value from leaking information
about the message string, and ensures no visible correlation between the
hashes of related strings. A hash function that does not exhibit this property
is called mallaeble.

Several widely used hash functions, including the NIST-standardized SHA
(Secure Hash Algorithms) functions [9], are built from block ciphers. While
the state of the art block cipher-based hash functions have shown considerable
resiliency to attacks, their security is nevertheless heuristic; in other
words, it does not reduce to a well-known difficult mathematical problem. The
search for a provably secure hash function is therefore, at the least, of
theoretical interest.

The idea of building hash functions from a group and its corresponding Cayley
graph was introduced in [18]. The generic design of Cayley hash functions has
several advantages over traditional hash functions. Firstly, their security is
equivalent to some concise mathematical problem. Cayley hash functions are
also inherently parallelizable, i.e. allow for simultaneous computation of the
hash value of different parts of the message, and recombining these at the
end. While the Tillich-Zémor hash functions are slower than SHA-256, they can
be designed to have reasonably efficient implementations: in [15] it is stated
that they can be made faster than SHA-1. In particular, when fields of
characteristic 2 are used, the group law is the most efficient.

There may also be other disadvantages of Cayley hash functions. By themselves,
such hash functions are inherently mallaeble: given a hash $h(m)$ of an
unknown message $m$, $h(x_{1}||m||x_{2})=h(x_{1})h(m)h(x_{2})$ for any texts
$x_{1},x_{2}$. Further, they lack preimage resistance for small messages.
However, in [15], the authors describe a heuristic modification which
seemingly resolves these issues, as well as enhances the efficiency. Cayley
hash functions have a simple, elegant, clear design related to hard
mathematical problems. A very generic description is given below.

######  Definition 1 (Cayley hash function).

Let $G$ be a finite group with a set of generators $S$ and $\mathcal{A}$ be an
alphabet the same size as $S$. Given an injective map
$\pi:\mathcal{A}\rightarrow S$, one may define the hash value of the message
$x_{1}x_{2}\dots x_{k}$ to be the group element
$\pi(x_{1})\pi(x_{2})\ldots\pi(x_{k})$.

Typically, one is concerned only with binary messages, and therefore with two-
generator Cayley hash functions. The common design principle behind the Cayley
hash functions is the performance of a walk on a regular Cayley graph
according to the bits of an input message, the last vertex giving the hash
value.

######  Definition 2 (Cayley Graph).

Let $G$ be a group and $S$ a subset of elements of $G$. The Cayley graph of
$C_{G,S}=(V,E)$ of $G$ with respect to $S$ is defined to have vertices $v_{g}$
corresponding to each element $g\in G$, and edges $(v_{g_{1}},v_{g_{2}})\in
E\iff\exists s\in S$ such that $g_{2}=g_{1}s$. Here, the set $S$ is the set of
graph generators.

The security of a Cayley hash function defined on a group $G$ is determined by
the properties of the corresponding graph. More precisely, the difficulty of
producing collisions for such a hash function depends on the difficulty of
solving the factorization problem in a certain finite non-abelian group.

######  Definition 3 (Factorization problem).

Let $G$ be a group with generators $S=\\{s_{1},\ldots,s_{k}\\}$ and $L>0$ be a
fixed constant. Given $g\in G$, return $m_{1},\ldots,m_{L}$ and $\ell\leq L$,
with $m_{i}\in\\{1,\ldots,k\\}$ such that
$\prod\limits_{i=1}^{\ell}s_{m_{i}}=g$. The factorization problem for $g=1$
fixed is called the representation problem.

Apart from hash functions, the difficulty of factorization in finite matrix
groups has been used to build some key exchange, encryption and authentication
schemes [4, 3, 2].

Factorization in finite groups is related to the famous conjecture of Babai on
the diameter of Cayley graphs, which states that diameter of any undirected
Cayley graph of non-abelian simple group is polylogarithmic in group size. In
other words, “short” factoriations always exist for finite non-abelian groups,
regardless of the choice of generating set. The conjecture is known to be true
for certain groups like
$SL_{2}(2,\mathbb{F}_{p}),SL_{2}(2,\mathbb{F}_{2^{k}})$. However, existing
generic proofs for any generating set are non-constructive. In [19], the
following Cayley hash function was defined in the group
$G=SL_{2}(\mathbb{F}_{p})$:

######  Definition 4 (Zémor Hash Function).

Choose the generators $A_{0}=\begin{pmatrix}1&1\\\ 0&1\end{pmatrix}$,
$A_{1}=\begin{pmatrix}1&0\\\ 1&1\end{pmatrix}$ of $SL_{2}(\mathbb{F}_{p})$.
For a message $m=m_{1}m_{2}\ldots m_{k}\in\\{0,1\\}^{*}$ define $H(m_{1}\ldots
m_{k})=A_{m_{1}}\ldots A_{m_{k}}$.

This hash function, given in [19] was attacked for both collisions and
preimages in [16] using the Euclidean algorithm. However, this attack is
specific to the generators $A_{0}$ and $A_{1}$. In [13], it is claimed that
the system is potentially secure by replacing $A_{0}$ and $A_{1}$ by
$A_{0}^{2}$ and $A_{1}^{2}$. We define the _generalized Zémor hash function_
as above, but using generators $A_{0}=\begin{pmatrix}1&\alpha\\\
0&1\end{pmatrix}$ and $A_{1}=\begin{pmatrix}1&0\\\ \beta&1\end{pmatrix}$ over
${\mathbb{F}_{p}}^{k}$. While the generators $A_{0}$ and $A_{1}$ have
multiplicative order $p$, and so one trivially has collisions of length $p$
with the empty word, we nevertheless also consider the case $k>1$ and study
the difficulty of finding non-trivial collisions (i.e. collisions of non-empty
words).

The following variant of the above hash function was later proposed in [7].

######  Definition 5 (Tillich-Zémor Hash function).

Let $n>0$ and $p(x)$ be an irreducible polynomial over $\mathbb{F}_{2}$. Write
$K=\mathbb{F}_{2}[x]/p(x)$. Consider $A_{0}=\begin{pmatrix}x&1\\\
1&0\end{pmatrix}$ and $A_{1}=\begin{pmatrix}x&x+1\\\ 1&1\end{pmatrix}$, which
are generators of $SL_{2}(K)$. For a message $m=m_{1}m_{2}\ldots
m_{k}\in\\{0,1\\}^{*}$ define $H(m_{1}\ldots m_{k})=A_{m_{1}}\ldots
A_{m_{k}}\pmod{p(x)}$. $K=\mathbb{F}_{2}[x]/\langle q(x)\rangle\cong
F_{2^{n}}$.

Collisions for this hash function for these set of generators were found in
[6]. This attack uses the structure in hash values of palindromic messages,
and a result of Mesirov-Sweet [8] on the Euclidean algorithm for polynomials
$x$ and $x+1$ in characteristic 2. This attack was extended to recover
preimages in [12]. Since current attacks do not allow controlling of the forms
of collisions, and work specifically for the set of generators $A_{0}$ and
$A_{1}$, the security is an open problem for general parameters.

In [10], the authors provide a new heuristic algorithm for factoring generic
generator sets by reducing them to contain a “trapdoor” matrix. Their
algorithm is subexponential in time, memory, and factorization lengths. This
algorithm, however, does not yield a practical attack on the Tillich-Zémor
design with generic generators for $n=160$. In fact, to the best of knowledge
till date, the collision and preimage resistance are recovered by replacing
$A_{0}$ and $A_{1}$ by $B_{0}=\begin{pmatrix}x^{2}&1\\\ 1&0\end{pmatrix}$ and
$B_{1}=\begin{pmatrix}x+1&1\\\ 1&0\end{pmatrix}$ [14]. We define the
_generalized Tillich-Zémor hash function_ as above, but using generators
$A_{0}=\begin{pmatrix}\alpha&1\\\ 1&0\end{pmatrix}$ and
$A_{1}=\begin{pmatrix}\beta&1\\\ 1&0\end{pmatrix}$ where
$\alpha,\beta\in{\mathbb{F}_{p}}^{k}$.

It has also been proposed to use LPS Ramanujan graphs [17] to construct Cayley
hash functions. However, these have also been cryptanalyzed [11]. Some other
methods of cryptanalysis for Cayley hash functions are discussed in [13].

##### Collisions from Triangular and Diagonal Matrices

In [14], it is shown that if one can produce “sufficiently many” messages
whose images in the matrix groups are upper/lower triangular, then one can
find collisions of the generalized Zémor and Tillich-Zémor hash functions.

######  Proposition 1.

Let $n$ be such that discrete logarithms can be solved in
$\mathbb{F}_{2^{n}}^{*}$. Let $\mathcal{D}$, $\mathcal{T}^{up}$,
$\mathcal{T}^{low}$, $\mathcal{L}^{v}$, $\mathcal{R}^{v}\subset
SL_{2}(\mathbb{F}_{2^{n}})$ be the subgroups of diagonal, upper and lower
triangular matrices and the subgroup of matrices with left or right
eigenvector $v$. If an attacker can compute $N$ random elements $M_{i}$ of one
of these subgroups together with bit sequences $m_{i}$ of length at most $L$
hashing to these matrices, then he can also find a message $m$ such that
$H_{ZT}(m)=I$. The message $m$ has expected size smaller than $NL2^{n/N}$ in
the diagonal case and smaller than $NL2^{1+n/N}$ in the other cases.

In this same work, the authors use random probabilistic search to find pre-
images of upper/lower triangular matrices, and subsequently uses these to
produce collisions. This approach works for any Cayley hash function, and for
$SL_{2}$ groups over any finite field.

## Summary of Contributions

This paper focuses on devising methods for producing collisions in algebraic
hash functions that may be seen as generalized forms of the well-known Zémor
and Tillich-Zémor hash functions. In contrast to some of the previous
approaches, we attempt to construct collisions in a structured and
deterministic manner.

In Section 2, we introduce a method for constructing messages with triangular
or diagonal hashes messages. For this, we extend existing hash values in
$SL_{2}({\mathbb{F}_{p}}^{k})$ into triangular or diagonal form by multiplying
with products of the form $A_{0}^{m}A_{1}^{n}$, where
$A_{0}=\begin{pmatrix}1&\alpha\\\ 0&1\end{pmatrix}$ and
$A_{1}=\begin{pmatrix}1&0\\\ \beta&1\end{pmatrix}$ denote generators. More
precisely, we consider the following problem.

######  Problem 1.

Given a matrix $C\in SL_{2}({\mathbb{F}_{p}}^{k})$ formed as product of
$A_{0}$ and $A_{1}$, find the conditions under which there exist integers $m$
and $n$ (of size significantly smaller than $p^{k}$) such that
$CA_{0}^{m}A_{1}^{n}$ is upper/lower triangular, or even diagonal. Compute $m$
and $n$ if they exist.

We also discuss the application of this method to produce collisions, and the
feasibility and efficiency thereof. Our method thus provides an alternate
deterministic approach to the method for finding triangular hashes in [14].

In Section 3, we consider the generalized Tillich-Zémor hash functions over
${\mathbb{F}_{p}}^{k}$ for $p\neq 2$, relating the generator matrices to a
polynomial recurrence relation, and derive a closed form for any arbitrary
power of the generators. We then provide conditions for collisions, and a
method to maliciously design the system so as to facilitate easy collisions,
in terms of this polynomial recurrence relation.

On simplifying the general criteria, and through experiments, our general
conclusion is that it is very difficult in practice to achieve the theoretical
collision conditions efficiently, in both the generalized Zémor and the
generalized Tillich-Zémor cases. Therefore, although the techniques are
interesting theoretically, in practice the collision-resistance of the
generalized Zémor functions is reinforced.

##  2 Generalized Zémor Hash functions

######  Definition 6 (Generalized Zémor hash functions).

Consider the generators $A_{0}=\begin{pmatrix}1&\alpha\\\ 0&1\end{pmatrix}$
and $A_{1}=\begin{pmatrix}1&0\\\ \beta&1\end{pmatrix}$ in the group
$SL_{2}({\mathbb{F}_{p}}^{k})$. For a message $m=m_{1}m_{2}\ldots
m_{k}\in\\{0,1\\}^{*}$ define the hash value $H(m_{1}\ldots
m_{k})=A_{m_{1}}\ldots A_{m_{k}}$.

The Zémor hash function proposed in [19] is a special case of this, with
$\alpha=1=\beta$. In [13] it was suggested that security is preserved when
$s_{0}^{2}$ and $s_{1}^{2}$ are used instead, these cases correspond to the
values $\alpha=2=\beta$. Thus, the generalized Zémor hash functions are so far
secure.

Clearly, $A_{0}^{m}=\begin{pmatrix}1&m\alpha\\\ 0&1\end{pmatrix}$ and
$A_{1}^{n}=\begin{pmatrix}1&0\\\ n\beta&1\end{pmatrix}$ for any integers $m$
and $n$. $A_{0}$ and $A_{1}$ have multiplicative orders $p$, so trivial
collisions of length $p$ with the empty word always exist. Nevertheless, we
study the general case of non-trivial collisions in the finite field
${\mathbb{F}_{p}}^{k}$. In general, one is interested in finding collisions
with a significantly smaller length than the orders, at most, say
$\mathcal{O}(\sqrt{p})$.

###  2.1 Euclidean Algorithm Attack for $\alpha=\beta=1$

In this subsection, we describe the attack of [16], which uses the Euclidean
algorithm, and explain why it fails if one chooses $\alpha\neq 1$, $\beta\neq
1$ in the hash function design. Consider a matrix $X=\begin{pmatrix}a&b\\\
c&d\end{pmatrix}\in SL_{2}(\mathbb{F}_{p})$ and suppose that we have found a
non-identity matrix $Y=\begin{pmatrix}A&B\\\ C&D\end{pmatrix}\in
SL_{2}(\mathbb{Z})$ that reduces modulo $p$ to $X$.Let
$A_{0}=\begin{pmatrix}1&1\\\ 0&1\end{pmatrix},\ A_{1}=\begin{pmatrix}1&0\\\
1&1\end{pmatrix}$. Consider the general case with generators
$\tilde{A_{0}}=A_{0}^{\alpha}=\begin{pmatrix}1&\alpha\\\ 0&1\end{pmatrix}$,
$\tilde{A_{1}}=A_{1}^{\beta}=\begin{pmatrix}1&0\\\ \beta&1\end{pmatrix}$.

We write

$Y=\begin{pmatrix}A&B\\\ C&D\end{pmatrix}=\begin{pmatrix}a_{i}&b_{i}\\\
c_{i}&d_{i}\end{pmatrix}A_{0}^{\alpha q_{i}}A_{1}^{\beta q_{i-1}}\ldots
A_{0}^{\alpha q_{2}}A_{1}^{\beta q_{1}}$

where $\begin{pmatrix}a_{0}&b_{0}\\\
c_{0}&d_{0}\end{pmatrix}=\begin{pmatrix}A&B\\\ C&D\end{pmatrix}$. Since the
matrix $X$ is obtained as a product of $\tilde{A_{0}}$ and $\tilde{A_{1}}$,
there exists an integer $n$ such that $\begin{pmatrix}a_{n}&b_{n}\\\
c_{n}&d_{n}\end{pmatrix}=A_{0}^{\alpha p_{n}}$ or
$\begin{pmatrix}a_{n}&b_{n}\\\ c_{n}&d_{n}\end{pmatrix}=A_{0}^{\alpha
p_{n}}=A_{1}^{\beta q_{n}}$. We wish to determine the values of the $q_{i}$,
$1\leq i\leq n$ for such an $n$. We have, for $1\leq i\leq n$,

$\displaystyle a_{i}$ $\displaystyle=a_{i-1}-\beta b_{i-1}q_{i-1}$
$\displaystyle b_{i}$ $\displaystyle=b_{i-1}-\alpha a_{i-1}q_{i}$
$\displaystyle c_{i}$ $\displaystyle=c_{i-1}-\beta d_{i-1}q_{i-1}$
$\displaystyle d_{i}$ $\displaystyle=d_{i-1}-\alpha c_{i-1}q_{i}$ (1)

where $\begin{pmatrix}a_{0}&b_{0}\\\
c_{0}&d_{0}\end{pmatrix}=\begin{pmatrix}A&B\\\ C&D\end{pmatrix}$ are the only
fixed values of the $a_{i},b_{i},c_{i},d_{i}$’s and $\alpha,\beta$ are treated
as integers smaller than $p$.

##### Case $\alpha=\beta=1$

First assume that $\alpha=\beta=1$. Since $AD-BC=1$, $\gcd(A,B)=\gcd(C,D)=1$,
and we have either $A>B$ or $D>C$. We consider the case $A>B$, the argument
for other case is analogous. Let $q_{1},\ldots,q_{n}$ be the quotients that
appear when Euclidean algorithm is applied to $(A,B)$, i.e.

$\displaystyle A$ $\displaystyle=Bq_{1}+r_{1}$ $\displaystyle B$
$\displaystyle=r_{1}q_{2}+r_{2}$ $\displaystyle\vdots$ $\displaystyle r_{i}$
$\displaystyle=r_{i+1}q_{i+2}+r_{i+2}$ $\displaystyle\vdots$ $\displaystyle
r_{n-2}$ $\displaystyle=r_{n-1}q_{n}=\gcd(A,B)q_{n}=q_{n}$

Note that $YA_{1}^{-q_{1}}A_{0}^{-q_{2}}=\begin{pmatrix}r_{1}&r_{2}\\\
C-Dq_{1}&-q_{2}(C-Dq_{1})+D\end{pmatrix}$, and for $i$ odd,
$YA_{1}^{-q_{1}}A_{0}^{-q_{0}}\ldots
A_{1}^{-q_{i}}=\begin{pmatrix}r_{i}&r_{i-1}\\\ \star&\star\end{pmatrix}$ and
$YA_{1}^{-q_{1}}A_{0}^{-q_{0}}\ldots
A_{1}^{-q_{i}}A_{0}^{-q_{i+1}}=\begin{pmatrix}r_{i}&r_{i+1}\\\
\star&\star\end{pmatrix}$. If $n$ is even then
$YA_{1}^{-q_{1}}A_{0}^{-q_{2}}\ldots A_{0}^{-q_{n}}=\begin{pmatrix}1&0\\\
q&1\end{pmatrix}=A_{1}^{x}$, for some $q\in\mathbb{Z}$, ($q<C$) since
$r_{n-1}=1$. In other words, we have $Y=A_{0}^{q_{n}}A_{1}^{q_{n-1}}\ldots
A_{0}^{q_{2}}A_{1}^{q_{1}+q}$ where $q_{1},\ldots,q_{n},q$ are obtained when
the Euclidean algorithm is applied to $(A,B)$. The practical application of
this principle to produce collisions of reasonable length is demonstrated in
[16]. This gives a polynomial time solution for collisions.

##### Case $\alpha\neq 1,\;\beta\neq 1$

In the case with general $\alpha,\beta$, there is no clear protocol to solve
the set of equations (2.1) for the $q_{i}$’s. For instance, we start with the
assumption that $A>B$, but it may still happen that $A\leq\beta B$, and then
there is no clear way to apply the Euclidean algorithm.

###  2.2 Extending messages for diagonal hashes over $\mathbb{F}_{p}$

In this subsection, we discuss the extension of messages to produce diagonal
hashes in $SL_{2}(\mathbb{F}_{p})$. The below lemma demonstrates the
production of a diagonal matrix starting with the hash of an arbitrary
message.

For a matrix $C$, we denote by $C[i,j]$ the $(i,j)^{\text{th}}$ entry of $C$.
Further, a message is denoted in its binary string representation
$m=0^{n_{1}}1^{m_{1}}\ldots 0^{n_{r}}1^{m_{r}}$ where multiplication
corresponds to concatenation, and for $b\in\\{0,1\\}$, the string $b^{n}$
denotesf the concatenation of $n$ consecutive $b$-bits.

######  Lemma 1.

Let $z$ be any message and $C:=H(z)\in SL_{2}(\mathbb{F}_{p})$ be its
corresponding hash value. Assume that $a:=C[0,0]\neq 0$. Then there exist
integers $m,n\in\\{0,1,\ldots,p-1\\}$ such that $C\cdot A_{0}^{m}\cdot
A_{1}^{n}$ is a diagonal matrix and $(C\cdot A_{0}^{m}\cdot
A_{1}^{n})[0,0]=C[0,0]$.

  * Proof.

Write $C=\begin{pmatrix}a&b\\\ c&d\end{pmatrix}$. Set $m=-b/(a\alpha)$ and
$n=-ac/\beta$. Then

$\displaystyle C\cdot A_{0}^{m}\cdot
A_{1}^{n}=\begin{pmatrix}a(1+mn\alpha\beta)+nb\beta&0\\\
c(1+mn\alpha\beta)+nd\beta&mc\alpha+d\end{pmatrix}$

Now, $c(1+mn\alpha\beta)+nd\beta=c(1+bc)-acd=c-c(ad-bc)=0$, since $C\in
SL_{2}({\mathbb{F}_{p}}^{k})$. Further,
$A(1+mn\alpha\beta)+nb\beta=a(1+bc)-abc=a$, and $mc\alpha+d=-bc/a+d=1/a$.
Thus, $C\cdot A_{0}^{m}\cdot A_{1}^{n}=\begin{pmatrix}a&0\\\
0&a^{-1}\end{pmatrix}$. ∎

####  2.2.1 Generating Collisions

In [14], the authors describe a method which uses the representation of 1 and
pre-images of multiple diagonal matrices to produce a collision with the hash
$H()$ of the empty word. We show here that Lemma 1 can be used to generate
collisions in an alternative fashion. Let $z$ be any message and $C:=H(z)\in
SL_{2}(\mathbb{F}_{p})$ be its hashed value. Observe that for any integers $m$
and $n$, the matrix $D:=A_{1}^{n}\cdot C\cdot A_{0}^{m}$ satisfies
$D[0,0]=C[0,0]$. Pick arbitrary distinct integers $n_{1},m_{1},n_{2},m_{2}$
and set $D_{1}:=A_{1}^{n_{1}}\cdot C\cdot A_{0}^{m_{1}}$and
$D_{2}:=A_{1}^{n_{2}}\cdot C\cdot A_{0}^{m_{2}}$. Then clearly,
$D_{1}[0,0]=C[0,0]=D_{2}[0,0]$. Now apply Lemma 1 and find integers
$\tilde{m}_{1},\tilde{m}_{2},\tilde{n}_{1},\tilde{n}_{2}$ such that
$\tilde{D_{1}}:=D_{1}\cdot A_{0}^{\tilde{m}_{1}}\cdot A_{1}^{\tilde{n}_{1}}$
and $\tilde{D_{2}}=D_{2}\cdot A_{0}^{\tilde{m}_{2}}\cdot
A_{1}^{\tilde{n}_{2}}$ are diagonal and satisfy
$\tilde{D_{1}}[0,0]=D_{1}[0,0]=C[0,0]$ and
$\tilde{D_{2}}[0,0]=D_{2}[0,0]=C[0,0]$. Since $\tilde{D_{1}}$ and
$\tilde{D_{2}}$ are diagonal, have the same entry, and lie in
$SL_{2}(\mathbb{F}_{p})$, they must be equal, i.e.
$\tilde{D_{1}}=\tilde{D_{2}}$. Defining $z_{1}=1^{n_{1}}\cdot z\cdot
0^{m_{1}+\tilde{m}_{1}}\cdot 1^{\tilde{n_{1}}}$ and $z_{2}=1^{n_{2}}\cdot
z\cdot 0^{m_{2}+\tilde{m}_{2}}\cdot 1^{\tilde{n_{2}}}$. Clearly, $z_{1}\neq
z_{2}$ but $H(z_{1})=H(z_{2})$.

######  Example 1.

For $p=7919$, $\alpha=5698$, $\beta=6497$, consider the message text

$\displaystyle z=$ $\displaystyle
0^{44}1^{41}0^{17}1^{49}0^{47}1^{17}0^{50}1^{31}0^{15}1^{10}0^{39}1^{12}0^{2}1^{0}0^{24}1^{41}0^{28}1^{23}0^{9}1^{0}0^{47}1^{23}0^{1}1^{30}0^{18}$
$\displaystyle
1^{32}0^{24}1^{14}0^{0}1^{49}0^{19}1^{28}0^{24}1^{26}0^{26}1^{26}0^{11}1^{1}0^{17}1^{20}0^{38}1^{22}0^{12}1^{38}0^{8}1^{33}0^{39}1^{42}0^{47}1^{29}$
$\displaystyle
0^{10}1^{41}0^{14}1^{45}0^{13}1^{40}0^{42}1^{13}0^{2}1^{6}0^{40}1^{31}0^{2}1^{27}0^{1}1^{7}0^{36}1^{19}0^{3}1^{25}0^{10}1^{27}0^{21}1^{2}0^{12}1^{23}$
$\displaystyle
0^{36}1^{8}0^{25}1^{39}0^{36}1^{0}0^{19}1^{39}0^{37}1^{32}0^{14}1^{4}0^{3}1^{12}0^{16}1^{23}0^{49}1^{25}0^{23}1^{19}0^{46}1^{23}0^{36}1^{31}$

We have, $H(z)=\begin{pmatrix}4812&5537\\\ 4987&1690\end{pmatrix}$. Choose
random numbers $m_{1}=18,n_{1}=30$, $m_{2}=35$, $n_{2}=33$ and compute
$\tilde{m_{1}}=6208,\tilde{n_{1}}=744$, $\tilde{m_{2}}=6191$,
$\tilde{n_{2}}=180$ using Lemma 1. Then for $z_{1}=1^{30}\cdot z\cdot
0^{6226}1^{744}$ and $z_{2}=1^{33}\cdot z\cdot 0^{6226}1^{180}$ we have the
collision $H(z_{1})=H(z_{2})=\begin{pmatrix}4812&0\\\ 0&1542\end{pmatrix}$.

It is clear that the above method provides a deterministic technique to
produce arbitratrily many distinct non-trivial collisions of size
$\mathcal{O}(p)$. For the collisions to be of practical length, we further
require that the values of the exponents $m$ and $n$ are considerably small
relative to $p$ so that the resulting messages are of reasonable length.

##### Experimental results

We looked for such $m$ and $n$ by random computer search in the above
examples, using randomly generated messages of reasonable length and checking
for the condition $m=-b/(a\alpha)<\sqrt{p}$ and $n=-ac/\beta<\sqrt{p}$.
Unfortunately, for larger values of $p$, experiments indicate a very low
probability of finding such values. For $30-40$ digit primes, brute force
could no longer find any such examples.

The below proposition describes a more structured approach for extending
messages of the form $T=A_{0}^{r}A_{1}^{s}$.

######  Proposition 2.

Consider a bound $\delta$. If there exist integers $r<\delta$, $y>p-\delta$
such that $s:=(y^{-1}-r^{-1})(\alpha\beta)^{-1}<\delta$ (where inverses are
taken mod $p$) and $s(1+rs\alpha\beta)>p-\delta$, then for the message
$T=A_{0}^{r}A_{1}^{s}$ (of length $\leq 2\delta)$, there exist $m,n<\delta$
such that $H(T)A_{0}^{m}A_{1}^{n}$ is diagonal.

  * Proof.

We have $H(T)=\begin{pmatrix}1+rs\alpha\beta&r\alpha\\\
s\beta&1\end{pmatrix}$. As per Lemma 1, the condition for
$H(T)A_{0}^{m}A_{1}^{n}$ diagonal is that $m=-r/(1+rs(\alpha\beta))$ and
$n=-s(1+rs(\alpha\beta))$. Write $x=(1+rs(\alpha\beta))$. For $m,n<\delta$ we
require $rx^{-1}>p-\delta$, and $sx>p-\delta$. We set $y:=rx^{-1}$, from this
we derive $s=(y^{-1}-r^{-1})(\alpha\beta)^{-1}$. Clearly, if $y>p-\delta$ and
$s(1+rs\alpha\beta)>p-\delta$ then $m=p-y<\delta$ and $n=p-sx<\delta$, and by
assumption, $r,s<\delta$, so the messages $T=A_{0}^{r}A_{1}^{s}$ and
$A_{0}^{m}A_{1}^{n}$ each have length $\leq 2\delta$ and
$H(T)A_{0}^{m}A_{1}^{n}$ is a diagonal matrix. ∎

This clearly yields an algorithm with time complexity
$\mathcal{O}(\delta^{2})$ to test if for given values of $\alpha$, $\beta$, a
message of the form can be extended to have a diagonal hash. Indeed, one needs
only to test all integers $r<\delta$, $y>p-\delta$ for the two conditions
given in Proposition 2.

###  2.3 Extending messages for triangular hashes over ${\mathbb{F}_{p}}^{k}$

We now turn our attention to the more general case of producing upper or lower
triangular hashes. In this subsection, we will consider the general case of
$k\geq 1$ for the generalized Zémor hash functions over
${\mathbb{F}_{p}}^{k}$, and study the feasibility of efficiently producing
messages hashing to upper triangular messages.

Transforming the hash values of a message into an upper or lower triangular
matrix leads to producing collisions due to the following observation, which
was explained in Propositon 3 of [14]. Suppose that one can produce $r$
distinct messages $z_{i}$ such that $H(z_{i})=\begin{pmatrix}a_{i}&b_{i}\\\
0&d_{i}\end{pmatrix}$ is upper triangular. Also let $e_{i}$ be exponents such
that $\prod\limits_{i=1}^{r}a_{i}^{e_{i}}=1$. In other words,
$(e_{1},\ldots,e_{r})$ is a solution to the representation problem in
$\mathbb{F}_{p^{k}}^{*}$, which in turn reduces to a discrete log problem,
since the multiplicative group of a finite field is cyclic. Then, for
$z=z_{1}\ldots z_{r}$ we have $H(z)=\begin{pmatrix}1&b\\\ 0&1\end{pmatrix}$
and thus $H(z||z)=\begin{pmatrix}1&0\\\ 0&1\end{pmatrix}$ which collides with
the hash value of the empty word.

We begin by proving some preliminary results below.

######  Lemma 2.

Suppose that the product $\alpha\cdot\beta\in\mathbb{F}_{p}$ and that
$C=\begin{pmatrix}a&b\\\ c&d\end{pmatrix}$ is an arbitrary product of finitely
many copies of $A_{0}$ and $A_{1}$. Then, $c/\beta\in\mathbb{F}_{p}$ and
$d\in\mathbb{F}_{p}$.

  * Proof.

Write $C=A_{0}^{m_{1}}A_{1}^{n_{1}}\ldots
A_{0}^{m_{r}}A_{1}^{n_{r}}:=\begin{pmatrix}a_{r}&b_{r}\\\
c_{r}&d_{r}\end{pmatrix}$. The proof proceeds by induction on $r$. For the
case $r=1$, we have $C=\begin{pmatrix}1+mn\alpha\beta&m\alpha\\\
n\beta&1\end{pmatrix}$. Clearly, $c_{1}/\beta=n_{1}\in\mathbb{F}_{p}$ and
$d=1\in\mathbb{F}_{p}$, so the result holds.

Now assume that the result holds for $r\geq 1$. Write $m:=m_{r+1}$ and
$n:=n_{r+1}$. We have

$C_{r+1}=\begin{pmatrix}a_{r}&b_{r}\\\
c_{r}&d_{r}\end{pmatrix}\cdot\begin{pmatrix}1+mn\alpha\beta&m\alpha\\\
n\beta&1\end{pmatrix}=\begin{pmatrix}a_{r}(1+mn\alpha\beta)+nb_{r}\beta&a_{r}m\alpha+b_{r}\\\
c_{r}(1+mn\alpha\beta)+nd_{r}\beta&c_{r}m\alpha+d_{r}\end{pmatrix}$

Now,

$\displaystyle c_{r+1}^{p}/\beta^{p}=$ $\displaystyle
1/\beta^{p}[c_{r}^{p}(1+mn\alpha\beta)^{p}+nd_{r}^{p}\beta^{p}]$
$\displaystyle=$ $\displaystyle
1/\beta^{p}[c_{r}^{p}(1+mn\alpha\beta)+nd_{r}^{p}\beta^{p}]$ $\displaystyle=$
$\displaystyle(c_{r}/\beta)^{p}(1+mn\alpha\beta)+nd_{r}^{p}.$

By the induction hypothesis we have $d_{r}^{p}=d_{r}\in\mathbb{F}_{p}$ and
$(c_{r}/\beta)^{p}=c_{r}/\beta\in\mathbb{F}_{p}$, and so
$c_{r+1}^{p}/\beta^{p}=(c_{r}/\beta)(1+mn\alpha\beta)+nd_{r}=c_{r+1}/\beta\in\mathbb{F}_{p}$.
Further,

$\displaystyle d_{r+1}^{p}=(c_{r}m\alpha+d_{r})^{p}=$ $\displaystyle
mc_{r}^{p}\alpha^{p}+d_{r}^{p}=mc_{r}^{p}\alpha^{p}+d_{r}=mc_{r}\cdot
c_{r}^{p-1}\alpha^{p}+d_{r}$ $\displaystyle=$ $\displaystyle
mc_{r}\cdot\beta^{p-1}\alpha^{p}+d_{r}$ $\displaystyle=$ $\displaystyle
mc_{r}\cdot(\alpha\beta)^{p-1}\alpha+d_{r}$ $\displaystyle=$ $\displaystyle
mc_{r}\alpha+d_{r}=d_{r+1}$

Hence, we have $c_{r+1}/\beta\in\mathbb{F}_{p}$ and
$d_{r+1}\in\mathbb{F}_{p}$. By induction, the statement holds for all $r\geq
1$ and hence the lemma holds. ∎

######  Lemma 3.

Let $k\geq 1$ and $\alpha\cdot\beta\in\mathbb{F}_{p}$. Let $z$ be any message
and $C:=H(z)$ be its corresponding hash value. Assume that $a:=C[0,0]\neq 0$.
Then, there exist integers $m,n\in\\{0,1,\ldots,p-1\\}$ such that $C\cdot
A_{0}^{m}\cdot A_{1}^{n}$ is upper triangular.

  * Proof.

Write $C=\begin{pmatrix}a&b\\\ c&d\end{pmatrix}$. For integers $m$ and $n$, we
have

$\displaystyle C\cdot A_{0}^{m}\cdot A_{1}^{n}=$
$\displaystyle\begin{pmatrix}a&b\\\
c&d\end{pmatrix}\begin{pmatrix}1+mn\alpha\beta&m\alpha\\\
n\beta&1\end{pmatrix}$
$\displaystyle=\begin{pmatrix}a(1+mn\alpha\beta)+nb\beta&ma\alpha+b\\\
c(1+mn\alpha\beta)+nd\beta&mc\alpha+d\end{pmatrix}$

Choose $m$ to be any integer such that $mc\alpha+d\neq 0$. Since
$\alpha\beta\in\mathbb{F}_{p}$, $c/\beta\in\mathbb{F}_{p}$ and
$d\in\mathbb{F}_{p}$, we also have
$c\alpha=\left(c/\beta\right)\cdot\alpha\cdot\beta\in\mathbb{F}_{p}$, and we
can define

$n:=-\dfrac{c}{\beta(mc\alpha+d)}\in\mathbb{F}_{p}$ (2)

This gives $C\cdot A_{0}^{m}\cdot
A_{1}^{n}=\begin{pmatrix}a(1+mn\alpha\beta)+nb\beta&ma\alpha+b\\\
0&mc\alpha+d\end{pmatrix}$. ∎

######  Corollary 1.

Let $k\geq 1$ and $\alpha\cdot\beta\in\mathbb{F}_{p}$. Let $\delta$ be a
bound. Let $C=\begin{pmatrix}a&b\\\ c&d\end{pmatrix}$ be the hash of an
arbitrary message and $m\in\\{0,1,\ldots,p-1\\}$ be an integer such that both
$m$ and $n=-c/(\beta(mc\alpha+d))\in\mathbb{F}_{p}$ are smaller than $\delta$.
Then $CA_{0}^{m}A_{1}^{n}$ has length at most $2\delta$ more than $C$ and is
upper triangular.

##### Experimental results

Again, we looked for such $m$ and $n$ by random computer search in the above
examples, using randomly generated messages of reasonable length and checking
for the condition above. Once again, for larger values of $p$, experiments
indicate a very low probability of finding such values. For $30-40$ digit
primes, brute force could no longer find any such examples.

Below, we explore a more structured approach for messages of the form
$T=A_{0}^{r}A_{1}^{s}$.

######  Lemma 4.

Let $k\geq 1$ and $\alpha\cdot\beta\in\mathbb{F}_{p}$. Consider a bound
$\delta$. If there exist integers $m,s<\delta$ such that
$s(ms\alpha\beta+1)^{-1}>p-\delta$, then for the message
$T=A_{0}^{r}A_{1}^{s}$ (of length $\leq 2\delta$, here $r$ can be chosen
freely), for $n=p-s(ms\alpha\beta+1)^{-1}<\delta$, $H(T)A_{0}^{m}A_{1}^{n}$ is
upper triangular.

  * Proof.

We have $H(T)=\begin{pmatrix}1+rs\alpha\beta&r\alpha\\\
s\beta&1\end{pmatrix}$. Let $m,s<\delta$ be integers such that
$s(ms\alpha\beta+1)^{-1}>p-\delta$. The condition for
$H(T)A_{0}^{m}A_{1}^{n}=\begin{pmatrix}1+rs\alpha\beta&r\alpha\\\
s\beta&1\end{pmatrix}\begin{pmatrix}1+mn\alpha\beta&m\alpha\\\
n\beta&1\end{pmatrix}=\begin{pmatrix}(1+rs\alpha\beta)(1+mn\alpha\beta)+rn\alpha\beta&r\alpha\\\
s\beta(1+mn\alpha\beta)+n\beta&1+ms\alpha\beta\end{pmatrix}$ being upper
triangular is that $n=-s(1+ms(\alpha\beta))^{-1}$. The result is now clear. ∎

This clearly yields an algorithm with time complexity
$\mathcal{O}(\delta^{2})$ to test if for given values of $\alpha$, $\beta$, a
message of the form $T=A_{0}^{r}A_{1}^{s}$ can be extended to one with an
upper triangular hash, for a fixed bound $\delta$. Indeed, one needs only to
test all integers $m,s<\delta$ for the two conditions given above.

Clearly, for $C\cdot A_{0}^{m}\cdot A_{1}^{n}$ to be upper triangular, $n$
needs to assume the value in equation (2). Below, we derive the general
condition (without the assumption $\alpha\cdot\beta\in\mathbb{F}_{p})$ on $m$
so that both the $m$ and $n$ lie in $\mathbb{F}_{p}$.

######  Proposition 3.

If $\alpha\cdot\beta\not\in\mathbb{F}_{p}$, then $C\cdot A_{0}^{m}\cdot
A_{1}^{n}$ is upper triangular for $m,n\in\mathbb{F}_{p}$ if and only if for

$\gamma=\left(\dfrac{d((d\beta)^{p-1}-c^{p-1})}{\alpha
c^{p}(1-(\alpha\beta)^{p-1})}\right),$ (3)

we have $\gamma^{p}=\gamma$, and $m=\gamma;\ n=\dfrac{-c}{\beta(mc\alpha+d)}$.

  * Proof.

From the proof of Lemma 3, it is clear that for $CA_{0}^{m}A_{1}^{n}$ to be
upper triangular, Equation (2) must hold, along with $m^{p}=m$ and $n^{p}=n$.
We have,

$\displaystyle-n=c/(\beta(m\alpha c+d))\in\mathbb{F}_{p}$
$\displaystyle\implies$ $\displaystyle
c^{p}/(\beta^{p}(m\alpha^{p}c^{p}+d^{p}))=c/(\beta(m\alpha c+d))$
$\displaystyle\implies$ $\displaystyle(c/\beta)^{p-1}\cdot(m\alpha
c+d)=m\alpha^{p}+d^{p}$ $\displaystyle\implies$ $\displaystyle
c^{p-1}\cdot(m\alpha c+d)=\beta^{p-1}\cdot(m\alpha^{p}c^{p}+d^{p})$
$\displaystyle\implies$ $\displaystyle m\alpha
c^{p}\cdot(1-(\alpha\beta)^{p-1})=\beta^{p-1}d^{p}-c^{p-1}d$
$\displaystyle\implies$ $\displaystyle
m=\dfrac{d((d\beta)^{p-1}-c^{p-1})}{\alpha c^{p}(1-(\alpha\beta)^{p-1})}$

Thus, for $m=\gamma$, one necessarily has
$n:=\dfrac{-c}{\beta(mc\alpha+d)}\in\mathbb{F}_{p}$. So, in order to obtain an
upper triangular matrix, the only condition that needs to be satisfied is
$\gamma^{p}=\gamma$. ∎

######  Lemma 5 (Case $k=2$).

Let $k=2$ and $\alpha\cdot\beta\not\in\mathbb{F}_{p}$. As before, let
$C=\begin{pmatrix}a&b\\\ c&d\end{pmatrix}\in SL_{2}(\mathbb{F}_{p^{2}})$ be an
arbitrary product of finitely many copies of $A_{0}$ and $A_{1}$. Then with
$\gamma$ defined as in (3), $\gamma^{p}=\gamma$ always holds.

  * Proof.

In this case, for any nonzero field element $y$ we have $y^{p^{2}-p}=y^{1-p}$,
so

$\displaystyle\gamma^{p}=\left(\dfrac{d((d\beta)^{p-1}-c^{p-1})}{\alpha
c^{p}(1-(\alpha\beta)^{p-1})}\right)^{p}$
$\displaystyle=(d^{p}c/\alpha^{p})\left(\dfrac{((d\beta)^{1-p}-c^{1-p})}{(1-(\alpha\beta)^{1-p})}\right)$
$\displaystyle=(d^{p}/c\alpha)1/(d\beta
c)^{p-1}(\alpha\beta)^{p-1}\left(\dfrac{((d\beta)^{p-1}-c^{p-1})}{(1-(\alpha\beta)^{p-1})}\right)$
$\displaystyle=d/(\alpha
c^{p})\left(\dfrac{((d\beta)^{p-1}-c^{p-1})}{(1-(\alpha\beta)^{p-1})}\right)=\gamma.$

∎

Thus, in $SL_{2}(\mathbb{F}_{p^{2}})$ one can always find collisions by right-
multiplying an arbitrary matrix by a product $A_{0}^{m}A_{1}^{n}$. In other
words, a message in $SL_{2}(\mathbb{F}_{p^{2}})$ is always extendable to have
a triangular hash.

######  Example 2.

Consider $SL_{2}(\mathbb{F}_{p^{2}})$ for $p=239$, with generator denoted by
$z$. Consider the following message text

$\displaystyle T=$ $\displaystyle
0^{17}1^{25}0^{11}1^{8}0^{38}1^{33}0^{29}1^{27}0^{40}1^{24}0^{4}1^{2}0^{38}1^{16}0^{16}1^{39}0^{50}1^{42}0^{36}1^{22}0^{2}1^{41}0^{27}1^{29}0^{11}$
$\displaystyle
1^{15}0^{29}1^{47}0^{29}1^{33}0^{47}1^{3}0^{35}1^{32}0^{49}1^{27}0^{24}1^{0}0^{21}1^{49}0^{33}1^{4}0^{50}1^{44}0^{42}1^{43}0^{4}1^{29}0^{14}1^{39}$
$\displaystyle
0^{14}1^{15}0^{41}1^{0}0^{41}1^{1}0^{20}1^{34}0^{4}1^{6}0^{43}1^{5}0^{11}1^{7}0^{37}1^{29}0^{40}1^{20}0^{1}1^{13}0^{2}1^{14}0^{31}1^{41}0^{19}1^{24}$
$\displaystyle
0^{50}1^{50}0^{25}1^{23}0^{30}1^{39}0^{6}1^{46}0^{39}1^{27}0^{8}1^{9}0^{25}1^{38}0^{0}1^{46}0^{15}1^{33}0^{47}1^{40}0^{40}1^{26}0^{48}1^{45}$

For a random choice of $\alpha$ and $\beta$, we may obtain hash
$H(T)=\begin{pmatrix}134z+110&131z+185\\\ 74z+17&58z+41\end{pmatrix}$.
Calculating $m$ and $n$ as per Lemma 3, we see that
$H(T)0^{1}1^{10}=\begin{pmatrix}106z+192&25z+30\\\ 0&218z+62\end{pmatrix}$.

A natural question arises here: can we generalize this method to make

$C\cdot A_{0}^{m_{1}}A_{1}^{n_{1}}\ldots A_{0}^{m_{r}}A_{1}^{n_{r}}$

upper/lower triangular and thereby extend the result to all
$SL_{2}({\mathbb{F}_{p}}^{k})$? Since the major constraint is the condition
$\gamma^{p}=\gamma$ (and the size of $\gamma$ does not seem easy to control),
we first explore how the value of $\gamma$ changes when $C$ is multiplied on
the right by a random product $A_{0}^{m}A_{1}^{n}$.

######  Theorem 1.

Let $C=\begin{pmatrix}a&b\\\ c&d\end{pmatrix}$ and $C^{\prime}:=C\cdot
A_{0}^{m}\cdot A_{1}^{n}=\begin{pmatrix}a^{\prime}&b^{\prime}\\\
c^{\prime}&d^{\prime}\end{pmatrix}$. Let $\gamma$ and $\gamma^{\prime}$ be
defined as in equation (3). Then, we have

$\gamma^{\prime}=(c/c^{\prime})^{p+1}(\gamma-m)$

  * Proof.

Let

$X:=\dfrac{1}{\alpha(1-(\alpha\beta)^{p-1})},\
\gamma:=\dfrac{Xd}{c^{p}}[(d\beta)^{p-1}-c^{p-1}]$

We have,

$\displaystyle\gamma^{\prime}=$ $\displaystyle
X\dfrac{d^{\prime}((d^{\prime}\beta)^{p-1}-(n\beta
d^{\prime}+c)^{p-1}))}{(c^{\prime})^{p}}=Xd^{\prime}\dfrac{(d^{\prime}\beta)^{p-1}-\frac{n\beta(d^{\prime})^{p}+c^{p}}{n\beta
d^{\prime}+c}}{(c^{\prime})^{p}}$ $\displaystyle=$ $\displaystyle
Xd^{\prime}\dfrac{(d^{\prime}\beta)^{p-1}(n\beta
d+c))-n\beta(d^{\prime})^{p}-c^{p}}{(c^{\prime})^{p+1}}$ $\displaystyle=$
$\displaystyle
Xd^{\prime}c\dfrac{(d^{\prime}\beta)^{p-1}-c^{p-1}}{(c^{\prime})^{p+1}}=Xd^{\prime}c\dfrac{(d^{\prime}\beta)^{p-1}-c^{p-1}}{(c^{\prime})^{p+1}}$
$\displaystyle=$ $\displaystyle\dfrac{Xcd^{\prime}}{c^{\prime
p+1}d^{\prime}\beta}[(mc^{p}\alpha^{p})\beta^{p}-c^{p-a1}(cm\alpha+d)\beta]$
$\displaystyle=$
$\displaystyle\dfrac{Xc}{{c^{\prime}}^{p+1}\beta}[mc^{p}\alpha\beta((\alpha\beta)^{p-1}-1)+d\beta((d\beta)^{p-1}-c^{p-1})]$

Plugging the values of $X$ and $\gamma$ from above into the equation, we get

$\displaystyle\gamma^{\prime}=$
$\displaystyle\dfrac{Xc}{(c^{\prime})^{p+1}\beta}mc^{p}\alpha\beta((\alpha\beta)^{p-1}-1)+\dfrac{Xcd}{(c^{\prime})^{p+1}}\left(\dfrac{c^{p}\gamma}{Xd}\right)$
$\displaystyle=$
$\displaystyle\left(\dfrac{c}{c^{\prime}}\right)^{p+1}[-m+\gamma]$

∎

For an extension where multiplication by a product $A_{0}^{m}A_{1}^{n}$ is
allowed twice, we have the following result.

######  Lemma 6.

For $C:=\begin{pmatrix}a&b\\\ c&d\end{pmatrix}$, there exits integers
$m_{1},m_{2},n_{1},n_{2}$ such that $CA^{m_{1}}B^{n_{1}}A^{m_{2}}B^{n_{2}}$ is
upper triangular if and only if the equation

$q_{3}x^{2}y+q_{2}xy+q_{1}y+q_{0}=0$ (4)

has a solution $(x,y)\in\mathbb{F}_{p}\times\mathbb{F}_{p}$, where
$q_{0},q_{1},q_{2},q_{3}$ are given by

$\displaystyle\begin{split}q_{3}&=c^{p^{2}}\alpha\beta((\alpha\beta)^{p^{2}-1}-1),\\\
q_{2}&=c^{p^{2}}\gamma\alpha\beta(\gamma^{p-1}-(\alpha\beta)^{p^{2}-1})+d\beta((d\beta)^{p^{2}-1}-1),\\\
q_{1}&=d\beta\gamma(c^{p^{2}}\gamma^{p-1}-(d\beta)^{p^{2}-1}),\\\
q_{0}&=c^{p^{2}}\gamma(\gamma^{p-1}-1).\end{split}$ (5)

  * Proof.

Let $C^{\prime}:=C\cdot A^{m}\cdot
B^{n}=\begin{pmatrix}a^{\prime}&b^{\prime}\\\
c^{\prime}&d^{\prime}\end{pmatrix}$ and let $\gamma^{\prime}$ be defined as in
equation (3). By Theorem 1 we have
$\gamma^{\prime}:=(c/c^{\prime})^{p+1}(\gamma-m)\in\mathbb{F}_{p}$. We treat
$x:=m$ and $y:=n$ as variables in $\mathbb{F}_{p}$. For $C^{\prime}$ to be
upper triangular for some values of $x$ and $y$, we require

$\displaystyle(\gamma^{\prime})^{p}=\gamma^{\prime}$ $\displaystyle\implies$
$\displaystyle
c^{p^{2}+p}(c^{\prime})^{p+1}(\gamma^{p}-x)=c^{p+1}(c^{\prime})^{p^{2}+p}(\gamma-x)$
$\displaystyle\implies$ $\displaystyle
c^{p^{2}}c^{\prime}(\gamma^{p}-x)=c(c^{\prime})^{p^{2}}(\gamma-x)$
$\displaystyle\implies$ $\displaystyle c^{p^{2}}(\gamma^{p}-x)(c+(c\alpha
x+d)y\beta)=c(c^{p^{2}})+(xc^{p^{2}}\alpha^{p^{2}}+d^{p^{2}})y\beta^{p^{2}})(\gamma-x)$
$\displaystyle\implies$ $\displaystyle
c^{p^{2}-1}[\gamma^{p}c+\gamma^{p}c\alpha\beta xy+\gamma^{p}d\beta
y-cx-c\alpha\beta x^{2y-d\beta
xy}=c^{p^{2}}\gamma+(c\alpha\beta)^{p^{2}}\gamma xy+$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad(d\beta)^{p^{2}}\gamma
y-c^{p^{2}}x-(c\alpha\beta)^{p^{2}}x^{2}y-(d\beta)^{p^{2}}xy$
$\displaystyle\implies$
$\displaystyle((c\alpha\beta)^{p^{2}}-c^{p^{2}}\alpha\beta)x^{2}y+(-(c\alpha\beta)^{p^{2}}\gamma+\gamma^{p}c^{p^{2}}\alpha\beta+(d\beta)^{p^{2}}-d\beta)xy+$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad(c^{p^{2}}\gamma^{p}(d\beta)-\gamma(d\beta)^{p^{2}})y+(\gamma^{p}c^{p^{2}}-\gamma
c^{p^{2}})=0$ $\displaystyle\implies$ $\displaystyle
q_{3}x^{2}y+q_{2}xy+q_{1}y+q_{0}=0$

where $q_{0},q_{1},q_{2},q_{3}$ are given as in Equation (5). The proof is now
complete. ∎

Note that for $q_{0},q_{1},q_{2},q_{3}$ as in Equation (5), we can rephrase
the condition in Lemma 6 as follows. $C:=\begin{pmatrix}a&b\\\
c&d\end{pmatrix}$ is upper triangularizable by right multiplication if and
only if the system of equations

$\begin{split}&q_{3}x^{2}y+q_{2}xy+q_{1}y+q_{0}=0\\\ &x^{p}=x\\\
&y^{p}=y\end{split}$ (6)

has a simultaneous solution $(x,y)$ in
${\mathbb{F}_{p}}^{k}\times{\mathbb{F}_{p}}^{k}$. One may then use Gröbner
bases to solve this system of equations. A corresponding conditions for $C$ to
be lower triangularizable by left/right multiplication and to be upper
triangularizable by left multiplication can be derived similarly.

######  Example 3.

For simplicity, consider the field $\mathbb{F}_{2^{5}}$ with generator $z_{5}$
and $\alpha=z_{5}^{3}+1$, $\beta=z_{5}^{3}+z_{5}^{2}+1$. Consider the hash
matrix

$C=\begin{pmatrix}z_{5}^{4}+z_{5}^{3}+z_{5}^{2}+z_{5}&z_{5}^{4}+z_{5}^{3}+z_{5}^{2}+z_{5}\\\
z_{5}^{3}&z_{5}^{4}+z_{5}^{3}+z_{5}^{2}\end{pmatrix}.$

Here, we have $\gamma=z_{5}^{4}+z_{5}+1$ and the polynomial in Equation (4) is
$(z_{5}^{2}+z_{5})x^{2}y+(z_{5}^{3}+z_{5}^{2}+1)xy+(z_{5}^{3})y+(z_{5}^{4}+z_{5}^{2}+z_{5})$.
The
$\langle(z_{5}^{2}+z_{5})x^{2}y+(z_{5}^{3}+z_{5}^{2}+1)xy+z_{5}^{3}y+(z_{5}^{4}+z_{5}^{2}+z_{5}),x^{p}-x,y^{p}-y\rangle$
is trivial, so its Gröbner basis is $\\{1\\}$.

We attempted the above experiment with various different values of $p$ and $k$
and random matrices $C$ which are products of $A$ and $B$. In each case,
without exception, we found no solution (i.e. the resulting Gröbner base of
the ideal $\langle q_{3}x^{2}y+q_{2}xy+q_{1}y+q_{0},x^{p}-x,y^{p}-y\rangle$
was $\langle 1\rangle$). Therefore, this method of extension to produce a
triangular matrix is not practically feasible.

##  3 Generalized Tillich-Zémor Hash Functions

In this section, we consider the generalized Tillich-Zémor hash function
$\phi$ with the generators $A_{0}=\begin{pmatrix}\alpha&1\\\ 1&0\end{pmatrix}$
and $A_{1}=\begin{pmatrix}\beta&1\\\ 1&0\end{pmatrix}$ where
$\alpha,\beta\in{\mathbb{F}_{p}}^{k}$.

More generally, treating $x$ as a variable, we consider the matrix
$Y=\begin{pmatrix}x&1\\\ 1&0\end{pmatrix}$ and first compute its powers.
Clearly, we have

$\displaystyle Y^{2}=\begin{pmatrix}x^{2}+1&x\\\ x&1\end{pmatrix},\
Y^{3}=\begin{pmatrix}x^{3}+x^{2}+x+1&x^{2}+1\\\ x^{2}+1&x\end{pmatrix}$

More generally, we can write

$\displaystyle Y^{n}=\begin{pmatrix}f_{n}(x)&f_{n-1}(x)\\\
f_{n-1}(x)&f_{n-2}(x)\end{pmatrix},\ n\geq 2$ (7)

where $f_{0}(x)=0$, $f_{1}(x)=1$, and

$f_{n}(x)=xf_{n-1}(x)+f_{n-2}(x)$ (8)

It is clear that the recurrence relation (8) fully describes the powers of the
matrix $Y$. The above formulation and recurrence relation were also derived in
[1].

###  3.1 Computing $f_{n}(x)$ for characteristic $p\neq 2$

In [1], an expression for $f_{n}(x)$ was derived in the case $p=2$. The
authors also calculate probabilities that the orders of A and B lie within
certain bounds. In this section, we address the case $p\neq 2$ and derive a
closed formula for $f_{n}(x)$.

We may solve the recurrence Equation (8) by finding roots of the auxiliary
polynomial $t^{2}-xt-1=0$. The quadratic formula then gives us

$t=\dfrac{x\pm\sqrt{x^{2}+4}}{2}.$

Setting $r=\dfrac{x+\sqrt{x^{2}+4}}{2}$ and $s=\dfrac{x-\sqrt{x^{2}+4}}{2}$, a
general solution to (8) has to be of the form $f_{n}(x)=ur^{n}+vs^{n}$. Note
that we also have the initial conditions $f_{1}(x)=1$ and $f_{0}(x)=1$ (or
equivalently $f_{2}(x)=x^{2}+1$). Plugging these in, we may solve for $u$ and
$v$ to get

$\displaystyle u=\dfrac{x+\sqrt{x^{2}+4}}{2\sqrt{x^{2}+4}},\
v=1-u=\dfrac{-x+\sqrt{x^{2}+4}}{2\sqrt{x^{2}+4}}.$

Write $w=\sqrt{x^{2}+4}$. Note that for any $n\geq 1$, we have

$\displaystyle\begin{split}f_{n}(x)&=ur^{n}+vs^{n}=\left(\dfrac{x+w}{2w}\right)\left(\dfrac{(x+w)^{n}}{2}\right)+\left(\dfrac{-x+w}{2w}\right)\left(\dfrac{(x-w)^{n}}{2}\right)\\\
&=\left(\dfrac{(x+w)^{n+1}}{2^{n+1}w}\right)-\left(\dfrac{(x-w)^{n+1}}{2^{n+1}w}\right)\\\
&=\dfrac{1}{2^{n+1}w}\left[\sum\limits_{i=0}^{n+1}\binom{n+1}{i}x^{i}w^{n+1-i}-\sum\limits_{i=0}^{n+1}\binom{n+1}{i}x^{i}w^{n+1-i}\right]\\\
&=\dfrac{1}{2^{n+1}}\left[\sum\limits_{0\leq i\leq n+1,\ n-i\text{ is
even}}\binom{n+1}{i}x^{i}w^{n-i}\right]\\\
&=\dfrac{1}{2^{n+1}}\left[\sum\limits_{0\leq i\leq n+1,\ n-i\text{ is
even}}\binom{n+1}{i}\sum\limits_{j=0}^{(n-i)/2}\binom{(n-i)/2}{j}x^{i+2j}4^{(n-i)/2-j}\right]\\\
&=\dfrac{1}{2^{n+1}}\left[\sum\limits_{0\leq i\leq n,\ n-i\text{ is
even}}\sum\limits_{j=0}^{(n-i)/2}\binom{n+1}{i}\binom{(n-i)/2}{j}2^{n-2j}x^{i+2j}\right]\\\
\end{split}$ (9)

Thus, $f_{n}(x)$ is always a polynomial in $\mathbb{F}_{p}[x]$, and we have a
closed formula for calculating it. Powers of $A_{0}$ and $A_{1}$ may therefore
be computed in constant time.

Note that ${\mathbb{F}_{p}}^{k}$ is typically viewed through the isomorphism
${\mathbb{F}_{p}}^{k}\cong\mathbb{F}_{p}[x]/\langle p(x)\rangle$ where $p(x)$
is an irreducible polynomial of degree $k$ over $\mathbb{F}_{p}$. Thus, an
element $\gamma\in{\mathbb{F}_{p}}^{k}$ is a polynomial of degree smaller than
$k$, say $\gamma=g_{\gamma}(x)$. $f_{n}(\gamma)$ can then be calculated as a
polynomial modulo $p(x)$ by simply composing $f_{n}$ and $g$, i.e.
$f_{n}(\gamma)=f_{n}(g_{\gamma}(x))\pmod{p(x)}$.

We also have the following straightforward observation. A similar statement is
found in [1].

######  Lemma 7.

Let $q(x)$ be any irreducible polynomial of degree $d$. Then, the sequence
$\\{f_{n}(x)\pmod{p(x)}\\}$ is periodic, and its order divides
$(p^{2k}-p^{k})(p^{2k}-1)/(p^{k}-1)$.

###### Proof.

Clearly, for $Y=\begin{pmatrix}x&1\\\ 1&0\\\ \end{pmatrix}$, Equation (7)
gives us a formula for $Y^{n}$ in terms of $f_{n}(x)$, $f_{n-1}(x)$ and
$f_{n-2}(x)$. Since $Y$ must have a finite multiplicative order $n_{y}$ in the
finite group $SL_{2}(\mathbb{F}_{p}[x]/\langle q(x)\rangle)$, we must have
$f_{n_{y}-1}(x)=0$, $f_{n}(x)=f_{n-2}(x)=1$. From this point onwards, the
sequence repeats its terms, and therefore its period is given by $n_{y}$,
which must divide the order of the matrix group. ∎

######  Lemma 8.

Suppose that the adversary can compute integers $m$ and $n$ such that
$f_{n-1}(g_{\alpha}(x))=f_{m-1}(g_{\beta}(x))\pmod{p(x)}$ and
$f_{n-2}(g_{\alpha}(x))=f_{m-2}(g_{\beta}(x))\pmod{p(x)}$. Then, the adversary
can compute a collision of size $\mathcal{O}(\max(m,n))$ for the Generalized
Tillich-Zëmor hash function $\phi$.

  * Proof.

In this case, it is clear from (8) that
$f_{n}(g_{\alpha}(x))=f_{m}(g_{\beta}(x))\pmod{p(x)}$, and so
$A_{0}^{n}=A_{1}^{m}$, i.e. $\phi(0^{n})=\phi(1^{m})$. ∎

Note that the above result includes the cases $m=0$ and $n=0$, i.e. finding
collisions with the identity matrix. However, by looking at the expression (9)
for $f_{n}(x)$, one sees that even for the simplest equation
$f_{n}(x)=0\pmod{p(x)}$, finding a solution for the value of $n$ is not
straightforward, since in (9) $n$ occurs both as a polynomial term (in the
binomial coefficients) and in the exponent of $2$. This problem seems to be a
complex amalgamation of a generalized discrete logarithm with a polynomial
rather than a single power. One may extend the above result to products with
more terms.

######  Lemma 9.

Let $\mathbb{F}_{p}[x]/\langle q(x)\rangle$ be a finite field. If an adversary
can find integers $m$ and $n$ such that the following relations hold

$\displaystyle f_{m}(f_{n}(x))+f_{m-1}(f_{n-1}(x))=1\pmod{q(x)}$
$\displaystyle f_{m}(f_{n-1}(x))+f_{m-1}(f_{n-2}(x))=0\pmod{q(x)}$
$\displaystyle f_{m-1}(f_{n}(x))+f_{m-2}(f_{n-1}(x))=0\pmod{q(x)}$
$\displaystyle f_{m-1}(f_{n-1}(x))+f_{m-2}(f_{n-2}(x))=1\pmod{q(x)},$

then $H(0^{m}1^{n})=H()$ gives a collision with the hash $H()$ of the empty
word.

Note that in both the above results, the problem potentially becomes even more
difficult if one constrains the values of $m$ and $n$ to yield practical-sized
collisions.

###  3.2 Malicious paramaters

As seen in the above discussion, the security of the generalized Tillich-Zëmor
hash functions relies on the choice of the irreducible polynomial through
which the finite field is constructed. Thus, a malicious construction of this
polynomial can lead to the designer of the hash function being able to easily
compute collisions.

In [5], the authors produce malicious polynomials in finite fields
$\mathbb{F}_{2^{m}}$, reducing the problem of collision-finding in the matrix
group to the search for an irreducible polynomial of degree $m$, such that
$m+1$ is a proper divisor of $q-1$ or $q+1$, where $q=2^{m}$. Over the field
so constructed, the matrix $A$ has a small order 263, and leads also to a non-
trivial collision, which the authors exemplify for
$SL_{2}(\mathbb{F}_{2^{131}})$. This attack fails if $q-1$ and $q+1$ are both
primes or if the factorization of their $\gcd$ involves large primes, since
the collisions yielded are then too long.

In [1], the authors also deal exclusively with the characteristic 2 case, and
propose an algorithm to decide whether the given irreducible polynomial leads
to a vulnerable system under the attack of [5], and propose a solution to fix
the vulnerability. In the following result, we describe a malicious design for
the choice of the polynomial defining the finite field, for odd characteristic
$p$.

######  Theorem 2.

If one can find $N$ such that $\gcd(f_{N}(x)-1,f_{N-1}(x))$ has an irreducible
divisor $q(x)$ of degree $d$, one can find a collision of size
$\mathcal{O}(N)$ for the hash function $\phi(x)$ over the finite field
${\mathbb{F}_{p}[x]}/{\langle q(x)\rangle}$. On the other hand, given a fixed
finite field ${\mathbb{F}_{p}[x]}/{\langle q(x)\rangle}$, if one can find an
integer $N$ such that $q(x)$ divides $\gcd(f_{N}(x)-1,f_{N-1}(x))$ then one
can find collisions of size $\mathcal{O}(N)$ for $\phi$.

  * Proof.

If one can find $N$ such that $\gcd(f_{N}(x),f_{{N}-1}(x))$ has an irreducible
divisor $q(x)$ of degree $d$, then $f_{N}(x)=1\pmod{q}(x)$,
$f_{N+1}(x)=0\pmod{q}(x)$, then the sequence
$\\{f_{n}(x)\pmod{\mathbb{F}_{p}[x]}/{\langle q(x)\rangle}\\}$ has a period
dividing $n_{y}$, and the multiplicative order of $Y$ in
$SL_{2}({\mathbb{F}_{p}[x]}/{\langle q(x)\rangle})$ divides $N$. Thus, one has
a collision of $H(0^{N})$ with the hash of the empty word. ∎

######  Example 4.

$q(x)=x^{12}+2x^{10}+x^{6}+2x^{4}+2x^{3}+x^{2}+x+1$ is an irreducible
polynomial over $\mathbb{F}_{3}$ such that $\\{f_{n}(x)\pmod{q}(x)\\}$ has
period $531440=3^{12}-1$. Thus, in $SL_{2}(\mathbb{F}_{3^{12}})$, we always
have collisions $H(0^{531440})=H(1^{531440})=H()$.

## References

  * [1] Kanat S. Abdukhalikov and Chul Kim.  On the security of the hashing scheme based on ${SL}_{2}$.  In Fast Software Encryption Workshop, 1998.
  * [2] Iris Anshel, Derek Atkins, Dorian Goldfeld, and Paul E. Gunnells.  Kayawood, a key agreement protocol.  IACR Cryptol. ePrint Arch., 2017:1162, 2017.
  * [3] Iris Anshel, Derek Atkins, Dorian Goldfeld, and Paul E. Gunnells.  Walnutdsa™: a group theoretic digital signature algorithm.  International Journal of Computer Mathematics: Computer Systems Theory, 6(4):260–284, 2017.
  * [4] Iris Anshel, Derek Atkins, Dorian Goldfeld, and Paul E. Gunnells.  Ironwood meta key agreement and authentication protocol.  Advances in Mathematics of Communications, 15(3):397–413, 2021\.
  * [5] Chris Charnes and Josef Pieprzyk.  Attacking the sl2 hashing scheme.  In Josef Pieprzyk and Reihanah Safavi-Naini, editors, Advances in Cryptology — ASIACRYPT’94, pages 322–330, Berlin, Heidelberg, 1995. Springer Berlin Heidelberg.
  * [6] Markus Grassl, Ivana Ilić, Spyros Magliveras, and Rainer Steinwandt.  Cryptanalysis of the Tillich–Zémor Hash Function.  Journal of Cryptology, 24(1):148–156, January 2011.
  * [7] Gilles Zemore Jean-Pierre Tillich.  Hashing with ${SL}_{2}$.  Technical report, Ecole Nationale Superieure des Telecommunications, France.
  * [8] Jill P. Mesirov and Melvin M. Sweet.  Continued fraction expansions of rational expressions with irreducible denominators in characteristic 2.  Journal of Number Theory, 27:144–148, 1987.
  * [9] Wouter Penard and Tim van Werkhoven.  On the secure hash algorithm family, 2008.
  * [10] Christophe Petit.  Towards factoring in ${SL}_{2}(\mathbb{F}_{p})$.  Designs, Codes and Cryptography, 71(3):409–431, June 2014.
  * [11] Christophe Petit, Kristin Lauter, and Jean-Jacques Quisquater.  Full cryptanalysis of lps and morgenstern hash functions.  In Rafail Ostrovsky, Roberto De Prisco, and Ivan Visconti, editors, Security and Cryptography for Networks, pages 263–277, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.
  * [12] Christophe Petit and Jean-Jacques Quisquater.  Preimages for the tillich-zémor hash function.  In Alex Biryukov, Guang Gong, and Douglas R. Stinson, editors, Selected Areas in Cryptography, pages 282–301, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.
  * [13] Christophe Petit and Jean-Jacques Quisquater.  Rubik’s for cryptographers.  IACR Cryptology ePrint Archive, 2011:638, 01 2011.
  * [14] Christophe Petit, Jean-Jacques Quisquater, Jean-Pierre Tillich, and Gilles Zémor.  Hard and easy components of collision search in the zémor-tillich hash function: New attacks and reduced variants with equivalent security.  In Marc Fischlin, editor, Topics in Cryptology – CT-RSA 2009, pages 182–194, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg.
  * [15] Christophe Petit, Nicolas Veyrat-Charvillon, and Jean-Jacques Quisquater.  Efficiency and pseudo-randomness of a variant of zémor-tillich hash function.  In 2008 15th IEEE International Conference on Electronics, Circuits and Systems, pages 906–909, 2008.
  * [16] Jean-Pierre Tillich and Gilles Zémor.  Group-theoretic hash functions.  In Algebraic Coding, 1993.
  * [17] Jean-Pierre Tillich and Gilles Zémor.  Collisions for the lps expander graph hash function.  In Nigel Smart, editor, Advances in Cryptology – EUROCRYPT 2008, pages 254–269, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.
  * [18] Gilles Zémor.  Hash functions and graphs with large girths.  In Workshop on the Theory and Application of of Cryptographic Techniques, pages 508–511. Springer, 1991.
  * [19] Gilles Zémor.  Hash functions and graphs with large girths.  In International Conference on the Theory and Application of Cryptographic Techniques, 1991.