Clarify if we want to prehash before signing messages

[ethanfrey]

NOTE This issue is not to do any coding, but just make a decision on our architecture

The original golang code uses https://godoc.org/golang.org/x/crypto/ed25519 which will produce the ed25519 signature of whatever we enter it. There is no prehashing here.

Every ledger code I have seen does prehashing on the transaction before signing. I am not sure if this is required, or just a convention. Maybe @rudi-cilibrasi knows better.

I did a little investigation and it seems there is a prehash step (using keccack) in ethereum as well:

• https://github.com/ethereum/wiki/wiki/JSON-RPC#eth_sign
• https://github.com/ethereumjs/ethereumjs-util/blob/master/index.js#L358-L385

When I worked on the first demo ledger app for cosmos, we had to use some flag to specify:

• this public key is in software, verify signature against full sign bytes
• this public key is in ledger, verify signature against sha256(sign bytes)

Needless to say this was clunky and didn't seem right. Let's discuss if we will need this prehashing step, and if so, consider doing it everywhere. This will update the signing algorithm used in weave, weave-js and in web4/@iov-keycontrol. We can pass the unhashed sign bytes to the keyring entries so they can verify the content (eg. ledger app), but then hash before signing them.

I would like some feedback here, especially anyone who has dealt with this issue before.

[webmaster128]

Libsodium includes a prehashing mechanism:

If the message doesn't fit in memory, it can be provided as a sequence of arbitrarily-sized chunks.
This will use the Ed25519ph signature system, that pre-hashes the message. In other words, what gets signed is not the message itself, but its image through a hash function.
If the message can fit in memory and can be supplied as a single chunk, the single-part API should be preferred.
Note: Ed25519ph(m) is intentionally not equivalent to Ed25519(SHA512(m)).

https://download.libsodium.org/doc/public-key_cryptography/public-key_signatures.html

This can also be called explicitly:

If, for some reason, you need to prehash the message yourself, use the multi-part crypto_generichash_*() APIs and sign the 512 bit output.

However, I do not yet fully understand the difference between single and multi part message signing.

[ethanfrey]

As far as I know we have a few signing mode possibilities:

• used ed25519(m) - currently done in golang, sign bytes w/o modification
• use ed25519ph(m)
• use ed25519(sha256(m))
• use ed25519(sha512(m))
• use ed25519(keccack256(m)) - this is ethereum style, well, with a different curve

The first one is simplest, but has limitations if messages are large or any library enforces prehash

The second one ed25519ph is recommended by libsodium, but it also seems to use a unique libsodium prehash that is not well documented, and may not be compatible with golang and ledger C implementations.
I think the official golang library doesn't support this... https://godoc.org/golang.org/x/crypto/ed25519#PrivateKey.Sign and I'd have to lie to it about the fact we did actually prehash if we do it manually

The next set ed25519(hash_func(m)) is a choice of various hash functions, should be portable and handle any message. We just must ensure we choose the same hash function everywhere.

[ethanfrey]

One suggestion was not to enforce one mode, but support multiple of these modes (eg. a whitelist of possible modes). Signers may chose which mode to use and return a mode flag along with the signature they produce. The verifier (golang blockchain, maybe also TS wallet) should be able to switch over mode flag and verify any of the officially supported algorithms.

This is a better idea that writing a specific KeyringEntry for every mode, just a flag for the pre-processing step. And it only limits us to the set of modes than can be verified in golang.

[webmaster128]

For secp256k1 the situation seems pretty open:

• pyca/cryptography generates test data using the prehashing algorithms first32Bytes(sha1(m)), first32Bytes(sha224(m)), first32Bytes(sha256(m)), first32Bytes(sha384(m)), first32Bytes(sha512(m)): https://github.com/pyca/cryptography/blob/master/docs/development/custom-vectors/secp256k1/generate_secp256k1.py#L17
• bitcoin-ts is prehashing agnostic and signs hashes directly: https://bitjson.github.io/bitcoin-ts/interfaces/secp256k1.html#signmessagehashcompact
• elliptic is prehashing agnostic and signs hashes directly: https://github.com/indutny/elliptic#api

[ethanfrey]

