Message Encryption with bitcoin address.

[mikewirth]

Can I encrypt a short message with a bitcoin address (public key) and send that to a person I know has the private key?  

If I use a bitcoin address to encrypt a message of only 30 characters - how long with the encrypted message be?  

How may this be done?

For example, my message is: "This is a test of my new system" and this is the public key: 12K5SyY2Z3DNsqFtTCnyGC3J7jYTCjM54m

What does the encrypted message look like and how does one arrive at making it?

[DeathAndTaxes]

No.  Bitcoin uses ECDSA which is a digital signature algorithm not an encryption algorithm.  You could use another algorithm which supports encryption however Bitcoin address is not a Public Key it is a hash of the public key.   If you need to use a third party algorithm, third party software, and exchange keys directly well you might as well use something that was designed for this purpose like PGP.

[Remember remember the 5th of November]

Can I encrypt a short message with a bitcoin address (public key) and send that to a person I know has the private key? 

If I use a bitcoin address to encrypt a message of only 30 characters - how long with the encrypted message be? 

How may this be done?

For example, my message is: "This is a test of my new system" and this is the public key: 12K5SyY2Z3DNsqFtTCnyGC3J7jYTCjM54m

What does the encrypted message look like and how does one arrive at making it?

Your best bet is to use Bitmessage.

[mikewirth]

No.  Bitcoin uses ECDSA which is a digital signature algorithm not an encryption algorithm.  You could use another algorithm which supports encryption however Bitcoin address is not a Public Key it is a hash of the public key.   If you need to use a third party algorithm, third party software, and exchange keys directly well you might as well use something that was designed for this purpose like PGP.

But could you first unhash the bitcoin address, and then use it as a public key in some encryption algorithm to encrypt my statement: "This is a test of my new system" - resulting in the only person able to decrypt it is the guy with the private key -  which happens to be the same private key used to sign bitcoin transactions?

Would that work?

[DannyElfman]

No.  Bitcoin uses ECDSA which is a digital signature algorithm not an encryption algorithm.  You could use another algorithm which supports encryption however Bitcoin address is not a Public Key it is a hash of the public key.   If you need to use a third party algorithm, third party software, and exchange keys directly well you might as well use something that was designed for this purpose like PGP.

But could you first unhash the bitcoin address, and then use it as a public key in some encryption algorithm to encrypt my statement: "This is a test of my new system" - resulting in the only person able to decrypt it is the guy with the private key -  which happens to be the same private key used to sign bitcoin transactions?

Would that work?

When you use any kind of encryption system the public key is some kind of derivative of the private key. You should be able to easily tell what your public key is based on your private key, but it should be difficult to tell what your private key is based on your public key. As discussed above the relationship between a bitcoin public key and a bitcoin private key is one that is not able to encrypt messages. 

[mikewirth]

As discussed above the relationship between a bitcoin public key and a bitcoin private key is one that is not able to encrypt messages.  

Is that really discussed above?  Is that really true?  It doesn't seem likely that these asymmetric keys can't be used for message encryption via asymmetric cryptography.  I wish I understood why that would be.

[DeathAndTaxes]

There are encryption systems which can use ECC keys.  

ECIES is one system:
https://en.wikipedia.org/wiki/Integrated_Encryption_Scheme

However a couple things to keep in mind.   I don't know of any widely deployed open source software which uses it so you will be reinventing the wheel.  Could you develop such software, extensively test it, and then ensure your recipient also has said software (doesn't do much good if the recipient isn't using it) so that you can encrypt a message using a PUBLIC KEY you obtain (not address which is a public key hash) so the recipient can decrypt it by exporting a private key from his wallet into some software he is unfamiliar with?  Probably.

It wouldn't work any better than other widely deployed systems like PGP and unless you are very good you run the risk of compromise which affects both systems.  I would by default be suspect of any software where I have to export one or more private keys from my wallet (that control MONEYZ) to a third party software in order to  decrypt a message.  Even if legit it certainly doesn't sound smart or reasonable.

