An infinite loop occurs when ED25519 signature verification

[jr981008]

jdk version：1.8.0_382
bc version: bcpkix-jdk18on-1.74

A 20-thread Vertx server processes ED25519 signature verification. When the TPS reaches 10000, an infinite loop occurs. Here is the stack of the problem thread and the code I used.

stack snap：
"vert.x-eventloop-thread-15" Id=176 RUNNABLE
at org.bouncycastle.math.ec.rfc8032.Scalar25519.reduceBasisVar(null:-1)
at org.bouncycastle.math.ec.rfc8032.Ed25519.implVerify(null:-1)
at org.bouncycastle.math.ec.rfc8032.Ed25519.verify(null:-1)
at org.bouncycastle.crypto.params.Ed25519PublicKeyParameters.verify(null:-1)
at org.bouncycastle.crypto.signers.Ed25519Signer$Buffer.verifySignature(null:-1)
at org.bouncycastle.crypto.signers.Ed25519Signer.verifySignature(null:-1)
at org.bouncycastle.jcajce.provider.asymmetric.edec.SignatureSpi.engineVerify(null:-1)
at java.security.Signature$Delegate.engineVerify(Signature.java:1392)
at java.security.Signature.verify(Signature.java:769)

code:

   private static boolean verify(String noce, String timestamp, String eccSign, byte[] eccPublicKey) {
        byte[] content = Bytes.concat(noce.getBytes(StandardCharsets.UTF_8),
            BytesGenerator.getTimestampOffsetBytes(Long.valueOf(timestamp)));
        boolean result = false;
        try {
            X509EncodedKeySpec x509EncodedKeySpec = new X509EncodedKeySpec(eccPublicKey);
            KeyFactory keyFactory = KeyFactory.getInstance("Ed25519");
            PublicKey publicKey = keyFactory.generatePublic(x509EncodedKeySpec);
            Signature signature = Signature.getInstance("Ed25519");
            signature.initVerify(publicKey);
            signature.update(content);
            result = signature.verify(Base64.decodeBase64(eccSign));
            if (!result) {
                RUNLOG.error("EccSignatureVerify failed. ");
            }
        } catch (Exception e) {
            RUNLOG.error("Exception happen ", e);
        }
        return result;
    }

This is an urgent question. We are not familiar with cryptographic algorithms. Thanks for any help.

[jr981008]

By attaching to process，get function param.
ScalarUtil.lessThan(last, Nu, Nv) is always false.

[jr981008]

ScalarUtil.getBitLength(last, p) It seems to keep flipping between the two values p[last]=-1 or 0.

ts=2024-03-11 21:59:43; [cost=7.03E-4ms] result=[[10,[-584333345,153520642,-831589256,2107610247,-966692209,14916415,-1902580523,463978880,1487883832,0,0,-1,-1,0,0,-1]],null,null]
method=org.bouncycastle.math.ec.rfc8032.ScalarUtil.getBitLength location=AtEnter
ts=2024-03-11 21:59:43; [cost=0.001684ms] result=[[10,[622396389,-1262780587,502664275,298457412,-109443955,-423812610,1472549535,1017851823,-414652022,-1,-1,-1,-1,0,0,-1]],null,null]
method=org.bouncycastle.math.ec.rfc8032.ScalarUtil.getBitLength location=AtEnter
ts=2024-03-11 21:59:43; [cost=0.00116ms] result=[[10,[-584333345,153520642,-831589256,2107610247,-966692209,14916415,-1902580523,463978880,1487883832,0,0,-1,-1,0,0,-1]],null,null]
method=org.bouncycastle.math.ec.rfc8032.ScalarUtil.getBitLength location=AtEnter
ts=2024-03-11 21:59:43; [cost=8.9E-4ms] result=[[10,[622396389,-1262780587,502664275,298457412,-109443955,-423812610,1472549535,1017851823,-414652022,-1,-1,-1,-1,0,0,-1]],null,null]
method=org.bouncycastle.math.ec.rfc8032.ScalarUtil.getBitLength location=AtEnter
ts=2024-03-11 21:59:43; [cost=8.36E-4ms] result=[[10,[-584333345,153520642,-831589256,2107610247,-966692209,14916415,-1902580523,463978880,1487883832,0,0,-1,-1,0,0,-1]],null,null]

[jr981008]

ScalarUtil.addShifted_NP(last, s, Nu, Nv, p); param always like this:
ts=2024-03-11 22:05:32; [cost=5.09E-4ms] result=[[10,0,[-1754378251,1998656237,-1462065216,-396282015,-1983421555,-2077490918,1914529897,49125049,1010209410,-553872943,1902535853,0,0,0,0,0],[-1206729734,1416301229,-1334253532,1809152835,-857248254,438729024,919837237,-553872943,1902535853,0,0,0,0,0,0,0],[622396389,-1262780587,502664275,298457412,-109443955,-423812610,1472549535,1017851823,-414652022,-1,-1,-1,-1,0,0,-1]],null,null]

[jr981008]

ScalarUtil.subShifted_NP alway like this:
ts=2024-03-11 22:07:19; [cost=4.79E-4ms] result=[[10,0,[-1716315207,889396293,-1790990196,2009785645,1235409578,1808580185,1484498910,1530955753,2083441220,-553872943,1902535853,0,0,0,0,0],[-1206729734,1416301229,-1334253532,1809152835,-857248254,438729024,919837237,-553872943,1902535853,0,0,0,0,0,0,0],[-584333345,153520642,-831589256,2107610247,-966692209,14916415,-1902580523,463978880,1487883832,0,0,-1,-1,0,0,-1]],null,null]
method=org.bouncycastle.math.ec.rfc8032.ScalarUtil.subShifted_NP location=AtEnter
ts=2024-03-11 22:07:19; [cost=5.01E-4ms] result=[[10,0,[-1716315207,889396293,-1790990196,2009785645,1235409578,1808580185,1484498910,1530955753,2083441220,-553872943,1902535853,0,0,0,0,0],[-1206729734,1416301229,-1334253532,1809152835,-857248254,438729024,919837237,-553872943,1902535853,0,0,0,0,0,0,0],[-584333345,153520642,-831589256,2107610247,-966692209,14916415,-1902580523,463978880,1487883832,0,0,-1,-1,0,0,-1]],null,null]
method=org.bouncycastle.math.ec.rfc8032.ScalarUtil.subShifted_NP location=AtEnter
ts=2024-03-11 22:07:19; [cost=4.96E-4ms] result=[[10,0,[-1716315207,889396293,-1790990196,2009785645,1235409578,1808580185,1484498910,1530955753,2083441220,-553872943,1902535853,0,0,0,0,0],[-1206729734,1416301229,-1334253532,1809152835,-857248254,438729024,919837237,-553872943,1902535853,0,0,0,0,0,0,0],[-584333345,153520642,-831589256,2107610247,-966692209,14916415,-1902580523,463978880,1487883832,0,0,-1,-1,0,0,-1]],null,null]

[cipherboy]

@jr981008 Do you have the message, public key, and signature that produce this loop? Thank you!

Also, what is "TPS in "When the TPS reaches 10000"?

[jr981008]

tps: indicates that the method is invoked 10000 times per second.The 10000 requests use different public and private key pairs, which are generated using the bc method.
The key and message data cannot be extracted from the environment, but the method parameters in the infinite loop can be obtained now.

[jr981008]

Key generation function：

        KeyPairGenerator keyGen;
        try {
            keyGen = KeyPairGenerator.getInstance(algorithm, "BC");
        } catch (NoSuchAlgorithmException | NoSuchProviderException e) {
            RUN_LOG.error("init key pair failed. ", e);
            return null;
        }
        keyGen.initialize(keySize);
        return keyGen.generateKeyPair();
    }```

The content of the signature is an array of 84 bytes and an 8-byte timestamp.

[jr981008]

I will try to get the data from the test environment after reproducing it, seem not hard to reproduce. I guess maybe key pairs trigger some boundary values in some scenarios. I don't see concurrency problem.

[cipherboy]

Hi @jr981008, I created the following attempted reproducer:

Contents of Reproducer.java

import java.lang.Runnable;
import java.lang.Thread;

import java.nio.charset.StandardCharsets;

import java.security.KeyFactory;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.PrivateKey;
import java.security.PublicKey;
import java.security.Security;
import java.security.Signature;
import java.security.spec.X509EncodedKeySpec;

import org.bouncycastle.jce.provider.BouncyCastleProvider;
import org.bouncycastle.util.encoders.Base64;

public class Reproducer {
    public static void main(String[] argv) throws Exception {
        Security.addProvider(new BouncyCastleProvider());

        Thread[] threads = new Thread[1000];
        KeyPair[] keyPairs = new KeyPair[threads.length/10];
        for (int i = 0; i < threads.length; i++) {
            if (keyPairs[i/10] == null) {
               keyPairs[i/10] = generate();
            }

            KeyPair kp = keyPairs[i/10];
            Thread t = new Thread(new Runner(kp, 10000));
            t.start();
            threads[i] = t;
        }

        for (Thread t : threads) {
            t.join();
        }
    }

    private static byte[] Bytesconcat(byte[] a, byte[] b) {
        byte[] ret = new byte[a.length + b.length];
        System.arraycopy(a, 0, ret, 0, a.length);
        System.arraycopy(b, 0, ret, a.length, b.length);
        return ret;
    }

    static class Runner implements Runnable {
        KeyPair kp;
        int count;

        public Runner(KeyPair kp, int count) {
            this.kp = kp;
            this.count = count;
        }

        @Override
        public void run() {
            try {
                // 84 bytes per https://github.com/bcgit/bc-java/issues/1599#issuecomment-1988600677
                String noce = "123456789012345678901234567890123456789012345678901234567890123456789012345678901234";
                String timestamp = "12345678";

                for (int i = 0; i < count; i++) {
                    byte[] sig = sign(noce, timestamp, this.kp.getPrivate());
                    String b64Sig = new String(Base64.encode(sig), StandardCharsets.UTF_8);

                    if (!verify(noce, timestamp, b64Sig, this.kp.getPublic().getEncoded())) {
                        throw new RuntimeException("verification failed");
                    }
                }
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }

    private static byte[] sign(String noce, String timestamp, PrivateKey priv) throws Exception {
        byte[] content = Bytesconcat(noce.getBytes(StandardCharsets.UTF_8),
            timestamp.getBytes(StandardCharsets.UTF_8)
        );

        Signature signature = Signature.getInstance("Ed25519", "BC");
        signature.initSign(priv);
        signature.update(content);

        return signature.sign();
    }

    private static boolean verify(String noce, String timestamp, String eccSign, byte[] eccPublicKey) throws Exception {
        byte[] content = Bytesconcat(noce.getBytes(StandardCharsets.UTF_8),
            timestamp.getBytes(StandardCharsets.UTF_8)
        );

        boolean result = false;

        X509EncodedKeySpec x509EncodedKeySpec = new X509EncodedKeySpec(eccPublicKey);
        KeyFactory keyFactory = KeyFactory.getInstance("Ed25519", "BC");
        PublicKey publicKey = keyFactory.generatePublic(x509EncodedKeySpec);
        Signature signature = Signature.getInstance("Ed25519", "BC");
        signature.initVerify(publicKey);
        signature.update(content);
        result = signature.verify(Base64.decode(eccSign));
        if (!result) {
            throw new RuntimeException("EccSignatureVerify failed. ");
        }

        return result;
    }

    private static KeyPair generate() throws Exception {
        KeyPairGenerator keyGen;
        keyGen = KeyPairGenerator.getInstance("ed25519", "BC");
        return keyGen.generateKeyPair();
    }
}

Contents of run.sh

#!/bin/bash

set -euxo pipefail

if [ ! -e jars ]; then
    mkdir jars
    pushd jars
        wget https://downloads.bouncycastle.org/java/bcutil-jdk18on-174.jar https://downloads.bouncycastle.org/java/bctls-jdk18on-174.jar https://downloads.bouncycastle.org/java/bcprov-jdk18on-174.jar https://downloads.bouncycastle.org/java/bcprov-ext-jdk18on-174.jar https://downloads.bouncycastle.org/java/bcpkix-jdk18on-174.jar https://downloads.bouncycastle.org/java/bcpg-jdk18on-174.jar https://downloads.bouncycastle.org/java/bcmail-jdk18on-174.jar https://downloads.bouncycastle.org/java/bcjmail-jdk18on-174.jar
    popd
fi

classpath="jars/bcprov-ext-jdk18on-174.jar:jars/bctls-jdk18on-174.jar:jars/bcutil-jdk18on-174.jar:jars/bcpg-jdk18on-174.jar:jars/bcprov-jdk18on-174.jar:jars/bcpkix-jdk18on-174.jar:jars/bcjmail-jdk18on-174.jar:jars/bcmail-jdk18on-174.jar"

javac -classpath "$classpath" Reproducer.java
java -classpath "$classpath:." Reproducer

This runs 1000 threads, sharing 100 keys, with each thread doing 10000 sign+verify operations, waiting for each thread to stop afterwards. Any hung thread, while not detected, should prevent stopping.

On my system (Intel i7-13700H / OpenJDK 21.0.2+13-Ubuntu-123.10.1), this takes about 1.5 minutes. No hung threads were detected.

So I'm definitely curious to hear if I'm constructing data incorrectly or if you have more concrete data about how this occurs. :-)

Edit: I re-read and saw you said each request used a unique key pair, so I swapped a local copy to doing that; 1000 threads, each with 10000 operations with unique keys = 10M ops over 10M unique keys.

Updated Reproducers based on below

Go looks fine with this set of data:

package main

import (
    "crypto/ed25519"
    "encoding/base64"
    "encoding/hex"
    "fmt"
)

func main() { 
    x509PublicKey := []byte{
        48, 42, 48, 5, 6, 3, 43, 101, 112, 3, 33, 0, 56, 110, 124, -9 + 256,
        -71 + 256, -24 + 256, 53, 57, 51, -80 + 256, 127, 29, -72 + 256,
        -40 + 256, 77, 55, 32, -69 + 256, 102, 124, -67 + 256, -127 + 256,
        27, 49, 43, 78, 51, -122 + 256, 114, 51, -118 + 256, 109,
    }
    fmt.Println("X.509 publicKey: " + hex.EncodeToString(x509PublicKey))
    
    // First 11 bytes are ASN.1 header information.
    publicKey := x509PublicKey[12:]
    fmt.Println("raw publicKey: " + hex.EncodeToString(publicKey))
    
    content := []byte{
        65, 65, 65, 98, 76, 103, 67, 89, 108, 111, 65, 65, 65, 81, 73, 67, 72,
        110, 106, 74, 113, 50, 106, 117, 112, 84, 85, 71, 45, 90, 54, 105, 77,
        113, 104, 113, 49, 52, 103, 65, 72, 84, 72, 111, 100, 117, 118, 119,
        105, 72, 68, 102, 79, 89, 74, 50, 48, 119, 95, 119, 66, 108, 110, 53,
        68, 74, 57, 83, 97, 78, 97, 99, 83, 73, 104, 53, 51, 107, 98, 110, 113,
        110, 114, 57, 101, -17 + 256, 52, -59 + 256,
    }
    fmt.Println("content: " + hex.EncodeToString(content))
    
    sig, err := base64.StdEncoding.DecodeString("dNxDIj/CG5FX5oahRGYhpGQEZLjuSHfqfjljy12oshuQiSQd791/NkSOxMdhdK8TGZQyHafihIOzwqeQaUf6Dw==")
    if err != nil { 
        panic("failed to decode base64: " + err.Error())
    }
    fmt.Println("sig: " + hex.EncodeToString(sig))
    
    typed := ed25519.PublicKey(publicKey)
    ret := ed25519.Verify(typed, content, sig)
    fmt.Printf("ret: %v\n", ret)
}

and outputs:

X.509 publicKey: 302a300506032b6570032100386e7cf7b9e8353933b07f1db8d84d3720bb667cbd811b312b4e338672338a6d
raw publicKey: 386e7cf7b9e8353933b07f1db8d84d3720bb667cbd811b312b4e338672338a6d
content: 414141624c6743596c6f414141514943486e6a4a71326a75705455472d5a36694d716871313467414854486f64757677694844664f594a3230775f77426c6e35444a3953614e616353496835336b626e716e723965ef34c5
sig: 74dc43223fc21b9157e686a1446621a4640464b8ee4877ea7e3963cb5da8b21b9089241defdd7f36448ec4c76174af131994321da7e28483b3c2a7906947fa0f
ret: true

as does OpenSSL 3.x:

$ echo 302a300506032b6570032100386e7cf7b9e8353933b07f1db8d84d3720bb667cbd811b312b4e338672338a6d | xxd -r -p > key.pub
$ echo '414141624c6743596c6f414141514943486e6a4a71326a75705455472d5a36694d716871313467414854486f64757677694844664f594a3230775f77426c6e35444a3953614e616353496835336b626e716e723965ef34c5' | xxd -r -p > content.raw
$ echo '74dc43223fc21b9157e686a1446621a4640464b8ee4877ea7e3963cb5da8b21b9089241defdd7f36448ec4c76174af131994321da7e28483b3c2a7906947fa0f' | xxd -r -p > sig.raw
$ openssl pkeyutl -verify -pubin -inkey key.pub -keyform DER -rawin -in content.raw -sigfile sig.raw
Signature Verified Successfully

But C# is affected as well:

using System;

using Org.BouncyCastle.Crypto;
using Org.BouncyCastle.Crypto.Generators;
using Org.BouncyCastle.Crypto.Parameters;
using Org.BouncyCastle.Crypto.Signers;
using Org.BouncyCastle.Math.EC.Rfc8032;
using Org.BouncyCastle.Security;
using Org.BouncyCastle.Utilities;
using Org.BouncyCastle.Utilities.Encoders;


Ed25519PublicKeyParameters publicKey = new Ed25519PublicKeyParameters(
    Hex.DecodeStrict("386e7cf7b9e8353933b07f1db8d84d3720bb667cbd811b312b4e338672338a6d"));
byte[] content = Hex.DecodeStrict("414141624c6743596c6f414141514943486e6a4a71326a75705455472d5a36694d716871313467414854486f64757677694844664f594a3230775f77426c6e35444a3953614e616353496835336b626e716e723965ef34c5");
byte[] sig = Hex.DecodeStrict("74dc43223fc21b9157e686a1446621a4640464b8ee4877ea7e3963cb5da8b21b9089241defdd7f36448ec4c76174af131994321da7e28483b3c2a7906947fa0f");

ISigner signer = new Ed25519Signer();
signer.Init(false, publicKey);
signer.BlockUpdate(content, 0, content.Length);
Console.WriteLine(signer.VerifySignature(sig));

run via:

$ dotnet new console
$ # (edit Program.cs) 
$ dotnet add package BouncyCastle.Cryptography
$ dotnet run
... hangs ...

Similarly, with the reference code from RFC 8032 Appendix A:

from eddsa2 import Ed25519

public = bytes.fromhex("386e7cf7b9e8353933b07f1db8d84d3720bb667cbd811b312b4e338672338a6d")
msg = bytes.fromhex("414141624c6743596c6f414141514943486e6a4a71326a75705455472d5a36694d716871313467414854486f64757677694844664f594a3230775f77426c6e35444a3953614e616353496835336b626e716e723965ef34c5")
signature = bytes.fromhex("74dc43223fc21b9157e686a1446621a4640464b8ee4877ea7e3963cb5da8b21b9089241defdd7f36448ec4c76174af131994321da7e28483b3c2a7906947fa0f")

print(Ed25519.verify(public, msg, signature))

the result is good:

$ python3 ./cli.py
True

[jr981008]

Thank you for your prompt reply, I'm trying to reproduce and get the content of the messages that are having problems with the public-private key pairs, It's going to take a while.I will try get it as soon as possible.

[jr981008]

Same code verify true without endless loop when using bcpkix-jdk15on. any one help? @dghgit

[dghgit]

It's going to be bcprov that's carrying the Ed25519 implementation. Is this also for 1.74?

[jr981008]

The problem is with version 1.74 @dghgit ，Is there any way to fix it?

[dghgit]

Ah... so bcprov-jdk15on is referring to a much older release isn't it? We're looking into the issue with 1.77 at the moment.

[jr981008]

I've tried all versions from 1.74-1.77 and all of them have the infinite loop problem. Trying version 1.70 just to show that the problem is not always there, it should be in the latest version.

[cipherboy]

@jr981008 check out 9c16579; this should resolve the issue :-)

[dghgit]

There's also an updated release for Java 8 and later on https://www.bouncycastle.org/betas now.

[jr981008]

Thanks @dghgit @cipherboy support.This method is commonly used for identification and authentication, may be a serious security issue.

[dghgit]

Glad to hear it's working, we will get a new release out soon. One last request, in future for anything like this please contact us at feedback-crypto@bouncycastle.org first. With anything likely to be a security issue we're more a fix first, release, then publish kind of organization.

[dghgit]

@jr981008 I'm in the process of filing a CVE report for this one while we're working on the release - would you email us at feedback-crypto@bouncycastle.org and let us know if you wish to be acknowledged for the report and how you would like us to list you. Thanks.

[adelel1]

Hello, we are also seeing this in 1.75. Does this bug affect the LTS version 2.73? We're thinking of moving back to this LTS release.

[jr981008]

Affect 1.71~1.77.

[adelel1]

Arh, ok, thanks. @dghgit Thanks for quickly resolving the above. Looks like we're a couple of weeks behind. Just wondering when your able to get a new 2.73 / 1.78 release out with this fix in?

[cipherboy]

@adelel1 April 5th is our planned release date currently.

You can use the beta available here: https://downloads.bouncycastle.org/betas/ (note that the build date is incorrect, but the patch is present).

The LTS is also affected.

[adelel1]

@cipherboy Thanks for the date. Are they published to a repo we can access? Has the LTS been updated in the beta list? Its still at 2.73.5. Thanks

[dghgit]

I've put up a beta for the LTS release. It may be missing the hardware support, if so I'll deal with it a bit later, it fixes the Ed25519 issue though. It's uploaded to the betas area listed above.

[dghgit]

2.73.6-SNAPSHOT beta has now been updated to include hardware support.

[dghgit]

1.78/1.78.1 is now live (either fixes CVE-2024-30172, but if you're using OSGI on a container running Java 8 or later, use 1.78.1).