Discussion:
[curves] Ed25519 "clamping" and its effect on hierarchical key derivation
Oleg Andreev
2017-04-07 21:17:42 UTC
Permalink
(a) that it would be nice to reuse existing code for EdDSA that
already does bit-twiddling clamping for the private-key-to-public-key
map, especially now that it has been formalized in an RFC;
Doesn't bit-twiddling only happen immediately after expanding 32-byte random string into a 64-byte "expanded secret key" where first half is a scalar where clamping is applied, and the second half is the "prefix" that later is hashed with the message to generate a nonce?

For instance, NaCl API accepts 64-byte secret and does not modify its bits - that's assumed to be done in the separate "generate keypair" function. EdDSA does not even have a name or interface for 64-byte secret key, and a Go lib for ed25519 also assumes privkey is a raw 32-byte buffer to be hashed.

I mean, is there really a piece of software accepts a 64-byte (already expanded) secret key and tweaks its bits? Because if there isn't, then bit-twiddling that happens in the interfaces accepting 32-byte strings is irrelevant to HKD schemes - they won't be able to derive a child pubkey from a parent pubkey if there's non-linear hashing involved.
Oleg Andreev
2017-04-07 23:40:42 UTC
Permalink
Post by Oleg Andreev
(a) that it would be nice to reuse existing code for EdDSA that
already does bit-twiddling clamping for the private-key-to-public-key
map, especially now that it has been formalized in an RFC;
Doesn't bit-twiddling only happen immediately after expanding 32-byte random string into a 64-byte "expanded secret key" where first half is a scalar where clamping is applied, and the second half is the "prefix" that later is hashed with the message to generate a nonce?
For instance, NaCl API accepts 64-byte secret and does not modify its bits - that's assumed to be done in the separate "generate keypair" function. EdDSA does not even have a name or interface for 64-byte secret key, and a Go lib for ed25519 also assumes privkey is a raw 32-byte buffer to be hashed.
I mean, is there really a piece of software accepts a 64-byte (already expanded) secret key and tweaks its bits? Because if there isn't, then bit-twiddling that happens in the interfaces accepting 32-byte strings is irrelevant to HKD schemes - they won't be able to derive a child pubkey from a parent pubkey if there's non-linear hashing involved.
Tony Arcieri just showed me this summary (https://blog.mozilla.org/warner/2011/11/29/ed25519-keys/)
of existing Ed25519 implementations where all (but NaCl) accept 32-byte privkey that
is hashed and then clamped as described in EdDSA.

This means that for all of these implementations, the smallest change
would be to factor out signing code using expanded 64-bit key, and let the outer scheme
manage creation of that key. NaCl library has that code factored out already, so no change necessary.

Here's an example of such refactoring for Go ed25519 library:
https://github.com/chain/chain/commit/88af34b0f40193d06c7f23576360f8fe7c101f0d

My conjecture is: if there is no implementation that accepts 64-byte expanded key
and sets bits in its left half, then arguments that bit-twiddling is good
for compatibility become irrelevant -- because no one except NaCl can possibly be compatible with any HKD scheme.
Gregory Maxwell
2017-04-08 00:07:50 UTC
Permalink
Post by Oleg Andreev
My conjecture is: if there is no implementation that accepts 64-byte expanded key
and sets bits in its left half, then arguments that bit-twiddling is good
for compatibility become irrelevant -- because no one except NaCl can possibly be compatible with any HKD scheme.
I think that people should really consider curves with cofactor 1.
Outside of the DH context where very efficient X-only has some nice
payoffs (though moderately efficient X-only is also possible for other
curves) the expected benefits seem to be more fiction than reality.
The cofactor needlessly complicates many usages, as we see in this
discussion; and failures to handle it well can result in invisible
failures and vulnerabilities..

With suitable use of constant moves (which can't be avoided completely
in ed25519 once you must handle arbitrary keys) other formulations can
be soundly constant time.

Irresponsibly written software is going to be busted regardless of the
curve used.

I like to use an example this implementation of 'ed25519' signatures,
which is widely linked all over the internet in 'lists of ed25519
software' pages, as though it were something you should use,
https://github.com/vbuterin/ed25519/blob/master/ed25519.py#L242

... It leaks the private key on the second signature and uses a
gratuitously timing-side-channel exposed double and add. Two of the
issues the construction is supposed to have designed out.

(As a more on-topic point, that implementation hashes the incoming
secret; adding to the body of 25519 software which isn't compatible
with hierarchical keys)

You cannot reliably engineer around raw carelessness or indifference.

I think the best we can do is pack all worst of the complexity as deep
inside as possible, to that it's all handled in the parts that _must_
be done with care and competence and extensive review. I think that
optimizing addition formula at the expense of cofactor (whos
complexity is not hidden behind a point_add function deep in the
software) does not accomplish this, at least for applications other
than pure DH.
Tony Arcieri
2017-04-08 00:54:16 UTC
Permalink
Post by Gregory Maxwell
I think that people should really consider curves with cofactor 1.
Outside of the DH context
I think e.g. secp256k1 has some very nice properties for signatures, but it
seems fairly common to want to use the same curve for signatures and D-H,
such as the Lightning Network adapting Trevor's Noise protocol to use
secp256k1 for D-H. I think it's probably worth considering both the
signatures and D-H use cases.

In regard to hierarchical key derivation which addresses both signatures
and D-H cases using Curve25519, the torsion safe representatives scheme
from the Tor developers seems to do this relatively elegantly.
--
Tony Arcieri
D. J. Bernstein
2017-04-15 14:41:49 UTC
Permalink
Post by Gregory Maxwell
You cannot reliably engineer around raw carelessness or indifference.
Actually, you can. Consider, e.g., the verified seL4 microkernel, which
enforces various clear security policies against _all other software_,
no matter how carelessly that software is written.

There's tremendous ongoing work into making the underlying engineering
techniques less expensive, more broadly applicable (the kernel is only
one part of the security picture), and more functional from the user's
perspective.

An important part of "less expensive" is systematically reducing the
size of the trusted computing base (TCB). In the crypto context this is
what leads to decisions such as

* replacing separate encryption+signatures with pure DH,
* implementing DH with Montgomery's very simple x-ladder formulas,
* choosing twist-secure Montgomery curves,
* focusing on one curve at an ample security level,
* choosing a prime very close to a power of 2,

etc., and in general getting the amount of critical crypto code down to
something that we can afford to convincingly verify. The fastest way
that we can get to wide deployment of verified software for encryption
_and_ authentication is by focusing on the simplest possible protocol
using X25519 and a similarly simple symmetric-cipher suite.

(We also have to do something to handle the risk of quantum computers;
but this doesn't justify doing anything more complicated than X25519 for
the pre-quantum part. Poor connectivity sometimes forces people to sign
data rather than using encryption to authenticate; but this doesn't
justify delaying deployment of pure X25519 solutions for the Internet.)

The same simplifications also have immediate side benefits such as
solidly stopping

http://blogs.adobe.com/security/2017/03/critical-vulnerability-uncovered-in-json-encryption.html

and other similar real-world vulnerabilities. Of course you can blame
these vulnerabilities on "carelessness"---many standards clearly tell
the programmers to add point-validation code!---but you have to realize
that you're advocating _more code_, and that this is just one out of
thousands of bad decisions that have made today's TCBs far too large.

You're working on a much more complicated bleeding-edge crypto protocol,
trying to achieve more advanced security features. These features seem
to require a significantly larger TCB. Of course having two metrics---

(1) the size of the TCB for core security features and
(2) the size of the TCB for more advanced security features

---means that it's not _necessarily_ possible to optimize both at the
same time, but this begs some really basic questions:

* Has anyone seriously tried to optimize #2?
* Does optimizing #1 do any noticeable damage to #2?

Anyway, if there _is_ a tension, then #1 is much more important---and a
much higher priority. Users need data encrypted and authenticated on a
massive scale; we need to get this done, and we need to get it right.

---Dan

Ron Garret
2017-04-07 23:57:50 UTC
Permalink
Post by Oleg Andreev
For instance, NaCl API accepts 64-byte secret
Not really. What appears to be a 64 byte secret key is actually a 32-byte secret key concatenated with the corresponding 32-byte public key.

rg
Oleg Andreev
2017-04-08 00:02:08 UTC
Permalink
Post by Ron Garret
Post by Oleg Andreev
For instance, NaCl API accepts 64-byte secret
Not really. What appears to be a 64 byte secret key is actually a 32-byte secret key concatenated with the corresponding 32-byte public key.
I noticed that for the Go ed25519 library, but in my copy of NaCl from 2011, 64-byte string is the scalar concatenated with "prefix" (term from EdDSA). See: https://gist.github.com/oleganza/78c9e30f8e292aa8b3aff849a1c28f2c#file-sign-c-L30-L70

PS. I was initially confused to learn that Go library uses 64-byte string to attach pubkey to a 32-byte scalar preimage. That's unfortunate, but I expect everyone else to be confused about this too for a long time to come.
Tony Arcieri
2017-04-08 00:06:47 UTC
Permalink
Post by Ron Garret
Not really. What appears to be a 64 byte secret key is actually a 32-byte
secret key concatenated with the corresponding 32-byte public key.
Oleg is describing the original NaCl API (as in https://nacl.cr.yp.to/),
not the API provided by the ref10 implementation (which has proliferated
from SUPERCOP). My understanding is this version has various
incompatibilities and security issues versus ref10.

This version uses a 64-bit secret key (sk) alongside a 32-bit public key.
See Brian Warner's writeup which Oleg linked for more information.

Here is the original key generation code from NaCl (2011), which fills a
64-byte secret key buffer with 32-bytes of randomness before expanding it
into 64-bytes using SHA-512. Note it also "pre-clamps" the secret scalar:

int crypto_sign_keypair(
unsigned char *pk,
unsigned char *sk
)
{
sc25519 scsk;
ge25519 gepk;

randombytes(sk, 32);
crypto_hash_sha512(sk, sk, 32);
sk[0] &= 248;
sk[31] &= 127;
sk[31] |= 64;

sc25519_from32bytes(&scsk,sk);

ge25519_scalarmult_base(&gepk, &scsk);
ge25519_pack(pk, &gepk);
return 0;
}
--
Tony Arcieri
Ron Garret
2017-04-08 00:33:59 UTC
Permalink
Post by Ron Garret
Not really. What appears to be a 64 byte secret key is actually a 32-byte secret key concatenated with the corresponding 32-byte public key.
Oleg is describing the original NaCl API (as in https://nacl.cr.yp.to/), not the API provided by the ref10 implementation (which has proliferated from SUPERCOP). My understanding is this version has various incompatibilities and security issues versus ref10.
This version uses a 64-bit secret key (sk) alongside a 32-bit public key. See Brian Warner's writeup which Oleg linked for more information.
int crypto_sign_keypair(
unsigned char *pk,
unsigned char *sk
)
{
sc25519 scsk;
ge25519 gepk;
randombytes(sk, 32);
crypto_hash_sha512(sk, sk, 32);
sk[0] &= 248;
sk[31] &= 127;
sk[31] |= 64;
sc25519_from32bytes(&scsk,sk);
ge25519_scalarmult_base(&gepk, &scsk);
ge25519_pack(pk, &gepk);
return 0;
}
Ah.

I’m using TweetNaCl which I had assumed had the same API as NaCl. But it doesn’t. TweetNacl does this:

int crypto_sign_keypair(u8 *pk, u8 *sk)
{
u8 d[64];
gf p[4];
int i;

randombytes(sk, 32);
crypto_hash(d, sk, 32);
d[0] &= 248;
d[31] &= 127;
d[31] |= 64;

scalarbase(p,d);
pack(pk,p);

FOR(i,32) sk[32 + i] = pk[i];
return 0;
}
Loading...