[bitcoin-dev] Overhauled BIP151

[bitcoin-dev] Overhauled BIP151

[Jonas Schnelli]

[-- Attachment #1: Type: text/plain, Size: 3316 bytes --]

Hi

During work on the implementation of BIP151 [1] I figured out that the current
published proposal could be further optimized.

I wrote an overhauled BIP151 specification with some – partially radical –
changes.

Now it’s unclear to me if this should be published under a new BIP nr. or if it
is acceptable to change the existing 151 proposal.
If a new BIP number would be required, I think withdrawing BIP151 should be
done (which somehow indicates we should alter 151).

The only BIP151 implementation I’m aware of is the one from Armory [2].
BCoins implementation has been removed [3].

The new proposal draft is available here:
https://gist.github.com/jonasschnelli/c530ea8421b8d0e80c51486325587c52

Major changes
=============
- the encryption handshake no longer requires the v1 protocol, it’s a pure
  32bytes-per-side „pseudorandom" key exchange that happens before anything else.
- the multi message envelope has been removed.
- a new NODE_ENCRYPTED service bit
- the key derivation and what communication direction uses what key is now more
  specific
- the length of a packet uses now a 3-byte integer with 23 available bits
- introduction of short-command-ID (ex.: uint8_t 13 == INV, etc.) which result in
  some v2 messages require less bandwidth then v1
- rekeying doesn’t require a message and can be signaled in the most
  significant bit in the packet-size field


Points that are in discussion and may be added to the BIP (or to a new one):

Hybrid NewHope key exchange
===========================
The current ECDH key exchange is vulnerable to Shor’s algorithm and is thus not
considered quantum-safe.
Following TORs approach [4] by adding a NewHope [5] key-exchange the handshake
protocol would very likely make the encryption PQ safe with little costs.
There is also a straight forward implementation [6] from the NewHope team that
has been submitted to NIST PQC project.

Inefficiency of ChaCha20Poly1305@openssh
========================================
The proposed AEAD could eventually be further optimized.
ChaCha20Poly1305@openssh uses at least three rounds of ChaCha20 which
eventually can be reduced to two (messages below <=64 bytes [inv, ping,
pong,...] only require one round of ChaCha20, but two for the Poly1305 key and
the message length encryption where the Poly1305 key chacha round „throws away“
32 bytes).


I would suggest that we don’t rehash discussions about the general
concept of encrypting the traffic. This has already been discussed [7][8].

I hope we can limit this thread to discuss further ideas for optimisation as well as
technical details of the published proposal or its implementation.


[1] https://github.com/bitcoin/bitcoin/pull/14032
[2] https://github.com/goatpig/BitcoinArmory/pull/510
[3] https://github.com/bcoin-org/bcoin/commit/41af7acfd68b0492a6442865afd439300708e662
[4] https://gitweb.torproject.org/user/isis/torspec.git/plain/proposals/XXX-newhope-hybrid-handshake.txt?h=draft/newhope
[5] https://eprint.iacr.org/2015/1092
[6] https://github.com/newhopecrypto/newhope

[7] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-February/013565.html
[8] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-June/012826.html


Thanks

[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [bitcoin-dev] Overhauled BIP151

[Eric Voskuil]

Without commenting on the other merits of either proposal, the addition of the service flag resolves bip151’s previously-discussed lack of backward compatibility.

e

> On Sep 3, 2018, at 21:16, Jonas Schnelli via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> Hi
> 
> During work on the implementation of BIP151 [1] I figured out that the current
> published proposal could be further optimized.
> 
> I wrote an overhauled BIP151 specification with some – partially radical –
> changes.
> 
> Now it’s unclear to me if this should be published under a new BIP nr. or if it
> is acceptable to change the existing 151 proposal.
> If a new BIP number would be required, I think withdrawing BIP151 should be
> done (which somehow indicates we should alter 151).
> 
> The only BIP151 implementation I’m aware of is the one from Armory [2].
> BCoins implementation has been removed [3].
> 
> The new proposal draft is available here:
> https://gist.github.com/jonasschnelli/c530ea8421b8d0e80c51486325587c52
> 
> Major changes
> =============
> - the encryption handshake no longer requires the v1 protocol, it’s a pure
>  32bytes-per-side „pseudorandom" key exchange that happens before anything else.
> - the multi message envelope has been removed.
> - a new NODE_ENCRYPTED service bit
> - the key derivation and what communication direction uses what key is now more
>  specific
> - the length of a packet uses now a 3-byte integer with 23 available bits
> - introduction of short-command-ID (ex.: uint8_t 13 == INV, etc.) which result in
>  some v2 messages require less bandwidth then v1
> - rekeying doesn’t require a message and can be signaled in the most
>  significant bit in the packet-size field
> 
> 
> Points that are in discussion and may be added to the BIP (or to a new one):
> 
> Hybrid NewHope key exchange
> ===========================
> The current ECDH key exchange is vulnerable to Shor’s algorithm and is thus not
> considered quantum-safe.
> Following TORs approach [4] by adding a NewHope [5] key-exchange the handshake
> protocol would very likely make the encryption PQ safe with little costs.
> There is also a straight forward implementation [6] from the NewHope team that
> has been submitted to NIST PQC project.
> 
> Inefficiency of ChaCha20Poly1305@openssh
> ========================================
> The proposed AEAD could eventually be further optimized.
> ChaCha20Poly1305@openssh uses at least three rounds of ChaCha20 which
> eventually can be reduced to two (messages below <=64 bytes [inv, ping,
> pong,...] only require one round of ChaCha20, but two for the Poly1305 key and
> the message length encryption where the Poly1305 key chacha round „throws away“
> 32 bytes).
> 
> 
> I would suggest that we don’t rehash discussions about the general
> concept of encrypting the traffic. This has already been discussed [7][8].
> 
> I hope we can limit this thread to discuss further ideas for optimisation as well as
> technical details of the published proposal or its implementation.
> 
> 
> [1] https://github.com/bitcoin/bitcoin/pull/14032
> [2] https://github.com/goatpig/BitcoinArmory/pull/510
> [3] https://github.com/bcoin-org/bcoin/commit/41af7acfd68b0492a6442865afd439300708e662
> [4] https://gitweb.torproject.org/user/isis/torspec.git/plain/proposals/XXX-newhope-hybrid-handshake.txt?h=draft/newhope
> [5] https://eprint.iacr.org/2015/1092
> [6] https://github.com/newhopecrypto/newhope
> 
> [7] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-February/013565.html
> [8] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-June/012826.html
> 
> 
> Thanks
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Overhauled BIP151

[Tim Ruffing]

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

Re: [bitcoin-dev] Overhauled BIP151

[Gregory Maxwell]

On Thu, Sep 6, 2018 at 11:33 PM Tim Ruffing via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> Now you can argue that the attacker is storing encrypted traffic today to decrypt it later.

That is the argument. We know for that state level parties are storing
unimaginable amounts of data for future decryption, that threat isn't
theoretical.

> Sure,
> but if that's your threat model then Bitcoin is probably not the right tool for you. (And if

Why not?

> you insist that Bitcoin is the right tool, then you can and probably should use it over Tor
> anyway.)

Currently, Tor provides _no confidentiality at all_ in that threat
model.  Part of why I think this enhancement is interesting is because
without it BIP151 doesn't actually add anything for those p2p
connections running over Tor, but with it -- it at least adds some
long term confidentiality hedge.

> It's not worth the hassle, would hinder adoption,

Why do you say this?

> impression of "bulletproof" security. Even worse, there will be too many people that will suddenly
> assume that Bitcoin is post-quantum secure.

People already make that claim with respect to public key hashing.  I
don't think "we shouldn't improve security because someone will
mistake an improvement for perfection" is an an especially interesting
argument.

> 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

Here is where I turn the argument around on you:   This requires
writing a non-trivial amount of moderately complex new cryptographic
code (which is not the case for PQ schemes-- that merely requires
dropping in pre-existing code) and yet I am not aware of any attack
model that this which would any improvement in actually delivered
security:  Bitcoin traffic is _trivially_ identifiable by its traffic
patterns.

(Blockstream  previously wrote the SW forward transform for asset
generation, but this requires the inverse too, as well as glue code.
It also isn't clear to me if it's possible to make this construction
constant time, which would be okay for BIP151 purposes but if we
wanted to have a generic uniform encoder in libsecp256k1 I think we'd
prefer it be constant time? maybe?)

The scheme in the BIP thus far achieves the property that there are no
fixed bytes for brain-dead byte matching DPI traffic filtering or
anti-virus to match on (or accidentally false positive on).  AV false
positives are already an existing problem with the current protocol
and any fixed bytes in the communication are at risk for false
positives or targeted filtering.   And achieving that property
requires basically nothing: a test for the first byte of a generated
serialized pubkey and a negate on the private key if it was wrong.

> key. Together with the encrypted packet lengths, the entire data stream looks like random then,

No, it doesn't-- due to traffic analysis.  Including, for example, the
pattern that 64-bytes must be sent in each direction, before further
data continues, bursts of traffic coinciding with blocks newly found
on the network, etc.

I don't believe that indistinguishable keys are actually useful
outside of the context of things like stegnographic embedding-- cases
where protocol 'metadata' doesn't tell you that a key is there
regardless.

I suppose if the code already existed to do it I might as well go
"okay, sure why not", it's not going to harm anything (the added
computation time to generate the uniform encoding would probably be no
more than a 10% slowdown).  I wouldn't argue against it on the basis
that someone might believe it resulted in anti-censorship properties
that it doesn't have ... even though it's clearly the case... because
I categorically reject that form of argument. :)

I think your view on the two distinctive proposals is askew: PQ
agreement has a clear benefit under a plausible threat model and is
quite easy to implement... while uniform encoding is somewhat harder
to implement (though admittedly not very hard) but doesn't appear to
provide a concrete benefit under any threat model that I'm currently
aware of...

> 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.

I also prefer the contributory key model, but Pieter proved me on IRC
last week that the attack form that I was concerned about was not
possible.

Do you actually have an attack in mind that you can spell out here?  I
don't see a harm in changing that, but given that I'd already twice
talked myself out of proposing the same thing, I'd like to understand
if I'm missing something. :)

> Re-keying
> =========
> The problem with signalling re-keying in the length field is that the length field is not covered
> by the MAC.

It's AAD data in the mac, unless I misunderstand the protocol.

> Deterministic rekeying rules may be better. Otherwise there will be implementations that rekey
> every 10 seconds

That would be pretty harmless, since the rekeying operation costs
similar to one message decryption.

> and implementations that just don't rekey at all (rendering the 10 s rekeying
> interval in the opposite direction useless).

The protocol requires rekeying at least after a given amount of data
is transmitted. Peers that violate that can be disconnected. But it
could be unfortunately infrequent.

> Different policies also make it possible to
> fingerprint implementations.

I agree that is a good point.

Personally I'd prefer that we used a ciphersuite that effectively
"rekeyed" every message-- along the lines of the constructions
described https://blog.cr.yp.to/20170723-random.html   Unfortunately I
was unable to find _any_ well analyized  authenticated encryption mode
that has the fast erasure property.   It's too bad because it would be
trivial to adhoc one (e.g. use the extra 32 bytes from the poly1305
chacha run to update the keys for the next message).

> What's better: 5 min or 30 min? I don't know, but both are reasonable choices. (Thats's very much

It doesn't much matter, except for fingerprinting reasons.

> like discussions about ciphers... What's better AES-GCM or ChaCha20/Poly1305? I don't know, but
> again both are reasonable choices.)

Here we have a very clear motiviation.  On devices without hardware
AES/clmul constant time AES-GCM is _terribly slow_ compared to
ChaCha20/Poly1305. Performance on the slowest devices is where the
the ones where the ciphersuite choice likely matters at all (because
it could actually make a meaningful difference in their system's
ability to keep up), and the slowest devices that I'm aware of users
commonly using are also devices without good AES-GCM performance.
Unfortunately.

On fast desktop hardware the performance of AES-GCM and
ChaCha20/Poly1305 is also fairly close.

So when it matters, chacha20/poly1305 is higher performance by a wide
margin.  (Too bad, because otherwise I'd much rather use AES-GCM)

> 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.)

This can be done at the message level. E.g. new TX messages that round
tx sizes up to the next multiple. I don't think useful low overhead
padding is otherwise possible.


> written in stone, again to avoid complexity and to avoid fingerprinting.

Writing things in stone is a great way to never finish a protocol.
Right now we know we have new upcoming proposals for messages where
the overhead matters, e.g. we need a replacement addr message ASAP,
and there is ongoing work for transaction relay that would also
benefit from low overhead.

The norm in Bitcoin is to ignore messages you don't know how to parse
anyways,  so there is no complexity that arises from "may negotiate"
itself-- only from actually making use of that possibility in the
future, so the merits of any particular usage could be decided when
something wants to actually use it.  The purpose of pointing out "may
negotiate" is, I think, primarily to avoid a debate about who would
assign numbers from this limited space in the future-- and the answer
just is that they're implementation defined (e.g. by the BIPs using
them).

> 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.

Right, encryption kills external analysers in any case. It's also easy
to just logprintf traffic (this is open source software after all),
which doesn't have a decoding problem.

>  - "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"?

I think it says 'received there' mostly because it's implicitly
telling you that you can hang up on someone who violates it. I agree
it would be more consistent to express it sending side there.

Re: [bitcoin-dev] Overhauled BIP151

[Jonas Schnelli]

