Timing Attack(Επίθεση Χρόνου)

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια

Εισαγωγικά πρέπει να πούµε τα εξής : Κατά τις διαδικασίες που εκτελούνται από τον αλγόριθµο ενός προγράµµατος για την εξαγωγή του προσωπικού κλειδιού (private key), αλλά και την κρυπτογράφηση ή αποκρυπτογράφηση ενός µηνύµατος, ο χρόνος υπολογισµού ποικίλοι. Αυτό δεν οφείλεται αποκλειστικά και µόνον στον αλγόριθµο. Εν γένει υφίσταται κυρίως λόγο των βρόγχων ενός αλγορίθµου (conditional statements), της µνήµης RAM, του είδους του επεξεργαστή του υπολογιστή που χρησιµοποιούµε, αλλά και των εντολών που αυτός χρησιµοποιεί, όπως για παράδειγµα οι τρόποι και ευκολία πολλαπλασιασµού και διαίρεσης. Τέλος εύλογο είναι ότι το µέγεθος των κλειδιών του κρυπτοσυστήµατος περιπλέκει χρονικά τον αλγόριθµο. Τα χρονικά δεδοµένα αυτά, τα οποία µπορούν εύκολα να παρατηρηθούν σε έναν τρίτο υπολογιστή, χρησιµοποιούνται στο timing attack.

Το σύστηµα RSA συνίσταται στον υπολογισµό τουR = y^x(modn) από τα οποία τα n,y καθώς είναι δηµόσιο κλειδί και υποκλεµµένη πληροφορία αντίστοιχα, αποτελούν τα γνωστά στοιχεία του κρυπταναλυτή. Στόχος του τελευταίου είναι να ανακτήσει την τιµή του x, του προσωπικού κλειδιού. Ο παραλήπτης του µηνύµατος (και στην περίπτωσή µας το θύµα του κρυπταναλυτή), οφείλει να υπολογίσει την τιµή R = y^x(modn) για διάφορες τιµές του y, ενώ οι χρόνοι υπολογισµού που θα χρειαστεί να κάνει τα παραπάνω και να αποκρυπτογραφήσει το κείµενο, θεωρούνται γνωστά για τον κρυπταναλυτή. Από τα δεδοµένα αυτά , δηλαδή τον χρόνο που χρειάστηκε το συγκεκριµένο computer για να αποκρυπτογραφήσει το κείµενο, καθίσταται γνωστό στον κρυπταναλυτή ποιο κρυπτοσύστηµα χρησιµοποιήθηκε.

Σε αυτό το σηµείο ας κατανοήσουµε τι συµβαίνει κατά τον υπολογισµό του R = y^x(modn) όπου το x είναι µεγέθους w δυαδικών ψηφίων (bits), από τον επεξεργαστή του υπολογιστή µας:

Το x παίρνει τιµές ακολουθίες ψηφίων 0 και 1 και ο υπολογιστής υπολογίζει την εκάστοτε αριθµητική παράσταση. Εποµένως αν το x παίρνει τιµές ακολουθίες ψηφίων 0 και1 και ο υπολογιστής υπολογίζει την εκάστοτε αριθµητική παράσταση. Εποµένως αν το x ήταν 01001000100001000001000000010000, µεγέθους 32 bit δηλαδή, ο επεξεργαστής θα έκανε την πράξη y⁰y¹y⁰y⁰y¹y⁰...y¹y⁰y⁰y⁰(modn)

Ουσιαστικά ο επεξεργαστής υπολογίζει την παραπάνω αριθµητική παράσταση έως ότου το επόµενο δυαδικό ψηφίο δεν υπάρχει όπου και σταµατά. Βάσει όλων αυτών ο κρυπταναλυτής πρέπει να εφαρµόσει κάποια µέθοδο για να µπορέσει να προσδιορίζει το εκάστοτε δυαδικό ψηφίο της παράστασης y^x(modn) και ο προσδιορισµός αυτός να µην είναι κάτι το εντελώς τυχαίο, όπως στην χρήση της ωµής επίθεσης όπου και θα δίναµε αυθαίρετες τιµές στο x έως ότου είχαµε καποιο αποτέλεσµα που να έβγαζε νόηµα µετά την αποκρυπτογράφηση του κειµένου µε το υποθετούµενο κλειδί x.

Βάσει των προαναφερθέντων αυτό που έχει να κάνει ο κρυπταναλυτής είναι κάτι απλό. Παρατηρεί τον υπολογιστή του παραλήπτη και καταγράφει τη χρήση του επεξεργαστή για τον υπολογισµό του y^x(modn). Αν ο χρόνος που απαιτείται από το σύστηµα του υπολογιστή να υπολογίσει τον αλγόριθµο, είναι γρήγορος, ενώ το R^b = y^b(modn) είναι πολύ γρήγορος, το εκθετικό ψηφίο b είναι µάλλον µηδέν (0) . Προφανώς η χρήση της παραπάνω διαδικασίας γίνεται έως ότου βρεθούν - υποτεθούν και τα επόµενα εκθετικά ψηφία.

Ως είδος ωµής επίθεσης, έτσι και στην επίθεση χρόνου, µετά την εξαγωγή κάπου αποτελέσµατος απευθείας γίνεται χρήση αυτού για να παρατηρηθεί αν επαληθεύει το κρυπτοσύστηµα. Έτσι σε περίπτωση που υπάρχει λάθος στην εύρεση ενός εκθετικού ψηφίου, η επίθεση δεν θα έχει µετά νόηµα αφού το κείµενο θα είναι µη αναγνώσιµο.

Για να γίνει η υπόθεση των δυαδικών ψηφίων πιο σίγουρη πρέπει να έχουµε έναν ελάχιστο αριθµό χρονικών δειγµάτων που θα χρησιµοποιήσουµε µε τον εξής τρόπο: Η όλη επίθεση προσεγγιστικά είναι σαν ένα πρόβληµα ανίχνευσης σήµατος. Ως επακόλουθο, για τα j διαφορετικά µηνύµατα y₀,y₁,...,y_{j − 1} µε αντίστοιχες χρονικές µετρήσεις T₀,T₁,...,T_{j − 1} η πιθανότητα ένα x_b για τα πρώτα b εκθετικά ψηφία να είναι το σωστό είναι ανάλογη µε :

Όπου t(x_i,y_b) είναι το µέγεθος της χρονικής διάρκειας που απαιτείται για τις πρώτες b επαναλήψεις του υπολογισµού του και F η συνάρτηση κατανοµής του T − t(x_i,y_b) για τις διάφορες τιµές του y και σωστά x_b. Eτσι µε τον παραπάνω τύπο και τη χρήση των µετρήσεων µας έχουµε την ευχέρεια να βελτιώσουµε την προσέγγιση της F.

Το άρθρο αυτό χρειάζεται επέκταση. Βοηθήστε τη Βικιπαίδεια επεκτείνοντάς το!