Skip to content

Instantly share code, notes, and snippets.

@jonasschnelli
Last active November 14, 2022 13:22
Show Gist options
  • Save jonasschnelli/c530ea8421b8d0e80c51486325587c52 to your computer and use it in GitHub Desktop.
Save jonasschnelli/c530ea8421b8d0e80c51486325587c52 to your computer and use it in GitHub Desktop.

  BIP: 324
  Layer: Peer Services
  Title: Version 2 Peer-to-Peer Message Transport Protocol
  Author: Jonas Schnelli <dev@jonasschnelli.ch>
          Dhruv Mehta <dhruvkaran@pm.me>
  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.

Objectives and Motivation

Add end-to-end encryption: The current Bitcoin p2p protocol(referred to as v1 in this document) is 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].[2]

Increase observability of attacks:: Adding opportunistic encryption as described in this document, introduces a high risk for attackers of being detected. Peer operators can compare encryption session IDs or use other form of authentication schemes [3] to identify an attack.

Add encryption without computation overhead: Each v1 p2p 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 v2 p2p message with ChaCha20 & Poly1305.

Add encryption without risk of network partition: Implementing this proposal maintains compatibility between v1 peers and v2 peers. There should be no risk of network patitions.

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[4].

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

The encryption handshake MUST happen before any other messages are exchanged between the peers. A shared secret is established at the end of the Elliptic Curve Diffie-Hellman(ECDH) handshake.

Both communication directions have different symmetric cipher keys deterministically derived from the same shared secret.

If the responding peer closes the connection after receiving the handshake request, the initiating peer MAY try to connect again with the v1 p2p 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.

Signaling BIP324 support

Peers supporting the transport protocol proposed here MUST signal the NODE_P2P_V2 = (1 << 11) service flag. Such peers MUST accept encrypted communication specified in this proposal.

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

Peers MAY make outbound connections exclusively 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 0x03). If the public key from the generated ephemeral key is an EVEN public key (starting with 0x02), its private key SHOULD be negated and then recalculated. Only using ODD public keys makes it more complex to identify the handshake based by analyzing the traffic and looking for 33 bytes that start with 0x02 or 0x03. This in turn increases the cost of censorship.

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

To aid identification of the v2 handshake from a v1 p2p message, 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

ecdh_priv_key = MakeNewKey()
for {
    ecdh_pub_key = ecdh_priv_key.GetPubKey()
    if (ecdh_pub_key[0] == 2) {
        // Public key is even, negate the private key and try again
        ecdh_priv_key.Negate();
    } else if (ecdh_pub_key[0..3] == NETWORK_MAGIC) {
        // Public key cannot start with the network magic bytes
        ecdh_priv_key = MakeNewKey();
    } else {
        break;
    }
}

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.[5]

After a successful v2 handshake, both peers:

  • MUST use the v2 message structure described in this document. Unencrypted v1 messages from either peer MUST lead to an immediate connection termination.
  • MUST wipe the ephemeral session key from memory and persistent storage.
A v1 peer will not perform the described handshake and will send a v1 version message to initiate a connection. v2 peers supporting this BIP MAY optionally allow unencrypted v1 communication by detecting a v1 version message by the initial 11-byte sequence of NETWORK_MAGIC || "version".

Keys and Session ID Derivation

The authenticated encryption construction proposed here requires two ChaCha20Forward4064-Poly1305 cipher suite instances per communication direction. Each cipher suite instance requires a 256-bit key. We derive the four required keys from the established ECDH secret (ECDH_KEY = SECP256k1_ECDH(X,y) = SECP256k1_ECDH(x,Y)) known to both peers after the handshake. The keys MUST be derived with HKDF [6] as shown below. Peer A is the handshake initiator, peer B is the responder.

Both peers MUST also calculate the 256-bit session id, SID.

