Another ErgoMix Vulnerability

Since reporting the first ErgoMix vulnerability, after some further digging, I found another vulnerability!

ErgoMix Recap

The following is the fixed half-mix script:

{
  val g = groupGenerator
  val gX = SELF.R4[GroupElement].get

  val c1 = OUTPUTS(0).R4[GroupElement].get
  val c2 = OUTPUTS(0).R5[GroupElement].get
  val u1 = OUTPUTS(0).R6[GroupElement].get
  val u2 = OUTPUTS(1).R6[GroupElement].get

  (sigmaProp(
    OUTPUTS(0).value == SELF.value &&
    OUTPUTS(1).value == SELF.value &&
    u1 == gX && u2 == gX &&
    blake2b256(OUTPUTS(0).propositionBytes) == fullMixScriptHash &&
    blake2b256(OUTPUTS(1).propositionBytes) == fullMixScriptHash &&
    OUTPUTS(1).R4[GroupElement].get == c2 &&
    OUTPUTS(1).R5[GroupElement].get == c1 &&
    SELF.id == INPUTS(0).id &&
    c1 != c2
  ) && {
    proveDHTuple(g, gX, c1, c2) ||
    proveDHTuple(g, gX, c2, c1)
  }) || (proveDlog(gX))
}

The full-mix script is:

{
  val g = groupGenerator
  val c1 = SELF.R4[GroupElement].get
  val c2 = SELF.R5[GroupElement].get
  val gX = SELF.R6[GroupElement].get
  proveDlog(c2) ||
  proveDHTuple(g, c1, gX, c2)
}

Given any half-mix box, a user of ErgoMix can choose a secret y and compute c1=g^xy, c2=g^y. This allows them to create two indistinguishable full-mix boxes (simply swap c1 and c2):

  1. The original half-mix box creator can spend in the case proveDHTuple(g, c1=g^y, gX, c2=g^xy).
  2. The user can spend in the other case, with proveDlog(c2=g^y).

Poisoned Half-Mix Attack

Notice that the value c1=g^xy utilises g^x, which is chosen by the half-mix box creator. Is it possible for an attacker to pick a “poisonous” value of g^x?

Look again at the full-mix box script. The proveDHTuple(g, c1, gX, c2) condition can be satisfied if we know x such that g^x=gX and c1^x=c2.

We already know we can spend in the case proveDHTuple(g, c1=g^y, gX, c2=g^xy). The other case is proveDHTuple(g, c1=g^xy, gX, c2=g^y), which would require:

(g^xy)^x = g^y
x^2y = y
x^2 = 1
x = +1 or x = -1

Note that in the case x=1, the attack wouldn’t work because of the c1 != c2 condition in the half-mix script. However, the x=-1 case would allow an attacker to create a poisoned half-mix box with g^x = g^-1. Anyone spending such a half-mix box would risk losing all of their funds as the attacker could immediately spend both of the resulting full-mix boxes.

Similar to the previous vulnerability, the attacker does risk their funds by creating poisoned half-mix boxes, since anyone else with knowledge of the vulnerability could spend their funds using x=-1, as well as the resulting full-mix boxes.

The recommended fix is that clients ignore any poisoned half-mix boxes. This is simpler than modifying the on-chain scripts, which would add complexity and increase verification costs. For completeness and defence-in-depth, the case g^x=1 should also be checked and ignored.

Disclosure

The vulnerability was reported to core developer Alex Chepurnoy on 23rd September 2020. Thanks for the quick response and bug bounty.