# Please punch holes in this authentication scheme

Folks, I am undertaking a crypto course in Uni. Our professor asked us to try and design some authentication schemes which are resistant to active attacks. This was just a in class exercise to get us interested in the topic. It did the trick, I have been trying to come up with something using what we have learned so far.

Here is a authentication scheme I developed :

Please punch holes through it and tell me what attacks are these vulnerable to?

P.S - Notation explanation : Ka+(Rb) denotes the encrypted text that was generated by encrypting the nonce generated by Bob using Alice's public key. This text is decrypted by Alice using her private key Ka- and gets Rb. Alice then encrypts Rb with her private key and sends it to bob. Who then uses Alice's public key to decrypt the message and get text. If this text is same as Rb then alice Has been authenticated to Bob

Similarly Ka-(Rb) denotes encrypted text obtained by encrypting nonce generated by Bob using alice's private key

P.P.S - Before you guys suggest Man-In_middle attack : Here is why I think it wont work :

-
Just to be clear, Alice and Bob know each other's public key before that protocol begins, right? – Gilles Oct 3 '13 at 12:15
Yes public keys are known – sukhvir Oct 3 '13 at 12:15
cleaned up comments dealing with minor mistake – mikeazo Oct 3 '13 at 14:09
@suhhvir: the sentence "Alice (then) encrypts Rb with her private key" is vague. First, a private key typically decrypts or sign, anything else must be defined precisely. Aloo, could it be that you considering the public (resp. private) xxcryption to be just $x\mapsto x^e\bmod N$ (resp. $x\mapsto x^d\bmod N$) where $(N,e)$ and $(N,d)$ are an RSA public/private key pair? That would be a serious (and classical) mistake. See e.g. this on the pitfalls of no or poor padding. – fgrieu Oct 3 '13 at 14:29
for the purpose of this exercise please assume that the encryption is very strong. and I am not using simple rsa encryption as you stated The question i am asking is : is this authentication scheme solid or are there attacks it could be vulnerable to? Attacks being : masquerade , modification , man-in-middle , replay etc. attack on the encryption is very general - it doesn't negate the logic behind this authentication. One can always change the encryption scheme to a stronger one. But changing the logic behind authentication is quite another matter – sukhvir Oct 3 '13 at 14:30

The protocol's description includes "Alice then encrypts $R_B$ with her private key". This has no standard meaning. Comments have clarified it is used an "RSA encryption scheme with proper padding" and I am taking as granted that encryption of $R_B$ using the private key half of $K_A$, denoted $K_A^-(R_B)$, is obtained by padding $R_B$ as in encryption, then applying the RSA private key exponentiation of $K_A$. This can be a valid form of signature (while RSA signature and encryption usually use different padding, it is possible to define a secure padding that works for both encryption and signature).

The protocol does nothing to prevent a MitM attack. In the usual definition of that, Charlie's goals are:

• impersonate as Alice to Bob, or/and to Bob as Alice;
• be able to understand all that Alice says to Bob, or/and Bob says Alice;
• be able to make Alice believe that something Charlie decides comes from Bob, or/and make Bob believe that something Charlie decides comes from Alice.

In order to achieve every single of these goals, Charlie:

• receives "I'm Alice" from Alice, relays that to Bob;
• receives "I'm Bob" from Bob, relays that to Alice;
• receives $K_A^+(R_B)$ from Bob, relays that to Alice; (I'm using the first drawing as reference, where's that before the next step)
• receives $K_B^+(R_A)$ from Alice, relays that to Bob;
• receives $K_A^-(R_B)$ from Alice, relays that to Bob, and also applies Alice's public key to that and removes any padding, thus getting $R_B$;
• receives $K_B^-(R_A)$ from Bob, relays that to Alice, and also applies Bob's public key to that and removes any padding, thus getting $R_A$.

From then on, Charlie acts with respect to Alice using the (unspecified) protocol defined for Bob, including deciphering Alice's messages, and forwarding anything Charlie decides to Alice, which has no way to tell that it comes from Charlie rather than Bob; and similarly acts with respect to Bob using the (unspecified) protocol defined for Alice.

Charlie reached all his goals. The only thing that Charlie does not know is the padding used in $K_A^+(R_B)$ and $K_B^+(R_A)$ if that's random padding, but there is no indication that some use is made of it.

Further, if for some reason Charlie wants to choose his own nonce $R_C$ as in the second drawing, rather than use $R_A$ or $R_B$ (perhaps because the protocol is extended with "After authentication, perform the action defined in the low 20 bytes of the $R$ that I sent"), Charlie can still achieve that. In order to impersonate Alice w.r.t. Bob using an $R_C$ of Charlie's choice instead of $R_A$ chosen by Alice, Charlie

• receives "I'm Alice" from Alice, relays that to Bob;
• receives "I'm Bob" from Bob, relays that to Alice;
• receives $K_A^+(R_B)$ from Bob, relays that to Alice;
• receives $K_B^+(R_A)$ from Alice, discards this, computes $K_B^+(R_C)$ and sends that to Bob;
• receives $K_A^-(R_B)$ from Alice, relays that to Bob, and also applies Alice's public key to that and removes any padding, thus getting $R_B$;
• kills the session with Alice;
• receives $K_B^-(R_A)$ from Bob, discards it.

From then on, Charlie acts with respect to Bob using the (unspecified) protocol defined for Alice, including deciphering Bob's messages, and forwarding anything Charlie decides to Bob, which has no way to tell that it comes from Charlie rather than Alice.
Kudos to mikeazo for finding a mistake, hopefully fixed.

In a comment to the present answer, the protocol is extended by adding:

Alice sends Bob a pre-master secret encrypted in Bobs public key; then both of them use this premaster to calculate master secret.. and communicate using that key"

That extended protocol is still vulnerable to an attack where Charlie impersonate Alice with respect to Bob. Charlie performs as in the first attack, then

• kills the session with Alice;
• pretending to be Alice, sends Bob a pre-master secret of Charlie's choice encrypted in Bobs public key;
• then Bob and Charlie use this premaster to calculate the master secret.

In fact, no addition after the protocol can protect against a MitM attack, unless it uses another public key of the participants, or another padding scheme with the existing key.

That's because Alice's behavior allows using her as a decryption oracle: by participating in the beginning of whatever extension of the protocol, Alice accepts doing steps that can be abused into the equivalent of decrypting anything with her private key, and since no other use is defined for her private key, making a fake connection attempt with Alice is as good as having Alice's private key.

The protocol can be strengthened, and the unclear "encrypt with private key" removed, as follows.

We consider an asymmetric encryption scheme with encryption $E_{Pub}(P)\mapsto C$ and decryption $D_{Priv}(C)\mapsto P$. We assume an infrastructure to verify the validity of public keys.

A participating entity $A$, when communicating with (alleged) entity $B$

