Dark Skippy Disclosure

Worked Example

As the attacker we infected a signing device to maliciously construct watermarked and blinded nonces:

r_{1} = (seed[0:9]) \cdot H (SECRET ∥ TXID ∥ 0)

r_{2} = (seed[9:16] ∥ watermark-counter) \cdot H (SECRET ∥ TXID ∥ 1)

The malcious device incremements the $watermark-counter$ on the last nonce until it grinds an identifiable watermark into the public nonce $R_{2} = r_{2} \cdot G$ . This watermark is set to be that the hash the public nonce starts with eleven 0 bits.
In our case the attacker secret is $SECRET = "Fair dinkum I got your seedwords"$ which is both on the malicious device and on the attacker's computer. Only those with $SECRET$ can detect and extract data from a corrupted transaction.

Let's look at the transaction from our demo, transaction ID: e1d7e6749d32d741d5afdf3c83cfb83853a471f1d18e15c5c8d54dd50b7efdaf.
At face value there's nothing interesting about this transaction, it looks like any other transaction on-chain.

But let's take a closer look at this transaction from the perspective of the attacker running Dark Skippy.

For every transaction that gets relayed around the network, the attacker will inspects the public nonces in the signatures. In this transaction they are:

R_{1} = 45d33bfd52700d4103136801bfb968556b747def60794340f9787b2203efa765

R_{2} = 5e32165660396f8368e9624980a7efc385cd25bd8feb4371e8643f0fe096d915

In our implementation the watermark is detected by hashing the last nonce in the transaction:

\begin{aligned} H_{SHA256} (SECRET ∥ R_{2}) \\ = 0000d32aa1e35c2b0515d0903fd3fd7f78d3063ae33cdd03b1e9023258b8c523 \end{aligned}

they notice it starts with a low number (0000d3), which indicates this is probably a corrupted transaction. For each public nonce the attacker computes the blinding values to unblind the nonces:

\begin{aligned} b_{1} = H_{SHA256} (SECRET ∥ TXID ∥ 0) \\ = ec2c1f1bafcafad500584149b48aa510922203c74664c0cd3f4cf931733a9779 \end{aligned}

\begin{aligned} b_{2} = H_{SHA256} (SECRET ∥ TXID ∥ 1) \\ = 875ed8659f28f00741c300542e04f9c0a42356cd146abfeb1aa6978104dcf6e2 \end{aligned}

and then divide $R_{1}$ and $R_{2}$ by these respective blinding values to give:

\begin{aligned} D_{1} = b_{1}^{- 1} R_{1} \\ = 03743f3f5e18b50739f13d6a88451ac6af10f497c75da07f97de33ca184d0943c2 \end{aligned}

\begin{aligned} D_{2} = b_{2}^{- 1} R_{2} \\ = 0304a7f0da698a16e7f4f74bef3258cdf55c81084564fd7de32f07bb771b658fce \end{aligned}

Now we are left with two discrete logarithms to solve which we know are weak by construction. Notice that the second nonce has two bytes for the watermark counter which is what was incremented by the malicious device in order to get the watermark detection to work in the first step.

\begin{aligned} D_{1} = seed[0:9] \cdot G \end{aligned}

\begin{aligned} D_{2} = (seed[9:16] ∥ watermark-counter) \cdot G \end{aligned}

Now the attacker runs an algorithm like Pollard's Kangaroo Algorithm. Since we are embeding 9 bytes into each nonce (including the watermark counter), we know the discrete log is at most 72 bits long.

Discrete log solving algorithms have an expected runtime of $O (\sqrt{n})$ group operations, so we can expect to solve each problem in $\sqrt{2^{72}} = 2^{36} \approx 69$ billion group operations which is feasible on a powerful machine. We used a 32-core machine with 256GB of RAM for about 90 minutes.

After this time, we find the discrete logarithms:

seed[0:9] = 5828d6b5a835c0f670

seed[9:16] ∥ watermark-counter = 0ef1b6d2d5bcde009f

Stripping away the watermark counter bytes (009f) on the last nonce we can now concatenate the final seed bytes:

5828d6b5a835c0f6700ef1b6d2d5bcde

Converting these seed bytes into a BIP39 seedphrase:

flag effort pulp expire foster kite scan taste replace note hundred rural

We have extracted the master secret from the transaction signatures. Now we can load it into a wallet to steal all the funds (try it!).

Elided Details

A few things need to note if you actually want to follow along at home:

TXIDs are binary consensus encoded.
It's not quite true that you need to solve for $D_{1}$ and $D_{2}$ . You might need to solve for $- D_{1}$ and/or $- D_{2}$ instead. This is because we don't know the original $R_{1}$ or $R_{2}$ the malcicious device used to encode the data, since they have their y-coordinate dropped.