Add additional signature algorithms

[aaronc]

We've had a chance to discuss various things about key management, but one important thing that hasn't been discussed much is new signature algorithms.

I'd like to see specifically:

• ed25519 (I know it's implemented but disabled)
• secp256r1 (I know people are concerned about NSA backdooring, but Tezos did it and esp with sub keys there are use cases because of the secure enclave on iOS/Android)
• in the future stuff like sr25519

One key issue to resolve is the address format for these new signature types, see #3685. The two approaches discussed there are a single byte prefix for the signature type or conditions like in weave. I'd be open to exploring either. It would be good to do this in a 21 byte address space to avoid collision with the existing 20 byte secp256k1 and multisig addresses, and to add one more byte of security for this expanded address space.

I don't have time to work on this at all right now really, I just see there is no open issue addressing this and want to have some place to track and discuss. I see it as potential future work that could be done by https://github.com/cosmos-cg-key-management once the sub key/delegation/group stuff is addressed.

[alexanderbez]

Thanks @aaronc. I'd specifically would like to see this parameterized better on chain. i.e. What curves are supported and their gas verification costs. Then governance can vote these in without needing to halt the chain (similar to param change proposals).

If we lay the groundwork like this, it'll be less controversial I think to introduce new curves. I would like to see new curves introduced as well. Specifically using a byte prefix makes sense along with potentially increasing the address space slightly.

/cc @zmanian

[zmanian]

Strongly in favor of nistp256(secp256r1). It is in the go standard library. It should be subkeys only but delegating to apple secure enclaves is great.

Strongly in favor is sr25519 or another Ristretto signature system.

Not in favor of ed25519, ed25519 badly supports key derivation and blinding and is suitable only for signatures.

[zmanian]

I don't think we need multiple address types, I don't there is any risk of address collisions. We already use common address formats for single and multisig. As long as all key types involve prover knowledge of a discrete log and collision resistant hash functions in address generation it should be safe.

[ValarDragon]

I'm in favor of multiple address types. Without it, address security is as secure as the weakest curve, and imo its important that the cryptography assumptions are isolated from one another. The cosmos hub may remain very conservative with its cryptography assumptions, but the entire ecosystem should not be restricted as such, and should have available a safer key as fallback.

For example if we integrated BLS signatures at the account layer, and then a tower NFS breakthrough happens, thats security loss for every pubkey.

The choice to not have multiple address types means that you can't have a chain with both post-quantum & pre-quantum pubkeys, and still consider the post-quantum pubkeys as a post-quantum fallback.

I'd prefer if multiple address types were implemented, but with optionality to group similar keys under the same type. (And in the case of only one type, then no extra space needs to be used)

[aaronc]

With one extra byte you can have 255 different address types or do it the way weave does with conditions. I believe it's prudent to err on the side of caution especially since the cost is quite low.

On Fri, Jul 26, 2019, 20:42 Dev Ojha notifications@github.com wrote:

I'm in favor of multiple address types. Without it, address security is as secure as the weakest curve, and imo its important that the cryptography assumptions are isolated from one another. The cosmos hub may remain very conservative with its cryptography assumptions, but the entire ecosystem should not be restricted as such, and should have available a safer key as fallback.

For example if we integrated BLS signatures at the account layer, and then a tower NFS breakthrough happens, thats security loss for every pubkey.

The choice to not have multiple address types means that you can't have a chain with both post-quantum & pre-quantum pubkeys, and still consider the post-quantum pubkeys as a post-quantum fallback.

I'd prefer if multiple address types were implemented, but with optionality to group similar keys under the same type. (And in the case of only one type, then no extra space needs to be used)

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/cosmos/cosmos-sdk/issues/4789?email_source=notifications&email_token=AAAL6FQ3ZYHCF2CPPE3HAMLQBOKXRA5CNFSM4IG7XKUKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD2577BQ#issuecomment-515637126, or mute the thread https://github.com/notifications/unsubscribe-auth/AAAL6FQPM3GFDOCHHDD3XQ3QBOKXRANCNFSM4IG7XKUA .

[zmanian]

So here is my counterpoint to the idea that that a break in one signature scheme renders the whole system insecure, let's say that a support signatures scheme suffered some kind of catastrophic break.

For instance, BLS signatures have Number Field Sieves improve and be implementable on actual computers that can physically exist.

The rational response would be to modify the state machine so that if you are instantiating an account that doesn't currently have a public key with a new public key the pub key type is prohibited.

[ValarDragon]

I agree that that line of reasoning protects you if the attack is found by a benevolent agency, who reveals it to the world. If you want nation state security, that doesn't hold. These are different design goals, but my personal preference is for the cryptography layer to have maximal security, and we hopefully bring the rest of the system up to that level of security over time.

[zmanian]

I am worried that breaking address uniformity will cause compatibility breakage across the ecosystem. Especially given all the unknowns about how service providers validate cosmos addresses.

We have set the expectation that addresses are 20 bytes. Saying that sometimes they are 20 or 21 bytes will cause chaos.

[ethanfrey]

Not in favor of ed25519, ed25519 badly supports key derivation and blinding and is suitable only for signatures.

Slip0010 for ed25519 provides nice key derivation and has been implemented in many languages (including go by stellar).

I don't understand what you mean by blinding. And afaik we only use the pubkeys for signatures, so I don't see the point there.

Basically, ed25519 seems to me generally as more stable than secp256k1 and I have not seen a good argument against it (except we want ethereum/bitcoin compatibility). You do know very much about cryptography, so I would be curious to hear a longer explanation (not just a one-liner) why ed25519 is not good for singing blockchain transactions.

[ethanfrey]

With one extra byte you can have 255 different address types or do it the way weave does with conditions. I believe it's prudent to err on the side of caution especially since the cost is quite low.

In weave, we also have 20 byte uniform addresses.

What we do is prefix the public key before hashing it to an address. That way we can do sig/secp256k1/<pubkey bytes> or sig/ed25519/<pubkey bytes> and then hash it.

Since we all assume sha256 is not reversable (and is impossible to cause collisions better than brute force), this means that even revealing my pubkey for my account offchain doesn't allow you to make a signature with another curve, as the preimages are curve dependent.

Since this prefix is only stored in memory in the computation phase, I don't see a problem, it can be any size.

I agree with keeping 20 byte address sizes consistent over all code. Unless we later have a major upgrade to 32 for other reasons.

I agree with backwards compatibility with current system, and would propose using no prefix for the current secp256k1 algorithm, and prefixing pubkeys from any other curve before hashing to an address.

[ValarDragon]

I agree with prefixing the public keys, that does solve this. I was about to post that we can do this with blake2 personalization strings haha.

[sunnya97]

@ValarDragon Or by hashing the amino encoded pubkey 😜

[github-actions[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[ebuchman]

Slip0010 for ed25519 provides nice key derivation and has been implemented in many languages (including go by stellar).

I think the HD derivations for ed25519 are all more or less broken or its too difficult to do them securely? Hence ristretto constructions like sr25519

[ethanfrey]

I think the HD derivations for ed25519 are all more or less broken or its too difficult to do them securely? Hence ristretto constructions like sr25519

I never saw any problems with them. @webmaster128 implemented slip0010 from spec in typescript for iov-core and cosmjs. The stellar library also works. I never heard of any issue with securing them relative to secp256k1, the only point is you can only use hardened derivation paths (the bitcoin trick of sharing a pubkey that can derive child-pubkeys is not possible)

[ebuchman]

See eg. tony's comments here https://github.com/solana-labs/solana/issues/6301#issuecomment-548506146. Unfortunately the main web3 forum post where Jeff Burdges comments on this (their cryptographer) seems to be down ...

[ethanfrey]

I read Tony's comment, and immediate found that the justification that they are broken

I'd suggest reading Jeff Burdges' writeup on them as they all have issues.

Leads to a missing page: https://forum.web3.foundation/t/key-recovery-attack-on-bip32-ed25519/44 I would be grateful for some background on the attack vectors (given other chains are using them and there is no public exploit of them).

The next comment seems to show work-arounds and that BIP32-Ed25519 and SLIP-0010 are safe "work arounds" for these issues.

[ebuchman]

I think the point is that any Ed25519 HD scheme is kind of a hack and its hard to gain confidence in them. And they're especially dangerous if the keys might be used for anything other than vanilla signatures. Hence the move to standardize around Rosetta constructions like sr25519 which remove the cofactor issues (eg. I believe polkadot has done this)

[webmaster128]

SLIP-0010 and BIP32-Ed25519 are used by a bunch of not so irrelevant coins supported by Trezor so it seems to be practical. But I'm not promoting those schemes here as I don't have a deep enough knowledge of the underlying crypto.

sr25519

Is there any spec for HD derivations of sr25519? I would be great to see one, but every time I looked for it, the situation was like do what Parity does, which includes funny text instead of numbers in the path components.

[ethanfrey]

Also interesting point on SEP-0005 basically, that using 5 paths for account-based systems doesn't make sense. (Although I think we do that for current cosmos-sdk secp256k1 keys). If you are looking into hd derivations, let's look at what paths make sense as well

[robert-zaremba]

I was thinking more about ed25519 in SDK. Now we have an issue because we have 2 implementations: one in Tendermint and one in SDK.

Maybe we should remove ed25519 from SDK (it's still not enabled in antehandlers) and use sr25519 instead? It would make sense because use of ed25519 is limited (It's not safe to use it with HD wallets).

[robert-zaremba]

BTW: This issue is very wide - would be good to break it down into few concrete tasks and close it. Eg:

• decided about ed25519
• Add secp256r1 Signing Keys #7718 (in progress)
• BLS
• ...?

[tac0turtle]

lets open specific issues about adding each key type instead of a larger issue

[danwt]

Was ante support ever added for ed25519? Thanks