Kad : audit architecture, routage, bootstrap, publication et joignabilité

1. Périmètre

Composants audités :

kademlia/kademlia/Defines.h
Kademlia.cpp
Prefs.cpp
Search.cpp
SearchManager.cpp
Indexed.cpp
UDPFirewallTester.cpp
net/KademliaUDPListener.cpp
routing/Contact.cpp
RoutingBin.cpp
RoutingZone.cpp
utils/UInt128.cpp
DownloadQueue.cpp
BaseClient.cpp
Opcodes.h

2. Source algorithmique

Les sources eMule citent explicitement l’article Kademlia de 2002. La structure générale repose sur un ID 128 bits, une distance XOR, une table de routage, un lookup itératif et du stockage près de la clé.

Mais il faut distinguer :

papier Kademlia
et
protocole Kad d'eMule

Kad contient de nombreuses règles spécifiques à l’écosystème eMule.

3. Paramètres centraux observés

Dans Defines.h :

K = 10
ALPHA_QUERY = 3
SEARCH_JUMPSTART = 1 s

Les durées courantes sont de l’ordre de 45 s pour plusieurs recherches classiques et plus longues pour les opérations de stockage.

4. Le Kad ID local

Prefs.cpp initialise :

m_uClientID.SetValueRandom()

et le persiste dans :

preferencesKad.dat

Le fichier mémorise notamment l’IP, un ancien champ de port devenu inutilisé et le Kad ID 128 bits. Si l’ID lu vaut zéro, il est régénéré.

5. Génération du Kad ID

CUInt128::SetValueRandom() utilise actuellement :

CryptoPP::AutoSeededRandomPool

pour générer 16 octets aléatoires. C’est un point distinct des anciens usages de rand() encore présents ailleurs.

6. Distance

Le code calcule fréquemment :

distance = ContactID;
distance.Xor(target);

Les listes de candidats sont ordonnées par cette distance. La proximité XOR est donc réellement le critère de progression.

7. RoutingZone

RoutingZone.cpp décrit un arbre binaire. Une zone est soit une branche possédant deux sous-zones, soit une feuille possédant un RoutingBin.

Les IDs sont traités relativement au centre local, considéré comme 000...000.

8. nodes.dat normal

La racine charge :

config\nodes.dat

Le parser reconnaît l’ancien format et des versions modernes 1 à 3. Les formats modernes commencent par un count nul afin d’empêcher de très anciens clients d’interpréter incorrectement la suite.

9. Enregistrement d’un contact

Selon la version du fichier :

Kad ID        16 octets
IP             4
UDP port       2
TCP port       2
version        1
UDP key        selon format
verified       selon format

Le code contrôle aussi que la taille restante du fichier est compatible avec le nombre de contacts annoncé.

10. Admission depuis nodes.dat

Contrôles observés :

GoodIPPort
IPFilter
restriction du port 53 pour anciens nœuds non obfusqués
type/version
limites globales d'IP

Un vieux fichier sans contact marqué verified peut déclencher une compatibilité qui les marque temporairement vérifiés afin d’accélérer le bootstrap.

11. Bootstrap nodes.dat spécial

Version 3 + BootstrapEdition == 1.

Le commentaire du code prévoit typiquement beaucoup plus de contacts qu’un cache normal. Ils ne sont pas injectés directement dans la routing table mais utilisés comme candidats de bootstrap.

12. Sélection bootstrap

La branche choisit jusqu’à :

50 candidats

parmi les contacts valides, triés selon la proximité XOR avec notre propre ID.

13. Motivation réseau

Le commentaire source explique qu’un petit nodes.dat identique distribué à tous entraînerait une concentration de connexions vers les mêmes nœuds. La bootstrap edition réduit ce risque en répartissant les tentatives.

C’est un exemple important d’un réglage qui doit être raisonné au niveau du réseau entier, pas uniquement du client local.

14. Bootstrap réseau

Le client envoie :

KADEMLIA2_BOOTSTRAP_REQ

Une réponse peut transmettre l’identité du répondant et jusqu’à environ 20 contacts.

Ces contacts restent des candidats ; ils ne deviennent pas automatiquement des pairs de confiance.

15. Self lookup

Après démarrage, la branche planifie un premier lookup de son propre ID dans les premières minutes, puis le renouvelle environ toutes les 4 heures.

Ce mécanisme aide à rafraîchir la connaissance de la zone logique proche.

16. Consolidation

La routing table possède un cycle de consolidation d’environ :

45 min

pour regrouper des zones lorsque la structure peut être simplifiée.

17. Démarrage d’un lookup

CSearch::Go() demande une réserve d’environ :

50 contacts candidats

à la routing table, puis interroge les meilleurs selon ALPHA_QUERY.

Pour un lookup NODE simple, le démarrage est plus conservateur.

18. ALPHA_QUERY

Valeur actuelle :

3

Ce parallélisme constitue un compromis entre progression rapide et charge réseau.

Il ne doit pas être augmenté sans mesure globale.

19. JumpStart

Si aucune réponse n’est arrivée pendant environ trois secondes, le lookup peut tenter un autre candidat.

Si la liste est épuisée :

PrepareToStop()

20. Tolérance aux nœuds morts

Lorsque les meilleurs nœuds attendus sont injoignables, le code possède une logique qui peut redemander davantage de contacts proches à un nœud ayant répondu.

Il ne suppose donc pas que les premiers candidats sont vivants.

21. Limite du nombre de contacts reçus

Une réponse qui contient plus de contacts que demandé est rejetée comme violation de protocole potentiellement malveillante.

Ce contrôle est explicite dans ProcessResponse().

22. Unicité IP

Pendant une réponse de routage :

pas plusieurs Kad IDs pour la même IP

La branche impose aussi hors LAN une limite de deux contacts par /24 dans une même réponse.

23. Portée anti-Sybil

Ces limites empêchent des abus simples, mais ne constituent pas une défense complète contre un acteur disposant de nombreuses adresses/réseaux.

Ne pas les présenter comme une preuve d’identité.

24. Vérification IP

VerifyContact() associe :

Kad ID
+
IP observée

à un état verified.

Toute instrumentation future doit distinguer :

appris
contacté
répondant
verified

25. Nœuds UDP firewalled

Le listener évite d’intégrer les nœuds UDP firewalled à la routing table. Pour router efficacement, un nœud doit pouvoir répondre en UDP.

26. Firewall TCP

Le client recueille plusieurs observations avant de conclure sur son état. La constante :

KADEMLIAFIREWALLCHECKS = 4

montre que la décision n’est pas fondée sur un seul témoin.

27. Port UDP externe

La branche demande le port vu de l’extérieur à plusieurs IP. Jusqu’à trois témoins sont utilisés et une concordance de deux observations permet d’accepter la valeur.

Sinon, le port externe est considéré peu fiable.

28. Statistiques de firewall

Le code maintient des estimations de ratios TCP/UDP firewalled parmi des nœuds compatibles observés.

Ce ne sont pas des statistiques exhaustives du réseau.

29. Estimation des fichiers Kad

Prefs.cpp dit explicitement qu’il n’existe pas de moyen réel de connaître exactement le nombre de fichiers de Kad.

Le nombre affiché est une estimation dérivée notamment d’une moyenne eD2K ou de l’index local.

Règle documentaire

Ne jamais présenter cette valeur comme un comptage exact.

30. Republication

Constantes 0.72a :

KADEMLIAPUBLISHTIMES = 5 h
KADEMLIAPUBLISHTIMEN = 24 h
KADEMLIAPUBLISHTIMEK = 24 h

Respectivement :

sources
notes
keywords

31. Limites d’index

Valeurs observées :

KADEMLIAMAXINDEX = 50 000
KADEMLIAMAXENTRIES = 60 000
KADEMLIAMAXSOURCEPERFILE = 1 000
KADEMLIAMAXNOTESPERFILE = 150

Le détail de Indexed.cpp doit être étudié avant toute conclusion sur les seuils effectifs d’admission/remplacement.

32. Charge des nœuds

Le moteur de publication reçoit des informations de charge. Après certains stores, la branche peut retarder l’utilisation d’un nœud très chargé.

Il existe donc déjà un mécanisme local d’évitement des zones saturées.

33. Buddy

Premier cycle FindBuddy après quelques minutes, puis réessais espacés lorsqu’un Buddy est nécessaire.

Le Buddy est lié à l’état TCP firewalled et à la capacité de callback Kad.

34. Callback Kad

Flux conceptuel :

lookup du Buddy
→ demande au Buddy
→ Buddy relaie la demande
→ client firewalled initie TCP

À distinguer absolument du callback serveur et du direct UDP callback.

35. Direct UDP Callback

Capacité annoncée si :

Kad actif
TCP firewalled
UDP ouvert/vérifié

Cela permet à certains clients d’éviter le Buddy pour la sollicitation de callback.

36. Types de sources Kad

DownloadQueue::KademliaSearchFile() distingue différents types : source joignable, source firewalled avec Buddy, direct callback, etc.

Ils ne sont pas tous instanciés de la même façon.

37. Trust boundary Kad

Observé

réponse UDP
latence
connexion TCP
callback réussi
payload

Déclaré

Kad ID
contacts
source metadata
flags firewall
port rapporté

Recoupé

port externe
firewall checks
IP verification

45. Hypothèse : valeur de verified

Mesurer si un contact verified présente réellement :

plus de réponses
moins de churn
meilleure stabilité

qu’un non-verified.

Ne pas le supposer.

46. Hypothèse : impact CGNAT/VPS sur les limites /24

Les règles IPv4 historiques peuvent se comporter différemment dans un Internet où CGNAT et hébergement massif sont courants.

Mesurer avant toute modification.

47. IPv6

La branche auditée reste fortement fondée sur IPv4. Ajouter IPv6 ne serait pas un changement local de type :

uint32 → IPv6

Cela toucherait le wire protocol, les structures de contacts, les callbacks, les filtres et l’interop.

À isoler dans une étude future.

48. Fuzzing nodes.dat

Fixtures :

count énorme
version inconnue
troncature
IP/port invalides
clé UDP tronquée
verified incohérent
bootstrap edition malformée

Objectif : rejet propre, sans crash ni allocation aberrante.

49. Fuzzing Kad UDP

Cibles :

BOOTSTRAP_RES
HELLO_REQ/RES
ROUTING_RES
SEARCH_RES
PUBLISH_REQ/RES
FIREWALL
CALLBACK

Tester notamment count, longueur, doublons et versions.

50. Rejeu déterministe

Construire un petit harness offline qui injecte des paquets enregistrés/synthétiques dans le parser, avec assertions sur l’état final.

C’est plus sûr que de tester des entrées malformées sur le réseau public.

51. Prudence sur les timers

Un timer local peut changer la charge imposée à tout Kad.

Aucune réduction de cadence ne doit partir d’une impression de lenteur.

52. Pas de « Kad Turbo »

Augmenter naïvement :

ALPHA
fréquence des lookups
republication
nombre de réponses

peut augmenter l’overhead sans produire plus de sources utiles.

53. Première amélioration raisonnable : observabilité

Avant toute modification wire :

compteurs
traces
histogrammes
motifs de rejet
latences
canal de découverte

54. Diagnostic bootstrap

Après instrumentation, un diagnostic pourrait distinguer :

aucun contact
contacts morts
UDP bloqué
port externe instable
Kad connecté mais TCP firewalled

Pour l’instant : mesurer seulement.

55. Ce que le code seul ne dit pas

Il ne permet pas de connaître en 2026 :

nombre réel de nœuds actifs
churn
ratio firewalled réel
part des sources utiles venant de Kad
durée de vie pratique d'un nodes.dat

Ces réponses exigent des mesures actuelles.

56. Conclusion

Le moteur Kad est déjà riche en défenses et en régulation :

limites de réponse
contrôles IP/sous-réseaux
verified state
filtrage UDP firewalled
JumpStart
load handling
publication bornée

La priorité de notre étude est :

comprendre
mesurer
rejouer
fuzzer

avant de changer quoi que ce soit.

Le Dossier 12 étudie ensuite le moment où deux clients découverts se rencontrent réellement : Hello, HelloAnswer et négociation des capacités.

================================================================================================