Why does steem use this canonical thing instead of strict secp256k1?

in #beyondbitcoin8 years ago (edited)

@baabeetaa and I hit this trying to make our blockchain interoperate with steemit. What this seems to show is that steems implementation of secp256k1 does not work like other implementations. We will not speculate on what this means for security here.

We had been talking API problems with steem. I was wrong. I never considered what @baabeetaa found today, which is that the problems are with encryption. It took him a great deal of work to confirm this.

https://docs.google.com/document/d/1X23vM6BJZRvu5vvp7ylxVfNiPQn034tDkiSGa76DfDE/edit?usp=sharing

I would have reported this privately as is the norm but have been deleted from steemit slack.

We thought it was an API problem. We thought it was an encryption problem. Both of these, because that's what they look like. And folks here deny it's a problem?

That's the problem guys. And the way it's handled is extra-baroque.

I'm installing Parity now to see how this is handled by Ethereum on @xeroc 's advice.
Update: It's handled differently, in a way that is more developer-friendly.

But hey, now we know about @bilthon83 's graphenej, that's cool.


So now I go off the cuff. Look, we tried, quite a bit, over quite a bit of time, to get this all working properly, and didn't. And I can see how it happened, and why. And I guess that's the root of issues here. I'm not going to go and say there's no issue, because there clearly is. It has to do with docs, and attitude, and support for a developer community. It seems to me that this is far more difficult and error-prone (both) than it needs to be. If you want to keep interfaces like this, fine. That's not my decision to make.

Don't be shocked after some time passes, and there's a second @faddat. And a third. And a fourth. And after a while, there'll have been a number of me's. I didn't do this to FUD. When I saw this it looked like a security threat and an insane way to use the tools at our disposal. We all looked at it, and that's what we saw, so we treated it as one. Look I get that it's early days for all things blockchain, but someone said to me yesterday:


...and I agree. It should be much easier to write tools that interface with graphene blockchains.

And I said to someone yesterday....


I'll stand by that, too. it reads like straight-up alien talk. This is what I mean:

And it's clearly not @xeroc's fault that it sounds like alien-talk, the procedure is bound to be, well, alien. I don't know of any other software interfaces that work even remotely like this one, and learning about this one definitely involved something that looked like, walked like, floated like and quacked like a security problem.

Here's another thing I said yesterday:

Thanks to everyone who helped us understand this futuristic method of doing things that involves adding 4 and 27 to stay compatible with other protocols. We'd surely never have guessed.

Sort:  

To be clear: I was wrong. I was also faced with something that looked exactly like a critical flaw in security.

More rotten eggs, more, throw more of them!

Here are your choices as I see them:

  1. Docs - This will enable you to make legit claims about your software's functionality. Today, most dismiss graphene out of hand because of its lack of docs. Don't believe me? I've been in the room and watched it happen. (And I was on the "pro-graphene" side in that particular room.)

  2. Keep throwin them eggs.

Those who do number one don't need to do number two.

Still not jumping to conclusions, but ... yeah.

https://github.com/steemit/steem/issues/1944

We should loosen the restriction in a HF. Because valid FC signatures are a subset of BIP-0062, after the hardfork we can clean up signature verification code and use BIP-0062 for historical verification.

This post has been edited for several times, little by little after people replied more and more. Now it looks totally different in comparison to the original one, and makes some replies looks strange. For more convenience for future readers, edit history of this post can be found here:
https://phist.steemdata.com/history?identifier=%40faddat%2Fsecp256k1-in-steem-doesn-t-adhere-to-standards

Here, to summarize:

I was wrong. What I saw was not what it looked like.

The API for steem still sucks/needs docs + tons of love.

My quick guess is that you're not taking into account how Graphene treats canonical signatures.

For reference, check xeroc's excellent post on transaction signing: https://steemit.com/steem/@xeroc/steem-transaction-signing-in-a-nutshell

Here's an extract:

Now, we are going to implement a loop that is crucial because the back-end only accepts canonical signatures and we have no way of knowing if the signature that is going to be produced will be canonical. That said we will derive a deterministic k parameter for the ECDSA signing and while generating this parameter will will add our loop counter to the digest before hashing. This results in a new deterministic k each round which will result in either a canonical or non-canonical signature.

I know a lot more about tendermint than I do graphene.

This could be the issue but I don't know, because well, if that is the case it doesn't seem real sensible. Thank you for your suggestion we will surely give this a try.

I reckon it's 99% certain this is the cause of your issue.

You may reckon right.

