From e5f168f599ba053ee5e6029387dd7ad4b95a7d28 Mon Sep 17 00:00:00 2001 From: Adam Ierymenko Date: Wed, 7 Oct 2015 13:35:46 -0700 Subject: Add proof of work request for future DDOS mitigation use. --- node/IncomingPacket.cpp | 121 ++++++++++++++++++++++++++++++++++++++++++++++++ node/IncomingPacket.hpp | 22 +++++++++ node/Packet.cpp | 2 +- node/Packet.hpp | 102 ++++++++++++++++++++++++++++++++-------- selftest.cpp | 14 ++++++ 5 files changed, 240 insertions(+), 21 deletions(-) diff --git a/node/IncomingPacket.cpp b/node/IncomingPacket.cpp index 19bea243..de901779 100644 --- a/node/IncomingPacket.cpp +++ b/node/IncomingPacket.cpp @@ -41,6 +41,8 @@ #include "Peer.hpp" #include "NetworkController.hpp" #include "SelfAwareness.hpp" +#include "Salsa20.hpp" +#include "SHA512.hpp" namespace ZeroTier { @@ -90,6 +92,7 @@ bool IncomingPacket::tryDecode(const RuntimeEnvironment *RR) case Packet::VERB_PUSH_DIRECT_PATHS: return _doPUSH_DIRECT_PATHS(RR,peer); case Packet::VERB_CIRCUIT_TEST: return _doCIRCUIT_TEST(RR,peer); case Packet::VERB_CIRCUIT_TEST_REPORT: return _doCIRCUIT_TEST_REPORT(RR,peer); + case Packet::VERB_REQUEST_PROOF_OF_WORK: return _doREQUEST_PROOF_OF_WORK(RR,peer); } } else { RR->sw->requestWhois(sourceAddress); @@ -1042,6 +1045,124 @@ bool IncomingPacket::_doCIRCUIT_TEST_REPORT(const RuntimeEnvironment *RR,const S return true; } +bool IncomingPacket::_doREQUEST_PROOF_OF_WORK(const RuntimeEnvironment *RR,const SharedPtr &peer) +{ + try { + // Right now this is only allowed from root servers -- may be allowed from controllers and relays later. + if (RR->topology->isRoot(peer->identity())) { + const unsigned int difficulty = (*this)[ZT_PACKET_IDX_PAYLOAD + 1]; + const unsigned int challengeLength = at(ZT_PACKET_IDX_PAYLOAD + 2); + if (challengeLength > ZT_PROTO_MAX_PACKET_LENGTH) + return true; // sanity check, drop invalid size + const unsigned char *challenge = field(ZT_PACKET_IDX_PAYLOAD + 4,challengeLength); + + switch((*this)[ZT_PACKET_IDX_PAYLOAD]) { + + // Salsa20/12+SHA512 hashcash + case 0x01: { + unsigned char result[16]; + computeSalsa2012Sha512ProofOfWork(difficulty,challenge,challengeLength,result); + + Packet outp(peer->address(),RR->identity.address(),Packet::VERB_OK); + outp.append((unsigned char)Packet::VERB_REQUEST_PROOF_OF_WORK); + outp.append(packetId()); + outp.append((uint16_t)sizeof(result)); + outp.append(result,sizeof(result)); + outp.armor(peer->key(),true); + RR->node->putPacket(_localAddress,_remoteAddress,outp.data(),outp.size()); + } break; + + default: + TRACE("dropped REQUEST_PROO_OF_WORK from %s(%s): unrecognized proof of work type",peer->address().toString().c_str(),_remoteAddress.toString().c_str()); + break; + } + } else { + TRACE("dropped REQUEST_PROO_OF_WORK from %s(%s): not trusted enough",peer->address().toString().c_str(),_remoteAddress.toString().c_str()); + } + } catch ( ... ) { + TRACE("dropped REQUEST_PROOF_OF_WORK from %s(%s): unexpected exception",peer->address().toString().c_str(),_remoteAddress.toString().c_str()); + } + return true; +} + +void IncomingPacket::computeSalsa2012Sha512ProofOfWork(unsigned int difficulty,const void *challenge,unsigned int challengeLength,unsigned char result[16]) +{ + unsigned char salsabuf[131072]; // 131072 == protocol constant, size of memory buffer for this proof of work function + char candidatebuf[ZT_PROTO_MAX_PACKET_LENGTH + 256]; + unsigned char shabuf[ZT_SHA512_DIGEST_LEN]; + const uint64_t s20iv = 0; // zero IV for Salsa20 + char *const candidate = (char *)(( ((uintptr_t)&(candidatebuf[0])) | 0xf ) + 1); // align to 16-byte boundary to ensure that uint64_t type punning of initial nonce is okay + Salsa20 s20; + unsigned int d; + unsigned char *p; + + Utils::getSecureRandom(candidate,16); + memcpy(candidate + 16,challenge,challengeLength); + + if (difficulty > 512) + difficulty = 512; // sanity check + +try_salsa2012sha512_again: + ++*(reinterpret_cast(candidate)); + + SHA512::hash(shabuf,candidate,16 + challengeLength); + s20.init(shabuf,256,&s20iv,12); + memset(salsabuf,0,sizeof(salsabuf)); + s20.encrypt(salsabuf,salsabuf,sizeof(salsabuf)); + SHA512::hash(shabuf,salsabuf,sizeof(salsabuf)); + + d = difficulty; + p = shabuf; + while (d >= 8) { + if (*(p++)) + goto try_salsa2012sha512_again; + d -= 8; + } + if (d > 0) { + if ( ((((unsigned int)*p) << d) & 0xff00) != 0 ) + goto try_salsa2012sha512_again; + } + + memcpy(result,candidate,16); +} + +bool IncomingPacket::testSalsa2012Sha512ProofOfWorkResult(unsigned int difficulty,const void *challenge,unsigned int challengeLength,const unsigned char proposedResult[16]) +{ + unsigned char salsabuf[131072]; // 131072 == protocol constant, size of memory buffer for this proof of work function + char candidate[ZT_PROTO_MAX_PACKET_LENGTH + 256]; + unsigned char shabuf[ZT_SHA512_DIGEST_LEN]; + const uint64_t s20iv = 0; // zero IV for Salsa20 + Salsa20 s20; + unsigned int d; + unsigned char *p; + + if (difficulty > 512) + difficulty = 512; // sanity check + + memcpy(candidate,proposedResult,16); + memcpy(candidate + 16,challenge,challengeLength); + + SHA512::hash(shabuf,candidate,16 + challengeLength); + s20.init(shabuf,256,&s20iv,12); + memset(salsabuf,0,sizeof(salsabuf)); + s20.encrypt(salsabuf,salsabuf,sizeof(salsabuf)); + SHA512::hash(shabuf,salsabuf,sizeof(salsabuf)); + + d = difficulty; + p = shabuf; + while (d >= 8) { + if (*(p++)) + return false; + d -= 8; + } + if (d > 0) { + if ( ((((unsigned int)*p) << d) & 0xff00) != 0 ) + return false; + } + + return true; +} + void IncomingPacket::_sendErrorNeedCertificate(const RuntimeEnvironment *RR,const SharedPtr &peer,uint64_t nwid) { Packet outp(source(),RR->identity.address(),Packet::VERB_ERROR); diff --git a/node/IncomingPacket.hpp b/node/IncomingPacket.hpp index 06220c4b..fd7a06c0 100644 --- a/node/IncomingPacket.hpp +++ b/node/IncomingPacket.hpp @@ -107,6 +107,27 @@ public: */ inline uint64_t receiveTime() const throw() { return _receiveTime; } + /** + * Compute the Salsa20/12+SHA512 proof of work function + * + * @param difficulty Difficulty in bits (max: 64) + * @param challenge Challenge string + * @param challengeLength Length of challenge in bytes (max allowed: ZT_PROTO_MAX_PACKET_LENGTH) + * @param result Buffer to fill with 16-byte result + */ + static void computeSalsa2012Sha512ProofOfWork(unsigned int difficulty,const void *challenge,unsigned int challengeLength,unsigned char result[16]); + + /** + * Verify the result of Salsa20/12+SHA512 proof of work + * + * @param difficulty Difficulty in bits (max: 64) + * @param challenge Challenge bytes + * @param challengeLength Length of challenge in bytes (max allowed: ZT_PROTO_MAX_PACKET_LENGTH) + * @param proposedResult Result supplied by client + * @return True if result is valid + */ + static bool testSalsa2012Sha512ProofOfWorkResult(unsigned int difficulty,const void *challenge,unsigned int challengeLength,const unsigned char proposedResult[16]); + private: // These are called internally to handle packet contents once it has // been authenticated, decrypted, decompressed, and classified. @@ -126,6 +147,7 @@ private: bool _doPUSH_DIRECT_PATHS(const RuntimeEnvironment *RR,const SharedPtr &peer); bool _doCIRCUIT_TEST(const RuntimeEnvironment *RR,const SharedPtr &peer); bool _doCIRCUIT_TEST_REPORT(const RuntimeEnvironment *RR,const SharedPtr &peer); + bool _doREQUEST_PROOF_OF_WORK(const RuntimeEnvironment *RR,const SharedPtr &peer); // Send an ERROR_NEED_MEMBERSHIP_CERTIFICATE to a peer indicating that an updated cert is needed to communicate void _sendErrorNeedCertificate(const RuntimeEnvironment *RR,const SharedPtr &peer,uint64_t nwid); diff --git a/node/Packet.cpp b/node/Packet.cpp index f69e4e79..2d973dff 100644 --- a/node/Packet.cpp +++ b/node/Packet.cpp @@ -45,7 +45,6 @@ const char *Packet::verbString(Verb v) case VERB_RENDEZVOUS: return "RENDEZVOUS"; case VERB_FRAME: return "FRAME"; case VERB_EXT_FRAME: return "EXT_FRAME"; - case VERB_P5_MULTICAST_FRAME: return "P5_MULTICAST_FRAME"; case VERB_MULTICAST_LIKE: return "MULTICAST_LIKE"; case VERB_NETWORK_MEMBERSHIP_CERTIFICATE: return "NETWORK_MEMBERSHIP_CERTIFICATE"; case VERB_NETWORK_CONFIG_REQUEST: return "NETWORK_CONFIG_REQUEST"; @@ -56,6 +55,7 @@ const char *Packet::verbString(Verb v) case VERB_PUSH_DIRECT_PATHS: return "PUSH_DIRECT_PATHS"; case VERB_CIRCUIT_TEST: return "CIRCUIT_TEST"; case VERB_CIRCUIT_TEST_REPORT: return "CIRCUIT_TEST_REPORT"; + case VERB_REQUEST_PROOF_OF_WORK: return "REQUEST_PROOF_OF_WORK"; } return "(unknown)"; } diff --git a/node/Packet.hpp b/node/Packet.hpp index 1413db10..93b594e5 100644 --- a/node/Packet.hpp +++ b/node/Packet.hpp @@ -523,10 +523,13 @@ public: */ enum Verb /* Max value: 32 (5 bits) */ { - /* No operation, payload ignored, no reply */ + /** + * No operation (ignored, no reply) + */ VERB_NOP = 0, - /* Announcement of a node's existence: + /** + * Announcement of a node's existence: * <[1] protocol version> * <[1] software major version> * <[1] software minor version> @@ -564,7 +567,8 @@ public: */ VERB_HELLO = 1, - /* Error response: + /** + * Error response: * <[1] in-re verb> * <[8] in-re packet ID> * <[1] error code> @@ -572,14 +576,16 @@ public: */ VERB_ERROR = 2, - /* Success response: + /** + * Success response: * <[1] in-re verb> * <[8] in-re packet ID> * <[...] request-specific payload> */ VERB_OK = 3, - /* Query an identity by address: + /** + * Query an identity by address: * <[5] address to look up> * * OK response payload: @@ -590,7 +596,8 @@ public: */ VERB_WHOIS = 4, - /* Meet another node at a given protocol address: + /** + * Meet another node at a given protocol address: * <[1] flags (unused, currently 0)> * <[5] ZeroTier address of peer that might be found at this address> * <[2] 16-bit protocol address port> @@ -613,7 +620,8 @@ public: */ VERB_RENDEZVOUS = 5, - /* ZT-to-ZT unicast ethernet frame (shortened EXT_FRAME): + /** + * ZT-to-ZT unicast ethernet frame (shortened EXT_FRAME): * <[8] 64-bit network ID> * <[2] 16-bit ethertype> * <[...] ethernet payload> @@ -628,7 +636,8 @@ public: */ VERB_FRAME = 6, - /* Full Ethernet frame with MAC addressing and optional fields: + /** + * Full Ethernet frame with MAC addressing and optional fields: * <[8] 64-bit network ID> * <[1] flags> * [<[...] certificate of network membership>] @@ -652,9 +661,10 @@ public: VERB_EXT_FRAME = 7, /* DEPRECATED */ - VERB_P5_MULTICAST_FRAME = 8, + //VERB_P5_MULTICAST_FRAME = 8, - /* Announce interest in multicast group(s): + /** + * Announce interest in multicast group(s): * <[8] 64-bit network ID> * <[6] multicast Ethernet address> * <[4] multicast additional distinguishing information (ADI)> @@ -667,7 +677,8 @@ public: */ VERB_MULTICAST_LIKE = 9, - /* Network member certificate replication/push: + /** + * Network member certificate replication/push: * <[...] serialized certificate of membership> * [ ... additional certificates may follow ...] * @@ -678,7 +689,8 @@ public: */ VERB_NETWORK_MEMBERSHIP_CERTIFICATE = 10, - /* Network configuration request: + /** + * Network configuration request: * <[8] 64-bit network ID> * <[2] 16-bit length of request meta-data dictionary> * <[...] string-serialized request meta-data> @@ -713,7 +725,8 @@ public: */ VERB_NETWORK_CONFIG_REQUEST = 11, - /* Network configuration refresh request: + /** + * Network configuration refresh request: * <[...] array of 64-bit network IDs> * * This can be sent by the network controller to inform a node that it @@ -724,7 +737,8 @@ public: */ VERB_NETWORK_CONFIG_REFRESH = 12, - /* Request endpoints for multicast distribution: + /** + * Request endpoints for multicast distribution: * <[8] 64-bit network ID> * <[1] flags> * <[6] MAC address of multicast group being queried> @@ -762,7 +776,8 @@ public: */ VERB_MULTICAST_GATHER = 13, - /* Multicast frame: + /** + * Multicast frame: * <[8] 64-bit network ID> * <[1] flags> * [<[...] network certificate of membership>] @@ -803,7 +818,8 @@ public: */ VERB_MULTICAST_FRAME = 14, - /* Ephemeral (PFS) key push: (UNFINISHED, NOT IMPLEMENTED YET) + /** + * Ephemeral (PFS) key push: (UNFINISHED, NOT IMPLEMENTED YET) * <[2] flags (unused and reserved, must be 0)> * <[2] length of padding / extra field section> * <[...] padding / extra field section> @@ -859,7 +875,8 @@ public: */ VERB_SET_EPHEMERAL_KEY = 15, - /* Push of potential endpoints for direct communication: + /** + * Push of potential endpoints for direct communication: * <[2] 16-bit number of paths> * <[...] paths> * @@ -899,7 +916,8 @@ public: */ VERB_PUSH_DIRECT_PATHS = 16, - /* Source-routed circuit test message: + /** + * Source-routed circuit test message: * <[5] address of originator of circuit test> * <[2] 16-bit flags> * <[8] 64-bit timestamp> @@ -977,7 +995,8 @@ public: */ VERB_CIRCUIT_TEST = 17, - /* Circuit test hop report: + /** + * Circuit test hop report: * <[8] 64-bit timestamp (from original test)> * <[8] 64-bit test ID (from original test)> * <[8] 64-bit reporter timestamp (reporter's clock, 0 if unspec)> @@ -1010,7 +1029,50 @@ public: * If a test report is received and no circuit test was sent, it should be * ignored. This message generates no OK or ERROR response. */ - VERB_CIRCUIT_TEST_REPORT = 18 + VERB_CIRCUIT_TEST_REPORT = 18, + + /** + * Request proof of work: + * <[1] 8-bit proof of work type> + * <[1] 8-bit proof of work difficulty> + * <[2] 16-bit length of proof of work challenge> + * <[...] proof of work challenge> + * + * This requests that a peer perform a proof of work calucation. It can be + * sent by highly trusted peers (e.g. root servers, network controllers) + * under suspected denial of service conditions in an attempt to filter + * out "non-serious" peers and remain responsive to those proving their + * intent to actually communicate. + * + * If the peer obliges to perform the work, it does so and responds with + * an OK containing the result. Otherwise it may ignore the message or + * response with an ERROR_INVALID_REQUEST or ERROR_UNSUPPORTED_OPERATION. + * + * Proof of work type IDs: + * 0x01 - Salsa20/12+SHA512 hashcash function + * + * Salsa20/12+SHA512 is based on the following composite hash function: + * + * (1) Compute SHA512(candidate) + * (2) Use the first 256 bits of the result of #1 as a key to encrypt + * 131072 zero bytes with Salsa20/12 (with a zero IV). + * (3) Compute SHA512(the result of step #2) + * (4) Accept this candiate if the first [difficulty] bits of the result + * from step #3 are zero. Otherwise generate a new candidate and try + * again. + * + * This is performed repeatedly on candidates generated by appending the + * supplied challenge to an arbitrary nonce until a valid candidate + * is found. This chosen prepended nonce is then returned as the result + * in OK. + * + * OK payload: + * <[2] 16-bit length of result> + * <[...] computed proof of work> + * + * ERROR has no payload. + */ + VERB_REQUEST_PROOF_OF_WORK = 19 }; /** diff --git a/selftest.cpp b/selftest.cpp index e938cf4d..090839ee 100644 --- a/selftest.cpp +++ b/selftest.cpp @@ -52,6 +52,7 @@ #include "node/CertificateOfMembership.hpp" #include "node/Defaults.hpp" #include "node/Node.hpp" +#include "node/IncomingPacket.hpp" #include "osdep/OSUtils.hpp" #include "osdep/Phy.hpp" @@ -285,6 +286,19 @@ static int testCrypto() ::free((void *)bb); } + /* + for(unsigned int d=8;d<=10;++d) { + for(int k=0;k<8;++k) { + std::cout << "[crypto] computeSalsa2012Sha512ProofOfWork(" << d << ",\"foobarbaz\",9) == "; std::cout.flush(); + unsigned char result[16]; + uint64_t start = OSUtils::now(); + IncomingPacket::computeSalsa2012Sha512ProofOfWork(d,"foobarbaz",9,result); + uint64_t end = OSUtils::now(); + std::cout << Utils::hex(result,16) << " -- valid: " << IncomingPacket::testSalsa2012Sha512ProofOfWorkResult(d,"foobarbaz",9,result) << ", " << (end - start) << "ms" << std::endl; + } + } + */ + std::cout << "[crypto] Testing C25519 and Ed25519 against test vectors... "; std::cout.flush(); for(int k=0;k