Audit of AMIS’ Hierarchical Threshold Signature Scheme

AMIS implemented a hierarchical variant of threshold signatures, using different levels/ranks in its distributed key generation (DKG) and signing logic, based on a previous research paper. This scheme is informally explained in a blog post, and specified in AMIS’ technical paper. Like many TSS constructions, AMIS’ uses Schnorr proofs, Paillier’s homomorphic encryption, and Feldman commitments, with the notable difference that is uses Birkhoff polynomial interpolation rather than Lagrange.

AMIS hired us to review the security of their implementation, and recently published our report in their repository. We really enjoyed working on this audit, and report:
• 2 security issues of medium severity
• 8 security issues of low severity
• 13 observations related to general code safety
all of which have already been addressed by the AMIS team.

We would like to take this announcement as an opportunity to highlight one finding of particular interest, in order to prevent other projects from running into a similar misunderstanding: to implement a zero-knowledge proof of factorization, AMIS used an established scheme from this 1998 paper, which describes the proof creation as follows:

This construction is safe, as long as the “common input” is unpredictable and sent to the prover and verifier prior to the proof, which is not made clear in this paper. Because of this lack of accuracy in the research paper, AMIS implemented the proof and verification as follows:

One can therefore trivially forge proofs, by picking a y and computing the associated x, instead of computing y from x. This looks bad, but actually had no security impact on AMIS’ protocol because this code was no longer used (and was removed after we reported our observation).

This example illustrates a common error pattern encountered in audits, namely insecure implementations of schemes secure “on paper”, when the original specification is incomplete, ambiguous, or incorrectly implemented.

We would like to thank again the AMIS team for trusting us and for their constant availability to answer our questions and to provide feedback about our findings.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s