[ANN] CoinMessage: Secure Messaging with Bitcoin Addresses

[altoz]

Hi everyone,

I've created a secure messaging library that uses the blockchain for the public key infrastructure. So far, this is a fairly straightforward implementation of ECC cryptograpy using the curve that Bitcoin uses for encryption, secp256k1. You can now send a secure message to any public bitcoin address that has spent something. Only the holder of the private key can read the message. The restriction on having an address that has already spent something is the result of the blockchain not containing the public key until someone has actually spent funds from that address.

The v0.1 alpha python code is here:

https://github.com/coinmessage/coinmessage

Among other things this should enable:

• Secure, encrypted messages where only one party has the key to read them.
• Logins to websites without passwords, instead using a challenge/response mechanism like GPG auth.
• A wallet client that can also be used for reading secure messages.
• A consistent pseudonymous internet identity that can provably be the same across websites.

Currently, you can only encrypt and decrypt messages from the python command-line.

I'm posting in the Development and Technical Discussion forum so that I can get feedback on the security implications. I've figured out the math and got it to work, but I'm by no means an ECC expert and would very much welcome feedback.

Thanks!

[1715091795]

1715091795

[1715091795]

1715091795

[1715091795]

1715091795

[1715091795]

1715091795

[1715091795]

1715091795

[Luke-Jr]

• Logins to websites without passwords, instead using a challenge/response mechanism like GPG auth.
• A consistent pseudonymous internet identity that can provably be the same across websites.

This has been builtin to Bitcoin-Qt since 0.6 and used for things like the Eligius mining pool and #Bitcoin-OTC for just about as long.
Here's an example walkthrough written by BunnyH.

[altoz]

• Logins to websites without passwords, instead using a challenge/response mechanism like GPG auth.
• A consistent pseudonymous internet identity that can provably be the same across websites.

This has been builtin to Bitcoin-Qt since 0.6 and used for things like the Eligius mining pool and #Bitcoin-OTC for just about as long.
Here's an example walkthrough written by BunnyH.

The link you gave is for signing public messages. Is there an option also for sending private messages?

For example, I can send you, who presumably owns this address: 134dV6U7gQ6wCFbfHUz2CMh6Dth72oGpgH a message:

AABs1tUzPFR/IEpuscV1KGZouTf0Wp11k0x9/jDkUZdLZ5DlalFrpc3h7tkXq5/E4Vbe7EHu6cjQleBx3QOMNSWGbZrTNKzlf3+TShRq

Only you should be able to read that message and only with your private key.

You're saying this exists in the Bitcoin-QT client?

edit: nevermind. I see you were talking only about the challenge/response using sign/verify. That makes sense. btw, I would appreciate it if you could decode that message as a test =)

[chriswilmer]

Hi everyone,

I've created a secure messaging library that uses the blockchain for the public key infrastructure. So far, this is a fairly straightforward implementation of ECC cryptograpy using the curve that Bitcoin uses for encryption (y^2 = x^3 + x + 7). You can now send a secure message to any public bitcoin address that has spent something. Only the holder of the private key can read the message. The restriction on having an address that has already spent something is the result of the blockchain not containing the public key until someone has actually spent funds from that address.

The v0.1 alpha python code is here:

https://github.com/coinmessage/coinmessage

Among other things this should enable:

• Secure, encrypted messages where only one party has the key to read them.
• Logins to websites without passwords, instead using a challenge/response mechanism like GPG auth.
• A wallet client that can also be used for reading secure messages.
• A consistent pseudonymous internet identity that can provably be the same across websites.

Currently, you can only encrypt and decrypt messages from the python command-line.

I'm posting in the Development and Technical Discussion forum so that I can get feedback on the security implications. I've figured out the math and got it to work, but I'm by no means an ECC expert and would very much welcome feedback.

Thanks!

Cool! Can't wait to try this later!

[altoz]

Hi everyone,

I've created a secure messaging library that uses the blockchain for the public key infrastructure. So far, this is a fairly straightforward implementation of ECC cryptograpy using the curve that Bitcoin uses for encryption (y^2 = x^3 + x + 7). You can now send a secure message to any public bitcoin address that has spent something. Only the holder of the private key can read the message. The restriction on having an address that has already spent something is the result of the blockchain not containing the public key until someone has actually spent funds from that address.

The v0.1 alpha python code is here:

https://github.com/coinmessage/coinmessage

Among other things this should enable:

• Secure, encrypted messages where only one party has the key to read them.
• Logins to websites without passwords, instead using a challenge/response mechanism like GPG auth.
• A wallet client that can also be used for reading secure messages.
• A consistent pseudonymous internet identity that can provably be the same across websites.

Currently, you can only encrypt and decrypt messages from the python command-line.

I'm posting in the Development and Technical Discussion forum so that I can get feedback on the security implications. I've figured out the math and got it to work, but I'm by no means an ECC expert and would very much welcome feedback.

Thanks!

Cool! Can't wait to try this later!

Thanks! If you want to post a bitcoin address, I'd appreciate it so I can send you a message you can try to decode!

[chriswilmer]

Sure, try this one:

142Wcxi8xFbTrBEnbdnHrFF1o2TCJnyKpq



-Chris

[altoz]

Sure, try this one:

142Wcxi8xFbTrBEnbdnHrFF1o2TCJnyKpq



-Chris

AAEg198WzHyD8J2XhxB8UKPaLXR2uzgri+TvlKUov1oSZCRLScvDaDcMdOvciqOhc96hRcny8pZakNpE2V0wzimADfj8makJoD6iEKne1NGAw3/TE4W2AZHEVaxnhFpaS60qRuZqWWbGraKnYMy4r1l5i1KKGVb86Gu4gZgKfqBcYc3fXyIyFeKGxgcOrhJW+r16KOvIqMoAvvFIhTx+jrpnRYe/fVpSev+qUl6PFoCuVF5VfuS/pTVWprp3/3KgIQRAC/edX3mbUVWqvmXMCt+6Z5l1dMOZ

[gmaxwell]

It's generally considered a bad practice to use the same keys for signing and encrypting, though its not quite as much of a trap for ECC as it is with RSA. Although it is somewhat easy when making things that do ECDH like this to fail to validate that the nonce sent is a point on the curve, and by doing that pretty easily leak the private key.

Calling this a "PKI" is a stretch. If I had to give you an address, I could have just given you a public key instead... then the use of a centralized database or even the blockchain at all wouldn't be required (no normal bitcoin node keeps an index that would be useful for this lookup, nor will any by default because doing so would add a gigabyte-and-growing overhead).

As Luke mentioned, the authentication use-cases are better handled through regular signmessage. This has the added benefit of not needing to depend on the centeralized key resolution service since you can authenticate a signmessage with only the address, plus it's already deployed.

Cheers.

[altoz]

Although it is somewhat easy when making things that do ECDH like this to fail to validate that the nonce sent is a point on the curve, and by doing that pretty easily leak the private key.

Can you elaborate on this point? What nonce can you send that would leak the private key and by whom? At least in my implementation, the nonce is generated by the message sender and the message receiver should, of course verify that the nonce is a point on the curve, but I'm missing how that would leak the private key.

Also, what is the danger to using the same key to sign and encrypt? Just curious.

[gmaxwell]

Can you elaborate on this point? What nonce can you send that would leak the private key and by whom? At least in my implementation, the nonce is generated by the message sender

who doesn't have the private key and may be malicious. That attack is that the sender picks a nonce which is not on the curve and then attempts to learn something about the point that the receiver has generated using the bogus point— e.g. probing it to see if the 'checksum' fails.

The secret key * off-curve-point is equivalent to performing ECDH on the quadratic twist, and for secp256k1 the twist is not really cryptographically strong. In a trivial cryptosystem where the decrypting party just happens to tell you the secret they derrive compromising their private key is not hard, in practical systems it can be harder to exploit but also hard to be confident if it's never exploitable.

Also, what is the danger to using the same key to sign and encrypt? Just curious.

The classic example is RSA where even deployed systems have been compromised by sending blinded encrypted data, getting them to sign it, and unblinding the result to yield decrypted data with that key.  Basically the security assumptions of an algorithm can be broken by doing other things with the key material outside of the algorithm... usually its fine. Sometimes it's not. Figuring out where its fine or not is hard, so it's considered a better practice to just generate separate signing and encryption keys and sign the encryption key to bind them... sometimes there are important reasons to compromise on this rule of thumb, of course. But absent a good reason its good to keep them separate (perhaps doubly so in that there are no strong proofs of ecdsa's security— only ones that make rather broad generalizations, if we can't prove ecdsa secure the being confidence that ecdsa plus a potential additional side channel to the secret key is harder.).

[altoz]

Can you elaborate on this point? What nonce can you send that would leak the private key and by whom? At least in my implementation, the nonce is generated by the message sender

who doesn't have the private key and may be malicious. That attack is that the sender picks a nonce which is not on the curve and then attempts to learn something about the point that the receiver has generated using the bogus point— e.g. probing it to see if the 'checksum' fails.

The secret key * off-curve-point is equivalent to performing ECDH on the quadratic twist, and for secp256k1 the twist is not really cryptographically strong. In a trivial cryptosystem where the decrypting party just happens to tell you the secret they derrive compromising their private key is not hard, in practical systems it can be harder to exploit but also hard to be confident if it's never exploitable.

Also, what is the danger to using the same key to sign and encrypt? Just curious.

The classic example is RSA where even deployed systems have been compromised by sending blinded encrypted data, getting them to sign it, and unblinding the result to yield decrypted data with that key.  Basically the security assumptions of an algorithm can be broken by doing other things with the key material outside of the algorithm... usually its fine. Sometimes it's not. Figuring out where its fine or not is hard, so it's considered a better practice to just generate separate signing and encryption keys and sign the encryption key to bind them... sometimes there are important reasons to compromise on this rule of thumb, of course. But absent a good reason its good to keep them separate (perhaps doubly so in that there are no strong proofs of ecdsa's security— only ones that make rather broad generalizations, if we can't prove ecdsa secure the being confidence that ecdsa plus a potential additional side channel to the secret key is harder.).

I apologize for my naivete, but I'm trying to understand the attack. My algorithm sends the short version of the nonce point (x plus parity) so the attacker sending an invalid nonce means the attacker sends an x that's past p but less than 2^256. Say the receiver has a broken program that doesn't check the nonce and gets a garbage message. What would the receiver do at this point to inform the attacker? Here is the message I got?

[gmaxwell]

I apologize for my naivete, but I'm trying to understand the attack. My algorithm sends the short version of the nonce point (x plus parity) so the attacker sending an invalid nonce means the attacker sends an x that's past p but less than 2^256. Say the receiver has a broken program that doesn't check the nonce and gets a garbage message. What would the receiver do at this point to inform the attacker? Here is the message I got?

Right, imagine the receiver that takes the form of network reachable service, and you can send it messages and it tells you what it decoded or just tells you if the checksum passed. You can now blast candidate messages (e.g. sweeping the checksum) at it and learn data derived from secret*(twist point), with all that indirection actually compromising something that would be impressive, but its clearly gone far outside of the realm of being able to make solid statements about the security by that point.

[altoz]

I apologize for my naivete, but I'm trying to understand the attack. My algorithm sends the short version of the nonce point (x plus parity) so the attacker sending an invalid nonce means the attacker sends an x that's past p but less than 2^256. Say the receiver has a broken program that doesn't check the nonce and gets a garbage message. What would the receiver do at this point to inform the attacker? Here is the message I got?

Right, imagine the receiver that takes the form of network reachable service, and you can send it messages and it tells you what it decoded or just tells you if the checksum passed. You can now blast candidate messages (e.g. sweeping the checksum) at it and learn data derived from secret*(twist point), with all that indirection actually compromising something that would be impressive, but its clearly gone far outside of the realm of being able to make solid statements about the security by that point.

If I'm not mistaken, this is an attack that can be performed on any elliptical curve, not just secp256k1. And obviously, other elliptical curves use the same mechanism to do secure messaging. Is the fact that the private exponent is also used to sign messages somehow related to this attack? Or is it the curve itself? 2^256 - p = 4294968273 or roughly 4.3 trillion maximum possible attempts that will give back different data. Is that enough data to find something?

Also if sweeping the checksum is the strategy, wouldn't having a longer checksum (say 2^256 bits) solve that problem?

Again, just trying to understand the attack here. Thanks for engaging an elliptical curve newb.

[altoz]

A random observation:

I discovered that BitMessage uses secp256k1 for encryption/decryption that's not very different from my code. Does this mean that bitmessage can also be compromised? The point of them using secp256k1 was so that people could use the same keys from bitcoin.

[Luke-Jr]

The point of them using secp256k1 was so that people could use the same keys from bitcoin.

This is a useful thing? How?

[altoz]

The point of them using secp256k1 was so that people could use the same keys from bitcoin.

This is a useful thing? How?

Not sure, you'd have to ask them, but I'd imagine it's because your identity is the same in both blockchains and some applications that use both can be made.

[Luke-Jr]

The point of them using secp256k1 was so that people could use the same keys from bitcoin.

This is a useful thing? How?

Not sure, you'd have to ask them, but I'd imagine it's because your identity is the same in both blockchains and some applications that use both can be made.

Addresses aren't identities.

[altoz]

Addresses aren't identities.

Let's not get pedantic. An address is something that can be used to identify an account, which could be used as an identity. That's how social security numbers, driver's licenses and the like work.

[Luke-Jr]

Addresses aren't identities.

Let's not get pedantic. An address is something that can be used to identify an account, which could be used as an identity. That's how social security numbers, driver's licenses and the like work.

No.
An address does not identify an account.

Side note: social security numbers are also not to be used for identity purposes.

[altoz]

Addresses aren't identities.

Let's not get pedantic. An address is something that can be used to identify an account, which could be used as an identity. That's how social security numbers, driver's licenses and the like work.

No.
An address does not identify an account.

Side note: social security numbers are also not to be used for identity purposes.

Of course an address identifies an account. That's what the whole blockchain is, a list of accounts and who owns what.

If you're just going to troll, I'd rather you not do this on this thread.