[-- Attachment #1: Type: text/plain, Size: 5938 bytes --]

Hi Tim

Thanks for the feedback.

I agree with all of Gregs answers.

> 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.)

All-or-none censorship attacks are out of scope for BIP151.
We won’t achieve DPI robustness in this proposal and I think it should not be part of the p2p protocol.

I think all-or-one censorship situations require an additional layer like TOR with OBFS4 (where AFAIK Eligator is used).
Eventually Core does directly support non-tor routed pluggable transports (it's partially already possible via SOCK proxy, but not on a gossip and plugin-launch level).

This does not exclude that we should obfuscate the key exchange as good as we can without blowing up the implementation too much.

The proposed encryption adds a robustness to the thread model with very little costs and low risks.

>   "salt = BitcoinSharedSecret||INITIATOR_PUBKEY||RESPONDER_PUBKEY" should just avoid this issue.

This is a good point and I’d like to see more concrete examples how this (the non dynamic salt) could be exploited.

> 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.

In ChaCha20Poly1305@openssh, the length field is AAD, encrypted with a different key and part of the MAC.

> 
> 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.)

The Rekey cost is two times a double-SHA256,… the costs of a rekey is similar to one or two v1 INV message creations.

> 
> 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.)

I think a new message type that could contain message + pad would be trivial.
Would this again be to obfuscate traffic patterns? Anti DPI is not the scope of BIP151.

> 
> 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.

I wanted to avoid too much central planing here and only cover the ones where it's most efficient (small messages that are used often).
The ASCII commands are in itself somehow pseude-robust against collision.
For a 1MB block message, using a 1-byte short ID (rather then a 6-byte ASCII command) would reduce the bandwidth requirement insignificant (99.99952%).

If we would always have used short IDs in the past, there could have been a collision between XTIN, compact, sendheaders or so.

> 
> 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?

Good points. Will make them more clear in the BIP.
I was under the false impression that it is obvious to disconnect in those cases.

> - How is a 64-bit nonce formed from one (two?) uint32?

That’s specified in ChaCha20Poly1305@openssh ("a nonce consisting of the packet sequence number encoded as a uint64“).
But I’ll specified that more clear.

> - What if the uint32 overflows?

The max data before rekey is 1GB, AFAIK it is impossible to overflow.

> - "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?

Current implementation proposal does a disconnect. With the risk of fingerprinting options, I think we can leave this open to the implementation?

> - "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“?

Yes. Should probably be „sent“,… and eventually a paragraph that states that a peer should disconnect if the remote peer did not rekey within that limit.

> Pseudocode could probably help here.

Agree. Will try to add.


[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [bitcoin-dev] Overhauled BIP151

[Tim Ruffing]

On Fri, 2018-09-07 at 02:31 +0000, Gregory Maxwell wrote:
> Currently, Tor provides _no confidentiality at all_ in that threat
> model.  Part of why I think this enhancement is interesting is
> because
> without it BIP151 doesn't actually add anything for those p2p
> connections running over Tor, but with it -- it at least adds some
> long term confidentiality hedge.
> 
Okay, sure, I was assuming that Tor will deploy it at some point. No
idea what the status is.

> > It's not worth the hassle, would hinder adoption,
> 
> Why do you say this?
My assumption is that NewHope is harder to implement. If you just 
drop-in existing code, it's not. And I've neither implemented NewHope
nor Elligator Squared, so I may just be wrong.

> 
> > impression of "bulletproof" security. Even worse, there will be too
> > many people that will suddenly
> > assume that Bitcoin is post-quantum secure.
> 
> People already make that claim with respect to public key hashing.  I
> don't think "we shouldn't improve security because someone will
> mistake an improvement for perfection" is an an especially
> interesting
> argument.

I don't like the argument either but I think it's real.

> (Blockstream  previously wrote the SW forward transform for asset
> generation, but this requires the inverse too, as well as glue code.
> It also isn't clear to me if it's possible to make this construction
> constant time, which would be okay for BIP151 purposes but if we
> wanted to have a generic uniform encoder in libsecp256k1 I think we'd
> prefer it be constant time? maybe?)
No idea if it can be made constant time but yeah I think it's not
crucial in this case.

> 
> I don't believe that indistinguishable keys are actually useful
> outside of the context of things like stegnographic embedding-- cases
> where protocol 'metadata' doesn't tell you that a key is there
> regardless.

I wasn't specific but my point is that these are indeed interesting
future directions. You can easily make the traffic look like any other
protocol which uses encryption. That's a really useful property if you
want to avoid censorship, even if traffic analysis still works. That's
true even if this it's not in the scope of this BIP, which is of course
the case.

If you ask me, that is more interesting than protecting against
potential decryption of P2P connections in a few decades. But I don't
have a definitive argument for this of course.


> I also prefer the contributory key model, but Pieter proved me on IRC
> last week that the attack form that I was concerned about was not
> possible.
> 
> Do you actually have an attack in mind that you can spell out
> here?  I
> don't see a harm in changing that, but given that I'd already twice
> talked myself out of proposing the same thing, I'd like to understand
> if I'm missing something. :)

I don't have a harmful example but here is harmless one (that you
probably know because it's really the simplest one can think of):

A             M             B 
   -- aG -->
                 <-- bG --
                  -- aG -->
  <-- bG --

Now A and B share the same session id but any attempt to communicate
will fail because they both think that they're the initiator. Of course
that's not a big deal because M is in neither of those sessions. So
it's not an attack but it's a weird property of the key exchange. But I
think it's desirable to avoid such things if the cost to do so is very
low.

Also, here is a better argument:

A             M             B 
   -- aG -->
                 <-- bG --
  <-- xG --
                  -- yG -->

After B's message, M's goal is create a collision of the session ids.
Since M can freely choose x and y, that's a birthday attack on the hash
function and needs 2^(l/2) work if the session id is l bits long.

Telegram has (had?) the same issue:
https://www.alexrad.me/discourse/a-264-attack-on-telegram-and-why-a-super-villain-doesnt-need-it-to-read-your-telegram-chats.html

With the other variant, M cannot collect both aG and bG upfront:

A             M             B 
   -- aG -->
                  -- yG -->
                 <-- bG --
  <-- xG --

Now M can only choose x, so this is a second-preimage attack and takes
2^l work. So with the this variant, you can have a session id that's
only half the size. That's a real difference if session ids are meant
to be comparable by humans, e.g., over the phone. 

(I think) it's possible to even go further with a 3-way handshake:
A                M                B 
   -- H(aG) -->
                    -- H(yG) -->
                   <--  bG   --
  <--  xG   --
   --  aG   -->
                    --  yG   -->

Here M has no flexibility at all, so the probability of a successful
attack against a single key exchange is just 2^(-l). This is similar to
ZRTP. I'm not saying that we should do this, it's something worth
noting that.

  
> 
> > Re-keying
> > =========
> > The problem with signalling re-keying in the length field is that
> > the length field is not covered
> > by the MAC.
> 
> It's AAD data in the mac, unless I misunderstand the protocol.

Oh nevermind.

> Personally I'd prefer that we used a ciphersuite that effectively
> "rekeyed" every message-- along the lines of the constructions
> described https://blog.cr.yp.to/20170723-random.html   Unfortunately
> I
> was unable to find _any_ well analyized  authenticated encryption
> mode
> that has the fast erasure property.   It's too bad because it would
> be
> trivial to adhoc one (e.g. use the extra 32 bytes from the poly1305
> chacha run to update the keys for the next message).

That adhoc construction is a very interesting idea. Hm... Just fyi, the
closest that comes to my mind is:
https://core.ac.uk/download/pdf/20880831.pdf

> The norm in Bitcoin is to ignore messages you don't know how to parse
> anyways,  so there is no complexity that arises from "may negotiate"
> itself-- only from actually making use of that possibility in the
> future, so the merits of any particular usage could be decided when
> something wants to actually use it.  The purpose of pointing out "may
> negotiate" is, I think, primarily to avoid a debate about who would
> assign numbers from this limited space in the future-- and the answer
> just is that they're implementation defined (e.g. by the BIPs using
> them).

Yeah, my point was not to write the entire list in stone. That was not
really clear from my message, sorry. Of course, new message types can
be added later. But I don't see a big advantage in allowing both ASCII
strings and short IDs. So I wanted to say that the usage of short IDs
should be written stone.

On Fri, 2018-09-07 at 10:34 +0200, Jonas Schnelli wrote:
> 
> > 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.)
> 
> I think a new message type that could contain message + pad would be
> trivial.
> Would this again be to obfuscate traffic patterns? Anti DPI is not
> the scope of BIP151.

Well, it's indeed to obfuscate traffic patterns but primarily for
confidentiality. If I see the length of the message, I can guess the
message type fairly well for example. (That's not no matter if my goal
as an attacker is to break your privacy or to censor your connection.
Of course more confidentiality helps also against DPI/censorship but
that was not my point here.)

> I was under the false impression that it is obvious to disconnect in
> those cases.

Yeah I think it's by far the most natural thing to do but it may be
better to make it explicit.

Tim