<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<br>
<div class="moz-cite-prefix">On 6/25/2014 8:37 AM, David Leon Gil
wrote:<br>
</div>
<blockquote
cite="mid:CAA7UWsVwR=NXRth=EUk=9v7gyt40csWegxkj5pxCuJM7GBs7cw@mail.gmail.com"
type="cite">
<p dir="ltr">Re signature nonces:</p>
<p dir="ltr">In general, I strongly prefer deriving the permanent
nonce key via, e.g., PMAC (prefix/postfix MAC)-SHAKE[r=x]* or
HMAC-SHA2-512 with a domain separator.**</p>
<p dir="ltr">It's deterministic, it avoids using more entropy than
necessary for security, and it makes private keys (in serialized
form) the same size as public keys.</p>
<p dir="ltr">(I have been modifying the experimental Goldilocks
code along these lines.)</p>
</blockquote>
Is your goal in doing this to reduce the size of serialized private
keys? The private keys are already derived from the 256-bit
symmetric key. You might consider using
goldilocks_underive_private_key().
<blockquote
cite="mid:CAA7UWsVwR=NXRth=EUk=9v7gyt40csWegxkj5pxCuJM7GBs7cw@mail.gmail.com"
type="cite">
<p dir="ltr">*** The recent cryptanalysis of reduced-round
Keccak/SHAKE as a stream cipher has left me mildly concerned
that non-uniform inputs may be problematic.</p>
</blockquote>
Is this the 6-round cube attack, or is there a stronger one?<br>
<br>
Cheers,<br>
-- Mike<br>
<br>
<blockquote
cite="mid:CAA7UWsVwR=NXRth=EUk=9v7gyt40csWegxkj5pxCuJM7GBs7cw@mail.gmail.com"
type="cite">
<div class="gmail_quote">On Jun 16, 2014 5:33 PM, "Trevor Perrin"
<<a moz-do-not-send="true" href="mailto:trevp@trevp.net">trevp@trevp.net</a>>
wrote:<br type="attribution">
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi,<br>
<br>
I'm wondering about using Curve25519 keys to create and verify
Ed25519<br>
signatures. For example, imagine you have existing Curve25519<br>
long-term keys being used for a DH protocol, and you'd like to
sign<br>
with these keys.<br>
<br>
Below is an attempt to provide security analysis, and work out
the details.<br>
<br>
I've run parts of this by a few people (Mike Hamburg, Robert
Ransom,<br>
CodesInChaos). I try to credit them where appropriate, but
that<br>
doesn't imply they endorse all of this.<br>
<br>
<br>
Joint security of signatures and DH<br>
----<br>
Schnorr signatures (like Ed25519) have a security proof in the
Random<br>
Oracle Model based on the (Elliptic Curve ) Discrete Log
assumption<br>
[1].<br>
<br>
Many DH protocols have security proofs in a model where the
attacker<br>
has access to a "Decision Diffie-Hellman" oracle. Often the
attacker<br>
can choose an arbitrary public key, cause a targeted key to
perform a<br>
DH operation with the chosen public key, and then "reveal" the
hashed<br>
output. By hashing different inputs and seeing if the result
equals<br>
the revealed value, the attacker gains a DDH oracle involving
the<br>
targeted key and her chosen key. These protocols can often
be proven<br>
secure in the Random Oracle Model based on the "Gap-DH"
assumption:<br>
i.e. the assumption that the Computational DH problem is hard
even<br>
when given a DDH oracle. Protocols that can be proven secure
in such<br>
a model include ECIES [2], NAXOS [3], Ntor [4], Kudla-Paterson
[5],<br>
HOMQV [6], and others.<br>
<br>
As in [7] section 4.4, it seems fairly easy to argue for
"joint<br>
security" when the same key is used for Schnorr signatures and
for a<br>
protocol with a Gap-DH/ROM security proof, provided the hash
function<br>
is used carefully so that RO queries for the signature can be<br>
distinguished from RO queries for the DH-protocol.<br>
<br>
In particular:<br>
- Giving the DH-protocol adversary a signing oracle doesn't
help it,<br>
as the signing oracle can be simulated in the ROM without
knowledge of<br>
the secret key [1,7].<br>
- Giving the signature adversary access to parties running
the<br>
DH-protocol (e.g. an eCK experiment [3] where the secret key
is held<br>
by an honest party) doesn't help if the protocol can be
simulated<br>
without knowledge of the secret key but with a DDH oracle. If
the<br>
signature adversary + simulator could use the DDH oracle to
break the<br>
DL problem, then the Gap-DH assumption would be violated [7].<br>
<br>
So in principle this seems secure, do people agree?<br>
<br>
<br>
Public-key conversion<br>
----<br>
A Curve25519 public-key is encoded as a 255-bit x-coordinate.
An<br>
Ed25519 public-key is encoded as a 255-bit y-coordinate, plus
a "sign"<br>
bit.<br>
<br>
For a "unified" public-key format, I think it makes sense to
stick<br>
with Curve25519:<br>
- Curve25519 has seen more deployment than Ed25519, so
existing<br>
public-keys are more likely to use the Curve25519 format.<br>
- The sign bit isn't strictly necessary, since it can be
assumed to<br>
be zero, and the private key can be adjusted to match (see
below).<br>
- The Curve25519 format is more efficient for DH since it can
be used<br>
directly with the Montgomery ladder. For signature
verification, the<br>
conversion from Curve25519 format to an Ed25519 point can be
combined<br>
with decompression, so using Curve25519 public keys to verify
Ed25519<br>
signatures can be almost as fast for verification as Ed25519
public<br>
keys (according to Mike Hamburg).<br>
- If code simplicity is more of a concern than speed, it's
easy to<br>
convert the curve25519 x-coordinate into an ed25519
y-coordinate by<br>
ed_y = (curve_x - 1) / (curve_x + 1) mod 2^255-19 (page 8 of
[8], hat<br>
tip Robert Ransom). The inversion takes perhaps 10-20% (?) of
the<br>
time for a variable-base scalar mult. The y-coordinate can
then be<br>
encoded along with a sign bit of 0, allowing existing Ed25519
code to<br>
be used.<br>
<br>
<br>
Private-key conversion<br>
----<br>
If the Ed25519 public-key sign-bit is assumed to be zero, the
private<br>
key may need to be adjusted (per Jivsov [9]). In other words,
if<br>
multiplying the Curve25519 private key by the Ed25519 base
point<br>
yields an Ed25519 x-coordinate that's "negative" as defined in
[8],<br>
the private key (a) must be negated modulo the order of the
base point<br>
(q), i.e. a = q - a.<br>
<br>
Some existing curve25519 implementations set bit 254 of the
private<br>
key within the scalarmult function, so will interfere with
this<br>
negation (observation due CodesInChaos). Robert Ransom
proposed<br>
another way to implement the negation that avoids having to
modify<br>
that code:<br>
- Before hashing, flip the sign bit of R<br>
- Before hashing, encode the sign bit of A as zero<br>
- As the last step, negate S, i.e. S = q - S<br>
<br>
Jivsov argues that fixing the sign bit doesn't lose security,
even<br>
against Pollard rho (anyone care to double-check the argument?
- [9]<br>
section 8). A side-channel that leaks only whether this
negation was<br>
performed (or not) only reveals the sign bit of the original
private<br>
key, so I think also doesn't reduce security.<br>
<br>
<br>
Hash inputs<br>
----<br>
Ed25519 calculates SHA512(R || A || M), where:<br>
- R is an Ed25519-encoded Schnorr commitment (= nonce *
base point)<br>
- A is an Ed25519-encoded public key<br>
- M is the message to sign<br>
<br>
The key-derivation in the DH protocol must hash distinct
inputs for<br>
the ROM security argument to hold. CodesInChaos suggested
beginning<br>
the key-derivation hash with 32 bytes of 0xFF, as this is an
invalid<br>
Ed25519 point.<br>
<br>
<br>
Signature nonce<br>
----<br>
In the original Ed25519 implementation [8], a single master
key is<br>
used to derive both (a) the Ed25519 private scalar and (b) a
secret<br>
key for nonce generation. Without such a master key, either<br>
- the nonce-generation key would have to be explicitly
generated and stored<br>
- the nonce would have to be taken from a (strong!) RNG<br>
- the private scalar would have to be used as the
nonce-generation key<br>
<br>
All of these seem adequate. Not sure which is best?<br>
<br>
Anyways, what else have I missed?<br>
<br>
<br>
Trevor<br>
<br>
<br>
[1] <a moz-do-not-send="true"
href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.8213"
target="_blank">http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.8213</a><br>
[2] <a moz-do-not-send="true"
href="http://www.cs.ucdavis.edu/%7Erogaway/papers/dhies.pdf"
target="_blank">http://www.cs.ucdavis.edu/~rogaway/papers/dhies.pdf</a><br>
[3] <a moz-do-not-send="true"
href="http://research.microsoft.com/pubs/81673/strongake-submitted.pdf"
target="_blank">http://research.microsoft.com/pubs/81673/strongake-submitted.pdf</a><br>
[4] <a moz-do-not-send="true"
href="http://cacr.uwaterloo.ca/techreports/2011/cacr2011-11.pdf"
target="_blank">http://cacr.uwaterloo.ca/techreports/2011/cacr2011-11.pdf</a><br>
[5] <a moz-do-not-send="true"
href="http://www.isg.rhul.ac.uk/%7Ekp/ModularProofs.pdf"
target="_blank">http://www.isg.rhul.ac.uk/~kp/ModularProofs.pdf</a><br>
[6] <a moz-do-not-send="true"
href="http://eprint.iacr.org/2010/638" target="_blank">http://eprint.iacr.org/2010/638</a><br>
[7] <a moz-do-not-send="true"
href="http://eprint.iacr.org/2011/615" target="_blank">http://eprint.iacr.org/2011/615</a><br>
[8] <a moz-do-not-send="true"
href="http://ed25519.cr.yp.to/ed25519-20110926.pdf"
target="_blank">http://ed25519.cr.yp.to/ed25519-20110926.pdf</a><br>
[9] <a moz-do-not-send="true"
href="https://datatracker.ietf.org/doc/draft-jivsov-ecc-compact/?include_text=1"
target="_blank">https://datatracker.ietf.org/doc/draft-jivsov-ecc-compact/?include_text=1</a><br>
_______________________________________________<br>
Curves mailing list<br>
<a moz-do-not-send="true"
href="mailto:Curves@moderncrypto.org">Curves@moderncrypto.org</a><br>
<a moz-do-not-send="true"
href="https://moderncrypto.org/mailman/listinfo/curves"
target="_blank">https://moderncrypto.org/mailman/listinfo/curves</a><br>
</blockquote>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
Curves mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Curves@moderncrypto.org">Curves@moderncrypto.org</a>
<a class="moz-txt-link-freetext" href="https://moderncrypto.org/mailman/listinfo/curves">https://moderncrypto.org/mailman/listinfo/curves</a>
</pre>
</blockquote>
<br>
</body>
</html>