Κρυπτανάλυση

Η **κρυπτανάλυση** (αγγλ.: *cryptanalysis*) είναι η μελέτη για την επινόηση μεθόδων που εξασφαλίζουν την κατανόηση του νοήματος της κρυπτογραφημένης πληροφορίας, έχοντας ως άγνωστες ποσότητες τον κρυφό μετασχηματισμό, το κλειδί, με βάση το οποίο αυτός πραγματοποιήθηκε και το κρυπτογραφημένο μήνυμα. Βασικός στόχος της είναι, ανάλογα με της απαιτήσεις του αναλυτή κρυπτοσυστημάτων ή αλλιώς *κρυπταναλυτή*, να βρει το κλειδί, το μήνυμα ή ένα ισοδύναμο αλγόριθμο που θα τον βοηθά να αναγνώσει το (κρυφό) μήνυμα. Ένας κρυπταλγόριθμος λέγεται ότι έχει «*σπάσει*», αν βρεθεί μια μέθοδος (πιθανοκρατική ή ντετερμινιστική) που μπορεί να βρει το μήνυμα ή το κλειδί με πολυπλοκότητα μικρότερη από την πολυπλοκότητα της *επίθεσης ωμής βίας* (αγγλ.: *brute force attack*). Η πρώτη νύξη σχετικά με την κρυπτανάλυση έγινε από ένα Άραβα μαθηματικό τον 8ο αιώνα με την εργασία *Ανταμπ-αλ-κουταπ* ή αλλιώς *Εγχειρίδιο των γραμματέων*.

Η κρυπτανάλυση είναι ο ένας από τους δύο κλάδους της κρυπτολογίας (ο άλλος είναι η *κρυπτογραφία*), η οποία ασχολείται με τη μελέτη της ασφαλούς επικοινωνίας. Σήμερα η κρυπτολογία θεωρείται ένα διεπιστημονικό γνωστικό πεδίο, το οποίο μπορεί να μελετηθεί ως όψη των εφαρμοσμένων μαθηματικών, της θεωρητικής πληροφορικής ή της επιστήμης ηλεκτρονικού μηχανικού. Παρεμφερείς κλάδοι είναι, αντιστοίχως, η στεγανογραφία και η στεγανοανάλυση.

## Είδη επιθέσεων

### Κρυπταναλυτικές επιθέσεις σε αλγορίθμους

Υπάρχουν έξι βασικές κρυπταναλυτικές επιθέσεις, κατηγοριοποιημένες ανάλογα με την ικανότητα του αντιπάλου (πόρους-υπολογιστική ισχύ) και το επίπεδο πρόσβασης που έχει ο επιτιθέμενος:

# Επίθεση βασισμένη στο κρυπτοκείμενο : Ο κρυπταναλυτής έχει στην διάθεση του Ν κρυπτομηνύματα με δεδομένη τη γνώση του αλγορίθμου. Σκοπός είναι να ανακαλύψει τα μηνύματα που περικλείουν τα κρυπτοκείμενα ή να εξαγάγει το κλειδί που χρησιμοποιήθηκε.
# Επίθεση βασισμένη στην γνώση μηνυμάτων κρυπτοκειμένων : Ο κρυπταναλυτής έχει στην διάθεση του μερικά ζευγάρια (μηνυμάτων, κρυπτοκειμένων). Ο στόχος είναι η εξαγωγή του κλειδιού ή ενός αλγορίθμου για την αποκρυπτογράφηση νέων μηνυμάτων (προσεγγιστικός αλγόριθμος) με το ίδιο κλειδί.
# Επίθεση βασισμένη στην επιλογή μηνυμάτων : Ο κρυπταναλυτής έχει καταφέρει να αποκτήσει πρόσβαση στη επιλογή του μηνύματος που θα κρυπτογραφηθεί. Στόχος είναι η εξαγωγή του κλειδιού ή ενός προσεγγιστικού αλγορίθμου.
# Προσαρμοσμένη επίθεση, βασισμένη στην επιλογή μηνυμάτων : Ο κρυπταναλυτής μπορεί να επιλέξει όχι μόνο μία συστάδα μηνυμάτων αλλά μπορεί να επιλέξει ποιο επόμενο μήνυμα θα κρυπτογραφηθεί(Κατάλληλη επιλογή ζευγαριών προσδίδει περισσότερη πιθανότητα για την τιμή του κλειδιού). Στόχος είναι η εξαγωγή του κλειδιού ή ενός προσεγγιστικού αλγορίθμου.
# Επίθεση βασισμένη στην επιλογή κρυπτοκειμένων: Ο κρυπταναλυτής μπορεί να επιλέξει κρυπτοκείμενα για αποκρυπτογράφηση (μελετά πώς συμπεριφέρεται ο αλγόριθμος στην αποκρυπτογράφηση) και έχει πρόσβαση στα αποκρυπτογραφημένα κείμενα.
# Προσαρμοσμένη επίθεση βασισμένη στην επιλογή μηνυμάτων - κλειδιών: Ο κρυπταναλυτής επιλέγει μια σχέση μεταξύ του άγνωστου κλειδιού και του δικό του κλειδιού και βάση των συμπερασμάτων που βγάζει από την ανάλυση (Είσοδος/έξοδος) στο σύστημα - στόχο και στο δικό του αντίγραφο (Κρυπταλγόριθμος) προσεγγίζει, μετά από κάποιες δοκιμές, το σωστό κλειδί.

### Επιθέσεις στο κανάλι επικοινωνίας

Υπάρχουν τέσσερεις βασικές απειλές στο κανάλι επικοινωνίας, κατηγοριοποιημένες με κριτήριο την ενεργή ή παθητική συμπεριφορά του αντιπάλου.

# Διακοπή γραμμής : Ο αντίπαλος έχει διακόψει την ροή της πληροφορίας από τον αποστολέα στον παραλήπτη (ενεργή συμπεριφορά)
# Υποκλοπή πληροφορίας από το κανάλι: Ο αντίπαλος αντιγράφει τις πληροφορίες που διαβιβάζονται στο κανάλι επικοινωνίας (παθητική συμπεριφορά – μη ανιχνεύσιμη)
# Τροποποίηση πληροφορίας στο κανάλι (Man-in-the-middle επίθεση): Ο αντίπαλος τροποποιεί τις πληροφορίες που διαβιβάζονται στο κανάλι με τέτοιο τρόπο, ώστε να αλλάξει το περιεχόμενο ή να αναγεννά δική του πληροφορία. (ενεργή συμπεριφορά)
# Πλαστογράφηση πηγής: Ο αντίπαλος προσποιείται ότι είναι ένα από τα μέλη που έχουν πρόσβαση στο κανάλι.

Είδη επιθέσεων στο κανάλι επικοινωνίας

## Ταξινόμηση Μοντέλων αξιολόγησης ασφάλειας

Υπάρχουν 4 βασικά μοντέλα για την αξιολόγηση των αλγορίθμων:
* Ασφάλεια άνευ όρων

* Υπολογιστική ασφάλεια

* Θεωρία πολυπλοκότητας

* Αποδείξιμη ασφάλεια.

### Ασφάλεια άνευ όρων (Τέλεια Ασφάλεια)

Αυτή η μέτρηση εστιάζεται στην διάκριση αν ένα κρυπτοσύστημα έχει ασφάλεια άνευ όρων. Η βασική υπόθεση είναι ότι όσο κρυπτοκείμενο και αν κατέχει ο αντίπαλος, δεν υπάρχει αρκετή πληροφορία για να ανακτήσει το ανοικτό κείμενο (μοναδική λύση), όση υπολογιστική ισχύ (άπειρη) και αν έχει στην διάθεση του. Χαρακτηριστικό παράδειγμα το σημειωματάριο μίας χρήσης.

### Υπολογιστική ασφάλεια (Πρακτική Ασφάλεια)

Αυτή η μέτρηση εστιάζεται στην υπολογιστική προσπάθεια "παράγοντας εργασίας", που χρειάζεται για να διασπαστεί ένα κρυπτοσύστημα. Στόχος των συγχρόνων συστημάτων είναι να εμφανίζουν μεγάλο παράγοντα δυσκολίας ώστε να μην είναι χρονικά δυνατό να διασπαστούν με τα διαθέσιμα (ή και τα μελλοντικά) μέσα.

### Ασφάλεια – θεωρία πολυπλοκότητας

Αυτή η μέτρηση εστιάζει στην ταξινόμηση της υπολογιστικής ικανότητας του αντιπάλου υπολογιστικών προβλημάτων ανάλογα με τους πόρους που απαιτούνται για την επίλυση τους. Οι πόροι αναφέρονται σε:

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

### Αποδείξιμη ασφάλεια

Αυτή η μέτρηση εστιάζεται στην απόδειξη ισοδυναμίας του μαθηματικού μοντέλου του κρυπτοσυστήματος με κάποιο πολύ γνωστό δύσκολο στην επίλυση του πρόβλημα (θεωρίας αριθμών). Χαρακτηριστικό παράδειγμα η *παραγοντοποίηση μεγάλων ακεραίων*.

## Κρυπτανάλυση Κλασικών Κρυπτοσυστημάτων

Υπάρχουν διάφοροι τύποι κρυπταναλυτικών επιθέσεων για τα κλασικά κρυπτοσυστήματα. Οι περισσότερες βασίστηκαν πάνω στην γλωσσική δομή του μηνύματος. Στις νεότερες μορφές Κρυπτανάλυσης Κλασικών Κρυπτοσυστημάτων παρατηρείται ή είσοδος της στατιστικής στην ανάλυση.

Σχήμα 3.1 Χάρτης Κρυπταναλυτικών μεθόδων

* Μέθοδος Ωμής Βίας
* Ανάλυση Συχνότητας Γλώσσας
* Μέθοδος Κασίσκι
* Μέθοδος Δείκτης Σύμπτωσης
* Μέθοδος Αμοιβαίου Δείκτη Σύμπτωσης

## Κρυπτανάλυση Σύγχρονων Κρυπτοσυστημάτων
* Διαφορική Κρυπτανάλυση (Differential Cryptanalysis)
* Γραμμική Κρυπτανάλυση (Linear Cryptanalysis)
* Κρυπτανάλυση στο Επίπεδο Υλικού (Side-channel cryptanalysis)
* Κλειδοσχεσιακή Κρυπτανάλυση (Releted Key Cryptanalysis)
* Κρυπτανάλυση Ισοτίμων (Cryptanalysis mod n)
* Κρυπτανάλυση τετραγώνου (Square Cryptanalysis)
* Στατιστική κρυπτανάλυση (Statistical Cryptanalysis)

## Αναφορές

* 'Γραμμική - Διαφορική κρυπτανάλυση και κατασκευή κρυπτογραφικά ασφαλών S-boxes*, 125, 2007 [http://nemertes.lis.upatras.gr/jspui/bitstream/10889/656/1/MasterThesis.pdf Μεταπτυχιακή Εργασία].  *
''