wultra / sike-java

SIKE for Java is a software library that implements experimental supersingular isogeny cryptographic schemes that aim to provide protection against attackers running a large-scale quantum computer.

⚠️ In July 2022, Wouter Castryck (KU Leuven) and Thomas Decru (KU Leuven) published an article "An efficient key recovery attack on SIDH" which provides an efficient attack on SIKE. As a result, the implementation below should only be used for research purposes and not for production deployment.

SIKE for Java

SIKE for Java is a software library that implements experimental supersingular isogeny cryptographic schemes that aim to provide protection against attackers running a large-scale quantum computer. The library is a result of a security research cooperation between Wultra and Raiffeisen Bank International Competence Centre for Cryptology and Biometrics.

We advise the readers who are new to SIDH or SIKE to check the official resources, which provide many educational materials.

• The "Supersingular isogeny key exchange for beginners" article explains the main concepts nicely.
• Official SIKE documentation: https://sike.org
• SIKE specification from round 3 NIST submission: https://sike.org/files/SIDH-spec.pdf
• The "Mathematics of Isogeny Based Cryptography" paper provides an introduction to the mathematics used by these algorithms.

Features

The port of SIKE to Java provides the following functionality:

• Key generation
• SIDH key exchange
• SIKE public key encryption (PKE)
• SIKE key encapsulation mechanism (KEM)

Following SIKE parameter sets are supported:

• SIKEp434
• SIKEp503
• SIKEp610
• SIKEp751

The project provides implementation ports for both reference and optimized implementations, and it is possible to switch the implementation type. The port currently does not support compressed keys. The field arithmetics is based on Java BigInteger in the reference implementation. The optimized implementation uses an unsigned long array representation of field elements, and the field arithmetics does not use any native code.

The private and public keys can be exported into:

• an octet representation as defined in the SIKE specification
• a byte array representation useful for a more optimal encoding

The private and public keys can be imported from either of these serialization formats.

The port includes KAT test vectors for all supported SIKE parameter sets.

Note that this port's aim was not to create a 100% identical port with the C code because the original syntax is not object-oriented. There are small differences between the C and Java implementations. However, given the passing KAT test vectors, the implementations should be 100% compatible.

Getting Started

If you prefer watching a video over reading a manual, you can watch the Getting Started Video which provides an introduction to using this library.

Usage

SIKE for Java provides an easy to use interface for generating keys and computing shared secrets.

Installation

Install Using Maven

The artifacts are currently not published in any public repository given the experimental stage of the implementation. Clone the project and install the artifact in the local Maven repository to use the library by running the following commands:

$ git clone https://github.com/wultra/sike-java.git
$ cd sike-java
$ git checkout tags/0.1.0 -b tags/0.1.0
$ mvn clean install

After that, add the following dependency in your project pom.xml file:

<dependency>
    <groupId>com.wultra.security</groupId>
    <artifactId>sike-java</artifactId>
    <version>0.1.0</version>
</dependency>

Use JAR File

Alternatively, use a pre-compiled sike-java.jar artifact from the releases page.

Initialization

As the first step, initialize the Bouncy Castle provider:

Security.addProvider(new BouncyCastleProvider());

On Android, first remove the default Bouncy Castle provider:

Security.removeProvider("BC");
Security.addProvider(new BouncyCastleProvider());

Initialize Bouncy Castle at the application start before using any of the SIKE for Java functionality.

Before generating keys, choose one of the available algorithm parameter sets depending on the desired NIST security level and parameter size (in bytes):

SIKE Parameter Set	NIST Security Level	Private Key Size	Public Key Size	Shared Secret Size
SIKEp434	1	374	330	16
SIKEp503	2	434	378	24
SIKEp610	3	524	462	24
SIKEp751	5	644	564	32

Two implementations are available:

• REFERENCE - slow implementation with a focus on readability of code
• OPTIMIZED - fast implementation with a focus on performance and security

The selected SIKE parameters need to be created using:

SikeParam sikeParam = new SikeParamP434(ImplementationType.OPTIMIZED);

Generating Keys

Generate key pairs using the KeyGenerator class:

KeyGenerator keyGenerator = new KeyGenerator(sikeParam);

Before generating a key pair, decide whether the party is ALICE or BOB.

For SIKE, ALICE is the server, and BOB is the client that initiates the communication.

To generate a key pair for ALICE, use:

KeyPair keyPairA = keyGenerator.generateKeyPair(Party.ALICE);

To generate a key pair for BOB, use:

KeyPair keyPairB = keyGenerator.generateKeyPair(Party.BOB);

Obtain the keys from the key pair using:

PrivateKey priv = keyPair.getPrivate();
PublicKey pub = keyPair.getPublic();

To export the keys into a byte array, call either of these methods:

• getEncoded() - returns the byte array representation of the key
• toOctetString() - converts the key to an octet string as defined in SIKE specification, you need to cast the key to SidhPrivateKey or SidhPublicKey to access this method

Obtain the numeric representation of keys using:

• priv.getKey() - returns the FpElement representing the private key
• pub.getPx() - returns the Fp2Element representing the public key element phi(Px)
• pub.getQx() - returns the Fp2Element representing the public key element phi(Qx)
• pub.getRx() - returns the Fp2Element representing the public key element phi(Rx)

Obtain the BigInteger representations of the keys using:

• priv.getM() - returns the BigInteger representing the private key
• pub.getPx().getX0().getX() - returns the BigInteger representing the real part of public key x coordinate phi(Px)
• pub.getPx().getX1().getX() - returns the BigInteger representing the imaginary part of public key x coordinate phi(Px)

Obtaining BigInteger representations of x coordinates of phi(Qx) and phi(Rx) is analogous to phi(Px).

Import private keys from their byte array representation:

SikeParam sikeParam = new SikeParamP434(ImplementationType.OPTIMIZED);
byte[] secret = secretBytes;
PrivateKey priv = new SidhPrivateKey(sikeParam, Party.ALICE, secret);

It is also possible to import private keys from their octet string representation:

SikeParam sikeParam = new SikeParamP434(ImplementationType.OPTIMIZED);
String secret = secretOctets;
PrivateKey priv = new SidhPrivateKey(sikeParam, Party.ALICE, secret);

Finally, it is also possible to import private keys from their BigInteger representation:

SikeParam sikeParam = new SikeParamP434(ImplementationType.OPTIMIZED);
BigInteger secret = new BigInteger(secretNumber);
PrivateKey priv = new SidhPrivateKey(sikeParam, Party.ALICE, secret);

Once having a private key, derive the public key using:

PublicKey pub = keyGenerator.derivePublicKey(Party.ALICE);

Public keys can also be imported from various serialization formats using the SidhPublicKey class constructors.

SIDH Key Agreement

SIDH is an underlying algorithm used in SIKE. Unlike SIKE, SIDH alone provides insufficient security (it is an IND-CPA scheme) and should only be used with ephemeral keys on both sides of the key exchange. As a result, we recommend not using SIDH for anything else but experiments. This documentation mentions SIDH mostly for the purpose of completeness.

⚠️ Continue Reading About SIDH

After initializing the keys for both parties, it is easy to compute the shared secret using SIDH. The process is the same for both parties. Similarly to DH or ECDH, SIDH uses the opposite public and private keys:

Sidh sidh = new Sidh(sikeParam);
Fp2Element secretA = sidh.generateSharedSecret(Party.ALICE, keyPairA.getPrivate(), keyPairB.getPublic());
Fp2Element secretB = sidh.generateSharedSecret(Party.BOB, keyPairB.getPrivate(), keyPairA.getPublic());

Obtain the byte array representing secret j-invariants of both sides using:

byte[] encoded = secret.getEncoded();

Both secrets secretA and secretB are equal in case the key agreement succeeded. The shared secret sizes match the Fp2Element sizes in the chosen SIKE parameter set, which is 1/3 of the public key size. Using a hashing function on the shared secret value is advised to obtain shorter shared secret sizes as well as eliminate any risks related to using the numeric representation of the j-invariant directly.

SIKE Key Encapsulation

The SIKE encapsulation and decapsulation process is different for either of the parties and starts on BOB's side:

SikeParam sikeParam = new SikeParamP434(ImplementationType.OPTIMIZED);
KeyGenerator keyGenerator = new KeyGenerator(sikeParam);
KeyPair keyPairB = keyGenerator.generateKeyPair(Party.BOB);

BOB transports his public key keyPairB to ALICE, who uses the public key for the encapsulation phase of the KEM:

Sike sike = new Sike(sikeParam);
EncapsulationResult encapsulationResult = sike.encapsulate(keyPairB.getPublic());

At this point, ALICE can calculate the shared secret and the encrypted message:

byte[] secretA = encapsulationResult.getSecret();
EncryptedMessage encryptedMessage = encapsulationResult.getEncryptedMessage();

The encryptedMessage is converted into a byte array representation encodedMessage and transported back to BOB who uses the public key and cipher text included in the message for the decapsulation phase of KEM. Obtain the byte array from the encrypted message for transport over network:

byte[] encodedMessage = encryptedMessage.getEncoded();

The encrypted message is recreated by BOB after the message transport and decapsulation is performed:

EncryptedMessage transportedMessage = new EncryptedMessage(sikeParam, encodedMessage);
byte[] secretB = sike.decapsulate(keyPairB.getPrivate(), keyPairB.getPublic(), transportedMessage);

Both secrets secretA and secretB are equal in case the key encapsulation and decapsulation succeeded. The shared secret sizes are listed in the table presented in the Initialization chapter. Using a hashing function on the shared secret value is advised to obtain shorter shared secret sizes.

Note that SIKE provides higher security than SIDH. It is an IND-CCA2 scheme and can be used with long term keys.

License

SIKE for Java is currently licensed using GNU AGPLv3 license. We may change the license in the future to a less restrictive one. Please consult us at [email protected] for the software use.

Oracle and Java are registered trademarks of Oracle and/or its affiliates. Other names may be trademarks of their respective owners.

sike-java's Issues

Use key generation logic from optimized implementation

The optimized SIKE implementation uses a slightly different logic when checking bounds for generated keys than the reference implementation (currently used). We should switch to this logic to avoid any differences with the official optimized implementation during key generation.

See:
https://github.com/microsoft/PQCrypto-SIKE/blob/master/Optimized_Implementation/portable/SIKEp503/sidh.c#L61
https://github.com/microsoft/PQCrypto-SIKE/blob/master/Optimized_Implementation/portable/SIKEp503/sidh.c#L72

Add public key validation for encapsulation

During decapsulation, the public key is verified perfectly. We should check whether validation is required during encapsulation.

Although the official SIKE implementation does not contain public key validation for decapsulation, several validation functions are available in the SIDH signature project:
https://github.com/yhyoo93/isogenysignature/blob/master/validate.c

SIKE round 3 support

The round 3 specification contains following changes:

• alg. 11 - bugfix of step 3 (the bug was only in specification, the implementation is correct)
• alg. 15 - changed steps 18 - 21 (the bug was only in specification, the implementation is correct)
• alg. 17 - bugfix of division by zero (should be already implemented)
• alg. 18 - bugfix of division by zero (should be already implemented)
• alg. 38 - bugfix of division by zero (should be already implemented)
• alg. 39 - bugfix of division by zero (should be already implemented)
• appendix D - check newly published optimized strategies for fast isogeny computations
• optimizations in methods: get_3_isog, eval_3_isog, xDBLADD, swap_points, fp2sqr_mont, fp2mul_mont, random_mod_order_A, random_mod_order_B, crypto_kem_dec and others
• review commits: https://github.com/microsoft/PQCrypto-SIDH/commits/master

Implement testing using KAT files

SIKE project publishes the KAT files which contain test vectors:

https://sike.org/files/KAT

Implement the parsing of KAT files, seed-based randomization and conversion from octet format. Prepare test of SIKEp434 against the related KAT file.

Get rid of import javax.xml.bind.DatatypeConverter in KatTester

On Jave 9+, the tests fail due to the use of the class that is a part of Java EE.

Since we use BC anyway, I suggest using byte[] Hex.decode(String s) instead.

Prepare the first release

Improve performance of BigInteger math

Currently, BigInteger math is used for field mathematics. We should consider switching to a faster implementation:

• BigInt from Huldra: https://github.com/bwakell/Huldra
• our own faster implementation in low level code

Preferably, ASM math should not be used to avoid portability issues with the library.

Bump BouncyCastle to 1.66

Verify Fp2ElementRef implementation

Some of the methods in Fp2Element class differ from the official implementation (e.g. sqrt). Although these methods are well tested, we should compare the performance and security parameters with the official implementation.

Document how encrypted message is sent back to Bob

Currently, we assume that the encrypted message somehow materializes on Bob's side but maybe we should be more specific about what is actually sent back to Bob. This may lead to providing getEncoded() method (or a similar one) on the EncryptedMessage class.

Add test in which the optimized calculations are verified against the reference

We probably should also enhance our tests by adding the following tests:

• Optimized client => Reference server.
• Reference client => Optimized server.

Constant time implementation of public key comparison

The public key comparison relies on the BigInteger.equals() method which is not constant time.

Verify updated constants for round 3

The round 3 implementation of SIKE introduced changes in following constants for various SIKE parameters:

• SIDH_SECRETKEYBYTES
• NBITS_ORDER
• MAXBITS_ORDER

We should double check whether these changes have any impact on the SIKE for Java implementation.

Port reference implementation of SIKE to Java

Take the source code available at https://sike.org and port the reference implementation to Java.

Add JavaDoc for all methods

Java 15 reports missing JavaDoc for any method as a warning.

Add a size unit by the parameter table

Migrate to single page docs

Use Arrays.hashCode for arrays

Objects.hash(...) cannot be used with multiple arrays as parameters.

Port optimized implementation of SIKE to Java

Take the source code available at https://sike.org and port the optimized implementation to Java, except for the math optimizations in assembly language.

Review use of public keyword in tests

Since we use JUnit 5, we might get away with not using a public keyword on classes and test methods. Let's explore the best practices and fix the test code if needed.

Improve key encapsulation documentation

The key encapsulation example in the documentation mentions that Bob's public key is transported to Alice. The example is missing public key serialization and deserialization on Alice's side.

Make SIDH less visible in documentation

Fix the naming across the repository

Let's call the project SIKE for Java, to avoid any possible association of "SIKE Java" with a product branding or name. We need to specifically make sure that "we implement SIKE algorithm, in a manner that is usable in Java programming language".

Add private non-arg constructor to classes that should not be instantiated directly

See the discussion under #51, i.e., UnsignedLong

Fix double checked locking when constructing SecureRandom

Currently, we use a code that may not work reliably. See discussion under #51.

Eliminate branching in SIKE decapsulation

As part of effort to eliminate potential side channel attacks, branching should be removed in SIKE decapsulation to prevent advanced timing attacks.

Add installation instructions to readme file

Implement subtraction with correction using 2p and 4p

The round 3 SIKE implementation introduces subtraction with reduction using 2p and 4p. This change should have a minor impact on performance.

Add .travis.yml file

Add support for additional SIKE parameters

Provide support for all SIKE parameters from the submission package:
https://sike.org/files/sike.tar.gz

Separate constants in reference and optimized implementations

The MontgomeryCurve class contains fields a and b. The a constant used in reference implementation is different from the A constant used in optimized implementation. Furthermore, the b constant is not used in optimized implementation.

We should separate the constant classes for each of the implementations and encapsulate all constants.

Documentation does not mention where to get Sike instance

There is no:

Sike sike = new Sike(...);

Add info about ECC to Readme docs