Triblers EC sicgnature scheme is not compatible with Crypto++

[DavidXanatos]

I tried to parse some tribler messages using a c++ app with crypto++ as crypto library for EC with GF(2^n) and run into a major issue, the signature length and format tribler uses is not compatible with the signature length crypto++ expects.

Also, tribler pads the "s" and "r" parameter sometimes with 0's
for the 4 curves setup in tribler,
the mismatch is a follows:

if (signature_length == 58) // as returned by crypto++ Verifier::SignatureLength
signature_length = 60; // as used by tribler
else if (signature_length == 102)
signature_length = 104;
else if (signature_length == 42)
signature_length = 42;
else if (signature_length == 144)
signature_length = 144;

the padding is applied for the key lengths that have here a mismatch, and its always one 0 byte for "s" and one for "r".
So if tribler would calculate the signature length correctly it wouldn't not need any padding.

tribler gets the expected signature length by
"int(ceil(len(ec) / 8.0)) * 2" where "len(ec)" is "m2.ec_key_keylen(ec.ec)" and "ec_key_keylen" is a wrapper for open ssl call "EC_GROUP_get_degree"

to get the right length

it is nececery to use ECDSA_size (\openssl-1.0.2a\crypto\ecdsa\ecs_lib.c) I think however this call returns the key size in DER encoding and not raw a.k.a. naked "r" and "s" concatenated.
the function is however almost right, what we want is the intern parameter "i" inside ECDSA_size, that is fed to "ret=ASN1_object_size(1,i,V_ASN1_SEQUENCE);"
looking into \openssl-1.0.2a\crypto\asn1\asn1_lib.c, ASN1_object_size we notice that we can recover "i" from the "ret" that is returned by ECDSA_size.

exposing ECDSA_size by adding
def get_ec_key_size(self):
assert m2.ec_key_type_check(self.ec), "'ec' type error"
return m2.ec_key_size(self.ec)
to M2Crypto/EC.py

and

adding changing dispersy/crypto.py
def get_signature_length(self, ec):
"""
Returns the length, in bytes, of each signature made using EC.
"""
sig_len = int(ceil(len(ec) / 8.0)) * 2

    der_len = ec.get_ec_key_size()

    der_len -= 2
    tmp_len = der_len
    if tmp_len > 128:
        while tmp_len > 0:
            tmp_len -= 1
            tmp_len >>= 8
            der_len -= 1
    der_len -= 6

    return sig_len

gives us the length as expected by crypto++ inside the der_len variable

to sum up:

ECDSA_size uses group = EC_KEY_get0_group(key); EC_GROUP_get_order(group, order, NULL to find out the signature length

while the tribler approach uses group = EC_KEY_get0_group(key); EC_GROUP_get_degree(group)

crypto ++ also takes the groupe_order to determine the signature length

so crypto++/ECDSA_size approach appears to me to be the correct one, get_degree seams to give only an upper bound for the signature length.

I don't know how feasible is this particular mod, as it requiters changing M2Crypto/EC.py that is some ware under /usr/lib/python...

therefor I would recommend to store the signature length before the signature inside the packets,
as the function create_signature(self, ec, data): from dispersy/crypto.py gets the actual length of "r" and "s" when it creates them.

PS: in addition to the key size issue there seams to be some additional incompatibility, sometimes signature test fails in the crypto++ based app but not in the triller client.

[synctext]

@NielsZeilemaker
You known why we append in this way perhaps?

[NielsZeilemaker]

Hi @DavidXanatos, you're quite right. The signature created by the M2CryptoSK class in crypto.py isn't compatible with any standard. As you discovered, the original developer decided to pad the r and s values with 0s and use a fixed length signature depending only on the curve (type).

I'm not a big fan on this, and I'd rather use the DER format eventhough that would add some small overhead. However, in order to preserve compatibility with messages created in the past, and by users of older versions of Dispersy we can't really switch to the DER encoding.
Moreover, you're fix of the signature_length method, although very interesting, would also not be backwards compatible.

If you're developing a new community, you could switch to the curve25519 curve. That's a wrapper of libnacl's dual-key (http://libnacl.readthedocs.org/en/latest/topics/dual.html), which should be easily parsable with c++.

I'm thinking of switching to this curve as the default in Dispersy, and deprecating the M2Crypto curves to encourage new communities to use the 25519.

[DavidXanatos]

I know that that would break compatibility, but would this be so much of an issue?
You could implement the fix depending on the dispersy version this way you could phase out old clients slowly, and once the majority of clients are up to date remove the old implementation.

[NielsZeilemaker]

I agree, if we push a new version of Dispersy and force everyone to upgrade, then at some point in time we wouldn't have this problem anymore.

However, communities are actually storing many of the messages created by Dispersy. For instance, in Tribler we have the AllChannelCommunity. This community stores votes created by users of older versions of Dispersy. These votes are dispersy messages, signed with the implementation currently used. Hence, we wouldn't be able to drop support for the current implementation without losing the ability to verify the signatures of these old messages.

For the peers that already received and verified those messages that isn't really a problem. But for new peers joining and synchronizing all these older messages, it will. As they still need to verify the signatures of the messages after receiving them.

E.g. if we remove/phase old this old method of generating/verifying signatures, we would lose all those messages from existing communities.

[DavidXanatos]

hmm... this is a issue indeed I haven't looked into the code in full detail (to many things to little time) but, does the messages have no expiration date?

It appears to me to be a significant issue in the designs scalability if it caches everything ever posted forever that may lead to the system collapsing at some point in future.

Also that means that the system caches not only the messages but also the "disperse-identity" messages to always be able to provide the key for verification?

And are there any limitations currently in place how many identity's a attacker having only a limited count of IPv4's to his disposal (I mean really limited like <= 8) can assume (running one modified malicious tribler per port per IPV4) can assume and vote/post content with?
If the network replicates the content permanently and there is no flood protection in place it may be a significant attack vector.

So may be it would be a reasonable approach to ad a message TTL and prepare for the crypto upgrade?

[NielsZeilemaker]

It does indeed, messages don't have an expiration date. We've played around with a cleanup window, which will throw out messages based on a global time. But this policy hasn't been tested in the wild.
For now its up to the community to design such behaviour, and we havn't used it yet.

Yes, that means storing the identity messages as well.

Currently there are no protections in place guarding against the whitewashing attack you're describing. But unfortunately, just filtering by IP won't fix it.

Moreover, I must stress that we don't implement flooding in Dispersy, and hence don't need a TTL. While defining your messages you can choose between having them stored at each peer, or not. If you let peers store messages, then they get synchronized over time (again not using flooding, but messages are pulled by peers). If you're telling them not to store messages, they have a single destination, and won't be forwarded by default. A community can implement forwarding itself if required, as I implemented in 4P.

[DavidXanatos]

If the messages are pulled by nodes, this still can result in them remaining in circulation for ever.
And those still some type of expiration mechanism would be good to have in my opinion.

And once there is such in place, you can more freely update the protocol implementation.

[NielsZeilemaker]

Pruning is implemented, and you're free to use it in a community. However, its not used in Tribler as of now. Those communities were build using an older version of Dispersy which did not have any pruning at that time.
Have a look at the pruning unit-test to have an example of how it works.
https://github.com/Tribler/dispersy/blob/devel/tests/test_pruning.py

[NielsZeilemaker]

Regarding your "remain in circulation for ever" comment. That's more or less the point of Dispersy, eventual consistency in a p2p network. Moreover, Dispersy will make sure that not one peer will receive the same message twice.

[DavidXanatos]

Ok, but if its available shouldn't it be used in tribler rather sooner than later?
Also is there a concept in place for any updating the protocol that would keep the network consistent?

[NielsZeilemaker]

It depends, it would make sense to add it to the AllChannelCommunity, but that one is relatively small currently. It contains 200k votes, which is roughly 50mb.
In the ChannelCommunities it doesn't make sense, as these torrents should be kept. Search doesn't store any messages, or at least it doesn't use the synchronization. And that's it, no other communities store messages.

[DavidXanatos]

hmm... I would say its a good idea to be able to change in future the protocol in some way so therefor something should be done to make this possible rather sooner than later in case it would require some break in compatibility.

[NielsZeilemaker]

There is no protocol in dispersy, basically it is a platform on top of you can implement communities. Communities define a protocol. Dispersy only implements features which can be used/reused by the protocols of the communities.

[DavidXanatos]

Well the signing and verifying part is done in the code inside the dispersy dir, and this part of the code also defines the binary packet format, does it not?
So to my humble understanding the dispersy code defines the binary protocol format.

[NielsZeilemaker]

Signing and verifying are actually policies you can turn off.
The protocol is defined by a community in the initiate_meta_messages method, an example:
https://github.com/Tribler/dispersy/blob/devel/discovery/community.py#L236

Here the discovery community defines 4 messages. The similarity-request message, which requires a signature and hence is using the MemberAuthentication. The ping and pong messages however, dont require a signature and hence are using the NoAuthentication policy.

So yes, the code to verify and sign a message is inside the dispersy dir. But no, it does not define the protocol.
Moreover, we can't simply assume in Dispersy that all communities will need pruning. This depends on the use case of the community, and hence has to be decided while implementing the community in the initialize meta message method.

[DavidXanatos]

Well, not to split hairs but in initiate_meta_messages you can only enable/disable signing you can not change its format unless of cause you disable it and than implement an own replacement, but thats not so elegant if we are looking for a way of making the protocol more compatible to standard crypto implementations.

Well i would say you need pruning + refresh, this way you can get rid of old outdated messages but at the same time keep all that is relevant indefinitely, well as long as it gets refreshed regularly.

Honestly I don't see a use case that would benefit from indexing a decade old content, so I would argue that any community would benefit from a pruning + refresh mechanism.

Or did i missed something here?

[NielsZeilemaker]

As a community designer you can actually specifiy which crypto to use. And like I said a couple comments ago, I might deprecate the M2Crypto signatures as they are implemented now. Choosing the nacl dualkey as a default. You can even use more than one crypto-variant in a single community. As the type of public key determines how messages are signed.

The goal of Dispersy was not to create a protocol, but rather to be a platform which allows you to create a protocol. Hence, you're able to define your messages in the initiate_meta_messages method. But in addition to those messages, Dispersy provides you with a default protocol able to synchronize messages, discover new peers, etc.

Therefore, Dispersy cannot simply say that all protocols (communities) build on it must do pruning. It can only provide the tools to allow protocols to do pruning.

Sure, decades old content might not make sense in most communities. But the ChannelCommunity as implemented in Tribler seems like a nice example. Content in those Communities shouldn't be thrown away simply because its old. Have a read in my Open2Edit paper, it suggests some use cases of Communities in which where pruning doesn't always make sense

We did however think about a type of pruning in which peers, after discovering that messages they created were pruned, would re-create a message (with the same content) and publish it again. This would for instance remove votes from users of Tribler which aren't around anymore.

Such a pruning system/technique might make sense to enable by default, but still allowing community designers to turn it off.