Jump to content

  • Log In with Google      Sign In   
  • Create Account

FREE SOFTWARE GIVEAWAY

We have 4 x Pro Licences (valued at $59 each) for 2d modular animation software Spriter to give away in this Thursday's GDNet Direct email newsletter.


Read more in this forum topic or make sure you're signed up (from the right-hand sidebar on the homepage) and read Thursday's newsletter to get in the running!


Can two strangers communicate securely without a friend?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
32 replies to this topic

#1 Cornstalks   Crossbones+   -  Reputation: 6991

Posted 06 February 2013 - 08:57 AM

I've been thinking about encryption this morning (and I have no clue why) and I started thinking about if it's at all possible for two strangers to establish a secure connection. I'm having my doubts, but I don't know a whole lot about encryption.

 

Today, we use SSL to try and establish a secure connection, but it relies on mutual friends of the two strangers (or in other words, certificates and certificate authorities). If the two strangers have no trusted mutual friend, then they can't validate certificates with their trusted mutual friend, and thus can't be entirely sure there isn't a man in the middle.

 

Is it even theoretically possible for two complete strangers to securely communicate without a mutual friend?


[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

Sponsor:

#2 slicer4ever   Crossbones+   -  Reputation: 3985

Posted 06 February 2013 - 09:26 AM

isn't this what public/private key's are for?

 

they exchange their public keys, encrypt their data to be sent with that public key, then decrypt with their own private keys.


Check out https://www.facebook.com/LiquidGames for some great games made by me on the Playstation Mobile market.

#3 samoth   Crossbones+   -  Reputation: 5036

Posted 06 February 2013 - 09:28 AM

Assuming "quantum cryptography" is not a consideration (does anyone have a working implementation?), no.

You need a shared secret of some kind (which complete strangers do not have) or a trusted third party to authenticate parties. Without a form of authentication, it is not really secure, ever.

Though there exist several three-pass protocols (e.g. Shamir) which presumably let you "securely" send a message to someone else without needing to distribute or exchange keys, they're still susceptible to a man-in-the-middle attack without a secret.

#4 samoth   Crossbones+   -  Reputation: 5036

Posted 06 February 2013 - 09:32 AM

 

isn't this what public/private key's are for?
 
they exchange their public keys, encrypt their data to be sent with that public key, then decrypt with their own private keys.

Vulnerable to man-in-the-middle.

Assume you want to contact this hot girl from the chat room and ask for her key. I intercept that key and send you mine instead. You send her your key, which I replace by my key as well. What now?

This works, reliably, if you have someone signing your keys. Not otherwise.

#5 slicer4ever   Crossbones+   -  Reputation: 3985

Posted 06 February 2013 - 09:33 AM

 

isn't this what public/private key's are for?
 
they exchange their public keys, encrypt their data to be sent with that public key, then decrypt with their own private keys.

Vulnerable to man-in-the-middle.

Assume you want to contact this hot girl from the chat room and ask for her key. I intercept that key and send you mine instead. You send her your key, which I replace by my key as well. What now?

This works, reliably, if you have someone signing your keys. Not otherwise.

that is very true, didn't think about the man in the middle distributing his key instead.


Check out https://www.facebook.com/LiquidGames for some great games made by me on the Playstation Mobile market.

#6 swiftcoder   Senior Moderators   -  Reputation: 10396

Posted 06 February 2013 - 09:48 AM

As an extension of the man-in-the-middle issue, how do you establish trust in the first place (i.e. how do you know who the other end is)?

 

Securely communicating with a random stranger is not useful. Since you don't know who they are, you have no idea what they are doing with your communication.

 

As a more concrete example: you find a website selling high-end laptops for $100 each. You are naturally cautious, but their order form has an SSL certificate. If the order form is secure, it must be safe to order, right?


Tristam MacDonald - Software Engineer @Amazon - [swiftcoding]


#7 DevLiquidKnight   Members   -  Reputation: 834

Posted 06 February 2013 - 10:04 AM

It is entirely possible to communicate securely without a friend, you should read more about cryptography. Man in the middle attacks can be detected with modern day cryptography, and it is possible to authentic that who you are talking to is indeed who you intend to talk to. Is this 100% full proof? No.

SSL is not the only way secure communication can be achieved, you could simply use a one time pad.


Edited by DevLiquidKnight, 06 February 2013 - 10:16 AM.


#8 Cornstalks   Crossbones+   -  Reputation: 6991

Posted 06 February 2013 - 10:11 AM

As an extension of the man-in-the-middle issue, how do you establish trust in the first place (i.e. how do you know who the other end is)?

Yeah, that's basically what I was thinking about this morning. If you want to talk to a complete stranger, you can't possibly know if you're talking to the right stranger without relying on someone else telling you "Yeah, that's the right guy."
 

Securely communicating with a random stranger is not useful. Since you don't know who they are, you have no idea what they are doing with your communication.

Well, yes, if they're a complete stranger you've got no clue what they're doing with the information you're sending them. But I was more interested in whether or not the sending and receiving of messages can be secure or not.
 

As a more concrete example: you find a website selling high-end laptops for $100 each. You are naturally cautious, but their order form has an SSL certificate. If the order form is secure, it must be safe to order, right?

Seems legit. Ha, nice example.

 

It is entirely possible to communicate securely without a friend, you should read more about cryptography.

Ooo, interesting. If there's a book that is a "light read" and explains things in simple English then I'd definitely be interested, if you know of any. On the other hand, if the only books covering that stuff are full of technical and algorithmic detail I'd probably rather just have someone explain it to me like I'm 4 :)

 

Man in the middle attacks can be detected with modern day cryptography, and it is possible to authentic that who you are talking to is indeed who you intend to talk to. Is this 100% full proof? No.

Can you elaborate on what kind of attacks we're still vulnerable to?


[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

#9 DevLiquidKnight   Members   -  Reputation: 834

Posted 06 February 2013 - 10:18 AM

This book is great:

 

http://www.crypto-textbook.com/

 

You can find it on amazon.

 

As for attacks we are vulnerable too, I imagine side-channel and implementation attacks being the primary target now of days.


Edited by DevLiquidKnight, 06 February 2013 - 10:21 AM.


#10 swiftcoder   Senior Moderators   -  Reputation: 10396

Posted 06 February 2013 - 10:23 AM

As for attacks we are vulnerable too, I imagine side-channel and implementation attacks being the primary target now of days.

And never discount good old-fashioned social engineering.


Tristam MacDonald - Software Engineer @Amazon - [swiftcoding]


#11 Milcho   Crossbones+   -  Reputation: 1177

Posted 06 February 2013 - 10:46 AM

Humor me on this:

There's an old story or something about how can two people exchange an item locked in a chest via a courier. 

Obviously putting a lock on the chest and sending the key with the courier allows the courier to unlock it. Likewise, sending the key along any other courier or different time still makes the transaction insecure.

So, the solution requires 3 transports in total.

1. Person A puts a lock on the chest, and send the locked chest, without the key, to person B. The key isn't sent at all, it remains with person A.

2. Person B puts a second lock on the chest, and sends the now doubly-locked chest back to person A, while keeping his own key with him at all times.

3. Person A unlocks his lock, since he's the only one that has the key, and sends person B the chest, which is now locked with the lock placed by person B only.

 

I know this isn't exactly a perfect analogy for digital communication. In digital communication, someone can observe a message before/after encryption - but I'm not encryption expert, so I'm not sure if its possible to devise a one-time algorithm to encrypt something, in a way that seeing both an encrypted and a decrypted message won't give away the key. This is the big IF that I see.

 

There's also the point that the two encryption methods used need to be compatible in a sense that decrypting a doubly-encrypted message will leave only the other encryption in place, and will then reveal the original message when the other encryption is removed. (that make sense? it's hard to word correctly)



#12 Cornstalks   Crossbones+   -  Reputation: 6991

Posted 06 February 2013 - 11:08 AM

*snip*

Isn't that still susceptible to man in the middle attacks? i.e. what if the courier service doesn't deliver the package to person B, but instead puts their own lock on the chest and gives it back to person A. Person A has no idea the second lock on there is the courier's and not person B's, so they unlock their lock and send it back. The courier service now unlocks their own lock, observes the contents of the chest (changing them if they feel like it), puts their lock back on it, and sends the chest to person B. Person B doesn't know it's the courier's lock on there and not person A's, so they put their lock on it, send it back, and the courier service unlocks their own lock and returns the chest. Person B gets the chest, unlocks their own lock, and observes the contents of the chest (which now the courier service could have altered, or at least observed the secret).
[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

#13 DevLiquidKnight   Members   -  Reputation: 834

Posted 06 February 2013 - 11:16 AM

....

 

That is what asymmetric cryptography solves. If I understand what you are saying correctly.


Edited by DevLiquidKnight, 06 February 2013 - 11:19 AM.


#14 Milcho   Crossbones+   -  Reputation: 1177

Posted 06 February 2013 - 11:25 AM

Isn't that still susceptible to man in the middle attacks [snip]

Yeah, I thought about that too, but your example makes it clear. Seems that it indeed would be.

 

That is what asymmetric cryptography solves. If I understand what you are saying correctly

My understanding of asymmetric cryptography is that you make the encryption key public, but the decryption key private, and generate those keys in a way that makes it hard to figure out the private key even if you know the public key. I was hoping that if you could keep both the encryption and decryption private you would get around that, but obviously as Cornstalks pointed out it's still quite vulnerable.



#15 SeraphLance   Members   -  Reputation: 1457

Posted 06 February 2013 - 11:29 AM

Both one-time pads and Diffie-Helman Key Exchange (what Milcho is describing) are vulnerable to man-in-the-middle attacks because in both methods, information must be sent insecurely before security can be established.

 

It's technically impossible to establish security insecurely.  At some point, you just have to take a shot in the dark, or connect to an existing infrastructure that already did (e.g. SSL).



#16 Bacterius   Crossbones+   -  Reputation: 9289

Posted 06 February 2013 - 11:30 AM

*snip*

Isn't that still susceptible to man in the middle attacks? i.e. what if the courier service doesn't deliver the package to person B, but instead puts their own lock on the chest and gives it back to person A. Person A has no idea the second lock on there is the courier's and not person B's, so they unlock their lock and send it back. The courier service now unlocks their own lock, observes the contents of the chest (changing them if they feel like it), puts their lock back on it, and sends the chest to person B. Person B doesn't know it's the courier's lock on there and not person A's, so they put their lock on it, send it back, and the courier service unlocks their own lock and returns the chest. Person B gets the chest, unlocks their own lock, and observes the contents of the chest (which now the courier service could have altered, or at least observed the secret).

 

Yes. Secure communication in the classical sense (i.e. no quantum key exchange) is unconditionally impossible* without securely pre-exchanging something. The shared information can take any form - SSL certificates are exactly that, since you trust that they prove the server's identity since they cannot be forged without attacking the SSL infrastructure (which is human-controlled and thus quite reliable).

 

My understanding of asymmetric cryptography is that you make the encryption key public, but the decryption key private, and generate those keys in a way that makes it hard to figure out the private key even if you know the public key. I was hoping that if you could keep both the encryption and decryption private you would get around that, but obviously as Cornstalks pointed out it's still quite vulnerable.

 

Yes, but the challenge is making sure the public key actually arrives to its destination. If you don't securely send your public key to the recipient, anyone can intercept it, replace it with his own public key, and mount an MITM. And now you have the same problem, how to send the public key securely? This is the problem SSL certificates solve.

 

* there are ways around this but they are quite unreliable (in particular, forcing the public key operations to take very long, so that an MITM can be detected temporally... but note this technically requires you to have access to a secure time source, and so on).


The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


#17 samoth   Crossbones+   -  Reputation: 5036

Posted 06 February 2013 - 11:32 AM

It is entirely possible to communicate securely without a friend, you should read more about cryptography.

Yes certainly, if you have a shared secret. Which you don't have.

Man in the middle attacks can be detected with modern day cryptography, and it is possible to authentic that who you are talking to is indeed who you intend to talk to.

Since I'm apparently lacking the cryptographic knowledge, would you care to explain how to detect MITM without a shared secret or a trusted party?

Seeing how you don't know the person you're talking to, how can you be sure that random-guy is not random-other-guy, and how can random-guy be sure that some message he receives is from you and not someone else?

Is this 100% full proof? No.

Which means no more and no less: You cannot securely communicate. Unless you re-define the word "secure" as something else. A secure scheme that is 99% secure is 0% secure.

SSL is not the only way secure communication can be achieved, you could simply use a one time pad.

Of course a one time pad is immensely useful for communicating with a stranger. It simplifies the communication greatly because you do not need logic for handling the message or its integrity. You can just write the output of rand() to a socket, because nobody is going to decipher it anyway :)

This goes hand in hand with compressing a message of any length to 4 bytes using a CRC. :)

#18 Bacterius   Crossbones+   -  Reputation: 9289

Posted 06 February 2013 - 11:36 AM

SSL is not the only way secure communication can be achieved, you could simply use a one time pad.

The one-time-pad doesn't provide "secure communication", it provides privacy (and only privacy) against a computationally unbounded attacker (an attacker with infinite computational power) which is anyway almost never required in any sensible modern security scheme (we tend to prefer practical security bounds to protect against attackers with reasonable computational power). And you require a pretty massive key exchange in order to make it work, so it doesn't really "solve" anything.


Edited by Bacterius, 06 February 2013 - 11:37 AM.

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


#19 DevLiquidKnight   Members   -  Reputation: 834

Posted 06 February 2013 - 11:46 AM

Since I'm apparently lacking the cryptographic knowledge, would you care to explain how to detect MITM without a shared secret or a trusted party?

Obviously a miscommunication problem here, I never said you did not need a third party to provide non-repudiation in this case. I merely stated its possible to communicate securely.

 

 

Which means no more and no less: You cannot securely communicate. Unless you re-define the word "secure" as something else. A secure scheme that is 99% secure is 0% secure.

Defining what security is, is an area of grays not black and whites. You trust your bank, its not 100% secure either. Most companies that require additional security will employ more then just cryptography.


 

Of course a one time pad is immensely useful for communicating with a stranger. It simplifies the communication greatly because you do not need logic for handling the message or its integrity. You can just write the output of rand() to a socket, because nobody is going to decipher it anyway.

I wouldn't use rand() its bound to be pseudo random.


Edited by DevLiquidKnight, 06 February 2013 - 11:58 AM.


#20 samoth   Crossbones+   -  Reputation: 5036

Posted 06 February 2013 - 12:34 PM

explain how to detect MITM without a shared secret or a trusted party?

Obviously a miscommunication problem here, I never said you did not need a third party to provide non-repudiation in this case. I merely stated its possible to communicate securely.
Man in the middle and non-repudiation are orthogonal. Please explain how to detect MITM without a shared secret or trusted party (using "modern cryptography")

Defining what security is, is an area of grays not black and whites.

It is indeed very black and very white. There is nothing in between being secure and not secure. Claiming something different, is somewhat disqualifying, if I'm allowed to say.

You trust your bank, its not 100% secure either.

A wrong analogy based on wrong assumptions. No sane person will trust a bank, not only because banks are demonstrably not secure, but more importantly because bankers are criminals. However, trusting a bank with your money is the lesser evil compared to having it in your house. The risk of losing everything is several orders of magnitude smaller (at least, in some countries).

A bank may not be perfectly safe against robbery, but the threshold is high, penalties are deterring, and there is an insurance. A communication protocol that is not perfectly safe against being tampered will be exploited the next day by every 12 year old downloading a script off the internet.

I wouldn't use rand() its bound to be pseudo random.

Any message encoded with a one time pad is as good as any other message of equal length, if you don't have the key -- since it is equivalent to every other message of equal length, depending on the key used.

Therefore, a pseudo-random message is not any worse than any other message. The unknown person you communicate with does not have the key, so gibberish remains gibberish. You can as well optimize this and use the output of rand() or send concatenations of "1234567890abcdef" (for every arbitrary message!). It is no more and no less meaningless.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS