cryptopp Added overloaded functions in the donna source files that let the caller specify a HashTransformation

On the Crypto++ wiki, it says:

ed25519 uses SHA512 as the hash. It is hard wired into the source files and there is no way to change it without recompiling sources. In the future we may add overloaded functions that allow the caller to specify a HashTransformation.

I added a bunch of overloaded functions to donna.h, donna_32.cpp, and donna_64.cpp with a new parameter called hash (or sometimes hashTf where "hash" was already being used as a variable name), which is a reference to a HashTransformation derived class that the functions will use instead of SHA512. The original functions remain unchanged, so any code that uses them doesn't have to be rewritten.

I didn't add a way to specify a HashTransformation in the high level Crypto++ objects, mostly cause I was too lazy to figure out how it works. I might try and figure it out at some point, but for now the ability to specify a HashTransformation is limited to the low level Donna functions.

I also fixed two typos in donna.h:

namespace and are curve25519_mult() -> namespace are curve25519_mult()
<tt>pubkey</tt> -> <tt>publicKey</tt>

The comments stating "At the moment the hash function for signing is fixed at SHA512." have been removed as well.

Jul 06 '21 01:07 NinjaSnail1080

@NinjaSnail1080,

Sorry for the late reply. I wanted to mull over this...

I think the way to go with this is to make the hash a template parameter, and not a member function parameter. That is:

template <class HASH>
struct ed25519
{
    typedef ed25519Signer Signer;
    typedef ed25519Verifier Verifier;
};

And push the hash down into ed25519Signer and ed25519Verifier.

I think the only supported hashes are SHA-512, SHA-3 and BLAKE2b. Maybe we should put a compile time assert in there to verify HASH::DIGESTSIZE >= 32.

Jul 22 '21 12:07 noloader

You mean HASH::DIGESTSIZE >= 64.

Anyway, I went ahead and tried to implement this. I also had to edit the files bench3.cpp, validat7.cpp, and validat9.cpp since they test the ed25519 objects. But now, when I try to build the library, I get this error:

Undefined symbols for architecture x86_64:
  "CryptoPP::ed25519Signer<CryptoPP::SHA512>::ed25519Signer(unsigned char const*, unsigned char const*)", referenced from:
      CryptoPP::Test::TestEd25519() in validat7.o
  "CryptoPP::ed25519Signer<CryptoPP::SHA512>::ed25519Signer(CryptoPP::RandomNumberGenerator&)", referenced from:
      CryptoPP::Test::BenchmarkEllipticCurveAlgorithms(double, double) in bench3.o
  "CryptoPP::ed25519Signer<CryptoPP::SHA512>::ed25519Signer(CryptoPP::BufferedTransformation&)", referenced from:
      CryptoPP::Test::TestEd25519() in validat7.o
      CryptoPP::Test::ValidateEd25519() in validat9.o
  "CryptoPP::ed25519Verifier<CryptoPP::SHA512>::ed25519Verifier(unsigned char const*)", referenced from:
      CryptoPP::Test::TestEd25519() in validat7.o
  "CryptoPP::ed25519Verifier<CryptoPP::SHA512>::ed25519Verifier(CryptoPP::ed25519Signer<CryptoPP::SHA512> const&)", referenced from:
      CryptoPP::Test::BenchmarkEllipticCurveAlgorithms(double, double) in bench3.o
      CryptoPP::Test::ValidateEd25519() in validat9.o
  "CryptoPP::ed25519PublicKey<CryptoPP::SHA512>::AssignFrom(CryptoPP::NameValuePairs const&)", referenced from:
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in bench3.o
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in validat7.o
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in validat9.o
  "CryptoPP::ed25519PublicKey<CryptoPP::SHA512>::BERDecodePublicKey(CryptoPP::BufferedTransformation&, bool, unsigned long)", referenced from:
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in bench3.o
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in validat7.o
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in validat9.o
  "CryptoPP::ed25519PublicKey<CryptoPP::SHA512>::BERDecode(CryptoPP::BufferedTransformation&)", referenced from:
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in bench3.o
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in validat7.o
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in validat9.o
  "CryptoPP::ed25519PrivateKey<CryptoPP::SHA512>::AssignFrom(CryptoPP::NameValuePairs const&)", referenced from:
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in bench3.o
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in validat7.o
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in validat9.o
  "CryptoPP::ed25519PrivateKey<CryptoPP::SHA512>::GenerateRandom(CryptoPP::RandomNumberGenerator&, CryptoPP::NameValuePairs const&)", referenced from:
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in bench3.o
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in validat7.o
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in validat9.o
  "CryptoPP::ed25519PrivateKey<CryptoPP::SHA512>::BERDecodePrivateKey(CryptoPP::BufferedTransformation&, bool, unsigned long)", referenced from:
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in bench3.o
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in validat7.o
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in validat9.o
  "CryptoPP::ed25519PrivateKey<CryptoPP::SHA512>::BERDecode(CryptoPP::BufferedTransformation&)", referenced from:
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in bench3.o
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in validat7.o
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in validat9.o
  "CryptoPP::ed25519Signer<CryptoPP::SHA512>::SignAndRestart(CryptoPP::RandomNumberGenerator&, CryptoPP::PK_MessageAccumulator&, unsigned char*, bool) const", referenced from:
      vtable for CryptoPP::ed25519Signer<CryptoPP::SHA512> in bench3.o
      vtable for CryptoPP::ed25519Signer<CryptoPP::SHA512> in validat7.o
      vtable for CryptoPP::ed25519Signer<CryptoPP::SHA512> in validat9.o
  "CryptoPP::ed25519Verifier<CryptoPP::SHA512>::VerifyAndRestart(CryptoPP::PK_MessageAccumulator&) const", referenced from:
      vtable for CryptoPP::ed25519Verifier<CryptoPP::SHA512> in bench3.o
      vtable for CryptoPP::ed25519Verifier<CryptoPP::SHA512> in validat7.o
      vtable for CryptoPP::ed25519Verifier<CryptoPP::SHA512> in validat9.o
  "CryptoPP::ed25519PublicKey<CryptoPP::SHA512>::GetVoidValue(char const*, std::type_info const&, void*) const", referenced from:
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in bench3.o
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in validat7.o
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in validat9.o
  "CryptoPP::ed25519PublicKey<CryptoPP::SHA512>::DEREncodePublicKey(CryptoPP::BufferedTransformation&) const", referenced from:
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in bench3.o
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in validat7.o
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in validat9.o
  "CryptoPP::ed25519PublicKey<CryptoPP::SHA512>::Validate(CryptoPP::RandomNumberGenerator&, unsigned int) const", referenced from:
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in bench3.o
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in validat7.o
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in validat9.o
  "CryptoPP::ed25519PublicKey<CryptoPP::SHA512>::DEREncode(CryptoPP::BufferedTransformation&) const", referenced from:
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in bench3.o
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in validat7.o
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in validat9.o
  "CryptoPP::ed25519PrivateKey<CryptoPP::SHA512>::GetVoidValue(char const*, std::type_info const&, void*) const", referenced from:
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in bench3.o
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in validat7.o
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in validat9.o
  "CryptoPP::ed25519PrivateKey<CryptoPP::SHA512>::DEREncodePrivateKey(CryptoPP::BufferedTransformation&) const", referenced from:
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in bench3.o
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in validat7.o
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in validat9.o
  "CryptoPP::ed25519PrivateKey<CryptoPP::SHA512>::Validate(CryptoPP::RandomNumberGenerator&, unsigned int) const", referenced from:
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in bench3.o
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in validat7.o
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in validat9.o
  "CryptoPP::ed25519PrivateKey<CryptoPP::SHA512>::DEREncode(CryptoPP::BufferedTransformation&, int) const", referenced from:
      CryptoPP::ed25519PrivateKey<CryptoPP::SHA512>::DEREncode(CryptoPP::BufferedTransformation&) const in bench3.o
      CryptoPP::ed25519PrivateKey<CryptoPP::SHA512>::Save(CryptoPP::BufferedTransformation&) const in bench3.o
      virtual thunk to CryptoPP::ed25519PrivateKey<CryptoPP::SHA512>::Save(CryptoPP::BufferedTransformation&) const in bench3.o
      CryptoPP::ed25519PrivateKey<CryptoPP::SHA512>::DEREncode(CryptoPP::BufferedTransformation&) const in validat7.o
      CryptoPP::ed25519PrivateKey<CryptoPP::SHA512>::Save(CryptoPP::BufferedTransformation&) const in validat7.o
      virtual thunk to CryptoPP::ed25519PrivateKey<CryptoPP::SHA512>::Save(CryptoPP::BufferedTransformation&) const in validat7.o
      CryptoPP::ed25519PrivateKey<CryptoPP::SHA512>::DEREncode(CryptoPP::BufferedTransformation&) const in validat9.o
      ...
  "non-virtual thunk to CryptoPP::ed25519PrivateKey<CryptoPP::SHA512>::GenerateRandom(CryptoPP::RandomNumberGenerator&, CryptoPP::NameValuePairs const&)", referenced from:
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in bench3.o
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in validat7.o
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in validat9.o
  "virtual thunk to CryptoPP::ed25519PublicKey<CryptoPP::SHA512>::GetVoidValue(char const*, std::type_info const&, void*) const", referenced from:
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in bench3.o
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in validat7.o
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in validat9.o
  "virtual thunk to CryptoPP::ed25519PrivateKey<CryptoPP::SHA512>::GetVoidValue(char const*, std::type_info const&, void*) const", referenced from:
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in bench3.o
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in validat7.o
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in validat9.o
  "virtual thunk to CryptoPP::ed25519PublicKey<CryptoPP::SHA512>::AssignFrom(CryptoPP::NameValuePairs const&)", referenced from:
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in bench3.o
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in validat7.o
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in validat9.o
  "virtual thunk to CryptoPP::ed25519PrivateKey<CryptoPP::SHA512>::AssignFrom(CryptoPP::NameValuePairs const&)", referenced from:
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in bench3.o
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in validat7.o
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in validat9.o
  "virtual thunk to CryptoPP::ed25519PublicKey<CryptoPP::SHA512>::Validate(CryptoPP::RandomNumberGenerator&, unsigned int) const", referenced from:
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in bench3.o
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in validat7.o
      vtable for CryptoPP::ed25519PublicKey<CryptoPP::SHA512> in validat9.o
  "virtual thunk to CryptoPP::ed25519PrivateKey<CryptoPP::SHA512>::Validate(CryptoPP::RandomNumberGenerator&, unsigned int) const", referenced from:
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in bench3.o
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in validat7.o
      vtable for CryptoPP::ed25519PrivateKey<CryptoPP::SHA512> in validat9.o
ld: symbol(s) not found for architecture x86_64

I can't figure out what went wrong here, but I committed the changes anyway so you could take a look at them.

Jul 24 '21 01:07 ghost

@NinjaSnail1080,

Thanks.

The problem is the *.cpp files do not provide a definition of a class with the hash. The *.cpp files would need to manually instantiate them. That's a pain in the ass. For each new hash, the source file would need to provide an explicit instantiation and be recompiled.

The way that the library has dealt with this problem in contemporary times is to provide an interface. So it might look like this:

// Interface + Implementation
template <class HASH>
struct ed25519Signer_Base
{
    const HashTransformation& GetHash() const {
        return m_hash;
    }
    HashTransformation& AccessHash() {
        return const_cast<HashTransformation&>(m_hash);
    }

protected:
    HASH m_hash;
};

template <class HASH>
struct ed25519Signer : public ed25519Signer_Base<HASH>
{
};

Then, in the bowels of the actual signing code - where you need to access the hash, you simply call AccessHash(). Something like this from xed25519 : 690. Notice the hash is now being passed to the Donna code.

size_t ed25519Signer::SignStream (RandomNumberGenerator &rng, std::istream& stream, byte *signature) const
{
    CRYPTOPP_ASSERT(signature != NULLPTR); CRYPTOPP_UNUSED(rng);

    const ed25519PrivateKey& pk = dynamic_cast<const ed25519PrivateKey&>(GetPrivateKey());
    int ret = Donna::ed25519_sign(stream, pk.GetPrivateKeyBytePtr(), pk.GetPublicKeyBytePtr(), signature, AccessHash());
    CRYPTOPP_ASSERT(ret == 0);

    return ret == 0 ? SIGNATURE_LENGTH : 0;
}

All of the Donna::ed25519_sign would be changed:

int
ed25519_sign(std::istream& stream, const byte secretKey[32], const byte publicKey[32],
             byte signature[64], HashTransformation& hash)
{
    return ed25519_sign_CXX(stream, secretKey, publicKey, signature, hash);
}

And Donna::ed25519_sign_CXX:

int
ed25519_sign_CXX(std::istream& stream, const byte sk[32], const byte pk[32], byte RS[64], HashTransformation& hash)
{
    ...

    /* r = H(aExt[32..64], m) */
    hash.Update(extsk + 32, 32);
    UpdateFromStream(hash, stream);
    hash.Final(hashr);
    expand256_modm(r, hashr, 64);

We would also need a CRYPTOPP_COMPILE_ASSERT(HASH::DIGESTSIZE == 64) somewhere to ensure folks don't instantiate an ed25519Signer or ed25519Verifier using the wrong hash.

And to ensure folks don't call the Donna code directly with the wrong size hash, we need something like:

int
ed25519_sign_CXX(std::istream& stream, const byte sk[32], const byte pk[32], byte RS[64], HashTransformation& hash)
{
    ...
    CRYPTOPP_ASSERT(hash.DigestSize() == 64);
    if (hash.DigestSize() != 64)
        return 1;
    ...
}

All of this is kind a pain in the ass. It is made worse because x25519 and ed25519 are not general purpose since they rely on specific Donna code (for example, you can only exponentiate with 9; and not 11 or 13). It is kind of why I delayed in changing things.

Jul 24 '21 08:07 noloader

I worked on it some more, but now even with these changes, I still get the same error as before when I try to build the library.

Jul 24 '21 18:07 ghost

I still get the same error as before when I try to build the library.

Look at the errors. The object files bench3.o, validat7.o and validat9.o instantiate the ed25519 gear. They are the ones that need the missing definition.

Now, for the missing definition, ed25519PrivateKey<CryptoPP::SHA512> and ed25519PublicKey<CryptoPP::SHA512> tell you you need to use the same trick on ed25519PrivateKey and ed25519PublicKey. (Or you need to explicitly instantiate the template for ed25519PrivateKey and ed25519PublicKey. Explicitly instantiation requires a recompile for each new hash, so use the interface trick.)

But stepping back a bit, it looks like one needs to choose the hash earlier than signing or verification. The hash is needed earlier when creating the public key from the secret key. See, for example, https://github.com/Matoking/python-ed25519-blake2b/blob/master/src/ed25519-supercop-ref/ed25519.c, where BLAKE2b is used instead of SHA-512. I was not clear if the hash was needed for just signing/verification; or both key derivation and signing/verification.

We should probably ask Bernstein about the way the hash is used just to be sure. Naively, I think it is OK as long as the hash is an ideal hash and acts as a PRF. But I think it is best to ask a real cryptographer about it.

So I am thinking use the interface trick on ed25519PrivateKey and ed25519PublicKey. Then, when you need to sign or verify, you get the hash from the key. Something like this. Notice the addition of pk.AccessHash().

size_t ed25519Signer::SignAndRestart(RandomNumberGenerator &rng, PK_MessageAccumulator &messageAccumulator, byte *signature, bool restart) const
{
    CRYPTOPP_ASSERT(signature != NULLPTR); CRYPTOPP_UNUSED(rng);

    ed25519_MessageAccumulator& accum = dynamic_cast<ed25519_MessageAccumulator&>(messageAccumulator);
    const ed25519PrivateKey& pk = dynamic_cast<const ed25519PrivateKey&>(GetPrivateKey());
    int ret = Donna::ed25519_sign(accum.data(), accum.size(), pk.GetPrivateKeyBytePtr(), pk.GetPublicKeyBytePtr(), signature, pk.AccessHash());
    CRYPTOPP_ASSERT(ret == 0);

    if (restart)
        accum.Restart();

    return ret == 0 ? SIGNATURE_LENGTH : 0;
}

Now that is the C++ code. We still have problems to solve. The first problem is, we need OIDs for each variant of ed25519. We cannot use 1.3.101.112 since it is no longer using SHA-512. The second problem is, we need independent test vectors.

You can find code for checking OIDs in xed25519.cpp, like shown below. The actual OID, like ASN1::Ed25519(), is defined in oids.h.

void ed25519PrivateKey::BERDecodeAndCheckAlgorithmID(BufferedTransformation &bt)
{
    OID oid(bt);

    if (!m_oid.Empty() && m_oid != oid)
        BERDecodeError();  // Only accept user specified OID
    else if (oid == ASN1::curve25519() || oid == ASN1::Ed25519())
        m_oid = oid;  // Accept any of the ed25519PrivateKey OIDs
    else
        BERDecodeError();
}

I don't know where to find OIDs for Ed25519/SHA-3 or Ed25519/BLAKE2b. Would you know where to find them?

Jul 28 '21 10:07 noloader

@NinjaSnail1080,

I looked for the OIDs for Ed25519/BLAKE2b and have not come across them (yet?). I've found a few implementations we can use for test vectors, however.

Let's ping @sneves. Samuel is part of the BLAKE2 team and is active on GitHub.

Samuel, do you know of OIDs allocated for Ed25519 keys and signatures using BLAKE2b? Bonus points if you know them for SHA-3.

Jul 30 '21 18:07 noloader

There was this, I'm not sure if that helps.

Jul 30 '21 19:07 sneves

LSH-512, Keccak-512, and Whirlpool could also be used with ed25519 since they also have a digest size of 64 bytes. So I guess we'd need OIDs for those too.

I looked through the document Samuel provided but I couldn't find anything about OIDs. My own googling didn't come up with anything either.

Jul 30 '21 20:07 ghost

Thanks @sneves,

Forgive my ignorance... Do you think the IETF's SPASM list would be able to field the question? https://www.ietf.org/mailman/listinfo/spasm.

Jeff

Jul 30 '21 21:07 noloader

Not sure what you mean. EdDSA (with Ed448) with BLAKE2b-512 is defined there as 1.3.6.1.4.1.1722.12.5.5, and ECDSA with BLAKE2b-512 as 1.3.6.1.4.1.1722.12.5.4. There doesn't seem to be an OID for Ed25519-BLAKE2b, though. If you ask Jean-Philippe, he might get you an OID for this.

Jul 31 '21 15:07 sneves

cryptopp cryptopp copied to clipboard

Added overloaded functions in the donna source files that let the caller specify a HashTransformation

cryptopp
cryptopp copied to clipboard