bouncycastle fails NTRU generation

Question

There are three types of default security levels of NTRU, implemented in bouncy-castle:

 1. NTRUSigningKeyGenerationParameters.TEST157
 2. NTRUSigningKeyGenerationParameters.APR2011_439
 3. NTRUSigningKeyGenerationParameters.APR2011_743

First two are generated normally, but when I try to generate the tird one, I get the next Exception:

SEVERE: Servlet.service() for servlet [mvc-dispatcher] in context with path [] threw exception [Request processing failed; nested exception is java.lang.IllegalStateException: Signing failed: too many retries (max=100)] with root cause java.lang.IllegalStateException: Signing failed: too many retries (max=100)

Here is piece of my code:

NTRUSigningPrivateKeyParameters ntruSigningPrivateKeyParameters1 = null;

    NTRUSigner ntruSigner = new NTRUSigner(ntruSigningKeyGenerationParameters.getSigningParameters());

    try {
        ntruSigningPrivateKeyParameters1 = new NTRUSigningPrivateKeyParameters(ntruSigningPrivateKeyParameters.getEncoded(), ntruSigningKeyGenerationParameters);
    } catch (IOException e) {

        e.printStackTrace();
    }

    ntruSigner.init(true, ntruSigningPrivateKeyParameters);
    byte [] res = ntruSigner.generateSignature();

Calling ntruSigner.generateSignature() with the third set of parameters leads to a such Exception.

Does anyone knows how to solve it?

Answer 1

Currently, it's a bug, so there are two solutions:

1. use another library - tbuktu's github project (bouncy-castle is using it with some modifications, as I see)
2. download sources, catch the bug of this generation parameter, solve it and pack into library for a project

Answer 2

It's not really a bug in the code. The problem is that the norm bound in the APR2011_743 and APR2011_743_PROD parameter sets is too low which means that the signer is unable to generate a valid signature.

For N=743, q=2048 and beta=0.127 you should choose a norm bound of around 545 (see equation 10 in J. Hoffstein et al, Performance improvements and a baseline parameter generation algorithm for NTRUSign) but the parameter sets in BouncyCastle use normBound=405. Changing this solves the issue.

Answer 3

Updating the normBound does appear to fix the issue, however I should point out the NTRUSigner class is now deprecated in Bouncy Castle. The NTRU signing algorithm was shown to be badly broken just over a year ago. See:

http://www.di.ens.fr/~ducas/NTRUSign_Cryptanalysis/DucasNguyen_Learning.pdf

for details.