In this little description we use the following notation:
+ concatenation
hash(x) the SHA-1 hash of x
sign(x, sk) the Ed25519 signature generated by signing x using signing key sk
verify(signature, x, vk) verifying the Ed25519 signature of x using veryfing key vk
There is a central identity server everyone trusts. The server has an Ed25519 keypair, the master keypair. Everyone possesses the master verification key (MVK), the signing key is kept secret (MSK).
Furthermore, the identity server has access to a database of pairs (username, hash(password)) for authentication use. Such accounts may have been created by users through for example a web interface - it's important that the registration process contains some sort of user interaction like a CAPTCHA.
When a client wants to participate in the kademlia network it needs a certificate. It first generates a signing/verifying keypair (respectively SK and VK). It then presents the following information to the identity server:
username, VK, timestamp in seconds, hash(username + VK + timestamp + password)
The timestamp is added to protect against replay attacks. The certificate server should deny the request if the timestamp is outdated. It's impossible for a MITM to alter this message without invalidating the hash, because password is secret. Incorporating the password in the hash allows the server to check the password by computing the same hash and comparing it to the given value. If the hashes don't match the request gets denied. Otherwise the following information is returned:
node_id, certificate_expiry, certificate, current_time, bootstrap_creation_time, bootstrap_list, sign(bootstrap_list + bootstrap_creation_time, MSK)
Where certificate consists of:
sign(node_id + certificate_expiry + VK + current_time, MSK)
Because the VK got randomly generated by the user there is zero chance someone else has submitted the same VK to the server (in which case the SK would be compromised anyway). Using this information and the signed certificate the VK acts like a nonce and no replay attacks can be made against this reply. MITM attacks are impossible because they can't sign using MSK (it's secret).
node_id is the node id to be used by Kademlia that is randomly generated by the certificate server. certificate_expiry is 4 byte unsigned integer containing timestamp of the moment this certificate expires in the amount of seconds since the Unix epoch (01/01/1970). A reasonable expiry is a week, balancing between reducing performance stress and allowing for quick certificate revocations. If needed the generated certificate can be cached until a day before the expiry time as to prevent useless duplicate certificates.
The bootstrap_list sent is a randomly selected list of (node_id, IP address, UDP port) pairs the authority deems active to use as bootstrapping information. The bootstrap_list is
The current_time sent is the current time on the server to synchronize the time with the node (synchronized clocks is needed for a node to function).
Anyone receiving this certificate can check the following (because anyone can verify this certificate using MVK):
1. The certificate is not expired.
2. node_id was randomly generated by the certificate authority.
3. VK was linked to node_id by the certificate authority.
So long for the initation process (consisting of two UDP packets total).
Every Kademlia packet should have the following structure:
signature, node_id, VK, timestamp, certificate_expiry, certificate, content
| |
+------------------------ message -----------------------------+
Where signature is:
sign(message + target_node_id, SK)
First of all, because node_id, VK, certificate_expiry and certificate are sent the claims 1, 2 and 3 before can be checked by the receiver. signature can be checked for validity as well, because the VK is sent and verified and target_node_id is always known to the receiver (being it's own node_id).
timestamp is an 8 byte unsigned timestamp giving the amount of milliseconds since the Unix epoch when this message got sent. Because nodes have synchronized time this can be checked for validity (accomodating for latency a treshold for ~10 seconds is reasonable and safe). If you cache all the pairs of (signature, timestamp) received in the last 10 seconds you can also filter out duplicate packets, fully ruling out replay attacks. The risk of sending the same timestamp to the same target node twice is minimal, and can even be fully mitigated if done smart - if no more than 1000 messages per second get send from one node to another. In the use case of Kademlia this never happens.
Because a valid signature requires the secret SK to make and contains both the message and the receivers node_id MITM attacks are ruled out, as well as attempts for replay attacks on other nodes (which did not have the duplicate filter).
Now the per-packet overhead of this system is reasonable.
signature: 64 bytes
node_id: 20 bytes
VK: 32 bytes
timestamp: 8 bytes
certificate_expiry: 4 bytes
certificate: 64 bytes
============================ +
192 bytes