Internet is perhaps one of the few places where almost everyone (most people have access to it) can express himself/herself. That gives the people great power and thus most governments try to control this free flow of information by monitoring all communications: chat, emails, instant messaging etc,
supposedly to prevent terrorism...
Whether the governments lie or not, I will not analyze it here. What I really know is that everyone deserves privacy. I can always whisper a secret and no law can prohibit me doing so. The same should apply to my Internet communications. I want to be able to say things to a friend without any government or person been able to
eavesdrop or interfere. And this can be done with strong encryption.
Encrypted communication is for me one of the best things a computer has to offer compared to a phone. There are two different kinds of encryption:
symmetric and
asymmetric.
Symmetric cryptography is the most known. The algorithms that implement this kind of encryption are not so computationally intensive. It uses only one key which both parts (the people that want to communicate) must already know and this is the main disadvantage. This can be done either during a face-to-face meeting or over another secure channel.
But what happens when you have no way of agreeing on a key with the other part? That's when public key encryption (asymmetric encryption) comes in. In asymmetric encryption there are two keys: the public one and the private one. You use the public key to encrypt a message which can only be decrypted by the corresponding private key. So in order to communicate safely with someone you follow these steps:
- Each of the two parts generate a pair of public - private keys.
- The two parts exchange their public keys over a possibly insecure communication channel.
- Now if one part wants to send a message to the other it simply encrypts it with the public key of the other part and then sends it. An eavesdropper cannot decrypt this message because he has not got the private key needed.
But even this type of encryption is not completely secure. One possible vulnerability is exploited with a
man-in-the-middle attack. Here is a possible scenario where Bob wants to talk with Alice while Mario performs a MITM attack.
- Bob generates a keypair. (a public and a private key) and sends his public key to Alice.
- Mario, who is an employer in Bob's ISP, has already generated a keypair and while the packet with Bob's key is transient he replaces Bob's key with his own (he also notes down Bob's public key).
- Alice receives Mario's public key but she believes it's Bob's.
- Alice generates a keypair and sends her public key to Bob but Mario replaces it with his own, just like he did with Bob's.
- Now Bob wants to send some data to Alice. He encrypts it with Mario's key believing that it's Alice's key and sends the encrypted data.
- The encrypted data is peaked by Mario who is able to decrypt them with his own private key. He then re-encodes them with Alice's correct public key and passes them on Alice.
- The same thing happens when Alice replies to Bob. Mario is able to eavesdrop on the connection even though both part's think that is secure.
There are, of course, some ways to reveal MITM attacks. One of them involves trusted third parties which are called
Certificate Authorities (CA) because they verify that the public keys have been exchanged correctly. In fact whenever you login to your Paypal, email etc account with a secure connection you do make an asymmetrically encrypted connection with that site. But, in order to ensure that there is no man in the middle, your browser also establishes another secure connection to a Certificate Authority (like
StartCom) in order to check the integrity of the public key you just received. The connection to the Certificate Authority is also asymmetrically encrypted but the public key of the CA is already embedded in your browser since you downloaded it.
So? Are our connections now safe? Well, your bank transactions are secure but the MITM problem remains for other types of communication. What if you want to communicate with a friend with a program that supports asymmetric encryption? You can't use a CA in this case because there can't be someone that knows the public keys of every user you chat with. Let alone that in some cases you might not trust anyone, not even a CA.
There are some other solutions to this problem. I read about a protocol called "Socialist Millionaire Protocol" that is used by
Off-The-Record Messaging (a secure instant messenger). Here is a copy-paste from
http://www.cypherpunks.ca/otr/Protocol-v2-3.1.0.html regarding the protocol:
While data messages are being exchanged, either Alice or Bob may run SMP to detect impersonation or man-in-the-middle attacks. As above, all exponentiations are done modulo a particular 1536-bit prime, and g1 is a generator of that group. All sent values include zero-knowledge proofs that they were generated according to this protocol, as indicated in the detailed description below.
Suppose Alice and Bob have secret information x and y respectively, and they wish to know whether x = y. The Socialist Millionaires' Protocol allows them to compare x and y without revealing any other information than the value of (x == y). For OTR, the secrets contain information about both parties' long-term authentication public keys, as well as information entered by the users themselves. If x = y, this means that Alice and Bob entered the same secret information, and so must be the same entities who established that secret to begin with.
I tried to understand the algorithm but I couldn't! And I think that it's too complex for no reason... They could use this protocol to achieve the same thing:
- Bob knows X and Alice knows Y and they want to compare them.
- Bob sends some random data to Alice. Alice does the same with some other random data.
- Bob appends X to the end of the data he received and then computes the hash of the new data. Alice appends Y to the end of the data she sent to Bob and computes the hash of the new data. Bob sends the hash to Alice. Alice checks whether the two hashes are the same.
- Alice appends Y to the end of the data she received and then computes the hash of the new data. Bob appends X to the end of the data he sent to Alice and computes the hash of the new data. Alice sends the hash to Bob. Bob checks whether the hashes are the same.
I think that this is a much simpler (to understand) protocol that achieves the same things.
I also came up with another protocol which guarantees that there is no one eavesdropping. It doesn't detect impersonations, just eavesdroppers. In fact it's not a new one, it's just an improved version of the protocol I used in SePuKTra (which you can download from
here but as I said it is not the new version of the protocol). The new protocol is much faster and like the old one it reveals man-in-the-middle attacks by measuring delays that the MITM is obliged to cause due to the nature of the protocol.
First of all some symbolisms:
- H(x) is the hash of x. Any hash function can be used. Take a look at MD5.
- E(x,k) is the symmetrically encrypted data of x with k used as the encryption key.
- DE(x,k) is the symmetrically decrypted data of x with k used as the decryption key.
- PK is the public key of the sender.
- RDP means Random Data Padding.
- & is the concatenation symbol (VB-style :-P).
- len(x) is the length in bytes of x.
The packets that are exchanged with this protocol can be placed in three categories and are all of a fixed length and why we will pad the messages with random data:
- D: The Data packet. It is composed of 4 parts:
len(RDP) & RDP & H(K) & E(PK & data,k)
- A: The Acknowledge packet. It is composed of 3 parts:
RDP & H(D)
- K: The Key packet. It is composed of 4 parts:
RDP & H(A) & k
Each part should run a
FSM that executes these steps:
- Exchange public keys with the other part and start an encrypted connection.
- If you are the part that initiated the connection then set time1=0 time2=inf and jump to step 11.
- Generate a random key (k) for a symmetric encryption.
- Read data (data) from user.
- Calculate E(data,k) and H(K) (where K is the last K packet received).
- Note down the current time (time1).
- Send a D packet (with the structure described above).
- Wait for an A packet.
- Note down the current time (time2).
- Send a K packet containing the H(A) and the key (k) you used in step 5.
- Wait for a D packet and store the encrypted data (data) it contains.
- Note down the current time (time3).
- If (time2-time1)*2<=(time3-time2) then either there is a MITM or you connection is really unstable.
- Send an A packet containing H(K).
- Wait for a K packet and store the key (k) it contains.
- Show DE(data,k) to the user.
- Jump to step 3.
The two parts should communicate in this mode for some time and then they may switch to normal communication using the same public keys.
Let's see how this works. While Bob chats with Alice the program includes the PK of Bob in every message he sends. Normally Mario would try to replace this PK with his own in order not to be discovered by Alice. But because the D packets contain the PK encrypted with a random key this replacement cannot be done immediately. So Mario has to withhold the D packets until the K packet arrives form Bob. This delay is visible to Alice because (time3-time2) becomes around 4 times bigger than (time2-time1). Mario could make this delay seem natural by artificially increasing (time2-time1) by delaying to send A packets to Alice but doing so would create even more delay on the side of Bob! So Mario can trick one of the two parts that the delays are natural but never both! In order to trick them both he might want to try and send A packets before receiving the D packet and K packets before receiving A packets (in order to create "negative" delays to both sides) but this cannot be done because every packet should include the hash of the very previous packet.
That's all for now. I will try to upload some sketches that visualize what I wrote. I am waiting for your comments!!!