But could you first unhash the bitcoin address

There is no such thing as "unhashing" a bitcoin address.  The user would have to supply you his public key not address (public key hash).  Once again it comes down to a very convoluted system for what benefit.   Just use open source software widely distributed and extensively peer reviewed like PGP.

[Peter R]

As discussed above the relationship between a bitcoin public key and a bitcoin private key is one that is not able to encrypt messages.  

Is that really discussed above?  Is that really true?  It doesn't seem likely that these asymmetric keys can't be used for message encryption via asymmetric cryptography.  I wish I understood why that would be.

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 via XOR encryption:

    encrypted_message = (clear-text message) XOR (symmetric key)

Obviously this only works for a single <= 256-bit message, but the technique can be easily extended to messages of arbitrary length¹.  

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.  


¹EDIT: the IES scheme D&T just posted is one such method of extending this technique to arbitrary-length messages: https://en.wikipedia.org/wiki/Integrated_Encryption_Scheme

  

[gmaxwell]

   encrypted_message = (clear-text message) XOR (symmetric key)

Danger! Will Robinson, Danger!

Say someone were to deploy the simple scheme you described just as you described it—  they they used it to secure queries sent to a simple web server.

I capture a message sent to them that I want to intercept, and I take the nonce out of it— but replace it with a message of my own (perhaps all zeros).

The server responds to me "INVALID REQUEST:  20iE⊥∩θ⊂∏↔θ⊂dlkvc25πδjdk⊕κ×σκk8κσ×3th7hξκδι2λσ∃KΣ‡"  ... now I xor with my 'message' and have the session keystream and can decode the message I intercepted.

Even if there isn't some handy error response I can invoke, I can still freely flip bits. "Wait, but if its in a transaction, thats signed right?"— no, I can rebind your message without knowing its content either with or without bitflips into another transaction but reuse the ephemeral key and exploit whatever interesting behavior I can squeeze out of that.

This kind of cryptosystem is often trivially insecure without strong authentication tied strongly to the ephemeral key.

Behold the kind of fun that happens when you don't get every detail just right (start reading at the second message): http://sourceforge.net/p/bitcoin/mailman/bitcoin-development/thread/5325B5BC.3030501@gmx.de/  (A cryptographic disaster (near miss) which started with a thread on this forum very much like this one, but one where more experienced folks happened to not notice it…)

[Peter R]

   encrypted_message = (clear-text message) XOR (symmetric key)

Danger! Will Robinson, Danger!

Say someone were to deploy the simple scheme you described just as you described it—  they they used it to secure queries sent to a simple web server.

I capture a message sent to them that I want to intercept, and I take the nonce out of it— but replace it with a message of my own (perhaps all zeros).

The server responds to me "INVALID REQUEST:  20iE⊥∩θ⊂∏↔θ⊂dlkvc25πδjdk⊕κ×σκk8κσ×3th7hξκδι2λσ∃KΣ‡"  ... now I xor with my 'message' and have the session keystream and can decode the message I intercepted.

Even if there isn't some handy error response I can invoke, I can still freely flip bits. "Wait, but if its in a transaction, thats signed right?"— no, I can rebind your message without knowing its content either with or without bitflips into another transaction but reuse the ephemeral key and exploit whatever interesting behavior I can squeeze out of that.

This kind of cryptosystem is often trivially insecure without strong authentication tied strongly to the ephemeral key.

Behold the kind of fun that happens when you don't get every detail just right (start reading at the second message): http://sourceforge.net/p/bitcoin/mailman/bitcoin-development/thread/5325B5BC.3030501@gmx.de/  (A cryptographic disaster (near miss) which started with a thread on this forum very much like this one, but one where more experienced folks happened to not notice it…)

I think I'm following your concern, but that's why I said:

Obviously this only works for a single <= 256-bit message, but the technique can be easily extended to messages of arbitrary length¹.  

¹EDIT: the IES scheme D&T just posted is one such method of extending this technique to arbitrary-length messages: https://en.wikipedia.org/wiki/Integrated_Encryption_Scheme  

If no one ever transmits more than a single <= 256 bit message with that session key, is there still a security problem?  Wouldn't this be an unbreakable one-time pad if only used once?  I can see the danger in sending more than one message XOR'd with the same session key, but I was just trying to explain the concept behind the Diffie-Hellman shared secret as simply as possible for a single transmission.  But perhaps I'm missing something.

[gmaxwell]

I think I'm following your concern, but that's why I said:

Obviously this only works for a single <= 256-bit message, but the technique can be easily extended to messages of arbitrary length¹.  
¹EDIT: the IES scheme D&T just posted is one such method of extending this technique to arbitrary-length messages: https://en.wikipedia.org/wiki/Integrated_Encryption_Scheme  

If no one ever transmits more than a single <= 256 bit message with that session key, is there still a security problem?  Wouldn't this be an unbreakable one-time pad if only used once?  I can see the danger in sending more than one message XOR'd with the same session key, but I was just trying to explain the concept behind the Diffie-Hellman shared secret as simply as possible for a single transmission.  But perhaps I'm missing something.

No.

You can send a single message, the concern has nothing to do with _you_ potentially reusing your nonce.

I can intercept your single message, modify it, send it to the receiver. I can take advantage of the receivers misbehavior on receipt of the corrupted message— either doing new things from bitflips (e.g. I guessed what part of your message likely was and twiddled bits), or if garbage messages will make the receiver echo back in plaintext I can use that to recover your one-time pad.

Another way to look at it is that without authentication an attacker can cause multiple messages with the same nonce to exist. It doesn't matter that you didn't create them, the additional messages with the same nonce are potentially problematic none the less.

[Peter R]

You can send a single message, the concern has nothing to do with _you_ potentially reusing your nonce.

I can intercept your single message, modify it, send it to the receiver. I can take advantage of the receivers misbehavior on receipt of the corrupted message— either doing new things from bitflips (e.g. I guessed what part of your message likely was and twiddled bits), or if garbage messages will make the receiver echo back in plaintext I can use that to recover your one-time pad.

Another way to look at it is that without authentication an attacker can cause multiple messages with the same nonce to exist. It doesn't matter that you didn't create them, the additional messages with the same nonce are potentially problematic none the less.

Thanks for reviewing this, Greg.  I have some more questions if you don't mind, because I'm still convinced a messaging scheme like this could be made very secure:

Aren't you assuming that the receiver is going to respond to your attacks using the same session key?  What I was imagining (but didn't describe), is that the receiver wouldn't respond until he can authenticate the sender (Alice).  Here's a more detailed description of the scheme:

1.  Alice encrypts her message with the Diffie-Hellman shared secret (or some derivative of it) as the symmetric key (encryption scheme TBD).

2.  She stores the cypher-text message in a file accessible via some URL.

3.  She sends a bitcoin TX to Address B with a special OP_RETURN output that means "you have a message":
     (a) the OP_RETURN output specifies the URL where the cyphertext message can be found,
     (b) the OP_RETURN output specifies the message hash (let's imagine for a moment that we have more than 40 bytes),
     (c) the OP_RETURN specifies some nonce needed, in addition to the shared secret, to determine the session key.

4.  Address B (let's call him Bob) receives the message notification and now obviously also knows Alice's pubkey.

5.  Bob downloads the cypertext file and decrypts it (the only missing piece of info was Bob's private key which he obviously knows).

6.  Bob knows this is the real message because he can compare the hash to the one in the OP_RETURN message notification.  But the message could have also been signed, so he could verify that Alice was the sender even without the hash comparison.  

7.  If the message is "bad," then Bob doesn't reply using the same session key.  I don't see why Bob needs to do anything, but I suppose he could respond with a (clear-text) NACK using another OP_RETURN output.  

8.  If the message is "good," then I would assume that the message would have also encoded some piece of information for Bob to create a new secure session for his return communication.  I think now the return communication could take place across any channel, because isn't it fully authenticated at this point?


I'm not sure, but I think 3(c) could be eliminated with the appropriate protocol and perhaps 3(b) too.

[piotr_n]

Can I encrypt a short message with a bitcoin address (public key) and send that to a person I know has the private key?  

If I use a bitcoin address to encrypt a message of only 30 characters - how long with the encrypted message be?  

How may this be done?

For example, my message is: "This is a test of my new system" and this is the public key: 12K5SyY2Z3DNsqFtTCnyGC3J7jYTCjM54m

What does the encrypted message look like and how does one arrive at making it?

There are few things that you should be aware of.

Bitcoin address is not a public key, but only its hash.
Having a public key you can verify whether it matches the address, but you need to have a way of getting the actual public key, if you want to go further from here.
That usually implies a cooperation from a person that you want to send the encrypted message to, but in general they'd have no much reasons to not cooperate.

Having a public EC key, you can implement a symmetric encryption.
In this case you would encrypt 256 bits of a clear data into 257 bits of an encrypted result.
Having the private key and the 257 bits, you can calculate from it the original 256 bits (of the clear data).

For encrypting messages you usually prefer using a randomly chosen (for one time use) symmetric key (e.g. AES).
Then you only use the asymmetric Elliptic Curve "crypto", for passing the secret symmetric key to the recipient (along with the AES encrypted message).

[InwardContour]

A much better, but similar solution would be to use PGP and somehow associate your PGP public key with your bitcoin address.

This would resolve the issue of potentially exposing your private key to anyone while keeping your goal of encrypting messages involving your bitcoin address.

[gmaxwell]

Aren't you assuming that the receiver is going to respond to your attacks using the same session key?

No. Not at all.

Can you review my post again with this in mind. Communication is hard and I take full responsibility for being unclear... but I think I'm going to just repeat myself at this point.  I'll gladly retry if you reread with the assumption that the users do not reuse the session key.

[luv2drnkbr]

You don't need ECC encryption to use an ECC key as a password.  As was pointed out, you can generate an ECC DH exchange-- which is shared secret in the stealth address documentation.  Then once you have the shared secret, you use any kind of symmetric encryption algorithm you want with this 256 bit shared secret as the password.  Or you can XOR the secret itself with a short message, or generate multiple ECC ephemeral keys, and XOR over the chain of shared secrets, and just concatenate the chain of public ephemeral keys, and then digitally sign the whole clump.

[e4xit]

Hi,

So I would like to revisit this thread if I may... If I had a publicly advertised bitcoin address which was the "pay point" for a service and I wanted to return to any entity paying to this address some encrypted data (in TX_OUT?) would I be able to do it so that they could just use their (bitcoin) private key to decrypt?

In this situation the sender would have by default had to already reveal (to the network) their public key, so i could encrypt the data (likely a hash) I want to return to them, and store it in the tx (somewhere) which is returned to the sending address (I know I know, bad bitcoin practice and LukeJR will probably have a field day with my terminology if he sees this), but hopefully you can understand some light on what I am thinking of doing here and let me know if it might be possible?

A possible application might be a tokenised authorisation/access system. Bitcoin user can send any amount of coin to a publicised pay point and recieve back a small dust (or other size) tx along with prunable, encrypted data. If this data was a hash which acts as, or corresponds to an access token (where the period/size of access was likely related to the size of initial deposit to the pay point). In this situation you could trustlessly give access to paying entities using a distributed ledger to exchange information, automagically.

Perhaps someone already though of this before and it just has a name I am not familiar with, or perhaps it won't work for technical reasons. Either way, perhaps it is enough of an idea for someone to use...?

[dabura667]

https://github.com/bitpay/bitcore/blob/master/lib/common/ECIES.js

Is this insecure?

[andytoshi]

In this situation the sender would have by default had to already reveal (to the network) their public key, so i could encrypt the data (likely a hash) I want to return to them, and store it in the tx (somewhere) which is returned to the sending address (I know I know, bad bitcoin practice and LukeJR will probably have a field day with my terminology if he sees this), but hopefully you can understand some light on what I am thinking of doing here and let me know if it might be possible?

Well, there is no "sending address" in the Bitcoin protocol, so this data would need to be passed out-of-band. This is not a "terminology problem" nor is it an opinion of Luke-Jr's. It's a fact about Bitcoin.

Then there is a general problem with using same keys for signing and encryption. To the best of my knowledge there is no attack based on simultaneous key use in ECDSA and ECIES, but I'm also not aware of any security proof that this is a safe combination. It is routinely true that the algebraic structure of two unrelated cryptosystems can be combined to produce an attack. For example, in the CryptoNote whitepaper a ring signature scheme is proposed which has two hash functions. It turns out you can remove one of these hash functions and replace by the identity function, and still prove security of the ring signatures --- and in fact I did this, thinking that this hash function was only there for historical reasons (in the ring signature scheme that CryptoNote's scheme is based on, this hash function provides compression, which isn't needed any longer in CryptoNote). But in fact, I'd have been wrong to remove this hash, because as they observe at the bottom of page 17, without the hash function their ring signature scheme interacts very badly with their stealth address scheme. I'm glad they mentioned this because I certainly wouldn't have caught this. (You can argue in this case that I'm just not very smart but imagine that the stealth addresses and ring signatures had been proposed by separate parties, and were combined by a non-cryptographer who was treating them as black boxes. You can see that "don't mix cryptosystems!" would have been very productive advice.)

Another general concern I have about the postings in this thread are comments along the lines of "wellll, I think I can make this secure, as long as the user doesn't do X or Y or Z". The problem with this line of thinking is that leads to very finicky and non-standard security properties, which means that anyone using the cryptosystem will need to think very carefully about exactly how the scheme is used. In professional cryptography, there are a variety of "standard security properties" which are very general and that cryptosystems are required to adhere to. For example, signature schemes should be EUF-CMA secure "existentially unforgeable under chosen message attack", meaning that even an attacker who is allowed to request signatures on arbitrary messages cannot forge one. Note that there is no dependence here on what messages are allowed to be signed, what the attacker is allowed to do, etc.

There are a couple of security properties that public-key encryption schemes ought to satisfy, which are similarly general. These properties are familiar to cryptographers and (relatively) easy for them to reason about. (Note that they do not cover side-channel attacks, and prove security only when their assumptions are satisfied --- e.g. that all random number generators are producing values that are truly indistinguishable from uniformly random ones.) Having a mathematical proof that a cryptosystem satisfies one of these properties is a prerequisite to the system even being worth analysing. Then we can consider the context that it will be used in, whether this security property is applicable, protection against side-channels, how to obtain any required randomness, who has access to what secret data, how secret data is stored or transferred, etc., etc.

There is a lot to this and if you can't get the basic provable security of the primitives down your system is hopeless. And it's simply impossible to do this with ad-hoc arguments or by layering nonstandard assumptions about how the cryptosystem will be used.

https://github.com/bitpay/bitcore/blob/master/lib/common/ECIES.js

Is this insecure?

I don't have the time to audit the code (at least, not well enough to publicly give my blessing), but it's worth considering that Javascript cryptography is nearly impossible to do securely.

[gwlloyd]

A much better, but similar solution would be to use PGP and somehow associate your PGP public key with your bitcoin address.

This would resolve the issue of potentially exposing your private key to anyone while keeping your goal of encrypting messages involving your bitcoin address.

Namecoin / OneName.io