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

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

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.

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. 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.

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.

---

From: Dan Brown <[email-masked]>
Date: Wed, 20 May 2015 22:40:08 +0000

> -----Original Message-----
> From: Alexey Melnikov
> 
the
> message to be signed, thus trivially supporting IUF APIs in
constant-space, at
> the cost of requiring collision resistant hash functions.
> 
cost
> of the signing algorithm having to buffer messages to be signed.
> 
actually
> a hash of the true message.

[DB] #3. 

If the results of our previous poll had been more flexible, then we could
have another option here:

#4: The signature should not depend on collision resistance, and should
adhere to the IUF API in constant space. 

E.g. choose the k value in ECDSA or EC-Schnorr as k = PRF(static_secret,
nonce(time,counter)), or even DRBG, then prepending R=kG to the message
before hashing: e.g. h = HASH(R,message)

Sorry that I forgot to mention this advantage in the previous poll.

---

From: Nico Williams <[email-masked]>
Date: Wed, 20 May 2015 19:00:53 -0500

> actually a hash of the true message.

I'd rather this be cast in terms of online/offline.  The question isn't
how much memory is needed, but whether the amount needed is fixed or
unbounded (e.g., proportional to message length).

Anyways, I think we should do #4, a rephrasing of #3, though I'm open to
all options listed thus far:

#4: provide both online and not-online signature schemes

Users could use an offline scheme in an online way and hash the message
themselves, but it seems best to do it in the scheme itself.

Nico
--

---

From: Adam Langley <[email-masked]>
Date: Wed, 20 May 2015 17:09:44 -0700

> unbounded (e.g., proportional to message length).

I think "online" is what's described in the question as the
"traditional" construction, i.e. operates in constant space. But could
you confirm so that I'm clear?

> themselves, but it seems best to do it in the scheme itself.

How would your #4 differ from #3? Would the signature scheme itself be
different? (As opposed to #3 which imagines a "wrapper" around a
signature scheme.) If so, wouldn't that be a bunch more complexity for
the specification and implementation?

Cheers

AGL

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 20 May 2015 17:27:42 -0700

> actually a hash of the true message.

Unless there's a specific reason why hashing 3 times in the "large message"
mode is "too slow", this seems like the best option to me. It provides a
defense against collisions and aside from the overhead of triple-hashing
should perform similarly in the "large message" case as the bottleneck for
large messages should be computing the digest over the large message, not
hashing hashes.

-- 
Tony Arcieri

---

From: "Jim Schaad" <[email-masked]>
Date: Wed, 20 May 2015 21:44:54 -0700

> From: Cfrg [mailto:[email-masked]] On Behalf Of Alexey Melnikov
> Sent: Wednesday, May 20, 2015 2:16 PM
> To: [email-masked]
> Subject: [Cfrg] Elliptic Curves - signature scheme: friendliness to low
memory
> implementations (ends on June 3rd)
> 
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.
> 
hash
> function that is employed. However, this approach implies that the signing
signing
> arbitrarily large messages invites implementations to process
unauthenticated
> data because of its potential size. 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.
> 
substitute into
> existing protocols then supporting a constant-space IUF API might be seen
as a
> requirement.
the
constant-space, at
cost
actually
> a hash of the true message.

#1 is fine as is #2.

I have no problems with being unfriendly to low memory implementations that
think they want to deal with large messages.  For a signing device, it can
be dealt with by sending the message through it twice and having it compute
both hashes the second time to make sure the same message is given.

Jim

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

---

From: Simon Josefsson <[email-masked]>
Date: Thu, 21 May 2015 11:48:46 +0200

> actually a hash of the true message.

#2: The signature scheme should not depend on collision resistance.

The part "at the cost of the signing algorithm having to buffer messages
to be signed" appears like speculation to me, and I disagree with it.

The majority of use-cases I am aware of sign short messages.

The use-cases that sign large messages I am aware of are those that sign
offline files.  The OpenPGP EdDSA draft already deals with this issue --
see https://tools.ietf.org/html/draft-koch-eddsa-for-openpgp-02 -- since
the OpenPGP framework essentially already provide the #3 "large message
mode".  S/MIME can do the same.  I cannot recall other significant
"large file" signing frameworks.

Thus, I don't think the CFRG has to solve the "large message" problem,
at least not until some other technology requests that from us.  OpenPGP
has already solved it.  Solving problems before they exist is rarely a
good idea.

The "large message" concern and the "low memory" concern are really two
different problems, and they don't necessarily have the same solution.
Thus, I'd like to comment on your text that leads up to the question:

> 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.

I don't agree with this.  The signing implementation does not have to
buffer the entire message.  There are several ways to solve this:

1) The application could hash the message before signing, using a
traditional hash like SHA256.  Then the signature scheme itself does not
rely on collision resistance, and the signing algorithm does not have to
do buffering.

2) The signing algorithm could have a different API and put the burden
on the caller to deal with this aspect.  By changing how the API looks
and how the application works, it is possible to avoid buffering the
entire message -- for example the application could seek through the
data stream twice when doing the signature.

Still, I believe this is a moot issue since any high-level application
that has the "large message" concern will solve this like OpenPGP does.

/Simon

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 21 May 2015 12:22:55 +0000

Alexey Melnikov <[email-masked]> writes:

>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.

It's also pretty much an instant fail for any API-based security toolkit that
implements streaming/staged message processing via the init/update/final
model, which seems to be pretty much all of them (using PKCS #11 as a
representative example, you've got "begin", "update", "update", [...], "end",
which hardcodes a single pass over the data, OpenSSL does the same thing, as
does CryptoAPI, Java (JCE/Bouncy Castle/whatever), my own cryptlib, and I'd
guess most other libraries).

>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. 

In most cases where you're processing large messages you don't have any
choice, and the signing is often done for things like accounting purposes
rather than because the devices involved are trying to enter into a legal
agreement.  For example medical images, which have to be uncompressed in order
to avoid introducing compression artefacts, are enormous, streamed out to a
remote system in a single pass, and signed purely for accounting/bookkeeping
purposes.  So you've got something where you absolutely need one-pass
processing, and the app/users couldn't care less about any fancy properties
that two-pass processing provides.

>#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.

+1.  Without having done a survey of all implementers, I do however get the
feeling that this is the only option available for practical use, meaning the
choice would be to either go with this option or have whatever other option
you select ignored because it's impractical for general use.

Peter.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 21 May 2015 14:03:28 +0000

+1

----- Original Message -----
From: Peter Gutmann [mailto:[email-masked]]
Sent: Thursday, May 21, 2015 08:22 AM
To: Alexey Melnikov <[email-masked]>; [email-masked] <[email-masked]>
Subject: Re: [Cfrg] Elliptic Curves - signature scheme: friendliness to low memory implementations (ends on June 3rd)

Peter.

---

From: Mike Hamburg <[email-masked]>
Date: Thu, 21 May 2015 07:57:40 -0700

#1 or #3.  It's important to support IUF APIs in practice.

---

From: Laurens Van Houtven <[email-masked]>
Date: Thu, 21 May 2015 08:41:34 -0700

Picking 1: #1. In order of preference: #1, #3, #2.

#2, for reasons already elucidated, is a non-starter. A collision-resistance constraint is nowhere near as painful as a one-shot constraint. #3 solves that, but at the expense of additional complexity.

lvh

> On May 20, 2015, at 2:16 PM, Alexey Melnikov <[email-masked]> wrote:
>

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 21 May 2015 19:52:17 +0300

On Thu, May 21, 2015 at 08:41:34AM -0700, Laurens Van Houtven wrote:
> #2, for reasons already elucidated, is a non-starter. A collision-resistance
> constraint is nowhere near as painful as a one-shot constraint. #3 solves
> that, but at the expense of additional complexity.

"Traditional model" already introduces a fair bit of the complexity. The
problem is that protocol may very well have a preference on "inner" hash,
but that hash is unsuitable for "outer" hash, due to insufficient length.

For example, let's take TLS 1.2 CertificateVerify message[1]. It signs
potentially lengthy data. But it just so happens that TLS 1.2 keeps running
hash of just that data, using so called "prf-hash" (which happens to be
also need to be CR).

So, the TLS 1.2 endpoint would very much prefer to use prf-hash as "inner"
hash. The problem is, that prf-hash is probably SHA-256, which has
insufficient output length. Or if it isn't SHA-256, it is probably SHA-384,
which doesn't work too well for 448-bit signatures.

One would probably want to have separation between hashes. One way would
be to stick an algorithm identifier[2]. Presumably there then could be
algorithm identifier for identity transform, which would then give #3
with very little additional complexity.

Of course, protocols would then get the fun of negotiating the mess...

If one wanted to add contexts to this[3], contexts would then appear only
in outer hash (in both generation of R and in final hash). Contexts are
short and should be pulled out of executable/firmware image anyway, so
no need to support IUF for those.

[1] This does not apply to TLS 1.3 current draft, where amount of data
to sign is always small. Also, TLS 1.2 ServerKeyExchange message signs
reasonable amount of data.

[2] Whatever the identifer, it needs to be handled as a blob.

[3] Contexts are meant to prevent cross-protocol attacks (those seem to
be common). The contexts must match on both sides, or signature fails to
verify.

-Ilari

---

From: Nico Williams <[email-masked]>
Date: Thu, 21 May 2015 15:14:45 -0500

> guess most other libraries).

I hate to agree with this, but this is just too common an API pattern.
The assumption of online signing is quite pervasive; an off-line-only
signature scheme might have a hard time getting traction.

> you select ignored because it's impractical for general use.

#3 wouldn't hurt.  From an API perspective #3 is best seen as *two*
signature schemes (with different OIDs), one of which is incompatible
with online signature APIs.

I'd certainly like to have both.  Protocols like TLS and PKIX should use
the off-line signature scheme when the implementor can manage it, as it
would be the preferred scheme.  Pretty much all apps using existing
crypto frameworks (generic APIs parametrized by algorithm ID) would get
the online version.

Nico
--

---

From: Watson Ladd <[email-masked]>
Date: Thu, 21 May 2015 18:49:32 -0400

> crypto frameworks (generic APIs parametrized by algorithm ID) would get

On the contrary, 3 would hurt unless properly designed. The danger is
that the same key could produce a valid signature under two different
algorithms, thus leading to potential exploitation. We would need to
ensure there are no collisions in what is fed into the signing
algorithm.

It seems as though determinism, one pass schemes, and avoiding
collision resistance are at odds, unfortunately, unless someone comes
up with a good idea.

Sincerely,
Watson Ladd

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

---

From: Tony Arcieri <[email-masked]>
Date: Thu, 21 May 2015 19:17:48 -0700

On Thu, May 21, 2015 at 3:49 PM, Watson Ladd <[email-masked]> wrote:

> algorithms, thus leading to potential exploitation.

Something that strikes me as a bit strange is if we do hash the input prior
to feeding it into #2, doesn't that defeat the point? Collisions in the
first hash are still collisions. So wouldn't any collision in the hash
function undo any collision-resistance that #2 provides? Am I missing
something here?

How about option #5(?): provide both #1 + #2. Implementation-wise you could
share the overwhelming majority of the code between both interfaces. The
difference between them seems trivial enough that providing both should be
easy. And to Watson's point, if we do it that way there shouldn't be any
chance of confusing the two as they should produce completely distinct
signatures.

#2 seems very nice for the TLS use case, especially as we've seen
collisions in older hash functions being used in real-world attacks against
TLS (e.g. Flame). I'm not saying I expect to see collisions in SHA-256 any
time soon, but I would hate to see #2 rendered unavailable because we can't
otherwise meet the requirements of low-memory devices signing large amounts
of data (FWIW, I think in most real-world use cases in those environments
the data is always going to be hashed in advance, probably by another
computer which actually has the memory to compute the hash)

-- 
Tony Arcieri

---

From: Nico Williams <[email-masked]>
Date: Fri, 22 May 2015 00:25:57 -0500

> ensure there are no collisions in what is fed into the signing

On the counter-contrary :) if we don't do #3 and only provide an
off-line signature scheme, then some users will *sometimes* sign a hash
of long messages, leaving us with the problem you point out.  But worse:
then we really can't address this in the signature scheme.

Or we could provide an online signature scheme only, and decidedly give
up collision resistance.

By providing both functions we can ensure that one private key for both
begets distinct sub-keys for each -- more hygienic key usage.

Mind you, the key hygiene argument seems unlikely here: the attacker
still has to produce a collision for a hash input they do not entirely
control (particularly the prefix).

> collision resistance are at odds, unfortunately, unless someone comes

Agreed.

My ranking from most desirable to easiest to give up is: determinism,
online, collision resistance.  But I admit uneasiness in giving up
collision resistance, but with #3 we can get the right mix of features
on an app-by-app basis.

#3 does mean making the user choose -- a higher cognitive load than we
would prefer to place on them.

Nico
--

---

From: "D. J. Bernstein" <[email-masked]>
Date: 22 May 2015 09:29:59 -0000

Watson Ladd writes:
> collision resistance are at odds, unfortunately

Probably one can split a message into

   * packet p0 plus a signature s0 of ("start",p0);
   * packet p1 plus a signature s1 of ("middle",s0,p1);
   * packet p2 plus a signature s2 of ("middle",s1,p2);
   * ...;
   * last packet pn plus a signature of ("end",previous s,pn).

I'm saying "probably" because this sort of thing needs formal security
analysis. But it's known how to do this sort of analysis, either
producing an attack or producing a convincing proof of security.

This is deterministic. It's resilient to collisions in the underlying
hash function. It's one-pass. Most importantly, it allows a one-pass
verifier to immediately reject any forged packet. The attacker can
truncate at any point---and sometimes this by itself is a big problem,
inherent in the concept of streaming, worse than having no message at
all---but (assuming the security analysis works) the attacker can't
forge any packets.

On the other hand, since the fans of streaming crypto interfaces have a
long history of building "verification" software and hardware that
blithely spews out forged packets directly from the attacker into other
components that can't handle it, I'm not sure what exactly is being
accomplished by providing a cryptographic algorithm that _can_ remove
all forged packets. Is the cryptographic user supposed to suddenly start
trusting these interfaces?

What _definitely_ improves security is switching to the much more robust
world of all-in-one crypto interfaces. In this world streamability is
clearly a bad idea: it provides no benefit, and trying to secure it
creates a serious cost in simplicity (not to mention performance).

More to the point, it's clear that these decisions should be made at a
layer above the basic signature algorithm. The basic algorithm---the
algorithm that everyone should use by default---should not allow
security and simplicity to be corrupted by the pursuit of streaming.

---Dan

---

From: Dan Brown <[email-masked]>
Date: Fri, 22 May 2015 14:20:21 +0000

> From: D. J. Bernstein

That's quite interesting!

---

I interpreted the chairs' #3 proposal to be something like this:

final_signature(m) 
= 
"0"|raw_signature("1pass", hash(message))
 or
"1"|raw-signature("2pass", message)
                    
The initial bit can be conveyed within the signature, or in the signer's
certificate if the signer is going to stick to one mode.

---

The goal of avoiding collision resistance seems worthwhile: at least, it
does when I think of MD5.

To reduce the reliance on collision-resistance in the 1pass case, the signer
can serialize the message, which we can codify, as in the example below.  

---

During initialization of the signature, the signer selects an unpredictable
value, such as

serializer=PRF(serializer_key, time | counter) 

The signer prepends serializer to the message, and then proceeds to sign as
usual.  

The signer either makes sure that every message it signs is serialized, or
else embeds an initial bit indicator prefix into the message to distinguish
between serialized and non-serialized signatures.

The verifier treats the serializer as part of the message, and does nothing
differently, except ignore the serializer.

The message suffers from some expansion, but the signature does not.  

The signature is still a deterministic function of the serialized message:
the signer has not touched any secret in the log space of the discrete
group, so we needn't worry about the usual repeated-ephemerals or
leak-and-lattice attacks, etc.

If the signer fails to implement the message serialization correctly, then
collision resistance is again needed, but not much else goes wrong.

---

Message serialization should not be confused with the signature's internal
ephemeral key/per-message secret/secret nonce, hence I've used a different
term.

---

From: "Salz, Rich" <[email-masked]>
Date: Fri, 22 May 2015 15:26:54 +0000

> ...this is just too common an API pattern.
> The assumption of online signing is quite pervasive; an off-line-only signature
> scheme might have a hard time getting traction.

+1

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 22 May 2015 18:48:36 +0300

> function undo any collision-resistance that #2 provides? Am I missing

Yeah, collisions in first hash cause signature collisions.
 
> chance of confusing the two as they should produce completely distinct

Add input for hash domain (with special value for "identity"):
- This is not hashed.
- This is SHA-256 output
- This is SHA-384 output
- This is SHA-512 output
- This is Blake2b-512 output
...
?

That also prevents mismatching hashes between signer and verifier.

Also, I thought that was #3 (can choose between online and offline)?

> computer which actually has the memory to compute the hash)

The only signature in TLS (including TLS 1.3 as of editor's copy) that is
actually over nontrival amount of data is TLS 1.0-1.2 Client certificate
verify.

And if the PRF-hash in TLS is not CR, one gets problems...

-Ilari

---

From: Nico Williams <[email-masked]>
Date: Fri, 22 May 2015 12:31:20 -0500

>    * last packet pn plus a signature of ("end",previous s,pn).

Say you're signing code.  Now you have to distribute O(N) additional
signatures, where N is the size of the message.  That's doable.  But to
verify in an online way as code is downloaded requires interspersing the
signatures with the code.  Which means new file formats (or new
protocols).

Say you're signing a large e-mail...  Now we'd need new message formats.

The point is that we're quite accustomed to online signature functions.
We *could* do without, but it will probably take a lot time and work to
get to where we're using deterministic, off-line, collision-resistant
signature schemes.

Which is why I see #3 as a reasonable compromise: we get a
deterministic, online scheme now that fits existing APIs and message
formats, and a deterministic off-line scheme that gives us collision
resistance and which will take time to get adopted.

> [...]

Being pragmatic about this does not make one a "fan".

Mind you, streaming is a very good thing, and not just in crypto,
because predictable state costs are very useful in engineering...

> creates a serious cost in simplicity (not to mention performance).

Agreed.  But we won't get there overnight.  And if we can retrofit
deterministic signature schemes into existing APIs and protocols at low
cost, why wouldn't we?

> security and simplicity to be corrupted by the pursuit of streaming.

That layer is also above CFRG.  All the more reason to give that layer
the tools they need to make the right choices and get deployment sooner
rather than later.

Practical considerations intrude.  That's terrible, but when you're
rebuilding an airplane mid-flight, practical considerations matter.
(With apologies to whoever I stole that analogy from; IIRC I first heard
it from Bill Sommerfeld.)

Nico
--

---

From: "D. J. Bernstein" <[email-masked]>
Date: 23 May 2015 00:41:31 -0000

In crypto there's a long history of bad API designs (in most cases
allegedly motivated by performance) producing neverending security
disasters. Streaming verification APIs are a perfect example: again and
again we see callers spitting out unverified data directly into software
that can't handle it, because that's the simplest way to use the APIs.

How long are the messages that are actually signed in IETF protocols?
For the protocols where the answer is uncontrolled: Do implementations
allow messages that don't fit into memory? How do those implementations
avoid passing along unverified data? For PGP we know that the answer is
"They do pass along unverified data, and this is a security nightmare."

There are other protocols that don't naturally trigger this problem---
they keep lengths under control, and implementations have no trouble
fitting messages into memory. These implementations should be encouraged
to use a simple, high-security, all-in-one verification API, and the
protocols should be encouraged to use a simple, high-security,
all-in-one signature system.

Nico Williams writes:
> Practical considerations intrude.

Specifying a simple, high-security, all-in-one, deterministic,
collision-resilient signature system doesn't stop higher-level protocols
from deciding to use this core system to sign hashes of messages, with
the obvious consequences. (It also doesn't stop them from using the core
system to sign individual packets, as outlined in my previous message,
with obvious performance effects and _hopefully_ no security impact; as
I said before, formal security analysis is needed.)

The core system should nevertheless be the default: the signature system
that's applied directly to messages in all the situations where
compromise isn't necessary.

> because predictable state costs are very useful in engineering...

If a tiny device is capable of doing the job in one pass, great---but
engineers don't say "You want to sort a gigantic file? Inconceivable!"
Most user-visible computing tasks work with large amounts of data in
ways that simply don't fit a tiny-memory single-pass streaming model.
(Much more is possible with multiple passes.)

What's particularly vicious about the verification example is that at
first glance the job _seems_ to fit a streaming model, but doing the job
_securely_ does _not_ fit a streaming model (unless the algorithm signs
separate packets---which, as you note, is incompatible with the common
practice of giving users separate "signatures"; it requires that the
data flow work with "signed messages", as in the NaCl API). So people
provide streaming APIs for verification, and security disintegrates.

---Dan

---

From: Ilari Liusvaara <[email-masked]>
Date: Sat, 23 May 2015 08:46:27 +0300

> "They do pass along unverified data, and this is a security nightmare."

I didn't quickly find list of IETF security protocols, but the only ones
that come to mind that would need to handle "large" (potentially too much
to store in memory) amounts of data are OpenPGP and CMS.

Then some places deal with "medium" (annoying to store in memory) amounts
of data, like TLS 1.0-1.2 client signatures and possibly something in
IPSec (looked briefly at the RFC, can't quickly estimate the amount of
data).

Most of the rest should be "small" (small amounts of data, highly
transient).

The places that sign "medium" amount of data usually also fundamentially
break the "signed message" model.

Finally, it should be noted that most of the security stuff in IETF
protocols assume that signatures are "deteched" (TLS syntax even
has a "macro" for that), and will not work with "sealed" signatures.

-Ilari

---

From: David Leon Gil <[email-masked]>
Date: Tue, 26 May 2015 17:32:49 +0000

> protocols assume that signatures are "deteched" (TLS
> syntax even has a "macro" for that), and will not work with
> "sealed" signatures.

I'm curious what the issue is here? (Maybe I don't understand what you mean
by "sealed"...)

I'm also not sure why bad decisions from the past should be left
uncorrected: a history, however long, of poor design choices is not a
*reason* to continue to make them.

- dlg
On Fri, May 22, 2015 at 10:46 PM Ilari Liusvaara <

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 26 May 2015 20:48:07 +0300

> I'm curious what the issue is here? (Maybe I don't understand what you mean

"Detached" signatures:
Sign: PrivKey x Message -> Signature
Verify: PubKey x Message x Signature -> Good or Bad.

(This is the usual mode)

"Sealed" signatures:
Sign: Privkey x Message -> Signed message
sign_open: Pubkey x Signed message -> Message or Bad.

(This is mostly seen in NaCl library[1])

> *reason* to continue to make them.

The problem is that trying to "fix" things like TLS to work would
be pretty nasty, given that those protocols were designed to use
"detached" signatures.

[1] I think the stock one offers just this, and most clones have
both this and ordinary "detached" ones).

-Ilari

---

From: Nico Williams <[email-masked]>
Date: Tue, 26 May 2015 14:09:33 -0500

I had been concerned with the signing side in my earlier posts.  I agree
that the verification side cannot be online regardless.  An online
signer can be useful because of HSMs and such.

> How long are the messages that are actually signed in IETF protocols?

There are at least two cases where online signatures are useful:

 - when signing bulk data (e.g., CMS, PGP);

 - when signing a communication transcript of more than two consecutive
   messages and the service needs to be stateless, putting the state in
   an encrypted state cookie.

   (A good example here is Kerberos KDC exchanges.)

In the latter the state cookie's size grows as the exchange grows.  (I'm
not sure that this is actually a problem, or that it will be.)

> allow messages that don't fit into memory? How do those implementations

It's not just memory, but I/O and performance, as well as interface
design considerations.

Signing a file can be done with much less memory than the file's size,
reading a block at a time and reading the file twice (in the case of
EdDSA).

Someone mentioned HSMs, for example.  An HSM interface to support
off-line signatures like EdDSA would require passing the message to the
HSM twice when the message doesn't fit in the HSM's memory.

It's also not just IETF protocols of today.  Imagine a filesystem where
there's a "commit" operation and where files are signed by the last
writer...  Random access writes go out the window with an off-line
signature scheme unless we're using something like a Merkle signature
tree.  You proposed something like that earlier, and pointed out that
we'd need security proofs.  Intuitively a Merkle tree of signatures
should work.  (Filesystems effectively implement a tree, and filesystems
like ZFS implement a Merkle hash tree, so a Merkle signature tree would
fit right in.)

> "They do pass along unverified data, and this is a security nightmare."

No matter what, complete signature verification must be required prior
to processing the signed data.  This means that verification is never
online.  I was only concerned with the signing side in my previous
messages.

The verifier side is easier than the signer side in that at least we
don't have to worry about HSMs.

> all-in-one signature system.

Yes.

Nico
--

---

From: Andrey Jivsov <[email-masked]>
Date: Tue, 26 May 2015 12:39:24 -0700

> actually a hash of the true message.

What if M'=HMAC( K, M ) gets signed, where M is the input message, K is 
some derivation of the signing key, and size(M') is collision-resistant 
size (e.g. it's HMAC-SHA-256 for Curve25519)? For example, for EdDSA one 
would feed M' into its hash-twice method, not M or Hash(M).

This means that the hash size will need to be matched with the double of 
the equivalent symmetric bit length, but this is a well-accepted assumption.

This maintains the benefit of the IUF. The practical benefit of this 
method is that the attacker doesn't get to play with two arbitrary M1 
and M2 of his choice hoping to find a collision. The attacker must use 
the signer as an oracle.

I believe that the above idea can be tweaked to maintain IUF (perhaps 
change the HMAC, save a few hashings, etc...).

I vote for #1, and if not #1, then #3,

How can a protocol that uses smartcards in untrusted environments, a 
protocols without hard limit of message size, adopt #2 (see the attack 
in http://www.ietf.org/mail-archive/web/cfrg/current/msg06759.html ) ? 
This likely means that TLS is out, due to smartcard client 
authentication. I can see that #2 is helpful in X.509 certificates, but 
#1 with a tweak is an improvement that might be acceptable.

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.

---

From: Simon Josefsson <[email-masked]>
Date: Thu, 28 May 2015 21:32:27 +0200

> to store in memory) amounts of data are OpenPGP and CMS.

Yes -- and OpenPGP has already solved this issue for EdDSA:
https://tools.ietf.org/html/draft-koch-eddsa-for-openpgp-02
I'm sure CMS could use a similar approach.

I believe the stream issue is a red herring.  There are no applications
or protocols waiting for CFRG to recommend a better digital signature
algorithm that supports streaming.

/Simon

---

From: Tony Arcieri <[email-masked]>
Date: Thu, 28 May 2015 19:45:18 -0700

> cost of the signing algorithm having to buffer messages to be signed.

I'll restate my vote again for clarity:

I vote for both #2 with #1 as a fallback, with the caveat is that I think
#1 is of waning usefulness. I'm sure some will cite the IoT use case, but I
think the constant-space requirement will generally go away as technology
improves.

For the TLS use case, I think both can be supported:

- TLS servers obtain certificates that use both algorithms, or servers that
don't care about supporting "tiny" clients can forego #1. I am guessing #2
is sufficient for most use cases
- "Tiny" clients can specify in their ClientHello that they only support
#1, and servers can respond with a cert signed using #1. These clients
forego collision resistance

I think most devices that "matter" (sorry if I'm being too judgmental here)
should be capable of #2

-- 
Tony Arcieri

---

From: Simon Josefsson <[email-masked]>
Date: Fri, 29 May 2015 21:49:11 +0200

> 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.

/Simon