Topic: Why are transaction malleable in the first place? (Read 3248 times)

Thank you very much for the code and I will look into adding "libsecp256k1" to my project (added to the "to do" list).

Canonicalization is not sufficient to eliminate malleability; and some forms of malleability are very useful. intentional, features-- like the ability to construct anyone-can-pay transactions.

They shouldn't be malleable; lack of canonicalization was an oversight.

It can be done using OpenSSL,

The code from Bitcoin core for this-- back when it used OpenSSL for signing:

        BN_CTX *ctx = BN_CTX_new();
        BN_CTX_start(ctx);
        const EC_GROUP *group = EC_KEY_get0_group(pkey);
        BIGNUM *order = BN_CTX_get(ctx);
        BIGNUM *halforder = BN_CTX_get(ctx);
        EC_GROUP_get_order(group, order, ctx);
        BN_rshift1(halforder, order);
        if (BN_cmp(sig->s, halforder) > 0) {
            // enforce low S values, by negating the value (modulo the order) if above order/2.
             BN_sub(sig->s, order, sig->s);
         }
        BN_CTX_end(ctx);
        BN_CTX_free(ctx);


(You might also want to look to using libsecp256k1 for signing in the future, not only does it handle this for you, it is sidechannel attack resistant and OpenSSL is not for this curve, it's also likely much better tested code than OpenSSL for this particular application.)

Good luck. 

It would be an easier sell, and a better product,  if the device just signed a message created elsewhere, displaying what it's signing and using deterministic R values if its trusted computing base has a minimal display/keyboard like Trezor.  Less code to inspect for funny business that might leak keys. Purely deterministic operation once past master private key generation, making it possible for a computer attached to the device to audit signatures to ensure that they are as expected.  I believe this would stop any random leakage by the device associated with its signatures, but obviously this requires that the wallet software in the associated computer do paranoid checking and that the checking hasn't been subverted.  (For best security it is important that the operational code be paranoid, so that it can deter probabilistic attacks keyed off of values in the signatures which may have been selected by some combination of pre-computation and social engineering.)

Although the CIYAM Wallet is not currently being used (except for testing by myself) I am wondering if I could get some help to change my ECDSA signing (assuming it isn't correct).

The code is here: https://github.com/ciyam/ciyam/blob/master/src/crypto_keys.cpp#L511

I'd appreciate a link to let me know how to fix it if it isn't right.

(can it be done using OpenSSL or do I need to include the Bitcoin ECDSA code to get it right?)

Thanks for your reply.

Absolutely, though its worth noting that while canonical encodings like DER are known and specified, virtually nothing enforces them. Bitcoin, from day one, has used a canonical encoding (DER)-- unfortunately, the underlying implementation in OpenSSL had undocumented behavior where it also accepted invalid DER until a couple months ago. (likewise, (all?) other similar libraries, such as bouncy castle behaved likewise-- this wouldn't have been escaped by not using OpenSSL). I spent some amount of time looking for precise DER implementations and BER implementations for reference test points in libsecp256k1 and was unable to find _any_ open source software which precisely implemented (no more accepted or rejected than specified) them. Even OpenSSL's recent fix for their behavior was not to correct their parser but instead to attempt to round-trip the encoding, which is not a guarantee. (You can see this list for some of the crazy things the OpenSSL parser, as an example, would accept.).

(And FWIW, the whole Bitcoin network has filtered these encodings everywhere for several years,  even though it required quite some wallets (like Armory and MTGOX) change their behavior).

But that deals with serialization, I am aware of no evidence that anyone has observed the algebraic malleability of ECDSA prior to us, and no evidence that anyone else took any action against it (now or previously).

As far as leaving serialization elements out of protocols, great care must be taken there too as there have been many vulnerabilities created by leaving things out. For example, the original PGP fingerprints hashed the modulus and exponent (but not their potentially non-canonical serialization), but also as a result had no delimitation so someone could move some bytes of your modulus into the exponent until they found a key they could factor, and then they'd have a weak key with the same fingerprint as you.

Signatures being covered under identifying hashes is ubiquitous, e.g. x509 certificate chains work just like bitcoin in this respect; and this interacts poorly with cert blacklisting due to malleability.

In any case, I don't want to belabor this, but you were really harsh and critical where I think the reality is almost 180 degrees out:  Bitcoin suffered from undocumented behavior in third party code; the outside world while somewhat aware of problems from non-canonicality has largely not acted on it-- Bitcoin Core is a leader in responsive and responsible handling of this, and our efforts resulted in the discovery of an additional form which appears to have not been known/discussed previously), which our ecosystem (out of all the ECDSA users in the world) appears to be the only ones at all protected against.

I really don't care much what armchair jockies on the forums (not specifically referring to you) think, and so I don't usually expend a lot of resources bragging... but to have someone be really harsh on a matter where I think our response has shown considerable innovation and leadership is, at least a little, bit frustrating!

It is unclear what you mean by "would not be significant", but the matter is largely orthogonal-- 6979 or not, implementations that do not heed the lowS behavior specifically will produce non-lowS signatures at a half the time per signature, leading to most of their transactions being blocked.  No wallet that I'm aware of has ever provided a "resign" button that might break through-- and when wallets do create new transactions they usually use a new random selection of coins, so 6979 would also produce a new signature. Even if they did provide a "resign" and used a random signature, once your transaction has more than a couple inputs the probability that it would pass a lowS test becomes very very low.

RFC6979 does not really close a covert channel either, alas, it is impossible to determine if a device is using 6979 without access to its keys and a malicious device could use 6979 99.99% of the time but then sometimes change to a kleptographic method (perhaps triggered by the message itself).   The RFC does eliminate the strong need for a good RNG at signing time --  a common implementation problem-- and make review/auditing somewhat easier.


Unfortunately if the device has free choice of its nonce (which having control of low/high S implies) then it has a high bandwidth covert channel.  E.g. produce the nonce as H(ECDH(attacker_pubkey, pubkey) || message_to_be_signed). More elaborate versions of this allow the embedding of additional data, beyond just leaking the current private key. Even if something constrains the choice of nonce, a malicious device can do rejection sampling to turn get N bits of covert channel out of the nonce by doing 2^n computation-- low vs high isn't different except by being computationally cheaper to use.   So, I'm not sure I'll be able to sell it in terms of covert channel suppression, but it's worth a try. Thanks for the suggestion.

Sorry, I thought your earlier question was just for didactic purposes.

One standard issue in cryptography that I was alluding to was the necessity of having canonical forms, so that signatures (which use hash functions) work properly after a message is mangled by the network.  This problem was obvious when encrypting messages sent over email, e.g. PGP and PEM (early 1990's). Another standard (but more subtle) issue is the opportunity for covert channels, which need only be low bandwidth before they can effectively leak a private key.  Thus an experienced cryptographer would have understood there might be a problem and could have looked for it. Indeed, in the case of bitcoin the problem was noted back in October 2012, as I pointed out in an earlier post.

The unique problem in bitcoin is that transaction identifiers depend on details of the signatures and that these identifiers are used as part of the protocol.  This is a bug in the bitcoin architecture. Without this bug, the low/high S issue would not have been of general consequence, making it unlikely there was anything in the open literature prior to bitcoin.  Also, the closing of a low/high-s covert channel would not be significant until deterministic signatures were used. In this regard, I note the date on RFC6979 is August 2013, which is after the bitcoin dev's were aware of the problem.

I did a little searching around to see if I could find a non-bitcoin example of the problem, but didn't find anything, probably for the reasons above.   This may not help you with regard to the HSM vendor, but as a customer of such a device I would not want to have an obvious potential covert channel, even if the output could be "fixed" by software in a nearby computer, since if the nearby computer could be trusted there would be no need for the HSM in the first place.  (Comment inapplicable if said HSM always outputs high-S.)

GMaxwell, also want to chime in with a thank you to you and all the core devs (and generally the community) doing a fantastic job.

tl121, I hear what you're saying regarding what looks like 'deer in headlights' syndrome but we have to keep in mind the 'core devs' are merely working on one branch of the open source project.  There is nothing stopping any of us, or more importantly the miners, enabling that option that I believe has been in bitcoincore for a long time.  People didn't simply because it wasn't an issue.

The adage "If it isn't broken, don't fix it" seems sensible when doing protocol work involving value, at least when the risk of a potential attack is merely a temporary inconvenience.  The fact that a historical fix was ready to be enabled should an attack happen seemed a very impressive bit of foresight.  Even if it hadn't existed, the protocol is robust enough that a fix could have been rolled out without doing long term harm to the network.

For bleeding edge or risky changes it seems sidechains are vastly more suitable while not risking the entire economy but perhaps I'm misguided?  I for one am impressed with the community's approach to progress so far.

I also find it great that someone demonstrated the malleability attack in a general way while the system is still young and not under pressure.

It's not users vs developers-- it's users vs users that are in question here.

In the case of the attack you cannot respend unconfirmed coins without issues while an attack is going on, in the case of lowS enforcement with half of your transactions will randomly get stuck (and never get unstuck, holding your coins hostage). Both are bad experiences for the user. I think the latter is considerably worse: any system's abstractions leak from time to time. Bitcoin isn't a system of "account balances", and for good reason. 99% of the time wallets can simulate that it is, but sometimes the fact that it isn't matters more (and even in ordinary use, the fact that it isn't has significant impacts on fees that can be worth the user's attention).

In the case of the former, it has been a non-issue until recently because no attack of this specific type was going on-- though, of course, we knew one could begin at any time (and immediately deployed all non-disruptive fixes);  in the case of the latter software was chaining over time-- but some users will just find that their preferred software just never gets updated for it; good luck sweeping their funds into another wallet with half (or more) the transactions getting stuck. Some users will try to install fixes but end up with malware instead and have their coins stolen, etc. While there was no attacks waiting for the migration to conforming to happen naturally was an approach which was intended to mitigate total disruption (and I believe it did)-- absent amaclin's demonstration it might have gone with virtually no disruption at all.

At every moment in this process we were thinking about protecting the user's experience and the value of the Bitcoin system to them-- from anticipating an issue no one had thought of before, to implementing, testing, reviewing, deploying fix code-- nagging other developers to fix their software, etc. All of these things took considerable work.  Simply saying "ah ha, today, this new rule is enforced due to this currently hypothetical attack: deal with it!" would have been much simpler.   Sometimes there is just a genuine conflict between different harms.

Thanks! it's good to hear comments like this.

The low-S, high-S issue was known to bitcoin developers over three years ago.  There was plenty of time to have fixed this a long time ago with an orderly phase-in.

Bouncing a transaction because a client is out of date would impinge on the reputation of the out-dated client.  It would not look to a new user of bitcoin as something flaky with the system as a whole.  It would not impinge on bitcoin as a whole, particularly if the "download" page on bitcoin.org had pulled the deprecated client from the list of bitcoin software.  This would not have been technically difficult to do.  The difficulty comes from the lack of Bitcoin governance and leadership and a focus on "code" and "nodes" more than on users and usage.

Well if they had changed that without informing and giving developers enough time to update their software to where almost everyone uses compliant code, then the network would essentially be DoS'ing itself. In your scenario, both transactions would have been "bounced" if they used High S, making it an even bigger inconvenience to users. That would have been a bigger perceived failure of the bitcoin system, not just the fact that someone can malleate their transactions and thus make spending from an unconfirmed transaction an even worse idea (given that it already is a bad idea).

That "mild" denial of service attack is likely to be perceived as a failure of the bitcoin system when it is experienced by a new bitcoin user.  This is particularly true if the sender makes two transactions in rapid succession from a balance of "old" coins, where the second transaction uses a change address from the first transaction.  This leads to counter-intuitive behavior, since the naive user believes he had all the necessary funds in hand, only to discover that the second transaction "bounces".

I suggest placing more emphasis on what bitcoin users experience, even if it means a little inconvenience for some developers.  

perfect moment to say: BIG THANK YOU for your continuous and well thought contributions and work on bitcoin core.
the core team has earned my trust over a long term and clearly deserves it (this includes other too).

(well i might disagree about blocksize but hey, i doubt there is anything in this world where anybody agrees with me)

I invite you to provide us with a hyperlink to a _single_ ECDSA implementation that dealt with ecdsa inherent malleability prior to Bitcoins existance (or our implementation of the fix in Bitcoin Core).

In one breath you say "mono culture is ecologically untenable", but yet you attack a strategy that is specifically constructed to be inclusive and avoid unnecessarily driving out implementations with fewer resources behind them out of the ecosystem.  You recognize that technically anyone could have fixed it, yet ignore your own completely failure to do so (or, seemingly, anything else productive in this context)-- in our case, we had a specific intention to preserve diversity in the ecosystem by not forcing updates on other implementations and their users, but you have no such excuse, arguing that it should have been done years ago. Remarkably, I find the seeming lack of logical consistency in your arguments more offensive your incivility.

Thank you for the link. I will bookmark it to read later. At least this malleability issue is more of a nuisance than a critical threat.

I'm sorry if I created the impression the problem would not have been solved if the core devs had done nothing.  That was not my intention.  I should have written more clearly.

Indeed,  if the core devs had not implemented a fix, they would have simply been bypassed. Perhaps this would even have been a good thing.  (I am one of the people who believes that multiple implementations of bitcoin are essential for its future growth and that the present mono culture is ecologically untenable.)

I have a better theory which does not involve leadership : warn, but let the system crash (if not systemic), and let it recovers by itself. (since it is the best interest of all participants)

You are wrong into thinking that if devs did not pulled out a new version it would not have been solved at all.

The technical problem is that a bitcoin transaction is identified by a transaction ID that is a hash that includes a digital signature.  The signature includes the solution of an  equation of the form Y^2 = x^3  + K*X + C.  If (Y, X) is a solution then so is (-Y, X) and no secret is needed to compute this alternative solution.  Unfortunately, the details (+Y or -Y) matter because they affect the transaction ID, which is used for various purposes in the bitcoin protocol and its software implementations.  This is a standard problem in cryptography and has a standard solution. In other words, it is a bug in the bitcoin protocol and implementation.  The bug and its obvious solution have been known to the bitcoin developers for over three years.

The actual problem has been that the "core" developers, while technically competent, have lacked the necessary leadership skills to act on their knowledge.  Instead they have been frozen with fear that they might inconvenience some bitcoin users and client developers by fixing the problem.  They have been acting like an animal caught in the headlights of an oncoming car, frozen with fear.

To their credit, these developers are technically competent and have deployed a fix to this problem at the last moment.  Next time there is a problem, however, the bitcoin community may not be so lucky, because technical competence is not sufficient.  Leadership skills are also required.  These include the ability to forsee potential problems, to chose an appropriate course of action, to persuade others to be followers and to accept the risks of failure by acting in a fearless fashion. 

Thanks. For anyone intersted, here is more reading on the subject, in the form of a BIP which attempts to address the alterable signature problem (among others): https://gist.github.com/sipa/8907691/67a2b9038aa37ad2f18eff6a8470253ae377456b