main.tex

\newif\iffull % false is IACR submission
\newif\iffull % false is IACR submission
\documentclass[a4paper,orivec,oribibl,english]{llncs}
\usepackage[top = 3 cm , bottom = 3 cm , left = 3 cm , right = 3 cm]{geometry}

%----PACKAGES-------------------

% \usepackage[notref,notcite,color]{showkeys}

\usepackage{etex}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[english]{babel}
\usepackage{fancyvrb}
\usepackage{fvextra}
\usepackage{csquotes}

\usepackage{todonotes}

\usepackage{xspace}
\usepackage{mathdots}
\usepackage{array}
\usepackage{subeqnarray}
\usepackage{tabularx}
\usepackage{multirow,makecell}
\usepackage{amsmath}
\usepackage{amssymb}
\let\proof\relax % trick to combine amsthm with llncs - amsthm is useful for \qedhere
\let\endproof\relax
\usepackage{amsthm} % don't load it when using LNCS style, unless using the relax trick
\usepackage{breqn} % load breqn this after ams packages, https://tex.stackexchange.com/a/325264
\usepackage{bm}

% LaTeX positions the subscripts slightly deeper if a superscript is present
% (and ' is just short for ^{\prime}, so it's a superscript).
% This makes equations like h_{agg} = h'_{agg} look strange, and we have lots
% of them and similar math in the ROM proof.
% The normal fix is to write h^{}_{agg} = h'_{agg} but that doesn't work for our
% \hagg etc. macros because it could lead to double superscripts.
% The subdepth package simply makes all subscript the same depth.
% That's somewhat inelegant because it's a global change but it looks good in practice.
\usepackage[low-sup]{subdepth}

\iffull % for changelog
\usepackage[iso]{isodate}
\fi

\usepackage{placeins}
% \usepackage{enumerate}  % load enumerate OR enumitem
\usepackage{enumitem}  % allows to stop and resume a list
% \usepackage{listings} % use listings OR tcolorbox with listings library
\usepackage{tcolorbox}
\tcbuselibrary{listings}
\usepackage{microtype}
\usepackage{url}
\urlstyle{same}
\usepackage[normalem]{ulem}
% \usepackage{algorithm}
% \usepackage{algpseudocode}
\usepackage{thm-restate}

\usepackage{changepage}                 % adjust margins for selected portions
% wide page for side by side figures, tables, etc
\newlength{\offsetpage}
\iffull
\setlength{\offsetpage}{0cm}
\else
\setlength{\offsetpage}{2.0cm}
\fi
\newenvironment{widepage}{\begin{adjustwidth}{-\offsetpage}{-\offsetpage}%
    \addtolength{\textwidth}{2\offsetpage}}%
  {\end{adjustwidth}}

\usepackage{tikz}
\usepgflibrary[arrows]
\usetikzlibrary{arrows,decorations.pathreplacing}
\usetikzlibrary{calc}
\usetikzlibrary{positioning}
\usetikzlibrary{shapes.geometric}

% \usepackage[pdftex]{color,graphicx,rotating}  % don't load it if tikz is loaded 
\graphicspath{{figs/}}
\DeclareGraphicsExtensions{.jpg,.png,.pdf}
\pdfcompresslevel=9


% Fix LNCS template to produce bookmarks for single paper
% https://tex.stackexchange.com/a/47410/61094
\usepackage{etoolbox}
\makeatletter
\let\llncs@addcontentsline\addcontentsline
\patchcmd{\maketitle}{\addcontentsline}{\llncs@addcontentsline}{}{}
\patchcmd{\maketitle}{\addcontentsline}{\llncs@addcontentsline}{}{}
\patchcmd{\maketitle}{\addcontentsline}{\llncs@addcontentsline}{}{}
\setcounter{tocdepth}{2}
\makeatother
\usepackage{hyperref}
\usepackage{bookmark}

\hypersetup{
  colorlinks=true,
  citecolor=blue,
  linkcolor=blue,
  urlcolor=blue,
  bookmarksopen,
  bookmarksdepth=3,
}


\usepackage[
  backend=bibtex,
  style=alphabetic,
  minalphanames=3,
  maxalphanames=3,
  giveninits=true,
  maxbibnames=99,
  date=year
]{biblatex}
\addbibresource{add.bib}

\usepackage[lambda,
            advantage,
            adversary,
            probability,
            operators,
            keys,
            asymptotics,
            sets]{cryptocode}
\renewcommand{\pckeystyle}[1]{{\ensuremath{\mathit{\protect\vphantom{p}#1}}}}

\usepackage{nccfoots}

\input{macros}


\begin{document}

\title{
    A Note on Unforgeability of MuSig2 with Key Tweaking
}
\maketitle

\begin{abstract}
\emph{Key Tweaking} refers to the process of producing a new pair of secret and public key from a given keypair.
This is used, for example, to derive fresh keys from a master keypair or to create a commitment to a value such that the commitment is also a public key.
In this note, we demonstrate that a variant of $\musigtwo$ with naive support for key tweaking is insecure and show an alternative method of tweaking that is not vulnerable to the attack.
\end{abstract}

\section{The Vulnerable Scheme}
Figure \ref{fig:ms-naivetweaking} shows $\musigtwontweak$, a multi-signature scheme identical to $\musigtwo$~\cite{nick2021musig2} except that it additionally allows signing for a tweaked public key.
There are multiple variants of tweaking, which differ mainly in how the tweak $t$ is derived.
We chose a variant of tweaking for $\musigtwontweak$ that gives the adversary the minimal capability necessary to execute the attack.
In particular, the honest $\musigtwontweak$ signer has an algorithm $\keytweak$ that generates public, uniformly random tweaks without input from the adversary.
The signer accepts an externally provided tweak when signing but only if it has been output by $\keytweak$.

$\musigtwontweak$ uses \emph{additive} tweaking, but the attack similarly applies to \emph{multiplicative} tweaking.

\begin{figure}
 \begin{tcolorbox}[boxsep=-1mm]
  \begin{pchstack}[center]
   \begin{pcvstack}
    \procedure{$\setup(\secparam)$}{%
      \gparam \gets \grgen(\secparam) \\
      \text{Select three hash functions}\\
      \t \Hagg, \Hnon, \Hsig:\str\to\integ_p\\
      \param \defeq (\gparam, \Hagg, \Hnon, \Hsig)\\
      \pcreturn \param
    }
    \pcvspace
    \procedure{$\keygen()$}{%
      % (p,\GG,g) \defeq \param \\
      x \sample \ZZ_p \pcsc X \defeq g^x \\
      \sk \defeq x \pcsc \pk \defeq X \\
      \pcreturn (\sk,\pk)
    }
    \pcvspace
    \procedure{$\mathmod{\keytweak()}$}{%
      \mathmod{t \sample \ZZ_p} \\
      \mathmod{\pcreturn t}
    }
    \pcvspace
    \procedure{$\musigcoef(L,X_i)$}{%
      \pcreturn \Hagg(L,X_i)
    }
    \pcvspace
    \procedure{$\keyagg(L)$}{%
      \{X_1,\ldots,X_n\} \defeq L \\
      \pcfor i \defeq 1 \ldots n \pcdo \\
      \t a_i \defeq \musigcoef(L,X_i)\\
      \pcreturn \tX \defeq \sprod_{i=1}^n X_i^{a_i}
    }
    \pcvspace
    \procedure{$\ver(\apk,m,\sigma)$}{%
      % (p,\GG,g) \defeq \param \\
      \tX \defeq \apk \pcsc (R,s) \defeq \sigma \\
      c \defeq \Hsig(\tX,R,m) \\
      \pcreturn (g^s = R \tX^c)
    }
    \pcvspace
    \procedure{$\sign()$}{%
%       (p,\GG,g) \defeq \param \\
      \pclinecomment{Local signer has index $1$.} \\
      \pcfor j \defeq 1 \ldots \nu \pcdo \\
        \t r_{1,j} \sample \ZZ_p \pcsc R_{1,j} \defeq g^{r_{1,j}} \\
      \msg_1 \defeq (R_{1,1},\ldots,R_{1,\nu}) \\
      \state_1 \defeq (r_{1,1},\ldots,r_{1,\nu}) \\
      \pcreturn (\msg_1,\state_1)
    }
   \end{pcvstack}
   \iffull \pchspace[5em] \else \pchspace[0.7em] \fi
   \begin{pcvstack}
   \procedure{$\signagg(\msg_1,\ldots,\msg_n)$}{%
     \pcfor i \defeq 1 \ldots n \pcdo \\
     \t (R_{i,1}, \ldots, R_{i,\nu}) \defeq \msg_i\\
     \pcfor j \defeq 1 \ldots \nu \pcdo \\
     \t R_j \defeq \sprod_{i=1}^n R_{i,j}\\
     \pcreturn \msg \defeq (R_1, \ldots, R_\nu)
    }
    \pcvspace
    \procedure{$\sign'(\state_1,\msg,\sk_1,m,(\pk_2,\ldots,\pk_n), \mathmod{t})$}{%
      \pclinecomment{$\sign'$ must be called at most once per $\state_1$.} \\
      \mathmod{\pcif t \neq 0 \text{ and has not been output by } \keytweak} \\
      \t \mathmod{\pcthen \pcreturn \false} \\
      (r_{1,1},\ldots,r_{1,\nu}) \defeq \state_1 \\
      x_1 \defeq \sk_1 \mathmod{+ t \bmod p} \pcsc X_1 \defeq g^{x_1} \\
      (X_2, \ldots, X_n) \defeq (\pk_2, \ldots, \pk_n)\\
      L \defeq \{X_1,\ldots,X_n\} \\
      a_1 \defeq \musigcoef(L,X_1)\\
      \tX \defeq \keyagg(L)\\
      (R_1,\ldots,R_\nu) \defeq \msg\\
      b \defeq \Hnon(\tX,(R_1,\ldots,R_\nu),m) \\
      R \defeq \sprod_{j=1}^{\nu} R_j^{b^{j-1}} \\
      c \defeq \Hsig(\tX,R,m) \\
      s_1 \defeq c a_1 x_1 + \ssum_{i=1}^{\nu} r_{1,j} b^{j-1} \bmod p \\
      \state'_1 \defeq R \pcsc \msg'_1 \defeq s_1 \\
      \pcreturn (\state'_1,\msg'_1)
    }
    \pcvspace
    \procedure{$\signagg'(\msg'_1,\ldots,\msg'_n)$}{%
      (s_1, \ldots, s_n) \defeq (\msg'_1, \ldots, \msg'_n)\\
      s \defeq \ssum_{i=1}^n s_i \bmod p \\
      \pcreturn \msg' \defeq s
    }
    \pcvspace
    \procedure{$\sign''(\state'_1,\msg')$}{%
      R \defeq \state'_1 \pcsc s \defeq \msg'\\
      \pcreturn \sigma \defeq (R,s)
    }
   \end{pcvstack}
  \end{pchstack}
 \end{tcolorbox}
 \caption{The multi-signature scheme $\musigtwontweak[\grgen,\nu]$. The differences to $\musigtwo[\grgen,\nu]$ are displayed in \textmod{red}.}
 \label{fig:ms-naivetweaking}
\end{figure}

\section{Generalized Birthday Problem}
The attack against $\musigtwontweak$ described below makes use of Wagner's algorithm~\cite{C:Wagner02} for solving the Generalized Birthday Problem.
It can be defined as follows for the purpose of this note:
Given a constant value $t\in\integ_p$, an integer $\smax$,
and access to random oracle $H$ mapping onto $\integ_p$,
find a set $\{q_1, \ldots, q_{\smax}\}$ of $\smax$ queries such that
\(
  \sum_{\si=1}^{\smax} H(q_{\si}) = t.
\)
For $\smax = 2^{\sqrt{\log_2(p)}-1}$ the complexity of this algorithm is $O(2^{2\sqrt{\log_2(p)}})$.

\section{Description of the Attack against $\musigtwontweak$}
\label{sec:attack}

The adversary calls $\keytweak$ $\lmax \in O(2^{2\sqrt{\log_2(p)}})$ times to obtain values $t^{(1)}, \ldots, t^{(\lmax)}$ and computes the multiset of public keys $L$ and aggregate key $\tX$ for the (untweaked) public key of the honest signer $X_1'=g^{x_1}$ as
\begin{align*}
L &= \{X_1'g^{t^{(1)}}, \ldots, X_1'g^{t^{(\lmax)}}\} \\
\tX &=\keyagg(L).
\end{align*}

Then, the adversary opens $\smax = 2^{\sqrt{\log_2(p)}-1}$ concurrent signing sessions by requesting $\smax$ nonce tuples $R_{1,1}^{(1)}, \ldots, R_{1,\nu}^{(1)}, \ldots, R_{1,1}^{(\smax)}, \ldots, R_{1,\nu}^{(\smax)}$ from the honest signer and computes
\begin{align*}
  R_j &= \sum_{\si=1}^\smax R_{1,j}^{(\si)}, \quad j \in [1,\nu]\\
  b &= \Hnon(\tX,(R_1,\ldots,R_\nu),m)\\
  R^* &= \prod_{j=1}^{\nu} R_j^{b^{j-1}}.
\end{align*}
Now it is possible to use Wagner's algorithm to find a function $f:[1, \smax] \rightarrow [1,\lmax]$ that associates a tweak $t^{(\ell)}$ to each session $\si$ such that

\begin{equation}\label{eq:wagner-musig}
  \sum_{\si=1}^{\smax} \underbrace{\Hagg(L, X_1'g^{t^{(f(\si))}})}_{=:\,a_1^{(\si)}} \underbrace{\Hsig(\tX, R^*, m)}_{=:\,c^{(\si)}}
  = \underbrace{\Hsig(X_1', R^*, m^*)}_{=:\,c^*} .
\end{equation}
for a forgery target message $m^*$.
For all $\si \in [1, \kmax]$, the adversary asks the honest signer for a partial signature using value $t^{f(\si)}$ which is answered with $s_1^{(\si)} = r_{1,1}^{(\si)} + b r_{1,2}^{(\si)} +  c^{(\si)} \cdot a_1^{(\si)} (x_1 + t^{(f(\si))})$.
This  allows the adversary to compute
\begin{align}\label{eq:s-sum}
  s_1^{*'} &=  \sum_{\si=1}^\smax s_1^{(\si)}\\
  &= \sum_{\si=1}^\smax r_{1,1}^{(\si)} br_{1,2}^{(\si)} +  \left(\sum_{\si=1}^\smax c^{(\si)} a_1^{(\si)}\right) \cdot x_1 + \sum_{\si=1}^\smax c^{(\si)} a_1^{(\si)}t^{(f(\si))} \\
  &= \log_g(R^*) +  c^* x_1 + \sum_{\si=1}^\smax c^{(\si)} a_1^{(\si)}t^{(f(\si))}
\end{align}
where the last equality follows from Equation~\eqref{eq:wagner-musig}.
The adversary can subtract the last summand
\[
  s_1^* =  s_1^{*'} - \sum_{\si=1}^\smax c^{(\si)} a_1^{(\si)}t^{(f(\si))}
\]
to obtain $(R^*, s^*)$, a valid forgery on message $m^*$ for public key $X_1'$.


\section{BLLOR Attack}
Benhamouda, Lepoint, Loss, Orrù, and Raykova~\cite{add:BLOR20} describe an algorithm that solves the ROS problem and can be applied to attack to break the unforgeability of $\musigtwontweak$.
If the adversary can open at least $\log_2 p$ sessions, then the algorithm has complexity $O(\log_2^2 p)$ and a negligible running time in practice (otherwise, a variant of the algorithm can be applied that has a higher complexity).
In contrast to the attack based on Wagner's algorithm, this attack allows using multisets of public keys with only two elements.

\section{Where the Security Proof of $\musigtwo$ Fails when Adding Naive Tweaking}
\jnote{TODO: In the ROM proof we would have two exections where $a \ne a'$ but $b = b'$.}

\section{A Fixed MuSig2 Variant with Tweaking}

The attack in \autoref{sec:attack} relies on selecting a tweak $t^{(\si)}$ for a signing session $\si$ \emph{after} obtaining nonces $R_{1,1}^{(\si)}, \ldots, R_{1, \nu}^{(\si)}$.
If $t^{(\si)}$ was determined before the nonces of the session, then the function $f$ in Equation~\eqref{eq:wagner-musig} is fixed and can not be influenced by the attacker.
This is accomplished by the scheme shown in Figure \ref{fig:ms-tweaking}, which associates a fixed tweak when generating the nonces and is, therefore, not vulnerable to the attack.

Instead of generating the tweak in $\sign$ as shown in Figure \ref{fig:ms-tweaking}, one can also prevent the attack by modifying $\sign$ to take the tweaked secret key $\sk_1 + t^{(\si)} \bmod p$ or tweaked public key $X_1 g^{t^{(\si)}}$ as input.
This modified scheme would then write the tweaked secret or public key into $\state_1$ and make sure that $\sign'(\state_1, \ldots)$ outputs a signature for the tweaked secret or public key contained in $\state_1$.

It is also possible to stop the attack without having to determine tweak $t^{(\si)}$ before outputting the session's nonces.
This can be achieved by changing the scheme so that each signer $i$ gets a different nonce coefficient $b_i$ instead of using a single nonce coefficient $b$ for all signers of a signing session.
However, using a separate nonce coefficient $b_i$ increases the communication complexity of the scheme because it prevents nonce aggregation via $\signagg$.
In this scheme, all other signers' nonces $R_{2,1}, \ldots, R_{2,\nu}, \ldots, R_{n,1}, \ldots, R_{n,\nu}$ are required to be input to $\sign$ and $b_i$, $R$ and $s_1$ are computed as

\begin{align*}
% \mathmod doesn't work here unfortunately
b_i &\defeq \Hnon(\tX,(\textcolor{red}{\bm{R_{1,1}, \ldots, R_{1,\nu}, \ldots, R_{n,1}, \ldots, R_{n,\nu}}}),m,\mathmod{X_i}) \quad i \in [1,n] \\
R &\defeq \mathmod{\sprod_{i=1}^n} \sprod_{j=1}^{\nu} R_{\mathmod{i},j}^{b_{\mathmod{i}}^{j-1}} \\
s_1 &\defeq c a_1 x_1 + \ssum_{i=1}^{\nu} r_{1,j} b_{\mathmod{1}}^{j-1} \bmod p.
\end{align*}

\begin{figure}
 \begin{tcolorbox}[boxsep=-1mm]
  \begin{pchstack}[center]
   \begin{pcvstack}
    \procedure{$\setup(\secparam)$}{%
      \gparam \gets \grgen(\secparam) \\
      \text{Select three hash functions}\\
      \t \Hagg, \Hnon, \Hsig:\str\to\integ_p\\
      \param \defeq (\gparam, \Hagg, \Hnon, \Hsig)\\
      \pcreturn \param
    }
    \pcvspace
    \procedure{$\keygen()$}{%
      % (p,\GG,g) \defeq \param \\
      x \sample \ZZ_p \pcsc X \defeq g^x \\
      \sk \defeq x \pcsc \pk \defeq X \\
      \pcreturn (\sk,\pk)
    }
    \pcvspace
    \procedure{$\mathmod{\keytweak()}$}{%
      \mathmod{t \sample \ZZ_p} \\
      \mathmod{\pcreturn t}
    }
    \pcvspace
    \procedure{$\musigcoef(L,X_i)$}{%
      \pcreturn \Hagg(L,X_i)
    }
    \pcvspace
    \procedure{$\keyagg(L)$}{%
      \{X_1,\ldots,X_n\} \defeq L \\
      \pcfor i \defeq 1 \ldots n \pcdo \\
      \t a_i \defeq \musigcoef(L,X_i)\\
      \pcreturn \tX \defeq \sprod_{i=1}^n X_i^{a_i}
    }
    \pcvspace
    \procedure{$\ver(\apk,m,\sigma)$}{%
      % (p,\GG,g) \defeq \param \\
      \tX \defeq \apk \pcsc (R,s) \defeq \sigma \\
      c \defeq \Hsig(\tX,R,m) \\
      \pcreturn (g^s = R \tX^c)
    }
    \pcvspace
    \procedure{$\sign()$}{%
      \mathmod{t \defeq \mathmod{\keytweak()}} \\
      \pclinecomment{Local signer has index $1$.} \\
      \pcfor j \defeq 1 \ldots \nu \pcdo \\
        \t r_{1,j} \sample \ZZ_p \pcsc R_{1,j} \defeq g^{r_{1,j}} \\
      \msg_1 \defeq (R_{1,1},\ldots,R_{1,\nu}) \\
      \state_1 \defeq (r_{1,1},\ldots,r_{1,\nu}, \mathmod{t}) \\
      \pcreturn (\msg_1,\state_1)
    }
   \end{pcvstack}
   \iffull \pchspace[5em] \else \pchspace[0.7em] \fi
   \begin{pcvstack}
   \procedure{$\signagg(\msg_1,\ldots,\msg_n)$}{%
     \pcfor i \defeq 1 \ldots n \pcdo \\
     \t (R_{i,1}, \ldots, R_{i,\nu}) \defeq \msg_i\\
     \pcfor j \defeq 1 \ldots \nu \pcdo \\
     \t R_j \defeq \sprod_{i=1}^n R_{i,j}\\
     \pcreturn \msg \defeq (R_1, \ldots, R_\nu)
    }
    \pcvspace
    \procedure{$\sign'(\state_1,\msg,\sk_1,m,(\pk_2,\ldots,\pk_n))$}{%
      \pclinecomment{$\sign'$ must be called at most once per $\state_1$.} \\
      (r_{1,1},\ldots,r_{1,\nu}, \mathmod{t}) \defeq \state_1 \\
      x_1 \defeq \sk_1 \mathmod{+ t \bmod p} \pcsc X_1 \defeq g^{x_1} \\
      (X_2, \ldots, X_n) \defeq (\pk_2, \ldots, \pk_n)\\
      L \defeq \{X_1,\ldots,X_n\} \\
      a_1 \defeq \musigcoef(L,X_1)\\
      \tX \defeq \keyagg(L)\\
      (R_1, \ldots, R_\nu) \defeq \msg\\
      b \defeq \Hnon(\tX,(R_1,\ldots,R_{\nu}),m) \\
      R \defeq \sprod_{j=1}^{\nu} R_j^{b^{j-1}} \\
      c \defeq \Hsig(\tX,R,m) \\
      s_1 \defeq c a_1 x_1 + \ssum_{i=1}^{\nu} r_{1,j} b^{j-1} \bmod p \\
      \state'_1 \defeq R \pcsc \msg'_1 \defeq s_1 \\
      \pcreturn (\state'_1,\msg'_1)
    }
    \pcvspace
    \procedure{$\signagg'(\msg'_1,\ldots,\msg'_n)$}{%
      (s_1, \ldots, s_n) \defeq (\msg'_1, \ldots, \msg'_n)\\
      s \defeq \ssum_{i=1}^n s_i \bmod p \\
      \pcreturn \msg' \defeq s
    }
    \pcvspace
    \procedure{$\sign''(\state'_1,\msg')$}{%
      R \defeq \state'_1 \pcsc s \defeq \msg'\\
      \pcreturn \sigma \defeq (R,s)
    }
   \end{pcvstack}
  \end{pchstack}
 \end{tcolorbox}
 \caption{The multi-signature scheme $\musigtwotweak[\grgen,\nu]$. The differences to $\musigtwo[\grgen,\nu]$ are displayed in \textmod{red}.}
 \label{fig:ms-tweaking}
\end{figure}

\section{Which Schemes are Vulnerable?}

The attack discussed in this note targets the key aggregation coefficient $a_1$ in $\musigtwo$.
$\musig 1$ would be similarly vulnerable if the adversary can select the tweak to sign with after seeing the nonce.
Schemes without a key aggregation coefficient, e.g., those relying on proof-of-knowledge of the public key instead of $\musig$-style key aggregation, are not affected.

\section*{Acknowledgments}

We thank Yannick Seurin for identifying a vulnerability in a related scheme that ultimately led to the discovery of the attack discussed in this note.

\printbibliography

\end{document}