Bitcoin Forum

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!

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. (http://eligius.st/~capa66/utl/my_eligius/index.html)

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

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!

Sure, try this one:

142Wcxi8xFbTrBEnbdnHrFF1o2TCJnyKpq

:)

-Chris

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

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.

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.

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.

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?

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.

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.

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.

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.

No, perhaps you should learn how bitcoin works before trying to extend it with functionality that mostly already exists anyway... sigh

http://download.wpsoftware.net/bitcoin/bitcoin-faq.pdf

Also accusing Luke-Jr of trolling is quite rich..

A user that just got out of newbie jail calling me anything is quite rich. One may suspect this could be Luke-Jr sock puppet.

Bitmessage keys are only used for encryption, not for signing. I tried talking atheros into it but to no avail  :D

Btw:Bitmessage does not have a blockchain.


IMHO the point is: Getting encryption right is difficult so don't complicate things any more than absolutely necessary.

altoz, I think your idea is great, and in general I am very supportive of developers and trying out new projects (even if they don't end up taking off for whatever reason)

I think luke-jr is being unnecessarily mean... I wouldn't take it personally

Interesting, I didn't know they don't have a blockchain. Isn't there some large block of data that stores the encrypted messages there in some way, though?

I guess what I'm asking is, my project seems about as secure as bitmessage, just from what we're both doing with the secp256k1 curve. So if coinmessage is not considered secure, can bitmessage? If not, what am I missing?

Thanks for the support. Thanks to the pointless exchange with Luke-Jr, I discovered what the "ignore" button is for!

Have you had a chance to look at the message I sent you?

Works like a charm! Cool!

I'm a big fan of Bitmessage too... I haven't followed up on the latest developments. It seems like there is certainly a need for an easy-to-use, decentralized, encrypted messaging service. Last I heard the jury was still out on whether Bitmessage was really scalable.

Awesome! Thanks for trying this!

Unfortunately I did not yet find the time to dive into Bitmessage but from the little I know clients store the messages for some days, I guess in a normal database.

The problem is that you use the same private key for both signing and encryption. Bitmessage does not do this.

By using the same key for both signing and encryption and you being able to influence the input / read output there are certainly additional attack vectors. For example you could create an unsigned transaction and try tricking the other party into signing it like a normal message.

In the example you gave, wouldn't that be an attack vector that is available without any encryption? For example, using the challenge-verify mechanism that Luke-Jr showed above, you can use an unsigned transaction as the challenge and the user would sign it and send the signature to the malicious attacker. At what step does the attacker need the encrypt/decrypt part?

No, you can't.
First, the challenge must be an understandable message, not just random-looking data.
Second, the message is internally prepended with a prefix before signing, to ensure this very thing doesn't happen.
Finally, it is not valid to sign a message with a key that has been used as an address in a transaction already, only unused addresses.

1. I am not a sockpuppet of Luke-Jr's.
2. Accusing core developers of having sock puppets and trolling is a stupid way to get anyone to take you seriously.
3. Putting core developers on your ignore list is a stupid way to learn anything.
4. My activity on bitcointroll says absolutely nothing about my knowledge or experience with bitcoin, its community or cryptography in general.
5. I didn't call you anything. I provided a link to the "accounts are not addresses" FAQ. I'll give you the benefit of the doubt and assume you read it, since my server logs show several accesses between the time I posted the link and the time of your "sock puppet" comment.

If you want to develop usable software with bitcoin, you need to listen to the experts in the community. You need to understand how bitcoin works. You need to be aware of existing tools (especially those built into the reference client!), and follow the current development and research. You need to understand the cryptography involved and common pitfalls surrounding it.

Instead, you published cryptographic software which abuses bitcoin primitives to obtain cryptographic keys (using some random centralized service no less!), which you then use for purposes they weren't designed for, to do something which has already been done. You then admitted that you weren't familiar with ECC and didn't understand what bitcoin addresses were for, and despite this you personally attacked Luke and myself. This is not the behaviour of a responsible person, or someone who can be trusted to properly develop cryptographic software.

How is it a centralized service... it's just code anyone can use?

Also, there is no reason why we can't provide critical feedback while also being nice and supportive.

My bad. I misread that he was using blockchain.info to obtain blockchain data.

Edit: I take this back. He is using bc.i: https://github.com/coinmessage/coinmessage/blob/master/coinmessage/services.py

Andytoshi and luke-jr. Please leave this thread. I'm currently ignoring both of you and as far as I can tell you have nothing of substance to your remarks beyond Luke's first.

Not so, there are twist-secure curves like the one used by curve25519 where the points on the twist are equally secure.

The general statement cautioning against using the same keys for encryption and signing is because the parallel composition of signing and encryption is an unanalyzed construct. I might be able to take some signatures, combine them algebraically, ask for a decryption, and learn something about the private key as a result. Providing parallel access to the private key material, even if its via constructs which are separately accepted as cryptographically strong, voids the security proofs and deployment confidences, and surprising weaknesses have shown up in the past as a result of it. ... so it's generally considered a good practice to avoid it where possible.

I'm disappointed to see that the conversation with Luke went unproductive there, he is responsible— AFAIK— the largest and longest standing use of bitcoin keys for identification/authentication purposes; which were one of your enumerated use cases.  I actually asked him to come here and respond specifically to those use cases.

Likewise, andytoshi has been active in the Bitcoin wizards channel where a lot of advanced cryptography is discussed for some time. He's not a sock of anyone, and negative tone is just going to discourage people from evaluating your system.

This might be true, but I still don't understand how useful such an attack would be. If the attack relies on sweeping the checksum, then having an impractically large checksum (2^128?) simply stops the attack.


This is the more valid objection. There's the possibility of a vulnerability yet undiscovered. Obviously, RSA has had this vulnerability so it makes sense that caution is being taken with ECC.

That said, a good, deliberately slow key derivation function should be able to make the attack very expensive. 50000 rounds of sha512, for example (to make it future-proof, we could make the rounds of sha512 necessary some fraction of the network difficulty and provide a timestamp of when it occurred). Would something like that make this more viable?

Also, you mention that it's good practice to avoid it where possible. does that mean there are cases where it isn't avoidable and this does take place?


Honestly, I'm finding your comments far more helpful than his. He could be a genius for all I know, but I'm not interested in pedantic arguments about what "account" means.


Sadly, I agree with you. Of course I have some share in that responsibility. Unfortunately, other than that first comment, I don't see anything of value in their other comments and I don't see much likelihood in there being any from them at this point. Life is too short to deal rudeness like that unless absolutely necessary.

Obviously, people are free to not evaluate the system. I think given the potential of the whole thing, I would be pretty disappointed if the only technical commentary I got was from you.

That said, thank you for your thoughts so far.

This seems along the lines of ECIES
http://en.wikipedia.org/wiki/Integrated_Encryption_Scheme

I'm not sure exactly how your system works but I would have thought it should be possible to use ECDH to create a shared secret without compromising your secret key and use this in a symmetric encryption scheme (AES) without compromising the shared secret? Isn't this basically what is done in ECIES?
The private key is used in the creation of the shared secret but if this is done ok then using the shared secret in a secure symmetric system shouldn't compromise it in any way.

I may have misunderstood things but I don't see how the same private key is used for signing and encrypting - the shared secret used for encrypting isn't the private key of the bitcoin address is it??

It is very much along those lines, yes.


Can you elaborate on this? The shared secret is rP where r is a random nonce in the prime field F/p and P is the public key point. This is never transmitted, rG is. I'm not sure I understand how this compromises the secret key?


The private key is not used in the creation of the shared secret since the person encrypting has only the public key and computes the shared secret through a nonce.

No, the shared secret used for encryption is not the same as the private key used to sign the bitcoin address.

I may not have understood gmaxwell correctly, but I thought this was still a potential vulnerability as the private key is still used for decryption?

Yes, that's the way I thought you were doing it?
I don't understand the problem. I think they might have not understood that you were using the shared secret for symmetric encryption.

So are you saying gmaxwell's main objection doesn't apply? That by having a shared secret with symmetric encryption inside, the attacks don't reveal anything about the private key?

II think bit message uses ECIES. I believe it's secure as long as you perform your key exchange ok and you're using a secure symmetric cryptography (I might be wrong). and I think ( but I don't know exactly what your program does) that you are using the same sort of ideas. You would probably be better off just implementing ECIES though.
 I don't think your OP explained your system in enough detail so it may have been misunderstood. Also bear in mind that I'm quite often wrong about stuff. :)
 
 

I am using ECIES, I think. I would need a more experienced cryptographer to examine the code to make sure, but it's fairly straightforward. The shared secret gets exchanged securely using the same discrete logarithm problem. The shared secret then is plugged into a key derivation function which is used to make a cipher and an hmac for evaluating the checksum. The cipher then is used for encrypting and decrypting the message. And the checksum is checked to make sure the message arrived un-modified. That's how ECIES works, I think. That's at least what I tried to implement.

Here is example walkthrought how it could be:
1) Go to website
2) Read a QR code on the main page with your smart phone application

After that, you are logged in with your bitcoin keys and username you chose when registered.

Registering:
1) Go to website
2) Click 'register'
3) Type in the username you want
4) Read a QR code on the main page with your smart phone application

After that, you are registered with bitcoin keys and username you chose.

Try it at http://cave.dy.fi. You can download an android application or simulate it with www-browser / copypaste.

This could be usefull to implement for loggin in to eligius?

My impression is that Luke-Jr isn't really interested in a new tech, more convenient though it may be.

Continuing to troll does not help your case.
I said nothing of the sort.

Luke-Jr, I can't see what you wrote, but please respect my wishes and stay away.

No, you don't get to demand this while continuing to slander me.

Luke-Jr, I've put you on my ignore list. I literally don't see anything you write. Please just leave and stop crapping my thread.

If you want to discuss things mano-a-mano, PM me.

No. The use of any particular encryption scheme does not answer the very minor and very abstract concern I raised about parallel use of the private keying material. I'm getting a very concerning sense of the blind leading the blind here, and the incivility is really out of line.

The "new tech" encryption based "two factor" authentication protocol described above is insecure against a malware infected host. Because it operates in-band and the authentication credential is unauthenticated and the malware can just steal the response. Presumably the purpose of having a two factor in the first place was to be secure against that. The sign-message mechanism— which could be given an exactly equivalent workflow, and which doesn't have the same additional security considerations to consider can be free of this weakness if used to specifically authenticate the action requested.

This has gone offtopic for this subforum.

[Edit: For historical interest sake, I should publish the weaknesses I reported privately:

I found a weakness for this cryptosystem which allows me to compromise it for a single message with 2^64 known-ciphertext queries to a decryption oracle.  E.g. the key-holders run a server (the oracle) that decrypts messages and returns the results and I obtain the ciphertext of a message someone else created (which the oracle refuses to decrypt for me, otherwise this would be trivial), and after making 2^64 queries to the decryption oracle I can decrypt the unknown message.

To accomplish this I take the nonce from the message to be decrypted, and combine it with the all zeros ciphertext (or any other known ciphertext for that matter) and sweep the 64-bit MAC space until it passes. I xor the resulting garbage decryption of zeros with the message thus recovering the plaintext.  This attack is a result of compromising the ECIES security claims by the reduction of the MAC size, though it only results in a complete break because of the use of counter mode AES.

Less cryptographically,

Using a centralized service to look up public keys creates weaknesses worse than just the 'obvious' privacy and availability ones because the implementation here doesn't check that the pubkey returned matches the address, though it trivially could.

This weakness is made exponentially worse because the public key is fetched over https using urllib2 which, as far as I can tell, doesn't do any certificate validation, so any MITM could substitute the public key.

Altoz has subsequently opened up issues for all these items: https://github.com/coinmessage/coinmessage/issues

I still have the general reservations with using encryption for authentication, especially in-band auth— and for reusing a single private key for signing and encryption, both are generally inadvisable practices though I'm not aware of any specific weakness they create here. Likewise, any usage that needlessly ties a user's identity to their finances could result in surprising losses of privacy, so I hope this approach isn't widely adopted even once the cryptographic weaknesses are fixed. If people want you to send them encrypted messages, get pubkeys from them!

]