Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Pre-hashing signature messages #322

Open
Tabaie opened this issue Jan 30, 2023 · 6 comments
Open

Pre-hashing signature messages #322

Tabaie opened this issue Jan 30, 2023 · 6 comments

Comments

@Tabaie
Copy link
Contributor

Tabaie commented Jan 30, 2023

I think it would be best to modify the Signer interface as follows:

type Signer interface {
  ⋮
  Sign(msg []byte) ([]byte, error)
  SignNum(msg big.Int, hFunc hash.Hash) ([]byte, error)
  ⋮
}

Sign takes in long messages such as human-readable strings. It then performs a hash-to-fr on the message, and passes it on to SignNum with nil as hFunc. Just like the current logic for Sign, when hFunc==nil, the input is considered pre-hashed and not hashed again. The hash used for hashing to Fr is a conventional one, but that would not create an issue on the SNARK side because any human-readable string can be reasonably expected to be known at SNARK compile time.

@Tabaie
Copy link
Contributor Author

Tabaie commented Jan 30, 2023

@ivokub @yelhousni Does this make sense? Does it address what #312 is about? If we reach consensus here I think we can skip the Wednesday meeting. 😁

@ivokub
Copy link
Collaborator

ivokub commented Jan 30, 2023

I'm not sure I follow completely. Shouldn't the interface be instead:

type Signer interface {
    Sign(msg []byte, hFunc hash.Hash) ([]byte, error)
    SignNum(msg *big.Int) ([]byte, error)
}

