Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?

  BIP: 324
  Layer: Peer Services
  Title: Version 2 Peer-to-Peer Message Transport Protocol
  Author: Jonas Schnelli <dev@jonasschnelli.ch>
  Status: Draft
  Type: Standards Track
  Created: 2019-03-08
  License: PD

Table of Contents

Abstract

This BIP describes a new Bitcoin peer to peer transport protocol with opportunistic encryption.

Motivation

The current peer-to-peer protocol is partially inefficient and in plaintext.

With the current unencrypted message transport, BGP hijack, block delay attacks and message tampering are inexpensive and can be executed covertly (undetectable MITM)[1].

Adding opportunistic encryption introduces a high risk for attackers of being detected. Peer operators can compare encryption session IDs or use other form of authentication schemes [2] to identify an attack.

Each current version 1 Bitcoin peer-to-peer message uses a double-SHA256 checksum truncated to 4 bytes. Roughly the same amount of computation power would be required for encrypting and authenticating a peer-to-peer message with ChaCha20 & Poly1305.

Additionally, this BIP describes a way to identify data which has been manipulated by peers (intercepting, then blocking or tampering with commands).

Encrypting traffic between peers is already possible with VPN, tor, stunnel, curveCP or any other encryption mechanism on a deeper OSI level, however, most of those solutions require significant technical experience in setting up a secure channel and are therefore not widely deployed.

Specification

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119[3].

A peer that supports the message transport protocol as defined in this proposal MUST accept encryption requests from all peers.

Both communication directions share the same shared-secret but have different symmetric cipher keys.

The encryption handshake MUST happen before sending any other messages to the responding peer.

If the responding peer closes the connection after sending the handshake request, the initiating peer MAY try to connect again with the v1 peer-to-peer transport protocol. Such reconnects allow an attacker to "downgrade" the encryption to plaintext communication and thus, accepting v1 connections MUST not be done when the Bitcoin peer-to-peer network has almost entirely embraced v2 communication.

NODE_P2P_V2

Peers supporting the transport protocol after this proposal MUST signal NODE_P2P_V2

NODE_P2P_V2 = (1 << 11)

A peer usually learns an address along with the expected service flags which MAY be used to filter possible outbound peers.

A peer signaling NODE_P2P_V2 MUST accept encrypted communication specified in this proposal.

Peers MAY only make outbound connections to peers supporting NODE_P2P_V2.

Handshake

 ----------------------------------------------------------------------------------------
 | Initiator                             Responder                                      |
 |                                                                                      |
 | x, X         := SECP256k1_KEYGEN()                                                   |
 | CLIENT_HDATA := X                                                                    |
 |                                                                                      |
 |               --- CLIENT_HDATA --->                                                  |
 |                                                                                      |
 |                                       y, Y           := SECP256k1_KEYGEN()           |
 |                                       ECDH_KEY       := SECP256k1_ECDH(X,y)          |
 |                                       SERVER_HDATA   := Y                            |
 |                                                                                      |
 |               <-- SERVER_HDATA ----                                                  |
 |                                                                                      |
 | ECDH_KEY     := SECP256k1_ECDH(x,Y)                                                  |
 ----------------------------------------------------------------------------------------

To request encrypted communication (only possible if yet no other messages have been sent or received), the initiating peer generates an EC secp256k1 ephemeral key and sends the corresponding 32-byte public key to the responding peer and waits for the remote 32-byte public key from the counterparty.

ODD secp256k1 public keys MUST be used (public keys starting with 0x02). If the public key from the generated ephemeral key is an EVEN public key (starting with 0x03), its public key SHOULD be negated and then recalculated. Only using ODD public keys makes it more complex to identify the handshake based on analyzing the traffic.

The handshake request and response message are raw 32byte payloads containing no header, length or checksum (the pure 32byte payload) and MUST be sent before anything else.

Public keys starting with the 4-byte network magic are forbidden and MUST lead to local regeneration of an ephemeral-key.

Pseudocode for the ephemeral-key generation

do {
    ecdh_key.MakeNewKey();
    if (ecdh_key.GetPubKey()[0] == 3) {
        ecdh_key.Negate();
    }
} while (m_ecdh_key.GetPubKey()[0..3] == NETWORK_MAGIC);

Once a peer has received the public key from its counterparty, the shared secret MUST be calculated by using secp256k1 ECDH.

Private keys will never be transmitted. The shared secret can only be calculated if an attacker knows at least one private key and the counterparty's public key. This key-exchange is based on the discrete log problem and thus not sufficiently strong against known forms of possible quantum computer algorithms. Adding an additional quantum resistant key exchange like NewHope is possible but out of scope for this proposal.

After a successful handshake, messages MUST use the "v2 messages structure". Non-encrypted v1 messages from the initiating peer MUST lead to an immediate connection termination.

After a successful handshake, both peers MUST wipe the ephemeral-session-key from memory and/or persistence storage.

A peer not supporting this proposal will not perform the described handshake and thus send a v1 version message. Peers supporting this BIP MAY optionally allow unencrypted v1 communication by detecting a v1 version message by the initial 11-byte sequence of 4byte net magic || "version".

Symmetric Encryption Cipher Keys

Once the ECDH secret (ECDH_KEY) is calculated on each side, the symmetric encryption cipher keys MUST be derived with HKDF [4] after the following specification:

1. HKDF extraction PRK = HKDF_EXTRACT(hash=SHA256, salt="BitcoinSharedSecret||INITIATOR_32BYTES_PUBKEY||RESPONDER_32BYTES_PUBKEY||NETWORK_MAGIC", ikm=ECDH_KEY).

2. Derive Key_1_A (K_1 communication direction A) K1A = HKDF_EXPAND(prk=PRK, hash=SHA256, info="BitcoinK_1_A", L=32)

2. Derive Key_2_A (K_2 communication direction A) K1B = HKDF_EXPAND(prk=PRK, hash=SHA256, info="BitcoinK_2_A", L=32)

3. Derive Key_1_B (K_1 communication direction B) K2 = HKDF_EXPAND(prk=PRK, hash=SHA256, info="BitcoinK_1_B", L=32)

3. Derive Key_2_B (K_2 communication direction B) K2 = HKDF_EXPAND(prk=PRK, hash=SHA256, info="BitcoinK_2_B", L=32)

Session ID

Both parties MUST also calculate the 256bit session-id using SID = HKDF_EXPAND(prk=PRK, hash=SHA256, info="BitcoinSessionID", L=32). The session-id can be used for authenticating the encryption-session (identity check).

The session-id MUST be presented to the user on request.

ChaCha20-Poly1305@Bitcoin Cipher Suite

Background

ChaCha20-Poly1305@Bitcoin AEAD is almost identical to the openSSH version [5]. The only difference to the @openSSH version is that the @Bitcoin version has a 3 byte package length (instead 4) and reuses the remaining bytes of the ChaCha20 round (21 length field encryption per ChaCha20 round; 21 x 3 < 64).

ChaCha20 is a stream cipher designed by Daniel Bernstein and described in [6]. It operates by permuting 128 fixed bits, 128 or 256 bits of key, a 64 bit nonce and a 64 bit counter into 64 bytes of output. This output is used as a keystream, with any unused bytes simply discarded.

Poly1305 [7], also by Daniel Bernstein, is a one-time Carter-Wegman MAC that computes a 128 bit integrity tag given a message and a single-use 256 bit secret key.

The chacha20-poly1305@bitcoin combines these two primitives into an authenticated encryption mode. The construction used is based on that proposed for TLS by Adam Langley in [8], but differs in the layout of data passed to the MAC and in the addition of encryption of the packet lengths.

Detailed Construction

The chacha20-poly1305@bitcoin cipher requires two 256 bits of key material as output from the key exchange. Each key (K_1 and K_2) are used by two separate instances of chacha20.

The instance keyed by K_1 is a stream cipher that is used only to encrypt the 3 byte packet length field and has its own sequence number. The second instance, keyed by K_2, is used in conjunction with poly1305 to build an AEAD (Authenticated Encryption with Associated Data) that is used to encrypt and authenticate the entire packet.

Two separate cipher instances are used here so as to keep the packet lengths confidential (best effort; for passive observing) but not create an oracle for the packet payload cipher by decrypting and using the packet length prior to checking the MAC. By using an independently-keyed cipher instance to encrypt the length, an active attacker seeking to exploit the packet input handling as a decryption oracle can learn nothing about the payload contents or its MAC (assuming key derivation, ChaCha20 and Poly1305 are secure). Active observers can still obtain the message length (ex. active ciphertext bit flipping or traffic shemantics analysis)

The AEAD is constructed as follows: for each packet, generate a Poly1305 key by taking the first 256 bits of ChaCha20 stream output generated using K_2, an IV consisting of the packet sequence number encoded as an LE uint64 and a ChaCha20 block counter of zero. The K_2 ChaCha20 block counter is then set to the little-endian encoding of 1 (i.e. {1, 0, 0, 0, 0, 0, 0, 0}) and this instance is used for encryption of the packet payload.

Packet Handling

When receiving a packet, the length must be decrypted first. When 3 bytes of ciphertext length have been received, they may be decrypted.

A ChaCha20 round always calculates 64bytes which is sufficient to encrypt a 3 bytes length field 21 times (21*3 = 63). The length field sequence number can thus be used 21 times (keystream caching).

The length field must be enc-/decrypted with the ChaCha20 keystream keyed with K_1 defined by block counter 0, the length field sequence number in little endian and a keystream position from 0 to 60.

Pseudo code example:

// init
sequence_nr_payload = 0; //payload sequence number
sequence_nr_length_field = 0; //length field sequence number (will be reused)
aad_length_field_pos = 0; //position in the length field cipher instance keystream chunk

...

// actual encryption
if cache_length_field_sequence_number != sequence_nr_length_field {
  cache_keystream_64_bytes = ChaCha20(key=K_1, iv=little_endian(sequence_nr_length_field), counter=0);
  cache_length_field_sequence_number = sequence_nr_length_field
}
packet_length = XOR_TO_LE(cache_length_field_sequence_number[aad_length_field_pos - aad_length_field_pos+3], ciphertext[0-3])

sequence_nr_payload++;
aad_length_field_pos += 3; //skip 3 bytes in keystream
if (aad_length_field_pos + 3 > 64) { //if we are outside of the 64byte keystream...
  aad_length_field_pos = 0; // reset at position 0
  sequence_nr_length_field++; // increase length field sequence number
}

Once the entire packet has been received, the MAC MUST be checked before decryption. A per-packet Poly1305 key is generated as described above and the MAC tag is calculated using Poly1305 with this key over the ciphertext of the packet length and the payload together. The calculated MAC is then compared in constant time with the one appended to the packet and the packet decrypted using ChaCha20 as described above (with K_2, the packet sequence number as nonce and a starting block counter of 1).

Detection of an invalid MAC MUST lead to immediate connection termination.

To send a packet, first encode the 3 byte length and encrypt it using K_1 as described above. Encrypt the packet payload (using K_2) and append it to the encrypted length. Finally, calculate a MAC tag and append it.

The initiating peer MUST use K_1_A, K_2_A to encrypt messages on the send channel, K_1_B, K_2_B MUST be used to decrypt messages on the receive channel.

The responding peer MUST use K_1_A, K_2_A to decrypt messages on the receive channel, K_1_B, K_2_B MUST be used to encrypt messages on the send channel.

Optimized implementations of ChaCha20-Poly1305@bitcoin are relatively fast, therefore it is very likely that encrypted messages will not require additional CPU cycles per byte when compared to the current unencrypted p2p message format (ChaCha20/Poly1305 versus double SHA256).

The initial packet sequence numbers are 0.

K_2 ChaCha20 cipher instance (payload) must never reuse a {key, nonce} for encryption nor may it be used to encrypt more than 2^70 bytes under the same {key, nonce}.

K_1 ChaCha20 cipher instance (length field/AAD) must never reuse a {key, nonce, position-in-keystream} for encryption nor may it be used to encrypt more than 2^70 bytes under the same {key, nonce}.

We use message sequence numbers for both communication directions.

 ------------------------------------------------------------------------------------------
 | Initiator                          Responder                                           |
 |                                                                                        |
 | AEAD() = ChaCha20Poly1305Bitcoin()                                                     |
 | MSG_A_CIPH = AEAD(k=K_1_A, K_2_A, payload_nonce=0, aad_nonce=0, aad_pos=0, msg)        |
 |                                                                                        |
 |                         --- MSG_CIPH --->                                              |
 |                                                                                        |
 |                                    msg   := AEAD(k=K_1_A,K_2_A, n=0, ..., MSG_A_CIPH)  |
 |                                                                                        |
 ------------------------------------------------------------------------------------------

AEAD Test Vectors

message   00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
k1 (DATA) 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
k2 (AAD)  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

AAD keystream
76 b8 e0 ad a0 f1 3d 90 40 5d 6a e5 53 86 bd 28 bd d2 19 b8 a0 8d ed 1a a8 36 ef cc 8b 77 0d c7 da 41 59 7c 51 57 48 8d 77 24 e0 3f b8 d8 4a 37 6a 43 b8 f4 15 18 a1 1c c3 87 b6 69 b2 ee 65 86

ciphertext
76 b8 e0 9f 07 e7 be 55 51 38 7a 98 ba 97 7c 73 2d 08 0d cb 0f 29 a0 48 e3 65 69 12 c6 53 3e 32

MAC
d2 fc 11 82 9c 1b 6c 1d f1 f5 51 cd 61 31 ff 08
message   01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
k1 (DATA) 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
k2 (AAD)  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

AAD keystream
76 b8 e0 ad a0 f1 3d 90 40 5d 6a e5 53 86 bd 28 bd d2 19 b8 a0 8d ed 1a a8 36 ef cc 8b 77 0d c7 da 41 59 7c 51 57 48 8d 77 24 e0 3f b8 d8 4a 37 6a 43 b8 f4 15 18 a1 1c c3 87 b6 69 b2 ee 65 86

ciphertext
77 b8 e0 9f 07 e7 be 55 51 38 7a 98 ba 97 7c 73 2d 08 0d cb 0f 29 a0 48 e3 65 69 12 c6 53 3e 32

MAC
ba f0 c8 5b 6d ff 86 02 b0 6c f5 2a 6a ef c6 2e
message
ff 00 00 f1 95 e6 69 82 10 5f fb 64 0b b7 75 7f 57 9d a3 16 02 fc 93 ec 01 ac 56 f8 5a c3 c1 34 a4 54 7b 73 3b 46 41 30 42 c9 44 00 49 17 69 05 d3 be 59 ea 1c 53 f1 59 16 15 5c 2b e8 24 1a 38 00 8b 9a 26 bc 35 94 1e 24 44 17 7c 8a de 66 89 de 95 26 49 86 d9 58 89 fb 60 e8 46 29 c9 bd 9a 5a cb 1c c1 18 be 56 3e b9 b3 a4 a4 72 f8 2e 09 a7 e7 78 49 2b 56 2e f7 13 0e 88 df e0 31 c7 9d b9 d4 f7 c7 a8 99 15 1b 9a 47 50 32 b6 3f c3 85 24 5f e0 54 e3 dd 5a 97 a5 f5 76 fe 06 40 25 d3 ce 04 2c 56 6a b2 c5 07 b1 38 db 85 3e 3d 69 59 66 09 96 54 6c c9 c4 a6 ea fd c7 77 c0 40 d7 0e af 46 f7 6d ad 39 79 e5 c5 36 0c 33 17 16 6a 1c 89 4c 94 a3 71 87 6a 94 df 76 28 fe 4e aa f2 cc b2 7d 5a aa e0 ad 7a d0 f9 d4 b6 ad 3b 54 09 87 46 d4 52 4d 38 40 7a 6d eb 3a b7 8f ab 78 c9

k1 (DATA) 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 14 15 16 17 18 19 1a 1b 1c 1d 1e 1f
k2 (AAD)  ff 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 14 15 16 17 18 19 1a 1b 1c 1d 1e 1f

AAD keystream
c6 40 c1 71 1e 3e e9 04 ac 35 c5 7a b9 79 1c 8a 1c 40 86 03 a9 0b 77 a8 3b 54 f6 c8 44 cb 4b 06 d9 4e 7f c6 c8 00 e1 65 ac d6 61 47 e8 0e c4 5a 56 7f 6c e6 6d 05 ec 0c ae 67 9d ce eb 89 00 17

ciphertext
39 40 c1 e9 2d a4 58 2f f6 f9 2a 77 6a eb 14 d0 14 d3 84 ee b3 0f 66 0d ac f7 0a 14 a2 3f d3 1e 91 21 27 01 33 4e 2c e1 ac f5 19 9d c8 4f 4d 61 dd be 65 71 bc a5 af 87 4b 4c 92 26 c2 6e 65 09 95 d1 57 64 4e 18 48 b9 6e d6 c2 10 2d 54 89 a0 50 e7 1d 29 a5 a6 6e ce 11 de 5f b5 c9 55 8d 54 da 28 fe 45 b0 bc 4d b4 e5 b8 80 30 bf c4 a3 52 b4 b7 06 8e cc f6 56 ba e7 ad 6a 35 61 53 15 fc 7c 49 d4 20 03 88 d5 ec a6 7c 2e 82 2e 06 93 36 c6 9b 40 db 67 e0 f3 c8 12 09 c5 0f 32 16 a4 b8 9f b3 ae 1b 98 4b 78 51 a2 ec 6f 68 ab 12 b1 01 ab 12 0e 1e a7 31 3b b9 3b 5a 0f 71 18 5c 7f ea 01 7d db 92 76 98 61 c2 9d ba 4f bc 43 22 80 d5 df f2 1b 36 d1 c4 c7 90 12 8b 22 69 99 50 bb 18 bf 74 c4 48 cd fe 54 7d 8e d4 f6 57 d8 00 5f dc 0c d7 a0 50 c2 d4 60 50 a4 4c 43 76 35 58 58 

MAC
98 1f be 8b 18 42 88 27 6e 7a 93 ea bc 89 9c 4a

v2 Messages Structure

Field Size Description Data type Comments
3 length & flag 23 + 1 bits Encrypted length of ciphertext payload (not counting the MAC tag) in number of bytes (only 2^23 is usable, most significant bit is the rekey-flag)
1-13 encrypted command variable ASCII command (or one byte short command ID)
? encrypted payload ? The actual data
16 MAC tag ? 128bit MAC-tag

Encrypted messages do not have the 4byte network magic.

The maximum message size is 2^23 (8,388,608) bytes. Future communication MAY exceed this limit and thus MUST be split into different messages.

Decrypting and processing the message MUST take place only AFTER successful authentication (MAC verification).

The 4byte sha256 checksum is no longer required because the AEAD (MAC).

Both peers MUST keep track of the message sequence numbers (uint32) of sent and received messages for building a 64-bit symmetric cipher IV.

The command field MUST start with a byte that defines the length of the ASCII command string up to 12 chars (1 to 12) or a short command ID (see below).

Short Command ID

To save valuable bandwidth, the v2 message format supports message command short IDs for message types with high frequency. The ID/string mapping is a peer to peer arrangement and MAY be negotiated between the initiating and responding peer. A peer conforming to this proposal MUST support short IDs based on the table below and SHOULD use short command IDs for outgoing messages.

Number Command
13 ADDR
14 BLOCK
15 BLOCKTXN
16 CMPCTBLOCK
17 FEEFILTER
18 FILTERADD
19 FILTERCLEAR
20 FILTERLOAD
21 GETADDR
22 GETBLOCKS
23 GETBLOCKTXN
24 GETDATA
25 GETHEADERS
26 HEADERS
27 INV
28 MEMPOOL
29 MERKLEBLOCK
30 NOTFOUND
31 PING
32 PONG
33 REJECT
34 SENDCMPCT
35 SENDHEADERS
36 TX
37 VERACK
38 VERSION

Length comparisons between v1 and v2 messages

v1 in: 4(Magic)+12(Command)+4(MessageSize)+4(Checksum)+37(Payload) == 61
v2 inv: 3(MessageSize&Flag)+1(Command)+37(Payload)+16(MAC) == 57
(93.44%)

v1 ping: 4(Magic)+12(Command)+4(MessageSize)+4(Checksum)+8(Payload) == 32
v2 pong: 3(MessageSize&Flag)+1(Command)+8(Payload)+16(MAC) == 28
(87.5%)

v1 block: 4(Magic)+12(Command)+4(MessageSize)+4(Checksum)+1’048’576(Payload) = 1’048’600
v2 block: 3(MessageSize&Flag)+6(CommandStr)+8(Payload)+16(MAC) == 28 = 1’048’601
(100.000095%)

Re-Keying

Re-keying can be signaled by setting the most significant bit in the length field before encryption. A peer signaling a rekey MUST use the next key for encrypted messages AFTER the message where the signaling has been done.

A peer identifying a rekey by checking the most significant bit in the envelope length must use the next key to decrypt messages AFTER the message where the signaling has been detected.

The next symmetric cipher key MUST be calculated by SHA256(SHA256(session ID || old_symmetric_cipher_key)) and the packet sequence numbers of the corresponding encryption direction must be set to 0.

Re-Keying interval is a peer policy with a minimum timespan of 10 seconds.

The Re-Keying must be done after every 1GB of data sent (recommended by RFC4253 SSH Transport) or if the last rekey was more than an hour ago.

Peers calculate the counterparty limits and MUST disconnect immediately if a violation of the limits has been detected.

Test Vectors

message   verack
k1 (DATA) 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
k2 (AAD)  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Payload seq-nr:   0
AAD seq-nr: 0
AAD pos: 0

Message before encryption
01 00 00 25

Ciphertext (3byte AD, 1byte command, 16 bytes MAC)
77 b8 e0 ba 1c 01 4b e6 1d 0c 66 81 f6 b8 d1 dc b4 cc 0e bf
message   PING (nonce=123456)
k1 (DATA) 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
k2 (AAD)  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Payload seq-nr:   335
AAD seq-nr: 15
AAD pos: 60

Message before encryption (3 bytes packet length, 1byte short command id, 4 byte message payload [ping nonce])
05 00 00 1f 40 e2 01 00

Ciphertext (3byte AD, 1byte command, 4 byte message payload [ping nonce], 16 bytes MAC)
16 43 15 a8 21 f0 a0 ce 24 25 42 8a d4 7a 24 50 d0 dd a6 b0 20 46 5f af

Risks

The encryption does not include an authentication scheme. This BIP does not cover a proposal to avoid MITM attacks during the encryption initialization. However, peers MUST show the session-id to the user on request which allows to identify a MITM by a manual verification on a secure channel.

Optional authentication schemes may be covered by other proposals [2].

An attacker could delay or halt v2 protocol enforcement by providing a reasonable amount of peers not supporting the v2 protocol.

Compatibility

This proposal is backward compatible (as long as not enforced). Non-supporting peers can still use unencrypted communications.

Reference implementation

References

  1. ^ Hijacking Bitcoin: Routing Attacks on Cryptocurrencies - M. Apostolaki, A. Zohar, L.Vanbever
  2. a b BIP150
  3. ^ RFC 2119
  4. ^ HKDF (RFC 5869)
  5. ^ https://github.com/jhcloos/openssh-chacha-poly1305/blob/master/PROTOCOL.chacha20poly1305
  6. ^ ChaCha20
  7. ^ Poly1305
  8. ^ "ChaCha20 and Poly1305 based Cipher Suites for TLS", Adam Langley

Acknowledgments

  • Pieter Wuille and Gregory Maxwell for most of the ideas in this BIP.
  • Tim Ruffing for the review and the hint for the enhancement of the symmetric key derivation.
  • Jonathan Cross for re-wording and grammar corrections

Copyright

This work is placed in the public domain.

@schildbach

This comment has been minimized.

Copy link

@schildbach schildbach commented Mar 22, 2019

What about Short Command IDs for GETDATA and TX messages? Both are quite frequent. Also during blockchain sync BLOCK and MERKLEBLOCK messages?

But generally I think transport encrytion should be separated from the protocol changes itself, into 2 specs which are independant. Otherwise we risk very slow adoption again, as we experienced with segwit because it stuffed so many small changes into a big spec.

(But nice to see Bitcoin Code is finally open minded about encrypting the transport!)

@flack

This comment has been minimized.

Copy link

@flack flack commented Mar 22, 2019

So I'm no cryptography expert, but could it be that instead of "tempering" you meant "tampering with"?

tampering:

  • to interfere so as to weaken or change for the worse —used with with

tempering:

  • to dilute, qualify, or soften by the addition or influence of something else
  • to anneal or toughen (glass) by a process of gradually heating and cooling
  • to make stronger and more resilient through hardship
  • to bring to a suitable state by mixing in or adding a usually liquid ingredient
@jcnelson

This comment has been minimized.

Copy link

@jcnelson jcnelson commented Mar 25, 2019

What is the advantage of encrypting the messages when anyone can connect to your node? A MITM can deduce that a remote endpoint is running the Bitcoin protocol by inspecting its traffic patterns, and if the remote endpoint is open to accepting new peers, the MITM can handshake with it and then receive data it can decrypt. If the purpose of this BIP is to prevent message tampering, then would it be sufficient for Bitcoin peers to simply sign their messages?

Also, while it is a stated motivation, this BIP doesn't appear to address IP prefix hijacking.

@naumenkogs

This comment has been minimized.

Copy link

@naumenkogs naumenkogs commented Mar 25, 2019

@jcnelson

In the case you explained, MITM would act as an inbound connection for a given node. We already have biases to make these inbound connections learn significantly less than outbound (13298), to make it more difficult for them to affect tx relay (14897), and perhaps other things in the codebase I don't remember. What I want to say here is connecting to someone is not equal to reading all the traffic they produce.

Although I see a possibility for a MITM to re-route outbound connections of a given node to MITM itself. But I believe then

  • we're in much bigger trouble than eavesdropping
  • authentication might solve this problem
@jonathancross

This comment has been minimized.

Copy link

@jonathancross jonathancross commented Apr 19, 2019

Hi @jonasschnelli - Here are some small corrections to the English:
https://gist.github.com/jonathancross/2e002268445b450b60a34c0e771027ef/revisions

Nice work!

@jonasschnelli

This comment has been minimized.

Copy link
Owner Author

@jonasschnelli jonasschnelli commented Apr 20, 2019

Thanks @jonathancross! Pulled in.

@mytwocentimes

This comment has been minimized.

Copy link

@mytwocentimes mytwocentimes commented Jun 10, 2019

J

I liked your presentation at Breaking ... I revisited your BIP ... here below some small corrections to the English and some nits. But, there is an ODD/EVEN mismatch. You refer to ODD and show "public keys starting with 0x02" ... should be 0x03.

Learned a lot by reading Overhaul ... thnx

https://gist.github.com/mytwocentimes/a040f51dc1ba94ac7a69bc2e3a1fb41c/revisions

@jonasschnelli

This comment has been minimized.

Copy link
Owner Author

@jonasschnelli jonasschnelli commented Jun 11, 2019

Thanks D!
I'll pull that in...

@onvej-sl

This comment has been minimized.

Copy link

@onvej-sl onvej-sl commented Jul 2, 2019

Only using ODD public keys makes it more complex to identify the handshake based on analyzing the traffic.

Could you explain it to me in more detail?

@jonasschnelli

This comment has been minimized.

Copy link
Owner Author

@jonasschnelli jonasschnelli commented Jul 3, 2019

Could you explain it to me in more detail?

Thanks for the comment. I'll try to expand this section.

Using a standard 33byte pubkey with 0x02 or 0x03 at the beginning would make a handshake trivially identifiable by someone listening on the wire. If we only use ODD pubkeys, the handshake looks pseudo-random (it is still easy to identify a bitcoin handshake by checking if the first 32 bytes is a valid secp256k1 curve point). It is a low hanging fruit that improves the identifiability-robustness slightly with almost no cost.

@wtogami

This comment has been minimized.

Copy link

@wtogami wtogami commented Sep 2, 2019

Adding opportunistic encryption introduces a high risk for attackers of being detected.

Confusingly worded

@pinheadmz

This comment has been minimized.

Copy link

@pinheadmz pinheadmz commented Nov 5, 2019

There are a few related schemes like Noise Protocol and Elligator I wonder if they would apply here? Why not use Noise Protocol's chaining key instead of key rotation? And wouldn't obfuscating EC points with Elligator improve privacy?

@hebasto

This comment has been minimized.

Copy link

@hebasto hebasto commented Apr 12, 2020

@jonasschnelli

If the public key from the generated ephemeral key is an EVEN public key (starting with 0x03), its public key SHOULD be negated and then recalculated.

It seems s/public/private/ is required.

@hebasto

This comment has been minimized.

Copy link

@hebasto hebasto commented Apr 12, 2020

@jonasschnelli
It seems possible to drop support for the REJECT command since it has been removed from the code base (bitcoin/bitcoin#15437).

@jonasschnelli

This comment has been minimized.

Copy link
Owner Author

@jonasschnelli jonasschnelli commented Apr 14, 2020

@hebasto: I'm unsure about the REJECT drop. BIP342 is mainly transport protocol proposal (message parsing stays intact). It's also ready complex and I fear a scope creep into the message processing layer if we start to including small things like the removal of the REJECT message.

@ariard

This comment has been minimized.

Copy link

@ariard ariard commented Apr 30, 2020

The handshake request and response message are raw 32byte payloads containing no header, length or checksum, and MUST be sent before anything else

Is this a DoS vector, you may ask to receiving peers performing KeyGen-and-ECDH-for-free ? I don't have secp256k1 bench in mind, but it's an issue we may ban inbound peer after too much session abandon.

You should also precise what receiving peer should do when key isn't valid (like starting with a 4-byte network magic or not secp256k1).

After a successful handshake, both peers MUST wipe the ephemeral-session-key from memor and/or persistence storage

You should destroy shared secret after session termination, for any reason.

Future communication MAY exceed this limit and thus MUST be split into different messages

Given v2 message structure, how fragmentation may be signaled ?

must be done after every 1GB of data

Given key is symmetric but data sent asymmetric who should bear data accounting exactly ?

More generic:

  • what's about a version byte ? (should have been already raised but as you mention future handshake replacement, or key size == protocol to use?)
  • are shared secrets validity time-bounded even without data exchanged to trigger re-keying?
  • pre-shared symmetric key mode ?

Overall, that's already huge, I guess it's wise to indicate that some parts are left to future specification.

@jonasschnelli

This comment has been minimized.

Copy link
Owner Author

@jonasschnelli jonasschnelli commented Apr 30, 2020

The handshake request and response message are raw 32byte payloads containing no header, length or checksum, and MUST be sent before anything else

Is this a DoS vector, you may ask to receiving peers performing KeyGen-and-ECDH-for-free ? I don't have secp256k1 bench in mind, but it's an issue we may ban inbound peer after too much session abandon.

It might be. Wouldn't that be true as well for a public openssh/ssh server as example?
Also, in V1, one can also DoS by requesting tons of blocks resulting in a lot of SHA256 operations.
Avoiding DoS is probably relatively hard (without blocking legitimate clients). IP based attempt counting, etc. is flawed IMO (easy to circumvent by a large and cheep IPv6 range).

You should also precise what receiving peer should do when key isn't valid (like starting with a 4-byte network magic or not secp256k1).

Good point. Will do.

After a successful handshake, both peers MUST wipe the ephemeral-session-key from memor and/or persistence storage

You should destroy shared secret after session termination, for any reason.

Good point. Will add. I think the ECDH shared secret can be cleansed from memory directly after HKDF-deriving the symmetric keys (and the session id).

Future communication MAY exceed this limit and thus MUST be split into different messages

Given v2 message structure, how fragmentation may be signaled ?

I think split messages would be a message processing layer problem rather than a transport problem.
Transport is up to 2^23 bytes.
If you need to transport 16MB, the message could hint the "page" (rather than the transport layer).

must be done after every 1GB of data

Given key is symmetric but data sent asymmetric who should bear data accounting exactly ?

Each channel (send/recv) has its own symmetric key, thus its own 1GB rule/counter. It's not 100% clear from the specs,... I'll try to add a note to make this more clear.

More generic:

  • what's about a version byte ? (should have been already raised but as you mention future handshake replacement, or key size == protocol to use?)

This is still in discussion.

  • are shared secrets validity time-bounded even without data exchanged to trigger re-keying?

Yes. The BIP states: The Re-Keying must be done after every 1GB of data sent (recommended by RFC4253 SSH Transport) or if the last rekey was more than an hour ago.

  • pre-shared symmetric key mode ?

Outside the current BIP scope.

@elichai

This comment has been minimized.

Copy link

@elichai elichai commented May 3, 2020

I'm missing the rationale of encrypting the length, especially without MACing it separately, what exactly does it give us?

@jonasschnelli

This comment has been minimized.

Copy link
Owner Author

@jonasschnelli jonasschnelli commented May 6, 2020

@elichai:
The chacha20poly1305@bitcoin AEAD is almost identical to the OpenSSH version of the AEAD: https://github.com/openssh/openssh-portable/blob/master/PROTOCOL.chacha20poly1305

Two separate cipher instances are used here so as to keep the packet
lengths confidential but not create an oracle for the packet payload
cipher by decrypting and using the packet length prior to checking
the MAC. By using an independently-keyed cipher instance to encrypt the
length, an active attacker seeking to exploit the packet input handling
as a decryption oracle can learn nothing about the payload contents or
its MAC (assuming key derivation, ChaCha20 and Poly1305 are secure).

Encrypted packet lengths result in a complete pseudo-random stream of data (except the handshake where one can identify a secp256k1 pubkey). But yes, an attacker can still analyse the traffic based on buffer sizes, etc. But the pseudo-random stream has better properties for increasing the censorship robustness (in case we want that later).

@ariard

This comment has been minimized.

Copy link

@ariard ariard commented May 8, 2020

It might be. Wouldn't that be true as well for a public openssh/ssh server as example?
Also, in V1, one can also DoS by requesting tons of blocks resulting in a lot of SHA256 operations.
Avoiding DoS is probably relatively hard (without blocking legitimate clients). IP based attempt counting, etc. is flawed IMO (easy to circumvent by a large and cheep IPv6 range).

With SSH, you avoid at least the KeyGen due to a static pubkey for the server? But I agree banning inbound IPv6 wouldn't work? Maybe leveraging some asmap work? But yes not for now..

From the review:

I guess there are multiple ways how peers want to agree on a mapping (protocol version, dedicated command exchange, versionstring, port, etc.).

In section Short Command ID, maybe you can add a sentence like "We defer mapping negotiation for future specification. In the meanwhile experimentation MAY happen using protocol version..."

Thanks for other answers.

@ariard

This comment has been minimized.

Copy link

@ariard ariard commented May 8, 2020

@jonasschnelli

I'm missing the rationale of encrypting the length, especially without MACing it separately, what exactly does it give us?

And I made the same point in PR review, but actually not MACing the length seems an issue, you may decrypt to some invalid length and therefore manipulate MAC-seek? I remember @cdecker explaining us why they do actually it in https://github.com/lightningnetwork/lightning-rfc/blob/master/08-transport.md, Elichai was there too.

@jonasschnelli

This comment has been minimized.

Copy link
Owner Author

@jonasschnelli jonasschnelli commented May 9, 2020

@ariard
Thanks for bringing this up. I think the MACing of the length field need thoughts (let me dive into this further).
One difference to the BOLT #8 encryption protocol is that BIP324 uses a independent ChaCha20 cipher (keystream) for the packet length where AFAIK the LN protocol uses the same key for length & payload.

@elichai

This comment has been minimized.

Copy link

@elichai elichai commented May 9, 2020

In BOLT 8 they encrypt+mac the length separately from the data, but you're right they use the same keystream for both.
(I personally don't have any comments on the scheme itself as it's the same one from openSSH, so I feel the right thing here is to read the research about openSSH :) )

@real-or-random

This comment has been minimized.

Copy link

@real-or-random real-or-random commented May 16, 2020

To be honest, I'm not sure if I can fully parse the algorithm, so I'm not sure what all goes into the MAC computation and which key it uses. (I think it would be great to have pseudocode for the entire thing, not just parts.) But the length included in the K_2 MAC (as AD), right?

Not MACing the length seems dangerous at first glance. Maybe splitting into K_1 and K_2 makes it secure. But this requires some thoughts These things can be very subtle. What about the following attack on the confidentiality of the message length?

Assume two messages are sent by one of the peers, one after the other, with lengths l_1 and l_2. The attacker sees the two ciphertexts and wants to learn the length of the first message. It guesses l_1, which gives it also a guess for l_2. The guess of l_1 gives it the position of the length field of the second message (that is supposed to be an encryption of l_2). The attacker modifies the length field to be very large, and it also modifies some bytes in the ciphertext of the second message. Then the attacker forwards the modified two messages to the other peer.
If the guess of the attacker was wrong, the other peer will terminate the connection (wrong MAC). If the guess was correct, the other peer won't terminate the connection because it still waits for the rest of the very long second message. So the attacker can learn whether the guess about the length was correct.

BUT: The attacker can learn the length of a message in flight anyway, namely by simply flipping some bits in the ciphertext of the content (not length), and forwarding the message byte by byte. Then as soon as the other peer terminates the connection, the attacker knows that the message was over now (and MAC failed).

So is confidentiality of the length the security goal here? When we develop protocols, we must state what security they should provide. Apparently the message length is not confidential against active attackers here. The draft here says "Two separate cipher instances are used here so as to keep the packet lengths confidential", which was copied from the OpenSSH doc. I guess what's meant here is that it's a best effort to encrypt packet lengths confidential because this makes traffic analysis harder but not impossible. Anyway, you can usually infer message lenghts by timing and by looking at how messages are split into lower level protocol messages (if it starts a second TCP packet, it was probably a second message). The only way to prevent leaking lengths is by padding messages. TLS1.3 supports this actually but I'm not aware that anyone uses it.

I agree with @elichai. Given that OpenSSH does it, I assume more people have looked into this?!

A more high-level comment is that given that BOLT has "overtaken" the progress here, it may be a good idea to steal some of their stuff, and if it's only key derivation etc. I think there's no need to reinvent the wheel ever time. (I hate to say this because I know progress is slow here anyway.)

@ariard

This comment has been minimized.

Copy link

@ariard ariard commented Jun 17, 2020

Reading "Two seperate cipher instances are used here so as to keep the packet lengths confidential but not create an oracle for the packet payload cipher by decrypting and using the packet length prior to checking the MAC" I don't understand an oracle on which properties of the packet it would create ? Assuming we use only K_1 and receiver must decrypt-then-MAC, if an attacker does a random truncation, a pending connection would mean length is equal superior, a closed connection would mean length is inferior. But this sounds a less effective way than byte-by-byte scenario described above. Unless we assume an attacker able to do only a one-time modification ?

Digging into SSH security analysis (circa 2006), I've found attacks on CBC mode of operation or MAC leaking information in the absence of rekeying. But nothing on MACing the length field of the binary packet. It may mean either it wasn't even considered as a theoretical attack or there are new concerns since then on authenticated protocol weaknesses which may explain BOLT8. I can't see by flipping length field byte and thus extending or truncating packet an attacker can leverage this, integrity check will fail in early steps of reception.

With regards to traffic analysis, even without looking on lower level protocols, Bitcoin one is so much characteristic (transaction size and interactivity of flooding, max-sized addr messages, block size and timing, ...) that analysis isn't that much hardened. Erlay may change this, at least for transaction propagation.

If we keep a separate key for encrypting length field, at least we should explicitly state its security purpose and known limitations.

@real-or-random

This comment has been minimized.

Copy link

@real-or-random real-or-random commented Jun 17, 2020

Reading "Two seperate cipher instances are used here so as to keep the packet lengths confidential but not create an oracle for the packet payload cipher by decrypting and using the packet length prior to checking the MAC" I don't understand an oracle on which properties of the packet it would create ?

I think the goal is that a recipient decrypting the lengths will not act as an oracle for the actual plaintexts. And this is indeed pretty clear if the lenghts are encrypted with K_1 and the actual plaintexts are encrypted with K_2. Given that hiding lengths seems to be a "best-effort" thing working against passive observers but an active attackers can learn the lengths (as we both observed in our posts), this is indeed important.

@ariard

This comment has been minimized.

Copy link

@ariard ariard commented Jun 17, 2020

Digging further in recent literature pointed to me by @elichai, it seems BIP 324 cipher isn't secure with regards to byte-counting fragmentation and fragmentation-related DoS active attacks, see https://degabriele.info/publications/Surfeit.pdf and https://eprint.iacr.org/2015/059.pdf. As we pointed out in above posts, current scheme is vulnerable to traffic analysis by active attacker to learn plaintext length.

Considering a) byte-counting fragmentation and bit flipping attacks we may add same counter-measure than OpenSSH, namely after detecting an invalid MAC wait receiving more packets until reaching MAX_PACKET_LENGTH and dropping connection at that point. Thus uniforming error cases between invalid MACs and max packet length, see Section 4.2 of 1st paper. A time-out should be implemented after first packet reception to avoid amplifying b).

Achieving a) would provide theoretically ciphertext boundary hiding security, even if you can observe timing and lower level protocols fragmentation, it wouldn't leak boundaries at the encryption layer itself. We may introduce in the future deliberate fragmentation of the ciphertext from the sender to blur further traffic analysis, at the cost of some latency.

For b) fragmentation-related DoS attacks we may add a MAC on encrypted length field generated with K_1. If length field is tampered, a probabilistic decryption to some higher range value may turn as a DoS vector, i.e allocating resources for a staling connection. Authenticating the field should prevent this behavior.

@LLFourn

This comment has been minimized.

Copy link

@LLFourn LLFourn commented Aug 24, 2020

I don't know much experience with transport encryption protocol engineering. I am basically learning as I go along. Hopefully my remarks are useful.
At a high level, I think all the primitive choices here are good and optimal for Bitcoin's requirements. Well done!

ODD secp256k1 public keys MUST be used (public keys starting with 0x02). If the public key from the generated ephemeral key is an EVEN public key (starting with 0x03), its public key SHOULD be negated and then recalculated. Only using ODD public keys makes it more complex to identify the handshake based on analyzing the traffic.

Can this just say use XOnly keys as described in BIP340 instead? This requires the x-coord is even (which starts with 0x02 I think in contradiction to this statement).

Re-keying can be signaled by setting the most significant bit in the length field before encryption. A peer signaling a rekey MUST use the next key for encrypted messages AFTER the message where the signaling has been done.

What is the motivation for explicit re-keying? It adds complexity because then you have to introduce rules for how long a key should last.
You are never going to get much security against an adversary who can adaptively own someone's machine because they saw some traffic they want to know pass through it.
Having only the 1GB rule would be sufficient to me.

@real-or-random wrote:

I think the goal is that a recipient decrypting the lengths will not act as an oracle for the actual plaintexts. And this is indeed pretty clear if the lenghts are encrypted with K_1 and the actual plaintexts are encrypted with K_2. Given that hiding lengths seems to be a "best-effort" thing working against passive observers but an active attackers can learn the lengths (as we both observed in our posts), this is indeed important.

I don't understand the concept of a "recipient decrypting lengths". Recipients decrypt the length then payload and check MAC. I don't see how to use such a recipient "as an oracle" for anything in the payload if the length and payload are encrypted with the same keystream. This seems like an important point but the motivation from the SSH document is not clear on this:

Two separate cipher instances are used here so as to keep the packet
lengths confidential but not create an oracle for the packet payload
cipher by decrypting and using the packet length prior to checking
the MAC

Isn't the correct solution here just to never do this? It seems like an easy thing to avoid doing.

@ariard wrote:

And I made the same point in PR review, but actually not MACing the length seems an issue, you may decrypt to some invalid length and therefore manipulate MAC-seek?

If you manipulate the length of the MAC won't it necessarily fail anyway because the MAC is for a message of certain length?

I have a feeling that MACing the length in BOLT-8 is just a byproduct of the way noise is designed. For each noise frame you must MAC it. Since you can't even find the MAC for the payload without the length of the message you have to send it first.
But everything you send has to have a MAC so you have to MAC the length and send it first.
If this is the case then it might be a good idea to avoid noise because of this superfluous MAC (depending on how it affects performance).

This is unfortunate because using something like noise could make the proposal more compelling since review of the general structure of the key exchange and transport encryption would have been done for us.
You could argue that openssh should provide the same standard of review since it is solving almost the same problem. The downside is that it wasn't designed as a re-usable "framework" so we have to guess a bit as to why there are separate keystreams for length and payload and no references to any extended discussion explaining it.

@real-or-random wrote:

So is confidentiality of the length the security goal here? When we develop protocols, we must state what security they should provide. Apparently the message length is not confidential against active attackers here. The draft here says "Two separate cipher instances are used here so as to keep the packet lengths confidential", which was copied from the OpenSSH doc.

I agree. Encrypting the length is justified here as part of a more general goal of keeping the packet data sent between two Bitcoin nodes as indistinguishable from random as possible. Tackling active attackers is a whole other ball game. It would be good if room for doing that can be left for a future BIP because they will need further research and I think this BIP is useful enough without them.

@sipa has an idea here that would be DH more indistinguishable. I'm not sure how appropriate he may think it is for BIP324 https://gist.github.com/sipa/29118d3fcfac69f9930d57433316c039

@ariard wrote:

For b) fragmentation-related DoS attacks we may add a MAC on encrypted length field generated with K_1. If length field is tampered, a probabilistic decryption to some higher range value may turn as a DoS vector, i.e allocating resources for a staling connection. Authenticating the field should prevent this behavior.

I can't imagine how probabilistic tampering of message lengths could be a DoS vector. If it was then you could just connect to someone and DoS them the same way by sending them long messages.

@real-or-random

This comment has been minimized.

Copy link

@real-or-random real-or-random commented Aug 26, 2020

@LLFourn

x-only public keys: Indeed, that's a natural choice. This draft simply predates BIP340.

re-keying: I agree, only having the 1GB rule needs less logic and avoids fingerprinting attacks etc.

I don't understand the concept of a "recipient decrypting lengths". Recipients decrypt the length then payload and check MAC. I don't see how to use such a recipient "as an oracle" for anything in the payload if the length and payload are encrypted with the same keystream.

If you use one key, some bytes in the stream are length and some are payload. For an attack you'd somehow need to the trick the recipient into believing that a byte at a payload position is a length byte. I don't see an attack either here but if things can be very subtle. In a security proof, you would exactly need to argue that the sender and recipient agree on which bytes are length and payload, and I don't think this is trivial. Using two keys makes this problem disappear and it's much easier to argue about the construction.

Two separate cipher instances are used here so as to keep the packet
lengths confidential but not create an oracle for the packet payload
cipher by decrypting and using the packet length prior to checking
the MAC

Isn't the correct solution here just to never do this? It seems like an easy thing to avoid doing.

How would you avoid it (without MACing the lengths)?

If you manipulate the length of the MAC won't it necessarily fail anyway because the MAC is for a message of certain length?

You mean "If you manipulate the length of the message"? I think your argument is correct but again, I think MACing the length gives us a protocol which is easier to analyze. Then you just don't need to think about what happens if the attacker plays around with the message lengths. MAC will fail, easy.

If this is the case then it might be a good idea to avoid noise because of this superfluous MAC (depending on how it affects performance).

Symmetric crypto is so cheap, why not just MAC everything?

Encrypting the length is justified here as part of a more general goal of keeping the packet data sent between two Bitcoin nodes as indistinguishable from random as possible

I'm not sure. Hiding message lengths can be an interesting goal on its own (but it seems hard, see above). I think this is different from censorship-resistance/having a pseudorandom byte string.

@sipa has an idea here that would be DH more indistinguishable. I'm not sure how appropriate he may think it is for BIP324 https://gist.github.com/sipa/29118d3fcfac69f9930d57433316c039

Yeah, that gist is somewhat outdated. If we want this, then the proper solution is to use Elligator squared as pointed out by one of the comments there. I think Pieter was just not aware of Elligator Squared. But after some discussions, we're converging towards making a pseudorandom byte string a non-goal. (This is somewhat inconsistent with the odd keys requirement but this one is just super cheap to do, I don't know.)

@LLFourn

This comment has been minimized.

Copy link

@LLFourn LLFourn commented Sep 3, 2020

@real-or-random

If you use one key, some bytes in the stream are length and some are payload. For an attack you'd somehow need to the trick the recipient into believing that a byte at a payload position is a length byte. I don't see an attack either here but if things can be very subtle. In a security proof, you would exactly need to argue that the sender and recipient agree on which bytes are length and payload, and I don't think this is trivial. Using two keys makes this problem disappear and it's much easier to argue about the construction.

Yes, I think that likely captures what the ssh devs were thinking.
While perhaps not trivial it does seem straightforward to prove the sender and receiver will agree on the position of the lengths. The fixed size length is at the beginning of each frame and each frame is terminated by a MAC. If the sender and receiver were to disagree on the position of any of the 3-byte lengths then they must also disagree on the length of the last payload because the length comes immediately after the last payload in terms of the keystream. However, if they disagree on the length of the last payload then the receiver must have accepted a MAC for a different payload that the sender did not send i.e. it has been forged.

Symmetric crypto is so cheap, why not just MAC everything?

I don't deal with symmetric crypto much so I don't have biases tuned to it. My general bias is against using cryptographic primitives unless they can actually be proved to do something for security (hopefully with a proof reducing to some property of the primitive). It's the same feeling I have against having to hash everything to 32 bytes in BIP340 before signing them.

I'm not sure. Hiding message lengths can be an interesting goal on its own (but it seems hard, see above). I think this is different from censorship-resistance/having a pseudorandom byte string.

I think I'm convinced that encrypting the length does close to nothing. I don't think it's quite nothing since it at least makes it harder to see how many frames were involved in a particular burst of communication and therefore what kind of messages were being sent.

Yeah, that gist is somewhat outdated. If we want this, then the proper solution is to use Elligator squared as pointed out by one of the comments there. I think Pieter was just not aware of Elligator Squared. But after some discussions, we're converging towards making a pseudorandom byte string a non-goal. (This is somewhat inconsistent with the odd keys requirement but this one is just super cheap to do, I don't know.)

Using XOnly keys is justified without reference to pseudorandomness IMO.
It's good to know that Elligator squared makes this possible with secp256k1.

@jonasschnelli

This comment has been minimized.

Copy link
Owner Author

@jonasschnelli jonasschnelli commented Sep 8, 2020

@ariard:

For b) fragmentation-related DoS attacks we may add a MAC on encrypted length field generated with K_1. If length field is tampered, a probabilistic decryption to some higher range value may turn as a DoS vector, i.e allocating resources for a staling connection. Authenticating the field should prevent this behavior.

The max package size is 8MB (length field is 23bits). If an attacker tempers with the length field and provokes an invalid decryption, isn't that similar to the status quo of V1 where an attacker can do the same (even with larger packets) and provokes infinite SHA256 calculations (which are on most machines pretty much the ~same level as our AEAD)?

As for a) I agree on unifying the error path for invalid MAC and oversized packets.

@ariard

This comment has been minimized.

Copy link

@ariard ariard commented Sep 9, 2020

re-keying : sounds we'll agree on sticking to 1 GB only ? Better to not rely on local clock.

From @real-or-random

You mean "If you manipulate the length of the message"? I think your argument is correct but again, I think MACing the length gives us a protocol which is easier to analyze. Then you just don't need to think about what happens if the attacker plays around with the message lengths. MAC will fail, easy.

I'm sharing the lean here. We can come up with a practical way to exploit tampering of length field, but if it's computationally cheap to do better to have it.

From @LLFourn

I think I'm convinced that encrypting the length does close to nothing. I don't think it's quite nothing since it at least makes it harder to see how many frames were involved in a particular burst of communication and therefore what kind of messages were being sent.

Letting length in plaintext is lowering the cost for any passive attacker to discover messages exchanged. I agree that's a marginal cost as of today if you assume ability to observe network layer activity from your victim. But in the future it would be beneficial if a day we work on synthetic traffic or path-aware routing.

From @jonasschnelli

The max package size is 8MB (length field is 23bits). If an attacker tempers with the length field and provokes an invalid decryption, isn't that similar to the status quo of V1 where an attacker can do the same (even with larger packets) and provokes infinite SHA256 calculations (which are on most machines pretty much the ~same level as our AEAD)?

You may have a hanging-out-connection-for-free as tampering might be lower in resources committed by an attacker compare to sending huge messages. But thinking further that's the same DoS cost for the victim than plainly dropping packets. It results as a victim has peer resources allocated for nothing. Not that much we can do if we assume network capabilities attacker, so you're right not worthy to worry further.

@jonasschnelli

This comment has been minimized.

Copy link
Owner Author

@jonasschnelli jonasschnelli commented Sep 10, 2020

@ariard @real-or-random

I'm sharing the lean here. We can come up with a practical way to exploit tampering of length field, but if it's computationally cheap to do better to have it.

If I get this approach right, it would require to MAC the encrypted length separately. Adding 16 bytes to each message. I'm less worried about the additional computational requirements but more about the bandwidth impact. Especially in pruned mode, almost 50% of the messages are <64 bytes. Where the 16byte additional MAC would have a significant impact on the bandwidth/traffic (probably ~>+10%).
Of course, if we have to do this, then that's it.

I still haven't seen practical attack possibilities via tempering the encrypted length field. Plus, wouldn't that also be a concern for the @openssh chacha20poly1305 AEAD? Is there a rational why they haven't MACed the length field?

I'm sorry if I repeat questions.

@jonasschnelli

This comment has been minimized.

Copy link
Owner Author

@jonasschnelli jonasschnelli commented Sep 10, 2020

@LLFourn

This comment has been minimized.

Copy link

@LLFourn LLFourn commented Oct 11, 2020

I stumbled across this design for "NoiseSocket" an extension to the noise protocol which is opinionated about lengths: https://raw.githubusercontent.com/noiseprotocol/noisesocket_spec/master/output/noisesocket.pdf

Note it does not MAC the length separately.

On an unrelated point, I just noticed that in BOLT-08 it makes a similar "decryption oracle" claim to the one made by the openssh devs about their double key thing.

In order to make traffic analysis more difficult, the length prefix for all encrypted Lightning messages is also encrypted. Additionally a 16-byte Poly-1305 tag is added to the encrypted length prefix in order to ensure that the packet length hasn't been modified when in-flight and also to avoid creating a decryption oracle.

https://github.com/lightningnetwork/lightning-rfc/blob/master/08-transport.md

I am either missing something basic about authenticated encryption or there is some powerful "decrption oracle" folklore embedded in people's minds around length fields.

@jesseposner

This comment has been minimized.

Copy link

@jesseposner jesseposner commented Oct 12, 2020

This blog post by Damien Miller the author of the chacha20-poly1305@openssh.com commit looks like it might shed some light on why there is no MAC for the length:

An active attacker can still play games by fiddling with the packet lengths, but doing so will reveal nothing about the packet payloads themselves - they can make the receiving end read a smaller or larger packet than intended, but the MAC will be checked (and the check will fail) before anything is decrypted or used.

So it sounds like there is no separate MAC for the length because if the length is modified then the MAC on the packet payload will fail to verify.

@real-or-random

This comment has been minimized.

Copy link

@real-or-random real-or-random commented Oct 13, 2020

So it sounds like there is no separate MAC for the length because if the length is modified then the MAC on the packet payload will fail to verify.

Yes, indeed, and this confirms our intuition.

I believe we should reach out to more people who worked on this. We're not the first to think about these subtleties and there's no need to reinvent the wheel.

@jesseposner

This comment has been minimized.

Copy link

@jesseposner jesseposner commented Oct 13, 2020

I believe we should reach out to more people who worked on this.

I will reach out to Damien Miller to see if he can provide more clarity on the "decryption oracle" claim. I will also ask if he can review this BIP for any general thoughts.

@jesseposner

This comment has been minimized.

Copy link

@jesseposner jesseposner commented Oct 14, 2020

But after some discussions, we're converging towards making a pseudorandom byte string a non-goal.

@real-or-random Do you think that making the keys pseudorandom should be a non-goal in the context of this BIP? If so, I'd be curious to hear the reasons because at first glance it seems like it would be useful.

@sipa

This comment has been minimized.

Copy link

@sipa sipa commented Oct 14, 2020

@jesseposner A reason to not care too much about pseudorandom keys is that Bitcoin P2P traffic has other ways in which it can be identified, such as traffic patterns, correlation with times that blocks are found, and almost universal usage of port 8333. Unless there is an actual plan through which these can be addressed (which seems very hard), it seems like a waste of effort to try to avoid this 1-bit leak as well.

@jesseposner

This comment has been minimized.

Copy link

@jesseposner jesseposner commented Oct 14, 2020

It might be useful to document the justification of using secp256k1. For example, Curve25519 potentially has some safety features that could be useful here. I suspect that adding a dependency outweighs any potential benefits from other curves, but it would be nice to make that explicit.

@jesseposner

This comment has been minimized.

Copy link

@jesseposner jesseposner commented Oct 14, 2020

@jesseposner A reason to not care too much about pseudorandom keys is that Bitcoin P2P traffic has other ways in which it can be identified, such as traffic patterns, correlation with times that blocks are found, and almost universal usage of port 8333. Unless there is an actual plan through which these can be addressed (which seems very hard), it seems like a waste of effort to try to avoid this 1-bit leak as well.

Ah, that makes sense. Thanks!

@jesseposner

This comment has been minimized.

Copy link

@jesseposner jesseposner commented Oct 15, 2020

Damien Miller confirmed that the reason for an independently keyed cipher instance for the length is not to prevent a known attack, but more as a risk mitigation strategy by avoiding giving the attacker access to a plaintext/ciphertext pair for the packet payload key:

Stream ciphers like chacha20 aren't subject to the same decryption oracle attacks as block ciphers like AES-CBC, but abundance of caution and all...

(He also mentioned that the rekeying might be on the conservative side for chacha20, and that the HKDF for key derivation is an improvement on SSH's KDF.)

So I think the issue can be described as follows: an attacker might learn the length, for example, with a bit-flipping attack, in which case the attacker would learn the plaintext and ciphertext of the length, and thus the length becomes a decryption oracle for the key used to encrypt the length. By using an independently-keyed cipher instance, the attacker might learn the ciphertext of the packet payload (by first learning the length), but would not learn any plaintexts for the packet payload key.

@LLFourn

This comment has been minimized.

Copy link

@LLFourn LLFourn commented Oct 16, 2020

Damien Miller confirmed that the reason for an independently keyed cipher instance for the length is not to prevent a known attack, but more as a risk mitigation strategy by avoiding giving the attacker access to a plaintext/ciphertext pair for the packet payload key

Nice! Thanks @jesseposner. That solves an important piece of the puzzle. This confirms that it was defensive engineering rather than some subtle attack that he figured out.

(He also mentioned that the rekeying might be on the conservative side for chacha20, and that the HKDF for key derivation is an improvement on SSH's KDF.)

Does anyone who has studied ChaCha20 actually recommend re-keying at all? it seems like it might be some more folklore. SSH has certainly used ciphers which must re-key like 3DES but I can't find anyone saying you should re-key ChaCha20 (after all it's a completely different design so maybe it doesn't need it?).

So I think the issue can be described as follows: an attacker might learn the length, for example, with a bit-flipping attack, in which case the attacker would learn the plaintext and ciphertext of the length, and thus the length becomes a decryption oracle for the key used to encrypt the length. By using an independently-keyed cipher instance, the attacker might learn the ciphertext of the packet payload (by first learning the length), but would not learn any plaintexts for the packet payload key.

This doesn't make sense to me. I think it sounds like leftover thinking from protecting against padding oracle attacks which he mentions. i.e. If you don't even decrypt any part of the plaintext before checking the MAC then obviously nothing can go wrong. I don't think it's so hard to see that you can get the same assurance using one key. Consider a modification to the following:

The AEAD is constructed as follows: for each packet, generate a Poly1305 key by taking the first 256 bits of ChaCha20 stream output generated using K_2, an IV consisting of the packet sequence number encoded as an LE uint64 and a ChaCha20 block counter of zero

To use only one key to decrypt a packet you just take the first 35 = 32 + 3 bytes. Use the 3 bytes to decrypt the length, then use the 32 bytes to check the MAC. If they validate you then decrypt the plaintext using the remaining bytes of the stream. Observe that these 35 bytes are always fixed at the block 0 of the the stream indexed by the packet sequence. It is guaranteed that no plaintext overlaps with these bytes since they always start after the 35th byte. Since the MAC key implicitly commits to the packet sequence you are always authenticating and decrypting in the same order as the sender intended. IMO Nothing can go wrong™

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.