a$.$ Digital signatures are sometimes used for authenticating users in network protocols. SSH and SSL$/$TLS$,$

for example, can both use such a mechanism. Consider the following login protocol:

$$ The server sends Alice a randomly chosen number x$.$

$$ Alice digitally signs the number with her secret signing key sk$,$ and sends the signature s $=$ Signsk$($x$)$

back to the server.

$$ The server checks the signature using Alice$$s public verification key vk$.$ If the signature is valid, i$.$e$.,$

V ervk$($x$,$ s$)=$ valid, then the server accepts Alice$$s connection request.

Suppose that Alice uses the same private key, both, to log in to such a server using the above protocol, and

also to sign the emails she sends to various recipients. Show how a server could trick Alice into helping the

server forge Alice$$s signature on an arbitrary email M$$

$,$ making it appear signed by Alice. Technically,

explain how the server can mount a universal forgery attack $($against email signature$)$ using Alice as a

chosen$-$message signing oracle $($in the login scheme$).$ Assume that email signature is normal full$-$fledged

hash$-$and$-$sign: i$.$e$.,$ to sign an email message M$,$ Alice hashes M into h$($M$)$ and outputs Signsk$($h$($M$)).$

How can the server trick Alice into signing an arbitrary email M$?$

b$.$Suggest a modification to the authentication protocol which would defeat this attack. Many solutions are possible for this question, some better than others; give the one you deem best.

c$.$ Learning from the above attack, what would be your word of wisdom regarding the $($re$-)$use of the same cryptographic keys for different purposes or in different protocols? Briefly explain what generally would be best avoided; and then think of an approach one could safely use if we really wanted to minimise the number of keys that Alice would need to store securely$.$