SDC deanonymization

[othexmr]

read the following from shen (Monero Research Lab): https://shnoe.wordpress.com/2016/02/11/de-anonymizing-shadowcash-and-oz-coin/

There is no way to contact you on the bug bounty program, thats why we had to do it here.
If this is serious: https://shadowproject.io/en/bounties you have to add a contact form there.

You can reach shen here: https://github.com/ShenNoether or via his email.

Edit: alright, theres an email with grey text on grey background...anyway doesn´t matter now.

[ghost]

I just sent an e-mail. I can be reached at shen.noether@gmx.com I would love to get a bounty!

[rynomster]

Thank's Shen, I don't know who controls the bounties, or who funds it. I will find out from the team

[ghost]

Thanks!

On 2/11/2016 2:50 AM, Ryno wrote:

That's Shen, I don't know who controls the bounties, or who funds it.
I will find out from the team

—
Reply to this email directly or view it on GitHub
#25 (comment).

[kewde]

@ShenNoether
I'm not a cryptographer, nor an expert in mathematics but I feel somewhat comfortable with the basics.

I took a quick dive into the source to inspect it a bit further and found something that may interfere with what has been previously claimed.

hG = EC_POINT_new(ecGrp)

The generator for the keyImage seems to be a random new EC point, indeed public key is the secret * generator but if the generator is a new random EC point then that wouldn't result in the public key.

[ghost]

@kewde- look at their comment in the function hash to EC:
// - bn(hash(data)) * G

here is the relevant code:
https://gist.github.com/ShenNoether/3686113566bc23bf836f

You are correct that if they took a completely new point, whose log is unknown, then it wouldn't be a problem. However, it is possible I am misinterpreting their code (as I am not completely familiar with it)

See also this comment:
// - keyImage = secret * hash(publicKey) * G

[kewde]

@ShenNoether

That's the code I've been going through, thank you for that by the way, makes it a lot more easy.

Anyways, just to make my findings more clear for everyone, I'll be writing it out by the lines.
In document found here:
https://gist.github.com/ShenNoether/3686113566bc23bf836f

Line 42: if (!(hG = EC_POINT_new(ecGrp))) //generates new generator.
Line: 48: if (hashToEC(&publicKey[0], publicKey.size(), bnTmp, hG) != 0) //passes new hG to hashToEC.

Which should result in the usage of a new point if the code strictly does what's described here:
Line 8: // - bn(hash(data)) * G

I've only looked over the code superficially, the math in your post is in fact correct but I'm doubting it's applicability to Shadow because of the random hG.

"You are correct that if they took a completely new point, whose log is unknown"
I don't know if hG = EC_POINT_new(ecGrp) would confirm with those requirements or not.

[ghost]

@kewde, ok so you would have to convince me that hG indeed returns a new point, and not a randomly generated new point every time (since it has to agree for the verifier), thus it must return a "fixed" new point. Thus why are they checking if it's a point? They would only need to check once (in testing).

[ghost]

@kewde, compare this code in their public key generation code:
// Generate a private key from just the secret parameter
int EC_KEY_regenerate_key(EC_KEY *eckey, BIGNUM *priv_key)
{
int ok = 0;
BN_CTX *ctx = NULL;
EC_POINT *pub_key = NULL;

if (!eckey) return 0;

const EC_GROUP *group = EC_KEY_get0_group(eckey);

if ((ctx = BN_CTX_new()) == NULL)
    goto err;

pub_key = EC_POINT_new(group);

if (pub_key == NULL)
    goto err;

if (!EC_POINT_mul(group, pub_key, priv_key, NULL, NULL, ctx))
    goto err;

[kewde]

I'm a bit confused by what you wrote, are you referencing to the if-check on line 42?
EC_POINT_new can return NULL, so they're setting hG to the value of EC_POINT_new first and then checking that the value in fact exists on line 42.

I'll be going out to grab some food, I'll be keeping an eye on this discussion as it evolves.
Thank you for reporting possible bugs and great work on the RingCT paper by the way.

[ghost]

@kewde, what I'm point out is 2 things: 1 Due to the way the sigs work, they can't just generate a new random point for the hashing every time (that would break verification). Although they could fix "one" alternative basepoint, and always use that. 2 They seem to be calling the same function when they get their pubkeys, which shows that it should in fact be the same basepoint.

[kewde]

@ShenNoether The function of discussion is part of the OpenSSL libraries which are quite generic libraries so the basepoints can be different based on which functions were called that precede the one in question. But then again I'm not very familiar with the OpenSSL libraries and their functions, but if one group is used (in EC_POINT_new(group)) for the verification of the signature, and a seperate one is used for the key generation, you'd end up with two alternative basepoints IIRC.

I'll leave it in the middle if Shadow does that or not, as I don't have the time to go through the source anymore.

[ghost]

@kewde if you look at where hashToEc is called for the initial L = aG and R = aH, you will see that they use the same ecGrp variable for their input to "new point" (thus the state to hashToEc) at each time. This is lines 275-297 here https://github.com/shadowproject/shadow/blob/master/src/ringsig.cpp

[ghost]

Proof:
https://raw.githubusercontent.com/ShenNoether/Deanon/master/sdcDeAnon.txt
Try yourself using the basic instructions here:
https://github.com/ShenNoether/Deanon

[kewde]

@ShenNoether
I also had been working on a reworked ringsig function and I too came to the conclusion that it's feasible.

I assume one way of fixing it is using a different hash algo, and another one being a different ec group with a different generator.

[gratefulcheddar]

@ShenNoether
Forgive me, I'm a noob trying to wrap my head around all of this.
What are the implications of this bug besides revealing a public key being added to the UTXO pool?

[ghost]

@timthomascode The bug reduces the anonymity to that of merely having stealth addresses, which isn't much better for privacy than bitcoin itself (used with best practice).

[rynomster]

It allows you to see which pubkey's secret key signed the transaction. It effectively makes our ringsignature implementation as private as normal stealth address transactions.

[kewde]

@ShenNoether

Monero used a different hash algo to fix this issue, but would a different generator (for HashToEC) also solve this bug? Secret * G would not be the public key anymore, but I have no idea if you can just pick a new gen and assume all points will be on the curve.

[ghost]

@kewde It would be nice to get some of that bounty before I point you guys in the right direction :) I would accept 2/3 payment if it's in btc instead of sdc.1APHPNctT1Lx3rqNsMuAMrGBNfcAD7aVuL

[kewde]

@ShenNoether
I get that, I'm not in charge of bounties but I've seen people donating towards the bounty fund, so it's being prepped as we speak. As I understand it, the payout was being made in SDC but may be partially Bitcoin, no idea!

Anyways, I want to thank you for the disclosure, unlike some parts of the Monero community, you've been really nice to work with.

I think fixing an alternative basepoint will work, but in any case we'll have to abandon the pool of current tokens :(

[SativaL]

hey all,
as me as a non dev and non team member of sdc but a believer. We should pay the bounty out via btc to gain back honesty and fix the bug. Im very thankful to Shen. That he found this flaw and hope we can go back developing the market with a secure privacy system as we did before.

Its only in my interest and many other Privacy and Freedom believers that we continue working together instead of fighting against each other for greediness.

Thank you all, have a great day !

[ghost]

@kewde @SativaL I was notified of this blog-post: https://blog.shadowproject.io/2016/02/14/all-is-not-lost/ in which they state payment will be in sdc.
Here is an sdc address where I can receive funds
SfKb88kc2P69jNXbMSxh2hPYS7dFjuWQNf
if you could redirect the payer here, since I have not received a response to my original e-mail, that would be much appreciated.

[AllienWorks]

@ShenNoether don't worry, it's all in the process. Thanks for posting your SDC address. You'll receive your bounty, we can assure you.

[rynomster]

@ShenNoether, I just want to confirm, can I send to SfKb88kc2P69jNXbMSxh2hPYS7dFjuWQNf?

[ghost]

Received bounty! Much appreciated. In answer to @kewde

Monero used a different hash algo to fix this issue, but would a different generator (for HashToEC) also solve this bug? Secret * G would not be the public key anymore, but I have no idea if you can just pick a new gen and assume all points will be on the curve.

It seems to me that using another generator so that you can't solve for the key-image anymore should solve the bug - however - I have not seen it done this way for whatever reason (possibly because if your other point is compromised then you again lose anonymity). The typical way to do it is something like I've written out here:
https://github.com/ShenNoether/ge_fromfe_writeup
(There are a few references in the intro with different algo's you could try as well, since obviously sdc is based on a different curve).
Best,
Shen

[ghost]

Note that secp256k1, which I think you are using is only marked as "somewhat rigid" https://safecurves.cr.yp.to/rigid.html so, although you are probably safe, it's maybe a tiny bit more risky to hinge all your anonymity on a single point - I'm not certain how serious that list is, but I would guess "somewhat rigid" is fine.

[kewde]

Hi @ShenNoether
We were fiddling with the code and tried something out to mitigate the bug using a different generator.
For practical programming reasons we inverted the base point using EC_POINT_invert() and then used EC_GROUP_set_generator() to set the generator.

Now I'm thinking that this is probably a bad approach because it could allow someone to invert the keyImage EC point and then still be able to perform the attack because elliptic curves have symmetry.

But I'm not sure about that, so I'll be writing a PoC to test that soon but I wanted your input on the matter.

[ghost]

If EC_POINT_invert just returns -1 * G, then no, that will not work.
Best,
Shen

On 2/16/2016 8:16 AM, kewde wrote:

Hi @ShenNoether https://github.com/ShenNoether
We were fiddling with the code and tried something out to mitigate the
bug using a different generator.
For practical programming reasons we inverted the base point using
EC_POINT_invert() and then used EC_GROUP_set_generator() to set the
generator.

Now I'm thinking that this is probably a bad approach because it could
allow someone to invert the keyImage EC point and then still be able
to perform the attack because elliptic curves have symmetry.

But I'm not sure about that, so I'll be writing a PoC to test that
soon but I wanted your input on the matter.

—
Reply to this email directly or view it on GitHub
#25 (comment).

[kewde]

@ShenNoether
Do you think the following could a safe solution?
keyImage = secret * secret * (hash * G)?

I've noticed that messing with the generator could create some caveats, it has to be picked at random and is not allowed to have any relationship to the previous existing basepoint, especially no multiplication else another vulnerability could be created.

[GnstheGrain]

@ShenNoether @LiteBit @sdcdev
Any update on that deanonymization ?

[rynomster]

We paid @ShenNoether the bounty, and he directed us towards a fix :) We've implemented the fix on the v1.3.4 branch and it's currently in testing. It's not fully deanonymized, but it's down to the same privacy that stealth addresses provide

[GnstheGrain]

Great news, thanks