Tangentially, depending on what your input and data model look like, canonicalisation takes O(nlogn) time (i.e. the cost of sorting your fields).
Here I describe an alternative approach that produces deterministic hashes without a distinct canonicalization step, using multiset hashing: https://www.da.vidbuchanan.co.uk/blog/signing-json.html
What's over my head possibly, from skimming it, about your multiset hashing is how it avoids the "these payloads have the same shape, so one could be re-sent as the other" issue? It seems like a solution to a different problem?
(I realise my comment reads a bit unclearly, it's basically two separate comments, split after the first paragraph)
(Not saying the signing problem in OP is invalid of course. Just a different problem.)
It doesn't matter if I sign the word "yes", if you don't know what question is being asked. The signature needs to included the necessary context for the signature to be meaningful.
Lots of ways of doing that, and you definitely need to be thoughtful about redundant data and storage overhead, but the concept isn't tricky.
I think this system is nice because it gives you compile-time guarantees that you can't sign without a domain separator, and you can't reuse a domain separator by accident. Also, I like the idea of generating these things randomly, since it's faster and scales better than any other alternative I could think of. And it even scales into some world where lots of different projects are using this system and sharing the same private keys (not a very likely world, I grant you).
#1 You sign a blob and you don't touch it before verifying the signature (aka "The Cryptographic Doom Principle") #2 Signatures are bound to a context which is _not_ transmitted but used for deriving the key or mixed into the MAC or what have you. This is called the Horton principle. It ensures that signer/verifier must cryptographically agree on which context the message is intended for. You essentially cannot implement this incorrectly because if you do, all signatures will fail to verify.
The article actually proposes to violate principle #2 (by embedding some magic numbers into the protocol headers and presuming that someone will check them), which is an incorrect design and will result in bad things if history is any indication.
Principles #1 and #2 are well-established cryptographic design principles for just a handful of decades each.
It's used exactly as you say: a shared context used as input for the signature that is not transmitted.
The OP is using unreadable hex strings in a way that obscures what’s actually going on. If you turn those strings into functionally equivalent text, then the signatures are computed over:
(serialized object, “This is a TreeRoot”)
func Verify(key Key, sig []byte, obj VerifiableObjecter) error
This API is wrong, full stop. Do not use this design. Sure, it might catch one specific screwup, but it will not catch subtler errors like confusing a TreeRoot that the signer trusts with a TreeRoot that means something else entirely. And it requires canonical encodings, which serves no purpose here. And it forces the verifier to deserialize unverified data, which is a big mistake.
The right solution is to have the sender sign a message, where:
(a) At the time of verification, the message is just bytes, and
(b) The message is structured such that it contains all the information needed to interpret it correctly.
So the message might be a serialization of a union where one element is “I trust this TreeRoot” and another is “I revoke this key”, etc. and the verification API verifies bytes.
If you want to get fancy and make domain separation and forward-and-backward-compatibility easier, then build a mini deserializer into the verifier that deserializes tuples of bytes, or at most UUIDs or similar. So you could sign (UUID indicating protocol v1 message type Foo, serialization of a Foo). And you make that explicit to the caller. And the verifier (a) takes bytes as input and (b) does not even try to parse them into a tuple until after verifying the signature.
P.S. Any protocol that uses the OP’s design must be quite tortured. How exactly is there a sensible protocol where you receive a message, read enough of it to figure out what type (in the protobuf sense) it contains such that there is more than one possible choice, then verify the data of that type? Are they expecting that you have a message containing a oneof and you sign only the oneof instead of the entire message? Why?
> it makes a concatenation of the domain separator (@0x92880d38b74de9fb) and the serialization of the object, and then feeds the byte stream into the signing primitive. Similarly, verification of an object verifies this same reconstructed concatenation against the supplied signature.
> Note that the domain separator does not appear in the eventual serialization (which would waste bytes), since both signer and receiver agree on it via this shared protocol specification. Encrypt, HMAC, and hash work the same way
> Note that the domain separator does not appear in the eventual serialization (which would waste bytes), since both signer and receiver agree on it via this shared protocol specification.
But saying it's about wasting bytes is a little confusing, as you observe that isn't really the point.
Domain separation happens in the input to the hash function, not on the wire. Because what arrives off the wire is UNTRUSTED input.
It seems like Horton Principle just says "all messages have ≤1 meaning". If a message signed by key X must be parsed using the canonical encoding, then aren't we done?
There is still room for danger. e.g., You send `GetUserPermissionLevel(user:"Alice")` and server responds with `UserNicknameIs(user:"Alice", value:"admin")`. If you fail to check the message type, you might get tricked.
Maybe it's nice if it was mathematically impossible to validate the signature without first providing your assumptions. e.g., The subroutine to validate message `UserNicknameIs(user:"Alice", value:"admin")` requires `ServerKey × ExpectedMessageType`. But "ExpectedMessageType" isn't the only assumption being made, is it?
You might get back `UserPermissionLevel(user:"Bob", value:"admin")` or `UserPermissionLevel(user:"Alice", value:"admin", timestamp:"<3d old>")`. Will we expect the MAC to somehow accept a "user" value? And then what do we do about "timestamp"?
Maybe we implement `ClientMessage(msgUuid: UUID, requestData:...)` and `ServerResponse(clientMsgUuid: UUID, responseData:...)`, but now the UUID is a secret, vulnerable to MITM attack unless data is encrypted.
It seems like you simply must write validation code to ensure that you don't misinterpret the message that is signed. There simply isn't any magic bullet. Having multiple interpretations for a sequence of bytes is a non-starter (addressed in the post). But once you have a single interpretation for a sequence of bytes, isn't it up to the developer to define a schema + validation logic that supports their use case? Maybe there are good off-the-shelf patterns, but--again--no magic bullets?
See my other comment here. By the time you call the OP’s proposed verify API you have already screwed up as a precondition of calling the API.
I didn't know that Protobuf wasn't canonical but even without this knowledge, there are many other factors which make it an inferior format to JSON.
Also, on a related topic; it seems unwise that essentially all the cryptographic primitives that everyone is using are often distributed as compiled binaries. I cannot think of anything more antithetical to security than that.
I implemented my own stateful signature algorithm for my blockchain project from scratch using utf8 as the base format and HMAC-SHA256 for key derivation. It makes it so much easier to understand and implement correctly. It uses Lamport OTS with Merkel MSS. The whole thing including all dependencies is like 4000 lines of easy-to-read JavaScript code. About 300 lines of code for MSS and 300 lines for Lamport OTS... The rest are just generic utility functions. You don't need to trust anyone else to "do it right" when the logic is simple and you can read it and verify it yourself! Simplicity of implementation and verification of the code is a critical feature IMO.
If your perfect crypto library is so complex that only 10 people in the world can understand it, that's not very secure! There is massive centralization and supply chain risk. You're hoping that some of these 10 people will regularly review the code and dependencies... Will they? Can you even trust them?
Choosing to use a popular cryptographic library which distributes binaries is basically trading off the risk of implementation mistake for the risk of supply chain attack... Which seems like a greater risk.
Anyway it's kind of wild to now be reading this and seeing people finally coming round to this approach. I've been saying this for years. You can check out https://www.npmjs.com/package/lite-merkle feedback welcome.
If strict typing and versioning are useless to you, sure.
extend google.protobuf.MessageOptions {
optional uint64 domain_separator = 1234;
}
message TreeRoot {
option (domain_separator) = 4567;
...
}This solves the message differentiation problem explicitly, makes security and memory management easier, and reduces routing to:
switch(msg.msgId): …
We can let one be managed by ICANN and the others various competing offerings on ETH.
[1]
I think that's what you mean by digest, but maybe you just mean `type` = `magic number`
Crypto is hard. Do it right. Get help from your tools. 'Nuff said.
Jeeze, I'm getting too old for this crap.
(edit on where the OIDs can be, and added another CVE)
>Forge (also called `node-forge`) is a native implementation of Transport Layer Security in JavaScript. Prior to version 1.3.0, RSA PKCS#1 v1.5 signature verification code is lenient in checking the digest algorithm structure
That's on brand for the javascript world, yes.
With asn1 being a can of worms, at least it's a can of worms with a reputation, unlike this nice magic trick.
Disclaimer: there exists a PR filled under my name into an asn.1 parser that fixes a bug, which is not merged since October 2022.
https://github.com/digitalbazaar/forge/commit/3f0b49a0573ef1...
- to have a convention to, instead of signing “payloads, to always sign “type identifier + payload”, to prevent adversaries from reusing your signature to sign the same payload, interpreted as a different type.
- use 64-bit type identifiers
- put the identifiers in the IDL (may need augmenting IDL to allow that)
#1 makes sense to me; #3 also makes sense, as that’s the place where people will have to look to learn about your types.
#2, I think, is up for discussion. These could be longer, Java-like strings “com.example.Foo”, or whatever.
I think some people also may disagree with the argument that putting type identifiers inside the payload makes messages too large, but I don’t have enough experience on that to make a judgment.
This is another example where you would think that "who it's for" is something the sender would sign but nope!
[1] https://theworld.com/~dtd/sign_encrypt/sign_encrypt7.html [2] https://computerresearch.org/index.php/computer/article/view...
Careful. I argue this is even worse. In this convention, you need to change the behavior of others. If I send a message to Alice with contents "Hey, I can't meet today" using your sign-encrypt-sign scheme, then Alice can take the inner most layer and use it to impersonate me. Alice can send "Hey, I can't meet today" to Bob at any time. I must rely on Bob demanding proof that he was, in fact, the intended recipient.
From the first link:
> Note though that an effective security standard should require not only that the author must provide one of these five proofs, but also that the recipient must demand some such proof as well.
If your convention was upgraded into a protocol with automatic verification, then that would be different.