Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Signing data structures the wrong way

blog.foks.pub

Post reply on HN
Print view View original

31–40 of 59 posts

Re: Signing data structures the wrong way

#31

Post by maxtaco »

lukev wrote: post #20

So, isn't this a rather longwinded way to say that a signature only extends to the scope of the message it contains? 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 c…

Hi, post author here. Agree that the idea isn't tricky, but it seems like many systems still get it wrong, and there wasn't an available system that had all the necessary features. I've tried many of them over the years -- XDR, JSON, Msgpack, Protobufs. When I sat down to write FOKS using protobufs, I found myself writing down "Context Strings" in a separate text file. There was no place for them to go in the IDL. I had worked on other systems where the same strategy was employed. I got to thinking, whenever you need to write down important program details in something that isn't compiled into the program (in this case, the list of "context strings"), you are inviting potentially serious bugs due to the code and documentation drifting apart, and it means the libraries or tools are inadequate.

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).

Re: Signing data structures the wrong way

#32

Post by amluto »

ahtihn wrote: post #6
formerly_proven wrote: post #4

This article claims that these are somewhat open questions, but they're not and have not been for a long time. #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/v…

Maybe I'm misunderstanding the article but I'm fairly sure the magic number is not transmitted. It's used exactly as you say: a shared context used as input for the signature that is not transmitted.

You’re right, but I think the commenter you’re replying to is also right.

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”)
and the verifier calls the API:

    func Verify(key Key, sig []byte, obj VerifiableObjecter) error
(I assume they meant Object not Objector.)

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?

Re: Signing data structures the wrong way

#33

Post by amluto »

Muromec wrote: post #14
formerly_proven wrote: post #4

This article claims that these are somewhat open questions, but they're not and have not been for a long time. #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/v…

The article proposes a way to agree on context out of band and enforce it with idl. This seems to be an implementation of the principle you mention

No, it’s completely wrong. It’s a very minor refinement of a terrible yet sadly common design that merely mitigates one specific way that the terrible design can fail.

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.

Re: Signing data structures the wrong way

#34

Post by actionfromafar »

kccqzy wrote: post #30
majormajor wrote: post #5

Earlier quoted context omitted.

I think a lot of people assume that the "name" of the type, for protos, will be preserved somewhere in the output such that a TreeRoot couldn't be re-used as a KeyRevoke. It makes sense that it isn't - you generally don't want to send that name every time - but it's non-obvious to people with a object-oriented-language background who just think "ah, different types are obviously different types." The serialization co…

This is just a mismatch between nominal typing and structural typing. Protobuf is basically structural typing. You can serialize a message defined with one schema and deserialize the result to a message with a different schema if the two schemata are compatible enough. Almost all normal programming languages use nominal typing. If you have `struct A {int a; int b};` it is distinct from `struct B {int a; int b};`.

C does too as a language, but it’s fairly easy to slip up at link time or runtime. At some point the types melt away and you sit there with pointers and offsets. Again, it’s not strictly the language’s fault (I think, I’m far from a standards lawyer).

Re: Signing data structures the wrong way

#35

Post by actionfromafar »

maxtaco wrote: post #28
cogman10 wrote: post #25

Why not digest the type as part of the hash? This avoids the problem in the article and keeps the transmission size small.

It should be possible to change the name of the type, and this happens often in practice. But type renames shouldn't break preexisting signatures. In this scheme you are free change the type name, and preexisting signatures still verify with new code -- of course as long as you never change the domain separator, which you never should do. Also you'd need to worry about two different projects reusing the same type nam…

That’s easily addressed. We just need a global immutable registry of types, their names, an alias list and revocation list. ;-)

We can let one be managed by ICANN and the others various competing offerings on ETH.

Re: Signing data structures the wrong way

#36

Post by HanyouHottie »

tennysont wrote: post #26
logicallee wrote: post #12

along the same lines, did you know that you can get an authenticated email that the listed sender never sent to you? If the third party can get a server to send it to themselves (for example Google forms will send them an email with the contents that they want) they can then forward it to you while spoofing the from: field as Google.com in this example, and it will appear in your inbox from the "sender" (Google.com)…

I asked about this on the PGP mailing list at one point, and I think I was told that the best solution is to start emails with "Hi ," which seems like a funny low-tech solution to a (sad) problem.

The solution to this problem without needing to modify your message is to use a protocol that will sign, then encrypt, then sign again. See section 5 here [1] or section 15 here [2].

[1] https://theworld.com/~dtd/sign_encrypt/sign_encrypt7.html [2] https://computerresearch.org/index.php/computer/article/view...

Re: Signing data structures the wrong way

#37

Post by efitz »

When my data structures are messages to be sent over a network, I always start with msgId and msgLen, both fixed width fields.

This solves the message differentiation problem explicitly, makes security and memory management easier, and reduces routing to:

switch(msg.msgId): …

Re: Signing data structures the wrong way

#38

Post by themafia »

maxtaco wrote: post #21
Muromec wrote: post #11

So another lesson had been relearned from asn.1. I'm proud of working in this industry again! Next we will figure out to always put versions into the data too

I would say two problems with the asn.1 approach are: (1) it seems like too much cognitive overload for the OIDs to have semantic meaning, and it invites accidental reuse; I think it matters way more that the OIDs are unique, which randomness gets you without much effort; and (2) the OIDs aren't always serialized first, they are allowed to be inside the message, and there are failures that have resulted ( https://nvd…

Those CVEs seem a little more subtle than OID serialization issues. In the first example there are actually two distinct problems in concert that lead to the vulnerability, one of which is when a "low public exponent" is used.

https://github.com/digitalbazaar/forge/commit/3f0b49a0573ef1...

Re: Signing data structures the wrong way

#39

Post by themafia »

tennysont wrote: post #23
formerly_proven wrote: post #4

This article claims that these are somewhat open questions, but they're not and have not been for a long time. #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/v…

Hmmmm. I agree that an ad-hoc implementation with protobufs can go wrong. But presumably, 1 canonical encoding for the private key constitutes the Horton principle? 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")` a…

Are keys that expensive to generate? You could have a unique signature key for each data type.

Re: Signing data structures the wrong way

#40

Post by maxtaco »

themafia wrote: post #38
maxtaco wrote: post #21

Earlier quoted context omitted.

I would say two problems with the asn.1 approach are: (1) it seems like too much cognitive overload for the OIDs to have semantic meaning, and it invites accidental reuse; I think it matters way more that the OIDs are unique, which randomness gets you without much effort; and (2) the OIDs aren't always serialized first, they are allowed to be inside the message, and there are failures that have resulted ( https://nvd…

Those CVEs seem a little more subtle than OID serialization issues. In the first example there are actually two distinct problems in concert that lead to the vulnerability, one of which is when a "low public exponent" is used. https://github.com/digitalbazaar/forge/commit/3f0b49a0573ef1...

It seems like in that PR, the fact that the OID wasn't checked is part of the problem. I think a better system wouldn't compile or would always fail to verify if the OID (domain separator) is wrong, and I think you'd get that behavior in the posted system.
Post reply on HN