Accessing Point representation of Ed448 for ECDH implementation

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Accessing Point representation of Ed448 for ECDH implementation

Danny van Heumen
Hi all,

First of all, I'm new to the list, so any pointers are welcome.

I'm currently a happy user of Bouncy Castle for its Ed448
(RFC8032) implementation. I use this for the otr4j implementation
(https://github.com/otr4j/otr4j) of OTRv4.

OTRv4 also specifies an ECDH key type, based on Ed448 Point
representation. (See
https://github.com/otrv4/otrv4/blob/master/otrv4.md#generating-ecdh-and-dh-keys.)
However, it requires a Point multiplication operation. AFAICT, Bouncy
Castle does not expose its internally used Point type and no methods
are exposed to perform scalar multiplication on a Point.

Am I missing something? If not, are there any plans/intentions to
expose the point representation? If not, are there any recommendations
you can give me on how I can best tackle this?

I currently use an amateurisch custom-made Ed448 Point implementation
which serves to prove that the code functionally works, but I would
like to get rid of it ASAP.

Let me know if you need any more information.

Kind regards,
Danny


Reply | Threaded
Open this post in threaded view
|

Re: Accessing Point representation of Ed448 for ECDH implementation

Danny van Heumen
On Sat, 8 Jun 2019 17:12:32 +0200
Danny van Heumen <[hidden email]> wrote:

> Hi all,
>
> First of all, I'm new to the list, so any pointers are welcome.
>
> I'm currently a happy user of Bouncy Castle for its Ed448
> (RFC8032) implementation. I use this for the otr4j implementation
> (https://github.com/otr4j/otr4j) of OTRv4.
>
> OTRv4 also specifies an ECDH key type, based on Ed448 Point
> representation. (See
> https://github.com/otrv4/otrv4/blob/master/otrv4.md#generating-ecdh-and-dh-keys.)
> However, it requires a Point multiplication operation. AFAICT, Bouncy
> Castle does not expose its internally used Point type and no methods
> are exposed to perform scalar multiplication on a Point.
>
> Am I missing something? If not, are there any plans/intentions to
> expose the point representation? If not, are there any recommendations
> you can give me on how I can best tackle this?
>
> I currently use an amateurisch custom-made Ed448 Point implementation
> which serves to prove that the code functionally works, but I would
> like to get rid of it ASAP.
>
> Let me know if you need any more information.
>
> Kind regards,
> Danny
>
>

I'm currently looking at package org.bouncycastle.math.ec
(https://bouncycastle.org/docs/docs1.5on/org/bouncycastle/math/ec/package-frame.html).
I'm not sure how I could have missed this, but I'm guessing this
already provides everything I need.

Any pointers are welcome.

In case it turns out this package already has everything I need,
apologies for the spam ...

Danny

Reply | Threaded
Open this post in threaded view
|

Re: Accessing Point representation of Ed448 for ECDH implementation

Peter Dettman-3
In reply to this post by Danny van Heumen
Hi Danny,

Please refer to the core implementation class in
org.bouncycastle.math.ec.rfc8032.Ed448.

IIUC, the generateECDH() method described in otrv4.md would just be a
slight adaptation of these methods from Ed448:

    public static void generatePrivateKey(SecureRandom random, byte[] k)
    {
        random.nextBytes(k);
    }

    public static void generatePublicKey(byte[] sk, int skOff, byte[]
pk, int pkOff)
    {
        Xof d = createXof();
        byte[] h = new byte[SCALAR_BYTES * 2];

        d.update(sk, skOff, SECRET_KEY_SIZE);
        d.doFinal(h, 0, h.length);

        byte[] s = new byte[SCALAR_BYTES];
        pruneScalar(h, 0, s);

        scalarMultBaseEncoded(s, pk, pkOff);
    }

where the 's' value from generatePublicKey has to be recovered as
our_ecdh.secret and 'pk[pkOff..]' as our_ecdh.public .

So that would be easy to provide. Unfortunately, generating a shared
secret is not going to be so easy, because BC currently only supports
the X448 function (from RFC 7748), implemented on curve448 i.e. the
Montgomery version of this curve (see
org.bouncycastle.math.ec.rfc7748.X448).

There are maps between the curves which *might* allow some sort of hack,
but the Montgomery X448 implementation is u-coordinate only, which
probably throws a wrench in that idea.

X448 key generation is already delegated to Ed448 and X448 shared secret
calculation is intended to eventually also be delegated, which would
involve adding to Ed448 exactly the non-basepoint scalar multiplication
that appears to be needed here; but we do not have it yet.

Regards,
Pete Dettman


On 8/6/19 10:12 pm, Danny van Heumen wrote:

> Hi all,
>
> First of all, I'm new to the list, so any pointers are welcome.
>
> I'm currently a happy user of Bouncy Castle for its Ed448
> (RFC8032) implementation. I use this for the otr4j implementation
> (https://github.com/otr4j/otr4j) of OTRv4.
>
> OTRv4 also specifies an ECDH key type, based on Ed448 Point
> representation. (See
> https://github.com/otrv4/otrv4/blob/master/otrv4.md#generating-ecdh-and-dh-keys.)
> However, it requires a Point multiplication operation. AFAICT, Bouncy
> Castle does not expose its internally used Point type and no methods
> are exposed to perform scalar multiplication on a Point.
>
> Am I missing something? If not, are there any plans/intentions to
> expose the point representation? If not, are there any recommendations
> you can give me on how I can best tackle this?
>
> I currently use an amateurisch custom-made Ed448 Point implementation
> which serves to prove that the code functionally works, but I would
> like to get rid of it ASAP.
>
> Let me know if you need any more information.
>
> Kind regards,
> Danny
>
>


Reply | Threaded
Open this post in threaded view
|

Re: Accessing Point representation of Ed448 for ECDH implementation

Peter Dettman-3
In reply to this post by Danny van Heumen
Hi Danny,
That package is really legacy/fallback code for curves we don't have
custom implementations for, and in any case only for Short Weierstrass
form curves, not Montgomery or Edwards.

Regards,
Pete Dettman

On 8/6/19 10:21 pm, Danny van Heumen wrote:

> I'm currently looking at package org.bouncycastle.math.ec
> (https://bouncycastle.org/docs/docs1.5on/org/bouncycastle/math/ec/package-frame.html).
> I'm not sure how I could have missed this, but I'm guessing this
> already provides everything I need.
>
> Any pointers are welcome.
>
> In case it turns out this package already has everything I need,
> apologies for the spam ...
>
> Danny
>


Reply | Threaded
Open this post in threaded view
|

Re: Accessing Point representation of Ed448 for ECDH implementation

Danny van Heumen
In reply to this post by Peter Dettman-3
Hi,

Thanks for the pointers. I'll respond in-line.

On Sun, 9 Jun 2019 15:22:29 +0700
Peter Dettman <[hidden email]> wrote:

> Hi Danny,
>
> Please refer to the core implementation class in
> org.bouncycastle.math.ec.rfc8032.Ed448.
>
> IIUC, the generateECDH() method described in otrv4.md would just be a
> slight adaptation of these methods from Ed448:
>
>     public static void generatePrivateKey(SecureRandom random, byte[]
> k) {
>         random.nextBytes(k);
>     }
>
>     public static void generatePublicKey(byte[] sk, int skOff, byte[]
> pk, int pkOff)
>     {
>         Xof d = createXof();
>         byte[] h = new byte[SCALAR_BYTES * 2];
>
>         d.update(sk, skOff, SECRET_KEY_SIZE);
>         d.doFinal(h, 0, h.length);
>
>         byte[] s = new byte[SCALAR_BYTES];
>         pruneScalar(h, 0, s);
>
>         scalarMultBaseEncoded(s, pk, pkOff);
>     }

Agree. I don't see a big problem there, either. That is, given my
limited knowledge. (I found the scalarMultBaseEncoded function before,
and I believe that's just the basepoint scalar multiplication, right?)

> where the 's' value from generatePublicKey has to be recovered as
> our_ecdh.secret and 'pk[pkOff..]' as our_ecdh.public .
>
> So that would be easy to provide. Unfortunately, generating a shared
> secret is not going to be so easy, because BC currently only supports
> the X448 function (from RFC 7748), implemented on curve448 i.e. the
> Montgomery version of this curve (see
> org.bouncycastle.math.ec.rfc7748.X448).
>
> There are maps between the curves which *might* allow some sort of
> hack, but the Montgomery X448 implementation is u-coordinate only,
> which probably throws a wrench in that idea.
>
> X448 key generation is already delegated to Ed448 and X448 shared
> secret calculation is intended to eventually also be delegated, which
> would involve adding to Ed448 exactly the non-basepoint scalar
> multiplication that appears to be needed here; but we do not have it
> yet.

What kind of expectations does Bouncy Castle have for such a scalar
multiplication implementation? What kind of guarantees are required at
minimum?

I'm willing to invest some time into looking into the scalar
multiplication, but I have limited knowledge of such low-level
implementations. I could do a naive one and with help from the community
see if we can improve. Or alternative, if one knows of suitable
reference material, I can try diving into the more complicated
implementations.

Would that be a possibility?

Regards,
Danny



Reply | Threaded
Open this post in threaded view
|

Re: Accessing Point representation of Ed448 for ECDH implementation

Peter Dettman-3
On 9/6/19 11:03 pm, Danny van Heumen wrote:

>> Please refer to the core implementation class in
>> org.bouncycastle.math.ec.rfc8032.Ed448.
>>
>> IIUC, the generateECDH() method described in otrv4.md would just be a
>> slight adaptation of these methods from Ed448:
>>
>>     public static void generatePrivateKey(SecureRandom random, byte[]
>>     public static void generatePublicKey(byte[] sk, int skOff, byte[]
>> pk, int pkOff)
>
> Agree. I don't see a big problem there, either. That is, given my
> limited knowledge. (I found the scalarMultBaseEncoded function before,
> and I believe that's just the basepoint scalar multiplication, right?)

Well, scalarMultBase is that, -Encoded also encodes the output point.


>> X448 key generation is already delegated to Ed448 and X448 shared
>> secret calculation is intended to eventually also be delegated, which
>> would involve adding to Ed448 exactly the non-basepoint scalar
>> multiplication that appears to be needed here; but we do not have it
>> yet.
>
> What kind of expectations does Bouncy Castle have for such a scalar
> multiplication implementation? What kind of guarantees are required at
> minimum?

Constant-time, then performance within reasonable complexity/clarity.


> I'm willing to invest some time into looking into the scalar
> multiplication, but I have limited knowledge of such low-level
> implementations. I could do a naive one and with help from the community
> see if we can improve. Or alternative, if one knows of suitable
> reference material, I can try diving into the more complicated
> implementations.
>
> Would that be a possibility?

What I would suggest is that I put together a simple implementation that
makes use of:

    private static void scalarMultStraussVar(int[] nb, int[] np,
PointExt p, PointExt r)

That method calculates r = nb * basepoint + np * p, so by setting nb to
0 it should be usable to get correct answers. It is not constant-time
(only used for verification) but it will serve for initial testing.

I would then ask you to confirm that the changes are working
(particularly interop tests), and I can then work on the constant-time
implementation, for which I should have some time in a week or two.

Regards,
Pete Dettman


Reply | Threaded
Open this post in threaded view
|

Re: Accessing Point representation of Ed448 for ECDH implementation

Danny van Heumen
Hi,

On Mon, 10 Jun 2019 12:37:33 +0700
Peter Dettman <[hidden email]> wrote:

> On 9/6/19 11:03 pm, Danny van Heumen wrote:
> >> [...]
> >
> > Agree. I don't see a big problem there, either. That is, given my
> > limited knowledge. (I found the scalarMultBaseEncoded function
> > before, and I believe that's just the basepoint scalar
> > multiplication, right?)  
>
> Well, scalarMultBase is that, -Encoded also encodes the output point.

Well, yes, but also encoded in the right format, I believe.
I looked at scalarMultBase yesterday, but I'm not sure what
representation PointExt is. (And there was nothing documenting that
AFAICT.)

> >> [...]
> >
> > What kind of expectations does Bouncy Castle have for such a scalar
> > multiplication implementation? What kind of guarantees are required
> > at minimum?  
>
> Constant-time, then performance within reasonable complexity/clarity.

Okay, thank you. Good to know.

> > [...]
>
> What I would suggest is that I put together a simple implementation
> that makes use of:
>
>     private static void scalarMultStraussVar(int[] nb, int[] np,
> PointExt p, PointExt r)
>
> That method calculates r = nb * basepoint + np * p, so by setting nb
> to 0 it should be usable to get correct answers. It is not
> constant-time (only used for verification) but it will serve for
> initial testing.

Wow, that would be great!

I currently have a class representing a Point, which requires the
following operations. I suspect you would already provide all of them,
but just to be explicit:

- Addition
- Multiplication
- Negation
- Encoding/Decoding to byte-representation (which I suspect will
  already be the default state for points as handled by the user of BC)

> I would then ask you to confirm that the changes are working
> (particularly interop tests), and I can then work on the constant-time
> implementation, for which I should have some time in a week or two.

The current code base already contains tests that verify explicitly
against my "amateur-implementation". So, simply replacing my
implementation with yours should be sufficient to do verification. (And
then figure out on which side the error is on.) It should be simple
enough.

I already managed to build BC libraries from the github mirror
(https://github.com/bcgit/bc-java.git), so just point me to a branch
when you are ready and I will build the binaries myself.

Again, I really appreciate the quick response/action.

Regards,
Danny