Subject: Re: [Cfrg] Signature proposal (quick-and-dirty additional material)

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 2 Jul 2015 21:29:51 +0300

Here is some very quick-and dirty material about the algorithm
(in presentation-like form, covering some of the design choices):

EdDSA:
======
- Advanced digital signature primitive, encompassing lots of
  improvements to the original ElGamal scheme.
- Free of inversions mod order.

EdDSA is an advanced signature primitive, having undergone
lots of improvements since the original ElGamal scheme.

EdDSA is also free of inversions mod order. Those are
annoying to implement and slow, especially if one is to
do those in way not vulernable to timing attacks.

Why not EdDSA:
==============
- EdDSA does not support IUF (which is REQUIRED).
- EdDSA has requirements for curves Curve448 won't meet.
- EdDSA requires exotic hashes at >255 bits.

Unfortunately, EdDSA won't do for three reasons:

Firstly, IUF was requirement, and EdDSA doesn't do that.

Secondly, EdDSA has rather severe curve requirements,
making Curve25519 effectively the only curve it is usable
on.

Thirdly, EdDSA needs double-width hash, which means more
than 512 bits if curve is more than 255 bits. And normal
hashes cap at 512 bits.

Modifications from EdDSA:
=========================
- Drop most restrictions on curve.
- Modify seed/a generation.
- IUF via prehashing
- Hash firewalling
- Add contexts

So EdDSA has to be modified in multiple ways...

Drop most restrictions on curve:
================================
- Modify point encoding, allowing (twisted) edwards curves
  over prime fields.
- Plus some size restrictions for security.

By modifying point encoding, one can allow pretty much arbitrary
(twisted) edwards curves over prime fields.

Also, some size restrictions are set for security.

Modify seed/a generation:
=========================
- Modify seed/a generation from private key material.
  - So that exotic hashes are not needed.
- seed and a are generated separatedly, instead of just hashing
  once and splitting.

By modifying generation of seed for pseudorandom parameter and
logarithm of public key, one can get rid of double-width hash.

Specifically, generate those parts separatedly instead of at
once and splitting. Then one only needs enough hash width to
generate unbiased pseudorandom parameter.

IUF via prehashing:
===================
- Some protocols seem to prefer to sign hashes.
  - E.g. TLS 1.2 CertificateVerify.
- Some protocols have hash preferences.
  - E.g. PRF-hash for TLS 1.2 CV.
- Avoids need to know signing key beforehand.

IUF is added via hashing the message before signing. It seems like
some protocols like to sign hashes, and sometimes with certain
hashes.

E.g. TLS 1.2. CertificateVerify, which also prefers PRF-hash
(which depends on TLS ciphersuite).

Also, one avoids problems from having to know the signing key before
one starts hashing for signature.

Hash firewalling:
=================
- Weak hashes seem to be perennial problem.
- More severe problems would arise from mixing up unhashed input
  (somebody is probably going to do that) and hashed input.
- -> Add indication of hash function used.

Weak hashes seem to be persistent problem. Yes, those should be
deimplemented, except that doesn't seem to happen as fast as we
would like.

Additionally, because the primitive takes unbounded amount of
input, somebody is probably going to try to stick the message there,
which tends to cause rather bad problems unless that is indicated.

So indicate the prehash used.

Add contexts:
=============
- Another perennial problem is cross-protocol attacks.
- Difficult to avoid in-band
- -> Add indication of context which both sides have to agree on.
  - Designated by protocol.

Another persistent, but much more obscure problem is using messages
from one protocol to attack another.

It is very difficult to design messages so that some other protocol
won't interpret those in bad ways.

A way to solve this would be to add input, designated by the protocol
signer and verifier must agree on for verification to succeed.

Other approaches:
=================
- Double-pipe v|m, m|rB.
  - Requires signer to pick key beforehand.
- Forking: m|pad|v, m|pad|rB.
  - Is this even secure?
  - Pad has to be picked carefully.
  - Needs somewhat non-standard hash interface.

Two other appoaches were either proposed or came into mind:

Firstly, double pipe construction where hash is run twice, with seed
at front of one of the hashes. This has properties of needing to
compute hash twice, which might be bit slow and that signer needs
to pick signing key at beginning.

Secondly, one could hash message, some padding material, possibly
containing lengths, then fork the context and add seed and point
encoding. No idea if this is secure or not, and even if could be
secure, one probably would have to be careful with pad construction.
Also, this needs somewhat non-standard hash interface.

-Ilari

---

From: Deirdre Connolly <[email-masked]>
Date: Mon, 13 Jul 2015 12:39:34 -0400

...
> making Curve25519 effectively the only curve it is usable
Following these points up with Bernstein, Lange et al.'s paper
<https://eprint.iacr.org/2015/677.pdf> on applying EdDSA to more curves
over finite fields with any odd *q*, not just where *q *mod 4 = 1,
including examples using Ed41417, Ed448, and Ed521.

On Thu, Jul 2, 2015 at 2:30 PM Ilari Liusvaara <[email-masked]>
wrote:

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

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 13 Jul 2015 21:23:30 +0300

> including examples using Ed41417, Ed448, and Ed521.

The message I sent was from July 2nd, which was before I saw the
EdDSA update (or indeed before the EdDSA update was posted, which
was apparently July 4th).

When makign a presentation out of the info in that post, I did
include the fact that there was relevant EdDSA update.

-Ilari

---

From: Deirdre Connolly <[email-masked]>
Date: Mon, 13 Jul 2015 14:41:50 -0400

> include the fact that there was relevant EdDSA update.
Great, thank you.

---

From: Tony Arcieri <[email-masked]>
Date: Mon, 13 Jul 2015 13:34:12 -0700

> including examples using Ed41417, Ed448, and Ed521.

The main point of contention with this paper seems to be the requirement
for a custom SHA-512 IV, which is difficult for anyone working with either
fixed-function devices or codebases where the IV is not parameterized
already.

To implement the algorithm described in the paper, implementations may need
to ship a custom version of SHA-512, which is considered undesirable by
many.

If this were addressed, I think this approach would be more highly favored.

-- 
Tony Arcieri

---

From: Ilari Liusvaara <[email-masked]>
Date: Sun, 19 Jul 2015 20:00:07 +0300

And here's the previous material in presentation form after some
substantial editing (9th version[1]).

Notes formatted something resembling a presentation speech are
included.

[1] I like to keep version numbers internally consistent, even
if that means apparently skipping lots of versions.

-Ilari