Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: Nicolas Dorier on October 10, 2015, 09:32:40 AM



Title: Malleability counter attack : Malleate to LowS instead of dropping HighS
Post by: Nicolas Dorier on October 10, 2015, 09:32:40 AM
I think that modifying any incoming transaction with Bitcoin core to enforce LowS would be better than just blocking HighS.

I am even tempted to code a fake node who does exactly that. Do you think it would help ?


Title: Re: Malleability counter attack : Malleate to LowS instead of dropping HighS
Post by: achow101 on October 10, 2015, 03:48:53 PM
I don't know if it would help, but someone already created a version of bitcoin core which malleates high s to low s.
convo in irc: http://bitcoinstats.com/irc/bitcoin-dev/logs/2015/10/08#l1444332212.0
github repo https://github.com/TheBlueMatt/bitcoin/tree/seed


Title: Re: Malleability counter attack : Malleate to LowS instead of dropping HighS
Post by: dexX7 on October 11, 2015, 02:23:35 PM
I had the idea in the New transaction malleability attack wave? Another stresstest? (https://bitcointalk.org/index.php?topic=1198032.msg12611204#msg12611204) thread, and gmaxwell mentioned something similar in Bitcoin Core pull request #6769 (https://github.com/bitcoin/bitcoin/pull/6769) (not sure, if related). TheBlueMatt then created the patch (https://github.com/bitcoin/bitcoin/compare/master...TheBlueMatt:seed), so this is definitely already ongoing. :)

Mutating high S to low S and rejecting high S is complementary, and the active mutation serves two goals:

- reducing the rate of actually rejected transactions (once the updated policy is deployed widely)
- potentially flushing out implementations, which create non-canonical signatures (by checking, which users complain about mutations etc.)


Title: Re: Malleability counter attack : Malleate to LowS instead of dropping HighS
Post by: Nicolas Dorier on October 14, 2015, 05:16:15 PM
For information I am running this program on my node :

Code:
using NBitcoin;
using NBitcoin.Protocol;
using NBitcoin.Protocol.Behaviors;
using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication3
{
class Program
{
class Behavior : NodeBehavior
{
protected override void AttachCore()
{
AttachedNode.MessageReceived += AttachedNode_MessageReceived;
}


ConcurrentDictionary<uint256, Transaction> _Transactions = new ConcurrentDictionary<uint256, Transaction>();

void AttachedNode_MessageReceived(Node node, IncomingMessage message)
{
var inv = message.Message.Payload as InvPayload;
if(inv != null)
{
node.SendMessageAsync(new GetDataPayload(inv.ToArray()));
}
var tx = message.Message.Payload as TxPayload;
if(tx != null)
{
bool mutated = false;
foreach(var txin in tx.Object.Inputs)
{
List<Op> ops = new List<Op>();
foreach(var op in txin.ScriptSig.ToOps())
{
if(op.PushData != null && IsValidSignatureEncoding(op.PushData))
{
TransactionSignature sig = new TransactionSignature(op.PushData);
if(!sig.IsLowS)
mutated = true;
ops.Add(Op.GetPushOp(sig.MakeCanonical().ToBytes()));
}
else
{
ops.Add(op);
}
}
txin.ScriptSig = new Script(ops.ToArray());
}
if(mutated)
{
if(_Transactions.TryAdd(tx.Object.GetHash(), tx.Object))
{
SendMessageAsync(new InvPayload(tx.Object));
}
}
}

var data = message.Message.Payload as GetDataPayload;
if(data != null)
{
foreach(var inventory in data.Inventory)
{
var txx = _Transactions.TryGet(inventory.Hash);
node.SendMessageAsync(new TxPayload(txx));
Console.WriteLine("Broadcasted : " + inventory.Hash);
}
}
var reject = message.Message.Payload as RejectPayload;
if(reject != null)
{
Console.WriteLine("Reject " + reject.Hash + " for " + reject.Reason);
}
if(_Transactions.Count > 1000)
_Transactions.Clear();
}

private void SendMessageAsync(InvPayload invPayload)
{
var group = NodesGroup.GetNodeGroup(AttachedNode);
foreach(var node in group.ConnectedNodes.Where(n => n != AttachedNode))
{
node.SendMessageAsync(invPayload);
}
}
public override object Clone()
{
return new Behavior(_Transactions);
}
public Behavior()
{

}
protected override void DetachCore()
{
AttachedNode.MessageReceived -= AttachedNode_MessageReceived;
}

public Behavior(ConcurrentDictionary<uint256, Transaction> tx)
{
this._Transactions = tx;
}
}
static void Main(string[] args)
{
new Program().Run();
}

private void Run()
{
var parameters = new NodeConnectionParameters();
parameters.TemplateBehaviors.Add(new Behavior());
var group = new NodesGroup(Network.Main, parameters);
group.MaximumNodeConnection = 10;
group.Connect();
_Group = group;
_Group.ConnectedNodes.Added += ConnectedNodes_Added;
_Group.ConnectedNodes.Removed += ConnectedNodes_Added;
Console.ReadLine();
}

void ConnectedNodes_Added(object sender, NodeEventArgs e)
{
Console.WriteLine("Connected : " + _Group.ConnectedNodes.Count);
}

NodesGroup _Group;




public static bool IsValidSignatureEncoding(byte[] sig)
{
// Format: 0x30 [total-length] 0x02 [R-length] [R] 0x02 [S-length] [S] [sighash]
// * total-length: 1-byte length descriptor of everything that follows,
//   excluding the sighash byte.
// * R-length: 1-byte length descriptor of the R value that follows.
// * R: arbitrary-length big-endian encoded R value. It must use the shortest
//   possible encoding for a positive integers (which means no null bytes at
//   the start, except a single one when the next byte has its highest bit set).
// * S-length: 1-byte length descriptor of the S value that follows.
// * S: arbitrary-length big-endian encoded S value. The same rules apply.
// * sighash: 1-byte value indicating what data is hashed (not part of the DER
//   signature)

var signLen = sig.Length;

// Minimum and maximum size constraints.
if(signLen < 9 || signLen > 73)
return false;

// A signature is of type 0x30 (compound).
if(sig[0] != 0x30)
return false;

// Make sure the length covers the entire signature.
if(sig[1] != signLen - 3)
return false;

// Extract the length of the R element.
uint lenR = sig[3];

// Make sure the length of the S element is still inside the signature.
if(5 + lenR >= signLen)
return false;

// Extract the length of the S element.
uint lenS = sig[5 + lenR];

// Verify that the length of the signature matches the sum of the length
// of the elements.
if((lenR + lenS + 7) != signLen)
return false;

// Check whether the R element is an integer.
if(sig[2] != 0x02)
return false;

// Zero-length integers are not allowed for R.
if(lenR == 0)
return false;

// Negative numbers are not allowed for R.
if((sig[4] & 0x80) != 0)
return false;

// Null bytes at the start of R are not allowed, unless R would
// otherwise be interpreted as a negative number.
if(lenR > 1 && (sig[4] == 0x00) && (sig[5] & 0x80) == 0)
return false;

// Check whether the S element is an integer.
if(sig[lenR + 4] != 0x02)
return false;

// Zero-length integers are not allowed for S.
if(lenS == 0)
return false;

// Negative numbers are not allowed for S.
if((sig[lenR + 6] & 0x80) != 0)
return false;

// Null bytes at the start of S are not allowed, unless S would otherwise be
// interpreted as a negative number.
if(lenS > 1 && (sig[lenR + 6] == 0x00) && (sig[lenR + 7] & 0x80) == 0)
return false;

return true;
}
}
}

Let me know if anyone think it is better I stop it.


Title: Re: Malleability counter attack : Malleate to LowS instead of dropping HighS
Post by: mezzomix on October 15, 2015, 07:18:46 AM
It's good enough if one node is modifying high S transactions to low S. There is no need to change the implementation for everyone.


Title: Re: Malleability counter attack : Malleate to LowS instead of dropping HighS
Post by: BitcoinNewsMagazine on October 15, 2015, 10:55:37 AM
New Bitcoin Core release 0.11.1 (https://bitcoin.org/en/release/v0.11.1) obviates the problem by mandating LowS.


Title: Re: Malleability counter attack : Malleate to LowS instead of dropping HighS
Post by: Nicolas Dorier on October 15, 2015, 12:40:16 PM
I'll keep my program running 1 or 2 weeks the time of miners to update. I'm not alone to do it, but it does not hurt.


Title: Re: Malleability counter attack : Malleate to LowS instead of dropping HighS
Post by: Nicolas Dorier on October 15, 2015, 12:59:45 PM
I am kind of surprised, very few transactions are LowS malleated. Nodes to which I connect always ask me to send the payload...
I thought I was not alone oO

Or maybe the HighS already reached all the other node so the LowS version is always ignored...


Title: Re: Malleability counter attack : Malleate to LowS instead of dropping HighS
Post by: dexX7 on October 15, 2015, 01:51:14 PM
New Bitcoin Core release 0.11.1 (https://bitcoin.org/en/release/v0.11.1) obviates the problem by mandating LowS.

This is a very good thing, nevertheless, I'd consider high S -> low S mutation as complementary measure, because a) there are nodes out there, which don't use the new policy, b) and miners, and c) wallet implementations.

Note that the policy rejects high S, which may result in legit transactions getting dropped, which is probably not a favorable outcome.

I am kind of surprised, very few transactions are LowS malleated. Nodes to which I connect always ask me to send the payload...
I thought I was not alone oO

Or maybe the HighS already reached all the other node so the LowS version is always ignored...

I'm running the "seed" branch, and I see many log entries indicating high S -> low S mutations from my node.


Title: Re: Malleability counter attack : Malleate to LowS instead of dropping HighS
Post by: Nicolas Dorier on October 15, 2015, 02:10:23 PM
Quote
I'm running the "seed" branch, and I see many log entries indicating high S -> low S mutations from my node.

I was kind of surprised, because everytimes I send "inv" a transaction, no node seems to know it and all ask the payload.

By the way, I can craft a special scriptPubKey to make mutator banned from network and get IP of people who mutate transactions to HighS, would it be useful ? does the malleability attack on right now ?

Craft a redeem script "<DerHighS> OP_EQUALVERIFY", spend it. The mutator will create an invalid transaction which will ban him from the network. Now, you look in your banlist and collect the IP.


Title: Re: Malleability counter attack : Malleate to LowS instead of dropping HighS
Post by: amaclin on October 15, 2015, 04:07:10 PM
I was kind of surprised, because everytimes I send "inv" a transaction, no node seems to know it and all ask the payload.
You are the only person who modify transactions today. My bot is paused for a long time.

Craft a redeem script "<DerHighS> OP_EQUALVERIFY", spend it.
This is non-standard script. Your peers will ignore this tx. Miners should ignore it also even get this tx.


Title: Re: Malleability counter attack : Malleate to LowS instead of dropping HighS
Post by: Nicolas Dorier on October 15, 2015, 04:10:50 PM
Craft a redeem script "<DerHighS> OP_EQUALVERIFY", spend it.
This is non-standard script. Your peers will ignore it. Miners should ignore it also even get this tx.

No, arbitrary redeem script are standard since 0.10.


Title: Re: Malleability counter attack : Malleate to LowS instead of dropping HighS
Post by: amaclin on October 15, 2015, 04:27:53 PM
No, arbitrary redeem script are standard since 0.10.
This is not true.

Look to this transaction:
https://blockchain.info/tx/6f1da8a16b067110be35690ca31dc6e483dcf908e83acfa44308bb03c70e3567
It has "arbitrary redeem script" (note: bc.i parses it incorrect)
But it is non-standard and there is no miner today who can confirm it.


Title: Re: Malleability counter attack : Malleate to LowS instead of dropping HighS
Post by: Nicolas Dorier on October 15, 2015, 05:24:48 PM
Quote
(note: bc.i parses it incorrect)
Yes, bc.i does not accept OP_RETURN either.
Quote
But it is non-standard and there is no miner today who can confirm it.
Nop.
Standard script rules relaxed for P2SH addresses (https://github.com/bitcoin/bitcoin/blob/047a89831760ff124740fe9f58411d57ee087078/doc/release-notes.md)

Too lazy to find the exact commit though. :p


Title: Re: Malleability counter attack : Malleate to LowS instead of dropping HighS
Post by: Nicolas Dorier on October 15, 2015, 05:29:41 PM
Also, the transaction you show me is not P2SH. The term "redeem script" always implies P2SH.


Title: Re: Malleability counter attack : Malleate to LowS instead of dropping HighS
Post by: amaclin on October 15, 2015, 09:27:37 PM
Also, the transaction you show me is not P2SH. The term "redeem script" always implies P2SH.
Wat?


Title: Re: Malleability counter attack : Malleate to LowS instead of dropping HighS
Post by: Nicolas Dorier on October 16, 2015, 04:26:47 AM
Redeem Script as described here. (https://github.com/bitcoin/bips/blob/master/bip-0016.mediawiki)


Title: Re: Malleability counter attack : Malleate to LowS instead of dropping HighS
Post by: Nicolas Dorier on October 17, 2015, 12:28:11 PM
For information, my node which is currently malleating HighS to LowS detects around 2 and 4% of HighS signatures.


Title: Re: Malleability counter attack : Malleate to LowS instead of dropping HighS
Post by: amaclin on October 18, 2015, 11:08:40 AM
Craft a redeem script "<DerHighS> OP_EQUALVERIFY", spend it. The mutator will create an invalid transaction which will ban him from the network. Now, you look in your banlist and collect the IP.

For information, my node which is currently malleating HighS to LowS detects around 2 and 4% of HighS signatures.

What if the inner p2sh (redeem) script is the

OP_2DUP OP_EQUAL OP_IF OP_RETURN OP_ENDIF OP_2 <pubkey> <samepubkey> OP_2 OP_CHECKMULTISIG

and the scriptSig is
OP_0 <signature> <malledsignature> <redeemScript>


Title: Re: Malleability counter attack : Malleate to LowS instead of dropping HighS
Post by: dexX7 on October 18, 2015, 04:25:07 PM
For information, my node which is currently malleating HighS to LowS detects around 2 and 4% of HighS signatures.

I started to track the numbers earlier the day, and I currently see about 3.5 %.

It would be interesting to know at which percentage the mutated transactions are mined. Did you gather some stats about this already?

Recently, these are the mutations I've seen: http://bitwatch.co/uploads/mutations-2015-10-18.log (not 100 % online)


Title: Re: Malleability counter attack : Malleate to LowS instead of dropping HighS
Post by: Nicolas Dorier on October 20, 2015, 01:26:40 PM
Craft a redeem script "<DerHighS> OP_EQUALVERIFY", spend it. The mutator will create an invalid transaction which will ban him from the network. Now, you look in your banlist and collect the IP.

For information, my node which is currently malleating HighS to LowS detects around 2 and 4% of HighS signatures.

What if the inner p2sh (redeem) script is the

OP_2DUP OP_EQUAL OP_IF OP_RETURN OP_ENDIF OP_2 <pubkey> <samepubkey> OP_2 OP_CHECKMULTISIG

and the scriptSig is
OP_0 <signature> <malledsignature> <redeemScript>

It would kick my bot ! :D

For information, my node which is currently malleating HighS to LowS detects around 2 and 4% of HighS signatures.

I started to track the numbers earlier the day, and I currently see about 3.5 %.

It would be interesting to know at which percentage the mutated transactions are mined. Did you gather some stats about this already?

Recently, these are the mutations I've seen: http://bitwatch.co/uploads/mutations-2015-10-18.log (not 100 % online)

I just ran again my mutator, the stat I gather is only the % of mutated and show it every 1000 tx. Boring stuff except when a bot go rampage and mutate 30% of them.


Title: Re: Malleability counter attack : Malleate to LowS instead of dropping HighS
Post by: amaclin on October 20, 2015, 01:37:22 PM
It would kick my bot ! :D
I think we have invented new game similar to https://en.wikipedia.org/wiki/Core_War  ;D

ALIEN VS. PREDATOR Mutator vs Malleator. See on every cinema bitcoin client in November '15


Title: Re: Malleability counter attack : Malleate to LowS instead of dropping HighS
Post by: dexX7 on November 11, 2015, 12:10:11 PM
Just as quick update, the mutation rate over the last 1373396 transactions (about 8 days) for me was 0.9899 %.


Title: Re: Malleability counter attack : Malleate to LowS instead of dropping HighS
Post by: Nicolas Dorier on November 12, 2015, 07:19:42 AM
Just as quick update, the mutation rate over the last 1373396 transactions (about 8 days) for me was 0.9899 %.

I know that coinprism (Open Asset, colored coin wallet) is using an old version of bitcoinjs which create HighS, but now they fix it on the backend to LowS.
I don't think open asset account for a lot, but the malleability attack pushed services to update.