Subject: [Cfrg] Hash verifier's certificate and use of implicit certificates (was RE: Why hash verifier's key?)

From: William Whyte <[email-masked]>
Date: Tue, 4 Aug 2015 13:20:36 -0400

Hi List,

Related to hashing the verifier's key:

In IEEE 1609.2 for connected vehicle security we use ECDSA (for standards
compliance reasons) but follow the lead of KCDSA and hash both the message
and the signing cert. This provides protection against misbinding attacks
where an attacker gets a certificate with the same public key as a victim
and is able to substitute their certificate on messages signed by the
victim. There are other ways of protecting against it (proof of possession
on cert requests, for example, or having the CA manipulate the public key
in the cert request as is done when generating implicit certs or in the
V2X butterfly key construction) but hashing the certificate is cheap and
ensures protection if the CA failed to provide protection by other means.

It's too late for 1609.2 to use the chosen CFRG signature algorithm, but
it might be worth considering whether CFRG should support this
countermeasure against misbinding: for example, by including metadata
related to the public key in the hash input, but allowing that metadata to
be the certificate rather than simply the public key.

A related requirement from 1609.2 that might be useful for CFRG to
consider arises from 1609.2's use of Qu-Vanstone implicit certificates.
Implicit certs contain a public key reconstruction value rather than a
public key and a signature, and are combined with the CA's public key to
obtain the certificate holder's public key. The advantages are: (a) you
save the 64 bytes of certificate signature, which is important in V2X; (b)
verification of a certificate + message signature can be done with a
single triple-multiply-and-add rather than with two
double-multiply-and-adds, cutting almost 50% off the time for an ECDSA
verify. (see [1] below for potential drawbacks/caveats, see [2] for an
outline of QV cert generation).

Two thoughts for consideration:

(1) Does EdDSA or any of the proposals support the use of implicit
certificates? (https://eprint.iacr.org/2009/620.pdf shows some sensitivity
in how particular flavors of implicit certs are combined with particular
signature algorithms, I don't know if there are problems with EdDSA.)
Should CFRG consider support for implicit certs to be a consideration? The
size and performance gains of implicit over explicit certificates were
compelling to us in V2X and it might be useful to see if the CFRG
signature scheme supports them.

Suggestion: Proposers of signature algorithms should be encouraged to
address whether they support QV or some similar implicit certificate
scheme.

(2) If implicit certificates are possible, the performance gain would be
lost if the public key had to be calculated before verification in order
to be input to the hash. However, the performance gain could be preserved
by allowing the input "public key information" to be the implicit
certificate itself rather than the public key. This seems like another
reason to consider allowing public key metadata rather than the public key
itself.

Suggestion: The CFRG signature algorithm should take "public key
information" as an explicit parameter and this should be allowed to be the
certificate or the public key, depending on context.

Finally, just wanted to note that in 1609.2 we actually use

  Hash ( Hash (M) || Hash (Cert) )

as the input to ECDSA signing/verification. This obviously has problems
with collision-resilience, but is efficient when the same cert is used to
sign multiple messages. It's not too late to change this and I'd love to
get feedback on this construction.

Cheers,

William

[1] Caveats: (a) if you verify multiple signed messages from the same
sender you lose this performance bonus; (b) if a message fails to verify
you don't know whether it's because the message or the certificate was
forged;  (c) QV certificates are patented, but that patent will eventually
expire; (d) I haven't looked into EdDSA enough to know if implicit certs
can be used securely with it, the construction is different enough from
ECDSA that it might not be secure; (e) possibly EdDSA's batching approach
allows for a similar speedup, but my understanding is that it doesn't.

[2] QV cert generation goes like this:

* The CA has a static keypair (c, C)
* Alice generates (a, A); sends (A, cert contents) to CA
* CA:
  * Generates (b, B)
  * Sets R = A+B; sets h = Hash (R, cert contents, CA cert)
  * Returns (R, s = c + hb) to Alice
* Alice's private key is c + h(a+b), and her public key is C + h*R. Alice
can calculate her private key as h*a + s and anyone who knows (R, cert
contents, CA cert) can calculate her public key.

There are alternative approaches, but they follow the same pattern.

-----Original Message-----
From: Cfrg [mailto:[email-masked]] On Behalf Of D. J. Bernstein
Sent: Saturday, August 01, 2015 7:03 PM
To: [email-masked]
Subject: Re: [Cfrg] Why hash verifier's key?

Context: EdDSA computes H(R,A,M) where A is the public key, instead of
Schnorr's H(R,M). The original Ed25519 paper says that this is "an
inexpensive way to alleviate concerns that several public keys could be
attacked simultaneously".

Dan Brown writes:
> Could one the EdDSA proposers more formally expand on what these
> "concerns" might be?

Is it clear that an attack against N keys can't succeed---i.e., find at
least one of the keys---with probability N times higher than an attack
against 1 key?

There are real attacks of this type. For example, if N users encrypt the
same counter with N AES-128 keys (a perfectly normal situation with many
modes---we don't want to blame the mode developers for doing something
simple and deterministic), then a well-known attack finds one of the
keys in time just 2^128/N with high probability. This turns into a
serious threat as N grows. This is why I recommend 256-bit secret keys;
it's also why EdDSA systematically avoids guessable 128-bit secrets.

For discrete logs the situation is better. There's a very strong "random
self-reduction" (the strongest type of "worst-case-to-average-case
reduction", stronger than in lattice-based crypto) guaranteeing that an
attack against N discrete logs can't have higher success probability
than an attack against 1 discrete log.

However, forging a signature could be easier than computing a discrete
log, and forging signatures against one of N keys could be N times more
likely than that. There's extensive security analysis regarding the
first concern, but where's the security analysis regarding the second
concern?

Inserting the public key A into the hash alleviates this concern---this
doesn't mean that it necessarily resolves the concern completely, but
it's similar to defenses that have been shown to work in other contexts.
The way that this type of insertion would show up in a hypothetical
generic-hash proof would be to force an attacker computing hashes to
commit to one key being attacked by each hash computation. Without the
public key, there's only a commitment to R, and it's not at all clear
that R is tied tightly enough to the public key to avoid the same loss
factor of N.

> Does inclusion of the verifier's public key in the hash precludes
> derivation of the verifier's public key from the signature?

It has this anonymity effect, yes, as pointed out by Ransom. However,
there are other ways to achieve the same effect with only slightly
higher cost; see Section 2.5 of the Elligator paper. This isn't the big
reason to insert the public key into the hash.

> On the other hand, being able to recover the public key from a
> signature might have some other advantages.  For example, one could
> compress certificate chain by omitting the issuer's public keys.

The current situation is that there are very large gaps between

   (1) the actual amount of data needed to send safe certificate chains,
   (2) the bandwidth used by TLS to send certificate chains, and
   (3) the total bandwidth used by TLS.

The huge gap between #2 and #3 is the obvious explanation for why the
gap between #1 and #2 has been allowed to persist.

My experience is that protocols that send much less data, and that pay
more attention to the overhead of signatures, start by removing the
massive redundancy of constantly sending the same public keys with the
same certificates---so their "chains" are just single signatures, and
then the type of tweak you're talking about doesn't save space.
Pintsov--Vanstone message recovery _does_ still save space, but
unfortunately is still patented (7249259) until September 2019.

---Dan

_______________________________________________
Cfrg mailing list
[email-masked]
http://www.irtf.org/mailman/listinfo/cfrg

---

From: "D. J. Bernstein" <[email-masked]>
Date: 7 Aug 2015 12:49:38 -0000

William Whyte writes:
> In IEEE 1609.2 for connected vehicle security we use ECDSA (for
> standards compliance reasons) but follow the lead of KCDSA and hash
> both the message and the signing cert.

You mean that the application is signing a pair (message,cert)? What
does this have to do with the choice of signature algorithm?

You seem to be suggesting that the signature algorithm per se is
supposed to have an extra side input, namely the certificate. Are
cryptographic libraries supposed to change their signature APIs to allow
a separate "cert" input? What's the format of this input? What happens
when a public key has multiple certificates? How should libraries handle
all of the signature standards that don't support this input?

More to the point, how is this supposed to be better than having the
application sign (message,cert), using the traditional concept of a
signature system? This concept has been stable for decades; it's shared
by theoretical papers, signature specifications, attack papers, and
software. From this perspective, having a cert side input to a signature
algorithm per se---rather than having it be part of how the higher-level
application decides to use signatures---is a severe layering violation.

It's of course important to prevent attackers from shuffling messages
around. That's why it's standard practice to incorporate all relevant
data _into the messages being signed_. This doesn't need, and doesn't
benefit from, any changes to the traditional concept of a signature
system. I've seen cases where there's real justification for rethinking
the layers in cryptography, but in this case the whole justification
sounds like "this application always needs to verify X,Y,Z so signature
systems should have X,Y,Z as separate inputs", and that's obviously a
bad argument.

  [ compared to ECQV ]
> possibly EdDSA's batching approach allows for a similar speedup, but
> my understanding is that it doesn't.

Verifying an EdDSA signature at security level 2^128 takes about 2.8*128
additions. Verifying a batch of 64 EdDSA signatures (with no requirement
of matching keys) takes 0.9*128 additions per signature, three times
better than verifying each signature separately. The 0.9 grows to just
1.2 for batch size 8, and occasional forgeries don't produce drastic
slowdowns. See

   http://cr.yp.to/badbatch/badbatch-20120919.pdf
   http://cr.yp.to/badbatch.html

for optimized verification algorithms and public-domain Python scripts
showing exactly how various verification algorithms work.

For batch size 2---e.g., verifying a signature on a message and also
verifying a certificate on the public key---there's still some benefit:
the algorithms take 2.1*2*128 additions (try "python straus6.py 2"), and
the code to distinguish forged messages from forged public keys can be
skipped.

It's hard to find people stating the actual number of additions (or any
other concrete performance results) for verification of (patented) ECQV
implicit certificates. There are many papers saying things like "X is
much faster than Y" where the reality is that X isn't so amazing---the
authors simply did a poor implementation of Y. My impression is that a
competent implementation of ECQV should have

   * similar speed to verifying size-2 EdDSA batches but
   * much worse speed than verifying larger EdDSA batches.