// Convert ECDH_KEY input key material into a pseudo-random key using HKDF extract.
PRK = HKDF_EXTRACT(hash=SHA256, salt="BitcoinSharedSecret||INITIATOR_32BYTES_PUBKEY||RESPONDER_32BYTES_PUBKEY||NETWORK_MAGIC", ikm=ECDH_KEY)

// Derive 32 byte keys used to encipher data A-> B
K1A = HKDF_EXPAND(prk=PRK, hash=SHA256, info="BitcoinK_1_A", L=32)
K2A = HKDF_EXPAND(prk=PRK, hash=SHA256, info="BitcoinK_2_A", L=32)

// Derive 32 byte keys used to encipher data B -> A
K1B = HKDF_EXPAND(prk=PRK, hash=SHA256, info="BitcoinK_1_B", L=32)
K2B = HKDF_EXPAND(prk=PRK, hash=SHA256, info="BitcoinK_2_B", L=32)

// Derive session id
SID = HKDF_EXPAND(prk=PRK, hash=SHA256, info="BitcoinSessionID", L=32)

Detecting MITM attacks

The v2 protocol is based on ECDH key exchange and cannot prevent MITM attacks. However, comparing the session id SID derived by both peers on a secure channel can help authenticate the session and make any MITM attacks observable.

v2 peers supporting this BIP, MUST present the session id to the user on request.

ChaCha20Forward4064-Poly1305@Bitcoin Cipher Suite

Existing cryptographic primitives

BIP324 leverages two cryptographic primitives designed by Daniel Bernstein:

ChaCha20 PRF

The ChaCha20 PRF (pseudo-random function)[7] takes as input: (1) 128 fixed bits (2) 256 bits of key material (3) a 64 bit IV/nonce and (4) a 64 bit counter and outputs: 512 pseudo-random bits. We will represent it as ChaCha20PRF(key, iv, ctr)

The ChaCha20 PRF can be composed into the ChaCha20 DRBG (deterministic random bit generator) to produce a keystream by incrementing the counter up to 2^70.

ChaCha20DRBG(key, iv) = ChaCha20PRF(key, iv, ctr=0) || ChaCha20PRF(key, iv, ctr=1) || ...

The ChaCha20 DRBG thus constructed does not provide forward and backward security in case of a compromised key. i.e if an attacker learns the key, they can decrypt all passively collected past and future ciphertext. This proposal outlines a new DRBG construction, the ChaCha20Forward4064 DRBG described below to add forward and backward security.

Poly1305 MAC

Poly1305 [8] 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.

New cryptographic primitives

ChaCha20Forward4064 DRBG

Assuming a node sends only ping messages (28 bytes in the v2 protocol) every 20 minutes (the timeout interval for post-BIP31 connections) on a connection, the node will transmit 4064 bytes in a little over 2 days. To provide forward and backward security, we propose re-keying the ChaCha20 DRBG every 4064 bytes of keystream. Once 4064 bytes of keystream from the ChaCha20 DRBG has been consumed, the next 32 bytes are used to re-key the cipher instance before continuing to obtain up to another 4064 bytes of keystream. The IV is initialized to 0 and incremented on every re-key event.

k0 = key
iv = 0
ks0, k1 = ChaCha20DRBG(k0, iv)[0:4064], ChaCha20DRBG(k0, iv)[4064:4096]
iv = iv + 1
ks1, k2 = ChaCha20DRBG(k1, iv)[0:4064], ChaCha20DRBG(k1, iv)[4064:4096]
...
ChaCha20Forward4064DRBG(key) = ks0 || ks1 || ks2 || ...

Both peers MUST keep track of the re-keying sequence numbers (uint64) to set as the ChaCha20 IV upon re-keying.

ChaCha20Forward4064-Poly1305@Bitcoin combines the ChaCha20Forward4064 DRBG(using it as a stream cipher by XORing the DRBG keystream with the plaintext or ciphertext) and the Poly1305 MAC into an authenticated encryption mode with addition of encryption of the packet lengths. The detailed construction follows.

