Re: [bitcoin-dev] Overhauled BIP151
On Thu, Sep 6, 2018 at 11:33 PM Tim Ruffing via bitcoin-dev 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"
Re: [bitcoin-dev] Overhauled BIP151
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
Re: [bitcoin-dev] Overhauled BIP151
On Fri, 2018-09-07 at 02:31 +, 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: AMB -- 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
Re: [bitcoin-dev] Overhauled BIP151
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
Re: [bitcoin-dev] Overhauled BIP151
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 > 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 ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
[bitcoin-dev] Overhauled BIP151
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 signature.asc Description: Message signed with OpenPGP ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