Batch variants of ECQV won't be any better than simply using batch
verification with EdDSA and skipping ECQV.

> you save the 64 bytes of certificate signature, which is important in
> V2X

You're talking about reducing the size of a certified public key from 96
bytes (32-byte public key, plus a 64-byte signature on the key) to 32
bytes. I understand that this is a noticeable savings in your context of
broadcasting rather short signed messages. However, the standard idea of
caching produces even larger savings:

   * Include a public key and certificate in 6.25% of the broadcasts.

   * In the other 93.75%, include only 4 bytes of the public key,
     relying on the receiver to have the full key cached. Having to try
     multiple keys will be quite rare, with negligible effect on the
     maximum sustainable load. (I'm assuming legitimate traffic; my
     understanding is that your system is trivially vulnerable to denial
     of service in any case.)

This costs just 9.75 bytes on average, much smaller than your 32 bytes.
Is this further savings not important? This also eliminates

   * the implicit requirement to have Alice and Bob ask your master
     certificate authority for help whenever they want to generate keys;

   * the difficulties of allowing changes of certificate authorities;
     and, obviously,

   * the need to pay Certicom for licensing ECQV.

If bandwidth isn't actually the top priority in V2X---for example, if it
has to be balanced against computational costs such as maintaining a key
cache---then properly evaluating the best V2X solution will require a
considerably more detailed explanation of the V2X cost metrics. I've
actually spent quite some time over the past few years reading V2X
stuff, and I've found the statements of crypto desiderata to be unclear,
unjustified, and unstable, but maybe everything is different now.

---Dan

---

From: William Whyte <[email-masked]>
Date: Tue, 11 Aug 2015 06:03:55 -0400

Hi Dan,

[certificate as input]

I was picking up on the EdDSA design where there already is an extra side
input, namely the public key. All I'm saying is that if the signature
design is going to have a side input I would like it to be possible for
that to be the certificate rather than the public key. It seems like the
questions you raise also apply to the question of including the public key
as a side input, unless I'm misreading the EdDSA proposal.

To recap, the reasons for allowing a side input of a certificate rather
than the raw public key are:

* It provides low-cost mitigation of cert misbinding attacks.
* It allows for efficient verification in the case where the public key
isn't immediately available, i.e. the implicit cert case.

>> What happens when a public key has multiple certificates?

This means that the sender is committing to which certificate they're using
to sign the message. That seems like a good thing. Do you think that if a
public key has multiple certificates it should be unclear which one the
sender intended to be used to verify?

[speed of verification]

In the ECDSA case, verification with a public key A involves calculating dG
+ eA, which takes about 1.5*128 adds and 2*128 doubles using the usual
trick.

If you use ECQV to derive the public from a reconstruction value R and the
CA public key U, you're calculating

  dG + e(U + h*R) = dG + eU + (e*h)R

where h is the hash of the certificate material. Using an extension of the
usual trick this takes about 1.75*128 adds and 2*128 doubles.

I'll admit I'm not familiar with the techniques you use to speed up EdDSA
verification to taking 2.8*128 adds. It could be that this speedup isn't
applicable to EdDSA or to Edwards curves. But this is the underlying idea
of fast (cert + message) verification with implicit certs. Do you see this
working with EdDSA?

[key size savings]

Yes, we do this. The current recommendation is to attach certs about once
every 5 messages and have an eight-byte digest otherwise. I don't see any
reason not to combine the two approaches, though.

[claimed drawbacks of implicit certs]

I think this is a mischaracterization. Alice and Bob need to ask the CA for
help when they generate certificates, not keys.

>>    * the difficulties of allowing changes of certificate authorities;

I don't think this is a bigger problem for implicit certs than explicit
certs. In either case, you need to manage migration carefully, make sure
end-entity certs have validity periods within the CA's validity period, and
consider what happens if the CA is revoked. I don't see implicit certs
making things more difficult here.

>>    * the need to pay Certicom for licensing ECQV.

The ECQV patents will expire eventually, and the technology has nice
advantages. I'm not saying that implementers of the CFRG signature scheme
should be required to implement implicit certs on day 1. I'm saying that if
the CFRG signature scheme supports implicit certs, that's a decision we'll
be happy with in the future.

Not directly relevant to this discussion, but for completeness: Certicom
have made an FRAND statement about the use of their patents in the context
of IEEE 1609.2 which means that they can be used for free in that context
under an implicit mutual disarmament agreement:
http://standards.ieee.org/about/sasb/patcom/loa-1609_2-certicom-22dec2010.pdf
.

[V2X requirements]

Maybe!

There isn't a single worldwide statement of requirements. In the US the
focus has been on making a single (cert + signature) verification as fast
as possible while still using ECDSA and standardized curves. You can argue
about whether standardized curves and ECDSA are the right choices, but
that's basically where the industry's comfort zone has ended up being. In
Europe the focus has been even more on reusing existing technology,
verifying large numbers of signatures, and avoiding IP, so the European
standards don't support implicit certs.

There isn't a single best V2X solution, but the use case the US has been
focused on is a cheap device (because mandated) that needs to verify a
single message + cert (for collision avoidance purposes) infrequently
(because collisions happen infrequently). This device is, as you say, going
to be vulnerable to DoS attacks, but it's not clear we can do anything
about that given the environment. You're right that maintaining a key cache
is the natural way to use implicit certs to verify multiple messages, but
that's for devices above the very bottom end so that additional cost is
discretionary.

Cheers,

William

On Fri, Aug 7, 2015 at 8:49 AM, D. J. Bernstein <[email-masked]> wrote:

> [email-masked]
> https://mail.ietf.org/mailman/listinfo/cfrg
>

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 11 Aug 2015 11:43:41 +0100

Hi William,

> [certificate as input]

FWIW, I'm unconvinced that the added complexity of certificate
handling of any sort at this level is at all worthwhile. For
example, if the input is supposed to be a certificate, is the
signing engine supposed to verify that it's a "good" cert? That
would add huge mostly-useless complexity. If nothing is verified,
then why not suggest just being able to bind an additional octet
string? And in that latter case, why isn't that just a part of
the to-be-signed data? I don't think there's a useful thing to
do here in general.

If implicit certs do need a different API then by all means
someone can define one, but I don't think that niche should be
used to determine the generic API.

Lastly, including any such additional complexity will mean that
CFRG miss the boat for some IETF working groups that have been
waiting quite a while already for the new curves work to complete.
Adding new wrinkles at this stage in the game would be
counterproductive IMO, esp. when we're so close to being done.

Bottom line: I think all of this would be better done at a higher
s/w layer, if at all. And this is also stuff to do later, if at
all, and not on this particular critical path.

Cheers,
S.

---

From: William Whyte <[email-masked]>
Date: Tue, 11 Aug 2015 06:59:09 -0400

Hi Stephen --

I accept all that, but doesn't the same thing apply to taking the public key
as an additional input? I'm saying that either the signature algorithm
should have a "public key info" input that accepts more than simply the
public key, or it should all be handled at the application layer. I'm happy
with either of those but don't like requiring that the public key and only
the public key is input through a special additional API field.

This is slightly orthogonal to the question of whether or not to use
implicit certs, BTW. The primary value of hashing the cert is to avoid
misbinding attacks. It also happens to be the case that for implicit certs,
hashing the public key only causes a performance hit. So again the point is
not to require an API for hashing the cert, but to say that we should either
have a general public key info input or handle hashing the public key at the
application layer.

Cheers,

William

-----Original Message-----
From: Stephen Farrell [mailto:[email-masked]]
Sent: Tuesday, August 11, 2015 6:44 AM
To: William Whyte; CFRG
Subject: Re: [Cfrg] Hash verifier's certificate and use of implicit
certificates (was RE: Why hash verifier's key?)

Hi William,

Cheers,
S.

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 11 Aug 2015 12:42:17 +0100

On 11/08/15 11:59, William Whyte wrote:
> as an additional input? 

No. Not unless there's a signature scheme where the public key
is not readily available to the signing code.

And the public key is inherently bound to the signature in all
the obvious use-cases so if CFRG want to include the public key
in the signing process I have no problem with that. I'd also
have no problem if the conclusion was that not binding the public
key was ok.

For a certificate, there's all the additional issues of "chaining
to what trust anchor" which may not in fact be known at signing
time, and which would be needed for a signing engine to check if
the certificate is good or not for any sensible definition of good.
(And that's not to mention the fun of dealing with X.50 and PGP
and even new interesting certificate formats being suggested by
various folks:-)

So no. Doing anything with certificates here would be a bad plan.

Defining a higher level API later that allows binding certificates
of some kind to this signature scheme could be done and would maybe
be useful if there were demand for it. I don't really see that as
being a CFRG thing though myself.

> I'm saying that either the signature algorithm

I would be fine with just the public key as that is always available
for these signature schemes.

> have a general public key info input or handle hashing the public key at the

And my answer is still "no thanks" - adding any certificate handing in
here now would be a fatal error. It'd still be wrong later I think but
trying to do so now would be fatal.

If CFRG start down that road and fail to define a scheme without any
certificate handling first, (and *very* soon!) my confident prediction
is that the signature scheme resulting will be overtaken by events
before it is finished. I currently have about 5 internet-drafts that
are looking to use Ed25519 and where I'm asking folks to hold off until
this work is done. I reckon that's what'll end up being used if this
process takes more than a handful of weeks longer. Your proposal falls
squarely into the kind of late change that would guarantee that kind
of failure. (As well as being wrong from a s/w engineering POV I think.)

So no thanks is still my response.

S.

---

From: William Whyte <[email-masked]>
Date: Tue, 11 Aug 2015 10:08:19 -0400

Hi Stephen,

I think you're saying "No thanks" to a different thing than I'm proposing.
I'm not saying we should require cert handling. I'm saying:

* If CFRG wants to include the public key, that's okay
* But if in the application setting it's also appropriate to hash in the
certificate, having a separate hash of the public key is unnecessary
* And if the application happens to be using implicit certificates, having a
separate hash of the public key is unnecessary *and* has a processing
impact.

One way to address these concerns would be to make the following change to
draft-josefsson-eddsa-ed25519-03, which allows existing implementations to
continue without modification (changes indicated by ***):

4.3.  Sign

   The signature of a message M under a secret key k is the 2b-bit
   string ENC(R) || ENC'(S), where ENC'(S) is defined as the b-bit
   little-endian encoding of S.  R and S are derived as follows.  First
   define r = H(h_b, ... h_(2b-1)), M) interpreting 2b-bit strings in
   little-endian form as integers in {0, 1, ..., 2^(2b)-1}.  Let R=rB
   and S=(r+H(ENC(R) || *** ENC(PK) *** || M)a) mod q, *** where ENC(PK)
   MUST be an unambiguous identifier for the public key. ENC(PK) SHOULD
   be ENC(A), the encoding of the public key, and is ENC(A) unless otherwise
   specified, but MAY be an application-specified identifier for the public
   key such as a public key certificate. ***

4.4.  Verify

   To verify a signature ENC(R) || ENC'(S) on a message M under a public
   key ENC(A), proceed as follows.  Parse the inputs so that A and R is
   an element of E, and S is a member of the set {0, 1, ..., l-1 }.
   Compute H' = H(ENC(R) || *** ENC(PK) *** || M) ***, where ENC(PK) is
   as defined for the sign operation, ***and check the group equation
   8SB = 8R + 8H'A in E.  Verification is rejected if parsing fails or
   the group equation does not hold.

Another way to address the concerns would be to say

4.3.  Sign

   ...  Let R=rB and S=(r+H(ENC(R) || M)a) mod q. *** It is strongly
recommended
   that the encoding of the message M includes the encoding of public key A.
***

Either of these work for me and are minimal impact. If CFRG decides that
there's no need to explicitly include the public key, that meets my
desiderata too.

>> I currently have about 5 internet-drafts that
are looking to use Ed25519 and where I'm asking folks to hold off until
this work is done. I reckon that's what'll end up being used if this
process takes more than a handful of weeks longer.

It'd probably be good if we had a sense from Alexey and Kenny of how much is
left to be done in this requirements-gathering process and how much
flexibility we have to set requirements. I see implicit cert support as a
nice-to-have that would sway my vote, all other things being equal, and I
see supporting the cert as the public key identifier as a
no-reason-not-to-have.

>> Your proposal falls
of failure.

I disagree, see above: my proposal can easily be accommodated without
breaking existing implementations or requiring any specification of cert
handling whatsoever in the base algorithm definition.

>> (As well as being wrong from a s/w engineering POV I think.)

I disagree, but then I would :-)

Cheers,
William

-----Original Message-----
From: Stephen Farrell [mailto:[email-masked]]
Sent: Tuesday, August 11, 2015 7:42 AM
To: William Whyte; CFRG
Subject: Re: [Cfrg] Hash verifier's certificate and use of implicit

S.

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 11 Aug 2015 15:15:08 +0100

On 11/08/15 15:08, William Whyte wrote:
> NC(PK) SHOULD

I still have the same issue with that. Either the signer checks
something or it does not. If it does not, the change is pointless
and all can and should be done via a higher level API. If the signer
does check something then we're back to the fatal error as well
as the s/w engineering complexity downsides involved in any
certificate checking of any sort. And that's not to mention the
issue that the signer cannot always know the inputs the verifier
will use to check a certificate, e.g. years later.

Sorry to be negative... but I'm completely negative wrt this change;-)

S.

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 11 Aug 2015 18:05:32 +0300

> separate hash of the public key is unnecessary *and* has a processing
 
Well, without hashing the public key, it is possible to perform tricks
like recover the public key. But I suspect very few applications want
to perform tricks like that, and those that do use specialized schemes.

And with regards to processing impact, one can store the public key
with private key (IIRC, some private key formats do that) or cache the
public key.

If certificate is needed (and it actually makes sense for the protocol,
as there are many protocols where certificates make no sense), it can
easily be included in application layer.

The same isn't true for e.g. hash firewalling input (for schemes that
allow signature-level online operation (and that was required)), or
personalization  input (reliably preventing cross-protocol attacks
"in-band" is virtually impossible task (there are all manner of
badly designed protocols)).

>    key such as a public key certificate. ***

That leaks the private key if one manages to get signature for the same
message on same key with two different certificates.

Stuff like that is why my proposal preprocesses the message in order to
include multiple inputs (hash firewalling and personalization).

> see supporting the cert as the public key identifier as a

See above for example of problems you hit with it.

-Ilari

---

From: "Santosh Chokhani" <[email-masked]>
Date: Tue, 11 Aug 2015 11:06:19 -0400

Stephen,

Binding a certificate instead of a public key seems to be a good idea.

It does not necessarily bring in the complexity related to trust anchors,
certification path, path validation, etc. for pure signature validation
function.  That work can be left up to the applications that establish trust
in the public key.  Those applications can match the bound certificate hash
to what they build.

Aside from your desire to not make changes at the last minute, am I missing
something?

-----Original Message-----
From: Cfrg [mailto:[email-masked]] On Behalf Of Stephen Farrell
Sent: Tuesday, August 11, 2015 10:15 AM
To: William Whyte <[email-masked]>; CFRG <[email-masked]>
Subject: Re: [Cfrg] Hash verifier's certificate and use of implicit

>    key such as a public key certificate. ***

I still have the same issue with that. Either the signer checks something or
it does not. If it does not, the change is pointless and all can and should
be done via a higher level API. If the signer does check something then
we're back to the fatal error as well as the s/w engineering complexity
downsides involved in any certificate checking of any sort. And that's not
to mention the issue that the signer cannot always know the inputs the
verifier will use to check a certificate, e.g. years later.

S.

---

From: William Whyte <[email-masked]>
Date: Tue, 11 Aug 2015 11:16:35 -0400

Hi Ilari,

I don't think that's right. You're saying that S(R, cert1, M) and S(R,
cert2, M) leak the key if R is the only unknown? But isn't that the same for
S(R, PK, M1), S(R, PK, M2)?

Cheers,

William

-----Original Message-----
From: Ilari Liusvaara [mailto:[email-masked]]
Sent: Tuesday, August 11, 2015 11:06 AM
To: William Whyte
Cc: Stephen Farrell; CFRG
Subject: Re: [Cfrg] Hash verifier's certificate and use of implicit

-Ilari

---

From: Viktor Dukhovni <[email-masked]>
Date: Tue, 11 Aug 2015 15:32:56 +0000

> So no. Doing anything with certificates here would be a bad plan.

And might not interoperate with RFC7250 (raw public keys in TLS).

And just the leaf certificate is not especially more useful than
just its public key, while certificate chains are just a hint to
the verifier that might construct a different chain, or not use an
X.509 chain at all.  

So definitely no certificate binding.  I'm neutral on public key
binding (for lack of cycles and expertise to figure out whether
that's good, bad or simply a waste of cycles).

-- 
	Viktor.

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 11 Aug 2015 18:37:50 +0300

On Tue, Aug 11, 2015 at 11:16:35AM -0400, William Whyte wrote:
> cert2, M) leak the key if R is the only unknown?

Yes:

a = (s1 - s2) / (h1 - h2) mod l.

(where s's are the signature parts and h's are the hash values)

And thanks to how the proposed changed scheme works, the R values are
equal.

> But isn't that the same for S(R, PK, M1), S(R, PK, M2)?

Except the r's are extremely unlikely to be the same, and have no
predictable relation.

-Ilari

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 11 Aug 2015 16:39:01 +0100

> Aside from your desire to not make changes at the last minute, am I missing

You appear to me to be ignoring a basic question - will the
signer check that input or not?

If not, why bother? (At this layer)

If so, what checks? Full RFC5280 checks? No? Then what? (Come
back in a year and tell me when you've agreed 'em all;-(
But then what about PGP? Or DANE? or William's fav. V2x cert
format? Same rules for all of those? No? Then what? (Come
back in N years and tell me when you've agreed 'em all:-(

And how is the verifier to know what inputs were signed how?
Ah so we need to include an encoding of that in the signature
bits eh? (Or we break interop.) Hmm. More years.

And how is the verifier to get all the same inputs? Well,
it cannot in general. So this scheme is only usable with
protocols that allow us to satisfy all of the above eh? End
result is after N years we get nothing good.

Adding any certificate handling of any kind to this CFRG work
on new curves is a terrible, awful, incredibly self-defeating
idea. (So now I'm off the fence properly:-)

S.

---

From: William Whyte <[email-masked]>
Date: Tue, 11 Aug 2015 11:39:32 -0400

equal.

Right, understood. Thanks.

William

-----Original Message-----
From: Ilari Liusvaara [mailto:[email-masked]]
Sent: Tuesday, August 11, 2015 11:38 AM
To: William Whyte
Cc: Stephen Farrell; CFRG
Subject: Re: [Cfrg] Hash verifier's certificate and use of implicit

Yes:

-Ilari

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 11 Aug 2015 20:42:06 +0300

> that's good, bad or simply a waste of cycles).

I think it is a good idea:

Some (badly done) protocols (just saw message pointing out such
attack on one such protocol, thankfully it was only in draft
stage) can be attacked via generating a key that verifies some
chosen message under given signature.

Hashing the public key blocks such attacks.

-Ilari

---

From: Viktor Dukhovni <[email-masked]>
Date: Tue, 11 Aug 2015 18:06:57 +0000

> Hashing the public key blocks such attacks.

Signature verifiers should already know the public key of the party
whose signature they are verifying.  In what context would one be
verifying a signature without knowing which public key to use?

If another key can produce the same signature, why is that a problem?

With RFC7250 raw public keys, the verifier is either statically
configured with the expected peer key, or uses something like
a DNSSEC signed:

    _<port>._<proto>.example.com. IN TLSA 3 1 1 <key digest>
    <corresponding RRSIG RR>

to check that public key presented in the handshake server "certificate
message" is authentic.  That key then signs the server key exchange
parameters, why does the key need to be part of the signed data?

-- 
	Viktor.

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 11 Aug 2015 21:25:15 +0300

> verifying a signature without knowing which public key to use?

The key to verify with might be attacker's key (and sometimes useful
attacks can be mounted via that).

-Ilari

---

From: Viktor Dukhovni <[email-masked]>
Date: Wed, 12 Aug 2015 15:56:48 +0000

> attacks can be mounted via that).

Sorry, I don't understand.  The assumption is that I am trusting
an attacker to sign something?  And then I'm surprised I'm vulnerable?

When might one plausibly be using an attacker's key to verify a
signature?  If you are about to do that, don't you lose even before
you start?  If the attacker can persuade you to trust a chosen key,
why not also an attacker chosen signature?

Are there in fact (rather unusual) protocols where the signature
authenticates the key, and not the converse?  If so, perhaps the
designs are simply broken, and trying to make their assumptions
valid is not a good idea...

-- 
	Viktor.

---

From: Taylor R Campbell <[email-masked]>
Date: Fri, 14 Aug 2015 03:49:35 +0000

Date: Wed, 12 Aug 2015 15:56:48 +0000
   From: Viktor Dukhovni <[email-masked]>

For anyone not paying attention to [email-masked]: It was almost the
case that this happened in a deployed IETF protocol, for Let's
Encrypt:

https://mailarchive.ietf.org/arch/msg/acme/F71iz6qq1o_QPVhJCV4dqWf-4Yc

Ilari commented briefly on the resilience of several CFRG signature
proposals to this problem:

https://mailarchive.ietf.org/arch/msg/acme/qr6pRAA17F2V2vKthaCPl-0i-SQ

Ilari: Perhaps for the sake of this list it would be worthwhile to
expand on that comment?

---

From: Watson Ladd <[email-masked]>
Date: Thu, 13 Aug 2015 20:58:40 -0700

> https://mailarchive.ietf.org/arch/msg/acme/F71iz6qq1o_QPVhJCV4dqWf-4Yc

And? Plenty of protocols the IETF has require nonstandard assumptions.
That's a problem with the protocol: ECDSA and RSA both don't meet this
useless definition. (Why useless? Because a protocol in which the
message has to indicate which key was used can always be fixed by
sending the key that was used along with it.)

In this case the protocol could just have involved publishing a hash
of the CSR somewhere. No need to get fancy.

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.