Topic: Is it possible to create a message readable only to the owner of an address? (Read 2696 times)

Like others have stated that im sure a program could be made to do this, but the question is why would you want to? Its much easier to just use pgp. Now, it was easy to do with the blockchain and the infrastructure that we have, then I think it would be great, but it wasn't built that way, could they build it into the code? probably, but I think there are more important things that need to be done first.

Not quite. The receiver needs to decrypt the message before checking the hash, which creates a difference in timing for "valid hash, bad message" and "invalid hash" so it is potentially possible for an attacker to guess messages and use timing to glean information. If there are error messages or observable behavioural differences, these could be used instead of timing. Also there are possibly things like length-extension attacks on the hash function. In fact, regardless of hash function strength, by exposing a hash of the message to the public, you run the risk of predictable messages being found by brute forcing a preimage of the hash. Using an HMAC (a) blocks potential regularity problems in the hash function, e.g. length extension, (b) doesn't give the public any information about the message, regardless of its predictability, (c) allows you to put the authentication on the ciphertext, avoiding the timing problem above.

Note that timestamps are low-entropy and can probably be confined to a small range using public information for most applications.


Thanks, glad we're on the same page .

Yes I believe I understand that.  I thought that by comparing the hash time-stamped in the message-notification TX to the hash of the encrypted message, that the receiver could immediately reject all modified messages (so that the response of a decryption oracle to any attack would be silence.)


Agreed.  It's important to be rigorous with proposed cryptosystems to avoid serious problems if such systems are implemented haphazardly and without proper peer-review.   You, Greg and several others here do a very good job with that.  I think that the discussions like this are still useful because it helps people learn about this interesting field, and perhaps we might make a bit of real progress from time to time too.  

Is this CCA-secure? (I dunno ... I would guess so in the random oracle model, but I wouldn't build a cryptosystem based on a guess.) Rather than using a plain old hash, an HMAC keyed with the shared secret would be better. This lets you apply authentication after the encryption, to avoid running afoul of "encrypt-then-MAC, never MAC-then-encrypt" as well as to avoid using multiple channels for a single message (which increases your attack and analysis surface significantly). Using a MAC-then-encrypt scheme is a very dangerous idea, so don't do it.


These aren't theoretical attacks. Any reaction to a marred ciphertext except outright immediate rejection will be used in a real attack. The only "theory" here is modeling the attack using a decryption oracle, but that's just a formal way of describing "any reaction to a marred ciphertext". Cryptography is broken unless proven secure, and if it has been proven secure, it should be assumed broken until it has been both audited by experts and used in the real world.

I'm describing problems with your scheme to give you an idea of the subtleties involved in designing cryptosystems. I'm a finite being and you should have no problem designing a system that will satisfy me by simply running through all the concerns I can think of. This will not give you a secure cryptosystem. It will give you a system that is as secure as I can design while communicating over the English language (which is very lossy) and without devoting any time to working through the details. So I can't give you specific attacks on specific implementations...this is unfortunate from a didactic perspective, but says nothing about the security of your system.

Edit: To be clear, you aren't being dense. This is really tricky stuff. But I want to say "these are the things you should be thinking about when thinking about crypto" without saying "it's safe under any circumstances to create your own crypto".

Right.  But what if Alice includes a hash of the message in the OP_RETURN-you-have-a-message TX [I probably don't have enough bytes in the OP_RETURN, but let's ignore that for now].  Wouldn't any message that gets scrambled by an attacker be detected since its hash wouldn't match what's embedded in the message-notification TX timestamped in the blockchain?  And an attacker clearly can't fake a message-notification TX without knowledge of Alice's private key.  

I apologize if I'm being dense and missing something obvious; it sounds like there's still a weakness I just don't really "get it" in the sense that I can see a practical attack against this specific implementation (rather than what seems to be a theoretical attack that involves oracles).    

The idea is that the attacker could modify the message along it's way from the messenger to the address controller. Or more likely, snoop the message off the wire or the blockchain or wherever, tweak it, and submit it separately. In either case the attacker can submit a message he doesn't know (except that it is a real message corrupted in some predictable way) and observe the address owner's response.

Note that even with a CCA-secure encryption scheme, messages should have a timestamp or nonce or something to prevent simple replay attacks.

Thank you kindly for taking the time to write such an in depth response.  It was very helpful and I learned something about the lens through which professional cryptographers view encryption systems.  I believe I can see that this messaging scheme is not secure against a chosen cyphertext adversary (CCA).  

It's still not completely clear to me why, if the goal is to send the message to the controller of a bitcoin address rather than to "Bob," we can't view this as an authenticated channel.  I suppose it comes down arguing security along the lines of "oh, well, as long as the user only does this, or the attacker can only do that, or..."

Snooping around, it seems that certain altcoins have implemented "encrypted messaging schemes" similar to this [which of course says nothing about their security ]

In academic cryptography you want well-defined security against arbitrary adversaries with well-defined powers. To make these useful in the real world, we try to make the definition of "security" as strong as possible: typically you want "indistinguishability", meaning that if the attacker gives you two messages of his choosing, and you reply with the encryption of one, he cannot tell which one with probability significantly different from 1/2. Here "significantly different" roughly means "goes to zero very quickly as you increase the bit security of the cryptosystem".

Two standard sets of adversary powers are

• Chosen plaintext adversary (CPA, "semantic security", "passive attacker"): The attacker has access to all the public parameters and public keys. He can therefore encrypt whatever he likes before and after submitting his two messages for encryption.
• Chosen ciphertext adversary (CCA, "active attacker"). The attacker also has access to a decryption oracle. Here before and after submitting two messages for encryption, he can also submit arbitrary ciphertexts for decryption to see what he gets back. The only rule is, after receiving the challenge encryption, he can't submit this to the decryption oracle!

These are deliberately very general. If you are arguing security along the lines of "oh, well, as long as the user only does this, or the attacker can only do that, or..." then you've got two problems. The first is that it's probably really hard to argue security rigorously under such an ad hoc definition. The second is that the security of your system now depends on exactly the way that it's used. This means that every change to the surrounding context of your system (e.g. how is the message transmitted, which messages are legal, who has access to what keys, etc., etc.) is now potentially a security bug. Nobody can do this kind of analysis continuously so you are screwed. A classic example of this sort of problem is the crazy mess that is TLS. That blog post also talks about encrypt-then-authenticate vs authenticate-then-encrypt, which is actually a instance of this CPA security being used where CCA security is needed.

Roughly, what CCA security means is that given a ciphertext, there is somehow a way to prove that it is a "real" ciphertext. (Not a way to prove that the ciphertext came from the right person, mind you, that is what Crowex is talking about. Just that it's not deliberately mangled in an effort to learn about its contents. As a simple example, suppose your cryptosystem was "derive an ephemeral shared secret C, then coerce the message M to a curvepoint and the encryption is CM". Believe it or not, simple multiplication like this is the basis for most CPA-secure systems --- you can see, if C is random to the attacker, then CM will be too, so the attacker sees the encryption as random data, and therefore cannot learn about the message well enough to tell one from the other with probability different from 1/2. But in the CCA game, this is easily broken. As the attacker, this is what I do: submit two messages M, M' and receive an encryption C. Submit 2C to the decryption oracle and receive a decryption P. Then P/2 was the original message.

What's interesting is that given a CPA-secure encryption system it is basically always possible to "bootstrap" this into a CCA-secure system. For example the Naor-Yung system (gzipped postscript --- anyone have a PDF link?. Maybe try Naor's website which has a link at "Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks", but this is broken for me.) works by encrypting the same message twice using different public keys, and providing a zero-knowledge proof that they are the same message. The trick is that the zero-knowledge proof requires knowledge of the shared secret (more specifically, knowledge of the random nonce used in the encryption --- it is not relevant to Naor-Yung that this randomness is used to generate an ephemeral shared secret). So when I try to do something sneaky like taking a ciphertext C and submitting 2C, I won't be able to make a new zero-knowledge proof, and the decryption oracle will simply reject the ciphertext.

This is cool: it means that CPA-secure systems are still interesting, even if their direct use is limited to pre-authenticated channels. So a good exercise is to head to IACR's eprint archive, find some CPA-secure systems, and try to break them in the CCA game. This is almost always possible --- sometimes as easily as I described above, sometimes not.

So here's your problem: with an unauthenticated channel (like broadcasting encryptions) you need CCA security. Otherwise an attacker can submit arbitrary ciphertexts, and depending on the details of the system (remember, this dependence is deadly!), will be able to get some sort of decryption oracle. Maybe this is simply "output an error if the message is not well-formed, or its padding is not well-formed, or whatever". No matter how weak the oracle is, it's still outside of the CPA security game under which the cryptosystem was proven secure. (In fact, error messages are exactly how the original TLS timing attack I linked earlier worked!) In any case, the result is that the security of your system is basically an accident of the exact way you set it up and the exact way your users use it. So in the future, they will do something weird, and the system will be broken as a consequence.

I hope this helps clarify the original message.

 The main problem is that when you are doing the initial public key exchange in order to get a shared secret and establish a secure channel, then if you are doing this key exchange over an insecure channel, then a man in the middle could replace both Alice and Bob's public keys with ones to which he holds the private keys. Then Alice and Bob think they are talking to each other but Mallory is decrypting Alice's message, changing it if he wants and re-encrypting it with the key he has sent to Bob and doing the same with the return messages.

 It is the problem of how you perform the initial authentication and how Bob knows that the public key is from Alice in order to establish a secure channel if you don't have a secure channel in the first place. This is why this technique is not secure unless maybe you use a PKI to authenticate people in the first place but then you must place your faith in a trusted third party and you must establish a secure communication channel with them in the first place.
 Or maybe you have another method of communication to cross check the public keys but then you need to know how secure this other method is.
 Authentication is a major problem especially if you want to mix it up with anonymity.

 If you know that you want to send a message to the owner of a certain bitcoin address and you know the public key then one identity is authenticated. So Bob knows what Alice's public key is because he knows Alice has signed a transaction with the private key corresponding to that public key.
 In this situation you can perform a key exchange over an insecure channel and Bob will know that he has established a shared secret with Alice and he is communicating with the private key holder for that address. Alice has received a public key over an insecure channel and won't really have any idea who she might be talking to.

 

 

Greg told me that this method is insecure, but I still don't understand why.  Like luv2drnkbr implied above, if you know the pubkey of the address whose owner you wish to message, why can't you use the Diffie-Hellman technique to derive a symmetric key (shared secret) with which you encrypt the message?:

----------------
If the public key for the bitcoin address you want to send an encrypted message is known, then you can.  As far as I know, there are no tools that allow you to easily do this now, but they could be built.  

The encryption technique is based around the elliptic curve Diffie-Hellman protocol.  Assume Alice wants to send an encrypted message to the owner of bitcoin address B, and assume that Alice knows the pubkey for B.  

   Qa = Alice's public key
   da = Alice's private key
   Qb = public key of bitcoin address B
   db = private key of bitcoin address B

Since (da, Qa) and (db, Qb) are EC key pairs, we know that:

   Qa = da * G       and      Qb = db * G

where G is the elliptic curve base point. But look what happens when we multiply Alice's private key with the bitcoin address B's public key:

    S = da * Qb
       = da * (db * G)

It's almost the same thing as what we get when we multipy B's private key with Alice's public key:

   S' = db * Qa
      = db * (da * G)

Because points on an elliptic curve form a group, multiplication is commutative and associative (like normal multiplication).  This means that S = S':

   S = da * (db * G) = da * db * G = db * da * G = db * (da * G) = S'

I labelled this term "S" because this is a shared secret that the owner of bitcoin address B will soon know…

OK, so back to our encryption technique.  Alice hashes S to get a symmetric key:

    symmetric key = sha256(S)

and then encrypts her message using the symmetric key.

She then posts the encrypted message somewhere public, and then sends a bitcoin transaction to address B with an OP_RETURN output that specifies (using a to-be-defined set of magic bytes) that a message has been prepared and the URL where the message can be found.  Because Alice had to sign the transaction to send this message notification, it means that Qa (her public key) is now known and that the owner of address B has the required information to decrypt the message at the specified URL.  
----------------------

^^ This technique is apparently insecure.    

I think that OP wants to send message to a holder of arbitrary address without any previous communications with him.
Just broadcast some data (with special web-site or service?) which will be garbage for all of us, but a message for owner of bitcoin address.

This is basically what a stealth address is.

EC math has the property that pubkey1 * privkey2 = pubkey3, and privkey1 * pubkey2 = pubkey3.

Note that one of you always has to use a private key in order to get pubkey3.

So you can generate the shared secret pubkey3, use any kind of encryption you want, with pubkey3 as the password, and send that to them along with your own pubkey, and then they will use their private key and your public key to find the shared secret which is the password to the encrypted data.

I would think the message protocol would be pretty simple.

Assumptions:

You have the Bitcoin address and you know the Bitcoin address is controlled by the person you wish to send the message to.

The person to receive the message publishes their public key in the block chain and/or sends you a standard signed message to give you their public key.

Now you have the public key so you:

Create a random AES bulk encryption key (BEK).
Combine this one time use BEK with a known header.
Encrypt this combination using the public key.
This becomes the message header.

Encrypt the message with the random AES BEK.

Send the message header containing the encrypted BEK.
Send the encrypted message.

The receiver simply extracts the BEK from the message header with their private key and then decrypts the message with the one time use BEK.

Any holes in this?  

Sign a message using your bitcoin client; the message is your PGP/GPG public key. Have the other guy do the same.

Then use PGP/GPG.

Electrum tried to implement message encryption/decryption in their software. gmaxwell found a bug in it so the feature was disabled. The next version, which is currently under development on their github repo, seems to have that feature enabled so maybe they've figured out a way to do it safely.

Here are some example implementations for encrypting with bitcoin public keys. (Not addresses, you'll need the public key.) No idea how much you can rely on these, I'd be interested to hear opinions.

ECIES:
node.js: https://bitcointalksearch.org/topic/ann-nodejs-ecies-encrypt-messages-to-bitcoin-addresses-627927
Python: https://github.com/planetbeing/bitcoin-encrypt

Not sure what this is:
https://github.com/jackjack-jj/jeeq (Python)
From the description of it here it seems to be original, which is cool but sounds like a good reason to prefer one of the other ones...
https://bitcointalk.org/index.php?topic=196378.5

Agreed. Doesn't look very useful, but for example if you have a public donation address you could send a private message to an anonymous donator (he revealed his public key while making the tx). If you include a pgp pubic key in your message he can answer you back.

Except that you'd have to get your Bitcoin public key to them in the first place.  You can't compute a public key from a Bitcoin address.

you may have a point there
I was just thinking that it may be cool to have and easy way (like, integrated to the qt-wallet) to securely send a message while being sure that the only recipient is the one who made a specific tx on the blockchain. That message could be used for exchanging pgp keys and we'd use pgp from there on...

First you'd have to extract your public key from the client.

Then you'd have to securely get this public key somehow to the person that wants to send you a message (which reduces the security of your bitcoins a bit since they are no longer protected by the SHA256 and RIPEMD160 algorithms used to generate the bitcoin address).

Next the person that wants to send you the message would need to import that public key into some software (I think you're suggesting they import it into the Bitcoin Core client?)

After that they'd need to create the message and encrypt it.

They would send you the encrypted message which you would need to import into your Bitcoin Core client so that you could then decrypt it.

How and why is this better than using a well tested, well established, and well known system such as PGP?