1 /*
2
3 Copyright (c) 2006-2018, Arvid Norberg
4 All rights reserved.
5
6 Redistribution and use in source and binary forms, with or without
7 modification, are permitted provided that the following conditions
8 are met:
9
10 * Redistributions of source code must retain the above copyright
11 notice, this list of conditions and the following disclaimer.
12 * Redistributions in binary form must reproduce the above copyright
13 notice, this list of conditions and the following disclaimer in
14 the documentation and/or other materials provided with the distribution.
15 * Neither the name of the author nor the names of its
16 contributors may be used to endorse or promote products derived
17 from this software without specific prior written permission.
18
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
23 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 POSSIBILITY OF SUCH DAMAGE.
30
31 */
32
33 #include <algorithm>
34
35 #include "libtorrent/kademlia/node_id.hpp"
36 #include "libtorrent/kademlia/node_entry.hpp"
37 #include "libtorrent/assert.hpp"
38 #include "libtorrent/broadcast_socket.hpp" // for is_local et.al
39 #include "libtorrent/random.hpp" // for random
40 #include "libtorrent/hasher.hpp" // for hasher
41 #include "libtorrent/crc32c.hpp" // for crc32c
42
43 namespace libtorrent { namespace dht {
44
45 // returns the distance between the two nodes
46 // using the kademlia XOR-metric
distance(node_id const & n1,node_id const & n2)47 node_id distance(node_id const& n1, node_id const& n2)
48 {
49 return n1 ^ n2;
50 }
51
52 // returns true if: distance(n1, ref) < distance(n2, ref)
compare_ref(node_id const & n1,node_id const & n2,node_id const & ref)53 bool compare_ref(node_id const& n1, node_id const& n2, node_id const& ref)
54 {
55 node_id const lhs = n1 ^ ref;
56 node_id const rhs = n2 ^ ref;
57 return lhs < rhs;
58 }
59
60 // returns n in: 2^n <= distance(n1, n2) < 2^(n+1)
61 // useful for finding out which bucket a node belongs to
distance_exp(node_id const & n1,node_id const & n2)62 int distance_exp(node_id const& n1, node_id const& n2)
63 {
64 // TODO: it's a little bit weird to return 159 - leading zeroes. It should
65 // probably be 160 - leading zeroes, but all other code in here is tuned to
66 // this expectation now, and it doesn't really matter (other than complexity)
67 return std::max(159 - distance(n1, n2).count_leading_zeroes(), 0);
68 }
69
min_distance_exp(node_id const & n1,std::vector<node_id> const & ids)70 int min_distance_exp(node_id const& n1, std::vector<node_id> const& ids)
71 {
72 TORRENT_ASSERT(ids.size() > 0);
73
74 int min = 160; // see distance_exp for the why of this constant
75 for (auto const& node_id : ids)
76 {
77 min = std::min(min, distance_exp(n1, node_id));
78 }
79
80 return min;
81 }
82
generate_id_impl(address const & ip_,std::uint32_t r)83 node_id generate_id_impl(address const& ip_, std::uint32_t r)
84 {
85 std::uint8_t* ip = nullptr;
86
87 static std::uint8_t const v4mask[] = { 0x03, 0x0f, 0x3f, 0xff };
88 static std::uint8_t const v6mask[] = { 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff };
89 std::uint8_t const* mask = nullptr;
90 int num_octets = 0;
91
92 address_v4::bytes_type b4{};
93 address_v6::bytes_type b6{};
94 if (ip_.is_v6())
95 {
96 b6 = ip_.to_v6().to_bytes();
97 ip = b6.data();
98 num_octets = 8;
99 mask = v6mask;
100 }
101 else
102 {
103 b4 = ip_.to_v4().to_bytes();
104 ip = b4.data();
105 num_octets = 4;
106 mask = v4mask;
107 }
108
109 for (int i = 0; i < num_octets; ++i)
110 ip[i] &= mask[i];
111
112 ip[0] |= (r & 0x7) << 5;
113
114 // this is the crc32c (Castagnoli) polynomial
115 std::uint32_t c;
116 if (num_octets == 4)
117 {
118 c = crc32c_32(*reinterpret_cast<std::uint32_t*>(ip));
119 }
120 else
121 {
122 TORRENT_ASSERT(num_octets == 8);
123 c = crc32c(reinterpret_cast<std::uint64_t*>(ip), 1);
124 }
125 node_id id;
126
127 id[0] = (c >> 24) & 0xff;
128 id[1] = (c >> 16) & 0xff;
129 id[2] = (((c >> 8) & 0xf8) | random(0x7)) & 0xff;
130
131 for (int i = 3; i < 19; ++i) id[i] = random(0xff) & 0xff;
132 id[19] = r & 0xff;
133
134 return id;
135 }
136
137 static std::uint32_t secret = 0;
138
make_id_secret(node_id & in)139 void make_id_secret(node_id& in)
140 {
141 if (secret == 0) secret = random(0xfffffffe) + 1;
142
143 std::uint32_t const rand = random(0xffffffff);
144
145 // generate the last 4 bytes as a "signature" of the previous 4 bytes. This
146 // lets us verify whether a hash came from this function or not in the future.
147 hasher h(reinterpret_cast<char const*>(&secret), 4);
148 h.update(reinterpret_cast<char const*>(&rand), 4);
149 sha1_hash const secret_hash = h.final();
150 std::memcpy(&in[20 - 4], &secret_hash[0], 4);
151 std::memcpy(&in[20 - 8], &rand, 4);
152 }
153
generate_random_id()154 node_id generate_random_id()
155 {
156 char r[20];
157 aux::random_bytes(r);
158 return hasher(r, 20).final();
159 }
160
generate_secret_id()161 node_id generate_secret_id()
162 {
163 node_id ret = generate_random_id();
164 make_id_secret(ret);
165 return ret;
166 }
167
verify_secret_id(node_id const & nid)168 bool verify_secret_id(node_id const& nid)
169 {
170 if (secret == 0) return false;
171
172 hasher h(reinterpret_cast<char*>(&secret), 4);
173 h.update(reinterpret_cast<char const*>(&nid[20 - 8]), 4);
174 sha1_hash secret_hash = h.final();
175 return std::memcmp(&nid[20 - 4], &secret_hash[0], 4) == 0;
176 }
177
178 // verifies whether a node-id matches the IP it's used from
179 // returns true if the node-id is OK coming from this source
180 // and false otherwise.
verify_id(node_id const & nid,address const & source_ip)181 bool verify_id(node_id const& nid, address const& source_ip)
182 {
183 // no need to verify local IPs, they would be incorrect anyway
184 if (is_local(source_ip)) return true;
185
186 node_id h = generate_id_impl(source_ip, nid[19]);
187 return nid[0] == h[0] && nid[1] == h[1] && (nid[2] & 0xf8) == (h[2] & 0xf8);
188 }
189
generate_id(address const & ip)190 node_id generate_id(address const& ip)
191 {
192 return generate_id_impl(ip, random(0xffffffff));
193 }
194
matching_prefix(node_id const & nid,int mask,int prefix,int offset)195 bool matching_prefix(node_id const& nid, int mask, int prefix, int offset)
196 {
197 node_id id = nid;
198 id <<= offset;
199 return (id[0] & mask) == prefix;
200 }
201
generate_prefix_mask(int const bits)202 node_id generate_prefix_mask(int const bits)
203 {
204 TORRENT_ASSERT(bits >= 0);
205 TORRENT_ASSERT(bits <= 160);
206 node_id mask;
207 std::size_t b = 0;
208 for (; int(b) < bits - 7; b += 8) mask[b / 8] |= 0xff;
209 if (bits < 160) mask[b / 8] |= (0xff << (8 - (bits & 7))) & 0xff;
210 return mask;
211 }
212
213 } } // namespace libtorrent::dht
214