Subject: [Cfrg] Signature proposal

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 22 Jun 2015 15:23:21 +0300

[This is an abridged version of more extended spec I'm working on,
omitting generation of a and seed, couponing and some more extended
security/design discussion.]

Asumptions made:
- p is prime.
- E is (twisted) Edwards curve over GF(p).[1]
- l is prime at least 2^200.5
- B is point on E with order l.
- LEB128(x) is unsigned LEB128 encoding of integer x.
- len(x) is length of octet string x in octets.
- ceil(x) is the smallest integer at least x.
- H(x) is hash function with output at least 64 bits longer than number
  of bits in l (or for curves not near power of two order, also at least
  5/4 of bits of l, whichever is greater) [3].
  - For Curve25519, minimum is (bit under) 320 bits, for Curve448, minimum
   is (bit under) 512 bits  (both curves are near power of two order).
- PH(x) is collision-resistant hash function of at least 200-bit output[2]
  or identity function. The protocol using negotiates or specifies.
- LSB(x) is the least significant bit of x.
- tointeger(x) reads octet string x as little-endian base-256 integer.

Points are converted into octet strings as little-endian encoding (with
ceil((p_bits+1)/8) octets) of LSB(x)*2^p_bits+y, where p_bits is the
number of bits in p (e.g. 255 for curves based on Curve25519 and 448
for curves based on Curve448).

Scalars (integers mod l) are converted into octet strings as little-
endian encoding (with ceil(l_bits/8) octets, where l_bits is the number
of bits in l).

Private key consists of:
- E (curve)
- H(x) (function)
- seed (octets)
- a  (scalar)

And public key:
- E (curve)
- H(x) (function)
- A=aB (point)

Signing:
========
Inputs:
- key: private key (E and H(x) are contained within)
- hash_id: If PH(x) is identity, this is empty string. Otherwise it is
  ASN.1 DER-encoded X.509 AlgorithmIdentifier for PH(x) (with omitted
  optional parameters encoded as ASN.1 NULL).
  - E.g. SHA-256 is 30 0d 06 09 60 86 48 01 65 03 04 02 01 05 00
    (15 octets).
  - E.g. Blake2b-256 is 30 0f 06 0b 2b 06 01 04 01 8d 3a 0c 02 01 20
    05 00 (17 octets).
- context: Context string (specified by protocol, default is empty
  string).
- message: The message to sign.

Let M' be concatenation of:
- LEB128(len(hash_id))
- hash_id
- LEB128(len(context))
- context
- LEB128(len(PH(message)))
- PH(message)

Let r_tmp be concatenation of:
- Octet 0x02
- LEB128(len(seed))
- seed
- M'

Let r = tointeger(H(r_tmp)) % l.

Let h_tmp be concatenation of:
- Octet 0x03
- LEB128(ceil((p_bits + 1) / 8))
- encode_point(rB)
- encode_point(aB)
- M'

Let h = tointeger(H(h_tmp)) % l.
Let s = (r - h*a) % l.

Signature is encode_pont(rB) || encode_scalar(s)

Verification:
=============
Inputs:
- key: public key (E and H(x) are contained within)
- hash_id, context, message: As with signing.
- signature: The output of signing.

Let R=rB, s and A=aB be be values decoded from inputs.

Let h be calculated as in sigining (all needed inputs are available)

Check if R = sB+hA. If this holds, signature is valid.

Security notes:
===============
- This is yet another Schnorr variant.
- hash_id is to counter cross-hash attacks (we all know that weak hashes
  should be deimplemented, except this doesn't seem to happen in the
  real world[4]).
- context is to counter cross-protocol attacks (these seem to be an
  issue in real world[5]).
- PH(x) needs to be CR (which identity trivially is). If protocol
  supports it, randomized hashes can be used to weaken this
  requirement.

Design notes:
=============
- The design is heavily based on EdDSA (mainly adds capability to
  operate on more curves, online operation and contexts).
- I made online operation take a raw hash, since most protocols seem
  to operate that way with existing signature functions (not having to
  potentially calculate the same hash multiple ways!).
- Context is not hashed since it should come from executable/firmware
  image and should generally be very short (few dozen octets at most).
- I picked X.509 AlgorithmIdentifier, since most used hashes seem to
  have those. Besides, most of the time the values can just be hardcoded
  in executable/firmware image as octet strings.[6]

[1] The actual requirements are (Edwards curves are an example):
- y is always in GF(p)
- All terms are constant or quadric in x.

(This is needed for point encoding to work).

[2] The 200 bit minimum is mostly there to exclude some crap hash
functions (and also as reasonable strength-matching).

[3] Some curve can need that much for elimination of excessive bias.

[4] E.g. Recently (unstrengthened) MD5 (collisions in seconds) was
found to be still enabled in GnuTLS. Also, all the crap crypto
(RC4, EXPORT(!), etc...) enabled in various TLS servers.

[5] E.g. Recently cross-protocol attack was found in Git push
signatures. And also, intial version of signatures for TLS 1.3 had
cross-protocol attack (both since fixed).

[6] There is IANA registry for hash function names, but it has 7
functions (three are crap and remaining four are the usual SHA-2 stuff)
and is annoying to update (standards track!)

-Ilari

---

From: Dan Brown <[email-masked]>
Date: Mon, 29 Jun 2015 16:09:30 +0000

Hi Ilari,

Your proposal looks like a very detailed and careful version of EdDSA.
Three unrelated comments follow:

1) I still prefer the ECDSA method (from Kravitz's DSA) in which R enters
the computation of s without passing through a hash function (but one can
also add it to the hash function, for double protection).  The direct use of
R provides ECDSA partial protection against the very unlikely risk of very
severe hash failures.

2) In reviewing your detailed specification, I realized something [probably
known already - who do I credit?] that might apply quite generally, i.e. to
other CFRG DL-based signature proposals, including mine.

Some hashes may be defined as a truncation of another hash, if I recall
correctly.  That seems quite bad if both are used to generate ephemeral
secrets in deterministic signatures, because it can introduce a linear
relation between the ephemeral secrets in two signatures, which, I think,
would compromise the signing key. 

I did not fact-check every detail in the attack worry above, but thought the
worry worth sharing because of the risk it would leak the signing key.  If
there's some reason the attack would fail, or there's no such hashes (i.e.
I'm completely misremembering!), then phew, and sorry.   If this really is a
problem, then: perhaps it is well-known (e.g. maybe it's part of EdDSA
paper, which I read and forgot); a countermeasure might be to use yet more
hash identifiers, or fix the hash used in the computation of ephemeral
secrets (or otherwise banning such truncated hashes).

3) Any reason why you allow I=order(B) to be as low as 201 bits?  I did not
think CFRG is considering such curves.

Best regards,

Dan

> -----Original Message-----

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 29 Jun 2015 09:38:12 -0700

> On Jun 29, 2015, at 9:09 AM, Dan Brown <[email-masked]> wrote:
> 
> Hi Ilari,
> 

I believe that this would compromise the signing key, at least if the two hashes
are used with the same curve and the length difference is small.  However, I’m
not aware of any two deployed hash functions where one is a truncation of
another; in particular, SHA512/n have different IVs.  So this would only happen
if you truncate the same hash to two difference lengths, or use a variable-
output-length hash with two different output lengths.

— Mike

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

---

From: Dan Brown <[email-masked]>
Date: Mon, 29 Jun 2015 17:06:04 +0000

> From: Michael Hamburg
[DB] Thanks for checking this.

Also, I did some after-post fact-checking and found that SHA-384 and SHA-224 do indeed use different IVs than SHA-512 and SHA-256.  Sorry for forgetting that crucial fact.

Good catch about the small difference in output length. Yes, I forgot to mention that the attacker has to guess the truncated bits to find a linear relation.  So, truncation from 512 down to 256 would defeat the attack.

I've since noticed that some (old?) versions of HMAC do allow truncation. Because I've suggested trying to avoid extension attacks on prefixed-hashing with SHA-1/2 to generated ephemeral secrets, I will look further into the impact of using HMAC as a PRF for this task.  I think it's just better to go with SHA-3, but an alternative is mandate no truncation to be used in the generation of the ephemeral key.

---

From: David Jacobson <[email-masked]>
Date: Mon, 29 Jun 2015 10:10:10 -0700

>> -----Original Message-----
Check out FIPS 186-4.  It defines SHA-512/224 and SHA-512/256, which are 
SHA-512 truncated to 224 and 256 bits respectively.  And it states, in 
Section 5.3.5 "SHA-512/224 (t = 224) and SHA-512/256 (t = 256) are 
approved hash algorithms."

     --David

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 29 Jun 2015 20:23:03 +0300

> > R provides ECDSA partial protection against the very unlikely risk of very

I most definitely do not want signer to have do any inversions mod order. Those
are slow and just too tempting to do in unsafe way.

> > would compromise the signing key. 

I did run into problems with multiple curves, which is the reason I stuck the
curve into keys (and at the same time stuck the hash too).

Also, the way full proposal (I omitted key generation) generates seed, if the
same hash function is used as for signing, there will be no linear relation,
as seeds will be of different lengths (unless there is only fractional-octet
differnce).

> > secrets (or otherwise banning such truncated hashes).

I think I have seen some hash function that did raw truncation. Not widely
used ones tho.

> output-length hash with two different output lengths.

Also, one would have to use one's own hash function (not the one indicated for
the key) for pseudorandom parameter generation and then have two of those that
are truncated versions of other and use those for the same key.

If one wanted some identifers, one would only need to stick one to generation
of r.

> > think CFRG is considering such curves.

Well, I used the WF100 limit from Safecurves. One could pick higher limit
(I think EdDSA had some quite ridiculously low one).

-Ilari

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 29 Jun 2015 20:25:48 +0300

On Mon, Jun 29, 2015 at 10:10:10AM -0700, David Jacobson wrote:
> Section 5.3.5 "SHA-512/224 (t = 224) and SHA-512/256 (t = 256) are approved
> hash algorithms."

Nope (as said elsewhere in this thread), SHA-512/224 ad SHA-512/256 are not
truncations of SHA-512. The IVs are different.

-Ilari

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Mon, 29 Jun 2015 17:30:50 +0000

>truncations of SHA-512. The IVs are different.

Yes and Yes.  :-)

I.e., yes SHA-384 and SHA-224 *are* truncations of SHA-512 and SHA-256
code-wise, and yes - they *also* do have different Ivs (with the
implication that one *cannot* compute SHA-256 of a blob, truncate the
output to 224 bits and say it is SHA-224 hash of the blob).

---

From: David Jacobson <[email-masked]>
Date: Tue, 30 Jun 2015 09:04:45 -0700

> output to 224 bits and say it is SHA-224 hash of the blob).
Thank you for correcting my error.  FIPS 180-4 says in section 4.2.3 
that the sequence of 80 64 bit words used in the algorithm is the same 
for SHA-384, SHA-512, SHA-512/224, and SHA-512/256. But those words are 
not the initial value.  That is defined in 5.3.6, and indeed depends on 
the truncated size.

    --David