HildisviniOttar/P2PK.md

## P2PK.md

      
    Raw
  

              P2PK.md
            
          
    Pay to Pub Key results in double-spend (x3)

In THORChain a user sends a transaction to Swap an asset for another. The other asset is specified in a memo string attached to the inbound transaction.
The toAddress specified in the memo can be various formats (eg an ETH address would be 0xabcd... and a Bitcoin address is typically bc1....
An exploit exists where a customer that sends a swap destined for a mangled public key will swap to BTC, but not observed by the system resulting in 3x more outbounds (double-spend x3).
A user who sends in $5m in this manner would receive around $14m in illegal funds (assuming they are not caught).
Technical details

An observed transaction outbound (from a Yggdrasil or Asgard vault) is observed then attempted to be matched against a corresponding legitimate txOutItem in the outbound queue. Once observed, the txOutItem is finalised as being sent.

An unobserved txOutItem (after some time) is assumed to have not been sent by the correponding Yggdrasil, and is re-scheduled to be sent by each (currently 3) Asgards one by one.
So if a transaction can be sent in by a user to be scheduled to one particular address, but is observed as another different address string, it is never matched and will be re-sent to the user 3x more times.
Pay to Public Key

Normally a bitcoin spend script these days is a form of Pay to Public Key hash (P2PKH). An old-school version that doesn't exist much but is still supported by BTCD library is Pay to Public Key (P2PK).
Firstly it is worth explaining some different public key formats. The actual public key is two 32 byte values X and Y, plus a leading byte that indicates the format the PubKey is in.
For an uncompressed pubkey, the format is 0x04 then 32 bytes X followed by 32 bytes Y for a total of 65 bytes. This is the one we're interested in. There are some others for Compressed & Hybrid which have different leading bytes.
The Exploit

Send a swap to a destination public key address and instead of a leading 0x04 you replace it with 0x05 then your X and Y (corresponding to your private key).
e.g. =:BTC.BTC:{hex encoded uncompressed pubkey with raw leading byte changed from 0x04 to 0x05}
THORChain BTCD de-mangles the 0x05 back to 0x04 during parsing, sends the tx out as 4XY, which is a different address than in the txOutItem, resulting in non-observation and double-spends.
Code walkthrough

In Bifrost Bitcoin client.go when signing a txOut we get to:
outputAddr, err := btcutil.DecodeAddress(tx.ToAddress.String(), c.getChainCfg())
ToAddress is attacker controlled (our mangled pubkey).
It turns out, DecodeAddress() will return an Address that is type {uncompressed, X, Y} which serialises into [4][X][Y] in the txscript that is sent to mempool.
The key parts of code are:
    // Serialized public keys are either 65 bytes (130 hex chars) if
    // uncompressed/hybrid or 33 bytes (66 hex chars) if compressed.
    if len(addr) == 130 || len(addr) == 66 {
        serializedPubKey, err := hex.DecodeString(addr)
        if err != nil {
            return nil, err
        }
        return NewAddressPubKey(serializedPubKey, defaultNet)
    }
This ^^ will be hit because our address (hex encoded) has length 130.
serializedPubKey is just our 65 bytes with first byte mangled.
Inside this we get to:
// NewAddressPubKey returns a new AddressPubKey which represents a pay-to-pubkey
// address.  The serializedPubKey parameter must be a valid pubkey and can be
// uncompressed, compressed, or hybrid.
func NewAddressPubKey(serializedPubKey []byte, net *chaincfg.Params) (*AddressPubKey, error) {
    pubKey, err := btcec.ParsePubKey(serializedPubKey, btcec.S256())
    if err != nil {
        return nil, err
    }

    // Set the format of the pubkey.  This probably should be returned
    // from btcec, but do it here to avoid API churn.  We already know the
    // pubkey is valid since it parsed above, so it's safe to simply examine
    // the leading byte to get the format.
    pkFormat := PKFUncompressed
    switch serializedPubKey[0] {
    case 0x02, 0x03:
        pkFormat = PKFCompressed
    case 0x06, 0x07:
        pkFormat = PKFHybrid
    }

    return &AddressPubKey{
        pubKeyFormat: pkFormat,
        pubKey:       pubKey,
        pubKeyHashID: net.PubKeyHashAddrID,
    }, nil
}
We will see in a moment that ParsePubKey() will return the raw XY.
Further down, the pkFormat defaults to PKFUncompressed if the magic number is not 2,3,6,7. In our case it's 5. It normally would be 4 for a legit uncompressed pk.
And lastly inside ParsePubKey where we give it our mangled [5][X][Y], this works because of:
    format := pubKeyStr[0] //5
    ybit := (format & 0x1) == 0x1
    format &= ^byte(0x1) //4
Here format is set to 5 initially (binary 101)
We extract the last bit (ybit) which is irrelevant.
Then the last line we CLEAR THE LSB. So our 5 turns into a 4. 🎉 🎉  And it decodes the X,Y perfectly as if it were a regular uncompressed PK.
Summary

Putting it all together:
We send in a mangled pubkey toAddress where instead of 4XY, it's 5XY. BTCD decodes it into an Address struct {uncompressed, X, Y} which is serialised to 4XY for publishing to the bitcoin mempool. This will be observed as toAddress=4XY.
Does not match 5XY in txOutItem. Double-spend. (Quad-spend with 3 asgards and a Ygg).
Chains affected

All utxo chains (BTC, LTC, BCH, DOGE). They all support P2PK.
Reported

To @thorsec on THORChain Discord 29th March 2022, around 0700h UTC.
Fix

Bifrost should not sign utxo where the decoded address reconstructed string does not match the txOut address string (for all utxo chains).
Addendum - fun with bech32

Once the above fix is in place it stops all address related shenanigans. The main thing to check is that changing the human-readable-part (hrp) of a bech32 address doesn't get accepted, and this is correct -- it must match the chain it is on, e.g. BTC mainnet is enforced to begin with bc1. Also Base58 encoded addresses are very strict about the format.
This section also ensures tb hrp is not used on btc mainnet:
// test that the network we are running matches the destination network
if !common.GetCurrentChainNetwork().SoftEquals(msg.Destination.GetNetwork(msg.Destination.GetChain())) {
	return nil, fmt.Errorf("address(%s) is not same network", msg.Destination)
}
But can we mangle bech32 such that two different bech32 addresses (string representations) with the same hrp decode to the same sequence of bytes?  (spoiler: no).
The key is how bech32 stores characters in 5-bit encoding. An address consists of:
[hrp] [separator "1"] [data encoded as characters each representing 5 bits] [6 char (30 bit) checksum].
For segwit address specifically, the data component is [5 bit version] [160 bits address].
5-bit Encoding uses characters: "qpzry9x8gf2tvdw0s3jn54khce6mua7l". So binary 00000 is q, 00001 is p etc.
For example to represent 11111111 00000000 bytes (0x00 0xFF), it would break into sequences of 5 bits:

11111 11100 00000 00000 (last one padded with 4 extra zeros). This is encoded to characters luqq.
To decode luqq we refer to the docs:  https://github.com/bitcoin/bips/blob/master/bip-0173.mediawiki#segwit-address-format

Convert the rest of the data to bytes:
Translate the values to 5 bits, most significant bit first.
Re-arrange those bits into groups of 8 bits. Any incomplete group at the end MUST be 4 bits or less, MUST be all zeroes, and is discarded.
There MUST be between 2 and 40 groups, which are interpreted as the bytes of the witness program.

So we get 11111111 00000000 0000.  The trailing 4 zeros are safely discarded.
OK so can we abuse this somehow? Let's look at a valid bech32 segwit P2WPKH address: bc1qw508d6qejxtdg4y5r3zarvary0c5xw7kv8f3t4.
Discarding the checksum v8f3t4, the last 5 bytes are y0c5xw7k.
The actual address starts after bc1q since q is a 5-bit witness number (zero in this case). So there are actually 32 data characters (w508d6qejxtdg4y5r3zarvary0c5xw7k) each 5 bits, totalling 160 bits (20 bytes) :) So the last character finishes on an 8 bit boundary perfectly.
y0c5xw7k is binary 00100 01111 11000 10100 00110 01110 11110 10110. Grouping into groups of 8 gives:
00100011 11110001 01000011 00111011 11010110.  (perfect alignment).
So if we were to insert any character onto the end, e.g. a q (00000), to try and mangle it, this results in an illegal 5-bit overrun.
In ConvertBits():
	// We pad any unfinished group if specified.
	if pad && filledBits > 0 {
		nextByte = nextByte << (toBits - filledBits)
		regrouped = append(regrouped, nextByte)
		filledBits = 0
		nextByte = 0
	}

	// Any incomplete group must be <= 4 bits, and all zeroes.
	if filledBits > 0 && (filledBits > 4 || nextByte != 0) {
		return nil, ErrInvalidIncompleteGroup{}
	}
Here pad is passed false by the callsite, so it doesn't pad. Which means this actually returns nil, ErrInvalidIncompleteGroup{} and does not decode.
Similarly there are no ways of omitting a character: for example by brute-forcing a private-key that has an address with lsb 00000: If we encoded that normally it would have a final digit q. If we removed that q and tried to decode it to 8-bit, we end up with 3 bits of data -- if these are non-zero we get the error above. If they are zero we only get 19 bytes of data which isn't a valid address.
bech32 is safe ✅