Re: [bitcoin-dev] Overhauled BIP151

From: Tim Ruffing <crypto@timruffing•de>
To: Jonas Schnelli <dev@jonasschnelli•ch>,
	Bitcoin Protocol Discussion
	<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Overhauled BIP151
Date: Fri, 07 Sep 2018 01:23:21 +0200	[thread overview]
Message-ID: <061aa38d8ceeb6caaae19d7c86e435a5f86b293b.camel@timruffing.de> (raw)
In-Reply-To: <640D015D-3DDB-43C4-9752-96ADABF64C91@jonasschnelli.ch>

Hi Jonas,

Great to see progress in this area. I have quite a few comments.

Post-quantum key exchange
=========================
I think that's overkill. Bitcoin has huge problems in the presence of a quantum computer, and the
confidentiality of the P2P messages is the most minor one. If there is a quantum computer and
Bitcoin remains in its current form, then people should probably stop using it.

Now you can argue that the attacker is storing encrypted traffic today to decrypt it later. Sure,
but if that's your threat model then Bitcoin is probably not the right tool for you. (And if
you insist that Bitcoin is the right tool, then you can and probably should use it over Tor
anyway.) Given the fact that essentially all information in Bitcoin will be public in some way,
there are probably cheaper attacks (MITM, traffic analysis).

It's not worth the hassle, would hinder adoption, and it has the potential to create a wrong
impression of "bulletproof" security. Even worse, there will be too many people that will suddenly
assume that Bitcoin is post-quantum secure.

Key exchange indistinguishable from random
==========================================
I would rather love to see a simple ECDH key exchange as currently used but with an encoding of
public key that provides indistinguishability from random bitstrings. "Elligator" does not work
but "Elligator Squared" [1] does the job for secp256k1 -- it just doubles the size of the public
key. Together with the encrypted packet lengths, the entire data stream looks like random then,
which is pretty useful against censorship resistance for example. (The only exception is that the
stream will never start with the magic bytes.)

Key derivation
==============
The key derivation can be improved. It should include each peer's understanding of its role,
i.e., requester (or "initiator" is the more common term) or responder. At the moment, an attacker
can create a situation where two peers think they're in the same session (with the same session
id) but they're actually not. Also, it's possible for an attacker to rerandomize the public keys.
That's nothing bad by itself but anything which restricts the flexibility of the attacker without
adding complexity is a good idea. Something like
   "salt = BitcoinSharedSecret||INITIATOR_PUBKEY||RESPONDER_PUBKEY" should just avoid this issue.

Re-keying
=========
The problem with signalling re-keying in the length field is that the length field is not covered
by the MAC. So the attacker can flip the signalling bit. The resulting protocol is probably still
secure but the malleability is certainly not desirable.

Deterministic rekeying rules may be better. Otherwise there will be implementations that rekey
every 10 seconds and implementations that just don't rekey at all (rendering the 10 s rekeying
interval in the opposite direction useless). Different policies also make it possible to
fingerprint implementations. Another problem is that people will set their policies arbitrarily.
What's better: 5 min or 30 min? I don't know, but both are reasonable choices. (Thats's very much
like discussions about ciphers... What's better AES-GCM or ChaCha20/Poly1305? I don't know, but
again both are reasonable choices.)

Symmetric crypto
================
You call it chacha20-poly1305@bitcoin but what's the difference to the openssh then? Is the
idea to save a call to chacha here as you mentioned?

I didn't think about this in detail: maybe there are a few meaningful cases where padding could
hide the message length without too much overhead. (I'm not convinced, just a random thought.)

Misc
====
"The ID/string mapping is a peer to peer arrangement and MAY be negotiated between the
requesting and responding peer." I think that's overly complicated. I suggest it should just be
written in stone, again to avoid complexity and to avoid fingerprinting. New implementations are
necessary anyway, so maybe just use IDs for anything? ASCII is nice if you want to debug your code
or some random network failure but that's hard anyway when encryption is used.

In general, the entire thing is a little bit underspecified. (I'm aware it's just a draft.)
A few examples:
 - What should a peer do if the MAC verification fails?
 - What should a peer do if it receives an even key?
 - "Processing the message before the authentication succeeds (MAC verified) MUST not be done."
 That should also apply to the ciphertext. (Or: What is a "message"?). It may be a good idea to
 to refer to the openssh document or steal from it; it does a pretty good job.
 - "Both peers MUST keep track of the message sequence number (uint32) of sent and received
 messages for building a 64-bit symmetric cipher IV." I think you mean nonce when you say IV?
 - What is the initial value of the sequence number?
 - How is a 64-bit nonce formed from one (two?) uint32?
 - What if the uint32 overflows?
 - "Re-Keying interval is a peer policy with a minimum timespan of 10 seconds." What if I receive
 too many re-keying requests? Nothing or should I raise the DoS score?
 - "The Re-Keying must be done after every 1GB of data sent or received" Hm, every peer updates its
 own sending key, so this should just read "sent" instead of "sent or received"?

Pseudocode could probably help here.

[1] https://eprint.iacr.org/2014/043.pdf