1. sends I'm $A$, and receives I'm $B$;
2. checks that $B\ne A$;
3. obtains the authentic public key $Pub_B$ of $B$ (how is not part of this protocol; a common technique is that $Pub_B$ is sent together with I'm $B$ as part of a certificate, which is verified according to a master public key);
4. draws a secret random $R_A=R_{A0}||R_{A1}||R_{A2}$ where each $R_{Aj}$ is 256-bit;
5. enciphers $R_A$ using $Pub_B$, yielding $C_A=E_{Pub_B}(R_A)$, sends it, and receives an alleged $C_B$;
6. deciphers $C_B$ using $Priv_A$, yielding $R_B=D_{Priv_A}(C_B)$ (or an error, which aborts the protocol);
7. breaks $R_B=R_{B0}||R_{B1}||R_{B2}$ into $R_{B0}$, $R_{B1}$, $R_{B2}$;
8. sends $R_{B0}$ and receives an alleged $\widehat{R_{A0}}$;
9. compares $R_{A0}$ and $\widehat{R_{A0}}$ (an inequality aborts the protocol);
10. uses $R_{A1}\oplus R_{B2}$ as an AES-GCM key for communication from $A$ to $B$, and uses $R_{A2}\oplus R_{B1}$ as an AES-GCM key for communication from $B$ to $A$.

Messages are exchanged at steps 1, 5, 8, and 10 only. The order in which messages are sent and received in these steps is left unspecified, so that $A$ and $B$ can proceed without waiting for the other side between steps involving message exchange. Step 2. is necessary, otherwise an adversary reflecting what Alice sends will successfully make Alice accept whatever information she sends at step 10.

This protocol is better than the original. At least, a passive eavesdroper can not decode the information exchanged at step 10, as would have been possible in the original protocol. However this scheme is still NOT secure against a MitM attack assuming only that $E_{Pub}(P)\mapsto C$ perfectly preserves confidentiality. In particular, an attack is possible when $E_{Pub}$ encrypts each bit of the plaintext $P$ separately; finding this attack is left as an absolutely necessary exercise to any reader diving into protocol design.

When $E_{Pub}(P)\mapsto C$ is one of the RSA encryption scheme in PKCS#1, or when we remove steps 7. and 8. (making $R_{A0}$ and $R_{B0}$ pointless), I can not think of any mean for a MitM to intercept or alter any part of the plaintext exchanged at step 10, provided $A$ and $B$ act according to the protocol, and in particular never disclose or use any of $R_A$, $R_B$, $R_{A1}\oplus R_{B2}$, $R_{A2}\oplus R_{B1}$ other than as instructed.

-
regarding your first part: In that scenario Charlie is merely acting like a server relaying the information . This isn't a MITM attack as the goal there is to get the information being traded after authentication. Now he hasn't authenticated himself to either Alice or Bob ... He has merely relayed info. All he has is Ra and Rb ... its much like SSL hello . Client_hello random and Server_hello random are known to anyone looking into the connection... but both these hello values are used later in addition to pre master secret to get a master secret – sukhvir Oct 3 '13 at 22:24
If i were to suggest that after successful authentication as described above in my post ... Alice sends bob a pre-master secret encrypted in Bobs public key . then both of them use this premaster to calculate master secret.. and communicate using that key . Charlie is left with nothing but Ra and Rb and a whole lot of nothing as he hasn't authenticated himself to either party – sukhvir Oct 3 '13 at 22:27
Regarding your second scenario as to Charlie giving out his own nonce . hre is why that won't work: imgur.com/iDLoQa9 – sukhvir Oct 3 '13 at 22:28
@sukhvir: Examples of attacks that fail are no good indication of security. Indeed the MitM in my original attack does not alter any message until after the authentication. He can successfully do these later alterations because in the first part, he managed to find $R_A$ and $R_B$ (using the method in the first paragraph of mikeazo's answer); that would allow him to derive the "symmetric encryption key (incorporating $R_A$ and $R_B) for future encryption", allowing to alter later messages. A passive adversary could only decipher. – fgrieu Oct 4 '13 at 20:05 Why does Alice encrypt$R_C\$ instead of a random value? – mikeazo Oct 4 '13 at 20:20

I think you have to specifically define what you're trying to do. Just "authentication" doesn't quite make sense from a practical stand point.

I can thinking of saying "hello" to someone for the purpose of "ok, if you get a hello from me then attack!!", but that protocol would look differently than what you're trying to do.

Why would you just "authenticate"? Can you help me out with that one?

Exchanging message for the purpose of sharing private symmetric keys makes sense, or sending each other secret messages just using asymmetric keys even makes sense (though slow, obviously), but just "authenticating" is odd .. and really doesn't do anything, because without the shared symmetric keys there is no promise that future chat will not be vulnerable to a MITM attack.

And therefore this is probably the best place to look for attacks. It may also be that you don't understand the question as asked, because it'd be odd for a professor to ask it that way. You might want to revisit the problem statement.

As for attack, can you tell me what happens if an attacker in the middle just delayed a message. Do we retransmit? Do we care if the other person actually got the message? What's the protocol? What happens if the message is corrupted? What's the agreement? Again, Do we retransmit or start with a whole new handshake? What happens if you do get a message but you got it slowly? If there was a retransmit, that message might be out of date and you shouldn't reply because another is forthcoming.

We (and your professor) can generously assume for you what it should do, but that's not really how you define protocols :)

Also, if you really are just 'authenticating' (whatever that means) why not just sign a timestamp and send that to each other? Again, I'm not entirely clear on what you're trying to achieve so I pose that really only to inspire an answer.

Perhaps you're trying to come up with a scheme that establishes that both parties have talked and confirmed that they're still alive at the current date. That, again, is a different protocol than what you're trying to do.

In particular, it suffers from an attack in that the final message could be delayed permanently. How does bob know that alice got his final message?

Unless you define exactly what 'authentication' means, it's hard to poke holes. If you define authentication as precisely meaning whatever your protocol supports, then yes, you have performed authentication.

BTW, you mentioned this is like ssl client/server hello. yes those are in the clear, you'll also notice they don't involve certificates or are encrypted (which comes later in the handshake). I think that false analogy is another example of the root of your misunderstanding of the problem.

-