# Homework 9 FCS

# 1

The code is written in the section below.

import os
import sys

import random, hashlib

import numpy
import math

from Crypto.PublicKey import DSA
from Crypto.Signature import DSS
from Crypto.Hash import SHA256


def rabin_miller(n):
	'''
	Check for primality
	'''
	if n == 2 or n == 3:
		return True

	if n % 2 == 0 or n < 2:
		return False

	s = n - 1
	t = 0

	while s % 2 == 0:
		s = s // 2
		t = t + 1

	for count in range (0, 10):
		a = random.randint(2, n-1)
		x = pow(a, s, n) # a^s mod n

		if x != 1:
			i = 0
			while x != (n - 1):
				if i == t - 1 :
					return False
				else:
					i = i + 1
					x = pow(x, 2, n) # x^2 mod n

	return True


def Gen(minPrime):
	while True:
		temp = random.randrange(minPrime, 100*minPrime)
		if rabin_miller(temp):
			q = temp
			
			# check if 2*q + 1 is prime or not
			if rabin_miller(2*q + 1):
				p = 2*q + 1 # p is a safe prime
				break
			else:
				q = None

	
	r = random.randrange(2, p-2) 
	g = pow(r,2,p)

	return g,p,q,r

def pubB(g, p, q):
	b = random.randint(1, q-1)
	B = pow(g,b,p) # private key
	return B, b

def pubA(g, p, q):
	a = random.randint(1, q-1)
	A = pow(g,a,p) # private key
	return A, a

def checkgpq(s, g,p,q):
	if s > p or p != 2*q+1:
		return False
	else:
		return True

def sendsAUTH(B):
	# Create a new DSA key
	key = DSA.generate(1024)
	publicKeyDSA = key.publickey().export_key()
	
	# # Sign a message
	message = bytes(str(B),'utf-8')
	hash_obj = SHA256.new(message)
	signer = DSS.new(key, 'fips-186-3')
	signature = signer.sign(hash_obj)
	return signature, publicKeyDSA


def checkAuth(msg,AUTH,pkeyDSA):
	# # Load the public key
	message = bytes(str(msg),'utf-8')
	hash_obj = SHA256.new(message)
	pub_key = DSA.import_key(pkeyDSA)
	verifier = DSS.new(pub_key, 'fips-186-3')
	
	# # Verify the authenticity of the message
	try:
		verifier.verify(hash_obj, AUTH)
		return True
	except ValueError:
		return False

def craftKey(pkeyDH,secret,p):
	K = pow(pkeyDH,secret,p)
	hashK = SHA256.new(bytes(str(K),'utf-8'))
	hashK = hashK.digest()
	return K, hashK



def main():
	
	s = 15917323323 # Alice chooses min value for p
	print(f'Alice sends s : {s}')

	
	g,p,q,r = Gen(s) # p, q are primes and the rest of the criterias are fulfilled

	print(f'Bob chooses g : {g}, p : {p}, q : {q}, r : {r}')

	B, b = pubB(g,p,q)

	AUTHbob, publicKeyDSAbob = sendsAUTH(B)
	print(f'B: {B}, AUTH Bob : {AUTHbob}')

	if checkgpq(s,g,p,q):
		print(f'Alice sanity check {checkgpq(s,g,p,q)}. if True then there\'s no problem')
	else:
		print('Not good')
		exit()

	if checkAuth(B,AUTHbob,publicKeyDSAbob):
		print('Alice has checked that the message is authentic')
	else:
		print('Message not authentic. Aborting Sequence.')

	A, a = pubA(g,p,q)

	AUTHalice, publicKeyDSAalice = sendsAUTH(A)

	print(f'A: {A}, AUTH Bob : {AUTHalice}')


	print('-----------------------Crafting key-------------------')

	Kalice, hashKalice = craftKey(B,a,p)
	print(f'Alice computes K: {Kalice} hash K: {hashKalice}')


	if checkAuth(A,AUTHalice,publicKeyDSAalice):
		print('Bob has checked that the message is authentic')
	else:
		print('Message not authentic. Aborting Sequence.')
		exit()

	Kbob, hashKbob = craftKey(A,b,p)
	print(f'Bob computes K: {Kbob} hash K: {hashKbob}')
	print('The hashed keys are the same? ',hashKalice == hashKbob)

if __name__ == '__main__':
	main()

# 2

The design of key management should allow for the main server to not be a single point of failure as there are multiple backups in available for redundancy. This would allow Alice to request her and Bob's key from multiple sources and maintain its availablity. It is also known that KDC has the problem of being a single point of failure if it is compromised. With this design, any KDC will no longer be a single point of failure as there are other KDCs to back it up.

## a)

### Limitation

1. Overhead Cost : Cost (financial, complexity) will increase as the implementation is costly.
2. Authentication issue : With the increase in number of avaialble KDC to connect to, an attacker can capture the first request in one of the connection and replay it to a different KDC. This would allow the attacker to obtain the encrypted key and use it to communicate with both Bob and Alice. This is also present in the single point KDC

## b)

Improvement:

- To protect against replay attacks, the Kerberos authentication protocol uses the concept of an authenticator. A Kerberos authenticator is embedded in the Kerberos protocol exchanges that occur between the authenticating client and the authentication server (in Windows, the domain controller—DC). It holds additional authentication data, such as the ticket lifetime, and most important, the client's timestamp. When the Kerberos logic on a DC or resource server validates a Kerberos authentication message, it will always check the authenticator's timestamp. If the timestamp is earlier or the same as a previous authenticator, the server-side Kerberos logic will reject the packet because it considers it part of a replay attack and user authentication will fail.

# 3
The symmetric key based mutual authentication protocol is subject to reflection attack if there are implementation issues:

1. The protocol allows the initiator to start with a nonce (for the responder to encrypt).

2. The protocol allows the nonce to be used more than once (previously used [$N_{X}$,$E_{K}$ ($N_{X}$ )] susceptible to record-and-replay).

Eve (the attacker) in the 1st session initiates the authentication to Bob by saying “I’m Eve”. After it receives the nonce $N_{B}$ from Bob, Eve opens a 2nd session and challenges Bob by sending the same nonce (assuming implementation issue 1). Bob will return the encryption of the nonce $E_{k}$ ($N_{B}$), which Eve will then go back to the 1st session and send $E_{k}$ ($N_{B}$) to Bob (either a result of implementation issue 1 or 2).

Diagram to show the issue:

# 4

The fair non-repudiation protocol below is referenced from D. Gollmann and J. Zhou, "An Efficient Non-repudiation Protocol," in Computer Security Foundations Workshop, IEEE, Rockport, Massachusetts, 1997 pp. 126.

The notations in the protocol description are as follows:
- K – message key defined by A
- C = $Enc_{k} (M)$ – commitment for message M encrypted under a key K
- EOO_C, EOR_C – evidence of origin and receipt of C
- EOO_K, EOR_K – evidence of origin and receipt of C
- con_K – evidence of confirmation of K

To reduce the trusted third party’s (TTP) involvement, the originator A sends an initial commitment C to recipient B. After B replies to the commitment C with the evidence or receipt EOR_C, A will send the key K and evidence of origin EOO_K, for recipient B to decrypt the commitment. B will then send the evidence of receipt EOR_K. Thus, the TTP will not be involved and is off-line.

The protocol is as follows:

1	A → B:	C, EOO_C
2	B → A:	EOR_C
3	A → B: 	K, EOO_K
4	B → A:	EOR_K

In the event that:

a) Originator A sends key K (message 3) but did not receive evidence or receipt EOR_K from recipient B (message 4),
b) Or if recipient B did not receive key K from originator A after sending evidence of receipt EOR_C (message 2),

The entities can recover the protocol if needed after a deadline fixed by the originator with respect to the TTP clock. Either the originator or recipient will contact the TTP. Once the TTP is contacted for resolving the protocol, originator A will send the key K to the TTP, and the TTP will then send the key K to B along with the evidence of confirmation con_K. A will receive con_K from the TTP after that.
The recovery protocol is as follows:

3’.	A → TTP:	K
4’.	B ← TTP:	K, con_K
5’.	A ← TTP:	con_k

Through this protocol, we can see that the involvement of the TTP is minimal and is functionally off-line as it is not involved in each instance of the service.