public-report-high-s.txt

# Problem

A lightning node must verify that its channel transactions are not only consensus-valid but also
tx-relay standard. The counterparty signatures are part of the local txn (commitment/HTLC)
as provided in the `commitment_signed`. Verifying consensus-validity of these signatures
but not their tx-relay standardness, let an attacker provoke a permanent tx-relay failure 
of the victim transactions. The attacker can steal in-flight HTLCs once they expire as the victim
can't trustlessly claim them onchain during the CLTV delay.

Bitcoin ECDSA signatures are made of the scalar pair (R, S). Since Bitcoin Core 0.10 [0], high-S 
(above curve order / 2) signatures aren't standard and thus any transaction containing one won't be 
relayed/mined on the regular p2p network. Note, that this check isn't part of consensus rules even
if has been proposed to be soft-forked [1].

Prior to v0.10, LND would have accepted counterparty high-S signature and broadcast tx-relay invalid 
local commitment/HTLC transactions. This can be exploited by any peer with an open channel whatever
victim situation (routing node, payment-receiver, payment-sender [2]).

Contrary to other Lightning implementations, LND uses `btcd.btcec.signature` for verifying counterparty
signatures at commimtnent signed exchange. This go package relies itself on the default golang crypto
ecdsa package. It differs from libsecp256k1, as the verification method doesn't enforce the lower-S
form of the signature, thus a libsecp256k1 signature validity is tighter than a golang ecdsa package
one.

Note, that LND didn't suffer of this vulnerability on opening/closing as it was relying on btcd.txscript
witness verification method with the correct standard flags, enforcing low-S signatures.

Note that Bitcoin Core (`CPubKey::Verify`) always normalize signatures before passing them to 
libsecp256k1 verification method which unconditionally enforces low-S (`secp256k1_ecdsa_verify`).
 
# Solution

As ECDSA signatures are inherently malleable, even if the counterparty provides a high-S signature
it can be normalized by the receiver to a tx-relay standard one.

A more proactive solution is to fail the channel at any reception of a high-S signature as it's a
clear signal that your counterparty is either malicious or buggy (most bitcoin softwares generate
low-S signature since a while [3]).

For now, the first solution has been adopted by the LND team. A spec change has been proposed to make 
the second a requirement.

# Background

A lightning node security underlies on the assumption to be always able to unilaterally broadcast
channel transactions in the aim to timely confirm them on-chain to enforce an off-chain negotiated 
balance.

It must be remembered that channel transactions are asymmetric, thus each party owns a different
version including all parties's balances/HTLCs. To broadcast its version, a party must own
a valid witness at anytime.

For commitment transactions, the witness stack is the following :

0 <localfunding_sig> <remotefunding_sig>

For HTLC-Success:

0 <remotehtlc_sig> <localhtlc_sig> <payment_preimage>

For HTLC-Timeout:

0 <remotehtlc_sig> <localhtlc_sig> <> (empty vector)

The <remotefunding_sig>/<remotehtlc_sig> are the ones which might have been maliciously malleated
by an attacker.

These signatures are provided at channel updated by a counterparty's `commitment signed`. Once it's
accepted, the local node must release the revocation secret for the previous channel state, thus
relying on the validity of highest state transactions for its funds safety.

These transactions must be unilaterally broadcasted in case of reaching the off-chain resolution 
deadline for [4]:
* offered HTLCs for a routing/original sender
* received HTLCs for a routing/last receiver

Note, this off-chain resolution deadline even if it's expressed as block height it's not equal
to a HTLC absolute timelock but must always be inferior. It offers a block buffer for a local node 
to broadcast, fee-bump and hopefully confirm its transations.

A non-standard transaction can still be confirmed by out-of-band agreement with a miner or a user
intervention to correct the transaction if possible. In the case of Lightning, the security model
doesn't assume this kind of user intervention and deployed timelocks would have been too short for
a reasonable intervention of a node operator.

# Discovery

While working on Rust-Lightning, I observed that the implementation was generating MINIMALIF-invalid
transactions due to a regression. This case wasn't covered by our test framework as there is no
easy-to-integrate utility to test transaction standardness. After patching the spec, to recall
the MINIMALIF requirement on some channel transactions witnesses [6], I audited deployed Lightning 
implementations w.r.t to Core script interpreter standardness flags. A quick test against LND (65f5119)
revealed this vulnerability.

After informing the LND team, I also informed the c-lightning and Eclair teams. Even if this
vulnerability is implementation specific, the tx-relay standardness issues it underscored could
have been failed by other implementations. Thus an urgency fix by one of the team could have revealed
easy-to-exploit weaknesses in other in-production implementations. As the vulnerability involves 
langage-specific serializers and dependencies, it's a hard task evaluate correctness of an implementation
without alerting the concerned developers teams. For the future, it would be better to have a clearer 
Lightning-wise coordination policy [7].

Note, that we agreed with the LND team for a 6-month embargo period, the double of channel funding
check CVEs. As the Lightning ecosystem is maturing, the funds are stake are also growing. It should
be minded how much Lightning software is sensible compared to other security/cryptographic software 
(e.g TLS). The high-stake node are known, channel connections are mostly open, they're operating on 
top of a public infrastructure (the Bitcoin network) and the codebases are fully open source. 
Ligthning node operators are running a Bitcoin bank in the plainsight, any failure might be observed
and exploited by an attacker.

I'm eager to engage the wider Lightning community on what a reasonable vulnerability embargo
should endure, both incentivizing dev teams to proactively fix their security vulnerabilities while 
minding a wide range of users, from business to hobbyists.

# Ecosystem Implications

This vulnerability is a case of a transaction standardness malleability. Transaction standardness
is a set of supplementary anti-DoS rules on top of Bitcoin consensus rulles. For e.g,
MIN_STANDARD_TX_NONWITNESS_SIZE or MINIMALIF-compliant witnesses. This set of rules isn't well-defined
as it's part of a full-node policy, which varies across implementations and versions.

There is no a tx-relay policy but as many tx-relay policies as there are full-node deployed as some
checks might be tighten by node settings. This fact is acknowledged by LN devs since a while who
are most of the time testing channel transactions standardness against lastest Core release, for lack
of better. 

This situation is concerning and sound to have been an undersight during Lightning/payment channels
protocols design. The transaction standardness surface is quite wide, and any standardness fault,
either accidental or malicious triggered, can provoke a loss of funds for a LN node.

Further, this tx-relay standardness issue has a wider echo as other time-sensitive multi-party
protocols (e.g vaults/CoinSwaps) are affected. All Bitcoin software implementing this class
of protocols must correctly sanitize counterparty contribution, to avoid jeopardizing funds
security or introducing easy DoS (e.g a dual-funded channel with counterparty non-standard input) [8]

At the Bitcoin base layer, a tigher, new tx-relay standard rule could potentially break the security 
of all these off-chain protocols and thus deployed silently without anyone realizing before it's
easy exploitation. As of today, tx-relay standardness fog is a systematic risk for layer 2
protocols relying on time-sensitive transactions.

# Timeline

2020-04-03: Vulnerability discovered, LND team notified
2020-04-29: lnd v0.10.0-beta released
2020-07-31: lnd v0.11.0-beta released
2020-10-08: Partial Disclosure, encourage lnd users to upgrade to lnd v1.11.x ASAP
2020-10-09: CVE assigned (https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2020-26895)
2020-10-20: Full Disclosure


[0] https://github.com/bitcoin/bitcoin/pull/6769
[1] https://github.com/bitcoin/bips/blob/master/bip-0147.mediawiki
[2] A sender won't be able to timeout its offered payment on the first link of the payment path thus
it might be claimed after the expiration with a preimage of which the utility is out-of-date
[3] https://github.com/bitcoinops/scaling-book/issues/9#issuecomment-599047992
[4] XXX
[5] For more information, see the Flood & Loot paper (https://arxiv.org/pdf/2006.08513.pdf). The 
channel timelocks which could have been exploited due to this current vulnerable are similar, even
if the attack building block differs (i.e malicious mempool-congestion)
[6] https://github.com/lightningnetwork/lightning-rfc/pull/764
[7] https://github.com/lightningnetwork/lightning-rfc/pull/772
[8] For a wider discussion, see https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-July/018063.html