Okay, the ledger requires a prehash. Either sha256, sha512, or keccak. So we must support it.

[ethanfrey]

I would follow the suggestion of multiple modes, and even generalize it to support multiple hashes. Concretely (in typescript):

export const enum Prehash {
  SHA256 = "sha256",
  SHA512 = "sha512",
  // maybe support these two, but not if it is much work
  KECCAK256 = "keccak256",
  RIPEMD160 = "ripemd160",
}

export interface Signature {
  readonly algo: Algorithm;
  readonly data: SignatureBytes;
  readonly prehash?: Prehash;
}

OR

export interface Signature {
  readonly algo: Algorithm;
  readonly data: SignatureBytes;
  readonly prehash: ReadonlyArray<Prehash>;
}

Where Algorithm is already defined in @iov/types as the curve we use. Top example shows 0 or 1 prehash, bottom shows 0 to N if we want to support signing eg. ripemd160(sha256(txBytes)), which is odd but seems bitcoin way.

We can request when signing possibly, but in any case the Keyring should return the signature with the prehashes used, so it can be verified.

[webmaster128]

Why is prehash optional in

export interface Signature {
  readonly algo: Algorithm;
  readonly data: SignatureBytes;
  readonly prehash?: Prehash;
}

I think there is always a prehash. It is just a question on which abstraction level it is implemented. I think we should make the explicit in any case

[ethanfrey]

The current code (weave, bcp-demo, weave-js) doesn't prehash at all and works great.
If we go for 0 or 1 and you don't like the optional parameter, I could add a RAW = "raw" to enum Prehash to signify no prehash

[ethanfrey]

I would like to continue supporting signatures on non-prehashed transactions (eg. passing full sign bytes into libsodium)

[webmaster128]

"passing full sign bytes into libsodium" means libsodium does the prehashing for you because the API is designed like that: https://github.com/jedisct1/libsodium/blob/569778b517496861a3880e0e690973bf08a52e08/src/libsodium/crypto_sign/ed25519/ref10/sign.c#L65
You cannot use arbitrary length input data with elliptic curves so the hashing is done somewhere.

I guess libsodium's crypto_sign is implemented as Ed25519(SHA512(m)) but I'll verify that.

[ethanfrey]

For me prehash means, I pass SHA512(m) into libsodium.
I will investigate ledger deeper, I think it will never be able to take an eg. 120 byte message m and produce the same signature that libsodium would, it would only match what libsodium would produce on eg. SHA256(m) or SHA512(m) depending on how you code the ledger app

[ethanfrey]

Nice link for libsodium algorithm btw

[webmaster128]

According to https://tools.ietf.org/html/rfc8032#section-4, Ed25519 is a PureEdDSA variant, which means that the pre-hash function is the identity (i.e. no prehashing).

However, part of Ed25519 is the ability to handle arbitrary sized input messags (M) because of an internal SHA512 step: https://tools.ietf.org/html/rfc8032#section-5.1.6

Given that, I think we can consider Ed25519 to be a signing mechanism that consumes plain messages M or prehashed messages PH(M). In this case, having an optional prehashing step makes sense.

The situation is different for Secp256k1, where the signing algorithm itself truncates input to be smaller than N (256bit). This must never happen on unprehashed messages.

[rudi-cilibrasi]

i agree with @webmaster128 so far

[webmaster128]

If we can avoid making prehash configurable it, I'd rather keep it uniform. libsodium suggests using Ed25519(blake2b(m)), where blake2b is their default generic hashing algorithm. The alternative is Ed25519(sha512(m)), which has the advantage that sha512 is a dependency of Ed25519 itself anyway.

The main difference between BLAKE2b and sha512 is probably flexible use (not needed in our use case) and speed (not needed in our use case). So I think we can choose whatever is more convenient to use.

I like the existence of synchronous JavaScript-only implementation of sha512 that is probably fast enough for the small chunks of data you store in a blockchain.

[ethanfrey]

Since Blake2b is not an option on the Ledger, and is less supported in libraries, let's go with sha512 and make it required.

I will update the backend code to perform sha512 after calculating sign bytes when verifying signatures. Then we can do that in the signers as well. Each keyring is responsible for performing the sha512 either in typescript or in hardware.