Recommend constant-time decoding of `secretKeyMultibase`

[silverpill]

Section 2.2.2 Multikey requires secret keys to be encoded using the base-58-btc alphabet. Example:

The encoding of an Ed25519 secret key MUST start with the two-byte prefix 0x8026 (the varint expression of 0x1300), followed by the 32-byte secret key data. The resulting 34-byte value MUST then be encoded using the base-58-btc alphabet, according to Section 2.4 Multibase, and then prepended with the base-58-btc Multibase header (z).

However, it is not mentioned that non-constant-time implementations of the encoding/decoding algorithm may lead to a key leakage (side-channel attack). Also, the algorithm specified in section 3.2 Base Decode may be not constant-time, as one of implementers explained in this comment: https://codeberg.org/fediverse/fep/issues/710#issuecomment-8154767

[dlongley]

I think the spec should probably be relaxed to allow base64url to be used, at least for secret keys.

Unfortunately, I think there are two competing security goals here: A desire for public key characters to not be confused with others (calls for base58 for public keys) and a desire for constant time implementations (at least when decoding) for secret keys (calls for base64url for secret keys).

Choosing base64url everywhere creates a problem for public keys -- and choosing base64url base58 everywhere creates a problem for secret keys. Choosing base58 for public keys might lead someone to mistakenly use this for secret keys (with a non-constant time implementation). Choosing base64url for secret keys might lead someone to mistakenly use this for public keys, leading to confusion attacks.

There doesn't seem to be a mitigation for the confusion attacks -- though having good constant time base58 decoders (even if challenging to write) does mitigate the other side. Given this, perhaps we should adjust the spec to say secret keys SHOULD be base64url encoded but MAY be base58 encoded (for backwards compatibility) -- and keep the public key requirements the same. Lastly, even though a constant-time base64url implementation is simpler than a base58 one, a developer could still also mistakenly use a non-constant time base64url implementation.

I will note that secret keys should NEVER be published in controller documents anyway, best practice is to use HSMs for high value use cases, and how one stores their secret keys is largely totally irrelevant wrt. the CID spec. There was simply a request in the working group to specify the secret key side of key expression in this specification -- but it's really public key expression that is important here, not what one does with secret keys. Some participants did not even want to say anything about secret keys -- because any advice could be taken too be too prescriptive, which may also be the case here.

EDIT: Fixed a confusing typo, thanks, @TallTed!

[TallTed]

@dlongley —

Choosing base64url everywhere creates a problem for public keys -- and choosing base64url everywhere creates a problem for secret keys.

I'm pretty sure one of those base64url should be base58, because as written, base64url creates a problem for both public and secret keys, so base64url should be eliminated as a candidate.

EDIT: This was fixed.

[interru]

A desire for public key characters to not be confused with others (calls for base58 for public keys)

If the only choices are base58 and base64, perhaps. But there is also base32.
I would argue in general, though, that the number of people who read and compare keys manually is converging to zero.
And if a key handling process of an implementation is forcing you to do that, it already is insecure.
Nobody wants to read base encoded data, and nobody should have to.

[dlongley]

A desire for public key characters to not be confused with others (calls for base58 for public keys)

If the only choices are base58 and base64, perhaps. But there is also base32.

True, though choices of this sort are also largely influenced by existing implementation availability in the ecosystem (which was and is base58-btc and base64url). There is frequently a better hash function or other cryptographic choice that exists when building global standards, but implementation availability (and implementers) drive what choices are made within a subset of options that pass various thresholds (e.g., security level). Since this specification is one for public documents, the decisions were made based on existing implementations and expression of public key material.

I don't think anyone should take away from this spec that how keys are to be expressed publicly means that there are extremely rigid requirements on secret keys -- and this is something we now know we ought to make more clear in the specification.

I would argue in general, though, that the number of people who read and compare keys manually is converging to zero.

I would also hope that the number of people who use non-constant time libraries to process secret key material will similarly converge to zero, but this these sorts of arguments or hopes are somewhat orthogonal to risk assessment. The arguments made in the related fediverse thread above, for example, are about concerns with what people "may do", not what people generally are doing. So if we're going to be consistent, the "we're converging or will likely converge" arguments aren't driving the conversation; we're worried about the outliers.

Btw, I do hear the echo "then don't recommend a secret key expression that might take convergence in another direction". That was definitely not the intention here. Like I said I don't think anyone in the Working Group intended this spec to be about secret key management. So we should probably help readers who have that takeaway not feel like they can't do whatever best practice suggests.

Secret key expression was merely specified here to be "complete" -- and was helpful for generating test vectors. I suggest the spec be more clear on this point and explicitly say: please use an HSM and whatever other best practices for managing secret keys; do not copy what's going on with secret key management in the test suite as that isn't intended for production systems.

And if a key handling process of an implementation is forcing you to do that, it already is insecure. Nobody wants to read base encoded data, and nobody should have to.

Yet, they do and continue to in many cases. I would not be at all surprised at how common this is and will continue to be -- and I expect it to be a harder problem to solve than to ensure a particular library is in use. And, again, one does not need to use base58 encoding for secret keys anyway because there's no interop there, the interop is with the public keys. Lastly, in the same vein of "...it already is insecure", one could add: if an attacker is able to trigger your system to load or decode the same secret key many times frequently, you might already have bigger problems too.

[interru]

True, though choices of this sort are also largely influenced by existing implementation availability in the ecosystem (which was and is base58-btc and base64url).

Except for BTC, cryptocurrencies, projects that are close to cryptocurrencies, and a few select sites, there is not much usage of base58. And in some instances it is considered legacy.

The examples that were used to illustrate the widespread adoption in this discussion are also really not convincing from my perspective. Some of the statements I couldn't verify, and some I could falsify.

Adoption can be quantified in this case. For example, using downloads from software repositories of languages where base encodings aren't built-ins.

Rubygems:

• base64: 310.840.581 (in bundled-gems, so adoption might be higher)
• base32: 48.323.510
• base58: 2.995.149

Even if you limit your view on the ecosystem around cryptocurrencies. The effects and impacts outside an ecosystem have to be considered. This spec is getting slowly adopted by projects outside the ecosystem.

Base64 and Base32 are defined in an rfc. There is no spec/rfc/standard describing base-58-btc. There is only a draft. The only reason you had to include an algorithm for de-/encoding is because there wasn't a spec that you could refer to.

Using base-58-btc as a MUST does look to me like a decision based on biased subjective preference.
base-58-btc isn't widespread, and it isn't standard. Choosing it was an odd choice with not a lot of justification.

I would also hope that the number of people who use non-constant time libraries to process secret key material will similarly converge to zero

You say that even though this spec here itself made the mistake of including a variable-time algorithm.

are about concerns with what people "may do"

We are beyond "may do" already. People are using variable-time base58 for secret keys.
And there are incorrect implementations of constant-time base58 floating around.

Lastly, in the same vein of "...it already is insecure", one could add: if an attacker is able to trigger your system to load or decode the same secret key many times frequently, you might already have bigger problems too.

That's common. Base encodings are primarily used to put data in text formats where binary can't directly be used. For instance, a DB query language (depending on the DB you are using).

[dlongley]

True, though choices of this sort are also largely influenced by existing implementation availability in the ecosystem (which was and is base58-btc and base64url).

Except for BTC, cryptocurrencies, projects that are close to cryptocurrencies, and a few select sites, there is not much usage of base58. And in some instances it is considered legacy.

The examples that were used to illustrate the widespread adoption in this discussion are also really not convincing from my perspective. Some of the statements I couldn't verify, and some I could falsify.

I hear your opinion. Please note that it would be just one of many in a Working Group setting, which requires balance and consensus in the face of potentially many competing opinions of others in the group, other data shared from various ecosystems of interest, and anything else that others bring to the table.

Adoption can be quantified in this case. For example, using downloads from software repositories of languages where base encodings aren't built-ins.

Rubygems:

• base64: 310.840.581 (in bundled-gems, so adoption might be higher)
• base32: 48.323.510
• base58: 2.995.149

Heard. If you aren't already, please do consider other ecosystems as well. For a deeper analysis, one could explore what percentage of these packages provides a constant time implementations (including base64, base32, and base58). If the argument is that everyone is just going to use any of these packages, but they are not themselves constant time, it would seem to cut against the choice mattering (in that dimension). However, perhaps these popular packages are all constant time for base64 and base32, and it would certainly help support the position that base64 and base32 would be safer bets for expressing private key material -- in the Ruby ecosystem.

I still think a simpler solution here is: Don't use private keys that are encoded in this way at all. Don't store private keys in plain text in production systems and use HSMs wherever possible. I understand this isn't always possible or that transitions to accomplish this over time must be made.

Even if you limit your view on the ecosystem around cryptocurrencies. The effects and impacts outside an ecosystem have to be considered. This spec is getting slowly adopted by projects outside the ecosystem.

I agree that this is an important consideration.

Base64 and Base32 are defined in an rfc. There is no spec/rfc/standard describing base-58-btc. There is only a draft. The only reason you had to include an algorithm for de-/encoding is because there wasn't a spec that you could refer to.

As an aside: have you looked at those RFCs to determine if they discuss the importance of constant time implementations, provide a constant time algorithm, link to one or, conversely, do not link to one that is not constant time?

Using base-58-btc as a MUST does look to me like a decision based on biased subjective preference. base-58-btc isn't widespread, and it isn't standard. Choosing it was an odd choice with not a lot of justification.

Speaking for myself, I don't personally care whether the alphabet is X or Y or the base is A or B, but it does matter to me that the choice isn't so disruptive to existing ecosystems so you don't get the interoperability that is desired. I believe decisions were made in good faith by the members of the Working Group who shared these goals. Please do also remember, that there are many, many decisions to be made by the Working Group over a relatively short period of time, some of which may take weeks or months to deliberate and significant emotional energy -- all by volunteers who have one or more other full time jobs. This was just one decision, and probably thought to be a lesser one given the others that required more work to achieve consensus.

Also, in some sense, every decision is based on a "biased subjective preference". The means by which to precisely and objectively measure, say, the use per capita of base58 vs. base32 for some population of interest was not on offer at the time (and still isn't now).

The preference for base58 was from Working Group participants who thought that that base58 was in sufficiently wide use in the implementation areas of interest at the time and that it would cause the least disruption to those implementers (and that there was an advantage in alphabet choice for public key expression). This was, of course, for each individual, constrained to some base level of effort for researching and thinking on the question. So, please don't presume bad faith. Also, I don't think base32 was even a significant option at the time because it was not considered to be in wide use for the use cases at hand.

I would also hope that the number of people who use non-constant time libraries to process secret key material will similarly converge to zero

You say that even though this spec here itself made the mistake of including a variable-time algorithm.

Though, I also said that this spec is fundamentally for expression public information, not private / secret -- so that's where the focus of the group was. Timing does not matter for the public case. I understand the concern that someone might reuse code for the public keys to express private keys -- and our mistake, I believe, was to not speak more strongly about this, since we also were compelled to write something down for "completeness" and for the test suite for the private key material expression. This context isn't there for readers of the spec, understandably, so we find ourselves having this discussion. I've proposed some remedies above with this perspective, but it will be up to the Working Group to decide how to take action; I'm just one voice.

are about concerns with what people "may do"

We are beyond "may do" already. People are using variable-time base58 for secret keys. And there are incorrect implementations of constant-time base58 floating around.

Again, I would encourage you to investigate whether the base32 and base64 libraries that are in use and popular are constant time implementations or not. One could even argue that it would be an easier battle to win against non-constant time implementations to pick the less popular encoding (presuming existing popular libraries are non-constant time). This would be because you wouldn't have to upgrade or worry about reuse of existing non-constant time libraries. One could imagine someone filing an issue that says we should have picked something entirely new because the existing landscape is a "lost cause of non-constant time implementations". I only offer this argument to demonstrate how wide the perspectives can get -- and considering them in getting to consensus is an important part of the standards-making process.

Anyway, I agree it's a problem for people to use non-constant time implementations with secret material and have proposed some ideas above for the Working Group to consider on what to say here. I don't think merely changing to base32 (which would be a big breaking change) would suddenly alleviate the problem either. We'll have to say a little more about how this spec is for public key expression, best practices should be followed for private keys, including not storing any private keys in plain text anywhere.

Lastly, in the same vein of "...it already is insecure", one could add: if an attacker is able to trigger your system to load or decode the same secret key many times frequently, you might already have bigger problems too.

That's common. Base encodings are primarily used to put data in text formats where binary can't directly be used. For instance, a DB query language (depending on the DB you are using).

I believe it's usually a mistake to store private keys in plain text. I agree that it's the case that it's sometimes done, either for expediency's sake -- with an eye toward later improvement based on current risk assessments (which hopefully also would cover the non-constant time decoding issue). So, the advice I would give is to first, use an HSM, if you can't do that, encrypt your private keys which should involve encrypting them in raw form, not any bloated base-encoded form, thus making this entire consideration irrelevant -- as it can wholly disconnect you from anything this specification has to say on private key expression. For example, use COSE (CWE) or JOSE (JWE) to encrypt your keys which will (or can) use base64url encoding for text-based storage.

If you must store your private keys in plain text in your database, make sure your risk profile is such that you don't expect a stolen database in the near term and you don't expect timing attacks to be feasible -- at least until you are able to adjust to use an HSM or encrypted private keys instead.

[dlongley]

Noticing the length of my own posts getting longer here, I'd say there's little reason to rehash past decisions and we ought to focus on what concrete changes can be sensibly made to the specification to help address the raised issue.