Detailed Construction

The ChaCha20Forward4064-Poly1305@Bitcoin cipher suite requires two 256-bit keys from the key exchange per communication direction. Each key (K1 and K2) is used by two separate instances of a ChaCha20Forward4064 DRBG. We will call the instances F(used for fixed-length purposes, using 35 bytes per message) and V(used for variable length purposes).

F = ChaCha20Forward4064DRBG(key=K1)
V = ChaCha20Forward4064DRBG(key=K2)

Packet Handling

When encrypting a message M of length len(M) bytes:

  1. Read 3 bytes from the DRBG instance, F, XOR them with the 3-byte litte endian encoding for len(M) and set the result as ciphertext C.
  2. Read len(M) bytes from V, XOR them with the len(M) bytes of M and append the result to C.
  3. Read 32 bytes from F and use it to instantiate a Poly1305 MAC, P.
  4. Compute a 16 byte MAC tag of contents in C using P. Append the tag to C. C is now the content that can be transmit to maintain confidentiality, integrity and optionally, authentication.
When receiving a packet with ciphertext and MAC, called C:

  1. The length MUST be decrypted when 3 bytes of ciphertext have been received. Read 3 bytes from the DRBG instance, F, XOR them with the first 3 bytes of the ciphertext. Interpret the resulting bytes as the little endian encoding of len(M)
  2. Read 32 bytes from F and use it to instantiate a Poly1305 MAC, P.
  3. Compute a 16 byte MAC tag of contents in C[0:3 + len(M)] and compare it to the 16 bytes at C[3 + len(M):]. The byte comparison must be done in a constant time manner. If the expected MAC tag differs from the provided MAC tag, the connection MUST be immediately terminated.
  4. Read len(M) bytes from V and XOR them with C[3:3 + len(M)] to obtain the plaintext.
The initiating peer MUST use F(K1A), V(K2A) to encrypt messages on the send channel, F(K1B), V(K2B) MUST be used to decrypt messages on the receive channel.

The responding peer MUST use F(K1A), V(K2A) to decrypt messages on the receive channel, F(K1B), V(K2B) MUST be used to encrypt messages on the send channel.

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 semantics analysis)

Optimized implementations of ChaCha20Forward4064-Poly1305@bitcoin are relatively fast, therefore it is unlikely that encrypted messages will require additional CPU cycles per byte when compared to the v1 p2p message format (double SHA256).

AEAD Test Vectors

TODO: Update the test vectors after swapping k1/k2 in code

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

ciphertext
76 b8 e0 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

MAC
df cd 91 c8 75 ee 88 71 8b 63 34 5d 75 0c 68 4a
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

ciphertext
77 b8 e0 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 

MAC
fb 6c f9 dc d7 e2 ee 80 7d 5f f9 81 eb 4a 13 5a
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

ciphertext
39 40 c1 c8 68 cd 14 5b d5 46 91 e9 b6 b4 02 c7 8b d7 ea 9c 37 24 fc 50 df c6 9a 4a 96 be 8d ec 4e 70 e9 58 18 8a a6 92 22 ea ef 3f 47 f8 00 3f 1b c1 3d cf 9e 66 1b e8 e1 b6 71 e9 cf 46 ba 70 5b ca 96 3e 04 77 a5 b3 c2 e2 c6 6f eb 82 07 26 9d db 01 b1 37 2a ad 68 56 3b b4 aa d1 35 af b0 6f be 40 b3 10 b6 3b ef 57 8f f9 39 f3 a0 0a 6d a9 e7 44 d2 8b a0 70 29 4e 57 46 d2 ca 7b b8 ac 2c 8e 3a 85 5a b4 c9 bc d0 d5 85 5e 11 b5 2c ac aa 2d db 34 c0 a2 6c d0 4f 4b c1 0d e6 dc 15 1d 4e e7 ce d2 c2 b0 de 8d ed 33 ff 11 f3 01 e4 02 75 59 e8 93 8b 69 bc eb 1e 5e 25 9d 41 22 05 6f 6a db d4 8a 06 28 b9 12 f9 0d 72 83 8f 2f 3a af 6b 88 34 2c f5 ba c3 cb 68 8a 9b 0f 7a fc 73 a7 e3 ca d8 e7 12 54 c7 86 ea 00 02 40 ae 7b d1 df 8b cf ca 07 f3 b8 85 72 3a 9d 7f 89 73 64 61 

MAC
7a c8 d9 35 a4 1b f9 54 64 32 36 0e 1c 54 37 08

v2 Messages Structure

Field Size Description Data type Comments
3 length 24 bits Encrypted length of ciphertext payload (not counting the 16 byte MAC tag or the 3 byte encrypted length) in number of bytes
1-13 encrypted message-type variable ASCII message-type (or one byte message-type-ID)
? encrypted payload ? The actual data
16 MAC tag ? 128bit MAC-tag

The v2 message structure does not need the 4byte network magic. The HKDF key derivation process embeds the network magic bytes into the salt for the extraction step. Using a different network identifier in that step will result in different derived keys per network.

The maximum message size is 2^24 (16’777’216) bytes. Future communication MAY exceed this limit and thus MUST be split into different messages.

The 4 byte sha256 checksum in v1 messages is no longer required because the MAC tag provides integrity and authentication.

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

Message-Type-ID

To save valuable bandwidth, the v2 message format supports message-type-IDs. 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 message-type-IDs based on the table below and SHOULD use message-type-IDs for outgoing messages.

Number Message Type
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
39 GETCFILTERS
40 CFILTER
41 GETCFHEADERS
42 CFHEADERS
43 GETCFCHECKPT
44 CFCHECKPT
45 WTXIDRELAY
46 ADDRV2
47 SENDADDRV2

Length comparisons between v1 and v2 messages

v1 inv: 4(Magic)+12(Message-Type)+4(MessageSize)+4(Checksum)+37(Payload) == 61
v2 inv: 3(MessageSize)+1(Message-Type)+37(Payload)+16(MAC) == 57
(93.44%)

v1 ping: 4(Magic)+12(Message-Type)+4(MessageSize)+4(Checksum)+8(Payload) == 32
v2 ping: 3(MessageSize)+1(Message-Type)+8(Payload)+16(MAC) == 28
(87.5%)

v1 block: 4(Magic)+12(Message-Type)+4(MessageSize)+4(Checksum)+1’048’576(Payload) = 1’048’600
v2 block: 3(MessageSize)+1(Message-Type)+1’048’576(Payload)+16(MAC) = 1’048’596
(99.9996%)

Test Vectors

TODO: Update the test vectors after swapping k1/k2 in code

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
sequence: 0

Message before encryption
01 00 00 25

Ciphertext (3byte AD, 1byte message-type, 16 bytes MAC)
77 b8 e0 53 14 05 09 d3 48 60 7a 07 58 00 77 44 be 48 21 ef
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
sequence: 0

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

Ciphertext (3byte AD, 1byte message-type-id, 4 byte message payload [ping nonce], 16 bytes MAC)
73 b8 e0 69 f8 02 ac a0 19 62 2f 1a 1d d3 d3 be de 22 2e d9 ff 17 51 40

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 [3].

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. ^ Encrypting traffic between peers is already possible with VPN, tor, I2P, stunnel, curveCP or any other encryption mechanism on a networking layer below the application, however, most of those solutions require significant technical experience in setting up a secure channel and are therefore not widely deployed.
  3. a b BIP150
  4. ^ RFC 2119
  5. ^ 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.
  6. ^ HKDF (RFC 5869)
  7. ^ ChaCha20
  8. ^ Poly1305

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.

@sipa
Copy link

sipa commented Nov 19, 2020

