Rate gate expensive validation of new identities in HELLO.

6 files changed, 87 insertions, 1 deletions

diff --git a/node/Constants.hpp b/node/Constants.hpp
index 6400e289..8803ecee 100644
--- a/node/Constants.hpp
+++ b/node/Constants.hpp
@@ -376,6 +376,26 @@
 #define ZT_PEER_GENERAL_RATE_LIMIT 1000
 
 /**
+ * Don't do expensive identity validation more often than this
+ *
+ * IPv4 and IPv6 address prefixes are hashed down to 14-bit (0-16383) integers
+ * using the first 24 bits for IPv4 or the first 48 bits for IPv6. These are
+ * then rate limited to one identity validation per this often milliseconds.
+ */
+#if (defined(__amd64) || defined(__amd64__) || defined(__x86_64) || defined(__x86_64__) || defined(__AMD64) || defined(__AMD64__) || defined(_M_X64) || defined(_M_AMD64))
+// AMD64 machines can do anywhere from one every 50ms to one every 10ms. This provides plenty of margin.
+#define ZT_IDENTITY_VALIDATION_SOURCE_RATE_LIMIT 2000
+#else
+#if (defined(__i386__) || defined(__i486__) || defined(__i586__) || defined(__i686__) || defined(_M_IX86) || defined(_X86_) || defined(__I86__))
+// 32-bit Intel machines usually average about one every 100ms
+#define ZT_IDENTITY_VALIDATION_SOURCE_RATE_LIMIT 5000
+#else
+// This provides a safe margin for ARM, MIPS, etc. that usually average one every 250-400ms
+#define ZT_IDENTITY_VALIDATION_SOURCE_RATE_LIMIT 10000
+#endif
+#endif
+
+/**
  * How long is a path or peer considered to have a trust relationship with us (for e.g. relay policy) since last trusted established packet?
  */
 #define ZT_TRUST_EXPIRATION 600000
diff --git a/node/IncomingPacket.cpp b/node/IncomingPacket.cpp
index ee4d62c0..41f3e47d 100644
--- a/node/IncomingPacket.cpp
+++ b/node/IncomingPacket.cpp
@@ -247,6 +247,10 @@ bool IncomingPacket::_doHELLO(const RuntimeEnvironment *RR,const bool alreadyAut
 				if (peer->identity() != id) {
 					// Identity is different from the one we already have -- address collision
 
+					// Check rate limits
+					if (!RR->node->rateGateIdentityVerification(now,_path->address()))
+						return true;
+
 					uint8_t key[ZT_PEER_SECRET_KEY_LENGTH];
 					if (RR->identity.agree(id,key,ZT_PEER_SECRET_KEY_LENGTH)) {
 						if (dearmor(key)) { // ensure packet is authentic, otherwise drop
@@ -285,7 +289,11 @@ bool IncomingPacket::_doHELLO(const RuntimeEnvironment *RR,const bool alreadyAut
 				return true;
 			}
 
-			// Check packet integrity and MAC
+			// Check rate limits
+			if (!RR->node->rateGateIdentityVerification(now,_path->address()))
+				return true;
+
+			// Check packet integrity and MAC (this is faster than locallyValidate() so do it first to filter out total crap)
 			SharedPtr<Peer> newPeer(new Peer(RR,RR->identity,id));
 			if (!dearmor(newPeer->key())) {
 				TRACE("rejected HELLO from %s(%s): packet failed authentication",id.address().toString().c_str(),_path->address().toString().c_str());
diff --git a/node/InetAddress.hpp b/node/InetAddress.hpp
index 6f070fbf..1dff710d 100644
--- a/node/InetAddress.hpp
+++ b/node/InetAddress.hpp
@@ -450,6 +450,30 @@ struct InetAddress : public sockaddr_storage
 		throw();
 
 	/**
+	 * @return 14-bit (0-16383) hash of this IP's first 24 or 48 bits (for V4 or V6) for rate limiting code, or 0 if non-IP
+	 */
+	inline unsigned long rateGateHash() const
+	{
+		unsigned long h = 0;
+		switch(ss_family) {
+			case AF_INET:
+				h = (Utils::ntoh((uint32_t)reinterpret_cast<const struct sockaddr_in *>(this)->sin_addr.s_addr) & 0xffffff00) >> 8;
+				h ^= (h >> 14);
+				break;
+			case AF_INET6: {
+				const uint8_t *ip = reinterpret_cast<const uint8_t *>(reinterpret_cast<const struct sockaddr_in6 *>(this)->sin6_addr.s6_addr);
+				h = ((unsigned long)ip[0]); h <<= 1;
+				h += ((unsigned long)ip[1]); h <<= 1;
+				h += ((unsigned long)ip[2]); h <<= 1;
+				h += ((unsigned long)ip[3]); h <<= 1;
+				h += ((unsigned long)ip[4]); h <<= 1;
+				h += ((unsigned long)ip[5]);
+			}	break;
+		}
+		return (h & 0x3fff);
+	}
+
+	/**
 	 * @return True if address family is non-zero
 	 */
 	inline operator bool() const throw() { return (ss_family != 0); }
diff --git a/node/Node.cpp b/node/Node.cpp
index add3117e..ec719668 100644
--- a/node/Node.cpp
+++ b/node/Node.cpp
@@ -78,6 +78,7 @@ Node::Node(
 
 	memset(_expectingRepliesToBucketPtr,0,sizeof(_expectingRepliesToBucketPtr));
 	memset(_expectingRepliesTo,0,sizeof(_expectingRepliesTo));
+	memset(_lastIdentityVerification,0,sizeof(_lastIdentityVerification));
 
 	// Use Salsa20 alone as a high-quality non-crypto PRNG
 	{
diff --git a/node/Node.hpp b/node/Node.hpp
index e616da3d..ee0d6c4c 100644
--- a/node/Node.hpp
+++ b/node/Node.hpp
@@ -283,6 +283,24 @@ public:
 		return false;
 	}
 
+	/**
+	 * Check whether we should do potentially expensive identity verification (rate limit)
+	 *
+	 * @param now Current time
+	 * @param from Source address of packet
+	 * @return True if within rate limits
+	 */
+	inline bool rateGateIdentityVerification(const uint64_t now,const InetAddress &from)
+	{
+		unsigned long iph = from.rateGateHash();
+		printf("%s %.4lx\n",from.toString().c_str(),iph);
+		if ((now - _lastIdentityVerification[iph]) >= ZT_IDENTITY_VALIDATION_SOURCE_RATE_LIMIT) {
+			_lastIdentityVerification[iph] = now;
+			return true;
+		}
+		return false;
+	}
+
 	virtual void ncSendConfig(uint64_t nwid,uint64_t requestPacketId,const Address &destination,const NetworkConfig &nc,bool sendLegacyFormatConfig);
 	virtual void ncSendError(uint64_t nwid,uint64_t requestPacketId,const Address &destination,NetworkController::ErrorCode errorCode);
 
@@ -302,9 +320,13 @@ private:
 
 	void *_uPtr; // _uptr (lower case) is reserved in Visual Studio :P
 
+	// For tracking packet IDs to filter out OK/ERROR replies to packets we did not send
 	uint8_t _expectingRepliesToBucketPtr[ZT_EXPECTING_REPLIES_BUCKET_MASK1 + 1];
 	uint64_t _expectingRepliesTo[ZT_EXPECTING_REPLIES_BUCKET_MASK1 + 1][ZT_EXPECTING_REPLIES_BUCKET_MASK2 + 1];
 
+	// Time of last identity verification indexed by InetAddress.rateGateHash()
+	uint64_t _lastIdentityVerification[16384];
+
 	ZT_DataStoreGetFunction _dataStoreGetFunction;
 	ZT_DataStorePutFunction _dataStorePutFunction;
 	ZT_WirePacketSendFunction _wirePacketSendFunction;
diff --git a/selftest.cpp b/selftest.cpp
index 9992d757..adac2f58 100644
--- a/selftest.cpp
+++ b/selftest.cpp
@@ -327,6 +327,17 @@ static int testCrypto()
 	}
 	std::cout << "PASS" << std::endl;
 
+	std::cout << "[crypto] Benchmarking C25519 ECC key agreement... "; std::cout.flush();
+	C25519::Pair bp[8];
+	for(int k=0;k<8;++k)
+		bp[k] = C25519::generate();
+	const uint64_t st = OSUtils::now();
+	for(unsigned int k=0;k<50;++k) {
+		C25519::agree(bp[~k & 7],bp[k & 7].pub,buf1,64);
+	}
+	const uint64_t et = OSUtils::now();
+	std::cout << ((double)(et - st) / 50.0) << "ms per agreement." << std::endl;
+
 	std::cout << "[crypto] Testing Ed25519 ECC signatures... "; std::cout.flush();
 	C25519::Pair didntSign = C25519::generate();
 	for(unsigned int i=0;i<10;++i) {