[netfinity]

It is known that from time to time the preferencedKad.dat file becomes corrupted, causing odd Kad IDs often with alot of zeros in it. One way to deal with this would be to create all Kad IDs with the high 32 bits of the Kad ID to be the hash of the lower 96 bits.

R = Random digits (or a 96 bit assymetric crypto key if one would want to implement a more advanced obfuscation implementation)
K = Kad ID
M = Mask for the lower 96 bits
H(x) = Is the md4 hashing function

A Kad ID is generated as follows
K = (H(R & M) & ~M) | (R & M)

A Kad ID is valid if the below equation is satisfied
K = (H(K & M) & ~M) | (K & M)

If this is implemented from a certain Kad version it would also be possible to detect corruption of Kad IDs in the network.

Regards
netfinity

[Some Support]

Mhh, I don't think that corrupted kad problems a such a big issue, as it seems also somewhat unlikely that only certain parts of 16 bytes file which is written in one flush get corrupted.
However your suggestion got me another idea, how your method can be of real help for the network: It may harden Kad _a lot_ against eclipsing attacks against the network. Short explanation: The point of an eclipsing attack is to introduce fake nodes which are closer to a keyword X than any other nodes. This requires that you can freely choose your KAD ID in order to adjust it in a way that its close or even fits the hash for a Keyword K. Now if we make the least significant 64 bit of a KadID random and then generate the most significant 64 bit out of a Hash from those 64 bit, you can no longer choose your KadID in such a way. The task to create a valid KadID for a given Keyword would be a brute force attack with 2^64 possibilites, which is strong enough to not make it trivial. Of course an attacker can still steal other KadID which are already close (and valid), however this will still make it impossible to create closer nodes making the attack a lot less effectiv. Plus eMule could figure out that something is wrong if it knows multiple clients with the same kad id, which is impossible currently.
Of course that would make debugging a lot harder for us, but this might be a reasonable price.

I have to rethink this whole issue, untill now its jsut a quick idea, but on the first look it really looks promising. Its not even adding one byte overhead

[cafebean]

Quote

create all Kad IDs with the high 32 bits of the Kad ID to be the hash of the lower 96 bits

won't this make the first 32 bits overhead? I think it is better if corruption detection is local only, say double back up the Kad ID to check against.

Quote

The task to create a valid KadID for a given Keyword would be a brute force attack with 2^64 possibilites

Not realy, an attacker only need to be closer than every good node, so brute force with as many tries as live kad nods will likely turn out one usable ID. Any way, why not make the entire 128 bits random, but use it's entire harsh to xor the distance.

Quote

Of course an attacker can still steal other KadID

Can't we secure it similar to the user hash used for secure identification?

Also there is a good side to making any kad ID easily. A power user could use it to passively observe a file or keyword on kad by having a close matching id. Or a lot of good clients can counter an eclipse by throwing good nodes at it.

[DavidXanatos]

Using the hash of the ID instead of the ID would breack backwards compatybility,
while making the ID safe allows a smooth move from the unsafe to the safe one, first allowing the unsafe one but letting new cleints us safe one, later one some versions later the few remaining unsafe ID's would be locked out.

[Some Support]

Quote

Not realy, an attacker only need to be closer than every good node, so brute force with as many tries as live kad nods will likely turn out one usable ID. Any way, why not make the entire 128 bits random, but use it's entire harsh to xor the distance.

True, you through have to consider that you need several of such IDs.. but this is a valid point, i have not considered. A brute force attack with 50 mio runs might be enough to create some of those, which is about 2^31 and therefore not really secure... not sure if its still worth it.

Quote

Any way, why not make the entire 128 bits random, but use it's entire harsh to xor the distance.

Its the same as proposed, just with the difference of having 128 pure random bytes, while my suggestion would reduce the true unique IDs to 2^64 (which is still enough). The difference is that this would add more overhead and more important would need a complete new implementation.

Quote

Can't we secure it similar to the user hash used for secure identification?

Not really. I mean it would work in theory, but the overhead is _way_ to big in this case compared to its advantages.

Quote

Also there is a good side to making any kad ID easily. A power user could use it to passively observe a file or keyword on kad by having a close matching id. Or a lot of good clients can counter an eclipse by throwing good nodes at it.

No, we don't really want clients messing with the routing in any way, that will sooner or later always cause problems.

[Semm]

Great thing you are discussing KAD-IDs!
Hardening KAD against Fake-IDs has been bugging me for some time, so instead of an own thread I think I will join in here:

As already mentioned KAD is at the moment very vulnerable to sibling attacks, since you can easily promote yourself to become the networks caretaker for certain files or keywords simply by setting up a few clients with KAD-IDs very close to the target hash.
Obvious faked or corrupted IDs have already been spotted in the KAD network, the most prominent of them might be “ID-Zero”, although I don’t know if the origin of those IDs is just an eMule-bug, some sort of secret lecher-mod handshake (like “[CHN][VeryCD]“), a buggy eMule-mod or even something more sinister.

So, what kind of dangers arises from fake-IDs?

1. Monitoring the network:

With the big servers gone, more and more people start to run eMule by only using KAD (btw. any ideas for a KAD-only client? ). Still companies like Mediadefender want to monitor file spread and keyword search. The German equivalent of Mediadefender for example is authorised by the German RIAA and the affected labels to monitor around 2000 explicitly chosen MP3 files for further lawsuits. A perfect job for fake IDs!

2. Abusing the network:

This year there were some reports of people trying to abuse DHT-networks like KAD as botnets, to create or backup DDoS-attacks by “conquering” very popular hashes (like the search-hash of keywords like “the” or “movie”) and redirect all requests to the DDoS target server!

3. Spreading fakes:

Well, servers redirecting people to fake files or spreading faked search-results have always been a problem for eMule. This scheme can be continued by faking KAD-IDs.

4. And most important: “Delete” files from the network by denying their very existence!

Just an example: You want to stop the distribution of Firefox1.5.12? Simply set up a few nodes with IDs near fb94bf73e2e0fd2efc26dc23b2786272 and answer all requests with “Firefox1.5.12? We’re very sorry but there a no sources for this file available in the entire network.” – No more Firefox in eMule!


So, the one basic solution would be to derive the client’s ID directly from its IP-address by hashing, as it was proposed for CHORD. Although I would suggest generating only the first 24 bits by hashing the IP-address and choose the remaining 104 bits otherwise, so you don’t end up with collisions in case of multiple clients behind a NAT and you have still at least some room for load-balancing client-ID variations. This way no attacker had a chance to get even close to a desired file hash on purpose!

Why only the first 24 bit? Well, as already mentioned to become a hash’s caretaker it isn’t utterly necessary to choose an ID representing the exact 128 bit hash, it’s enough to make sure nobody else has a ID closer to the target-hash than your own ID. So only an ID’s first 20 to 25 bits are of real interest, the rest mostly just eliminates the theoretical possibility of collisions.

The only disadvantage would be that clients with dynamic-IP couldn’t keep their ID forever, but this could also have a positive effect in terms of load-balancing since for example otherwise a very popular keyword like “movie” could be stuck with a 56k dial-up user forever!

Generating the first half of an ID by hashing the randomly chosen second half as Some Support suggested sounds good, since you don’t have to consider the dynamic-IP issue, but since for KAD only the first 20 to 25 bit are significant, I fear brute-forcing is way too easy. For example, to get a perfect match at the first 22 bits you have to randomly generate more or less an average of 4 million hashes.
Just some numbers: The COPACOBANA machine, build by the university of Kiel here in Germany for around 10.000$ is able to perform 48 billion (!!) DES decryptions per second, my 2 year old single-core Athlon64 is able to generate 4 million SHA1 hashes in 4,5 seconds.

As DavidXanatos mentioned securing the KAD IDs will break backwards- compatibility, like the introduction of Secure-IDs did. (Therefore secure KAD-IDs should be introduced quickly so it won’t take ages till you can make their usage mandatory.)
But since at the moment, with of the loss of the big servers, fake IDs are the premier choice for attacking, monitoring and abusing the eMule network and steps have to be taken to harden KAD against those attacks!

[Some Support]

Quote

So, the one basic solution would be to derive the client’s ID directly from its IP-address by hashing, as it was proposed for CHORD. Although I would suggest generating only the first 24 bits by hashing the IP-address and choose the remaining 104 bits otherwise, so you don’t end up with collisions in case of multiple clients behind a NAT and you have still at least some room for load-balancing client-ID variations.

I already thought about this, actually even before the (gone wrong ) hashing idea, but i do not think its a viable solution. First, IP-Changes are too frequent in general and sometimes happen even during the runtime of eMule. The overhead caused by frequent Kad ID changes and the vastly increasing amount of out-dated indexed informations might be even worse than some eclipsing attacks. Additionally when starting up, a client in general doesn't knows its own IP (well this is a implementation problem which could be fixed, but nevertheless).

Second: IPs aren't equally common, the adress space is not used completely (or even close) and they add a geographic factor. This mean a 32bit IP address (and its resulting hash) has a randomness of maybe 20-24(?) bits. I fear that with the general randomness flawed with those factors might have some bad consequences to the spreading of KAD IDs. Also there are certain providers which put several hundred users behind one IP.

Third: A attacker with even medium amount of ressources to spend can probably choose at least 10 bits of his IP adress freely (buy renting a small subnet, costs only a few bucks), further reducing the effect.

IMHO all those points are too much of a disadvantage compared to the possible protection plus to implement it at this point. (And before someone comes with the next idea A centralized server to give out signed IDs is out of question).

[Semm]

Some Support, on Oct 21 2007, 04:49 PM, said:

The overhead caused by frequent Kad ID changes and the vastly increasing amount of out-dated indexed informations might be even worse than some eclipsing attacks.

Well on the other hand deleting entire files from the network might be even worse than additional KAD-overhead (In my case KAD-overhead is just something about of 1 MByte per hour, no problem if this numer would increase.).

Some Support, on Oct 21 2007, 04:49 PM, said:

Second: IPs aren't equally common, the adress space is not used completely (or even close) and they add a geographic factor. This mean a 32bit IP address (and its resulting hash) has a randomness of maybe 20-24(?) bits. I fear that with the general randomness flawed with those factors might have some bad consequences to the spreading of KAD IDs.

Every good hash function spreads even with similar input, that's one of the basic requirements of a good hashfunction.
Sure, the resulting hashes would be bound to their IP address, so today I am responsible for the hash resulting out of 184.12.13.85 and tomorrow maybe my neighbour will be in charge, but the hashes itself will still spread equally over the 24 bit space.

Some Support, on Oct 21 2007, 04:49 PM, said:

Third: A attacker with even medium amount of ressources to spend can probably choose at least 10 bits of his IP adress freely (buy renting a small subnet, costs only a few bucks), further reducing the effect.

Well as far as I know renting an enitre IP-Space isn't that cheap and you still have the hashing issue - you may choose any of your 65025 IPs freely, but you can't define their hash, with 4 million KAD-users there is a good chance somebody else has a closer IP-hash!

This post has been edited by Semm: 21 October 2007 - 05:20 PM

[Some Support]

Quote

Well on the other hand deleting entire files from the network might be even worse than additional KAD-overhead (In my case KAD-overhead is just something about of 1 MByte per hour, no problem if this numer would increase.).

You personal overhead really isn't quite valid on a network wide view and its quite related to which keyword you index. Also smaller lines can't take as much overhead as bigger ones, while the kad overhead is the same on all lines (statistically). And files are not deleted on a eclipsing attack, but jsut hard up to impossible to find as long as the attack runs.

Quote

Every good hash function spreads even with similar input, that's one of the basic requirements of a good hashfunction.

This doesnt changes the fact that the randomness is decreased if your input is less random, simply because a hash for input X is always the same.

Quote

Well as far as I know renting an enitre IP-Space isn't that cheap and you still have the hashing issue - you may choose any of your 65025 IPs freely

No but the chance that you find a better ID is not bad, since 10 bits out of 20-24 effectivly used (in the IP space) is a good shot. Anyway, i'm not deying that it would make it hard for an attacker, i just do think that given the disadvantages, the advantages are not enough to implement it.

[netfinity]

Some Support said:

Mhh, I don't think that corrupted kad problems a such a big issue, as it seems also somewhat unlikely that only certain parts of 16 bytes file which is written in one flush get corrupted.

Well the only time it happened me all the 16 bytes was zero'ed. However I do have gotten known.met and some other data getting randomly corrupted due to a buffer overrun in the id3lib, so it is possible.


One way to make it quite hard to choose a KadID and almost impossible to steal one would be to let the random part to be the public key of for example an elliptic curve crypto algorithm. Don't know how much CPU power it would require thought, but Kad doesn't handle that much of data so it might be feasable to use an assymetric encryption on all request packets which would ensure that only the node holding the private key could ever interpret and respond the request. Note that the keys doesn't need to be uncrackable, just hard enought to not make it worth the effort!

[Some Support]

netfinity, on Oct 21 2007, 07:02 PM, said:

One way to make it quite hard to choose a KadID and almost impossible to steal one would be to let the random part to be the public key of for example an elliptic curve crypto algorithm. Don't know how much CPU power it would require thought, but Kad doesn't handle that much of data so it might be feasable to use an assymetric encryption on all request packets which would ensure that only the node holding the private key could ever interpret and respond the request. Note that the keys doesn't need to be uncrackable, just hard enought to not make it worth the effort!

128 bit is not enough for a public key, its a second task to break it. Also on a first look i dont see how this would prevent anyone from choosing a ID close to his target, it only avoids stealing it (the same stuff which is used for SecureID already).
Anyway i though into a similar direction too a bit, like having a Kad ID creating algorithm which take a long time to create a new ID but a short time to verify it, together with the partial hashing thing. The goal would be to make brute force even a "small" number of several millions too CPU intensive. I'm not sure if its possible actually (would ahve to think about it, if you can realize this properly with prime factorization for example), but this would cause quite some scalability issues, even if it would work: On a Athlon64 5000 it might take a second to create a kad ID and on a Pentium 100Mhz 5 hours. While something which takes 1 second on a Pentium100 would take only some nanoseconds on a real big PC... so thats not going to work this way neither. I dont think there is really a decentralized and valid way to aovid clients beeing able to choose their ID.

[netfinity]

Wikipedia on Elliptic curve cryptography said:

The hardest ECC scheme (publicly) broken to date had a 109-bit key (that is about 55 bits of security). For the prime field case, it was broken near the beginning of 2003 using over 10,000 Pentium class PCs running continuously for over 540 days (see [2]). For the binary field case, it was broken in April 2004 using 2600 computers for 17 months (see [3]).

This should be more than enought, but the question is how much CPU it would take to encrypt/decrypt on a slow pentium. However it would be enought to encrypt just 4 bytes or so as those bytes could carry a symetric key part.

Yes the problem is as always the scaleability, but it increases the complexity of an attack and may slow it down to a point where it isn't really useful (for the attacker) anymore. This method by itself would probably not be enought by itself but add to the overall security. Question is just could a 100MHz Pentium do this in realtime? If so then this should be very cheap to implement!

[Semm]

Some Support, on Oct 21 2007, 05:54 PM, said:

This doesnt changes the fact that the randomness is decreased if your input is less random, simply because a hash for input X is always the same.

Sorry, but where is here a real problem for KAD? As long as everyone who is online has a different ID and they are all spread over the available ID-Space, so you have the load-balance effect, KAD is okay!

netfinity, on Oct 21 2007, 09:16 PM, said:

Wikipedia on Elliptic curve cryptography said:

The hardest ECC scheme (publicly) broken to date had a 109-bit key (that is about 55 bits of security). For the prime field case, it was broken near the beginning of 2003 using over 10,000 Pentium class PCs running continuously for over 540 days (see [2]). For the binary field case, it was broken in April 2004 using 2600 computers for 17 months (see [3]).

This should be more than enought, but the question is how much CPU it would take to encrypt/decrypt on a slow pentium. However it would be enought to encrypt just 4 bytes or so as those bytes could carry a symetric key part.

The issue isn't to avoid someone breaking a cryptographic key, it is to avoid someone generates a lot of random keys in a reasonable time to chose the best output as KAD-ID for a sibling attack. So the key generation-method has to be time consuming, but should not be very CPU/machine dependant!

This post has been edited by Semm: 21 October 2007 - 10:19 PM

[Some Support]

netfinity, on Oct 21 2007, 09:16 PM, said:

This should be more than enought, but the question is how much CPU it would take to encrypt/decrypt on a slow pentium. However it would be enought to encrypt just 4 bytes or so as those bytes could carry a symetric key part.

Yes the problem is as always the scaleability, but it increases the complexity of an attack and may slow it down to a point where it isn't really useful (for the attacker) anymore. This method by itself would probably not be enought by itself but add to the overall security. Question is just could a 100MHz Pentium do this in realtime? If so then this should be very cheap to implement!

Indeed, i didnt knew too much about ecc yet, seems to be not too common. Anyway my main questions stays: What is the point of your approach? It would make it impossible to steal anotherones ID. Ok fair enough. But useless since you can create a better ID yourself to attack the network anyway. The first aim has to be to avoid that User X can create an ID close to keyword Z. Only if this is done in a reliable way, this can be further improved by putting in stuff to avoid that other valid IDs get stolen and used for such an attack. But that is really the least problem.
I don't know if i misunderstood you, if so please explain.

[Zar0n]

Some Support, on Oct 21 2007, 05:49 PM, said:

I already thought about this, actually even before the (gone wrong ) hashing idea, but i do not think its a viable solution. First, IP-Changes are too frequent in general and sometimes happen even during the runtime of eMule. The overhead caused by frequent Kad ID changes and the vastly increasing amount of out-dated indexed informations might be even worse than some eclipsing attacks. Additionally when starting up, a client in general doesn't knows its own IP (well this is a implementation problem which could be fixed, but nevertheless).

Well ISP's and geographic locations have fixed ranges and when you lose connection and reconnect you will stay inside that range so if u only use the fixed part there is no problem.

The hashing should be based on that range and then there is no problem if u lose connection and change IP.

So this way they could not attack globally unless they put a bot in each ISP.

Just and idea

This post has been edited by Zar0n: 22 October 2007 - 02:06 AM

[leuk_he]

netfinity, on Oct 21 2007, 11:16 PM, said:

Question is just could a 100MHz Pentium do this in realtime? If so then this should be very cheap to implement!

Question: Does one really want to support Pentium 100, and if you do, and have enough memory , and does every cleint have to verify all kadid received against some key, or could that be made optional?

[fabtar]

I'm not very expert in these issues but I think that there is a way to stop evil guys from gaining the desired KadID.
KadID may be forced by doing an hash from the client's IP and other datas (month, year ... :-) ).
In this way KadID cannot be random but pseudo-random (thanks to hash algorithms).KadID is bounded to client-IP and other time datas(allowing slow rotations), Invalid kadIDs could be detected immediately.
This idea could be applied also only to a portion of KadID, the other piece could be randomly chosen.
I hope my thoughts are pertinent.

[leuk_he]

fabtar, on Oct 22 2007, 02:19 PM, said:

KadID may be forced by doing an hash from the client's IP and other datas (month, year ... :-) ).
This idea could be applied also only to a portion of KadID, the other piece could be randomly chosen.

This was more or less already answered:

Some Support, on Oct 21 2007, 06:49 PM, said:

I already thought about this, actually even before the (gone wrong smile.gif ) hashing idea, but i do not think its a viable solution. First, IP-Changes are too frequent in general and sometimes happen even during the runtime of eMule. The overhead caused by frequent Kad ID changes and the vastly increasing amount of out-dated indexed informations might be even worse than some eclipsing attacks. Additionally when starting up, a client in general doesn't knows its own IP (well this is a implementation problem which could be fixed, but nevertheless).

Adding a data/time component woud lead to automatic reset & loss of data in the kad network every xx days (what ever time component you would choose). Not good. Anyway, haveing the (upper part of) the ip as a source for a relevant part of the kadid would be good for some percentage of fake kad id.

BTW, not knowing your ip is not really a problem, since kad now currently is bootstrapped (most of the time) from known clients, at which stage you would know your ip number.

edit: oops, quoting error.

This post has been edited by leuk_he: 22 October 2007 - 12:48 PM

[DavidXanatos]

@SS
I thing netfinity ment that you rundomly create the private key, and the outcomming public key ised ad KAD ID would be rundom, the point would be hat you can not create any ID you want, you have to create private keys make the public one and look if thay fit your needs. What would be a broute force atack and kopefully hard enough to prevent bad people from getting ID's thay want.

[netfinity]

DavidXanatos is right at the point that with asymetric keys only Kad IDs with a corresponding private key would be valid, so you can't choose ID's freely althought you can create alot of them til you get close enought to your target. Secondly it would prevent bad guys from stealing the Kad ID's from valid nodes in an attempt to conceal these nodes, which is probably worse than a big bunch of, not that hard to detect, nodes flocking around a specific keyword.

It wouldn't stop the attacks but would require the attacker to spend alot of CPU and memory resources which would make the attacks cost a little bit more. Other methods would be needed too like in my SafeKAD filter where only one contact per IP is allowed and contacts are not allowed to change their ID.

It's unfortunate that some ISPs like to rotate their IP addresses now and then to prevent their customers from hosting servers as it would otherwise be interesting to embedd a part of the IP inside the Kad ID to detect for example a shuffle attack where an evil node switch the identities of nodes it return in search results.