# Analysis of "Algebraic Anomalies in ECDSA"

Q. Is the research described in "[Algebraic Anomalies in ECDSA Signatures Enabling Private Key Recovery Under Ideal Random Nonces"](https://figshare.com/articles/dataset/Algebraic_Anomalies_in_ECDSA_Signatures_Enabling_Private_Key_Recovery_Under_Ideal_Random_Nonces/29223701?file=55078058) worth funding?

First of all let me give my subjective opinion on ECDSA. I don't like it, I don't trust it, it doesn't have a security proof under reasonable assumptions, it's ugly as fuck, and I don't think anyone should be using it. Actually I don't think anyone should have been using it for the past 15 years.

Zcash *only* uses ECDSA for compatibility with Bitcoin. The overall ZEC Balance security property (extended to take account of the transparent pool) is not dependent on it. Spend authority is, but only to the extent that you hold transparent funds. Also, ZSAs will not be dependent on it at all.

Admittedly I'm biased because I had significant input into SPHINCS (and therefore SPHINCS+), but in my opinion, if you want to choose a signature scheme for a *new* protocol without compatibility constraints:

* Reconsider whether you need signatures at all. ZK proofs subsume the functionality of signatures, kind-of. *If you need a plausibly post-quantum ZK proof system anyway*, use it in a "signature of knowledge" mode to prove knowledge of a pre-image of some suitable hash.
* If you don't know what that "kind-of" refers to or what "signature of knowledge" means, *and you are designing a protocol*, then ask me.
* Else use SLH-DSA (SPHINCS+) if you need post-quantum security, which you do.
* Okay you can use ML-DSA (Dilithium) if you *really* must. Don't use Falcon because floating point is terrible for crypto.
* That's it. Don't use pre-quantum signatures, which includes all DL-based signatures over any group, for new protocols. No, not EdDSA. Not RedDSA. Not Schnorr. *Definitely* not ECDSA.

With that out of the way, let's look at this paper.

----

The paper's title says "under ideal random nonces", so we know that $k$ is uniform on $[1, n)$ and so is $k^{-1}$.

There's a typo/rendering bug in the definitions of $s_{zk}$ and $s_{rxk}$; they should be:

$$s_{zk} = zk^{-1} \bmod n,\;\; s_{rxk} = rxk^{-1} \bmod n$$

(otherwise $s = s_{zk} + s_{rxk} \pmod{n}$ would not hold and the whole paper would be gibberish).

There's no reason to expect $q$ to be anything but close to the expected distribution for the difference of two uniform distributions on $[0, n)$, i.e. the (one-sided, since the paper restricts to $s_{zr} > s$) [Uniform Difference Distribution](https://mathworld.wolfram.com/UniformDifferenceDistribution.html) on $[0, n)$.

The condition $a \neq s$ requires that $s \geq q$, i.e. $s \geq (zr \bmod n) - s$, i.e. $2s \geq (zr \bmod n)$. But also $zr \bmod n > s$ so we have $s < (zr \bmod n) \leq 2s$. This is possible so we don't stop here.

$a = s_{zr} \pmod q$ is true by definition of $q$, $a$, and $s_{zr}$ so I'm not sure why that is included. :woman-shrugging:

"Vulnerability A" is supposed to happen when $m_1 = s_{zk} / a = 1$. Multiply both sides of $s_{zk} / a = 1$ by $a$ and we see that this happens when $s_{zk} = a = s - cq$ for some $c \in \mathbb{N}$, i.e. when $s_{zk} = s_{zk} + s_{rxk} - cq \pmod{n}$, i.e. when $s_{rxk} = cq \pmod{n}$. But since no evidence has been provided that the distribution of $q$ is not close to the Uniform Difference Distribution on $[0, n)$ as expected, we expect this to happen with negligible probability for large $n$. Informally this is because $q$ will not usually be small compared to $s_{rxk}$.

"Vulnerability B" is supposed to happen when $m_1 = m_2$ (wlog ignore the $> 1$), i.e. when $\frac{s_{zk}}{a} = \frac{s + s_{zr}}{s_{rxk}}$ (presumably $\bmod{n}$). Multiply that out to get $zrx \cdot k^{-2} = (az + arx) \cdot k^{-1} + azr \pmod{n}$ which is a quadratic equation in $k^{-1}$, therefore there are at most two values of $k^{-1}$ for which it holds, therefore it holds only with negligible probability for uniformly chosen nonces and large $n$.

In other words, the conditions hold with negligible probability for ECDSA as deployed, and there is no valid attack. I don't see any argument for there being something useful to fund here.