0
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • $\begingroup$ Just generate generate a hundred random messages, request one signature and check if any other message verifies, request another signature, check for any other message verifies, ... $\endgroup$
    – SEJPM ♦
    May 28 '16 at 18:30
  • $\begingroup$ Yes but how can I exploit this in my favor? Random messages are meaningless. $\endgroup$
    – Jjang
    May 28 '16 at 19:19
  • $\begingroup$ This really depends on your definition of "exploit". If you want to break the standard security notions for signatures, my above explanation suffices, if you want to construct a meaningful / chosen message this looks impossible (to me). $\endgroup$
    – SEJPM ♦
    May 28 '16 at 19:24
  • $\begingroup$ I have to show some "exploit", something useful I could cheat people with. I think breaking the standard is obvious due to the collision with prob. 0.2. $\endgroup$
    – Jjang
    May 28 '16 at 19:53
  • $\begingroup$ This is for educational purpose of course. $\endgroup$
    – Jjang
    May 28 '16 at 19:54
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.