Compatibility with cloudflare/circl

[cblaettl]

Hi,

First of all thank you very much for this awesome library!

Im currently working on a Go project which has to work with SCIDH keys generated by this library.
I'd like to use cloudflare/circl for the Go part, but I couldn't get them to work yet.

Do you know if these libraries are even compatible at all? Or maybe you can point me in the right direction.

I've tried the following:

package main

import (
	"crypto/rand"
	"encoding/base64"
	"fmt"

	"github.com/cloudflare/circl/dh/csidh"
)

var rng = rand.Reader

func main() {
	var privateKey csidh.PrivateKey
	var publicKey csidh.PublicKey

	if err := csidh.GeneratePrivateKey(&privateKey, rng); err != nil {
		panic(err)
	}

	csidh.GeneratePublicKey(&publicKey, &privateKey, rng)

	var privateOut [37]byte

	if ok := privateKey.Export(privateOut[:]); !ok {
		panic("failed to export")
	}

	fmt.Printf("privateKeyA: %s\n", base64.StdEncoding.EncodeToString(privateOut[:]))

	var publicOut [64]byte

	if ok := publicKey.Export(publicOut[:]); !ok {
		panic("failed to export")
	}

	fmt.Printf("publicKeyA: %s\n", base64.StdEncoding.EncodeToString(publicOut[:]))
}

and then tried to generate a public key from the printed private key. But that failed:

echo "LiTrMfNR3E4iHSTFEiu8I+ETtBVV7z79Ub+0vk/QsERcvu0kuw=="|sibc csidh-pubkey -
Traceback (most recent call last):
  File "/usr/local/bin/sibc", line 8, in <module>
    sys.exit(main())
  File "/usr/local/lib/python3.9/site-packages/click/core.py", line 1137, in __call__
    return self.main(*args, **kwargs)
  File "/usr/local/lib/python3.9/site-packages/click/core.py", line 1062, in main
    rv = self.invoke(ctx)
  File "/usr/local/lib/python3.9/site-packages/click/core.py", line 1668, in invoke
    return _process_result(sub_ctx.command.invoke(sub_ctx))
  File "/usr/local/lib/python3.9/site-packages/click/core.py", line 1404, in invoke
    return ctx.invoke(self.callback, **ctx.params)
  File "/usr/local/lib/python3.9/site-packages/click/core.py", line 763, in invoke
    return __callback(*args, **kwargs)
  File "/usr/local/lib/python3.9/site-packages/click/decorators.py", line 26, in new_func
    return f(get_current_context(), *args, **kwargs)
  File "/usr/local/lib/python3.9/site-packages/sibc/__main__.py", line 153, in csidh_pubkey
    click.echo(b64encode(algo.public_key(b64decode(secret_key.read()))))
  File "/usr/local/lib/python3.9/site-packages/sibc/csidh/__init__.py", line 133, in public_key
    xy = self.gae.GAE_at_0(sk)
  File "/usr/local/lib/python3.9/site-packages/sibc/csidh/gae_df.py", line 58, in GAE_at_0
    return self.GAE(
  File "/usr/local/lib/python3.9/site-packages/sibc/csidh/gae_df.py", line 626, in GAE
    E_k, m, e = self.evaluate_strategy(
  File "/usr/local/lib/python3.9/site-packages/sibc/csidh/gae_df.py", line 277, in evaluate_strategy
    s_i = sign(e[pos])  # Sign of e[pos]
IndexError: tuple index out of range

Thanks a lot in advance. :)

EDIT: I've also tried other test cases but they all seem to fail. Maybe I have to adjust some parameters for this to work?

[JJChiDguez]

Hello there!

It's good to read you are enjoying and using the library. I hope this library helps increase the use of isogeny-based primitives (at least, as a toolkit for learning/using isogenies in practice).

Answering

Do you know if these libraries are even compatible at all?

In summary, both libraries are not directly compatible; see below the main difference:

1. The Go-code is doing a non-constant-time implementation of csidh (at least at field operation level).
2. The keyspace from the Go-code is [-5,5]⁷⁴ ≈ 2²⁵⁶, that is, private keys are integer vectors e with entries eᵢ in [-5,5]. On the other hand, sibc works with "optimal" bound vectors, that is, eᵢ is an integer in [-mᵢ, mᵢ] where each mᵢ is fixed and possibly different from another mⱼ.
3. In the Go-code private keys are arrays of 37=74/2 bytes (see var privateOut [37]byte), while in the csidh-default configuration of sibc, this array has length 74.

As a consequence, private keys generated by the Go-code are not compatible with the private keys from sibc because of

1. Different private key entry ranges: eᵢ is an integer in [-mᵢ, mᵢ]. For instance, sibc use these bounds;
2. Different array lengths (I think this is the main issue why sibc is failing, it tries to access to (for example) the 38th entry of e, but it fails because the Go-code output has just 37 entries).

[cblaettl]

Thanks, for your insightful answer.

I'm working on a project with the goal to port the vula project to Go.
Having this library compatible with cloudflare/circl is currently the biggest challenge for the project.

Would it be possible to adjust these parameters to make them work together? And if yes, how big of an effort would it be?
For now I don't worry about constant-time or not.

I've also opened an issue on the cloudflare repo, to maybe help speed-up this process.

[JJChiDguez]

No problem!

I am not sure how considerable effort would require. At first, It could be easy, but let me check it and comment/discuss it later.