COMP 4337/9337 Authentication, Key Distribution
Authentication, Key Distribution
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
WK02-02: Authentication, Key Distribution
(Asymmetric)
Securing Fixed and Wireless Networks, COMP 4337/9337
Today’s Agenda
▪ Authentication Recap
▪ Key distribution using asymmetric encryption
▪ Public-key distribution of secret keys
▪ Introduction to Formal Method for Protocol Specification and
Verification: AVISPA Tool
Recap
*Did anyone bother to look
at lightweight encryption?
Recap Authentication Basics
▪ Quick recap, possibly already done in 3331/9331
(Kurose-Ross Ch8)
▪ These are basic building blocks
▪ Make sure you understand this well as they help
material covered in this subject.
Authentication
▪ Goal: Bob wants Alice to“prove”her identity to him
▪ Protocol ap1.0: Alice says “I am Alice”
Failure scenario??
“I am Alice”
Authentication
▪ Goal: Bob wants Alice to“prove” her identity to him
▪ Protocol ap1.0: Alice says “I am Alice”
In a network,
Bob can not “see” Alice, so
Eve simply declares
herself to be Alice
Authentication: Another try
▪ Protocol ap2.0: Alice says “I am Alice” in an IP packet containing her
source IP address
“I am Alice”
Alice’s
IP address
Failure scenario??
Authentication
▪ Protocol ap2.0: Alice says “I am Alice” in an IP packet containing
her source IP address
Eve can create
a packet “spoofing”
Alice’s address
Authentication: Another try
Protocol ap3.0: Alice says “I am Alice” and sends her secret password to
“prove” it.
Failure scenario??
“I’m Alice”Alice’s
IP addr
Alice’s
password
OKAlice’s
IP addr
Authentication: Another try
Protocol ap3.0: Alice says “I am Alice” and sends her secret password to
“prove” it.
“I’m Alice”Alice’s
IP addr
Alice’s
password
OKAlice’s
IP addr
Alice’s
IP addr
Alice’s
password
I’m
Alice
Playback attack: Eve records
Alice’s packet and later plays it
back to Bob
Authentication: Another try
Protocol ap3.1: Alice says“I am Alice”and sends her encrypted secret
password to“prove”it.
Failure scenario??
“I’m Alice”Alice’s
IP addr
encrypted
password
OKAlice’s
IP addr
Authentication: Another try
Protocol ap3.1: Alice says“I am Alice”and sends her encrypted secret
password to“prove”it.
“I’m Alice”Alice’s
IP addr
Encrypted
password
OKAlice’s
IP addr
Alice’s
IP addr
Encrypted
password
I’m
Alice
Record and playback still works
Authentication: Yet another try
▪ Goal: avoid playback attack
▪ nonce: number (R) used only once-in-a-lifetime
▪ ap4.0: to prove Alice “live”, Bob sends Alice nonce, R. Alice must
return R, encrypted with shared secret key
Failures, drawbacks?
Authentication: ap 5.0
▪ ap4.0 requires shared symmetric
key
▪ can we authenticate using public
key techniques?
▪ ap5.0: use nonce, public key
cryptography
ap 5.0: Security hole
▪ man (or woman) in
the middle attack:
Eve poses as Alice
(to Bob) and as Bob
(to Alice)
ap 5.0: Security hole contd.
▪ man (or woman) in the middle attack: Eve poses as Alice (to Bob) and as Bob (to
Alice)
▪ Difficult to detect:
▪ Bob receives everything that Alice sends, and vice versa. (e.g. so Bob, Alice
can meet one week later and recall conversation!)
▪ Problem is that Eve receives all messages as well!
▪ What made this MiTM attack possible?
Public Key Encryption Algorithms (Recap)
▪ Requirements:
need K ( ) and K ( ) such that1 + -B B
given public key K , it should be impossible to
compute private key K
B
2
+
-
RSA: Rivest, Shamir, Adelson algorithm
Public Key Cryptography
symmetric key crypto
• Requires sender, receiver
know shared secret key
• Q: how to agree on key in
first place (particularly if
never “met”)?
public key crypto
▪ radically different
approach [Diffie-
Hellman76, RSA78]
▪ sender, receiver do not
share secret key
▪ public encryption key
known to all
▪ private decryption key
known only to receiver
RSA: Getting Ready
▪ A message is a bit pattern.
▪ A bit pattern can be uniquely represented by an
integer number.
▪ Thus encrypting a message is equivalent to
encrypting a number.
▪ Example
▪ m= 10010001. This message is uniquely represented
by the decimal number 145.
▪ To encrypt m, we encrypt the corresponding number,
which gives a new number (the ciphertext).
RSA: Creating Public/Private Key Pair
1. Choose two large prime numbers p, q.
(e.g., 1024 bits each)
2. Compute n = pq, z = (p-1)(q-1)
3. Choose e (with ewith z. (e, z are “relatively prime”). E.g.: 4 and 9 are
relatively prime. 6 and 9 are not.
4. Choose d such that ed-1 is exactly divisible by z.
(in other words: ed mod z = 1 ).
5. Public key is (n,e). Private key is (n,d).
K
B
+ K
B
-
RSA: Creating Public/Private Key Pair
0. Given (n,e) and (n,d) as computed above
1. To encrypt bit pattern, m (m < n), compute:
c = m mod ne (i.e., remainder when m is divided by n)
2. To decrypt received bit pattern, c, compute:
m = c mod nd (i.e., remainder when c is divided by n)d
Magic
happens!
m = (m mod n)e mod n
d
c
RSA Simple Example
▪ Bob chooses p=5, q=7. Then n=35, z=24.
e=5 (so e, z relatively prime).
d=29 (so ed-1 exactly divisible by z).
letter m m
e c = m mod ne
l 12 248832 17
encrypt:
c m = c mod nd
17 4819685721067509150-
91411825223071697
12
c
d
letter
l
decrypt:
Note: Assume that letters a-z are numbered 1 to 26 and hence l=12
RSA Another Important Property
▪ The following property will be very useful later:
K (K (m)) = m
BB
- +
K (K (m))
BB
+ -
=
use public key first,
followed by private
key
use private key first,
followed by public
key
Result is the same!
Diffie-Hellman Key Exchange
▪ Alice’s private key = 5, Bob’s private key = 4, g=3, p=7
▪ Alice’s public key = 35 mod 7 = 5, Bob’s public key = 34 mod 7 = 4
▪ Alice’s shared key = 45 mod 7 = 2, Bob’s shared key = 54 mod 7 = 2
Diffie-Hellman Key Exchange - MiTM
▪ Alice’s private key = 5, Bob’s private key = 4, g=3, p=7
▪ Alice’s public key = 35 mod 7 = 5, Bob’s public key = 34 mod 7 = 4
▪ Alice’s shared key = 45 mod 7 = 2, Bob’s shared key = 54 mod 7 = 2
Diffie-Hellman Key Exchange – MiTM (self-learn)
▪ Draw the protocol exchange and show how MiTM works in the previous scenario.
▪ Read about: Station-to-Station (STS) protocol was developed by Diffie, Van
Oorschot, and Wiener in 1992
▪ Learn what counter measure is used to avoid this attack
▪ Fundamental design principles used in many real-world protocols e.g WPA-3
Formal Analysis of Security Protocols
▪ Engineers/developers take a reactive approach
▪ Design protocols for known attack vectors
▪ Fix problems after attacks have actually happened or Zero day
▪ Formal Analysis can aid improving security
▪ Not bullet proof but can discover many security holes
▪ Take remedial action during design/implementation phase
▪ Example: Formal analysis showed vulnerabilities in SSL/TLS
record protocols
Formal Analysis of Security Protocols Contd.
▪ Tools and techniques vary in their strength and sophistication,
some are simpler to use, others have more advanced features with
steep learning curve
▪ Complex tools: Tamarin, Scyther, Proverif ….. List goes on
▪ Simpler tool: AVISPA, lot of examples of Internet protocols
▪ We introduced AVISPA for appreciation, if this interests you, you
can explore others in your own time
▪ Formal analysis is beyond scope of this course (not
examinable)
Acknowledgements
▪ Network Security Essentials: Stallings, Chapter 4 provided by Henric Johnson, Blekinge
Institute of Technology,Sweden ( Please refer to Section 4.3 and 4.4 from Staillings)
▪ Computer Networking A top-Down Approach: Jim Kurose and Keith Ross, chapter 8