|
Wiselib
|
wiselib.testing/algorithms/crypto/eschenauer_gligor/eschenauer_gligor_algorithm.h
Go to the documentation of this file.
00001 /*************************************************************************** 00002 ** This file is part of the generic algorithm library Wiselib. ** 00003 ** Copyright (C) 2008,2009 by the Wisebed (www.wisebed.eu) project. ** 00004 ** ** 00005 ** The Wiselib is free software: you can redistribute it and/or modify ** 00006 ** it under the terms of the GNU Lesser General Public License as ** 00007 ** published by the Free Software Foundation, either version 3 of the ** 00008 ** License, or (at your option) any later version. ** 00009 ** ** 00010 ** The Wiselib is distributed in the hope that it will be useful, ** 00011 ** but WITHOUT ANY WARRANTY; without even the implied warranty of ** 00012 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ** 00013 ** GNU Lesser General Public License for more details. ** 00014 ** ** 00015 ** You should have received a copy of the GNU Lesser General Public ** 00016 ** License along with the Wiselib. ** 00017 ** If not, see <http://www.gnu.org/licenses/>. ** 00018 ** ** 00019 ** Author: Christoph Knecht, University of Bern 2010 ** 00020 ***************************************************************************/ 00021 #ifndef ESCHENAUER_GLIGOR_ALGORITHM_H 00022 #define ESCHENAUER_GLIGOR_ALGORITHM_H 00023 00024 #include <math.h> 00025 #include "util/base_classes/routing_base.h" 00026 #include "algorithm/eschenauer_gligor_message.h" 00027 #include "algorithm/eschenauer_gligor_crypto_handler.h" 00028 #include "algorithm/eschenauer_gligor_config.h" 00029 #include "algorithm/aes.h" 00030 #ifdef SHAWN 00031 #include <stdlib.h> 00032 #endif 00033 00034 // this part is used to patch the files manually 00035 #ifndef SHAWN 00036 static const uint8_t keys[ RING_SIZE * 16 ] = "aa22bbbbcccc"; 00037 uint8_t identifiers[ RING_SIZE * 2 + NEIGHBOUR_COUNT * 2 ] = "aa11bbbbcccc"; 00038 uint8_t backup_keys[ NEIGHBOUR_COUNT * 16 ] = "aa00bbbbcccc"; 00039 #endif 00040 00041 namespace wiselib 00042 { 00052 template<typename OsModel_P, 00053 typename Routing_P, 00054 typename NodeidIntMap_P, 00055 typename Radio_P = typename OsModel_P::Radio, 00056 typename Debug_P = typename OsModel_P::Debug> 00057 class EschenauerGligorAlgorithm 00058 : public RoutingBase<OsModel_P, Radio_P> 00059 { 00060 public: 00061 typedef OsModel_P OsModel; 00062 typedef Routing_P RoutingType; 00063 typedef NodeidIntMap_P MapType; 00064 typedef Radio_P Radio; 00065 typedef Debug_P Debug; 00066 00067 typedef typename OsModel::Timer Timer; 00068 00069 typedef typename RoutingType::RoutingTable RoutingTable; 00070 typedef typename RoutingType::RoutingTableIterator RoutingTableIterator; 00071 00072 typedef typename Radio::node_id_t node_id_t; 00073 typedef typename Radio::size_t size_t; 00074 typedef typename Radio::block_data_t block_data_t; 00075 typedef typename Radio::message_id_t message_id_t; 00076 typedef typename MapType::iterator MapTypeIterator; 00077 00078 typedef typename Timer::millis_t millis_t; 00079 00080 typedef EschenauerGligorAlgorithm<OsModel, RoutingType, MapType, Radio, Debug> self_type; 00081 typedef EschenaurGligorMessage<OsModel, Radio> Message; 00082 typedef self_type* self_pointer_t; 00083 00084 inline EschenauerGligorAlgorithm(); 00085 inline void enable(); 00086 inline void disable(); 00087 inline void send( node_id_t, size_t, block_data_t* ); 00088 inline void receive( node_id_t, size_t, block_data_t* ); 00089 00090 inline void set_routing_type( RoutingType* routing ) 00091 { routing_ = routing; }; 00092 00093 inline RoutingType* routing_type() 00094 { return routing_; }; 00095 00096 inline void init( Radio& radio, Timer& timer, Debug& debug ) 00097 { 00098 radio_ = &radio; 00099 timer_ = &timer; 00100 debug_ = &debug; 00101 } 00102 00103 // automatic patching (during runtime) by Shawn 00104 #ifdef SHAWN 00105 uint8_t identifiers[ RING_SIZE * 2 + NEIGHBOUR_COUNT * 2 ]; 00106 uint8_t keys[ RING_SIZE * 16 ]; 00107 uint8_t backup_keys[ NEIGHBOUR_COUNT * 16 ]; 00108 #endif 00109 00110 private: 00111 inline void key_proposal_( node_id_t, node_id_t, node_id_t ); 00112 inline void print_ring_(); 00113 inline void print_neighbours_(); 00114 inline void send_identifier_list_(); 00115 inline void send_key_proposal_( node_id_t, node_id_t, node_id_t, uint16_t ); 00116 inline void send_neighbour_list_( node_id_t ); 00117 inline void send_neighbour_request_( node_id_t ); 00118 inline void timer_elapsed_( void* ); 00119 00120 // subroutines called during reception 00121 inline void process_encrypted_message_( node_id_t, Message * ); 00122 inline void process_exchange_identifiers_( node_id_t, Message * ); 00123 inline void process_key_proposal_( node_id_t, Message * ); 00124 inline void process_neighbour_list_( node_id_t, Message *, uint8_t ); 00125 inline void process_neighbour_request_( node_id_t, Message * ); 00126 inline void work_neighbour_request_( void* ); 00127 00128 // adds a new key to the ring 00129 inline void store_new_key_( uint8_t * ); 00130 00131 // returns some "random" time used for waiting 00132 inline millis_t random_work_period_() 00133 { 00134 #ifdef SHAWN 00135 seed_ = ( rand() * ( 1.0 / ( RAND_MAX + 1.0 ) ) ) * 60; 00136 return (millis_t)( seed_ + MIN_WORK_TIME ) * 1000; 00137 #endif 00138 #ifndef SHAWN 00139 seed_++; 00140 seed_ = seed_ % 63; 00141 return (millis_t)( work_period_[seed_] + MIN_WORK_TIME ) * 1000; 00142 #endif 00143 }; 00144 00145 Radio& radio() 00146 { return *radio_; } 00147 00148 Timer& timer() 00149 { return *timer_; } 00150 00151 Debug& debug() 00152 { return *debug_; } 00153 00154 typename Radio::self_pointer_t radio_; 00155 typename Timer::self_pointer_t timer_; 00156 typename Debug::self_pointer_t debug_; 00157 00158 RoutingType *routing_; 00159 00160 // storage container for all the neighbouring nodes (including the offset corresponding to their key) 00161 MapType neighbour_map_; 00162 00163 int callback_id_; 00164 uint16_t seq_nr_; 00165 uint16_t seed_; 00166 uint8_t work_period_[64]; 00167 00168 EschenauerGligorCryptoHandler<OsModel, AES<OsModel> > crypto_handler_; 00169 00170 enum MessageIds 00171 { 00172 EXCHANGE_IDENTIFIERS = 120, 00173 ENCRYPTED_MESSAGE = 121, 00174 NEIGHBOUR_LIST_1 = 122, 00175 NEIGHBOUR_LIST_2 = 123, 00176 KEY_PROPOSAL = 124, 00177 NEIGHBOUR_REQUEST = 125 00178 }; 00179 00180 node_id_t request_from_; 00181 node_id_t request_dest_; 00182 }; 00183 // ----------------------------------------------------------------------- 00184 // ----------------------------------------------------------------------- 00185 // ----------------------------------------------------------------------- 00186 template<typename OsModel_P, 00187 typename Routing_P, 00188 typename NodeidIntMap_P, 00189 typename Radio_P, 00190 typename Debug_P> 00191 EschenauerGligorAlgorithm<OsModel_P, Routing_P, NodeidIntMap_P, Radio_P, Debug_P>:: 00192 EschenauerGligorAlgorithm() 00193 : radio_ ( 0 ), 00194 timer_ ( 0 ), 00195 debug_ ( 0 ), 00196 callback_id_ ( 0 ), 00197 seq_nr_ ( 0 ) 00198 {} 00199 // ----------------------------------------------------------------------- 00200 template<typename OsModel_P, 00201 typename Routing_P, 00202 typename NodeidIntMap_P, 00203 typename Radio_P, 00204 typename Debug_P> 00205 void 00206 EschenauerGligorAlgorithm<OsModel_P, Routing_P, NodeidIntMap_P, Radio_P, Debug_P>:: 00207 enable() 00208 { 00209 #ifdef DEBUG_EG 00210 debug().debug( "EschenauerGligorAlgorithm: Booting (Node %i)\n", radio().id() ); 00211 #endif 00212 #ifdef DEBUG_EG 00213 print_ring_(); 00214 #endif 00215 00216 #ifdef SHAWN 00217 srand ( time( NULL ) * ( 3 * radio().id() + 2 ) ); 00218 #endif 00219 00220 seed_ = radio().id(); 00221 00222 work_period_[0] = 29; 00223 work_period_[1] = 25; 00224 work_period_[2] = 43; 00225 work_period_[3] = 36; 00226 work_period_[4] = 52; 00227 work_period_[5] = 10; 00228 work_period_[6] = 53; 00229 work_period_[7] = 5; 00230 work_period_[8] = 23; 00231 work_period_[9] = 58; 00232 work_period_[10] = 56; 00233 work_period_[11] = 29; 00234 work_period_[12] = 53; 00235 work_period_[13] = 21; 00236 work_period_[14] = 41; 00237 work_period_[15] = 0; 00238 work_period_[16] = 20; 00239 work_period_[17] = 13; 00240 work_period_[18] = 54; 00241 work_period_[19] = 29; 00242 work_period_[20] = 43; 00243 work_period_[21] = 20; 00244 work_period_[22] = 4; 00245 work_period_[23] = 22; 00246 work_period_[24] = 2; 00247 work_period_[25] = 42; 00248 work_period_[26] = 0; 00249 work_period_[27] = 28; 00250 work_period_[28] = 52; 00251 work_period_[29] = 28; 00252 work_period_[30] = 40; 00253 work_period_[31] = 21; 00254 work_period_[32] = 54; 00255 work_period_[33] = 23; 00256 work_period_[34] = 58; 00257 work_period_[35] = 46; 00258 work_period_[36] = 33; 00259 work_period_[37] = 51; 00260 work_period_[38] = 52; 00261 work_period_[39] = 57; 00262 work_period_[40] = 50; 00263 work_period_[41] = 49; 00264 work_period_[42] = 27; 00265 work_period_[43] = 44; 00266 work_period_[44] = 10; 00267 work_period_[45] = 8; 00268 work_period_[46] = 44; 00269 work_period_[47] = 31; 00270 work_period_[48] = 22; 00271 work_period_[49] = 39; 00272 work_period_[50] = 0; 00273 work_period_[51] = 5; 00274 work_period_[52] = 59; 00275 work_period_[53] = 5; 00276 work_period_[54] = 27; 00277 work_period_[55] = 2; 00278 work_period_[56] = 47; 00279 work_period_[57] = 28; 00280 work_period_[58] = 31; 00281 work_period_[59] = 40; 00282 work_period_[60] = 56; 00283 work_period_[61] = 11; 00284 work_period_[62] = 2; 00285 work_period_[63] = 50; 00286 00287 millis_t time = random_work_period_(); 00288 00289 radio().enable_radio(); 00290 radio().template reg_recv_callback<self_type, &self_type::receive>( this ); 00291 routing_->template reg_recv_callback<self_type, &self_type::receive>( this ); 00292 timer().template set_timer<self_type, &self_type::timer_elapsed_>( time, this, 0 ); 00293 } 00294 // ----------------------------------------------------------------------- 00295 template<typename OsModel_P, 00296 typename Routing_P, 00297 typename NodeidIntMap_P, 00298 typename Radio_P, 00299 typename Debug_P> 00300 void 00301 EschenauerGligorAlgorithm<OsModel_P, Routing_P, NodeidIntMap_P, Radio_P, Debug_P>:: 00302 disable() 00303 { 00304 #ifdef DEBUG_EG 00305 debug().debug( "EschenauerGligorAlgorithm: Disable\n" ); 00306 #endif 00307 00308 routing_->unreg_recv_callback(); 00309 } 00310 // ----------------------------------------------------------------------- 00311 template<typename OsModel_P, 00312 typename Routing_P, 00313 typename NodeidIntMap_P, 00314 typename Radio_P, 00315 typename Debug_P> 00316 void 00317 EschenauerGligorAlgorithm<OsModel_P, Routing_P, NodeidIntMap_P, Radio_P, Debug_P>:: 00318 receive( node_id_t from, size_t len, block_data_t *data ) 00319 { 00320 if( from == radio().id() ) 00321 return; 00322 00323 message_id_t msg_id = *data; 00324 Message *message = (Message *)data; 00325 00326 switch( msg_id ) 00327 { 00328 // we got a list of key identifiers 00329 case EXCHANGE_IDENTIFIERS: 00330 process_exchange_identifiers_( from, message ); 00331 break; 00332 // some encrypted content was sent over the network 00333 case ENCRYPTED_MESSAGE: 00334 process_encrypted_message_( from, message ); 00335 break; 00336 // some neighbour of us wants to establish a path using a secondary node 00337 case NEIGHBOUR_LIST_1: 00338 process_neighbour_list_( from, message, 1 ); 00339 break; 00340 // some neighbour of us wants to establish a path using a secondary and tertiary node 00341 case NEIGHBOUR_LIST_2: 00342 process_neighbour_list_( from, message, 2 ); 00343 break; 00344 // we received a proposal for a identifier-key pair 00345 case KEY_PROPOSAL: 00346 process_key_proposal_( from, message ); 00347 break; 00348 // we need a second level Neighbourhood-Analysis 00349 case NEIGHBOUR_REQUEST: 00350 process_neighbour_request_( from, message ); 00351 break; 00352 } 00353 } 00354 // ----------------------------------------------------------------------- 00355 template<typename OsModel_P, 00356 typename Routing_P, 00357 typename NodeidIntMap_P, 00358 typename Radio_P, 00359 typename Debug_P> 00360 void 00361 EschenauerGligorAlgorithm<OsModel_P, Routing_P, NodeidIntMap_P, Radio_P, Debug_P>:: 00362 send( node_id_t destination, size_t len, block_data_t *data ) 00363 { 00364 #ifdef DEBUG_EG 00365 debug().debug( "EschenauerGligorAlgorithm: Sending encrypted Message to Node %i (Node %i)\n", destination, radio().id() ); 00366 #endif 00367 00368 Message message; 00369 message.set_msg_id( ENCRYPTED_MESSAGE ); 00370 message.set_node_id( radio().id() ); 00371 message.set_dest_id( destination ); 00372 00373 message.set_seq_nr( 1 ); 00374 00375 // find the next hop to send the message to 00376 RoutingTable *table = routing_->routing_table(); 00377 RoutingTableIterator it = table->find( destination ); 00378 00379 if( it != table->end() && it->second.next_hop != radio().NULL_NODE_ID ) 00380 { 00381 // AES has fixed size 16 Bytes Blocks 00382 uint16_t length_aes = ( len / 16 + 1 ) * 16; 00383 00384 MapTypeIterator itt = neighbour_map_.find( it->second.next_hop ); 00385 00386 if( itt != neighbour_map_.end() ) 00387 { 00388 uint16_t offset = itt->second; 00389 uint8_t key[16]; 00390 00391 if( offset < RING_SIZE ) 00392 memcpy( key, keys + offset * 16, 16 ); 00393 else 00394 memcpy( key, backup_keys + ( offset - RING_SIZE ) * 16, 16 ); 00395 00396 uint8_t encrypted[ length_aes ]; 00397 00398 // encrypt it 00399 crypto_handler_.key_setup( key ); 00400 crypto_handler_.encrypt( data, encrypted, length_aes ); 00401 00402 message.set_payload( length_aes, encrypted ); 00403 routing_->send( it->second.next_hop, message.buffer_size(), (uint8_t*)&message ); 00404 } 00405 } 00406 } 00407 // ----------------------------------------------------------------------- 00408 // sends a list containing the own key identifiers 00409 template<typename OsModel_P, 00410 typename Routing_P, 00411 typename NodeidIntMap_P, 00412 typename Radio_P, 00413 typename Debug_P> 00414 void 00415 EschenauerGligorAlgorithm<OsModel_P, Routing_P, NodeidIntMap_P, Radio_P, Debug_P>:: 00416 send_identifier_list_() 00417 { 00418 #ifdef DEBUG_EG 00419 debug().debug( "EschenauerGligorAlgorithm: Sending Identifier-List (Node %i)\n", radio().id() ); 00420 #endif 00421 00422 Message message; 00423 message.set_msg_id( EXCHANGE_IDENTIFIERS ); 00424 message.set_node_id( radio().id() ); 00425 00426 uint16_t i; 00427 uint8_t k = 0; 00428 uint8_t temp[ RING_SIZE * 2 + NEIGHBOUR_COUNT * 2 ]; 00429 00430 for( i = 0; i < RING_SIZE + NEIGHBOUR_COUNT; i++ ) 00431 { 00432 uint8_t ident[2]; 00433 memcpy( ident, identifiers + i * 2, 2 ); 00434 00435 // do not send blacklisted or unused keys! 00436 if( *( ident ) != 0xff || *( ident + 1 ) != 0xff ) 00437 { 00438 memcpy( temp + k * 2, ident, 2 ); 00439 k++; 00440 } 00441 } 00442 00443 message.set_seq_nr( 1 ); 00444 message.set_payload( (size_t)( k * 2 ), (block_data_t*)temp ); 00445 00446 radio().send( radio().BROADCAST_ADDRESS, message.buffer_size(), (block_data_t*)&message ); 00447 } 00448 // ----------------------------------------------------------------------- 00449 template<typename OsModel_P, 00450 typename Routing_P, 00451 typename NodeidIntMap_P, 00452 typename Radio_P, 00453 typename Debug_P> 00454 void 00455 EschenauerGligorAlgorithm<OsModel_P, Routing_P, NodeidIntMap_P, Radio_P, Debug_P>:: 00456 print_ring_() 00457 { 00458 // print ring and identifiers 00459 uint16_t i; 00460 00461 debug().debug( "EschenauerGligorAlgorithm: Keyring (Node %i)\n\n", radio().id() ); 00462 00463 for(i=0; i< RING_SIZE + NEIGHBOUR_COUNT; i++) 00464 { 00465 uint16_t j; 00466 uint8_t ident[2]; 00467 uint8_t key[16]; 00468 00469 memcpy( ident, identifiers + i * 2, 2 ); 00470 00471 // do not display blacklisted or unused keys! 00472 if( *( ident ) != 0xff || *( ident + 1 ) != 0xff ) 00473 { 00474 if( i < RING_SIZE ) 00475 memcpy( key, keys + i * 16, 16 ); 00476 else 00477 memcpy( key, backup_keys + ( i - RING_SIZE ) * 16, 16 ); 00478 00479 debug().debug( "Nr %d: 0x", i ); 00480 debug().debug( "%02x%02x", *( ident + 1 ), *( ident ) ); 00481 debug().debug( " => " ); 00482 for(j=0; j<16; j++){ 00483 debug().debug( "%02x", *( key + j ) ); 00484 } 00485 debug().debug( "\n" ); 00486 } 00487 } 00488 debug().debug( "\n" ); 00489 } 00490 // ----------------------------------------------------------------------- 00491 template<typename OsModel_P, 00492 typename Routing_P, 00493 typename NodeidIntMap_P, 00494 typename Radio_P, 00495 typename Debug_P> 00496 void 00497 EschenauerGligorAlgorithm<OsModel_P, Routing_P, NodeidIntMap_P, Radio_P, Debug_P>:: 00498 print_neighbours_() 00499 { 00500 // print node_id, ring and identifiers 00501 debug().debug( "EschenauerGligorAlgorithm: Neighbours (Node %i)\n\n", radio().id() ); 00502 00503 for( MapTypeIterator it = neighbour_map_.begin(); it != neighbour_map_.end(); ++it ) 00504 { 00505 uint16_t i; 00506 uint8_t ident[2]; 00507 uint8_t key[16]; 00508 00509 memcpy( ident, identifiers + it->second * 2, 2 ); 00510 00511 if( it->second < RING_SIZE ) 00512 memcpy( key, keys + it->second * 16, 16 ); 00513 else 00514 memcpy( key, backup_keys + ( it->second - RING_SIZE ) * 16, 16 ); 00515 00516 debug().debug( "Node %i: 0x", it->first ); 00517 debug().debug( "%02x%02x", *( ident + 1 ), *( ident ) ); 00518 debug().debug( " => " ); 00519 for(i=0; i<16; i++){ 00520 debug().debug( "%02x", *( key + i ) ); 00521 } 00522 debug().debug( "\n" ); 00523 } 00524 00525 debug().debug( "\n" ); 00526 } 00527 // ----------------------------------------------------------------------- 00528 template<typename OsModel_P, 00529 typename Routing_P, 00530 typename NodeidIntMap_P, 00531 typename Radio_P, 00532 typename Debug_P> 00533 void 00534 EschenauerGligorAlgorithm<OsModel_P, Routing_P, NodeidIntMap_P, Radio_P, Debug_P>:: 00535 timer_elapsed_( void* userdata ) 00536 { 00537 #ifdef DEBUG_EG 00538 debug().debug( "EschenauerGligorAlgorithm: Execute TimerElapsed (Node %i)\n", radio().id() ); 00539 #endif 00540 millis_t time = random_work_period_(); 00541 #ifdef DEBUG_EG 00542 debug().debug( "EschenauerGligorAlgorithm: Using %ims as new Timersetting ", time ); 00543 debug().debug( "(Node %i)\n", radio().id() ); 00544 #endif 00545 00546 send_identifier_list_(); 00547 timer().template set_timer<self_type, &self_type::timer_elapsed_>( time, this, 0 ); 00548 } 00549 // ----------------------------------------------------------------------- 00550 template<typename OsModel_P, 00551 typename Routing_P, 00552 typename NodeidIntMap_P, 00553 typename Radio_P, 00554 typename Debug_P> 00555 void 00556 EschenauerGligorAlgorithm<OsModel_P, Routing_P, NodeidIntMap_P, Radio_P, Debug_P>:: 00557 process_exchange_identifiers_( node_id_t from, Message *message ) 00558 { 00559 uint16_t i; 00560 uint16_t j; 00561 uint8_t found = 0; 00562 uint8_t own[2]; 00563 for( i=0; i < ( message->payload_size() / 2 ); i++ ) 00564 { 00565 uint8_t *foreign = (uint8_t*)( message->payload() + i * 2 ); 00566 00567 // now check whether this identifier is in our list 00568 for( j=0; j < RING_SIZE + NEIGHBOUR_COUNT; j++ ) 00569 { 00570 memcpy( own, identifiers + j * 2, 2 ); 00571 00572 if( *own == *foreign && *( own + 1 ) == *( foreign + 1 ) ) 00573 { 00574 // do not use blacklisted keys (identifier set to 0xffff) 00575 if( *own != 0xff || *( own + 1 ) != 0xff ) 00576 { 00577 found = 1; 00578 break; 00579 } 00580 } 00581 } 00582 if( found ) 00583 break; 00584 } 00585 00586 if( found ) 00587 { 00588 #ifdef DEBUG_EG 00589 debug().debug( "EschenauerGligorAlgorithm: Found common identifier to %u: 0x", message->node_id() ); 00590 debug().debug( "%02x%02x (Node %i)\n", *( own + 1 ), *( own ), radio().id() ); 00591 #endif 00592 // update the used key 00593 neighbour_map_[message->node_id()] = j; 00594 00595 #ifdef DEBUG_EG 00596 print_neighbours_(); 00597 #endif 00598 00599 #ifdef SHAWN 00600 debug().current_time(); 00601 #endif 00602 00603 } 00604 else 00605 { 00606 #ifdef DEBUG_EG 00607 debug().debug( "EschenauerGligorAlgorithm: No common identifier found to %u (Node %i)\n", message->node_id(), radio().id() ); 00608 #endif 00609 00610 send_neighbour_list_( message->node_id() ); 00611 } 00612 } 00613 // ----------------------------------------------------------------------- 00614 template<typename OsModel_P, 00615 typename Routing_P, 00616 typename NodeidIntMap_P, 00617 typename Radio_P, 00618 typename Debug_P> 00619 void 00620 EschenauerGligorAlgorithm<OsModel_P, Routing_P, NodeidIntMap_P, Radio_P, Debug_P>:: 00621 process_encrypted_message_( node_id_t from, Message *message ) 00622 { 00623 MapTypeIterator it = neighbour_map_.find( from ); 00624 00625 if( it != neighbour_map_.end() ) 00626 { 00627 uint16_t offset = it->second; 00628 uint8_t key[16]; 00629 00630 if( offset < RING_SIZE ) 00631 memcpy( key, keys + offset * 16, 16 ); 00632 else 00633 memcpy( key, backup_keys + ( offset - RING_SIZE ) * 16, 16 ); 00634 00635 uint16_t payload_size = message->payload_size(); 00636 uint8_t deciphered[ payload_size ]; 00637 00638 // decrypt it 00639 crypto_handler_.key_setup( (uint8_t*)key ); 00640 crypto_handler_.decrypt( message->payload(), deciphered, payload_size ); 00641 00642 // the message has not reached its destination yet 00643 if( message->dest_id() != radio().id() ) 00644 { 00645 #ifdef DEBUG_EG 00646 debug().debug( "EschenauerGligorAlgorithm: Received Message for Node %i - Forwarding Now... (Node %i)\n", message->dest_id(), radio().id() ); 00647 #endif 00648 00649 RoutingTable *table = routing_->routing_table(); 00650 RoutingTableIterator it = table->find( message->dest_id() ); 00651 if( it != table->end() && it->second.next_hop != radio().NULL_NODE_ID ) 00652 { 00653 MapTypeIterator itt = neighbour_map_.find( it->second.next_hop ); 00654 if( itt != neighbour_map_.end() ) 00655 { 00656 offset = itt->second; 00657 00658 if( offset < RING_SIZE ) 00659 memcpy( key, keys + offset * 16, 16 ); 00660 else 00661 memcpy( key, backup_keys + ( offset - RING_SIZE ) * 16, 16 ); 00662 00663 // encrypt it 00664 crypto_handler_.key_setup( (uint8_t*)key ); 00665 crypto_handler_.encrypt( deciphered, deciphered, payload_size ); 00666 message->set_payload( payload_size, deciphered ); 00667 00668 routing_->send( it->second.next_hop, message->buffer_size(), (uint8_t*)message ); 00669 } 00670 } 00671 } 00672 // the message has reached its destination 00673 else 00674 { 00675 #ifdef DEBUG_EG 00676 debug().debug( "EschenauerGligorAlgorithm: Received Message from Node %i (Node %i)\n", message->node_id(), radio().id() ); 00677 #endif 00678 00679 notify_receivers( message->node_id(), payload_size, deciphered ); 00680 } 00681 } 00682 } 00683 // ----------------------------------------------------------------------- 00684 template<typename OsModel_P, 00685 typename Routing_P, 00686 typename NodeidIntMap_P, 00687 typename Radio_P, 00688 typename Debug_P> 00689 void 00690 EschenauerGligorAlgorithm<OsModel_P, Routing_P, NodeidIntMap_P, Radio_P, Debug_P>:: 00691 send_neighbour_list_( node_id_t destination ) 00692 { 00693 uint8_t i = 0; 00694 00695 Message message; 00696 message.set_node_id( radio().id() ); 00697 00698 message.set_msg_id( NEIGHBOUR_LIST_1 ); 00699 node_id_t temp[ neighbour_map_.size() ]; 00700 00701 for( MapTypeIterator it = neighbour_map_.begin(); it != neighbour_map_.end(); ++it ) 00702 { 00703 temp[i] = it->first; 00704 i++; 00705 } 00706 00707 message.set_seq_nr( 1 ); 00708 message.set_payload( (size_t)( i * sizeof( node_id_t ) ), ( block_data_t *)temp ); 00709 00710 if( i > 0 ) 00711 { 00712 #ifdef DEBUG_EG 00713 debug().debug( "EschenauerGligorAlgorithm: Sending Neighbour-List (Node %i)\n", radio().id() ); 00714 #endif 00715 00716 routing_->send( destination, message.buffer_size(), ( uint8_t* )&message ); 00717 } 00718 } 00719 // ----------------------------------------------------------------------- 00720 template<typename OsModel_P, 00721 typename Routing_P, 00722 typename NodeidIntMap_P, 00723 typename Radio_P, 00724 typename Debug_P> 00725 void 00726 EschenauerGligorAlgorithm<OsModel_P, Routing_P, NodeidIntMap_P, Radio_P, Debug_P>:: 00727 process_neighbour_list_( node_id_t from, Message *message, uint8_t mode ) 00728 { 00729 if( mode == 1 ) 00730 { 00731 uint8_t size = message->payload_size() / sizeof( node_id_t ); 00732 uint8_t i; 00733 uint8_t k = 0; 00734 uint16_t candidate = 0xffff; 00735 uint16_t last = 0; 00736 uint8_t flag = 0; 00737 00738 while( k < size ) 00739 { 00740 // this loop basically "sorts" the neighbour list 00741 for( i = 0; i < size; i++ ) 00742 { 00743 uint8_t *bla = (uint8_t *)( message->payload() + i * sizeof( node_id_t ) ); 00744 node_id_t temp; 00745 memcpy( &temp, bla, sizeof( node_id_t ) ); 00746 00747 if( temp < candidate && temp >= last ) 00748 candidate = temp; 00749 } 00750 last = candidate + 1; 00751 flag = 0; 00752 00753 for( MapTypeIterator it = neighbour_map_.begin(); it != neighbour_map_.end(); ++it ) 00754 { 00755 if( candidate == it->first ) 00756 { 00757 flag = 1; 00758 break; 00759 } 00760 } 00761 if( flag ) break; 00762 k++; 00763 } 00764 00765 // if candidate is != 0xffff it refers to the first common neighbour 00766 if( candidate != 0xffff && flag ) 00767 { 00768 #ifdef DEBUG_EG 00769 debug().debug( "EschenauerGligorAlgorithm: Found common Neighbour to Node %i: %i (Node %i)\n", message->node_id(), candidate, radio().id() ); 00770 #endif 00771 00772 key_proposal_( candidate, candidate, from ); 00773 } 00774 // no common neighbour could be found -> ask neighbours for help! 00775 else 00776 { 00777 send_neighbour_request_( from ); 00778 } 00779 } 00780 // mode is set to 2 00781 else 00782 { 00783 node_id_t *container = ( node_id_t* )message->payload(); 00784 node_id_t destination = *container; 00785 00786 node_id_t via = message->node_id(); 00787 00788 uint8_t size = message->payload_size() / sizeof( node_id_t ); 00789 uint8_t i; 00790 uint8_t k = 0; 00791 uint16_t candidate = 0xffff; 00792 uint16_t last = 0; 00793 uint8_t flag = 0; 00794 00795 container++; 00796 size--; 00797 00798 while( k < size ) 00799 { 00800 // this loop basically "sorts" the neighbour list 00801 for( i = 0; i < size; i++ ) 00802 { 00803 uint8_t *bla = (uint8_t *)( message->payload() + i * sizeof( node_id_t ) ); 00804 node_id_t temp; 00805 memcpy( &temp, bla, sizeof( node_id_t ) ); 00806 00807 if( temp < candidate && temp >= last ) 00808 candidate = temp; 00809 } 00810 last = candidate + 1; 00811 flag = 0; 00812 00813 for( MapTypeIterator it = neighbour_map_.begin(); it != neighbour_map_.end(); ++it ) 00814 { 00815 if( candidate == it->first ) 00816 { 00817 flag = 1; 00818 break; 00819 } 00820 } 00821 if( flag ) break; 00822 k++; 00823 } 00824 00825 // if candidate is != 0xffff it refers to the first common neighbour 00826 if( candidate != 0xffff && flag ) 00827 { 00828 #ifdef DEBUG_EG 00829 debug().debug( "EschenauerGligorAlgorithm: Found common Neighbour to Node %i via %i: %i (Node %i)\n", destination, via, candidate, radio().id() ); 00830 #endif 00831 00832 key_proposal_( candidate, via, destination ); 00833 } 00834 } 00835 } 00836 // ----------------------------------------------------------------------- 00837 template<typename OsModel_P, 00838 typename Routing_P, 00839 typename NodeidIntMap_P, 00840 typename Radio_P, 00841 typename Debug_P> 00842 void 00843 EschenauerGligorAlgorithm<OsModel_P, Routing_P, NodeidIntMap_P, Radio_P, Debug_P>:: 00844 key_proposal_( node_id_t via, node_id_t via2, node_id_t destination ) 00845 { 00846 // get first nonassigned key! 00847 uint16_t i; 00848 uint8_t flag = 0; 00849 for( i = 0; i < RING_SIZE + NEIGHBOUR_COUNT; i++ ) 00850 { 00851 uint8_t ident[2]; 00852 memcpy( ident, identifiers + i * 2, 2 ); 00853 00854 // do not test blacklisted or unused keys! 00855 if( *( ident ) != 0xff || *( ident + 1 ) != 0xff ) 00856 { 00857 flag = 1; 00858 for( MapTypeIterator it = neighbour_map_.begin(); it != neighbour_map_.end(); ++it ) 00859 { 00860 if( it->second == i ) 00861 flag = 0; 00862 } 00863 00864 if( flag ) 00865 break; 00866 } 00867 } 00868 00869 if( flag ) 00870 { 00871 send_key_proposal_( via, via2, destination, i ); 00872 } 00873 } 00874 // ----------------------------------------------------------------------- 00875 template<typename OsModel_P, 00876 typename Routing_P, 00877 typename NodeidIntMap_P, 00878 typename Radio_P, 00879 typename Debug_P> 00880 void 00881 EschenauerGligorAlgorithm<OsModel_P, Routing_P, NodeidIntMap_P, Radio_P, Debug_P>:: 00882 send_key_proposal_( node_id_t via, node_id_t via2, node_id_t destination, uint16_t offset ) 00883 { 00884 #ifdef DEBUG_EG 00885 debug().debug( "EschenauerGligorAlgorithm: Found unused Key at Offset %i (Node %i)\n", offset, radio().id() ); 00886 #endif 00887 00888 #ifdef DEBUG_EG 00889 debug().debug( "EschenauerGligorAlgorithm: Sending Key Proposal to Node %i via %i (Node %i)\n", destination, via, radio().id() ); 00890 #endif 00891 00892 Message message; 00893 message.set_msg_id( KEY_PROPOSAL ); 00894 message.set_node_id( radio().id() ); 00895 message.set_dest_id( destination ); 00896 00897 message.set_seq_nr( 1 ); 00898 00899 // get identifier and key 00900 uint8_t data[ 18 ]; 00901 memcpy( data, identifiers + offset * 2, 2 ); 00902 00903 if( offset < RING_SIZE ) 00904 memcpy( data + 2, keys + offset * 16, 16 ); 00905 else 00906 memcpy( data + 2, backup_keys + ( offset - RING_SIZE ) * 16, 16 ); 00907 00908 RoutingTable *table = routing_->routing_table(); 00909 RoutingTableIterator it = table->find( via ); 00910 00911 if( it != table->end() ) 00912 { 00913 // AES has fixed size 16 Bytes Blocks 00914 uint16_t length_aes = ( 18 / 16 + 1 ) * 16; 00915 00916 MapTypeIterator itt = neighbour_map_.find( via ); 00917 00918 print_neighbours_(); 00919 00920 if( itt != neighbour_map_.end() ) 00921 { 00922 uint16_t offset = itt->second; 00923 uint8_t key[16]; 00924 00925 if( offset < RING_SIZE ) 00926 memcpy( key, keys + offset * 16, 16 ); 00927 else 00928 memcpy( key, backup_keys + ( offset - RING_SIZE ) * 16, 16 ); 00929 00930 uint8_t encrypted[ length_aes + sizeof( node_id_t ) ]; 00931 00932 // encrypt it 00933 crypto_handler_.key_setup( key ); 00934 crypto_handler_.encrypt( data, encrypted, length_aes ); 00935 00936 // store via2 in the payload 00937 memcpy( encrypted + length_aes, ( uint8_t* )&via2, sizeof( node_id_t ) ); 00938 00939 message.set_payload( length_aes + sizeof( node_id_t ), encrypted ); 00940 routing_->send( via, message.buffer_size(), (uint8_t*)&message ); 00941 } 00942 } 00943 } 00944 // ----------------------------------------------------------------------- 00945 template<typename OsModel_P, 00946 typename Routing_P, 00947 typename NodeidIntMap_P, 00948 typename Radio_P, 00949 typename Debug_P> 00950 void 00951 EschenauerGligorAlgorithm<OsModel_P, Routing_P, NodeidIntMap_P, Radio_P, Debug_P>:: 00952 process_key_proposal_( node_id_t from, Message *message ) 00953 { 00954 MapTypeIterator it = neighbour_map_.find( from ); 00955 00956 if( it != neighbour_map_.end() ) 00957 { 00958 uint16_t offset = it->second; 00959 uint8_t key[16]; 00960 00961 if( offset < RING_SIZE ) 00962 memcpy( key, keys + offset * 16, 16 ); 00963 else 00964 memcpy( key, backup_keys + ( offset - RING_SIZE ) * 16, 16 ); 00965 00966 uint16_t payload_size = message->payload_size() - sizeof( node_id_t ); 00967 uint8_t deciphered[ payload_size + sizeof( node_id_t ) ]; 00968 00969 // decrypt it 00970 crypto_handler_.key_setup( (uint8_t*)key ); 00971 crypto_handler_.decrypt( message->payload(), deciphered, payload_size ); 00972 00973 node_id_t *via = ( node_id_t* )( message->payload() + payload_size ); 00974 00975 // the message has not reached its destination yet 00976 if( message->dest_id() != radio().id() ) 00977 { 00978 #ifdef DEBUG_EG 00979 debug().debug( "EschenauerGligorAlgorithm: Received Key Proposal for Node %i - Forwarding Now... (Node %i)\n", message->dest_id(), radio().id() ); 00980 #endif 00981 00982 node_id_t next; 00983 00984 if( radio().id() == *via ){ 00985 next = message->dest_id(); 00986 if( from != message->node_id() ) 00987 *via = from; 00988 } 00989 else 00990 { 00991 next = *via; 00992 } 00993 00994 RoutingTable *table = routing_->routing_table(); 00995 RoutingTableIterator it = table->find( next ); 00996 if( it != table->end() && it->second.next_hop != radio().NULL_NODE_ID ) 00997 { 00998 MapTypeIterator itt = neighbour_map_.find( it->second.next_hop ); 00999 if( itt != neighbour_map_.end() ) 01000 { 01001 offset = itt->second; 01002 01003 if( offset < RING_SIZE ) 01004 memcpy( key, keys + offset * 16, 16 ); 01005 else 01006 memcpy( key, backup_keys + ( offset - RING_SIZE ) * 16, 16 ); 01007 01008 // encrypt it 01009 crypto_handler_.key_setup( (uint8_t*)key ); 01010 crypto_handler_.encrypt( deciphered, deciphered, payload_size ); 01011 01012 // store via in the payload 01013 memcpy( deciphered + payload_size, ( uint8_t* )via, sizeof( node_id_t ) ); 01014 01015 message->set_payload( payload_size + sizeof( node_id_t ), deciphered ); 01016 01017 routing_->send( it->second.next_hop, message->buffer_size(), (uint8_t*)message ); 01018 } 01019 } 01020 } 01021 // the message has reached its destination 01022 else 01023 { 01024 #ifdef DEBUG_EG 01025 debug().debug( "EschenauerGligorAlgorithm: Received Key Proposal from Node %i (Node %i)\n", message->node_id(), radio().id() ); 01026 #endif 01027 01028 // get first nonassigned key! 01029 uint16_t i; 01030 uint8_t flag = 0; 01031 uint8_t ident[2]; 01032 for(i=0; i< RING_SIZE + NEIGHBOUR_COUNT; i++) 01033 { 01034 memcpy( ident, identifiers + i * 2, 2 ); 01035 01036 // do not test blacklisted or unused keys! 01037 if( *( ident ) != 0xff || *( ident + 1 ) != 0xff ) 01038 { 01039 flag = 1; 01040 for( MapTypeIterator it = neighbour_map_.begin(); it != neighbour_map_.end(); ++it ) 01041 { 01042 if( it->second == i ) 01043 flag = 0; 01044 } 01045 if( flag ) 01046 break; 01047 } 01048 } 01049 01050 if( flag ) 01051 { 01052 uint16_t own_ident, foreign_ident; 01053 memcpy( &own_ident, ident, 2 ); 01054 memcpy( &foreign_ident, deciphered, 2 ); 01055 01056 if( own_ident < foreign_ident ) 01057 { 01058 send_key_proposal_( from, *via, message->node_id(), i ); 01059 } 01060 else 01061 { 01062 store_new_key_( deciphered ); 01063 } 01064 } 01065 else 01066 { 01067 store_new_key_( deciphered ); 01068 } 01069 } 01070 } 01071 } 01072 // ----------------------------------------------------------------------- 01073 template<typename OsModel_P, 01074 typename Routing_P, 01075 typename NodeidIntMap_P, 01076 typename Radio_P, 01077 typename Debug_P> 01078 void 01079 EschenauerGligorAlgorithm<OsModel_P, Routing_P, NodeidIntMap_P, Radio_P, Debug_P>:: 01080 store_new_key_( uint8_t *data ) 01081 { 01082 // check whether this key has already been stored - this case occurs 01083 // because of the random waiting times between distributing the identifier lists 01084 uint16_t i; 01085 uint8_t flag = 1; 01086 uint8_t ident[2]; 01087 01088 for( i = RING_SIZE; i < RING_SIZE + NEIGHBOUR_COUNT; i++ ) 01089 { 01090 memcpy( ident, identifiers + i * 2, 2 ); 01091 01092 if( *( ident ) == *( data ) && *( ident + 1 ) == *( data + 1 ) ) 01093 { 01094 flag = 0; 01095 break; 01096 } 01097 } 01098 01099 if( flag ) 01100 { 01101 // get first unused or blacklisted key! 01102 flag = 0; 01103 01104 for( i = RING_SIZE; i < RING_SIZE + NEIGHBOUR_COUNT; i++ ) 01105 { 01106 memcpy( ident, identifiers + i * 2, 2 ); 01107 01108 if( *( ident ) == 0xff && *( ident + 1 ) == 0xff ) 01109 { 01110 flag = 1; 01111 break; 01112 } 01113 } 01114 01115 if( flag ) 01116 { 01117 #ifdef DEBUG_EG 01118 debug().debug( "EschenauerGligorAlgorithm: Added new Key to the Ring (Node %i)\n", radio().id() ); 01119 #endif 01120 01121 memcpy( identifiers + i * 2, data, 2 ); 01122 memcpy( backup_keys + ( i - RING_SIZE ) * 16, data + 2, 16 ); 01123 01124 send_identifier_list_(); 01125 } 01126 } 01127 } 01128 // ----------------------------------------------------------------------- 01129 template<typename OsModel_P, 01130 typename Routing_P, 01131 typename NodeidIntMap_P, 01132 typename Radio_P, 01133 typename Debug_P> 01134 void 01135 EschenauerGligorAlgorithm<OsModel_P, Routing_P, NodeidIntMap_P, Radio_P, Debug_P>:: 01136 send_neighbour_request_( node_id_t destination ) 01137 { 01138 #ifdef DEBUG_EG 01139 debug().debug( "EschenauerGligorAlgorithm: Sending Neighbour-Request (Node %i)\n", radio().id() ); 01140 #endif 01141 01142 Message message; 01143 message.set_msg_id( NEIGHBOUR_REQUEST ); 01144 message.set_node_id( radio().id() ); 01145 message.set_seq_nr( 2 ); 01146 message.set_payload( (size_t)( sizeof( node_id_t ) ), (block_data_t*)&destination ); 01147 01148 radio().send( radio().BROADCAST_ADDRESS, message.buffer_size(), (block_data_t*)&message ); 01149 } 01150 // ----------------------------------------------------------------------- 01151 template<typename OsModel_P, 01152 typename Routing_P, 01153 typename NodeidIntMap_P, 01154 typename Radio_P, 01155 typename Debug_P> 01156 void 01157 EschenauerGligorAlgorithm<OsModel_P, Routing_P, NodeidIntMap_P, Radio_P, Debug_P>:: 01158 process_neighbour_request_( node_id_t from, Message *message ) 01159 { 01160 node_id_t *destination = ( node_id_t* )message->payload(); 01161 request_from_ = from; 01162 request_dest_ = *destination; 01163 01164 millis_t time = ( random_work_period_() - MIN_WORK_TIME * 1000 ) / 30; 01165 timer().template set_timer<self_type, &self_type::work_neighbour_request_>( time, this, 0 ); 01166 } 01167 // ----------------------------------------------------------------------- 01168 template<typename OsModel_P, 01169 typename Routing_P, 01170 typename NodeidIntMap_P, 01171 typename Radio_P, 01172 typename Debug_P> 01173 void 01174 EschenauerGligorAlgorithm<OsModel_P, Routing_P, NodeidIntMap_P, Radio_P, Debug_P>:: 01175 work_neighbour_request_( void *userdata ) 01176 { 01177 // check whether we have an encrypted link to the sending node 01178 MapTypeIterator it = neighbour_map_.find( request_from_ ); 01179 if( it != neighbour_map_.end() ) 01180 { 01181 uint8_t i = 1; 01182 01183 Message message; 01184 message.set_node_id( radio().id() ); 01185 01186 message.set_msg_id( NEIGHBOUR_LIST_2 ); 01187 node_id_t temp[ neighbour_map_.size() + 1 ]; 01188 01189 temp[0] = request_from_; 01190 01191 // build a list of all the neighbours we have an encrypted link to 01192 for( MapTypeIterator it = neighbour_map_.begin(); it != neighbour_map_.end(); ++it ) 01193 { 01194 if( it-> first != request_from_ ) 01195 { 01196 temp[i] = it->first; 01197 i++; 01198 } 01199 } 01200 01201 message.set_seq_nr( 1 ); 01202 message.set_payload( (size_t)( i * sizeof( node_id_t ) ), ( block_data_t* )temp ); 01203 01204 if( i > 1 ) 01205 { 01206 #ifdef DEBUG_EG 01207 debug().debug( "EschenauerGligorAlgorithm: Sending Neighbour-List Depth 2 (Node %i)\n", radio().id() ); 01208 #endif 01209 01210 routing_->send( request_dest_, message.buffer_size(), (uint8_t*)&message ); 01211 } 01212 } 01213 } 01214 } 01215 #endif
