Authentication Using Asymmetric Keys Haipeng Dai haipengdai@nju.edu.cn 313 CS Building Department of Computer Science and Technology Nanjing University
Authentication Using Asymmetric Keys Haipeng Dai haipengdai@nju.edu.cn 313 CS Building Department of Computer Science and Technology Nanjing University
Authentication Problem:How do you prove to someone that you are whom you claim to be? Any system with access control must solve this problem. ■ Goals: -1.Mutual Authentication:each party authenticates itself to the other party. -2.Key Establishment:establish a session key.This session key will be used to encrypt and decrypt messages between the two parties using symmetric key cryptography. Methods -Authentication with asymmetric keys -Authentication with symmetric keys -Human authentication 2
2 Authentication Problem: How do you prove to someone that you are whom you claim to be? Any system with access control must solve this problem. Goals: ─ 1. Mutual Authentication: each party authenticates itself to the other party. ─ 2. Key Establishment: establish a session key. This session key will be used to encrypt and decrypt messages between the two parties using symmetric key cryptography. Methods ─ Authentication with asymmetric keys ─ Authentication with symmetric keys ─ Human authentication
Authentication Using Asymmetric Keys Assumption -Everyone knows your public key -No one(except you)knows your private key Threat Model (i.e.,what we assume attackers can do): -Message injection Inject a new message into a channel,e.g.,TCP poisoning attacks injecting TCP RESET. Message modification Modify a message in a channel -Message loss .Delete a message in a channel -Message replay Replay an old message.The message is authentic,but old. 3
3 Authentication Using Asymmetric Keys Assumption ─ Everyone knows your public key ─ No one (except you) knows your private key Threat Model (i.e., what we assume attackers can do): ─ Message injection ● Inject a new message into a channel, e.g., TCP poisoning attacks injecting TCP RESET. ─ Message modification ● Modify a message in a channel ─ Message loss ● Delete a message in a channel ─ Message replay ● Replay an old message. The message is authentic, but old
Version 1 A,n,(nPRA Alice (Private key PRA Public key PUA) Bob Here n denotes a nounce. An ideal nounce has two properties Freshness(No repetition) -Each nounce is used at most once during any infinite execution of a protocol ●Unpredictability -Knowing all nounces used in the past does not help to determine the next nounce to be used -In practice,it is simulated using a large random number. -Sometimes we only need the freshness property.In this case,we can use: Increasing sequence number.The sender needs to remember the last sequence number.The numbers may increase randomly each time. Real time,i.e.,time stamp. 4
4 Version 1 Here n denotes a nounce. ─ An ideal nounce has two properties ● Freshness (No repetition) – Each nounce is used at most once during any infinite execution of a protocol ● Unpredictability – Knowing all nounces used in the past does not help to determine the next nounce to be used ─ In practice, it is simulated using a large random number. ─ Sometimes we only need the freshness property. In this case, we can use: ● Increasing sequence number. The sender needs to remember the last sequence number. The numbers may increase randomly each time. ● Real time, i.e., time stamp. Alice (Private key PRA, Public key PUA) Bob A, n, {n}PRA
Version 1 A,n,{npRA Alice Bob Question 1:Can we replace (n)by nUA? -Answer:No.Everyone knows PUa and can compute {n}PUA. Question 2:What is wrong with this authentication protocol? -Answer:No.An attacker can replay this message later to authenticate himself to Bob. -How to fix this problem? 5
5 Version 1 Question 1: Can we replace {n}PRA by {n}PUA ? ─ Answer: No. Everyone knows PUA and can compute {n}PUA . Question 2: What is wrong with this authentication protocol? ─ Answer: No. An attacker can replay this message later to authenticate himself to Bob. ─ How to fix this problem? Alice Bob A, n, {n}PRA
Version 2 A n Alice n PRA Bob Now attackers cannot replay (n}PRA Question:What is wrong with this authentication protocol? -No session key is established. -Authentication-mutual identity verification session key establishment -How to fix this problem? 6
6 Version 2 Now attackers cannot replay {n}PRA. Question: What is wrong with this authentication protocol? ─ No session key is established. ─ Authentication= mutual identity verification + session key establishment ─ How to fix this problem? Alice Bob A n {n}PRA
Version 3 A n Alice (n,Kab PRA Bob Kab denotes a session key Question:What is wrong with this authentication protocol? -Answer:Attackers can see Kab because they know Alice's public key. -How to fix this problem? 7
7 Version 3 Question: What is wrong with this authentication protocol? ─ Answer: Attackers can see Kab because they know Alice’s public key. ─ How to fix this problem? Alice Bob A n {n, Kab}PRA Kab denotes a session key
Version 4 A n Alice in,KabPRAJPUn Bob Kab denotes a session key Only Bob can decrypt{KU Denning Sacco "Time Stamps in Key Distribution Protocols"(1981) Question:What is wrong with this authentication protocol? Answer:vulnerable to man-in-the-middle attacks: 一 the attacker makes independent connections with the victims and relays/modifies/injects/deletes messages between them. 8
8 Version 4 Only Bob can decrypt {{n, Kab}PRA}PUB. Denning & Sacco “Time Stamps in Key Distribution Protocols” (1981) Question: What is wrong with this authentication protocol? Answer: vulnerable to man-in-the-middle attacks: ─ the attacker makes independent connections with the victims and relays/modifies/injects/deletes messages between them. Alice Bob A n {{n, Kab}PRA}PUB Kab denotes a session key
Man-in-the-middle (MITM)Attack on Version 4 Alice I am Robert I am Alice Bob Robert A n (n,KarPRA PUR Now,Robert knows Ka {(n KarpRA)PUn When Alice begins to talk to Robert,Robert starts to talk to Bob as Alice. Question:How to fix this problem? -Solution 1:use {fn,Kar}PURPRA to replace {fn,Kar)PRA)PUR - Solution 2:use {(n,R,Kar)PRA}PUR to replace {n,KarPRA)PUR Principle:Encryption should be inside a signature,otherwise we need to include principal's names. 9
9 Man-in-the-middle (MITM) Attack on Version 4 When Alice begins to talk to Robert, Robert starts to talk to Bob as Alice. Question: How to fix this problem? ─ Solution 1: use {{n, Kar}PUR}PRA to replace {{n, Kar}PRA}PUR. ─ Solution 2: use {{n, R, Kar}PRA}PUR to replace {{n, Kar}PRA}PUR. Principle: Encryption should be inside a signature, otherwise we need to include principal’s names. A n {{n, Kar}PRA}PUR Alice Bob A n Robert {{n, Kar}PRA}PUB Now, Robert knows Kar I am Robert I am Alice
Version 5 A n Alice {n Kabj PUBPRA Bob KAB denotes a session key Now only Alice and Bob can know the session key KAB Question:What is wrong with this authentication protocol? -Authentication-=mutual identity verification session key establishment 一 Bob authenticates Alice,but Alice did not authenticate Bob. -How to fix this problem? 10
10 Version 5 Now only Alice and Bob can know the session key KAB. Question: What is wrong with this authentication protocol? ─ Authentication= mutual identity verification + session key establishment ─ Bob authenticates Alice, but Alice did not authenticate Bob. ─ How to fix this problem? Alice Bob A n {{n, Kab}PUB}PRA KAB denotes a session key