openssh unix dev - Feb 2019 - [PATCH] use ecdh/X25519 from openssl when possible (openssl-1.1.0+)

See attached:

(1) patch against 7.9p1, tested with openssl 1.1.0j and openssl 1.1.1a on
linux/i386; passes regression
test and connects to unpatched sshd without problems;

I hacked a bit regress/unittests/kex, and benchmarked
    do_kex_with_key("curve25519-sha256 at libssh.org", KEY_ED25519,
256);
Before:
  0.3295s per call
After:
  0.2183s per call

That is, 50% speedup; assuming ed25519 (added to openssl in 1.1.1) takes about
same time as ecdh/x25519,
there are potential for total 200% speedup in KEX.

(2) rebased patch against git master; passes regression test;

I relied on presence of NID_X25519 for autodetection; probably it makes sense to
check if is
actually working it autoconf; then again, maybe not (it won't work when
cross-compiling anyway).

P.S. given amount of feedback I received so far, it seems everyone follows motto
"it cannot be secure
if it is not slow".
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 7.9p1-0001-use-kex-x25519-from-openssl-when-possible.patch
Type: text/x-patch
Size: 9337 bytes
Desc: not available
URL:
<http://lists.mindrot.org/pipermail/openssh-unix-dev/attachments/20190217/7dce2537/attachment-0002.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: master-0001-use-kex-x25519-from-openssl-when-possible.patch
Type: text/x-patch
Size: 11456 bytes
Desc: not available
URL:
<http://lists.mindrot.org/pipermail/openssh-unix-dev/attachments/20190217/7dce2537/attachment-0003.bin>

On 17.02.2019 15:46, Yuriy M. Kaminskiy wrote:
> See attached:
> 
> I hacked a bit regress/unittests/kex, and benchmarked
>     do_kex_with_key("curve25519-sha256 at libssh.org",
KEY_ED25519, 256);
> Before:
>   0.3295s per call
> After:
>   0.2183s per call
> 
> That is, 50% speedup; assuming ed25519 (added to openssl in 1.1.1) takes
about same time as ecdh/x25519,
> there are potential for total 200% speedup in KEX.
(Very slightly tested) patch attached.

Guess what? I was wrong:
    0.0113s per call (with both curve25519 and ed25519 patches applied, and
openssl-1.1.1a)

2800% faster.

openssh's ed25519 was not just slow. It was *very* slow.

FWIW, ecdh-sha2-nistp256/ecdsa-sha2-nistp256:
    0.0288s per call

(still 1000% faster than current openssh's {ed,curve}25519 combo)

(I also attached patch I used for benchmarking, it is *not* for upstream
inclusion for sure)
> P.S. given amount of feedback I received so far, it seems everyone follows
motto "it cannot be secure
> if it is not slow".
-------------- next part --------------
A non-text attachment was scrubbed...
Name: master-0001-use-ed25519-sig-from-openssl-when-possible.patch
Type: text/x-patch
Size: 10900 bytes
Desc: not available
URL:
<http://lists.mindrot.org/pipermail/openssh-unix-dev/attachments/20190218/8df648e6/attachment-0002.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: test_kex-benchmark.patch
Type: text/x-patch
Size: 1005 bytes
Desc: not available
URL:
<http://lists.mindrot.org/pipermail/openssh-unix-dev/attachments/20190218/8df648e6/attachment-0003.bin>

On 17.02.2019 15:46, Yuriy M. Kaminskiy wrote:
> See attached:
> 
> (1) patch against 7.9p1, tested with openssl 1.1.0j and openssl
> 1.1.1a on linux/i386; passes regression test and connects to
> unpatched sshd without problems;
As ed25519-from-openssl patch came out a bit less convoluted, I've
tried to do same with ecdh/x25519.

So, here are V2:
(1) use openssl-1.1.1a api,
(2) [optional] emulate openssl-1.1.1a api for openssl-1.1.0.

Unfortunately, it was a bit slower (as it needs to (de)serialize
private key):
> I hacked a bit regress/unittests/kex, and benchmarked
>     do_kex_with_key("curve25519-sha256 at libssh.org",
KEY_ED25519, 256);
> Before:
>   0.3295s per call
> After:>   0.2183s per call
openssl/1.1.0j, curve25519 + ecdsa-sha256 (openssh's builtin eddsa is too
slow,
so difference between V1 and V2 is lost in noise, so I replaced ed25519
with ecdsa/p256 for this test)

ecdh/25519 V1:
   0.0185s per call
ecdh/25519 V2:
   0.0205s per call

openssl/1.1.1a, curve25519 + ed25519 (with ed25519 patch)
ecdh/25519 V1:
    0.0115s per call
ecdh/25519 V2:
    0.0131s per call (worse by 14%)
> That is, 50% speedup; assuming ed25519 (added to openssl in 1.1.1)
> takes about same time as ecdh/x25519, there are potential for total
> 200% speedup in KEX.
> 
> (2) rebased patch against git master; passes regression test;
> 
> I relied on presence of NID_X25519 for autodetection; probably it
> makes sense to check if is actually working it autoconf; then again,
> maybe not (it won't work when cross-compiling anyway).
> 
> P.S. given amount of feedback I received so far, it seems everyone
> follows motto "it cannot be secure if it is not slow".
-------------- next part --------------
A non-text attachment was scrubbed...
Name: master-0001-use-curve25519-ecdh-from-openssl-1.1.1a-when-possibl.patch
Type: text/x-patch
Size: 6638 bytes
Desc: not available
URL:
<http://lists.mindrot.org/pipermail/openssh-unix-dev/attachments/20190218/a5d30a2d/attachment-0002.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: master-0002-curve25519-ecdh-emulate-openssl-1.1.1-API-on-openssl.patch
Type: text/x-patch
Size: 4836 bytes
Desc: not available
URL:
<http://lists.mindrot.org/pipermail/openssh-unix-dev/attachments/20190218/a5d30a2d/attachment-0003.bin>

Suspect you'd get more traction by targeting libressl.? As that is what 
upstream uses.

Ben

Yuriy M. Kaminskiy wrote on 2/18/19 2:29 PM:
> On 17.02.2019 15:46, Yuriy M. Kaminskiy wrote:
>> See attached:
>>
>> (1) patch against 7.9p1, tested with openssl 1.1.0j and openssl
>> 1.1.1a on linux/i386; passes regression test and connects to
>> unpatched sshd without problems;
> As ed25519-from-openssl patch came out a bit less convoluted, I've
> tried to do same with ecdh/x25519.
>
> So, here are V2:
> (1) use openssl-1.1.1a api,
> (2) [optional] emulate openssl-1.1.1a api for openssl-1.1.0.
>
> Unfortunately, it was a bit slower (as it needs to (de)serialize
> private key):
>
>> I hacked a bit regress/unittests/kex, and benchmarked
>>      do_kex_with_key("curve25519-sha256 at libssh.org",
KEY_ED25519, 256);
>> Before:
>>    0.3295s per call
>> After:>   0.2183s per call
> openssl/1.1.0j, curve25519 + ecdsa-sha256 (openssh's builtin eddsa is
too slow,
> so difference between V1 and V2 is lost in noise, so I replaced ed25519
> with ecdsa/p256 for this test)
>
> ecdh/25519 V1:
>     0.0185s per call
> ecdh/25519 V2:
>     0.0205s per call
>
> openssl/1.1.1a, curve25519 + ed25519 (with ed25519 patch)
> ecdh/25519 V1:
>      0.0115s per call
> ecdh/25519 V2:
>      0.0131s per call (worse by 14%)
>
>> That is, 50% speedup; assuming ed25519 (added to openssl in 1.1.1)
>> takes about same time as ecdh/x25519, there are potential for total
>> 200% speedup in KEX.
>>
>> (2) rebased patch against git master; passes regression test;
>>
>> I relied on presence of NID_X25519 for autodetection; probably it
>> makes sense to check if is actually working it autoconf; then again,
>> maybe not (it won't work when cross-compiling anyway).
>>
>> P.S. given amount of feedback I received so far, it seems everyone
>> follows motto "it cannot be secure if it is not slow".
>
>
> _______________________________________________
> openssh-unix-dev mailing list
> openssh-unix-dev at mindrot.org
> https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev