Ιστορικό Σπασίματος WEP Επ1: FMS Attack

  1. Επεισόδιο 1: FMS Attack
  2. Επεισόδιο 2: KoreK Attack
  3. Επεισόδιο 3: PTW Attack
  4. Επεισόδιο 4: Chopchop Attack

 

Οι Fluhrer, Mantin και Shamir (εξ’ ου και το FMS από τα αρχικά τους), δημοσίευσαν την πρώτη επίθεση ανάκτησης κλειδιού του WEP το 2001. Η επίθεσή τους βασίζεται στην ακόλουθη ιδέα: Ο επιτιθέμενος που παθητικά «ακούει» την κίνηση των δεδομένων ενός δικτύου προστατευμένου με WEP, μπορεί να καταγράψει πολλά κρυπτογραφημένα πακέτα συμπεριλαμβανομένων των IVs που χρησιμοποιήθηκαν για τα πακέτα αυτά. Επειδή τα πρώτα bytes του plaintext των περισσοτέρων πακέτων είναι εύκολο να προβλεφθούν, ο επιτιθέμενος μπορεί να ανακτήσει τα πρώτα bytes των keystreams που χρησιμοποιήθηκαν για την κρυπτογράφηση αυτών των πακέτων. Όλα τα υπόλοιπα bytes του κλειδιού ανά πακέτο είναι τα ίδια για όλα τα πακέτα αλλά αρχικά άγνωστα στον επιτιθέμενο.

Ας υποθέσουμε ότι ο επιτιθέμενος γνωρίζει τα πρώτα \(l\) bytes ενός κλειδιού RC4 που χρησιμοποιήθηκε για να παραχθεί ένα keystream X. Μπορεί λοιπόν να εξομοιώσει τα πρώτα \(l\) βήματα του RCA-KSA και να γνωρίζει το \(S_{l}\) και \(j_{l}\). Στο επόμενο βήμα του RC4-KSA, έχουμε:

\[j_{l+1}=j_{l}+K[l]+S_{l}[l]\]
και το \(S_{l}[l]\) αλλάζει θέση με το \(S_{l}[j_{l+1}]\). Αν ο επιτιθέμενος μπορούσε να αποκαλύψει το \(S_{l+1}[l]\), θα μπορούσε εύκολα να ανακτήσει το \(K[l]\) απλά υπολογίζοντας την διαφορά:
\[S_{l}^{-1}\left [ S_{l+1}[l] \right ]-j_{l}-S_{l}[l]\]
Για να αποκαλυφθεί αυτή η τιμή, οι προαναφερθέντες κύριοι έκαναν το εξής:
Ας υποθέσουμε πως οι παρακάτω συνθήκες, ισχύουν μετά τα πρώτα \(l\) βήματα του RC4-KSA:

 

  1. \(S_{l}[1]< l\)
  2. \(S_{l}[1]+S_{l}\left [ S_{l}[1] \right ]=l\)
  3. \(S_{l}^{-1}[X[0]]\neq 1\)
  4. \(S_{l}^{-1}[X[0]]\neq S_{l}[1]\)
Στα επόμενα βήματα του RC4-KSA, μια τιμή \(k=S_{l}[j_{l+1}]\) θα αλλάξει θέση με το \(S_{l+1}[l]\). Αν το \(j\) αλλάζει τυχαία για το υπόλοιπο του RC4-KSA, οι τιμές \(S[1]\), \(S[S[1]]\) και \(S[l]\) δεν θα μεταβληθούν για το υπόλοιπο του RC4-KSA με πιθανότητα \(\left ( \frac{1}{e} \right )^{3}\). Όταν το πρώτο byte του output παραχθεί από το RC4-PRGA, το \(j\) θα πάρει την τιμή \(S_{n}[1]\) και τα \(S_{n}[1]\) και \(S_{n}[j]\) θα αλλάξουν θέση μεταξύ τους.

Μετά την αλλαγή θέσεων, συνεχίζει να ισχύει ότι \(S[1]+S[S[1]]=l\) και το \(X[0]\), δηλαδή το πρώτο byte του output του RC4-PRGA, θα ισούται με το \(S[l]\). Αν οι συνθήκες 3 και 4 πάψουν να ισχύουν, αυτό θα σήμαινε ότι το \(S[1]\) ή το \(S[S[1]]\) έχουν μεταβληθεί. Στην σπάνια περίπτωση να συνεχίσουν να ισχύουν και οι 4 συνθήκες, η συνάρτηση:

\[F_{fms}\left ( K[0],…,K[l-1],X[0] \right )=S_{l}^{-1}[X[0]]-j_{l}-S_{l}[l]\]
Θα πάρει την τιμή \(K[l]\) με πιθανότητα περίπου \(\left ( \frac{1}{e} \right )^{3}\approx 5\)%. Θα αναφερόμαστε σε αυτή την ομάδα συνθηκών μαζί με την συνάρτηση ως “correlation” για το RC4. Οι συντάκτες της επίθεσης αναφέρονται σε αυτές τις συνθήκες (ή τουλάχιστον στις πρώτες δυο) ως “resolved condition”.

Χρησιμοποιώντας αυτό το correlation, μπορεί να ανακτηθεί όλο το κλειδί του WEP. Ο επιτιθέμενος λαμβάνει πακέτα από κάποιο δίκτυο προστατευμένο με WEP και ανακτά το πρώτο byte του keystream που χρησιμοποιήθηκε για να κρυπτογραφηθούν τα πακέτα που έλαβε, μαντεύοντας το πρώτο byte του plaintext. Υπάρχουν πολλές τεχνικές δημιουργίας traffic σε ένα δίκτυο προστατευμένο με WEP (που έχουμε αναλύσει σε άλλο άρθρο και δεν θα μπούμε σε λεπτομέρειες εδώ) ακόμα και χωρίς το κλειδί του δικτύου, που επιτρέπουν την ανάκτηση των πρώτων 1000+ bytes του keystream ανά πακέτο. Ο επιτιθέμενος επιλέγει τα πακέτα που το resolved condition ισχύει και υπολογίζει την \(F_{fms}\) για αυτά τα πακέτα. Κάθε αποτέλεσμα της \(F_{fms}\) μπορεί θα θεωρηθεί ως μια ψήφος για την τιμή \(Rk[0]\). Μόλις ληφθούν αρκετά πακέτα, ο επιτιθέμενος επιλέγει την τιμή του \(Rk[0]\) βασισμένος στο πλήθος των ψήφων που έχουν παραχθεί από την \(F_{fms}\). Αν η επιλογή του ήταν σωστή, τότε γνωρίζει τα πρώτα \(l\)= 4-bytes του κλειδιού ανά πακέτο και μπορεί να συνεχίσει για το \(Rk[1]\). Να σημειωθεί ότι όλα τα πακέτα πρέπει να επανεξετασθούν για το κατά πόσο το resolved condition ισχύει διότι η επαλήθευση αυτή εξαρτάται από την τιμή του \(Rk[0]\). Μόλις όλα τα bytes του \(Rk\) έχουν καθοριστεί, ο επιτιθέμενος τσεκάρει αν το κλειδί που πήρε ως αποτέλεσμα είναι σωστό κάνοντας κάποιες δοκιμαστικές αποκρυπτογραφήσεις. Αν το κλειδί είναι σωστό, η επίθεση έχει πετύχει. Αν δεν είναι, τότε θα πρέπει να ψάξει για μια εναλλακτική τιμή του \(Rk[i]\) που να είναι σχεδόν το ίδιο πιθανή λύση. Ύστερα, βάζει την καινούρια τιμή στο decision tree σε «βάθος» \(i\) και συνεχίζει την επίθεση με αυτή την εναλλακτική επιλογή του \(Rk[i]\).

Παρ’ όλο που το 5% πιθανότητες επιτυχίας δείχνει εντυπωσιακό, η επίθεση χρειάζεται 4.000.000 με 6.000.000 πακέτα για να πετύχει με πιθανότητα τουλάχιστον 50%. Αυτό συμβαίνει γιατί το resolved condition ισχύει μόνο για ένα μικρό σύνολο τυχαία επιλεγμένων IVs.

Επόμενο επεισόδιο >>

 

Leave a Reply

Your email address will not be published.