Subject: [Cfrg] existential forgeries and protocol design

From: Robert Moskowitz <[email-masked]>
Date: Mon, 07 Jun 2010 09:19:42 -0400

In

http://www.ietf.org/id/draft-mcgrew-fundamental-ecc-03.txt

Section 10.4

    If no hash function is used in an ElGamal signature system, then the
    system is vulnerable to existential forgeries, in which an attacker
    who does not know a private key can generate valid signatures for the
    associated public key, but cannot generate a signature for a message
    of its own choosing.  (See [E1985] for instance.)  The use of a
    collision-resistant hash function eliminates this vulnerability.

If Bob ALWAYS signs all messages, then it does not matter that Malice 
can also sign the message.  Alice will get the same message.

Thus in this limited use of signatures, functions like CMAC with a 
'public' key can be used to produce the value to sign.  It does not 
matter that someone else can also produce this same signature.  Alice 
would never see a message from Bob that Bob did not sign (even if Malice 
regenerated the same signature).

Existential forgeries are only a problem when Bob sometimes signs a 
message and sometimes does not, and it is significant that Bob HAS 
signed the message. But again, if Bob ALWAYS signs all messages, so what?

---

From: Robert Moskowitz <[email-masked]>
Date: Mon, 07 Jun 2010 16:03:14 -0400

I was asked to clearify my question.

I am trying to understand what an 'existential forgery' is and what is 
the risk.  Because I am designing a protocol that does not have a hash 
primative.  It does have CMAC.

Why no hash primative; such a basic part of our cryptographic tool kit?  
Code space.  Or at least the vendors cry everytime they have to add 
something else.  So what is the minimum needed?  I do want to include 
ECDSA signatures and up crops hashing again...

> can also sign the message.  Alice will get the same message.

In the protocol design, all packets are digitally signed.  There is 
never a case of sometimes a packet is signed and sometimes not.  So if 
there is a existential forgery vulnerablity, so what?

> would never see a message from Bob that Bob did not sign (even if 
> Malice regenerated the same signature).

Instead of using a cryptographic hash like SHA-256, eating up a lot of 
code space, you CMAC with some public key to get the value to sign.  It 
is always there, so what if it can be generated by either Bob or Malice?

> signed the message. But again, if Bob ALWAYS signs all messages, so what?

I think I am beginning to see a bit here.  Malice can impersonate Bob, 
using Bob's public key.  Alice cannot tell that the packet came from Bob 
or Malice.  My defence against this is Alice uses Bob's public key to 
encrypt a secret that Bob has to use.  Only Bob can decrypt this, Malice 
can't.

So existential forgery is a problem if you do not include a separate 
proof of ownership of the private key.

Bob or 
Malice                                                                
Alice or Malice2

  Sign (Bob's PK, stuff)  -------->
<----------- Sign(Alice's PK, (stuff, Encrypt(Bob's PK, secret), 
MAC(secret))
Bob only                                                                 
     Alice Only
  Sign (Bob's PK, (stuff, Encrypt(Alice's PK, secret2), MAC(secret))  
-------->
<-----------     Encrypt (secret|secret2, data)  -------->

In the above exchange either Bob or Malice could generate the ist 
packet, using Bob's key (Bob doing it right with his private key, Malice 
attacking using Bob's public key), Alice can't be sure.

The second packet could be generated by either Alice of Malice2 using 
Alice's and Bob's keys.  Only Bob can process this packet, performing 
the Decrypt operation.  So Alice is assured that the third packet could 
only come from Bob.

The third packet could only be generated by Bob and only Alice can 
process it.  All following packets MUST use the secret from the 2nd and 
3rd packet to ensure each party that the exchange was properly performed.

thank you for making me go through this exercise to clearify my 
question.  I know **THINK** I understand the risk of existential 
forgeries and how to mitigate that risk.

---

From: John Wilkinson <[email-masked]>
Date: Mon, 7 Jun 2010 18:04:38 -0400

On Mon, Jun 7, 2010 at 4:03 PM, Robert Moskowitz
<[email-masked]> wrote:
> Bob or Malice

