Τεχνικές ασφαλείας σε ασύρματα δίκτυα αισθητήρων με έμφαση στην μείωση κόστους σε σχήματα διαχείρισης κλειδιών με χρήση τοπολογικών μεθόδων

Abstract

Wireless Sensor Networks are an emerging type of industry-targeted networks that typically consist of a number of spatially distributed nodes, usually equipped with environmental sensors, working together to execute a particular application. As the utility of WSN becomes more apparent in recent years, and new types of applications are being implemented in sensitive application areas, the necessity of securing these networks, and especially inter-node communications within them, from interception and injection of malicious data is becoming apparent.This dissertation focuces mainly on the study of key management schemes, and specifically, the minimization of network overhead for key management processes when a group communication model-supporting scheme is used, in which each node possesses cryptographic material that enables it to communicate directly with all other nodes in the network.The Logical Key Hierarchy scheme is used as a basis. In this scheme, key management is performed by a Key Server. There exists a network key, shared between all nodes in the network, and which can be used to communicate between any two nodes. To reduce the cost of changing it, a hierarchy of keys, in the form of a tree, is used.As an initial step in the dissertation, an encrypted image transmission application is implemented on network of TelosB nodes, running the Contiki operating system. Key management was implemented using the S2RP scheme, which is based on LKH. The performance of the encrypted image transmission was tested and compared to unencrypted transmission. Additionally, measurements were taken for the performance of the S2RP rekeying procedures.The results of the encrypted image transmission showed that encryption of data transmissions, even for a demanding application like image transmission, is quite applicable, despite the additional overhead. Rekeying procedure measurements showed that such key management schemes are indeed applicable in a WSN, but the overhead is non-negligible and must be taken into account in the design of the network, and it may be necessary to regulate network transmission parameters, such as the minimum transmission interval, to minimize the losses in the critical rekeying packets, while keeping the execution time of these processes within reasonable limits.As a next step in the thesis, methods of minimizing the network overhead for LKH key management schemes were studied and implemented. Method of creation of efficient key hierarchies, that lead to rekeyings with minimal network transmissions were explored. The approach that was followed was topological, or topology-aware, i.e. key structures correspond to the network connection graph. The methods are collectively named TALK: Topology-Aware LKH Key ManagementThe algorithms that were developed are logically split into two sections. The first is finding the optimal node to assume the Key Server role. This is done by locally collecting data on the network topology at each node, and calculating at each candidate node some suitability metrics. The second part of the algorithms is the very creation of the key tree on the Key Server, using the knowledge of the network topology received during the previous step.Measurements and simulations that show the applicability of the algorithms, as well as the improvement of the network overhead in relation to the plain, random creation of key trees, were performed.In the next chapter, the possibility to further reduce the rekeying overhead is studied, using two nested levels of LKH key hierarchies. At the lower level, the nodes of the network are assigned into End Clusters, each having an End Cluster Head. Cluster heads of this level comprise the Super Cluster, which has a Super Cluster Head, that acts as general network coordinator. A separate LKH tree is used in each cluster. The proposed Key Management Scheme is named CHAT: clustered hierarchical key management for Wireless Sensor Networks using network topology.In the basic scheme, non-ECH nodes share cryptographic material only with nodes in their own their EC, and can communicate directly with them. Inter-EC communication is routed through the corresponding ECHs, who, being able to communicate with each otherand, take on the role of message re-encryption . In relation to a real group communication model, there is some overhead on inter-cluster communication, but the rekeying cost is heavily reduced, as key changes no longer concern the whole network, but only parts of it.Using the TALK methods as a basis, the SCH and first ECH is selected using the TALK Key Server selection procedure. The remaining ECHs are selected using an iterative algorithm, whereby the most suitable of the remaining candidates is chosen at each step. The general idea behind the selection criteria is preference of candidates with several nodes in their neighborhood, and who also are not near any already selected ECHs. Having all needed ECHs selected, the remaining nodes are assigned to ECs, using an algorithm which yields coherent ECs and minimum hops assignments.Two variants of the basic scheme are also presented: The first is the introduction of a network-wide encryption key, which is shared between all network nodes, allowing the use of a group communication model, such as a simple LKH, and overhead-free inter-cluster communication, at the expense of an increase in the rekeying cost. The second variation in the basic scheme is the introduction of overlap between the ECs. This is a compromise between the previous variants, having more flexibility than the basic scheme in data transmissions, and a rekeying cost that is greater than in the basic scheme, but lower than using a network-wide key.Simulations were performed for the validation of the schemes' performance. These show that each variant has different rekeyign and data traffic cost characteristics, and thus each one is proposed for different types of applications: The basic scheme presents minimal key change costs, which do not increase much with the network size. However it also exhibits a non-negligible increase in inter-cluster communication costs. Therefore, its used is recommended for applications the traffic patterns of which can match the scheme's clusters. The variant with the network-wide key does not incur an overhead for communication costs. The rekeying cost is far greater than the basic scheme, but much less than the simple LKH application, and even the TALK scheme. Thus, it is proposed as a generic solution for applications which have traffic between any nodes, but also need a fairly low rekeying cost for a group communication scheme. Finally, the cluster overlapping variant presents very low rekeying cost for large networks, approaching that of the basic scheme, while offering much greater flexibility in communication, while the communication overhead due to the non-optimal routing of the packets can be replaced by routing through the minimum path and performing additional re-encryptions as needed. It is recommended for very large networks with any communication needs.

Τα Ασύρματα Δίκτυα Αισθητήρων είναι ένας τύπος δικτύων που απαρτίζονται εν γένει από πληθώρα χωρικά κατανεμημένων κόμβων, συνήθως εφοδιασμένων με περιβαλλοντικούς αισθητήρες, που λειτουργούν συνεργατικά με στόχο την εκπλήρωση κάποιας συγκεκριμένης εφαρμογής. Καθώς η χρησιμότητα των ΑΔΑ γίνεται όλο και πιο εμφανής, με νέους τύπους εφαρμογών να υλοποιούνται σε αυτά σε ευαίσθητους τομείς, αναδεικνύεται η ανάγκη της διασφάλισης των δικτύων αυτών από υποκλοπές και εισαγωγή ψευδών δεδομένων. Στη διατριβή αυτή εξετάζεται κατά κύριο λόγο η διαχείριση κλειδιών, με βασικό στόχο την επίτευξη της κατά το δυνατόν μικρότερης επιβάρυνσης του δικτύου για τις διαδικασίες διαχείρισης κλειδιών, όταν χρησιμοποιείται μοντέλο επικοινωνίας ομάδας, στο οποίο κάθε κόμβος διαθέτει δύναται να επικοινωνήσει άμεσα, από κρυπτογραφικής άποψης, με όλους τους υπόλοιπους κόμβους του δικτύου.Σαν βάση χρησιμοποιείται το σχήμα Logical Key Hierarchy. Σε αυτό η διαχείριση κλειδιών πραγματοποιείται από έναν Διακομιστή Κλειδιών, ενώ χρησιμοποιείται ένα κλειδί δικτύου, το οποίο μοιράζεται σε όλους τους κόμβους του δικτύου. Για την μείωση του κόστους για την αλλαγή του τελευταίου, χρησιμοποιείται επιπλέον μια ιεραρχία κλειδιών, με μορφή δέντρου.Σαν πρώτο βήμα στη διατριβή γίνεται υλοποίηση εφαρμογής κρυπτογραφημένης μετάδοσης εικόνας μέσα από ένα δίκτυο κόμβων TelosB και πάνω από το λειτουργικό σύστημα Contiki. Υλοποιήθηκε διαχείριση κλειδιών μέσω του σχήματος S2RP, βασισμένο στο LKH. Πάνω σε αυτά ελέγχθηκε η απόδοση της κρυπτογραφημένης μετάδοσης εικόνων και συγκρίθηκε με τη μη κρυπτογραφημένη μετάδοση. Επιπλέον έγιναν μετρήσεις στην απόδοση των διαδικασιών αλλαγής κλειδιών του S2RP.Τα αποτελέσματα της κρυπτογραφημένης μετάδοσης εικόνας έδειξαν πως η κρυπτογράφηση των δικτυακών μεταδόσεων στα ΑΔΑ, παρά την εισαγωγή κάποιας επιβάρυνσης σε σχέση με τις απλές μεταδόσεις, είναι αρκετά εφαρμόσιμη, ακόμα και για απαιτητικές εφαρμογές, όπως η μετάδοση είκόνων. Οι μετρήσεις των διαδικασιών αλλαγής κλειδιών έδειξαν την εφαρμοσιμότητα του σχήματος σε ΑΔΑ, αλλά με μη αμελητέα επιβάρυνση, που πρέπει να ληφθεί σοβαρά υπόψη στη σχεδίαση του δικτύου, ενώ πιθανόν να είναι αναγκαία και η ρύθμιση των παραμέτρων της δικτυακής μετάδοσης, όπως το ελάχιστο μεσοδιάστημα μεταξύ μεταδόσεων, ώστε να ελαχιστοποιηθούν οι απώλειες στα κρίσιμα πακέτα αλλαγής κλειδιών, κρατώντας παράλληλα το χρόνο εκτέλεσης των διαδικασιών αυτών σε λογικά πλαίσια.Σαν επόμενο βήμα εξετάστηκαν μέθοδοι ελαχιστοποίησης της δικτυακής επιβάρυνσης για χρήση σχημάτων διαχείρισης κλειδιών τύπου LKH. Εξετάστηκαν τρόποι δημιουργίας των ιεραρχιών κλειδιών, που να οδηγούν σε αλλαγές κλειδιών με κατά το δυνατόν μικρή δικτυακή επιβάρυνση. Ακολουθήθηκε τοπολογική προσέγγιση, δηλαδή η δημιουργία δομών κλειδιών που "αντιστοιχούν" στο γράφο σύνδεσης του δικτύου. Οι μέθοδοι αυτοί ονομάζονται συλλογικά TALK: Topology-Aware LKH Key Management.Οι αλγόριθμοι που αναπτύχθηκαν χωρίζονται λογικά σε δυο τμήματα. Το πρώτο είναι η εύρεση του βέλτιστου κόμβου για το ρόλο του Διακομιστή Κλειδιών. Αυτό γίνεται με συλλογή στοιχείων για την τοπολογία του δικτύου σε κάθε κόμβο, και τοπικό υπολογισμό σε κάθε υποψήφιο κόμβο κάποιων μετρικών για την καταλληλότητά του. Δεύτερο τμήμα των αλγορίθμων είναι η ίδια η δημιουργία του δέντρου κλειδιών στον Διακομιστή Κλειδιών, χρησιμοποιώντας τη γνώση της τοπολογίας του δικτύου από το προηγούμενο βήμα.Για την υποστήριξη της μεθοδολογίας πραγματοποιήθηκαν μετρήσεις και εξομοιώσεις που δείχνουν την εφαρμοσιμότητα των αλγορίθμων, καθώς και τη βελτίωση της δικτυακής επιβάρυνσης σε σχέση με την απλή, τυχαία δημιουργία δέντρων κλειδιών.Στη συνέχεια εξετάζονται τρόποι περαιτέρω μείωσης της επιβάρυνσης στις αλλαγές κλειδιών, με χρήση δυο επιπέδων από ιεραρχίες κλειδιών τύπου LKH. Στο χαμηλότερο επίπεδο οι κόμβοι του δικτύου χωρίζονται σε "Εnd clusters", με έναν επικεφαλής η κάθε μια (End Cluster Head). Οι επικεφαλής αυτού του επιπέδου δημιουργούν μια "Super Cluster", με έναν επικεφαλής (Super Cluster Head) ο οποίος λειτουργεί ως γενικός συντονιστής στο δίκτυο. Σε κάθε συστάδα λειτουργεί και διαφορετικό δέντρο LKH. Το Σχήμα που αναπτύχθηκε ονομάζεται CHAT: clustered hierarchical key management for Wireless Sensor Networks using network topology.Στο βασικό σχήμα, οι μη-ECH κόμβοι μοιράζονται κρυπτογραφικό υλικό μόνο με κόμβους της EC τους και μπορούν να επικοινωνήσουν απευθείας με αυτούς. Η διασυσταδική επικοινωνία δρομολογείται μέσω των αντίστοιχων ECH, οι οποίοι ανήκουν στην SC, και μπορούν να επικοινωνήσουν, αναλαμβάνοντας την επανακρυπτογράφηση του μηνύματος. Σε σχέση με ένα πραγματικό μοντέλο επικοινωνίας ομάδας, υπάρχει κάποια επιβάρυνση στην διασυσταδική επικοινωνία, αλλά μειώνεται το κόστος αλλαγής κλειδιών.Χρησιμοποιώντας ως βάση τις μεθόδους του TALK, επιλέγεται ένας κόμβος που θα λειτουργήσει ως SCH και ECH μιας εκ των EC, κατά αντιστοιχία με τον Διακομιστή Κλειδιών στο απλό LKH / TALK. Οι υπόλοιποι ECH επιλέγονται με χρήση ενός επαναληπτικού αλγορίθμου που επιλέγει υποψηφίους με αρκετούς κόμβους στην περιοχή τους, οι οποίοι παράλληλα δε θα είναι κοντά σε ήδη επιλεγμένους ECH. Με επιλεγμένους τους ECH, γίνεται η ανάθεση των υπόλοιπων κόμβων σε ECs, με αλγόριθμο που οδηγεί σε συνεκτικά ECs και αναθέσεις μικρότερης δυνατής απόστασης.Παρουσιάζονται επίσης και δυο παραλλαγές του βασικού σχήματος: Η πρώτη είναι η εισαγωγή ενός καθολικού κλειδιού κρυπτογράφησης, που μοιράζεται σε όλους τους κόμβους του δικτύου, κάτι που επιτρέπει τη χρήση μοντέλου επικοινωνίας ομάδας, όπως στο απλό LKH, και τη διασυσταδική επικοινωνία χωρίς κάποια επιβάρυνση, αντάλλαγμα αύξηση στο κόστος αλλαγής κλειδιών. Δεύτερη παραλλαγή στο βασικό σχήμα είναι η εισαγωγή κάποιας επικάλυψης μεταξύ των ECs. Αυτό αποτελεί συμβιβαστική λύση μεταξύ των προηγούμενων, δίνοντας μεγαλύτερη ευελιξία από το βασικό σχήμα στην επικοινωνία μεταξύ κόμβων, αλλά και κόστος αλλαγής κλειδιών που, παρότι μεγαλύτερο από αυτό του βασικού σχήματος κλιμακώνεται καλύτερα από τη χρήση καθολικού κλειδιού.Η κάθε λύση παρουσιάζει διαφορετικά χαρακτηριστικά κόστους αλλαγής κλειδιών και κίνησης δεδομένων, και προτείνονται για διαφορετικούς τύπους εφαρμογών: Το βασικό σχήμα παρουσιάζει ελάχιστο κόστος αλλαγής κλειδιών, που δεν αυξάνεται ιδιαίτερα με το μέγεθος του δικτύου, αλλά μη μηδαμινή αύξηση στο διασυσταδικό κόστος επικοινωνίας. Έτσι προτείνεται για εφαρμογές των οποίων η κίνηση μπορεί να αντιστοιχηθεί στις συστάδες του σχήματος. Η παραλλαγή με το καθολικό κλειδί δεν παρουσιάζει καμία επιβάρυνση στο επικοινωνιακό κόστος. Το κόστος αλλαγής κλειδιού είναι αρκετά μεγαλύτερο από το βασικό σχήμα, αλλά αρκετά μικρότερο από την απλή εφαρμογή LKH, και ακόμα και από το σχήμα TALK. Έτσι προτείνεται ως γενική λύση, για εφαρμογές με κίνηση μεταξύ οποιωνδήποτε κόμβων, η οποία απαιτεί ένα αρκετά μικρό κόστος αλλαγής κλειδιών για σχήμα με υποστήριξη επικοινωνίας ομάδας. Τέλος, η παραλλαγή με την επικάλυψη συστάδων παρουσιάζει πολύ μικρό κόστος, που προσεγγίζει αυτό του βασικού σχήματος, προσφέροντας ταυτόχρονα και πολύ μεγαλύτερη ευελιξία στην επικοινωνία, ενώ η μειωμένη, σε σχέση με το βασικό σχήμα, επικοινωνιακή επιβάρυνση, λόγω μη βέλτιστης δρομολόγησης των πακέτων, μπορεί να αντικατασταθεί από επιπλέον επανακρυπτογραφήσεις και δρομολόγηση ελάχιστου μονοπατιού. Προτείνεται για αρκετά μεγάλα δίκτυα με οτιδήποτε επικοινωνιακές ανάγκες.