What do you think of the idea that this baroque chapter in the process should be simplified?

Hey rainman thanks for this explanation. Ill grab xeroc to bring further into this discussion. I hope this is the reason...cause when same input somehow = different output every time...it concerns me. Looks like i need to do some reading. Please stay in this discussion as u are already proving to be highly valuable.

This is at the core of the reasons why faddat and baabeetaa could not build the beyondbitcoin.io site ...and also stopped them from making it easy to crosspost to steem from their social "media hub" blockchain.

I believe signatures will be different every time and that is expected, since we're dealing with non-deterministic signatures here.

Anyways, xeroc'x post over there is how I managed to solve this in graphenej. The relevant part of the code is in here: https://github.com/kenCode-de/graphenej/blob/master/graphenej/src/main/java/de/bitsharesmunich/graphenej/Transaction.java#L142

Should it be simpler?

And thanks.

Steem community,

Can anyone really read that doc and not get the heebie jeebies about widening the attack surface?

I'm sorry, but it truly seems baroque. What happened to simple is beautiful?

And this is my honest advice: stop doing things that are done better, yourself. grpc is better than this for you and for developers. Capn'proto would also work.

You may proceed with the ritualistic throwing of eggs.

You are also encouraged to test the crap out of our chains security in the same fashion. Maybe, somehow we can all make this work. And it would be neat, because there's a lot we can offer each other, and this is me all "whoa, alright, cool, but totally that's not... What you might ever expect..."

If you really need sonething canonical you can try the rfc-compliant k and if the sig fail to be canonical .. you can increment k by one until you sig is canonical. Easy as that.

@xeroc

Your word carries a lot of weight with me, so please put it to me squarely:

Do you think this poses a threat to security?

How about usability?

Isn't it something that can be simplified a great deal?

If I'm off-base here, tell me so.

Just give up the FUDing already, we've explained why you had this issue. There is no security issue here, in fact it's a non issue that you're attempting to make a big deal out of.

If you weren't trying to FUD you would've just asked someone like xeroc who knows how this works and he would've explained it in 1 minute.

In fact, these more strict requirements make the system more secure.
You can realize that when you think about it from the information theoretical point of view. The requirement for r and s each being of length 32 means that the signature has to have a length of 64 (+1 for the pubkey recovery parameter). This requirement makes it impossible to leak information of the private key into the signature, no matter what you do.

As for not being deterministic, there actually is no requirement for it whatsoever. All that RFC6979 results in is a random k which is needed to prevent an easy derivation of k from two signatures (if the same k is used twice). This can be done by using RFC6979, or just some random timestamp. Being able to deterministically derive k has no other impact than making sure that k isn't reused. And for that reason, graphene (as well as most clients) implement RFC6979 and then permute the k if necessary.

@svk

Attitudes like that are a threat to security here. Hell, it's why I stopped using the site. Why is there this extreme anti-progress undercurrent around here?

Hey xeroc, regarding to Piston, is this still available?
There is a 'Lost connection to node' error message.

Dear @rainman
I can see you voted for witness arhag who doesn't have a working witness anymore since a long time.. I am new, dedicated and hoping to achieve dreams. Your vote can really really help me. I hope you would consider it.. https://steemit.com/witness-category/@rival/rival-week-2-steem-witness-update-thank-you-daretoask

To clarify why I mentioned "it" took me 2years to figure it out.

  • I did not work full time on this project but in my spare time whenever I felt like dealing with crypto and not with my thesis.
  • it actually is the whole python-library stack that not only does the signing but also the serialization. I wanted it to be as flexible as possible and that is why it took so long.

I fully comprehend the volume of work you had to do and that's entirely what I disagree with.

The ecosystem would be much larger if these things were less mysterious. Imagine that you'd been able to get it finished in a month-- imagine what you might've built then?

This has nothing to do with the secp256k1 implementation in use but rather with the canonicality check and the way k is derived and updated if canonicality isnt achieved.
libsecp256k1 even offers an optional API to overwrite how to deal with a deterministic k and tret it if necessary.

Why have you been deleted from the slack? Or are we just going to leave that dangling there?

That's all I know is that I can't access it anymore.

Maybe you should ask someone who has control of that slack, like @ned.

So I suppose it's just as dangling for me, as it is for you.

What do you know and when did you know it? We were all deleted from slack in August, 2016.

Actually, I was a member of the steem slack till sometime in Feb 2017.

Oh man. That sucks.

Indeed. We are all human and thus stupid and this is why they should write some doc's for graphene.

This is getting scary & ugly. Someone needs to do some explanation. Lets call for transparency.

