Fixed 20 byte addresses reduce security and don't accommodate all use cases

[aaronc]

In Regen Ledger we have the need to create a couple of different types of Account types other than the ones that are defined in the SDK. These Account's wouldn't have a public key associated with them but would have other authorization methods for sending coins. One example is an Account for an "organization" type entity that can only spend coins based on governance decisions. The ID of one of these organizations is internally just an auto-incrementing integer.

In looking at the implementation for addresses I see that they are fixed in length to 20 bytes. While the length of these keys may be enough to prevent any possible collisions via sheer randomness, I am concerned that this length limitation and the lack of any sort of prefixing on the built in address types reduces security because it increases the chance for a collision however small.

I don't have a lot of context for why the design is the way it is, but it seems to me that a more cautious design would be to add some sort of 1 byte prefix to the existing addresses (secp256k1 and ed25519) and allow for different address lengths as measures to prevent collisions. At a minimum, I would want the option to choose a different address length for my custom account types to at least avoid any potential collision there and to also avoid needing to unnecessarily pad them with zeros. I'm thinking that maybe the current 20 byte limitation is to ensure that addresses are entered correctly but maybe the bech32 checksum takes care of that?

---

For Admin Use

• Not duplicate issue
• Appropriate labels applied
• Appropriate contributors tagged
• Contributor assigned/self-assigned

[aaronc]

Just a bit more context on what I see as a potential security issue beyond sheer collision. If support for different key types is added to the SDK and they all are in the same overlapping address space, a vulnerability in any key type affects all other keys that don't have a pub-key registered. For example say we support signature algorithms A, B and C. If at some point there is a vulnerability in algorithm A that allows some malicious user to hack these keys, this vulnerability affects all addresses with no associated pub key whether or not they were generated with algorithm A, B or C because at the SDK level all addresses overlap. So you will not be protected just because you were smart and chose B or C because you knew they were more modern and attack-proof. A simple one byte prefix would prevent this scenario.

[ValarDragon]

Agreed! It is bad design that address sizes are fixed at 20 bytes. I suspect it is that way solely because time constraints / it was convenient when initially writing that code.

Also with 20 bytes, the chance of a random collision attack does increase, thereby increasing the ease to double spend. With 20 bytes, the double spend difficulty is roughly 80 bits of security.

In your second comment, if I understand correctly, you are commenting on effectively "if there is a pre-image attack in keyspace A", and seek domain separation in what goes into the hash. This seems like a great idea to me.

As for what is the best way to make addresses and address hashing domain separated, I don't know. The current 20 byte assumption is deep rooted, coming from the Pubkey type itself. It feels like the first step will be making the SDK do the hashing of the pubkey bytes into an address. I don't remember if the pubkey bytes are amino encoded before being hashed within the default pubkey types, if that is the case, that does satisfy the domain separation, but its kind of at an odd level. (Since pubkey types aren't supposed to know about one another)

[aaronc]

I don't remember if the pubkey bytes are amino encoded before being hashed within the default pubkey types, if that is the case, that does satisfy the domain separation, but its kind of at an odd level. (Since pubkey types aren't supposed to know about one another)

They're not amino-encoded except for the multisig key, but I don't see how that would actually provide separation after the hashing happens.

https://github.com/tendermint/tendermint/blob/master/crypto/secp256k1/secp256k1.go#L143-L151
https://github.com/tendermint/tendermint/blob/master/crypto/ed25519/ed25519.go#L138-L140
https://github.com/tendermint/tendermint/blob/master/crypto/multisig/threshold_pubkey.go#L71-L73

So currently three address types overlapping.

[aaronc]

In your second comment, if I understand correctly, you are commenting on effectively "if there is a pre-image attack in keyspace A", and seek domain separation in what goes into the hash. This seems like a great idea to me.

Exactly

[ValarDragon]

They're not amino-encoded except for the multisig key, but I don't see how that would actually provide separation after the hashing happens.

Oh yeah, you are right :), it would need prefixing from the SDK as you were suggesting.

[aaronc]

So I think a minimum solution would be to allow overriding the address length validation here: https://github.com/cosmos/cosmos-sdk/blob/develop/types/address.go#L102-L104

But that doesn't really address the larger issue which I think is related to how key types are registered and processed in general. It seems like the main code that controls what key types get accepted or rejected is this: https://github.com/cosmos/cosmos-sdk/blob/develop/x/auth/ante.go#L262-L288. This doesn't allow the definition of custom key types which I know has been discussed before and would be nice. But also, the way this allows or rejects key types by using strings.Contains seems like a vulnerability in and of itself. So what this is basically saying is that if there is any type registered with amino that contains the word "ed25519" that was provided as the pub key and it can generate that address, well then we'll accept it as the pub key. So maybe this is a far fetched vulnerability, but I do remember reading that the object capabilities model was concerned about vulnerabilities in third party code. Well if that is a real threat, then all third party code needs to do is register some fake pub key type with amino that contains the word ed25519 and it will be accepted as valid by the ante handler.

So anyway, I guess what I would propose is that we have some method on the ante handler to register what are the acceptable concrete pub key types and what are their associated address prefixes, etc.

[alexanderbez]

Thanks for following up on this issue @aaronc. Supporting varying address length and custom key types is something that the SDK should support. To address some of your points:

It seems like the main code that controls what key types get accepted or rejected is this: https://github.com/cosmos/cosmos-sdk/blob/develop/x/auth/ante.go#L262-L288. This doesn't allow the definition of custom key types which I know has been discussed before and would be nice.

Correct. The SDK currently on supports secp256k1 keys as they're the only ones fully tested within the context of the Cosmos Hub (gaia). It would be ideal if the ante-handler supported custom types through config/params.

But also, the way this allows or rejects key types by using strings.Contains seems like a vulnerability in and of itself.

The PubKey interface defined in Tendermint has no Type method. This this, albeit hacky, solution on checking the stringified type arose due to needs when developing Ethermint -- I can't recall exactly. Ideally, we'd implement and use the Type method here. Are you stating there is a vulnerability if a malicious amino library was used?

Do you have any suggested means of supporting varying key types? Should this be part of genesis and fetched through params? We already use the param store in the auth module and ante-handler.

[aaronc]

Are you stating there is a vulnerability if a malicious amino library was used?

It appears that way.

Do you have any suggested means of supporting varying key types? Should this be part of genesis and fetched through params? We already use the param store in the auth module and ante-handler.

I'll try to think it through a bit.

[aaronc]

I'm starting to work on a PR to address this and hope to post a draft soon.

One thing that I want to point out is that it might be worth thinking this through a bit more before Atom transfers are enabled. If we do want to move to 21 byte addresses as the default (which might be the easiest way to solve this), it would be much easier to do that before Atoms start moving around. Of course, I'm sure there are ways we could extend the address format later, but just saying I think it'd be easier first...

[ethanfrey]

Hi @aaronc

I spent quite a bit of time thinking about this issue while building weave... The other cosmos Sdk.

Basically I define a condition to be a type and format as human readable string with some binary data appended. This condition is hashed into an Address (again at 20 bytes). The use of this prefix makes it impossible to find a preimage for a given address with a different condition (eg ed25519 vs secp256k1).

This is explained in depth here https://weave.readthedocs.io/en/latest/design/permissions.html

And the code is here, look mainly at the top where we process conditions. https://github.com/iov-one/weave/blob/master/conditions.go

It doesn't involve go Amino or other complex encodings.

I'd love feedback on this approach, which we have happily used to differentiate multisig vs public keys vs distribution contracts.

[aaronc]

@alexanderbez @ValarDragon here is a draft of some changes which would allow SDK users to define their own address formats and public key types: #4166.

It doesn't address any improvements or modifications to what is in gaia (it seems pretty clear that's a longer discussions), but just allows for customization.

Let me know what you think.

[aaronc]

I'd love feedback on this approach, which we have happily used to differentiate multisig vs public keys vs distribution contracts.

@ethanfrey thanks for sharing. If I understand correctly what you're doing, you're basically allowing for an address to be formed from a condition string which includes the type of key and the 20-byte address for that key. Is that roughly accurate? If that's the approach, I think the weakness would be that you're compressing even more information into a 20-byte space. My guess is that this would decrease the collision resistance because there are even more possible source conditions that can be mapped to the same address, but we'd probably need to talk to a professional cryptographer to know the details and how much security is/isn't lost.

[ethanfrey]

@aaronc you understood the main point.

Yeah, AFAIK, 20 bytes should be collision resistance when the preimages are unique and not malleable. A space of 2^160 would expect some collision to be likely around 2^80 elements (birthday paradox). And if you want to find a collision for some existing element in the database, it is still 2^160. 2^80 only is if all these elements are written to state.

The good example you brought up was eg. a public key bytes being a valid public key on two algorithms supported by the codec. Meaning if either was broken, you would break accounts even if they were secured with the safer variant. This is only as the issue when no differentiating type info is present in the preimage (before hashing into an address).

I would like to hear an argument if the 20 bytes space is an actual issue for security, as I would be happy to increase my address sizes in weave. I just figured cosmos and ethereum and bitcoin all use 20 bytes, it should be good enough. And the arguments above which made me feel it was secure. But I have not done a deeper analysis.

[robert-zaremba]

If at some point there is a vulnerability in algorithm A that allows some malicious user to hack these keys, this vulnerability affects all addresses with no associated pub key whether or not they were generated with algorithm A, B or C because at the SDK level all addresses overlap. So you will not be protected just because you were smart and chose B or C because you knew they were more modern and attack-proof. A simple one byte prefix would prevent this scenario.

Also with 20 bytes, the chance of a random collision attack does increase, thereby increasing the ease to double spend. With 20 bytes, the double spend difficulty is roughly 80 bits of security.

This depends on the implementation.
Signature validation is done using a Public Key, not an address. So it's not 20 bytes -- ed25519 public key is 256 bits = 32 bytes.

The problems is there only if all resources in the storage are identifiable by address.