Subject: [Cfrg] ECDSA_CFRG details

From: Dan Brown <[email-masked]>
Date: Mon, 20 Jul 2015 16:17:59 +0000

Dear CFRG,

Further detail about my ECDSA_CFRG proposal,

a high-level pseudocode,
hash choice,
pseudorandom function,
conversion of points to integers,
backwards/forwards (non-)inter-operation with ECDSA,

follows below.

(1) High-level pseudocode
=========================

The pseudocode consists of two C++-like files.  This pseudocode
assumes some functions that convert between various types of objects.
I will describe some of these functions further below.

Proviso: I have not run, or tested, this pseudocode.  If it has
errors, e.g. due to my typos, then these are overruled by the math in
my earlier description of ECDSA_CFRG.

////////////////////////////////////////////////////
// File ecdsa_cfrg_spec.cpp
// ECDSA_CFRG pseudocode spec only: not for real use
# include "ecdsa_cfrg.hh"
# define VERIFY verify // verify_via_ecdsa

static bool verify (point Q, bits M, ecdsa sig)
{
return sig.r == f((hash(M)*G + sig.r*Q) / sig.s) ;
}

static bool verify (point Q, bits M, ecdsa_cfrg sig)
{
return sig.s*sig.R == hash(M||sig.R)*G + f(sig.R)*Q ;
}

static bool verify_via_ecdsa (point Q, bits M, ecdsa_cfrg sig)
{
return verify (Q, M||sig.R, (to_ecdsa)(sig)) ;
}

bool verify_ecdsa_cfrg (bits Q, bits M, bits sig)
{
return VERIFY((to_point)(Q), M, (to_ecdsa_cfrg)(sig)) ;
}

bits verification_key_ecdsa_cfrg (bits key)
{
return (to_bits)(prf(key) * G) ;
}

bits sign_ecdsa_cfrg (bits key, bits M)
{
mult k = prf(key, M) ;
mult m = prf(key, k) ; // mask leaky / op
mult d = prf(key) ;
point R = k*G ;
mult s = (hash(M||R) + f(R)*d) / (k*m) ;
return (to_bits)((ecdsa_cfrg){R , (s*m)}) ;
}

////////////////////////////////////////////////////////
// File "ecdsa_cfrg.hh" (types and conversions)
typedef struct { /*...*/ } mult ;
typedef struct { /*...*/ } point ;
typedef struct { /*...*/ } bits ;
typedef struct {point R; mult s;} ecdsa_cfrg ;
typedef struct {mult r; mult s;} ecdsa ;
point G = { /*...*/ } ;
bits to_bits (point) ;
point to_point (bits) ;
bits to_bits (ecdsa_cfrg) ;
ecdsa_cfrg to_ecdsa_cfrg (bits) ;
mult to_mult (point P)
/* Weierstrass: { return (to_mult)((to_bits)(x(P)));} */ ;
# define f to_mult
ecdsa to_ecdsa (ecdsa_cfrg sig)
{
return (ecdsa){f(sig.R), sig.s} ;
}
mult hash (bits) ;
mult prf (bits) ; // MUST: deterministic
mult prf (bits, bits) ; // SHOULD: deterministic
mult prf (bits, mult) ; // SHOULD: non-deterministic
bool operator == (mult, mult);
mult operator + (mult, mult);
mult operator * (mult, mult);
mult operator / (mult, mult);
bits operator || (bits, bits);
bits operator || (bits M, point R)
{ return M || (to_bits)(R) ; }
bool operator == (point, point);
point operator + (point, point);
point operator * (mult , point);
point operator / (point, mult ); // ECDSA verify spec only

(2) Hash function
=================

The choice of hash for ECDSA_CFRG is determined by the curve.

In the pseudocode a function hash is specified.  This is obtained by
using the following bit-string-outputting hash function, and then
reducing the corresponding integer modulo the based point order.

Implicit in this a conversion of bit string to an integer, which will
follow the same convention used for point coordinates,
i.e. little-endian or big-endian.

(2a) For curves (with base point order) of 256 bits or less,
e.g. P-256 or Curve25519, the hash is SHA-384 (one of the SHA2
hashes) truncated to the bit length of the base point order.

Rationale:
- This is effectively wide-pipe, because the SHA384 internal state is
  512 bits.
- I've heard that SHA-384 is widely available.
- The truncation pattern follows the old ECDSA practice, making it
  slightly easier to re-use a ECDSA verifier.

(2b) For curves (with base point order) of bit lengths between 257 and
512 inclusive, the hash is SHA3-512 (one of the SHA3 hashes) truncated
to one bit less than that bit length of the base point order.

Rationale:
- This is wide-pipe, because the internal SHA3-512 internal state is
  1024 bits.
- For higher strength curves, it makes sense to use best available
  hash in amount of review and provenance, i.e. SHA-3.
- The truncation chops one additional bit, so the hash output is
  smaller than the base point order, which fends off Vaudenay domain
  parameter attacks.

(2c) For curves with base point order of 571 bits of less, use the same
hash as determined by the rules of (2b).  This is nearly wide-pipe,
and a kind of grandfathering rule.

(2d) For curves with base point order of 572 bits or more, one must
one wait until a sufficiently wide-pipe hash is approved by CFRG.
Sorry.

(3) PRF for ephemeral key ("nonce") generation
==============================================

In the pseudocode an overloaded function prf, which is now described,
in two stage.  The first stage assumes a hash-like PRF with two inputs
a key, and variable length message, and a fixed length output.  The
second stage defines the PRF.

Stage 1, using a PRF ...

prf(seed) = PRF(seed, 0^8), where 0^8 is the octet of all zero bits.

prf(seed,message) = PRF(seed,1^8 || message).

prf(seed,multiplier) = to be defined, used for masking, uses run-time
entropy.  Maybe prf(seed, multiplier) = PRF(seed, (01)^4 || multiplier
|| run-time-nonce) 

A rationale for the key separation within the message input is to use
on the PRF security goals, that the PRF output with a fixed seed
reveals nothing about the messages.  This tries to avoid fiddling
with seed input to the PRF, since PRF do not promise resilience to
related key attacks.

The reason about being so pedantic with PRF goals, is that slight
biases in the keys are known to expose DL signatures.  So, let's stick
with the promised goals of PRFs.

Stage 2, choosing a PRF ...

The recommended of PRF will be related to the hash from section (2)
above.  The relatedness is for convenience.

When the hash is SHA-384, the PRF will be HMAC-SHA-384 with no
truncation.  The PRF seed is the HMAC key.

When the hash is SHA3-512, the PRF will be SHAKE256 using seed as a
prefix.  The output length will be set to be 50% above the base point
order bit length (rounding up).

A rationale for these PRFs is that HMAC is widely believed to provide
a good PRF in addition to a MAC property.  I'm hoping the same will be
true for SHAKE256.

If there are better variable-in and fixed-out length PRFs, then I
would like to know about them.

The extra 50% in the bit length of the output before reduction aims to
reduce the information-theoretic exposure of the static signing keys.

Also, if an implementer later opts to diverge from this recommendation
by truncating to the bit length of base point order, which also seems
secure for curves whose base point order is quite close to a power of
two, then the truncation attack that I sent an email about earlier
will not work because the truncated bits will be too many.

(4) Conversion of points to scalar integer multipliers
======================================================

The high-level pseudocode uses a function f, a macro for a function
to_mult that has input of a point, and output a scalar integer
multiplier.

For Weierstrass format curves, just follow the similar pattern used
for ECDSA curves.

For other curve formats, I recommend using the default compressed bit
string representation of a point, and then the default conversion of
bit strings to integers.  Or, if people prefer, using a single
coordinate, i.e. the one used in a Montgomery ladder, representing it
as a bit string, and then an integer.

The main, and very mild, security goal for f is that one should have a
good chance of recovering R from f(R). 

(5) Backwards (and forwards) (non-)inter-operation
=================================================

(5a) Backwards interoperability with ECDSA verifiers

Existing ECDSA verifiers that can adapt easily the curve and hash, _can_
be used to verify ECDSA_CFRG signatures by applying a simple
transformation to the signature and to the message.

This interoperability can be viewed as a convenience, but it is also
has a security benefit.  It is the reason why signer-absent forgery of
ECDSA_CFRG cannot be easier than signer-absent forgery of ECDSA.  In
other words, the modifications have not introduced new security risks
in the area of signer-absent forgery.

(5b) Non-interoperability with ECDSA 

Existing ECDSA signers, some of which have severe implementation
faults, _cannot_ be used to generated ECDSA_CFRG unless they are
drastically modified.  This is backwards non-inter-operation of
signers.

Existing ECDSA signatures, _cannot_ be verified with a strict
ECDSA_CFRG verifier.  This is forward non-inter-operation of verifiers.

These two non-inter-operations are a security benefit in that they
prevent broken ECDSA signers, or the resulting ECDSA forgeries to be
used against ECDSA_CFRG.

(5c) Curve formats

In my ideal world, an old generic-curve ECDSA verifier could be used
to verify ECDSA_CFRG with new curves.  There seems to be strong
preference in CFRG to use incompatible formats for new curves, so this
ideal would not be feasible.

Best regards,

Daniel Brown
Certiom Research / BlackBerry Standards