Subject: Re: [Cfrg] existential forgeries and protocol design

From: David Wagner <[email-masked]>
Date: Mon, 7 Jun 2010 16:43:30 -0700 (PDT)

Robert Moskowitz  wrote:
> I am trying to understand what an 'existential forgery' is

http://en.wikipedia.org/wiki/Forgery_%28cryptography%29

It is the accepted notion of security for digital signatures.
I would not recommend using any digital signature scheme that
falls short of this level of security.

You can find more in a good textbook on cryptography.  e.g.,
  http://cseweb.ucsd.edu/users/mihir/cse207/w-ds.pdf 
  http://cseweb.ucsd.edu/users/mihir/cse207/w-mac.pdf 
I'd guess the Katz-Lindell book will say something as well.
There is lots written on the subject.

> Because I am designing a protocol that does not have a hash 
> primative.  It does have CMAC.

I don't know whether one could design an alternative scheme that avoids
the use of a hash function, but it's not trivial (designing something like
PKCS#2 or OAEP is non-trivial as it stands, even with a hash function).
I would definitely recommend against trying to design something on your
own.  This is going to sound flip, but: if you have to ask, you probably
don't know enough to design an alternative that will be reliably secure.

To put another way: if you really need to build a secure signature
scheme without using any hash function, and if it needs to be secure,
I suspect you probably need to hire a knowledgeable cryptographer to do
some serious design work.  (Don't expect this to be cheap.)

---

From: Robert Moskowitz <[email-masked]>
Date: Mon, 07 Jun 2010 20:29:47 -0400

> http://en.wikipedia.org/wiki/Forgery_%28cryptography%29

I did find this, and it was a good help.

> falls short of this level of security.

I will comment on the rest of your message later, but had a thought.

If the message to sign is a 256 bit random number, and is signed with a 
ECDSA-256 key, is this vulnerable to an existential forgery?

I am trying to understand this all better.

---

From: John Wilkinson <[email-masked]>
Date: Mon, 7 Jun 2010 21:58:43 -0400

> ECDSA-256 key, is this vulnerable to an existential forgery?

If you give me a random bit string, I cannot forge your signature on
it. (Or, if I can, your signature scheme is badly broken, and
vulnerable to more than just existential forgeries, but actual
forgeries as well.) But I can forge your signature on an unlimited
number of random-looking bit strings, just not ones of my choosing,
nor of any one specified to me. If Alice expects to receive Bob's
signature on a random-looking string, how is she to know that Bob
signed it instead of me?

If your answer is that Alice provided the random-looking string to
Bob, and demanded his signature, then you have two problems:

1. It's not clear what you're trying to achieve by this.

2. Certain signature schemes may compromise the *private* key if the
signer signs messages of someone else's choosing. (This is another
reason for the incorporation of a pre-image resistant hash function
into the overall signature scheme.)

All in all, I'd second Prof. Wagner's advice, but even more bluntly (I
don't think you'll be offended). You are *not* qualified to be mucking
around, making changes to standardized signature schemes. (I'm not
qualified either, FWIW.) I can't imagine any implementer would even
offer to provide you with ECDSA functionality *without* any hash
function.

Maybe if you tell us what you're trying to accomplish, someone on this
list can suggest a way for you to do it without using hashes or ECDSA.