Completely agree. This is some really, really strange stuff that we're being asked to do to interface with their code. I never expected that we'd find something that looks exactly like a security problem, and then find out that the solution is something that seems to actually weaken security through complexity and baroque style.

The trouble is that none of us knows. And that the signing docs are.... enormous. What is the purpose of all the complexity?

You are well aware, or should be, of [email protected].

Have I ever had anything to send there before?

Did I have a communications channel that got cut off?

Why should I be aware of this?

Aren't you happy I reported it instead of not?

Let's get down to brass tacks: who did your secp256k1 code for C++ and JavaScript?

Do you claim to be using canonical SECP256k1?

How about the non determinism?

We have run the ecc library we are using over the bitcoind test vectors, everything passes.

Cheers. I will now decline to pay your tantrum further attention. If you have any additional bug reports of a security nature, we now both know that you know both the professional as well as the attention-seeking routes to report them.

Good day.

Hi, so what is the purpose of all the complexity? Is it optimization? Because it looks like alien-speak to me. And I know it, I'm an idiot. Thing is just about everyone is.

So complexity like this is going to harm this site and its community in the long run.

Please be encouraged to test our software in the same manner and report in the same manner as strident and loud as you'd like. We'd rather that than have security issues effect our users. Really, you're encouraged.

Further, we'd love to talk with you about safely interoperating. There's a lot of room to grow guys. I mean, a lot. So shall we grow?

Odd that my account on your slack got deleted after I posted about interoperating. That was my last post of course, but I can't know why it was deleted. Maybe it's because I'd mention something like this. Maybe it's because I'd like my software to work with yours. Maybe it's because you folks are gun-shy and paranoid. Maybe it's because I'm too loud and push too hard.

That's the trouble, as always: I can't know.

Hope the next time someone hits something that looks like a security problem, they report it, too. Your approach won't help much.

Generally they do, as it says right in our readme how to email us. You are the first and only one thus far to take the public tantrum approach.

Damn. I am such an asshole.

I am glad u brought this to the blockchain though i will "speculate" that given what ive seen it does look like the cryptography has been tampered with or is at least different from what it seems it should be.

Trouble with stuff like this is that it's really hard to pin down what may be the cause. It does not seem like they are using the canonical secp256k1. @baabeetaa and I are happy to speak with anyone about exactly how we ended up finding it. @baabeetaa suggests creating RPC libraries.

Well i will be actively trying to help you all get to the bottom of this. I really do remember bytemaster (aka dan larimer) saying graphene using deterministic signature scheme...but that was awhile ago and was before Steem existed. So i might be completely wrong.

Im just thankful that it wasnt something worse than this. I was a bit concerned what this could mean...

Thank you fuzzy. My total assessment is that I don't know. Thing is I or anyone should be able to know. Hell, you should be able to know, even as you say as a "code-idiot".

I wouldnt calt it tampering but simply being more strict. That is evetything there is to see. Graphene simply doesnt accept every signature that is valid for other chains but requires additional properties to be fulfilled. Namely r and s need to be of lenght 32. No way around it and the only possible way to achieve such a property for any message is to pick a deterministic k and add a random part to it and try with another sig.

Tale a look at how canonicality is done in ethereum. You will be surprised.

@xeroc,

Looking.

This? And the few other related bits across their code?

https://github.com/ethereum/go-ethereum/blob/6d15d00ac4b5f162737a27dfa6f8e9976383776e/accounts/abi/event.go

Yes, it looks a good deal simpler.

@xeroc

Thinking about how to approach this to see if I am FUD-ing or not, I'm installing Parity, the leading ethereum client, and I'll compare to the same steps on graphene.

If your serialization expects a 65byte signature and you only provide 63 byte .. then it needs to either perform running length encoding or do zero padding. The former leads to additional data on the serialization while the latter leaves you with meaningless bytes in the serialization that can be used to hide information (e.g. leakage of private key data) -- this is particularilly a concern for hardware wallets where you don't see what code is actually executed.

That said, restricting signatures to 65bytes is easiest with respect to security, scalability and network efficiency.

You are actually right, the canonicality of eth signatures does not require a loop, but they need to deal with signatures that are (maybe) shorter than 64bytes. How they deal with it is their decision to make. Graphene architects made the decision to not allow shorter signatures and there are good reasons to do so: backend performance, information leakage, consistency, etc..

How is it possible to optimize for back-end performance without potentially leaking information?

Also, doesn't a variable key length improve the situation overall and reflect a more standard implementation?