What, exactly, are you trying to accomplish with this handshake? Key
exchange? If so, then why do you need signatures at all? I'm confused.

An existential forgery is the creation of a valid signature, without
using the signer's private key, on a message not signed by the signer,
and not chosen by the attacker. Hash functions are used in digital
signature schemes to prevent the negative consequences of existential
forgeries. Under (EC)DSA, an attacker can easily generate countless
existential forgeries. The use of a pre-image resistant hash function
makes it computationally infeasible for the attacker to generate a
message that corresponds with the hash value that he forged the
signer's signature on. In essence, "Malice" in your example (I prefer
"Eve"), can forge Bob's signature all day long, but he can never
produce the messages that Bob has supposedly signed, making the
forgeries rather useless.

Unfortunately for you, CMAC is *not* pre-image resistant; it is easy
to work backwards from any random pattern of bits to a message of the
attacker's choosing (up to a few random bits in the last block). If
you tried to use CMAC as the "hash" in your digital signature scheme,
those existential forgeries may suddenly become quite useful to the
attacker.

I can't imagine an implementation of ECDSA not including, at least,
SHA1, but if it doesn't, I suggest that you re-evaluate the use of
signatures in your scheme.

HTH

-John

---

From: Robert Moskowitz <[email-masked]>
Date: Mon, 07 Jun 2010 18:32:19 -0400

> signatures in your scheme.

Deal with sensor vendors that want as little code as possible.  They 
don't want SHA-1.  They don't want HMAC.  They kick and scream about 
ECC.  At least MOST have already done AES-CCM.  Some even want to throw 
out TCP and just use UDP.

I will get back to you on a more detailed response to your comments.

---

From: Len Sassaman <[email-masked]>
Date: Tue, 8 Jun 2010 20:04:29 +0200 (CEST)

On Mon, 7 Jun 2010, Robert Moskowitz wrote:

> Existential forgeries are only a problem when Bob sometimes signs a message 
> and sometimes does not, and it is significant that Bob HAS signed the 
> message. But again, if Bob ALWAYS signs all messages, so what?

Suppose you have a protocol that expects to only see one signature over 
the payload, and following Postel's Law, it doesn't discard this weird 
two-signature blob, but instead displays it with the second signature as 
the only one easily viewable by the user?

I'd be wary of making the claim "[some given attack] is only a problem if 
[X]".

--Len.

---

From: Steven Bellovin <[email-masked]>
Date: Tue, 8 Jun 2010 15:23:34 -0400

On Jun 8, 2010, at 2:04 29PM, Len Sassaman wrote:

>> Existential forgeries are only a problem when Bob sometimes signs a message and sometimes does not, and it is significant that Bob HAS signed the message. But again, if Bob ALWAYS signs all messages, so what?
> 
> Suppose you have a protocol that expects to only see one signature over the payload, and following Postel's Law, it doesn't discard this weird two-signature blob, but instead displays it with the second signature as the only one easily viewable by the user?

Right.  Note that this is the transition strategy to a new hash function for S/MIME....
> 
> I'd be wary of making the claim "[some given attack] is only a problem if [X]".

That depends on the protocol definition; multiple signatures aren't always meaningful.

		--Steve Bellovin, http://www.cs.columbia.edu/~smb

---

From: Len Sassaman <[email-masked]>
Date: Tue, 8 Jun 2010 22:52:21 +0200 (CEST)

> That depends on the protocol definition; multiple signatures aren't 

Sure, though one also has to consider not only the protocol definition but 
how implementations might handle situations where they receive invalid 
protocol input with errors that they can recover from. So a protocol that 
only specifies one hash per blob might be open to attack if it receives 
more than one valid hash on that blob.

(I ran into something similar recently with X.509; for some reason, 
multiple CNs are permitted, though only one is ever used, and the 
implementation specs (RFCs, etc.) are not helpful as far as determining 
which CN to use, so OpenSSL and CryptoAPI and NSS all handle the situation 
differently.)

This sort of thing is why I avoid sweeping generalizations about the lack 
of security problems in [some approach]. While some of them are bound to 
be true, it's a dangerous way of thinking about security.

--Len.