Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/11742
Title: Ασφάλεια δεδομένων σε υλικό με τη χρήση ελλειπτικών καμπυλών binary Edwards
Other Titles: Hardware data security with the use of binary Edwards elliptic curves
Authors: Δημόπουλος, Χαράλαμπος
Keywords: Υλικό
Λογισμικό
Ελλειπτικές καμπύλες
Κυβερνοασφάλεια
Ψηφιακές υπογραφές
Προστασία
Σχεδίαση
Υλοποίηση
Κυβερνοεπίθεση
Κρυπτογραφία
Keywords (translated): Hardware
Software
VLSI
Elliptic curves
FPGA
Cybersecurity
Digital signatures
Side channel attack
Design
Binary Edwards
Protection
Cryptography
Abstract: Αντικείμενο της εργασίας αυτής αποτελεί ένα αρκετά ενδιαφέρον ζήτημα στο χώρο της Κρυπτογραφίας, αυτό της προσπάθειας ανάδειξης πιο αποδοτικών και ασφαλέστερων οικογενειών Ελλειπτικών Καμπυλών καθώς και την πρακτική εφαρμογή αυτών. Υπό αυτό το πρίσμα, η εργασία αυτή καταπιάνεται με την ανάπτυξη ενός Κρυπτογραφικού Συστήματος Ελλειπτικών Καμπυλών βασισμένο στις Καμπύλες Edwards και πιο συ- γκεκριμένα τη δυαδική τους μορφή, δηλαδή τις Binary Edwards Curves. Αρχικά, σε μαθηματικό επίπεδο, γίνεται μια σύγκριση μεταξύ των διαφορετικών οικογενειών καμπυλών με τα αντίστοιχα μειονεκτήματα και πλεονεκτήματα που προσφέρει η καθεμία. Σε σχέση με τις ήδη καθιερω- μένες καμπύλες Weierstrass, οι Καμπύλες Edwards θεωρούνται ολοκληρω- μένες και ομοιόμορφες, καθώς δεν παρουσιάζουν σημεία εξαίρεσης που αποτελούν τρωτό σημείο όσον αφορά την ασφάλεια. Μειονέκτημά τους όμως σε σχέση με τις Weierstrass είναι η απόδοσή τους λόγω των περισ- σότερων πράξεων πεπερασμένων πεδίων που απαιτούν. Σε αυτό το σημείο πρέπει να ληφθεί η σωστή απόφαση όσον αφορά τον τύπο πεπερασμένου πεδίου, καθώς αυτή θα επηρρεάσει σε με- γάλο βαθμό τη μορφή και του υπόλοιπου συστήματος. Υπό αυτό το πρίσμα, μία επιλογή αφορά την εφαρμογή του Κρυπτογραφικού Συστήματος εξο- λοκλήρου σε λογισμικό, προσφέροντας αρκετά μεγάλη ευελιξία με σοβαρό ανίκτυπο όμως την ταχύτητα εκτέλεσης και την ασφάλεια από επιθέσεις τύπου Side Channel Analysis. Η άλλη προσέγγιση είναι μια υλοποίηση ως επί το πλείστον σε υλικό, γεγονός που προσδίδει τις μέγιστες επιδόσεις και ασφάλεια, με αντίκτυπο παρ’όλα αυτά το χρόνο σχεδιασμού και την ανε- λαστικότητα που αναπόφευκτα προσδίδει μία τέτοιου τύπου υλοποίηση. Θέλοντας λοιπόν να προσδώσουμε ταχύτητα στο σύστημά μας προχωρούμε στην επιλογή δυαδικών GF (2 k ) πεδίων αντί των πρώτων GF ( p ) και κατά συνέπεια στην υλοποίησή των πράξεών τους απευθείας σε υλικό, αφού σε αυτά απλουστεύονται κατά μεγάλο βαθμό σχεδιαστικά οι πράξεις αυτές. Έχοντας επίγνωση πλέον οτι στο χαμηλότερο επίπεδο οι πράξεις της πρόσθεσης και του πολλαπλασιασμού σε πεδία GF (2 k ) θα υλοποι- ηθούν σε υλικό, προσπαθούμε να αντλήσουμε όσο το δυνατόν περισσό- τερη ταχύτητα ανά χρόνο σχεδίασης γίνεται. Παρατηρούμε λοιπόν πως στον αλγόριθμο γέννησης και επικύρωσης υπογραφών ECDSA η πιο απαι- τητική ενέργεια είναι η πράξη του Βαθμωτού Πολλαπλασιασμού (Scalar Multiplication). Για αυτόν τον λόγο λαμβάνεται η απόφαση το Κρυπτο- γραφικό Σύστημα να είναι ένα υβρίδιο υλικού-λογισμικού, με την πράξη του Βαθμωτού Πολλαπλασιασμού να πραγματοποιείται σε υλικό και τις υπόλοιπες αλγοριθμικές ενέργειες να τις αναλαμβάνει το λογισμικό. Προχωρώντας προς τον τελικό στόχο την υλοποίηση ενός πολλα- πλασιαστή με ισορροπημένα χαρακτηριστικά όσον αφορά την ταχύτητα v και τον αριθμό των χρησιμοποιούμενων λογικών πυλών, χωρίς όμως να υστερείται προστατευτικών μέτρων απέναντι σε SCA επιθέσεις, εφαρμό- ζουμε μία σειρά από τεχνικές βελτιστοποίησης. Πιο συγκεκριμένα, μετά από μία Data Dependency Graph ανά- λυση, αναμιγνύονται οι GF (2 k ) πράξεις και της Πρόσθεσης και του Διπλα- σιασμού σημείου καμπύλης και παραλληλίζονται ταυτόχρονα σε επίπεδα, δημιουργώντας ένα συμπαγές συνονθύλεμα που αποκρύπτει όσο το δυνα- τόν περισσότερη κρίσιμη πληροφορία καθ’όλη τη διάρκεια εκτέλεσης του Βαθμωτού Πολλαπλασιασμού. Ο πολλαπλασιαστής είναι δομημένος από τρεις ξεχωριστές και ημιαυτόνομες μονάδες που αναλαμβάνουν η κάθε μια την αποθήκευση των αποτελεσμάτων στο δικό τους αρχείο καταχωρητών και την επανάκτηση των τιμών αυτών ώστε να προωθηθούν στις επιμέρους αριθμητικές μονάδες προς υπολογισμό των νέων αποτελεσμάτων. Στις μονάδες αυτές έχει εφαρμοστεί μία τεχνική σημαντικής μεί- ωσης της επιφάνειας του δικτύου πολυπλεκτών μέσω της ομαδοποίησης των αποτελεσμάτων ανά δύο. Τις τρεις αυτές μονάδες συγχρονίζει μία Μηχανή Πεπερασμένων Καταστάσεων (FSM), υπεύθυνη για τη διαβίβαση όλων των σημάτων ελέγχου. Μία επιπλέον τεχνική αφορά τη δόμηση του Αρχείου Καταχωρητών με τέτοιο τρόπο ώστε να διαχειρίζεται πιο απο- δοτικά τη διάρκεια ζωής των αποτελεσμάτων με συνέπεια τη μείωση του αριθμού των αναγκαίων καταχωρητών. Περισσότερες λεπτομέρειες για τις συγκεκριμένες τεχνικές παρουσιάζονται στο Κεφάλαιο 3. Στην προσπάθεια να ενισχυθεί το συνολικό σύστημα από επιθέ- σεις τύπου SPA (Simple Power Attack) και SCA (Side Channel Analysis), έχει προταθεί μία σειρά αντίμετρων. Η εκτέλεση του Βαθμωτού Πολλαπλα- σιασμού επιτυγχάνεται με τη χρήση του αλγορίθμου Montgomery Power Ladder (MPL), ο οποίος προσφέρει απόκρυψη των εκτελεσθέντων πράξεων σημείων χωρίς όμως την εισαγωγή επιπλέον ψεύτικων πράξεων. Εκτός όμως από τον παραλληλισμό επιπέδων των GF (2 k ) πράξεων και τη χρήση του MPL, δύο επιπλέον μέτρα προστασίας από SCA επιθέσεις έχουν εφαρ- μοστεί. Το πρώτο αφορά την τυχαιοποίηση της βαθμωτής τιμής του πολλα- πλασιασμού, η οποία γίνεται σε επίπεδο λογισμικού και το δεύτερο αφορά την τυχαιοποίηση των προβολικών συντεταγμένων του σημείου εξόδου του Βαθμωτού Πολλαπλασιαστή πολλές φορές κατά τη διάρκεια εκτέλεσης του πολλαπλασιασμού. Για να δοκιμαστεί η αρχιτεκτονική του συστήματος αυτού σε πραγματικές συνθήκες, υλοποιήθηκε σε υλικό με τη βοήθεια του Zynq- 7000 SoC FPGA (Zedboard). Ο Βαθμωτός Πολλαπλασιαστής συνδέεται με έναν επεξεργαστή ARM Cortex-A9 μέσω ενός driver γραμμένου σε C. Τα αποτελέσματα που παράχθηκαν φανερώνουν μία ισορροπημένη σχεδίαση, με αρκετά ικανοποιητικές τιμές όσον αφορά το συνδυασμό ταχύτητας και χρησιμοποιούμενης επιφάνειας. Τέλος, το σύστημα ελέγχθηκε ως προς την αντίσταση που προ- σφέρει ενάντια σε επιθέσεις μέσω της χρήσης της τεχνικής του Test Vector vi Leakage Assessment (TVLA), όπου επίσης φανερώθηκαν αρκετά ικανοποι- ητικά αποτελέσματα που του προσδίδουν ένα σεβαστό επίπεδο προστα- σίας. Λαμβάνοντας υπόψιν λοιπόν και τις θετικές μετρήσεις υλοποίησης όπως αναφέρθηκαν παραπάνω, φανερώνεται πως το σύστημα αυτό απο- τελεί μία ολοκληρωμένη λύση όσον αφορά τα διάφορα χαρακτηριστικά του και υλοποιημένο με βάση μία καινούρια οικογένεια καμπυλών.
Abstract (translated): The point of interest of this Thesis is an important subject in the field of Cryptography, notably the effort of nominating and implementing in practice a safer and more efficient family of Elliptic Curves. Through this scope, we developed an Elliptic Curve Cryptosystem based on the Edwards Curves family and more specifically its binary GF (2 k ) representation, Binary Edwards Curves. Firstly, a comparison is performed in mathematical level between the different family types of Elliptic Curves, highlighting the advantages and disadvantages each one offers. Compared to the already standardized Weierstrass family, Edwards Curves are considered unified and complete, due to the absence of exception points that could expose critical security vulnerabilities. On the other hand, they tend to perform generally slower than Weierstrass curves because of the higher number of field operations they require. At this point in the design process, the correct finite field must be chosen that will drastically alter the form of the remaining system. One highly flexible approach is implementing every aspect of the Cryptographic System in software while lacking in operational speed and Side Channel Attack resistance. The other approach is essentially a mostly hardware-based implementation that sacrifices flexibility and design time for high levels of performance and security. Working towards a faster system, binary GF (2 k ) fields were used instead of primary GF ( p ) ones, due to the simplicity they offer in a hardware design. Imbued with the knowledge that at the lowest level the GF (2 k ) addition and multiplication operations will be hardware implemented, we try to improve the performance to design time ratio. Observing the ECDSA signature generation and verification algorithms we conclude that the Scalar Multiplication is the most demanding operation. This leads to the decision of implementing a purely hardware Scalar Multiplier that completes an otherwise purely software-based system design. A series of optimization techniques are then applied on the scalar multiplier, aiming for a balanced design in respect to speed and number of logic gates that also doesn’t lack protective countermeasures against SCAs. After a Data Dependency Graph analysis, the GF (2 k ) addition and doubling operations are grouped together and parallelized in multiple layers, hiding critical information during the execution of the scalar multiplication. The multiplier’s architecture consists of three semi-autonomous units, each with their own register file where the results are being stored again for future calculations. By grouping in pairs the inputs to the arithmetic units at the multiplexer network level, we achieve significant reduction in occupied LUTs. viii The control of all the systems is operated by a Finite State Machine (FSM). The last optimization technique is applied on the Register File by optimizing the data lifespan which leads to a reduction in necessary registers. More information on these techniques is presented in Chapter 3. In order to improve the system’s resistance against Simple Power Attacks and Side Channel Analysis attacks, a series of countermeasures is proposed. Regarding the scalar multiplication algorithm, the Montgomery Power Ladder (MPL) algorithm is implemented, offering operation masking without introducing any dummy operations overhead. The last two SCA resistance countermeasures we implemented are the software-based scalar blinding and the randomization of the projective coordinates of the output point at the end of every MPL round. For implementation of the system in real-time, we used the Zynq- 7000 SoC FPGA (Zedboard). The Scalar Multiplier is connected with an ARM Cortex-A9 through a C driver. The implementation results reveal a quite balanced design regarding used logic gates and execution speed. Lastly, for test purposes of the SCA resistance, the Test Vector Leakage Assessment (TVLA) technique generated quite positive results, indicating a strong level of protection. The combination of both scopes’ interesting results indicates the implemented system is a complete, protected and well balanced solution in a newly explored family of Elliptic Curves.
Appears in Collections:Τμήμα Ηλεκτρολ. Μηχαν. και Τεχνολ. Υπολογ. (ΔΕ)

Files in This Item:
File Description SizeFormat 
Nemertes_DimopoulosCh(ele).pdf2.63 MBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons