Three Message Authentication Protocol

Question

I have a protocol where "A" initiates communication with "B". "B" then sends a challenge to check if "A" is really "A". "B" does not remember sending the challenge so "A" has to respond by sending the challenge back along with encrypted challenge with her key.

Example:

A ----Hi i am A-----> B
A <-- challenge --- B
A --- Challenge + Encrypted challenge ---> B

Modified

A ----Hi i am A-----> B
A <-- challenge + encrypted challenge with "B" key --- B
A --- Encrypted challenge with A+B Key ---> B

Are any of these two protocols secure for "A" authenticating itself to "B"?

Answer 1

So

A ----- says wants to contact B ----------------------->  B

A <---- encrypt some challenge with his private key ----  B

A ----- decrypt the challange with B public key
    encrypt the challange with A private key
    encrypt the challange with B public key
    send both to B ------------------------------------>  B

    decrypt the challange with A public key   ---------   B
    decrypt the challange with B private key
    they are the same? ok, so I could open a
        a message to me (good) that was sent
        from someone who have the A private key.

Problems with that:

• Does B have the public key from A?
• If not, where does he gets it ? (answer: some PKI ?)
• If yes, is he sure that the keys belongs to A? (answer: certificate)
• and he verifies that A's key is valid (answer: CRL or OCSP)
• Does A have the public key from B? The same questions apply.

Doing those verifications, it would work. Not doing then means that you'd have a problem with:

• A not knowing that he contacted B
• B not knowing he received a message from A

Answer 2

Your requirement is not very clear, I don't know what you mean by “A authenticating itself to B” (What does B know a priori about A? How do you test a successful authentication?), nor by encrypted challenge (encrypted by what). But the answer is probably no. Neither of these protocols guarantee that A sends the last message.

Assuming that only A can produce encrypted challenge from challenge, then all this protocol (either version) guarantees is that A has received a challenge that purported to be from B. If A will only produce its second message after having tried to contact B, then your protocol even guarantees that A has tried to contact B at some point. But an attacker can at the very minimum carry on a replay attack: record (and perhaps block) the response from A in the first step, then send it (possibly after modifying it) to B.

Note that even if B remembered that it had sent the challenge, this would not help. The attack only requires that the attacker can see the challenge.

To build a secure protocol, you first need to be more rigorous about your definitions: what kind of key (typically either shared symmetric or asymmetric) and what your high-level requirements mean concretely. Then you'll need to think about message integrity (what prevents an attacker from modifying a message in transit?). An easy way to ensure message integrity is to authenticate the message, and that requires (among other things) that A encodes the challenge with a secret that A knows.

Answer 3

In order to build a secure challenge-response system where the challenge is forgotten by the server before the response is returned, you have to make sure that an attacker can't send you a response to a challenge you didn't send, or a challenge that was directed toward someone else, or a challenge that is old or has already been used.

First of all, you can make sure that all of your challenges are genuine by "signing" them in some way. You don't have to use traditional signing protocols to do this since it's not a general-purpose signature. Instead, just take your existing challenge, append some "secret" string to it, and take a cryptographic hash of the result (e.g. SHA-256). Then include the hash as part of the challenge. When a you get a challenge back from the client, you can verify its authenticity by repeating the process, and comparing the transmitted hash with the one you compute. If space is a premium, you only need to include a small subset of the entire hash.

To make sure that challenges can't be used to authentiate against someone else's account, you can make the account identification part of either the challenge itself, or part of the authentication described above. That is, instead of just appending a "secret" string, you can append both the username AND a secret string, and then hash THAT. Similarly, you can tie challenges to a given connection ID, IP host address, etc., by incorporating that information into the signature.

Finally, you can make challenges time-sensitive by incorporating the current time into the challenge content, and you can prevent replay attacks by giving each challenge an ID and disallowing responses that refer to an already-used ID.

Your system can look like this, as an example. Note that this example is just off the top of my head, while yours should probably be a bit more sophisticated than this. But this at least demonstrates how such a system could work.

Client:  
 say: My name is "Alice"

Server:
 *    super-secret key is "swordfish"  
 *    sha1sum("Alice|30Nov11@12:03|swordfish")="4f9167de1e754d...."
 say: Please sign this string: "Alice|30Nov11@12:03|4f9167de1e"  

Client:
  * password is "mustang"
  * sha1sum("Alice|30Nov11@12:03|4f9167de1e|mustang")="6148f8d7bd9eeb6...."
  * say: Challenge was "Alice|30Nov11@12:03|4f9167de1e"
  * say: Response is "6148f8d7bd9eeb6c9156c5be385e96871721f6df"

Server:
  * verify that user's name is in the challenge
  * verify that timestamp is no more than 5 minutes in the past
  * verify that "4f916..." corresponds to challenge with checksum replaced by "swordfish"
  * verify that response is challenge with user's password appended