Malleability counter attack : Malleate to LowS instead of dropping HighS

[Nicolas Dorier]

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 ?

[1715196852]

1715196852

[1715196852]

1715196852

[1715196852]

1715196852

[1715196852]

1715196852

[1715196852]

1715196852

[1715196852]

1715196852

[achow101]

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

[dexX7]

I had the idea in the New transaction malleability attack wave? Another stresstest? thread, and gmaxwell mentioned something similar in Bitcoin Core pull request #6769 (not sure, if related). TheBlueMatt then created the patch, 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.)

[Nicolas Dorier]

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.

[mezzomix]

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.

[BitcoinNewsMagazine]

New Bitcoin Core release 0.11.1 obviates the problem by mandating LowS.

[Nicolas Dorier]

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.

[Nicolas Dorier]

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...

[dexX7]

New Bitcoin Core release 0.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.

[Nicolas Dorier]

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.

[amaclin]

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.

[Nicolas Dorier]

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.

[amaclin]

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.

[Nicolas Dorier]

(note: bc.i parses it incorrect)

Yes, bc.i does not accept OP_RETURN either.

But it is non-standard and there is no miner today who can confirm it.

Nop.
Standard script rules relaxed for P2SH addresses

Too lazy to find the exact commit though. :p

[Nicolas Dorier]

Also, the transaction you show me is not P2SH. The term "redeem script" always implies P2SH.

[amaclin]

Also, the transaction you show me is not P2SH. The term "redeem script" always implies P2SH.

Wat?

[Nicolas Dorier]

Redeem Script as described here.

[Nicolas Dorier]

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

[amaclin]

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>

[dexX7]

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)