Otherwise I do not know what to do with the hash in SignNum if msg is larger than some bound. And in that case I would also return something numeric from SignNum.
How would this look for BLS signatures? I'm not sure but I think that we need to map to point, not a scalar, so *big.Int as an argument wouldn't cover it? (I may be wrong also, don't know too much about BLS)

@ivokub
Copy link
Collaborator

ivokub commented Jan 31, 2023

Following up from #313 (comment), I would propose instead changing the functions for generating/unmarshalling keys for making prehashing hash functions/Fiat-Shamir hash function etc. a property of the key instead. So, instead of having an interface for generating the key as:

func New(ss twistededwards.ID, r io.Reader) (signature.Signer, error)

(or corresponding alternatives in ECDSA, Schnorr, BLS), we instead have

type EdDSAKeyOption func(opt *config) error

func WithRandomnessSource(r io.Reader) EdDSAKeyOption
func WithPreHashing(hFunc hash.Hash) EdDSAKeyOption

func New(ss twistededwards.ID, opts... EdDSAKeyOption) (sign.Signer, error)

and then the interface for sign.Signer would be

type Signer interface {
    Sign(msg []byte) ([]byte, error)
    Verify(msg, sig []byte) (bool, error)

In this case, user wouldn't have to figure out at every call what are the additional parameters (or even worse, taking the untrusted input from input, see JWT None problems)

I would avoid SignNum method in the interface as per signature scheme the raw input which is used for computing may differ (scalars, points etc.). Imo it is sufficient to add WithRawBytesMsg etc. option which assumes that input to Sign/Verify is canonical representation of the input and the function shouldn't pre-hash it.

When marshalling/unmarshalling, we can either embed the configuration into the corresponding PrivateKey/PublicKey structs, or allow adding options to the Bytes/SetBytes.

On that note, I guess it would also be good to have Unmarshal/Marshal in signature/... packages so that the user wouldn't have to define variables of correct type. So instead of

import `github.com/consensys/gnark-crypto/ecc/bn254/ecdsa`

func main() {
   var pk PrivateKey
   err := pk.SetBytes(b)
   if err != nil {
       panic(err)
   }
   pk.Sign(msg)
}

we can have

import `github.com/consensys/gnark-crypto/signature/ecdsa`

func main() {
   pk, err := ecdsa.Unmarshal(ecc.BN254, b)
   if err != nil {
       panic(err)
   }
   pk.Sign(msg)
}

@yelhousni
Copy link
Collaborator

I think that your proposition is what makes most of sense from all discussed options ✚1️⃣

@Tabaie
Copy link
Contributor Author

Tabaie commented Jan 31, 2023

@ivokub I agree with your argument for key options vs many parameters, and I'm starting to doubt the necessity of exposing a "sign custom string" function in the first place.

I was anticipating a lot of use cases where the user would sign a message like "hi this is an EDDSA signature" which with the new MiMC patch would result in an error with a sufficiently long message. The best way to handle these imo is to hash the message to fr first.

Now if there are many such use-cases (which I'm not sure of) I think it would be nice to have Sign/Verify functions that take care of that initial hashing, and if not we should make it clear that the message should always be an fr element. That's why I thought a big.Int may be appropriate to indicate the input is numerical, as opposed to a []byte which from a user's perspective could be anything.

What are your thoughts? Do we really need to make signing customs strings easy and what is the best generic way to receive an fr element input (without using the type fr.Element)?

@ivokub
Copy link
Collaborator

ivokub commented Jan 31, 2023

@ivokub I agree with your argument for key options vs many parameters, and I'm starting to doubt the necessity of exposing a "sign custom string" function in the first place.

I was anticipating a lot of use cases where the user would sign a message like "hi this is an EDDSA signature" which with the new MiMC patch would result in an error with a sufficiently long message. The best way to handle these imo is to hash the message to fr first.

Now if there are many such use-cases (which I'm not sure of) I think it would be nice to have Sign/Verify functions that take care of that initial hashing, and if not we should make it clear that the message should always be an fr element. That's why I thought a big.Int may be appropriate to indicate the input is numerical, as opposed to a []byte which from a user's perspective could be anything.

What are your thoughts? Do we really need to make signing customs strings easy and what is the best generic way to receive an fr element input (without using the type fr.Element)?

So I think there are several cases for the message we want to cover:

  • input is an arbitrary length byte-string. And I think this is the default case if we do not apply any options to the signer. Then we always hash the message to the target domain using some sensible default values. We can modify the used hash function with WithMessageHash option (if applicable)
  • input is a short byte-string which can be un-marshaled into the target domain (e.g. for ECDSA we need to map to F_r). We do not hash it and try to deserialize into the target domain element. If it fails then output a signing/verification error. For this we would have to instantiate the signer with WithRawMessage (etc.) option. Most particularly, we do not check that the input has some minimum length etc.
  • input is already prehashed into the target domain and it is byte serialisation of the target domain element. It is slightly different from the previous case as we also have to check that the serialisation is correct (e.g. slice has particular number of bytes etc.) For this we would have to instantiate the signer with WithPrehashed option.

As an example of the different uses (currently doing it for ECDSA but should hold for other schemes)

// input is an arbitrary length byte-string. By default we use SHA2-256+modreduce
pk, err := ecdsa.New(ecc.SECP256K1)
msg := []byte("this is a very long byte string which doesn't necessarily fit into scalar field")
sig, err := pk.Sign(msg)
// doesn't err

// input is an arbitrary length byte-string, but we use snark-friendly mimc
pk, err := ecdsa.New(ecc.SECP256K1, WithMessageHash(mimc.MiMC))
msg := []byte("this is a very long byte string which doesn't necessarily fit into scalar field")
sig, err := pk.Sign(msg)
// doesn't err

// input is a short arbitrary byte string, with no message hashing.
pk, err := ecdsa.New(ecc.SECP256K1, WithRawMessage())
msg := []byte("foo")
sig, err := pk.Sign(msg) // internally left pad msg with enough zeros so that can `var el fr.Element; el.FromBytes(paddedMsg)`
// doesn't err

// but if the input without message hash is long then doesn't work :(
pk, err := ecdsa.New(ecc.SECP256K1, WithMessage())
msg := []byte("this is a very long byte string which doesn't necessarily fit into scalar field")
sig, err := pk.Sign(msg)
// errs, error "can not unmarshal message into fr.Element"

// if we have already prehashed the message
pk, err := ecdsa.New(ecc.SECP256K1, WithPrehashed())
var el fr.Element
el.SetRandom()
msg := el.Bytes()
sig, err := pk.Sign(msg)
// doesn't err, input is a canonical representation of fr.Element

// but if we feed arbitrary bytes into prehashed instance, doesn't work
pk, err := ecdsa.New(ecc.SECP256K1, WithPrehashed())
msg := []byte("short")
sig, err := pk.Sign(msg)
// errs, error "message is not canonical representation of fr.Element"

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants