# Is biber Turing complete?

I am wondering whether biber inherits Turing completeness from TeX.

To show Turing completeness (without the requirement that the memory is infinite), we would need to emulate a Turing-complete device (like the TM as defined by Alan Turing, Rule 110, HTML5+CSS3 or alike).

## My initial tests

Let's start with the basics. We compile using pdflatex mwe && biber mwe && pdflatex mwe && pdflatex mwe.

Question: Can we count?

% cat mwe.tex && echo "-----" && cat mwe.bib
\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[backend=biber]{biblatex}
\bibliography{mwe}
\begin{document}
As discussed in Wang's paper~\cite{wang2004}.
\printbibliography
\end{document}
-----
@article{wang2004,
title={\newcounter{h}\setcounter{h}{4}Collisions for Hash Functions MD\theh, MD\stepcounter{h}\theh, HAVAL-128 and RIPEMD.},
author={Wang, Xiaoyun and Feng, Dengguo and Lai, Xuejia and Yu, Hongbo},
journal={IACR Cryptology ePrint Archive},
volume={2004},
pages={199},
year={2004}
}


Question: What about control sequences / definitions?

% cat mwe.tex && echo "-----" && cat mwe.bib
\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[backend=biber]{biblatex}
\bibliography{mwe}
\begin{document}
As discussed in Wang's paper~\cite{wang2004}.
\printbibliography
\end{document}
-----
@article{wang2004,
title={\def\prefix{MD}Collisions for Hash Functions \prefix4, \prefix5, HAVAL-128 and RIPEMD.},
author={Wang, Xiaoyun and Feng, Dengguo and Lai, Xuejia and Yu, Hongbo},
journal={IACR Cryptology ePrint Archive},
volume={2004},
pages={199},
year={2004}
}


Question: What about functions; hence control sequences with arguments? This should provide us recursion for our computational device.

% cat mwe.tex && echo "-----" && cat mwe.bib
\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[backend=biber]{biblatex}
\bibliography{mwe}
\begin{document}
As discussed in Wang's paper~\cite{wang2004}.
\printbibliography
\end{document}
-----
@article{wang2004,
title={\def\prefixed#1{MD#1}Collisions for Hash Functions \prefixed{4}, \prefixed{5}, HAVAL-128 and RIPEMD.},
author={Wang, Xiaoyun and Feng, Dengguo and Lai, Xuejia and Yu, Hongbo},
journal={IACR Cryptology ePrint Archive},
volume={2004},
pages={199},
year={2004}
}


Answer: Oh darn, this one fails.

! Illegal parameter number in definition of \NewValue.
1
l.39 ...fixed{4}, \prefixed{5}, HAVAL-128 and RIPEMD.}

? X
No pages of output.
Transcript written on mwe.log.


Apparently, the hash symbol is invalid in biber. \catcode-ing the hash symbol does not seem to be possible either.

1. Is it possible to define recursive algorithms in biber?
2. If not, are there any iterative looping commands available in biber?
3. If not, can we achieve a Turing-complete device using any TeX-based tool for citations? (any combination of BibLaTeX/bibtex/biber/multibib/bibtopic)

Update: My point with Turing completeness is that e.g. infinite loops are possible, which I consider as "exploits" for certain server applications interpreting bib-files. I removed xindy from the list of tools as it is only about indexing.

• Is biblatex a programming language, to begin with? – egreg Apr 20 '16 at 23:03
• Literature like cseweb.ucsd.edu/~hovav/dist/tex-login.pdf indicates that BibTeX can be used for exploits. However, I never saw a pure-BibTeX exploit. I started with BibLaTeX. Feel free to consider BibTeX (or any other TeX-based citation tool). – meisterluk Apr 20 '16 at 23:08
• Your answer for (1) is defining stuff in LaTeX - not Biblatex. Your answer for (2) is defining stuff in TeX - not Biblatex. Of course, if you allow yourself to count TeX as 'part of' Biblatex (for some bizarre reason) then Biblatex must be Turing complete because TeX is. But this doesn't make any sense: Biblatex is not a standalone thing at all. It is defined on top of LaTeX which is a bunch of macros defined on top of TeX. BibTeX is different because BibTeX is a distinct programme with its own language. Surely Biber is the relevant analogue - not Biblatex. – cfr Apr 20 '16 at 23:14
• xindy is used for indexing, normally, and not citations. I don't understand the concept of a 'Turing complete device' consisting of a LaTeX package and anything since the package is just a text file. If you load it, the compiler does things with the instructions, but the package can't execute anything on its own. If you are asking whether you could put malicious code into a .bib file such that the code would be executed on compilation if the entry was cited and the usual compilation cycle followed, then I'd assume yes. I don't see any other assumption would be safe regardless of Turing. – cfr Apr 21 '16 at 2:12
• TeX is Turing complete so any text read by TeX can do anything if read 'as is'. One can arrange to read back only strings (using \readline in e-TeX or with a bit more work in classical TeX), which are then just 'text' but of course loose usefulness for typesetting (what if I want to read back a legitimate control sequence). However, this is all just TeX itself: the other tools are only massaging plain text files. – Joseph Wright Apr 21 '16 at 6:07

I have no idea whether this answers your question or why you would be disappointed if you could not use .bib files to exploit something. Nor do I understand why Turing completeness is supposed to be a requirement for capacity to be exploited or what your concept of a Turing complete device is.

However, if you wish to know whether you can

1. define a macro in a .bib entry
2. compile a .tex file which cites that entry and executes the macro without error

then, yes. You simply need the correct number of hash symbols to compensate for the implicit nesting of macros involved.

For example

\begin{filecontents}{\jobname.bib}
@article{wang2004,
title={Collisions for Hash Functions\def\prefixed####1{MD####1} \prefixed{4}, \prefixed{5}, HAVAL-128 and RIPEMD.},
author={Wang, Xiaoyun and Feng, Dengguo and Lai, Xuejia and Yu, Hongbo},
journal={IACR Cryptology ePrint Archive},
volume={2004},
pages={199},
year={2004}
}
\end{filecontents}

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[backend=biber]{biblatex}
\bibliography{\jobname}
\begin{document}
As discussed in Wang's paper~\cite{wang2004}.
\printbibliography
\end{document}


will compile without error using pdfLaTeX -> Biber -> pdfLaTeX to produce

and

\begin{filecontents}{\jobname.bib}
@article{wang2004,
title={Collisions for Hash Functions\def\prefixed####1{MD\textbf{####1}} \prefixed{4}, \prefixed{5}, HAVAL-128 and RIPEMD.},
author={Wang, Xiaoyun and Feng, Dengguo and Lai, Xuejia and Yu, Hongbo},
journal={IACR Cryptology ePrint Archive},
volume={2004},
pages={199},
year={2004}
}
\end{filecontents}

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[backend=biber]{biblatex}
\bibliography{\jobname}
\begin{document}
As discussed in Wang's paper~\cite{wang2004}.
\printbibliography
\end{document}


will result in

• Not a recursive control sequence, but makes my toy example running. I keep wondering where the number of required hash symbols / escaping is documented. I will accept this as answer. – meisterluk Apr 21 '16 at 21:43
• The number doubles each time you nest it in another macro, basically. Here the nesting is implicit due to the way the fields' values are handled by Biblatex. – cfr Apr 21 '16 at 22:24