<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>