Subject: Re: [Cfrg] Elliptic Curves - signature scheme: friendliness to low memory implementations (ends on June 3rd)

From: Andrey Jivsov <[email-masked]>
Date: Mon, 01 Jun 2015 22:37:22 -0700

On 5/29/2015 12:49 PM, Simon Josefsson wrote:
> Andrey Jivsov <[email-masked]> writes:
>
>> Major OpenPGP implementations use streaming mode to sign (e.g. in 'cat
>> InFile | gpg --clearsign'), just as with encryption, without writing
>> sensitive data to a temporary file. They depend on IUF. I haven't seen
>> this with SMIME/CMS -- this is harder, but possible.
> It is no problem to support streaming of inputs and at the same time
> support for example EdDSA which does not follow the IUF paradigm.  Don't
> confuse Unix stdin/stdout streaming with streaming of input to a digital
> signature algorithm.

Yes, but what cost "no problems" actually has in some cases?

Before: one could hash during streaming.
After: one extra re-hashing is needed, denying the benefit of hashing 
while streaming.

To fix this new demand of low-level crypto there needs to be an 
engineering fix at a higher level. In the case of OpenPGP applications 
this means the buffering of the entire input must happen, somehow.

If a user signs+encrypts a 1 TB file, he needs to have at least 2TB of 
disk space, one at the destination, and another at an 
implementation-specific location (e.g. /tmp directory, at destination, 
or $HOME). Besides user unfriendliness, such as slower performance and 
extra free space demands, one cannot really delete/wipe a sensitive file 
on an SSD drive, and the temporary file allows good possibility for 
signature fault attacks.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Tue, 2 Jun 2015 11:10:04 +0000

100% agree with Andrey. 

----- Original Message -----
From: Andrey Jivsov [mailto:[email-masked]]
Sent: Tuesday, June 02, 2015 01:37 AM
To: [email-masked] <[email-masked]>
Subject: Re: [Cfrg] Elliptic Curves - signature scheme: friendliness to low memory implementations (ends on June 3rd)

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

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 2 Jun 2015 14:43:19 +0300

On Mon, Jun 01, 2015 at 10:37:22PM -0700, Andrey Jivsov wrote:
> To fix this new demand of low-level crypto there needs to be an engineering
> fix at a higher level. In the case of OpenPGP applications this means the
> buffering of the entire input must happen, somehow.

All signature algorithms in OpenPGP sign message hash, not the message
itself. So streaming input works fine (assuming the hash function is
CR).

-Ilari

---

From: Taylor R Campbell <[email-masked]>
Date: Wed, 3 Jun 2015 04:19:43 +0000

Date: Wed, 20 May 2015 22:16:16 +0100
   From: Alexey Melnikov <[email-masked]>

   Chairs wish to poll the group on the following topic (please pick one):

   #1: The signature scheme should follow the traditional model of hashing
   the message to be signed, thus trivially supporting IUF APIs in
   constant-space, at the cost of requiring collision resistant hash
   functions.

   #2: The signature scheme should not depend on collision resistance, at the
   cost of the signing algorithm having to buffer messages to be signed.

   #3: option #2, but with an additional "large message" mode defined for
   protocols that feel that they need it, where the message to be signed is
   actually a hash of the true message.

#2.  Let's not repeat the error of RSASSA-PSS's reliance on collision
resistance which led to certificate forgery in the real world with MD5
collisions[1], and let's discourage anyone from designing denial of
service against verifiers into new protocols.

Given a deterministic signature scheme S_k(m) built on a hash function
F_r(m) needing only target collision resistance, it is easy to imagine
a randomized long-message signature scheme satisfied either by
signing-time entropy or by collision resistance of F_r: for a secret
key k and message m, randomly generate r and yield as the signature
`F_r' || S_k(`F_r' || F_r(m)).  The reverse is not so easy.

But while this scheme may be useful to put band-aids over legacy
protocols, it encourages designing protocols that admit denial of
service for verifiers.  Practical protocols involving large messages
should split them into parts that can be verified independently.

The best way to split signed messages likely varies from application
to application: signing numbered parts individually in sequence or
computing a Merkle tree of the parts using F_r and then signing the
root[2] are both plausible.  But there's no need for recommendation of
the basic underlying signature scheme to wait on standardizing these.

[1] Bellare & Rogaway's original PSS proposal, in `The Exact Security
of Digital Signatures -- How to Sign with RSA and Rabin' from
Eurocrypt'96, would have avoided the problem by relying only on target
collision resistance of a keyed hash function.  But RSA, Inc. broke it
when standardizing RSASSA-PSS for PKCS#1 in 2003, by unkeying and
derandomizing the hash function.

[2] For example, Tahoe-LAFS uses a signed Merkle tree for random
access to mutable files.  However, rather than randomly choose F_r per
message, it uses the fixed hash m |---> SHA-256(SHA-256(m)), so it
relies on collision resistance of SHA-256.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Wed, 3 Jun 2015 12:23:07 +0000

#1.

---

From: Rene Struik <[email-masked]>
Date: Wed, 03 Jun 2015 17:14:57 -0400

Dear colleagues:

I still do not understand some of the statements below. Please see 
inline (RS>>, <<RS).

I think having to buffer messages, as with some deterministic Schnorr 
scheme variants, would be highly undesirable. So, based on this I should 
vote against #2. However, I am not sure whether that statement, 
including logical implications, is correct. Similarly, if I wanted 
constant-size I/Os, as #1 seems to suggest, would I then always be stuck 
with requiring collision resistance? Or, do I just not understand what 
is meant with "buffering", and IUF "pattern" in the email poll below?

Best regards, Rene

On 5/20/2015 5:16 PM, Alexey Melnikov wrote:
> Signature schemes have, traditionally, hashed the message to be signed to
> a representative value and then actually signed that value. This has led
> to APIs that follow the Init, Update*, Final (IUF) pattern that allows for
> fragmented or very large messages to be signed with constant memory usage.
>
> Alternatively, some signature schemes hash the message to be signed twice,
> where a prefix of the second hash depends on the result of the first.
> Ed25519 is an example of a scheme of this type. This typically allows the
> signature scheme to require fewer assumptions about the strength of the
> hash function that is employed. However, this approach implies that the signing
> algorithm would have to buffer the entire message. That could lead to
> unacceptable memory usage for applications that sign very large messages.
RS>> Isn't the double signing merely an artifact of running the Schnorr 
signature scheme in a mode where the ephemeral private key is 
deterministically derived from message and private info?
I don't see how this would apply with the original Schnorr scheme, since 
there one simply has s:= k - e d (mod n), where e=h(m,R), where R:=kG, 
where n size of prime-order subgroup, and where k is randomly picked. 
Only with deterministic versions, such as EdDSA, does one also have 
k=f(m,d), for some suitably chosen function f. So, buffering concerns 
only seem at play with deterministic signature schemes. Or, am I missing 
something here?
<<RS
>
> Penalising large messages might be seen as a positive by some because
> signing arbitrarily large messages invites implementations to process
> unauthenticated data because of its potential size.
RS>> I do not understand this, since with non-deterministic schemes one 
does not seem to have this buffering issue on the signing side. For 
verification, obviously one needs to do some computations that depends 
on the entire data-to-be-signed into account, so one can only really 
release this data after positive result of the consistency check 
{whether or not one uses a deterministic or non-deterministic signature 
scheme}.
<<RS
> Also, designs that
> really wish to do this can always define that the message to be signed is
> actually a hash of the data. In doing so they would reintroduce the
> requirement that the hash function be collision resistant, but can
> implement an IUF API in constant space again.
>
> On the other hand, if we wish a signature primitive to be easy to
> substitute into existing protocols then supporting a constant-space IUF
> API might be seen as a requirement.
RS>>
The question seems to be whether requiring constant-space IUF would rule 
out particular solution directions. For non-deterministic Schnorr, where 
k is obtained from an independent RNG source, couldn't one simply 
compute e:=H(m,R) in a streaming fashion, assuming one has a pair (k, 
R:=kG) available?
<<RS

> RS>> Not sure whether the implicit assumptions underlying these choices.
<<RS

> constant-space, at the cost of requiring collision resistant hash
RS>> Not sure whether this statement is universally correct.
<<RS
> cost of the signing algorithm having to buffer messages to be signed.
RS>> As suggested before, non-deterministic Schnorr seems to fall into 
this category, while not requiring buffering. Again, if I need stronger 
coffee, please let me know.
<<RS

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

---

From: Taylor R Campbell <[email-masked]>
Date: Wed, 3 Jun 2015 22:47:34 +0000

Date: Wed, 03 Jun 2015 17:14:57 -0400
   From: Rene Struik <[email-masked]>

   Isn't the double signing merely an artifact of running the Schnorr 

Requiring signers to have a source of entropy at signing time to
randomly choose a distinct k for each signature has historically been
a source of high-profile cryptography disasters[1][2].

The NIST was warned about this in 1991 when standardizing the DSA, and
ignored the warning[3], claiming that entropy at signing time is no
more likely to be bad than entropy at key generation time.  Debian
showed them wrong.

There are three security concerns in Alexey's poll and your question:

(a) secret key recovery if k is reused or even slightly predictable,

(b) signature forgery if the attacker can find collisions in the hash
function, and

(c) denial of service or processing of unauthenticated data if a
protocol requires the verifier to consume arbitrarily large messages
before verifying the signature.

Randomized DSA- or Schnorr-type schemes that use an entropy source at
signing time are vulnerable to (a).  You can defend against this (and
EdDSA does) by hashing the secret key together with the message to
derive k deterministically: the secret key is unpredictable to the
attacker, so standard PRF assumptions imply k is unpredictable too.
(Bonus: easy test vectors for the real signing code.)

Schemes defined in terms of H(m) for a fixed H are vulnerable to (b).
You can defend against this (and EdDSA does) by using a keyed hash
H_k(m) and relying only on target collision resistance instead of
collision resistance.

You could defend against both (a) and (b) by hashing the message under
a different key, say h, and signing H_h(m) -- that is, choose h
randomly, compute H_h(m), and derive k from the secret key and H_h(m)
to sign the message h || H_h(m).  But this leaves (c).

Protocols designed under the assumption of streaming I/U/F are likely
to be vulnerable to (c).  You can defend against this (and EdDSA does)
by encouraging protocol designers to sign and verify short messages
rather than long ones, and to split long messages into independently
verifiable parts, e.g. by signing each part separately or signing the
root of a Merkle tree of parts.

[1] Debian broke OpenSSL's PRNG seeding so that it had only 2^15
possible seeds, enabling recovery of (EC)DSA secret keys used on
affected systems with predictable k even if the secret key was
otherwise secure.  https://wiki.debian.org/SSLkeys

[2] Sony reused k verbatim for PlayStation 3 firmware updates signed
with ECDSA, enabling recovery of the firmware signing key.

fail0verflow, `Console Hacking 2010: PS3 Epic Fail', 27c3, 2010.
http://events.ccc.de/congress/2010/Fahrplan/attachments/1780_27c3_console_hacking_2010.pdf

[3] Miles E. Smid and Dennis K. Branstad (NIST), `Response to Comments
on the NIST Proposed Digital Signature Standard', CRYPTO'92, LNCS 740,
pp. 76--88, Springer, 1993.  (See Sec. 4.9 about k.)

---

From: Stephen Farrell <[email-masked]>
Date: Thu, 04 Jun 2015 00:04:49 +0100

I'd hate to miss one of Alexey's polls:-)

I'm almost neutral on this one. While we have historically preferred
#1 for the reason noted in the subject line, there are really very few
cases where that turns out to be a real issue, as opposed to being a
theoretical one.

So I think we could probably live with #2, and that could suffice for
TLS and DNSSEC and other applications, even though #2 would mean
that users of the signature scheme (e.g. IETF protocol developers) may
need to learn something new, which is a downside.

While #3 seems superficially attractive, my guess is it'd cause more
confusion and interop issues, and is of course offering a choice to
users of the scheme and so I don't like that one:-)

So put me down for (#2 or #1) for this one, with a very very tiny
preference for #2 and documenting that one ought not use this for
signing large things directly (which one probably ought not do in any
case). But #1 would also be an acceptable outcome from my POV since
we're in practice already dependent on the collision resistance of
all the relevant hash functions and that won't ever really go away
as long as there are RSA/SHA256 certificates out there which'll be
the case for years and maybe decades to come. So the security
benefit of #2 isn't so great, although it's real.

If, later on, there is a real need for signing a large thing in a very
memory constrained device, or for verifying such a signature in such a
device, then we could always just define another set of codepoints
and OIDs, etc. for that and treat it as just another signature scheme
that happens to involve the same curve and hash function but used in a
different manner. (And I would guess there'll be more work to do in
this space, if not for that, then for a signature scheme with message
recovery, probably for the just-forming cose wg would be my bet at
the moment, but we'll see what we see.)

Cheers,
S.

On 20/05/15 22:16, Alexey Melnikov wrote:
> unauthenticated data because of its potential size. Also, designs that

---

From: Tom Yu <[email-masked]>
Date: Wed, 03 Jun 2015 19:31:14 -0400

> implement an IUF API in constant space again.

Based on some conversations with people who deal with crypto in high
performance applications, there are use cases for which minimizing
copying and optimizing cache usage can bring significant improvements.
Making multiple passes over messages could cause cache bottlenecks even
on systems that have large amounts of memory.  This was mosty in the
context of symmetric crypto, but I imagine that there are probably
signing scenarios where this is the case.

> Chairs wish to poll the group on the following topic (please pick one):

No strong opinion, but leaning toward #1 or #3.

---

From: Rene Struik <[email-masked]>
Date: Wed, 03 Jun 2015 21:07:47 -0400

Hi Taylor:

I  think that lots of assertions and claims in the email poll are 
somewhat (or, perhaps, a lot) "off" and put people (at least me) on the 
wrong footing. Hence, my email.

Thanks for your anecdotal pointers, which are well-documented factoids 
of in-expert implementations (aka stupidity).

Rene

---

From: Yoav Nir <[email-masked]>
Date: Thu, 4 Jun 2015 08:06:36 +0300

> On Jun 4, 2015, at 2:31 AM, Tom Yu <[email-masked]> wrote:
> 

There could be. But if we generate a signature scheme that works well for certificate authorities as well as common protocols such as TLS, SSH, IKE, and S/Mime, we should do that. 

If that doesn’t fit some use cases, there can be another signature scheme for them. This is kind of like #3, but I don’t think it’s required that the two schemes be linked.

Yoav

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 4 Jun 2015 09:56:58 +0300

> users of the scheme and so I don't like that one:-)

Having an option of hashing the message first (with an indication that
message was prehashed or even what hash was used) would be #3.

Conversely, that would be the most reasonable implementation of #3.

The reason for including hash function is to guard against trying to
confuse implementations over what hash function is used, allowing
forging signatures using stronger hashes by abusing weaker ones. The
internal hash function is much less of concern due to natural
strengthtening from hashing in various things derived from key.

> benefit of #2 isn't so great, although it's real.

The problem with #1 isn't so much the CR requirement, but what it will
do to implementation safety:

Basically, it is difficult to do #1 without either:
- Prehashing the message with something capabile of signing much larger
  things. Adding an indication that this prehash has been done would give
  #3).
- Making scheme that is dangerous by breaking basic safety.

The basic safety requirements I am thinking are:

1) Determinism.

The scheme is fully deterministic.

Breaking this makes the implementations very hard to test.

2) No random/unpredictable inputs except key.

No input to functions except key may be assumed random in any way nor
unpredictable.

Breaking this makes primitive easy to misuse in ways that cause
catastrophic breakage (reveal signing private key).

3) No scalar inversions or square roots for signature

Signing must not need computing 1/x mod l or sqrt(x) mod l.

Breaking this doesn't just make scheme slow, but also causes severe
side-channel hazards.

And sidechannels matter: Modern CPUs and OSes are ridiculously vulernable,
with attackers capable of exploiting such bugs across virtual machines on
the same physical hardware.

4) No nonces in main mode

The main mode may not assume any input is not repeated.

Breaking this again makes scheme easy to misuse with very bad results
(hopefully anything using special modes will read the caveats).

Breaking any of these will cause real-world failures, as has been
demonstrated many times by ECDSA.

-Ilari

---

From: Rene Struik <[email-masked]>
Date: Thu, 04 Jun 2015 09:27:17 -0400

Hi Ilari:

Just curious about your side channel remarks: could you give an example 
where side channel resistance of sqrt{x} is required? Wouldn't this 
computation only arise if one were to uncompress points, or can you give 
another example?

Best regards, Rene

---

From: Rene Struik <[email-masked]>
Date: Thu, 04 Jun 2015 10:09:29 -0400

Hi Ilari:

Just curious about your remark that deterministic signatures would allow 
for easier testability.

I don't know how these tests would exactly look like, but I presume 
these take as input some messages and public keys written in a spec and 
then checking whether the signature output is indeed as listed in the 
spec for the corresponding message/public key pairs {let us assume that 
these test parameters have been confirmed independently, prior to ending 
up in this spec}. Wouldn't one be able to get similar testability 
results by listing as input some messages and public/private key pairs, 
and then checking whether the signature output is indeed as listed in 
the spec? {After all, one can recompute all private parameters, once the 
private signing key is known.} If so, this would provide easy 
testability also in case of non-deterministic signature schemes. Note 
that the signature verification routine already provides virtually all 
the mechanisms to implement these "self tests", so incremental 
implementation cost would be virtually zero.

In either case, the testability argument seems to provide only evidence 
re "expected" implementation behavior with specified test parameters and 
not for any non-specified input/output parameters.

Best regards, Rene

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 4 Jun 2015 17:58:59 +0300

On Thu, Jun 04, 2015 at 10:09:29AM -0400, Rene Struik wrote:

> Note that the signature verification routine already provides virtually all
> the mechanisms to implement these "self tests", so incremental implementation
> cost would be virtually zero.

The problem is that this only catches buggy generation of the signature
once k is chosen (which one tends to quickly notice anyway, since nothing
works properly). It does not catch buggy generation of k (which is much harder
to notice and could easily lead to catastrophic failure). 

-Ilari

---

From: Rene Struik <[email-masked]>
Date: Thu, 04 Jun 2015 11:24:18 -0400

Hi Ilari:

Well, neither do deterministic signatures seem to help here: if one 
presumes k=f(m,d) and indeed finds that, for fixed public signature key, 
repeats of message m produce the same signature, this does not 
necessarily imply that f depends on private parameter d (for all one 
knows, k could only depend on public parameter m). This can only be 
detected if one prints the private parameter d in the spec. However, 
this does not say anything about behavior with "non-printed-in-the-spec" 
parameters.

Rene

---

From: David Jacobson <[email-masked]>
Date: Thu, 04 Jun 2015 09:14:53 -0700

If the field modulus p is congruent to 3 mod 4, one of the square roots 
of x can be computed by x^((p+1)/4) mod p, and the inverse can computed 
with x^(p-2) mod p.  Since the exponent is known, one does not need to 
worry about leaking bits of the exponent.  Underneath that, it is just 
multiplies and adds, and of those leak were are had anyway.

I don't see the problem.

      --David Jacobson

On 6/4/15 6:27 AM, Rene Struik wrote:
> Hi Ilari:
>
> Just curious about your side channel remarks: could you give an 
> example where side channel resistance of sqrt{x} is required? Wouldn't 
> this computation only arise if one were to uncompress points, or can 
> you give another example?
>
> Best regards, Rene
>

---

From: Watson Ladd <[email-masked]>
Date: Thu, 4 Jun 2015 09:25:20 -0700

On Thu, Jun 4, 2015 at 8:24 AM, Rene Struik <[email-masked]> wrote:

> repeats of message m produce the same signature, this does not necessarily
> imply that f depends on private parameter d (for all one knows, k could
> only depend on public parameter m). This can only be detected if one prints
> the private parameter d in the spec. However, this does not say anything
> about behavior with "non-printed-in-the-spec" parameters.

No, the spec specifies a function sign(message, private_key) that returns a
signature. Because it specifies the function completely (defines the
function), it's possible to provide message, private_key pairs and require
the output to be a specific form. The functionality tested this way is
exactly the functionality used.

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

---

From: Taylor R Campbell <[email-masked]>
Date: Thu, 4 Jun 2015 16:38:11 +0000

Date: Thu, 04 Jun 2015 11:24:18 -0400
   From: Rene Struik <[email-masked]>

How do you write a test vector for signing without including the
signing key?

For a deterministic scheme, test vectors of the form

(secret key, message, signature)

verify correctness of the complete signing operation.

For a nondeterministic scheme, test vectors of the form

(secret key, message, nonce, signature)

verify only correctness of the deterministic part of the signing
operation, and cannot verify correctness of nonce generation.  For
RSASSA-PSS, `nonce' generation is inconsequential for security; for
ECDSA, nonce generation makes or breaks it.

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 4 Jun 2015 19:50:28 +0300

On Thu, Jun 04, 2015 at 09:14:53AM -0700, David Jacobson wrote:
> If the field modulus p is congruent to 3 mod 4, one of the square roots of x
> can be computed by x^((p+1)/4) mod p, and the inverse can computed with
> x^(p-2) mod p.  Since the exponent is known, one does not need to worry
> about leaking bits of the exponent.  Underneath that, it is just multiplies
> and adds, and of those leak were are had anyway.

I was talking about l, not p (even ECDH needs constant-time 1/x mod p,
and sqrt(x) mod p pretty much only pops up in point decompression, which
is verification side).

Sqrt(x) mod l: l can be 1 mod 8, even for p 3 mod 4 (e.g. Curve41417).
Fortunately, no signature primitive seems to use sqrt(x) mod l for anything.

1/x mod l: x^(l-2) mod l does work, but is pretty slow (there are more multiples
and each multiply is slower than with 1/x mod p). ECDSA does have this when
signing (it inverts secret k), easily creating side channels when unsafe methods
(e.g. EGCD) are used.

-Ilari

---

From: Derek Atkins <[email-masked]>
Date: Thu, 04 Jun 2015 12:59:20 -0400

Rene Struik <[email-masked]> writes:

> Hi Ilari:
>
> Just curious about your remark that deterministic signatures would
> allow for easier testability.
>
> these take as input some messages and public keys written in a spec
> the spec for the corresponding message/public key pairs {let us assume
> that these test parameters have been confirmed independently, prior to

No, you would publish the *PRIVATE* key, the message, and the signature,
so that you could verify that your implementation generates the exact
same signature given the exact same inputs.

You could theoretically do this with a non-deterministic scheme as well
if you also publish the random nonces along with the private key
parameters.  But having a deterministic signature scheme is better,
IMHO, because frankly some devices don't have a good source of random
numbers.

-derek
-- 
       Derek Atkins                 617-623-3745
       [email-masked]             www.ihtfp.com
       Computer and Internet Security Consultant

---

From: Rene Struik <[email-masked]>
Date: Thu, 04 Jun 2015 13:00:03 -0400

This only verifies that the implementation outputs behavior consistent 
with what is written in the spec. It does not verify correctness for any 
other input or for a non-exposed signing key {an implementation could 
simply include a table look-up for "CFRG test vectors" and do its own 
thing otherwise (and you would not catch this...)}. This illustrates the 
limited value of such tests. Comparing test results with a handful of 
printed values in a spec is *not* the same as validating the proper 
functioning of an implementation module.

---

From: Mike Hamburg <[email-masked]>
Date: Thu, 04 Jun 2015 10:13:02 -0700

Rene,

Your quibble is true for any testing scheme.  Public test vectors in a 
spec aren't for proving that a piece of software is free of hidden 
faults.  They are for software authors checking that their 
honestly-written software does at least roughly the right thing, at 
least some fraction of the time.  An evaluator can also use their own 
test vectors to defeat a "CFRG lookup table", but that still does not 
prove the absence of backdoors.

Obviously the coverage you get from this varies by primitive, so AES is 
more testable than signing.  Fine.  But specifying deterministic 
signatures still improves testability, to a degree that will be useful 
in the real world.

-- Mike

On 06/04/2015 10:00 AM, Rene Struik wrote:
> with what is written in the spec. It does not verify correctness for 
> any other input or for a non-exposed signing key {an implementation 
> could simply include a table look-up for "CFRG test vectors" and do 
> its own thing otherwise (and you would not catch this...)}. This 
> illustrates the limited value of such tests. Comparing test results 
> with a handful of printed values in a spec is *not* the same as 
> validating the proper functioning of an implementation module.
>

---

From: Yoav Nir <[email-masked]>
Date: Thu, 4 Jun 2015 20:20:10 +0300

> On Jun 4, 2015, at 7:59 PM, Derek Atkins <[email-masked]> wrote:
> 

I agree. Additionally, that test with provided nonces forces you to have aa special test path in your code.

Normally, your cryptographic library wouldn’t expose to the user that it is using random input. Consider OpenSSL’s ECDSA signing function:
  ECDSA_SIG*     ECDSA_do_sign(const unsigned char *dgst, int dgst_len, EC_KEY *eckey);

Internally this function calls whatever random number generator is either part of the library or used by it, but the user doesn’t need to worry about it.

Once you have the need to test, you need a new function. OpenSSL has that as well:
  ECDSA_SIG*     ECDSA_do_sign_ex(const unsigned char *dgst, int dgstlen, 
                        const BIGNUM *kinv, const BIGNUM *rp,
                        EC_KEY *eckey);

The application doesn’t call this second function. It calls the first function. So you’re testing a function that is different from the one that you are testing.

That’s an artifact of having to test randomized signatures. There is no equivalent for, say, RSA.

Yoav

P.S. Yes, I know that the first function just calls the second function, and that the second function generates randoms if kinv and rp are NULL. But this expanded API would not exist if not for the need of testing.

---

From: Nico Williams <[email-masked]>
Date: Thu, 4 Jun 2015 13:36:32 -0500

On Thu, Jun 04, 2015 at 10:09:29AM -0400, Rene Struik wrote:
> [...]

It isn't possible to write test vectors for non-deterministic signature
schemes unless you expose PRNG state or nonce inputs as explicit
arguments to the API.  Regardless of whether one chooses to do that or
not, non-deterministic signature schemes whose security falls apart when
nonces are reused (or are predictable) is a really bad idea.

Anyways, we've already determined that we have consensus in favor of
deterministic signature schemes.  You could ask that that matter be
re-opened, but first re-read the threads that led there.

Nico
--

---

From: Nico Williams <[email-masked]>
Date: Thu, 4 Jun 2015 13:39:51 -0500

On Thu, Jun 04, 2015 at 10:13:02AM -0700, Mike Hamburg wrote:
> Obviously the coverage you get from this varies by primitive, so AES
> is more testable than signing.  Fine.  But specifying deterministic
> signatures still improves testability, to a degree that will be
> useful in the real world.

Deterministic signatures do much more than make it easier to test
implementations: they also remove hidden state and/or dependency on
TRNGs (and in the process, one more possible place to check has no side
channels).  This is a big deal.  Tests shows the implementation works,
and determinism shows the implementation should continue to work when
used in production.

Nico
--

---

From: Rene Struik <[email-masked]>
Date: Thu, 04 Jun 2015 15:21:33 -0400

I think one lesson one can draw from "piecemeal polls" is that it might 
make it harder to consider system-wide trade-offs.

Hence, the questions in my email of yesterday, June 3, 2015, 5.14pm EDT, 
see http://www.ietf.org/mail-archive/web/cfrg/current/msg06875.html. I 
think these still stand.

Rene

---

From: Watson Ladd <[email-masked]>
Date: Thu, 4 Jun 2015 12:54:40 -0700

> see http://www.ietf.org/mail-archive/web/cfrg/current/msg06875.html. I

Note that verifiers will still accept signatures generated with random k,
permitting the avoidance of double hashing while preserving the more than
collision property in systems which actually require this.

---

From: Nico Williams <[email-masked]>
Date: Thu, 4 Jun 2015 15:02:45 -0500

On Thu, Jun 04, 2015 at 03:21:33PM -0400, Rene Struik wrote:
> I think one lesson one can draw from "piecemeal polls" is that it
> might make it harder to consider system-wide trade-offs.

This sub-poll became clearly necessary after the poll as to determinism
started, since that's when the online vs. CR matter came up.  Even if
the chairs had foreseen that outcome and produced a more complete single
poll, the overall outcome would probably still have been that we want a
deterministic signature scheme because the alternative hasn't worked out
well in practice and it's easy to see how it is very difficult to make
it work out well in practice.  And once all these polls are done I
suppose the chairs could well ask to confirm the overall outcome, but
there's nothing wrong with organic discovery of consensus.

Incidentally, Watson L. pointed out earlier in this poll that maybe we
can't get a deterministic, online, and CR (independent of the hash
function) signature scheme.  Nothing has changed since then on that
front.

The trade-offs come out the same for me: deterministic is the first
priority, so we're down to choosing between online and CR.

Since one can always make an online and not-CR scheme out of an offline
scheme, that's clearly what we should do, and everyone can be pleased.
(There's an extra hashing step in this case, but if bulk data is the
source of the online requirement, then the extra hash step is a
performance non-issue.)

For me the only question left is whether we should specify an online
scheme tightly integrated with the off-line scheme #3.  At first I was
in favor of this, now I'm in favor of #2 alone.  Online by generic
construction will do.  But I'm not opposed to #3 either.  I'm just
opposed to #1 on account of the past failures we have seen with online
signature schemes: the hash functions we've used have had a bad history
on the CR front, and we don't really have the confidence we need on the
current batch of hash functions.

Perhaps *after* a decade of SHA-3 cryptanalysis research we'll find that
SHA-3 is good enough for an online signature scheme and then we might be
sad about the choice to have an offline scheme back in 2015, but that
sadness will not be due to the scheme becoming insecure as a result, but
just that we could have been less paranoid.  I can live with that.

Nico
--

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 4 Jun 2015 23:18:34 +0300

On Thu, Jun 04, 2015 at 03:21:33PM -0400, Rene Struik wrote:
> I think one lesson one can draw from "piecemeal polls" is that it might make
> it harder to consider system-wide trade-offs.
> 
> Hence, the questions in my email of yesterday, June 3, 2015, 5.14pm EDT, see
> http://www.ietf.org/mail-archive/web/cfrg/current/msg06875.html. I think
> these still stand.

Going through briefly.

- Randomly generating k in Schnorr is very dangerous. And the dangers go
  far beyond testability.
- One can do deterministic one-pass Schnorr at cost of requiring nonces
  (the usual definition, not the bizarro one ECDSA uses).
- However, I think that is still too dangerous for main mode.
- The message size argument is that since verification is not streamable,
  and thus large message cause pain for verifiers, let's also cause pain
  for signers in order to keep those message sizes in check.

-Ilari

---

From: Nico Williams <[email-masked]>
Date: Thu, 4 Jun 2015 15:23:27 -0500

> collision property in systems which actually require this.

Right, special-purpose implementations can resort to such optimizations
because special-purpose implementations are more likely to manage the
requisite state and/or TRNG.  But for general purpose implementations we
should have deterministic behavior.

Note also that verification for message-derived k schemes is still
online (though implementations should generall not permit access to the
message prior to signature verification).  It's only the signature
function that is made offline by the CR constructions we've discussed.

Nico
--

---

From: Watson Ladd <[email-masked]>
Date: Thu, 4 Jun 2015 13:35:34 -0700

> function that is made offline by the CR constructions we've discussed.

Let's consider an actual scheme for a moment, namely EdDSA. The verifier
takes R and s, computes e=H(R, M), and determines if R=sG+eP. This only
requires one pass through the message, not two, which for some reason we
are calling "online" vs. "offline".

Why don't we see if anyone has an actual objection to EdDSA, instead of
fooling around trying to repeat this work? It's soon going to be over a
year: I'd like to see a finished product then,

---

From: Nico Williams <[email-masked]>
Date: Thu, 4 Jun 2015 16:53:37 -0500

> year: I'd like to see a finished product then,

+1

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 5 Jun 2015 09:16:14 +0300

> > year: I'd like to see a finished product then,

The few prototypes I have written are heavily inspired by EdDSA. The
differences have been (some are bad ideas):

1) Modify k-generation to support larger curves

Generate d and seed as separate expansions of secret key.

This is needed in order to use SHA-512 and other standard-issue
512-bit hashes with 448-bit curve.

2) Optional couponing

Take in nonce (the usual kind, not the ECDSA kind) and pregenerate
k and kG out of that. 

Bad idea for standard use (needed for some specialist low-latency
applications).

3) Tweaks

Change way k is derived from key and message, so the same message can
generate different signatures.

Probably a bad idea: One can leak secret key by maliscously abusing
this.

4) Signature contexts

Extra data that must match between signer and verifier, to counter cross-
protocol attacks.

Cross-protocol attacks against signatures seem to be dime dozen.

5) Hash domains

Add function used for message prehashing (which may be indentity) into
signature.

Allows support for both online and offline mode and prevents attacking
stronger hashes by confusing those with weaker ones.

-Ilari

---

From: Simon Josefsson <[email-masked]>
Date: Sat, 06 Jun 2015 03:53:54 +0200

> After: one extra re-hashing is needed, denying the benefit of hashing

I believe you are mistaken.  OpenPGP with EdDSA only hashes once, during
streaming.

> this means the buffering of the entire input must happen, somehow.

This is false, there is no need to buffer the entire message.  Just hash
the stream and sign the hash.

> extra free space demands, one cannot really delete/wipe a sensitive
> file on an SSD drive, and the temporary file allows good possibility
> for signature fault attacks.

I believe GnuPG already implements EdDSA signing, so you can look at the
implementation to see how it actually works.  There is no temporary
files the same size as the input.

/Simon

---

From: Andrey Jivsov <[email-masked]>
Date: Sun, 07 Jun 2015 23:38:26 -0700

On 06/05/2015 06:53 PM, Simon Josefsson wrote:
...
> I believe you are mistaken.  OpenPGP with EdDSA only hashes once, during

For example, GnuPGP, which follows the 
https://tools.ietf.org/html/draft-koch-eddsa-for-openpgp-02#section-5 
(search for "a digest of the message is used as input"), hashes the 
message three times.

_gcry_ecc_eddsa_sign hashes the input twice (per EdDSA spec), and the 
'gcry_mpi_t input', the input to the EdDSA sign function, is the hash of 
the message (note that the input is the MPI, not a file or a buffer). 
The higher-level code hashed the actual input into that MPI passed to 
_gcry_ecc_eddsa_sign.

By doing so GnuPG implementation and the spec above depend on the poll's 
#3 as the only mode (for large or small messages alike).

It follows that GnuPG signing method always depends on collision 
resistance of the hash function, (always with ECDSA, and always with 
EdDSA). This means that the 2 extra hashings done in the EdDSA sign 
function don't buy much (at least they don't free one from using a 
collision resistant function).

> the stream and sign the hash.

Correct. This is poll's #3. One would need to buffer during streaming 
with poll's #2.

> files the same size as the input.

I double-checked the above with the libgcrypt-1.6.3 source code.

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 8 Jun 2015 14:09:44 +0300

On Sun, Jun 07, 2015 at 11:38:26PM -0700, Andrey Jivsov wrote:
> 
> It follows that GnuPG signing method always depends on collision resistance
> of the hash function, (always with ECDSA, and always with EdDSA). This means
> that the 2 extra hashings done in the EdDSA sign function don't buy much (at
> least they don't free one from using a collision resistant function).

Yes, those two don't free from having to have CR hash function, however, what
those do is:

- Not having to do "nonce" generation involving random numbers (which has
  a long history of trainwrecks).
- Not having to do divisions mod order. Divisions mod order when verifying are
  annoying, divisions mod order when signing are dangerous.

And besides, both "extra" hashes look to be just one SHA-512 block if hash
algorithm is SHA-256.

And signing long messages like CMS and OpenPGP do is more of an exception.
Most signing is of short messages.

-Ilari

---

From: Alexey Melnikov <[email-masked]>
Date: Tue, 09 Jun 2015 15:21:35 +0100

> actually a hash of the true message.

After discussing answers to this poll chairs concluded that despite
security limitations of Initiliase-Update-Finalise (IUF) APIs on verifier's
end, there is rough consensus that any recommended CFRG signature scheme
should support such APIs.

The next step for CFRG is to solicit proposals for EC signature schemes that
satisfy the previously agreed requirements, including support for the IUF APIs.

---

From: Watson Ladd <[email-masked]>
Date: Tue, 9 Jun 2015 14:44:05 -0700

> satisfy the previously agreed requirements, including support for the IUF
APIs.

Does this mean that option 3 has been taken, or option 1? Or will we permit
both and decide based on what the schemes look like?

---

From: Nico Williams <[email-masked]>
Date: Tue, 9 Jun 2015 20:02:57 -0500

> both and decide based on what the schemes look like?

My take is that this is still to be decided (otherwise why not be clear
about it?).

I think it would be a terrible mistake to not have a deterministic and
collision-resistant signature scheme, but it would not be a terrible
mistake to *also* have a deterministic and not-CR (but online) signature
scheme.  One can argue that having the latter is an invitation to others
to make terrible mistakes, but it can't possibly be as bad as not having
*any* determnistic and CR signature scheme.

Nico
--

---

From: Tony Arcieri <[email-masked]>
Date: Tue, 9 Jun 2015 18:09:45 -0700

On Tue, Jun 9, 2015 at 6:02 PM, Nico Williams <[email-masked]> wrote:

> scheme.

+1. I was trying to make that same point with my vote

-- 
Tony Arcieri

---

From: Simon Josefsson <[email-masked]>
Date: Wed, 10 Jun 2015 16:03:47 +0200

> (search for "a digest of the message is used as input"), hashes the

Well, not really, it hashes the message (the data to sign) once, and
then signs the hash value using EdDSA.  Yes, EdDSA internally hashes its
input (the hash value) twice, but that won't require buffering the
entire data to sign (the message).  I believe it was that property
("hash entire message once or multiple times") that was under
discussion.  So I think we actually agree on everything except we had
different contexts of this discussion.

> 'gcry_mpi_t input', the input to the EdDSA sign function, is the hash
> of the message (note that the input is the MPI, not a file or a
> buffer). The higher-level code hashed the actual input into that MPI
> passed to _gcry_ecc_eddsa_sign.
>
> By doing so GnuPG implementation and the spec above depend on the
> poll's #3 as the only mode (for large or small messages alike).

Right.  Thanks for analysis.

> collision resistant function).

Right.

> Correct. This is poll's #3. One would need to buffer during streaming

Not so fast -- it would be perfectly fine for CFRG to stop and only do
#2 and leave the #3 part to higher-level protocols, like OpenPGP and
S/MIME which has the large-message-concern.  It seems OpenPGP has
already done this.

/Simon

---

From: "D. J. Bernstein" <[email-masked]>
Date: 13 Jun 2015 00:31:36 -0000

Alexey Melnikov writes:
> security limitations of Initiliase-Update-Finalise (IUF) APIs on
> verifier's end, there is rough consensus that any recommended CFRG
> signature scheme should support such APIs.

I can't figure out what this statement means. Can you please clarify
what you're saying the rough consensus is?

Taking, e.g., Ed25519 as an example: Would recommending

   * Ed25519(m) as the higher-security default and
   * Ed25519(SHA-3-512(m)), with an IUF API, for protocols that want
     small devices to be able to handle large messages in one pass

meet the requirement to "support" an IUF API?

Or are you saying that the recommendation would have to be just
Ed25519(SHA-3-512(m)), and that there's rough consensus against
splitting out the Ed25519(m) layer for protocols that want the higher
security?

---Dan

---

From: Tony Arcieri <[email-masked]>
Date: Fri, 12 Jun 2015 18:12:43 -0700

> what you're saying the rough consensus is?

+1. Given the numbered options, which one do you mean?

-- 
Tony Arcieri

---

From: Alexey Melnikov <[email-masked]>
Date: Tue, 16 Jun 2015 10:05:40 +0100

On 13/06/2015 02:12, Tony Arcieri wrote:
> On Fri, Jun 12, 2015 at 5:31 PM, D. J. Bernstein <[email-masked] 
> <mailto:[email-masked]>> wrote:
>

There was rough consensus for the option #1.

---

From: Alexey Melnikov <[email-masked]>
Date: Tue, 16 Jun 2015 10:18:57 +0100

> splitting out the Ed25519(m) layer for protocols that want the higher
The rough consensus is that CFRG EC signature recommendation to IETF 
would have to provide IUF API.

In your example, this means that "Ed25519(SHA-3-512(m)), with an IUF 
API" satisfies the requirement and CFRG poll result doesn't say anything 
about (doesn't recommend and doesn't prohibit) "Ed25519(m) as the 
higher-security default".

---

From: "D. J. Bernstein" <[email-masked]>
Date: 19 Jun 2015 06:27:52 -0000

I'm still unable to figure out what the chairs are saying the rough
consensus is. I'll keep using Ed25519 and SHA-3-512 to illustrate the
options available:

   Option #1: Specify Ed25519(SHA-3-512(m)) with an IUF API.
   Option #2: Specify higher-security Ed25519(m).
   Option #3: Specify Ed25519(m) as the higher-security default and
              Ed25519(SHA-3-512(m)) for applications that need IUF.

I understand that the chairs are saying that the following position has
rough consensus: the demand for deploying IUF APIs in some applications
outweighs the security concerns regarding those APIs; consequently, CFRG
needs to specify an IUF signature scheme, such as Ed25519(SHA-3-512(m)).

This is, however, compatible with _also_ specifying the more fundamental
Ed25519(m) layer as the default higher-security signature scheme. My
reading of the discussions so far is that it would be easy to justify
doing this: specifying Ed25519(m) as the higher-security default and
Ed25519(SHA-3-512(m)) for applications that need IUF. Both Ed25519(m)
and Ed25519(SHA-3-512(m)) have clearly attracted significant interest.

Are the chairs saying that the rough consensus is to do this? Or that
the rough consensus is to _not_ do this? Or still unsettled?

I would expect the first answer, but what I've seen is a completely
unclear mix of the second answer and the third answer. See quotes below.
Obviously clarification is required.

Alexey Melnikov writes:
> API" satisfies the requirement and CFRG poll result doesn't say
> anything about (doesn't recommend and doesn't prohibit) "Ed25519(m) as
> the higher-security default".

Okay. This seems to be a clear statement that the rough consensus is
against option #2---the choice between option #1 and option #3 hasn't
been resolved yet. "Doesn't recommend" allows option #1, and "doesn't 
prohibit" allows option #3.

In other words, you're saying that the rough consensus is that CFRG
needs to provide Ed25519(SHA-3-512(m)) or something else with an IUF
API, and that it isn't settled yet whether CFRG will also provide
something like Ed25519(m).

> There was rough consensus for the option #1.

This contradicts the "doesn't prohibit" statement. Option #1 would mean
specifying _only_ Ed25519(SHA-3-512(m)), and _not_ specifying Ed25519(m)
as the higher-security default.

---Dan

---

From: Alyssa Rowan <[email-masked]>
Date: Fri, 19 Jun 2015 19:00:15 +0100

On 2015-06-19 07:27, D. J. Bernstein wrote:

> I understand that the chairs are saying that the following
> position has rough consensus:

I've largely stayed out of this poll as I don't have an incredibly
strong opinion here, but I'd also like clarity.

EdDSA(H(m)) is weaker than EdDSA(m). Of course we desire
collision-resistance in any hash that we choose, but EdDSA(m) doesn't
NEED it.

If we propose a change to Ed25519 that makes it weaker, we'll need to
be very, very careful to justify why: otherwise our recommendations to
the upstream working group may well not be useful in contrast to
existing rough consensus and running code in, e.g., GnuPG and OpenSSH.
If we don't have a strong opinion, is it really worth the change?

TLS WG don't seem to have any concerns about Ed25519 implementation:
they're in fact talking about which OIDs to allocate. They are the
ones who will implement it in a way which most interacts with
init-update-final APIs: if they don't care to change it, need we?

- -- 
/akr

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Fri, 19 Jun 2015 18:04:25 +0000

>collision-resistance in any hash that we choose, but EdDSA(m) doesn't

Yes EdDSA(H(m)) is weaker, but (a) this weakness is negligible even from
the theoretical point of view, and (b) it is much more *usable* and
*practical* that EdDSA(m).

Needless to say, I much prefer EdDSA(H(m)), for the simple reasons
mentioned above.

---

From: Tony Arcieri <[email-masked]>
Date: Fri, 19 Jun 2015 11:19:23 -0700

On Fri, Jun 19, 2015 at 11:04 AM, Blumenthal, Uri - 0553 - MITLL <
[email-masked]> wrote:

> the theoretical point of view

Uhh, remember Flame? Collisions have been used in real-world attacks
against the X.509 PKI.

-- 
Tony Arcieri

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Fri, 19 Jun 2015 20:24:48 +0000

> On Fri, Jun 19, 2015 at 11:04 AM, Blumenthal, Uri - 0553 - MITLL
> <[email-masked]> wrote:
> Uhh, remember Flame? Collisions have been used in real-world attacks against
> the X.509 PKI.

Uhh, IMHO we are supposed to be practical even when paranoid. I find it
certain that we all would be beyond caring by the time collisions are
produced in SHA-3.

---

From: Alexey Melnikov <[email-masked]>
Date: Fri, 19 Jun 2015 21:46:28 +0100

Alyssa,

> If we don't have a strong opinion, is it really worth the change?
Just a reminder that CFRG is not trying to rubber-stamp any particular 
signature algorithm. CFRG might end up converging on something based on 
EdDSA, but at the moment it is too early to tell.

> init-update-final APIs: if they don't care to change it, need we?
TLS WG will not assign an OID until the signature recommendation is 
settled in CFRG. Stephen (Security AD) was quite clear that he is 
against proliferation of multiple ciphers/signatures/etc and that he 
wants the signature issue to be settled in CFRG first.

Best Regards,
Alexey

---

From: "Paterson, Kenny" <[email-masked]>
Date: Fri, 19 Jun 2015 20:51:27 +0000

Hi,

On 19/06/2015 07:27, "D. J. Bernstein" <[email-masked]> wrote:

>consensus is.

Option 1: the IUF API.

We will focus on that option for now.

(Consensus *was* rough though.)

> I'll keep using Ed25519 and SHA-3-512 to illustrate the
>options available:

I appreciate that you are using Ed25519 merely to make things concrete,
but it's perhaps worth making it clear that we've not yet settled on any
particular signature scheme. Of course, Schnorr and DSA variants will be
prime candidates. 

Alexey and I are meeting tomorrow to discuss how to structure the next
part of our work. We hope to come to the list with a proposal for that
soon after.

Cheers,

Kenny

---

From: Björn Edström <[email-masked]>
Date: Fri, 19 Jun 2015 22:51:08 +0200

I like Option #3. That seems likely what people are going to do anyway
(modulo choice of hash function).

As a working software engineer in the industry a potential break of
the hash function in this case would be the least of my concern.

- Björn

---

From: Adam Langley <[email-masked]>
Date: Fri, 19 Jun 2015 14:32:26 -0700

Ponder, for a second, a world in which CFRG specified two schemes:
Ed25519(m) and Ed25519(H(m)).

Also consider a PKI system that issues certificates and CRLs.
Certificates are a type of message and are some serialisation of {0,
name, public-key of name}, where the zero is a single byte that serves
as a "type" indicator. CRLs are another type of message and are {1,
start-time, end-time, list of revoked certificate hashes}.

A signed message is {message, signature-algorithm, signature}.

Now, you might not think that this design is wise, but I would argue
that it's plausible as it's similar to X.509.

I, the attacker, can register a domain name and get a certificate for
it. The CA happens to sign with Ed25519(H(m)), even though the
messages aren't very large. So, offline, I iterate over many domain
names and pick one where the hash of the certificate structure for
that name and my public-key looks like a valid CRL message. I need to
fix the first byte to be one, probably fix a few other length bytes,
and obviously my fake CRL has to be exactly the length of a hash, but
the work-factor is pretty plausible.

Now I register that domain name and get a certificate for it. Then I
construct {message = fake CRL, signature-algorithm = Ed25519(m),
signature = signature from real certificate}. That should validate,
no? If I can construct a valid, signed CRL that covers a wide range of
time then I've broken revocation in this system.

The key here is that the attacker can specify the signature algorithm
and confuse the verifier. X.509 allows exactly this but, even if not,
I suspect that people will use the same key in several different
contexts like that.

So we would need to be careful with Ed25519(H(m)).

Cheers

AGL

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Fri, 19 Jun 2015 21:40:30 +0000

On 6/19/15, 17:32 , "Adam Langley" <[email-masked]> wrote:

>Ed25519(m) and Ed25519(H(m))…...
>

Good point. But doesn’t that imply the ability to create collisions in H()
at will?

>So we would need to be careful with Ed25519(H(m)).

Sure… On the other hand, I’d like a demonstration, if possible. One
example of the above would suffice. :-)

P.S. I assume H() is a decent hash, e.g. SHA-3 or BLAKE2.

---

From: Adam Langley <[email-masked]>
Date: Fri, 19 Jun 2015 14:53:06 -0700

> Good point. But doesn’t that imply the ability to create collisions in H()

No, it's just a hash-cash problem: find x such that the first byte of
H(x) is one, and such that a couple of other bytes in H(x) have
certain values. Even if the hash function is perfect, trying 256
different values of x should give you one where H(x) starts with a
particular byte.

Cheers

AGL

-- 
Adam Langley [email-masked] https://www.imperialviolet.org

---

From: Paul Hoffman <[email-masked]>
Date: Fri, 19 Jun 2015 14:56:26 -0700

On Jun 19, 2015, at 2:32 PM, Adam Langley <[email-masked]> wrote:
> So, offline, I iterate over many domain
> that name and my public-key looks like a valid CRL message.

In order to do this, don't you need to have broken the preimage resistance of the hash, or that the output length of the hash has to be 160 bits or less?

--Paul Hoffman

---

From: Tony Arcieri <[email-masked]>
Date: Fri, 19 Jun 2015 15:03:34 -0700

On Fri, Jun 19, 2015 at 1:24 PM, Blumenthal, Uri - 0553 - MITLL <
[email-masked]> wrote:

> As the expression goes "attacks always get better". I definitely care
about having constructions that would survive SHA-3 collisions, and I also
think they might pose a credible threat in the next two decades or so.

I guess the counterargument is to swear off primitives with fewer sharp
edges due to the constraints of devices that will be obsolete in a few
years? I would prefer to have cryptographic primitives that stand the test
of time.

-- 
Tony Arcieri

---

From: "Paterson, Kenny" <[email-masked]>
Date: Fri, 19 Jun 2015 22:08:09 +0000

Folks,

I appreciate the input, but let's not rerun all the arguments we've
already had. 

People were quite rightly asking the chairs to provide more clarity on the
result of the poll. We've now done that.

It was narrow, but option 1 had the most support.

Cheers

Kenny  

On 19/06/2015 23:03, "Tony Arcieri" <[email-masked]> wrote:

>On Fri, Jun 19, 2015 at 1:24 PM, Blumenthal, Uri - 0553 - MITLL
><[email-masked]> wrote:
>
>
>about having constructions that would survive SHA-3 collisions, and I
>also think they might pose a credible threat in the next two decades or
>so.
>
>
>years? I would prefer to have cryptographic primitives that stand the
>test of time.
>
>
>-- 
>Tony Arcieri
>
>
>

---

From: Andrey Jivsov <[email-masked]>
Date: Fri, 19 Jun 2015 15:29:49 -0700

> So we would need to be careful with Ed25519(H(m)).
We can stress that IUF is a property of the key. I think this is a 
natural thing to do.

Randomized signatures mitigate these concerns too. The attack Adam 
described assumes that the attacker controls the image of the H(m) fed 
by the CA to Ed25519.

Compare this with sig = nonce | Ed25519(H(nonce | m))), where the signer 
picks/derives the unpredictable nonce somehow. Applications that want 
IUF need it for "large" files, and they shouldn't mind expanding the 
signature with an explicit nonce.

( On Adam's particular attack, it's odd that a (small) X.509 cert is 
signed as Ed25519(H(m)), but a (large) CRL as Ed25519(m) ).

---

From: Taylor R Campbell <[email-masked]>
Date: Fri, 19 Jun 2015 22:58:55 +0000

Date: Fri, 19 Jun 2015 21:40:30 +0000
   From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>

   On 6/19/15, 17:32 , "Adam Langley" <[email-masked]> wrote:

   >Ed25519(m) and Ed25519(H(m))...

This is why I and others pointed out that you need to sign the choice
of H along with H(m) if you want to do this seriously:

Ed25519(`literal' || m)
Ed25519(`SHA3-512' || SHA3-512(m))
r || Ed25519(`BLAKE2S-PRF' || r || BLAKE2S-PRF_r(m))

   >the work-factor is pretty plausible.

   Good point. But doesn't that imply the ability to create collisions in H()
   at will?

No, just the ability to find a message whose hash's first few bytes
are the same as the first few bytes of a valid CRL message.  If you
want to specify n bits exactly, it takes 2^n tries on average.

---

From: Alyssa Rowan <[email-masked]>
Date: Sat, 20 Jun 2015 00:02:25 +0100

On 2015-06-19 21:46, Alexey Melnikov wrote:

> Just a reminder that CFRG is not trying to rubber-stamp any 
> particular signature algorithm.

Naturally, I'm just saying: the further we diverge from something
people already recognise as good, the more we'll need make sure to
justify that divergence to scrutiny, or they might not want to use it.

On 2015-06-19 19:04, Blumenthal, Uri - 0553 - MITLL wrote:
> it is much more *usable* and *practical* that EdDSA(m).

Of course the TLS WG, as implementers, get the last word on what is
usable and practical for them.

I was simply pointing out that OpenSSH have deployed EdDSA(m) with
absolutely no troubles, and so have GnuPG, which have large messages.
It worked for them, so I don't think it's a huge concern in practice?

But I also accept #1 is easier to shoe-horn into, say, PKCS#11, and
agl's articulated the precise scenario underlying my discomfort with #3.

- -- 
/akr

---

From: Andrey Jivsov <[email-masked]>
Date: Fri, 19 Jun 2015 16:13:07 -0700

On 06/19/2015 04:02 PM, Alyssa Rowan wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
>

No, OpenPGP uses EdDSA(H(m)) only, i.e. it relies on IUF and doesn't use 
the "high security" option, I believe exactly to avoid "troubles".

http://www.ietf.org/mail-archive/web/cfrg/current/msg06923.html

...

---

From: Taylor R Campbell <[email-masked]>
Date: Fri, 19 Jun 2015 23:15:12 +0000

Date: Sat, 20 Jun 2015 00:02:25 +0100
   From: Alyssa Rowan <[email-masked]>

For the record: GnuPG deployed EdDSA(H(m)), not EdDSA(m), because
every signature in OpenPGP takes the form Sign(H(m)) for some hash
function H which may vary from message to message according to user
preferences.

(This is not to say that OpenPGP's approach is a good idea.  Not much
has changed in it in the two decades since it was first designed, in
spite of two decades of advances in cryptography engineering.  Should
the CFRG recommend that new protocols ignore decades of advances and
experience from practical attacks in the wild, in favour of remaining
stuck in the cryptography engineering practices of 1995?)

---

From: Dan Brown <[email-masked]>
Date: Sat, 20 Jun 2015 00:38:35 +0000

So, if we're stuck with deterministic + IUF, maybe we can do reverse Schnorr, with the point being suffixes to the message instead of prefixed, and then rely on wide pipe hash without any extension‎ properties, etc., which is slightly than a simple hash (or is it?).

Sent from my BlackBerry 10 smartphone on the Rogers network.
  Original Message
From: Paterson, Kenny
Sent: Friday, June 19, 2015 6:08 PM
To: Tony Arcieri; Blumenthal, Uri - 0553 - MITLL
Cc: [email-masked]
Subject: Re: [Cfrg] Summary of the poll: Elliptic Curves - signature scheme: friendliness to low memory implementations (ends on June 3rd)

Folks,

Cheers

Kenny

---

From: Stephen Farrell <[email-masked]>
Date: Sat, 20 Jun 2015 03:23:37 +0100

A clarification...

> wants the signature issue to be settled in CFRG first.

Yes, that's how I want to see things go, for fairly the obvious
reason that other outcomes will cause confusion at least.

However, if there is IETF consensus for something else (e.g. if the
TLS WG did prefer something different to the CFRG outcome, and if
that consensus was maintained through an IETF last call) then my
preferences would not matter.

S.