Επίθεση χρόνου

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

Σύστημα RSA

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

Υπολογισμός

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

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

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

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

Επαλήθευση κρυπτοσυστήματος

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

Για να γίνει η υπόθεση των δυαδικών ψηφίων πιο σίγουρη πρέπει να έχουµε έναν ελάχιστο αριθµό χρονικών δειγµάτων που θα χρησιµοποιήσουµε µε τον εξής τρόπο: Η όλη επίθεση προσεγγιστικά είναι σαν ένα πρόβληµα ανίχνευσης σήµατος. Ως επακόλουθο, για τα ${\displaystyle j}$ διαφορετικά µηνύµατα ${\displaystyle y_{0},y_{1},...,y_{j-1}}$ µε αντίστοιχες χρονικές µετρήσεις ${\displaystyle T_{0},T_{1},...,T_{j-1}}$ η πιθανότητα ένα ${\displaystyle x_{b}}$ για τα πρώτα ${\displaystyle b}$ εκθετικά ψηφία να είναι το σωστό είναι ανάλογη µε :

${\displaystyle P(x_{b})\propto \prod _{i=0}^{j-1}F(T_{i}-t(x_{i},y_{b})).}$

Όπου ${\displaystyle t(x_{i},y_{b})}$ είναι το µέγεθος της χρονικής διάρκειας που απαιτείται για τις πρώτες ${\displaystyle b}$ επαναλήψεις του υπολογισµού του ${\displaystyle y^{x_{i}}(modn)}$ και ${\displaystyle F}$ η συνάρτηση κατανοµής του ${\displaystyle T-t(x_{i},y_{b})}$ για τις διάφορες τιµές του ${\displaystyle y}$ και σωστά ${\displaystyle x_{b}}$. Έτσι µε τον παραπάνω τύπο και τη χρήση των µετρήσεων µας έχουµε την ευχέρεια να βελτιώσουµε την προσέγγιση της ${\displaystyle F}$.