Simple Authentication Protocols II
CS 3IS3
Ryszard Janicki
Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada
Acknowledgments: Material based on Information Security by Mark Stamp (Chapters 9.4-9.7)
Ryszard Janicki
Simple Authentication Protocols II 1/16
TCP-based Authentication
TCP (Transmission Control Protocol) was not intended for use as an authentication protocol
But IP (Internet Protocol) address in TCP connection may be (mis) used for authentication
T
C
h
A
e
lso
,o
P
3
–
ne m
od
e
of
IP
w
a
y
H
a
Sec
(Re
al
Wo
partially) relies on IP address for authentication
TCP 3-way Handshake:
Initial sequence numbers: SEQ a and SEQ b Supposed to be selected at random
n
d
rld
P
s
a
k
ro
toc
ol
– next,
SYN, SEQ a
SYN, ACK a+1, SEQ b
ACK b+1, data
Alice
Bob
Initial sequence numbers: SEQ a and SEQ b If not, might have problems…
o Supposed to be sele
Ryszard Janicki
cted at random
Simple Authentication Protocols II 2/16
TCP 3-way Handshake
TCP Authentication Attack I
SYN, SEQ a
SYN, ACK a+1, SEQ b
ACK b+1, data
ack
———————————————————————————–
TCP Authentication Att
Alice Bob
Initial sequence numbers: SEQ a and SEQ b o Supposed to be selected at random
If not, might have problems… Part 3 Protocols
55
Trudy
5. 5.
5.
Alice
Bob
5.
Part 3 Protocols
56
Ryszard Janicki
Simple Authentication Protocols II 3/16
TCP Authentication Attack II
Trudy cannot see what Bob sends, but she can send packets to Bob, while posing as Alice
Trudy must prevent Alice from receiving Bob’s response (or else connection will terminate)
If password (or other authentication) required, this attack fails
If TCP connection is relied on for authentication, then attack might succeed
Bad idea to rely on TCP for authentication
Ryszard Janicki
Simple Authentication Protocols II 4/16
Zero Knowledge Proof (ZKP)
Alice wants to prove that she knows a secret without revealing any info about it
Bob must verify that Alice knows secret
But, Bob gains no information about the secret
Process is probabilistic
Bob can verify that Alice knows the secret to an arbitrarily
high probability
An “interactive proof system”
Ryszard Janicki
Simple Authentication Protocols II 5/16
Bob’s Cave I
Bob’s Cave
Alice knows secret Alice kpnhorwassseectroetophernaspeatoh open pbaethtwbetewneRenaRndanSd S, both w(a“oyspe(“nospaenrsSaepsarmilela””)
P
Can she convince knows the secret without
Q RS
Can she convince Bob that she
Bob that she knows
the secret without revealing phrase?
revealing phrase?
Part 3 Protocols
61
Ryszard Janicki
Simple Authentication Protocols II 6/16
Bob’s Cave II
Alice go to the case and stay on either R or L side (50/50 probability)
Bob: “Alice, come out on S side”
Alice (quietly): “Open …”
IfAlice does not know the
secret. . .
. . . then Alice could come out from the correct side with probability 1/2
If Bob repeats this n times and Alice does not know secret,
she can only fool Bob with probability 1 ≈ 0 2n
Ryszard Janicki
Simple Authentication Protocols II 7/16
Fiat-Shamir Protocol I
Cave-based protocols are inconvenient
Can we achieve same effect without the cave?
Finding square roots modulo N is difficult Equivalent to factoring
Suppose N = pq, where p and q are primes Alice has a secret S
Nandv=S2 modNarepublic,Sissecret
Alice must convince Bob that she knows S without revealing any information about S
Ryszard Janicki
Simple Authentication Protocols II 8/16
Fiat-Shamir Protocol II
Fiat-Shamir
Public: Modulus N and v = S2 mod N
Public: Modulus N and v = S2 mod N
Alice selects random r , Bob chooses e ∈ {0, 1}
Alice selects random r, Bob chooses e {0,1}
Bob verifies: y2 = x ·ve mod N Bob verifies: y2 = xve mod N
Alice secret S random r
x = r2 mod N e {0,1}
y = r Se mod N
Bob random e
Note that y2 = r2 · S2e = r2 · (S2)e = x · ve mod N o Note that y2 = r2 S2e = r2 (S2)e = x ve mod N
Part 3 Protocols
64
Ryszard Janicki
Simple Authentication Protocols II 9/16
Fiat-Shamir: e = 1
Fiat-Shamir: e = 1
Public: Modulus N and v = S2 mo2d N Public: Modulus N and v = S mod N
Alice selects random r, Bob chooses e = 1
Alice selects random r, Bob chooses e =1
Alice secret S random r
x = r2 mod N e =1
y = r S mod N
Ify2 =x·v modN thenBobacceptsit
If y2 = xv mod N then Bob accepts it
And Alice passes this iteration of the protocol
o And Alice passes this iteration of the protocol Note that Alice must know S in this case
Note that Alice must know S in this case Part 3 Protocols 65
Bob random e
Ryszard Janicki
Simple Authentication Protocols II 10/16
Fiat-Shamir: e = 0
Fiat-Shamir: e = 0
Alice secret S random r
x = r2 mod N e =0
y = r mod N
Public: Modulus N and v = S2 mo2d N Public: Modulus N and v = S mod N
Alice selects random r, Bob chooses e = 0
Alice selects random r, Bob chooses e = 0
Bob must checks whether y2 = x mod N
Bob must checks whether y2 = x mod N
Alice does not need to know S in this case!
“Alice” does not need to know S in this case!
Part 3 Protocols 66
Bob random e
Ryszard Janicki
Simple Authentication Protocols II 11/16
Fiat-Shamir
Public: modulus N and v = S2 mod N
Secret: Alice knows S
Alice selects random r and commits to r by sending x = r2 mod N to Bob
Bob sends challenge e ∈ {0, 1} to Alice Alicerespondswithy=r·Se modN Bobcheckswhethery2=x·ve modN
If everyone follows protocol, math works:
Public: v = S2 mod N
Alice to Bob: x = r2 mod N and y = r · Se mod N Bobverifies:y2=x·ve modN
Can Trudy convince Bob she is Alice?
If Trudy expects e = 0, she follows the protocol: send x = r2 in message 1 and y = r in message 3 IfTrudyexpectse=1,shesendsx=r2·v−1 inmessage1 and y = r in message 3
If Bob chooses e ∈ {0, 1} at random, Trudy can only trick Bob with probability 1/2
Ryszard Janicki
Simple Authentication Protocols II 12/16
Fiat-Shamir Facts
Trudy can trick Bob with probability 1/2, but. . .
. . . after n iterations, the probability that Trudy can convince
Bob that she is Alice is only 1 2n
Just like Bob’s cave!
Bob’s e ∈ {0, 1} must be unpredictable/random Alice must use new r each iteration, or else. . .
If e = 0, Alice sends r mod N in message 3
If e = 1, Alice sends r · S mod N in message 3 AnyonecanfindS givenr modN andr·S modN
Ryszard Janicki
Simple Authentication Protocols II 13/16
Fiat-Shamir Zero Knowledge
Zero knowledge means that nobody learns anything about the secret S
Public: v = S2 mod N
Trudy sees r2 mod N in message 1
Trudy sees r · SmodN in message 3 (if e = 1)
If Trudy can find r from r2 mod N, she gets S But that requires modular square root calculation
If Trudy could find modular square roots, she could get S from public v
Protocol does not seem to “help” to find S
Ryszard Janicki
Simple Authentication Protocols II 14/16
ZKP in the Real World
Public key certificates identify users
No anonymity if certificates sent in plaintext
ZKP offers a way to authenticate without revealing identities
ZKP supported in MS’s Next Generation Secure Computing Base (NGSCB), where. . .
. . . ZKP used to authenticate software “without revealing machine identifying data”
Ryszard Janicki
Simple Authentication Protocols II 15/16
Best Authentication Protocol?
It depends on. . .
The sensitivity of the application/data
The delay that is tolerable
The cost (computation) that is tolerable
What crypto is supported (public key, symmetric key, . . . ) Whether mutual authentication is required
Whether PFS, anonymity, etc., are concern
. . . and possibly other factors
Ryszard Janicki
Simple Authentication Protocols II 16/16