Can ordering be enforced in msgpack.

Is there a way that we can make msgpack respect and enforce ordering on serialisation.

This is very important from a cryptographic usecase. I can take any arbitrary map, list and so on, in any language and produce the same cryptographic hash for that content. E.g.

import msgpack
import hashlib
print hashlib.sha256(msgpack.packb({"a": 4, "b": 6})).hexdigest()

But this means that ordering must be respected on serialization even between languages. I can see this being implemented as a serializer flag that ensures that any iterable passed is emitted in the order it was given.

No. There was discussion about "canonical" form. But no conclusion.

Could we restart this discussion? Its a really important requirement for us and we cannot find any predictable serialisation format.

What about bencode?

BTW, your example is unclear. What is order? Python's dict doesn't have order. (I made patch
for preserving order, but I don't know it will be reviewed before Python 3.6 beta).

Did you mean lexicographical order?

Fair point on the example being not quite right. Order should be defined by iteration. An example can be seen with OrderedDict, this will iterate based on insertion order, if any other order is needed just create an iterator that provides key, value in that order.

I haven't seen bencode before I will look into it.

msgpack-python/pull/164

Actually achieves exactly what I was hoping for but it was rejected.

@jkbbwr

@jkbbwr I can't get what you said. OrderedDict's iteration order is "insertion order", and msgpack/msgpack-python#164 is order defined by <. (BTW, current implementation follows
iteration order).

And as I've commented in msgpack/msgpack-python#164, sorting dict key is not enough
for stable output.

If canonical order is specified in msgpack, I'll add option for it.
But I don't want to add option for such an incomplete thing. msgpack-python has tons of options, already.

Then what steps are needed to define canonical order for msgpack?
Is there a first step to drawing it up?

@frsyuki

Join ML
Attract some languages most common msgpack library developers' interest. (It may require some realistic usecases)
Get final agreement from @frsyuki

It may take few years. Why don't you try bencode first?

If you're intending to have a canonical representation of MessagePack for cryptographic hashing purposes, you're going to run into a lot more problems than just map order. For example:

MessagePack does not enforce a canonical representation of integers. The number -20 could be encoded as EC, D0 EC, D1 FF EC, and more. Most MessagePack encoding libraries write non-negative as unsigned and choose the shortest representation (discarding the signedness and size of static types), but this is not required of the spec. Bugs are regularly filed against MessagePack libraries asking for ways to preserve signedness of static types or detect the original serialized width of parsed integers, and for good reason: the spec allows these so it's reasonable to assume you can use them to store semantically relevant information.
Similarly, MessagePack does not enforce canonical widths for any of its blobs or compound types. This is especially important because the str8 type did not exist in the old MessagePack spec, and the lack of size enforcement means that messages produced by old libraries are forward-compatible with new ones. Many libraries also have a "compatibility mode" where they only use fixstr/str16/str32 to continue to produce messages that can be parsed by both old and new parsers. A canonical representation of MessagePack would prevent all backwards compatibility.
Most MessagePack libraries in dynamic languages do not preserve float width. They just convert everything to a 64-bit double. If you have a 32-bit float in your message, decoding and re-encoding it in Python or Go will produce a 64-bit double. They might do other damage even to float64 such as normalizing NaNs or modifying subnormal floats.
MessagePack does not enforce uniqueness of map keys. Some implementations will allow them to be produced, and implementations will treat duplicate map keys differently. Does your implementation reject messages with duplicate keys? Does it give you a map that allows duplicates? If it silently ignores duplicates, does it give you the first value or the last one? These are potential security vulnerabilities in your cryptographic hash so you need to be absolutely sure what happens here. This also ignores other higher-level considerations of unicode equivalence. It's common to want to normalize keys which can create more duplicates.
The MessagePack spec officially requires UTF-8 in strings, but different libraries have different ways of dealing with this. The C/C++ reference implementation (last I checked) does not enforce UTF-8: it allows any arbitrary byte sequence. The Java implementation on the other hand cannot preserve invalid sequences: the options are either to replace invalid bytes with the unicode replacement character (U+FFFD) or reject the message. If a C/C++ message is produced containing a string with an invalid UTF-8 sequence, it is not possible for the Java implementation to decode and re-encode it. Again the transformation to replacement characters here is a potential security vulnerability.

Map order is perhaps the biggest issue that prevents a canonical representation, but it is by no means the only one, and as others have mentioned it is not trivial to define a canonical map ordering. As much as I dislike this non-answer to your original question, what you're trying to accomplish by encoding a message and hashing the result is not a good idea in the first place. MessagePack simply does not have a canonical representation and probably never will. The spec would require far too much additional work and restrictions to impose canonicalization.

If you want a cryptographic hash of a MessagePack message that is preserved across re-encoding, you will need to define your own hashing algorithm on the parsed data rather than the encoded form. You will need to be very careful of vulnerabilities such as the ambiguity of silently ignoring duplicate keys. You should reject ambiguous messages, preserve only those parts that are semantically relevant to you, and normalize the rest. For example reject messages with invalid UTF-8, NFC-normalize all keys (or simply reject non-ASCII keys), reject messages with duplicate map keys (both before and after string normalization), sort maps in ascending order of NFC UTF-8 representation of keys, hash all integers as 64-bit (and ensure that you handle u64 correctly), figure out what to do with floats (possibly reject them altogether), etc.

tl;dr don't do this.

"don't do this" isn't exactly helpful to solving the problem. But thanks for the advice. I will be looking into other ideas.

I can mention that regarding order of map elements, there was a discussion on the erlang-questions ML (in short: erlang doesn't guarantee map element ordering, except in comparisons).

One conclusion was that since most language environments with a map type don't nail down the element ordering, a map is inherently unsuited as a portable representation, regardless of how it's serialized for transport. Better then to use arrays, which do have a defined order.

Essentially, this would be an argument that a canonical encoding in msgpack would not have to address map element ordering, since this cannot be relied on across language environments anyway. Addressing the basic data types would then be sufficient.

(An exception, of course, would be a 1-element map, so an array of 1-element maps could be a viable representation.)

python3: make conversion to string deterministic

call.test.py (deep_dict_convert)

test: fix call.test.py (deep_dict_convert)

test: make box-py/call.test.py compatible with python 2 and 3

test: make box-py/call.test.py compatible with Python 2 and 3

test: make output of box-py/call.test.py deterministic

Navigation Menu

Repository navigation

Can ordering be enforced in msgpack. #215

8 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Can ordering be enforced in msgpack. #215

Description

Activity

methane commented on Aug 24, 2016

jkbbwr commented on Aug 24, 2016

methane commented on Aug 24, 2016

jkbbwr commented on Aug 24, 2016

jkbbwr commented on Aug 24, 2016

methane commented on Aug 24, 2016

jkbbwr commented on Aug 24, 2016

methane commented on Aug 24, 2016

ludocode commented on Aug 28, 2016

jkbbwr commented on Aug 29, 2016

uwiger commented on Mar 20, 2018

8 remaining items

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions