Bitcoin Forum
November 08, 2024, 02:42:48 AM *
News: Latest Bitcoin Core release: 28.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: « 1 [2]  All
  Print  
Author Topic: Is it possible to create a message readable only to the owner of an address?  (Read 2696 times)
andytoshi
Full Member
***
Offline Offline

Activity: 179
Merit: 151

-


View Profile
September 16, 2014, 01:54:49 PM
 #21

Greg told me that this method is insecure, but I still don't understand why.

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.
Peter R
Legendary
*
Offline Offline

Activity: 1162
Merit: 1007



View Profile
September 16, 2014, 04:23:01 PM
 #22

Greg told me that this method is insecure, but I still don't understand why.
In academic cryptography you want well-defined security against arbitrary adversaries with well-defined powers...

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 Smiley]

Run Bitcoin Unlimited (www.bitcoinunlimited.info)
andytoshi
Full Member
***
Offline Offline

Activity: 179
Merit: 151

-


View Profile
September 16, 2014, 04:59:35 PM
 #23

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..."

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.
Peter R
Legendary
*
Offline Offline

Activity: 1162
Merit: 1007



View Profile
September 16, 2014, 05:46:06 PM
 #24

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..."

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.

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

Run Bitcoin Unlimited (www.bitcoinunlimited.info)
andytoshi
Full Member
***
Offline Offline

Activity: 179
Merit: 151

-


View Profile
September 16, 2014, 07:12:48 PM
 #25

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.  

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.

Quote
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).    

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".
Peter R
Legendary
*
Offline Offline

Activity: 1162
Merit: 1007



View Profile
September 16, 2014, 07:53:54 PM
 #26

These aren't theoretical attacks. Any reaction to a marred ciphertext except outright immediate rejection will be used in a real attack.

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

Quote
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".

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.  

Run Bitcoin Unlimited (www.bitcoinunlimited.info)
andytoshi
Full Member
***
Offline Offline

Activity: 179
Merit: 151

-


View Profile
September 16, 2014, 08:12:49 PM
 #27

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

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.

Quote
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. 

Thanks, glad we're on the same page Smiley.
bigasic
Hero Member
*****
Offline Offline

Activity: 924
Merit: 1000



View Profile
September 16, 2014, 09:13:42 PM
 #28

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.
Pages: « 1 [2]  All
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!