Malleability counter attack : Malleate to LowS instead of dropping HighS

Nicolas Dorier

hero member

Activity: 714

Merit: 662

Quote from: dexX7 on November 11, 2015, 07:10:11 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.

dexX7

legendary

Activity: 1106

Merit: 1026

Just as quick update, the mutation rate over the last 1373396 transactions (about 8 days) for me was 0.9899 %.

amaclin

legendary

Activity: 1260

Merit: 1019

Quote from: Nicolas Dorier on October 20, 2015, 08:26:40 AM

It would kick my bot ! Cheesy

I think we have invented new game similar to https://en.wikipedia.org/wiki/Core_War Grin

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

Nicolas Dorier

hero member

Activity: 714

Merit: 662

Quote from: amaclin on October 18, 2015, 06:08:40 AM

Quote from: Nicolas Dorier on October 15, 2015, 09:10:23 AM

Craft a redeem script " 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.

Quote from: Nicolas Dorier on October 17, 2015, 07:28:11 AM

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 OP_2 OP_CHECKMULTISIG

and the scriptSig is
OP_0

It would kick my bot ! Cheesy

Quote from: dexX7 on October 18, 2015, 11:25:07 AM

Quote from: Nicolas Dorier on October 17, 2015, 07:28:11 AM

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.

dexX7

legendary

Activity: 1106

Merit: 1026

Quote from: Nicolas Dorier on October 17, 2015, 07:28:11 AM

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)

amaclin

legendary

Activity: 1260

Merit: 1019

Quote from: Nicolas Dorier on October 15, 2015, 09:10:23 AM

Craft a redeem script " 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.

Quote from: Nicolas Dorier on October 17, 2015, 07:28:11 AM

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 OP_2 OP_CHECKMULTISIG

and the scriptSig is
OP_0

Nicolas Dorier

hero member

Activity: 714

Merit: 662

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

Nicolas Dorier

hero member

Activity: 714

Merit: 662

Redeem Script as described here.

amaclin

legendary

Activity: 1260

Merit: 1019

Quote from: Nicolas Dorier on October 15, 2015, 12:29:41 PM

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

Wat?

Nicolas Dorier

hero member

Activity: 714

Merit: 662

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

Nicolas Dorier

hero member

Activity: 714

Merit: 662

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

Too lazy to find the exact commit though. :p

amaclin

legendary

Activity: 1260

Merit: 1019

Quote from: Nicolas Dorier on October 15, 2015, 11:10:50 AM

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

hero member

Activity: 714

Merit: 662

Quote from: amaclin on October 15, 2015, 11:07:10 AM

Quote from: Nicolas Dorier on October 15, 2015, 09:10:23 AM

Craft a redeem script " 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

legendary

Activity: 1260

Merit: 1019

Quote from: Nicolas Dorier on October 15, 2015, 09:10:23 AM

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.

Quote from: Nicolas Dorier on October 15, 2015, 09:10:23 AM

Craft a redeem script " 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

hero member

Activity: 714

Merit: 662

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

dexX7

legendary

Activity: 1106

Merit: 1026

Quote from: BitcoinNewsMagazine on October 15, 2015, 05:55:37 AM

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.

Quote from: Nicolas Dorier on October 15, 2015, 07:59:45 AM

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

hero member

Activity: 714

Merit: 662

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

Nicolas Dorier

hero member

Activity: 714

Merit: 662

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.

BitcoinNewsMagazine

legendary

Activity: 1806

Merit: 1164

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

mezzomix

legendary

Activity: 2772

Merit: 1277

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.

Nicolas Dorier

hero member

Activity: 714

Merit: 662

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 _Transactions = new ConcurrentDictionary();

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 ops = new List();
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 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.

dexX7

legendary

Activity: 1106

Merit: 1026

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

achow101

staff

Activity: 3458

Merit: 6793

Just writing some code

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

Nicolas Dorier

hero member

Activity: 714

Merit: 662

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 ?

Topic: Malleability counter attack : Malleate to LowS instead of dropping HighS (Read 3644 times)