Charles et al (J Cryptol 22(1):93–113, 2009) explained how one can construct hash functions using expander graphs in which it is hard to find paths between specified vertices. The set of solutions to the classical Markoff equation \(X^2+Y^2+Z^2=3XYZ\) in a finite field \(\mathbb {F}_q\) has a natural structure as a tri-partite graph using three non-commuting polynomial automorphisms to connect the points. These graphs conjecturally form an expander family, and Fuchs et al (Math Cryptol 1(1):103–121, 2022) suggested using this family of Markoff graphs in the CGL construction. In this note we show that in both a theoretical and a practical sense, assuming two randomness hypotheses, one can compute paths in a Markoff graph over \(\mathbb {F}_q\) by factoring \(q-1\) and solving three discrete logarithm problems in \(\mathbb {F}_q^*\) . In particular, the path problem can be solved in subexponential time.
