Let's assume a digital signature scheme such that there's a probability of 0.2 for two random messages to have the same signature.
How can I exploit this sheme?
I'm having difficulties in finding an exploit since the messages has to be random.
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.Sign up to join this community
Formally, a signature scheme is broken, as soon as you can generate a message-signature-pair that you were not given before.
Thus, generating a large bunch of pairs of (random) messages $(m_1,m_2)$, and requesting a signature for one $(m_1)$ of them and verifying if the signature also verifies the other message is a strategy that will yield you a new message-signature-pair $(m_2,s_1)$ rather sooner than later.
Now if you want to make an impressive demonstration of what the above means, you could just generate a large bunch of end-entity X.509 certificates (only differing by the serial number?) and a large bunch of X.509 intermediate CA certificates. The signer will be the CA which only issues end-entitiy certificate by signing the hash of the certificate. Thus your messages become the hashes of the certificates (which are computationally indistinguishable from random strings) and rather sooner than later you'll get a signature for an EE certificate that also verifies for one of the intermediate CA certificates and thus you have successfully forged a (valid) intermediate CA certificate and can run havok with this one.