Alternatively you could just increment the IV and reset the block counter after each 4096 byte chunk. This is aesthetically pleasing to me because then you could just make the next key always be the first 32 bytes of block=0 rather than the last 32 of a 4096 byte boundary. This is also what noise does:

I like the idea of resetting the counter but incrementing IV every 4064(4096) bytes. That makes the output of the rekeying stream cipher just a concatenation of 4064 bytes out of 4096-byte consecutive messages for the underlying stream cipher. (technically I don't think there is a reason to even increment the IV, as updating the key also has a progress effect - but by incrementing the IV, we guarantee that even if the key ends up in a cycle, the stream output doesn't).

It's orthogonal to the question of using the first or last 32 bytes, though. I used the last 32 bytes because it means a very-low-memory or very-low-latency implementation is possible that doesn't precompute, and doesn't need to remember the future key or compute a block twice.

@jonasschnelli
Copy link
Author

@sipa:

Every packet draws 35 bytes from M (32 bytes for poly1305, 3 bytes for length encryption), and N bytes from the P stream (for payload encryption). Everything is byte-aligned; there is no 21 lengths per counter increment or so; just use all output bytes.

Is there a reason why you switched the stream cipher instance for the poly1305 key?
ChaCha20-Poly1305@openssh as well as this current proposal take the poly1305 key from the payload cipher instance (and not from the length encryption cipher instance). I don't know it if makes a difference but was wondering if you had a reason for that change.

@gmaxwell
Copy link

Poly and length use a fixed number of bits per messages sent while payload is variable, so changing lengths can't cause either set of bits to get misinterpreted as the wrong kind. Keeping them separate I think is much more obvious in its protection against decryption failure from acting as an oracle for the other key-stream. E.g. corrupting the length of the prior packet won't cause the receiver to use a different but highly related poly1305 key for this packet.

I think it also has a side benefit of making the usage of the two streams more equal which would make the secrecy duration more uniform in the case where the implementation isn't computing the streams ahead and forgetting the initial values.

@jonasschnelli
Copy link
Author

jonasschnelli commented Jan 19, 2021

I have changed this document (including the test vectors) to adapt the internal 4096byte rekeying rule. Thanks for an additional review.
Implementation of that new AEAD is here: bitcoin/bitcoin#20962

@sipa
Copy link

sipa commented Jan 20, 2021

@jonasschnelli Cool, happy to see progress here.

As for explaining the protocol, perhaps it's clearer if it's described as a number of layers? The current flat description makes it a bit hard to see the big picture.

Layers I can think of:

  • Existing cryptographic primitives used:
    • The ChaCha20 PRF: a function from (in our usage) 256-bit key, 64-bit IV to a byte sequence (up to 2^70 bytes)
    • The Poly1305 MAC: a function from a single-use 256-bit key and a variable-length message to a 128-bit authenticator
  • The ChaCha20/forward4064 PRF: a function taking a 256-bit key and producing a byte sequence:
    • This is constructed by starting with k0=key and concatenating:
    • c0=ChaCha20(key=k0, IV=0)[0:4096]; call k1=c0[4064:4096]; output c0[0:4064]
    • c1=ChaCha20(key=k1, IV=1)[0:4096]; call k2=c1[4064:4096]; output c1[0:4064]
    • ...
  • The bitcoin cipher stream, taking as input two 256-bit keys k1 and k2 up front, and then a sequence of variable-length messages that are converted into a byte stream.
    • At initialization time, instantiate two ChaCha20/forward4064 PRFs called F (fixed, with key k1) and V (variable, with key k2).
    • To encode, for every message M with length L:
      • Read 3 bytes from F, which are XOR'ed with the 24-bit LE encoding of L, and output.
      • Read 32 bytes from F, which are used to instantiate a Poly1305 MAC P with that key
      • Feed the 3 unencrypted (or encrypted?) length bytes into P (this is the additional data part of the AEAD). Anything else? Perhaps the network magic? This part seems unspecified in the current text. We may want this padded to a multiple of 16 bytes, so that the ChaCha20 32-byte blocks align with the Poly1305 blocks.
      • For every byte B in M:
        • Read 1 byte from V, XOR it with B, and output it.
        • Feed the resulting byte (B xor V) into P.
      • Compute the 16-byte authenticator from P and output it.
    • To decode, ...
    • (this isn't actually a AEAD anymore, as there is no discernible per-message encryption/authentication, and things only make sense when described as operating on a sequence of messages. I don't think this is a problem, but it may be worth explaining. It probably also explains some of the oddities in the openssh protocol, which still can be described more or less on a per-message basis)
  • The overall protocol which consists of:
    • ECDH negotiation
    • Instantiating two cipher streams (one in each direction), using the two derived HKDF-derived keys from the ECDH output
    • Switching over to the application protocol, with a particular packet layout (each packet is command, either 1 byte or spelled out, plus payload), turning every packet into one

I think using this kind of structure makes it easier to explain the various design decisions and rationale for every step.

@LLFourn
Copy link

LLFourn commented Feb 1, 2021

It's exciting to see this new design moving along. Thanks @jonasschnelli.

I was wondering what people thought of the idea of using the ECDH + transport encryption described here for applications other than Bitcoin p2p e.g. Lightning or other Bitcoin L2 protocols. We can easily anticipate many layer 2 protocols will need an encrypted transport. The DLC group is already in need of a proposal. Although it would be possible to re-use some parts of BOLT-8 the 2-byte max frame length that noise enforces means they cannot map authenticated frames to messages as they do in lightning (DLCs require quite large messages). I've also heard this is also a bit of a nuisance for LN developers in sending large routing messages (but I don't know the details and would happy to be corrected).

The only difficulty is that these protocols will often need authentication against static public keys e.g. Lightning. Also I guess Bitcoin p2p may want authentication at some point in the future? I am not suggesting we include how authentication should work here but I was wondering what others thought it could look like. It would be nice if the spec here could be modular so the line between Bitcoin p2p and the key exchange + transport message encryption bit were very clear.

@gmaxwell
Copy link

gmaxwell commented Feb 1, 2021

The way auth is accomplished has already been covered in other old drafts, you authenticate a hash of the session key inside the encrypted session.

@sipa and I had intended to propose a fairly novel ZKP that, in the context of bitcoin p2p like usage, would prevent an attacker from knowing if authentication was in use at all-- greatly increasing the risk of detection for large scale active observers. This avoids the problem in more traditional protocols where an evesdropper just drop the connection and let the connection re-establish without interception when they detect authentication is in use. ( https://gist.github.com/sipa/d7dcaae0419f10e5be0270fada84c20b .. I think thats the latest update on that? )

The nice thing about authenticating an encrypted session is that it fits nicely with doing whatever adaptive application supported and potentially user interactive stuff you might want to do. The down side is that it may require an additional protocol round trip-- totally irrelevant for long lived connections like in Bitcoin, but I presume that is a reason that separation of concerns isn't more common in established standards.

@gmaxwell
Copy link

gmaxwell commented Feb 2, 2021

@LLFourn out of curiosity, are you aware of any protocol that works like this: An authentication scheme like poly1305 produces a 256-bit authentication tag and 96 bits of it are emitted in the message, but then the remaining 160 bits are fed in as the initial state of the authenticator for the next message. As a result even though the probability of accepting a false single message is the kind-of-high 1:2^96 the probability of not disconnecting at a subsiquent message becomes extremely low extremely fast.

@sipa
Copy link

sipa commented Feb 2, 2021

@gmaxwell Poly1305 only has 128-bit auth tags, so it isn't that much of a difference.

@LLFourn Yeah, this proposal grew out of an earlier one that added both encryption and (optional, obviously) authentication. The encryption part became this document, and the authentication part turned into the optional authentication scheme that @gmaxwell came up with originally and linked to. Have a look, it's pretty cool. Once we're a bit further here I'll try to get working on that again.

@jonasschnelli That brings me to this: I remember having discussions with @gmaxwell and @real-or-random about an ability to request protocol upgrades before the application-level stuff starts. This could be used for e.g. augmenting the protocol (say, a PQC key negotiation) but may also allow doing authentication early instead of inside the application layer. I don't remember the details, but for now it may suffice to just say: the side that is creating the connection (outbound) must start by sending an (properly encrypted, ...) empty packet (or some specific thing) to indicate "we're done negotiating". Anything else can then be reserved for future updates. Thoughts?

@LLFourn
Copy link

LLFourn commented Feb 9, 2021

@gmaxwell

The way auth is accomplished has already been covered in other old drafts, you authenticate a hash of the session key inside the encrypted session.

Seems reasonable. Although, this does leak some information over what noise does. Receiving the signature allows you to convince a third party that you (or someone) did indeed establish a connection with the party.

There is a cool trick I found reading Damgard's notes on witness indistinguishable sigma protocols [1]. Instead of proving I know secret key for X, I can prove that I know the secret key for X OR the DH shared secret. Since the verifier knows I don't know the secret key for the shared secret the verifier is convinced of the same thing (i.e. I know the secret key for X). However they cannot re-use the proof to convince anyone else because no one else could be convinced that the DH key is unknown to them.

I am not sure that this is a practical issue though.

@sipa and I had intended to propose a fairly novel ZKP that, in the context of bitcoin p2p like usage, would prevent an attacker from knowing if authentication was in use at all-- greatly increasing the risk of detection for large scale active observers. This avoids the problem in more traditional protocols where an evesdropper just drop the connection and let the connection re-establish without interception when they detect authentication is in use. ( https://gist.github.com/sipa/d7dcaae0419f10e5be0270fada84c20b .. I think thats the latest update on that? )

I think I had seen this briefly -- it looks cool. Having authenticated connections covertly probe for interception is a nice idea esp in the case of Bitcoin p2p. I wonder if it achieves the property I mentioned above against a malicious verifier just because of its structure.

The nice thing about authenticating an encrypted session is that it fits nicely with doing whatever adaptive application supported and potentially user interactive stuff you might want to do. The down side is that it may require an additional protocol round trip-- totally irrelevant for long lived connections like in Bitcoin, but I presume that is a reason that separation of concerns isn't more common in established standards.

This is what I was thinking too. Looking at what is done in the noise XK [2] that lightning uses I don't think there actually would be an extra round of communication doing in session auth with a simple signature (or WI proof).

@LLFourn out of curiosity, are you aware of any protocol that works like this: An authentication scheme like poly1305 produces a 256-bit authentication tag and 96 bits of it are emitted in the message, but then the remaining 160 bits are fed in as the initial state of the authenticator for the next message.

I haven't seen anything like this. I haven't studied how Poly1305 works at all so I have no idea what's gonna happen when you use it in a non-black-box way :)

[1] https://www.cs.au.dk/~ivan/Sigma.pdf (end of Section 7).
[2] http://www.noiseprotocol.org/noise.html#handshake-patterns

@jonasschnelli
Copy link
Author

@dhruv is taking over this BIP (with my help [and others] in the background).
I just updated this gist to @dhruv latest version (https://gist.github.com/dhruv/5b1275751bc98f3b64bcafce7876b489).

@LLFourn
Copy link

LLFourn commented Aug 18, 2021

I made the decision to post my comments over on the @dhruv's gist since I guess that's where further updates will go for now?

@michaelfolkson
Copy link

@dhruv's gist is currently a fork of this one. Agreed, it would be nice to know which one is the intended latest draft of the BIP from this point onwards.

@dhruv
Copy link

dhruv commented Aug 23, 2021

Yes, let's communicate on my fork for now and treat that as the latest draft.

There's another feature in development. Once we have that in the draft, I'll move the conversation over to the mailing list and create a PR into the bips repository.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment