Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Let assume two participants Alice and Bob who perform a given protocol which is a sequence of messages exchange between them.
My question is: How can I provide a secure and authentic communication channel using cryptography, so that when Bob sends a message "M" to Alice, the latter will be able to know whether or not the message "M" is from Bob?
Is there a solution without using certificates?
"Authentic" is defined with regards to an identity. A message from Bob is authentic only insofar as Bob is distinct from Charlie. There must be something which, from the outside, makes Bob and Charlie two different entities.
In a computerized world with networks, Alice can "see" other people only through the data they send. Moreover, everybody can buy a computer, so what Bob can compute, so can Charlie. The only remaining way for Bob to be distinct from Charlie is what Bob knows. That's how identities are defined in cryptography: you are what you know.
So Alice can make sure that a given message $M$ comes from Bob (and not Charlie) only if Bob does some computation over the message $M$ which involves some data that Bob knows, but not Charlie.
A basic, traditional setting is when the "secret" known by Bob is a sequence of bytes which Alice knows too. That sequence of bytes can then be used as key in a Message Authentication Code: this is a kind of checksum, which Bob can compute over $M$, and that Alice can recompute over $M$ since she also knows the "secret"; that's how Alice verifies the MAC. But Charlie cannot compute the MAC since he does not know the secret. The shared secret can also be used as key for symmetric encryption, so that the message contents can remain confidential: there again, Alice can decrypt the data encrypted by Bob (since she knows the secret) but Charlie cannot. Combining symmetric encryption and a MAC while using the same secret as key for both can be somewhat perilous; there are subtleties.
The traditional scheme has the drawback of having a shared secret between Alice and Bob: since identities are "what we know", this means that Alice and Bob are really the same entity, "Bobalice". The scheme above is about Bobalice talking to himself/herself. That's not a useless model: that's what happens when you encrypt some data so that you can store it, and decrypt it back later; i.e. you are talking with yourself through time. In practice, for two distinct human beings, this means that Alice can authenticate Bob's message, but cannot prove it, because whatever MAC Bob computes, Alice could have computed as well. Also, setting up a shared secret between two people can be hard in some contexts (they must have met beforehand, or something like that). Finally, in the context of software (which is, by definition, quite dumb), there can be some issues if an attacker tries to send back to Alice one of her own messages: Alice knows that a message $M$ is from Bob because only Alice and Bob know the secret value which is needed to compute the MAC, and (that's the critical point) Alice remembers that she did not send that specific message -- so it must be from Bob. The "remember" bit can be tricky; a simple way is to add the sender name in each message (so that a message from Alice always begins by "From Alice").
To go further, we need public key cryptography. This leads to the following protocol: Bob has a key pair for an asymmetric encryption algorithm (e.g. RSA) or a key exchange algorithm (e.g. Diffie-Hellman). The "public" part of the key is known by everybody (that's what "public" means), including Alice. The "private" part of the key is known by Bob only (it is "private"). Alice choose a random sequence of bytes $K$ and encrypts $K$ with Bob's public key; she sends the result to Bob. Bob uses his private key to decrypt $K$, at which point ALice and Bob have a shared secret ($K$) and they can use it as above, with symmetric encryption and a MAC.
With public key cryptography, Bob is distinct from everybody else, including Alice; he has his very own private key. Bob's identity is defined as "whoever controls the private key corresponding to that public key". This still requires Alice to be able to know, in a reliable way, Bob's public key, where "reliable" means that Alice will not be induced into mistakenly using Charlie's public key. That's where certificates come into play: a certificate is a piece of data which is signed by an authority and says: "this is Bob's public key". It is a way to distribute public keys (and their binding to identities) in a verifiable fashion. There can be other ways.
For instance, in the SSH protocol, a client (which tries to connect to a remote server) knows the server public key by remembering it (the client stores a local copy of the public key). This requires a specific bootstrap procedure, for the first time the client connects to a given server, but afterwards the server key is known to the client, and the client just uses it to authenticate the server.
There needs to be some secret or private information which Bob knows (and a possible attacker doesn't), and we need a way how Alice somehow can check that Bob has this information.
This could be a private key, where Alice knows the corresponding public key (and that it is owned by Bob). Then Bob can use the private key to sign the message M, or some messages used during the negotiation of the channel, to make sure that there is no man-in-the-middle attack. The custom way to make sure that Alice knows that Bob is the owner is by providing a certificate which states this, but any other way (i.e. they did meet before) would work, too.
Another possibility would be a shared secret, like a password. Of course, Bob can't simply send the password with the message (at least, if he isn't sure about Alice's identity and the confidentiality of the connection), as then an interceptor can read the password. But Bob and Alice both can derive a key from the password , and use this key as the authentication key for a MAC (message authentication code), accompanying the message. (You can also derive an encryption key from this password, to also get confidentiality.)
More elaborate protocols allow that Alice doesn't have Bob's password itself, but only a "password verifier", which allows checking that Bob has the password, but is not enough to authenticate a message by itself.
All three methods are available with the SSL or TLS protocols: the first is usually done with certificates, but also works without them (or using self-signed certificates), as long as Alice can somehow verify Bob's public key. The second is known as "pre-shared key", the third one as SRP (both TLS extensions).
Yes, of course there is a way.
Paulo answered in the context of generating the cryptographical session (that is, when Alice starts the conversation, how does she know she's really talking to Bob); I'll answer in the context of the actual messages (the session she originally established is with Bob, but how does she know that the message she just got is from Bob as well).
Well, the mechanism that's most common method uses a 'Message Authentication Code' (or MAC). This is a cryptographical primitive that takes a message and a key, and generates a 'tag'. The fundamental property of a MAC is that if you don't know the key, you cannot generate the 'tag' for any message (even if you've seen other message/tag pairs with the same key). One common MAC is called HMAC (see http://en.wikipedia.org/wiki/HMAC )
Now, when you generate the cryptographical session, we generate session keys that both Alice and Bob know (and no one else); we use those keys to encrypt the traffic. So, what we do is also generate a pair of MAC keys as well (one to authenticate the traffic from Alice to Bob, and one to authenticate the traffic from Bob to Alice).
Now, when Bob sends a message to Alice, he takes his copy of the "Bob to Alice" MAC key, and uses it to compute the MAC of his message; he then appends that message to the encrypted message.
And, when Alice gets this message, she takes her copy of the "Bob to Alice" MAC key, and computes the MAC of Bob's message. She then compares the MAC that she computed with the MAC she finds in the message. If the two MAC compares, she accepts the message.
Here is why this works: she knows that only someone who knows the MAC key can generate a MAC correctly. She also knows that there are only two people who knows that key; herself and Bob. She also knows that she'll never create a message based on that key (she uses another MAC key when sending a message to Bob), and so the message must have come from Bob (and wasn't modified in transit).
