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

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

 

Το 2007, μια νέα γενιά επιθέσεων στο WEP δημοσιεύεται από τους Pyshkin, Tews και Weinmann. Η επίθεσή τους μας παρουσιάζει δύο νέα concepts:

Όλα τα προηγούμενα correlations που χρησιμοποιήθηκαν, απαιτούσαν 2-4 τιμές μέσα στο \(S\) να μην αλλάξουν κατά την διάρκεια της συνέχειας του RC4-KSA καθώς επίσης απαιτούνταν πολλές προϋποθέσεις που έπρεπε να ισχύουν για να χρησιμοποιηθεί το correlation. Γι’ αυτό τον λόγο, μόνο ένας μικρός αριθμός πακέτων μπορούσε να χρησιμοποιηθεί για να ψηφίσει κάποιο συγκεκριμένο keybyte.
Το 2005, ο Klein έδειξε ότι το \(l-X[l-1]\) παίρνει την τιμή του \(S[l]\) με πιθανότητα \(\frac{2}{n}\). Αν το \(S_{l}[l]\) μείνει ανέπαφο μέχρι να παραχθεί το \(X[l-1]\), η συνάρτηση:

\[F_{Klein}\left ( K[0], … ,K[l-1],X[l-1] \right )=S_{l}^{-1}[l-X[l-1]]-\left ( S_{l}[l]+j_{l} \right )\]
παίρνει την τιμή του \(K[l]\) με πιθανότητα \(\frac{2}{n}\). Αυτό το αποτέλεσμα είναι γνωστό κι ως “The Jenkins correlation”. Το \(S_{l}[l]\) παραμένει ανέπαφο με πιθανότητα περίπου \(\frac{1}{e}\) . Αν το \(S_{l}[l]\) τροποποιηθεί πριν παραχθεί το \(X[l-1]\), η \(F_{Klein}\) παίρνει μια τυχαία τιμή. Έχοντας όλα αυτά κατά νου, η πιθανότητα η \(F_{Klein}\) να πάρει την τιμή \(K[l]\) είναι:
\[\left ( \left ( \frac{1}{e} \right ) \frac{2}{n} \right )+\left ( \left ( 1-\frac{1}{e} \right ) \frac{1}{n} \right )\approx \frac{1,37}{n}\]
Αυτό το correlation δεν έχει καθόλου απαιτήσεις σχετικά με την εσωτερική κατάσταση του RC4 ή του keystream οπότε κάθε πακέτο μπορεί να χρησιμοποιηθεί.

Το δεύτερο καινούριο concept είναι μια αλλαγή στον δομή της επίθεσης. Μέχρι τώρα, κάθε επίθεση ήταν βασισμένη στο decision tree και κάποια στρατηγική αναζήτησης χρησιμοποιείτο για να καθοριστεί το κλειδί αναλύοντας ένα-ένα τα bytes.
Ας υποθέσουμε ότι ο επιτιθέμενος γνωρίζει τα πρώτα \(l\) bytes ενός κλειδιού RC4 και καταφέρνει να ανακτήσει το \(k=S_{l+2}[l+1]\) αντί για το \(S_{l+1}[l]\). Τώρα ισχύει ότι:

\[S_{l+1}^{-1}[k]-S_{l+1}[l+1]-S_{l}[l]-j_{l}=K[l]+K[l+1]\]
και ο επιτιθέμενος θα είχε ανακτήσει την τιμή του \(K[l]+K[l+1]\). Με πολύ μεγάλη πιθανότητα, ισχύει ότι:
\(S_{l+1}^{-1}[k]=S_{l}^{-1}[k]\) και \(S_{l+1}[l+1]=S_{l}[l+1]\)

 

Κάνοντας την αντικατάσταση στην προηγούμενη εξίσωση, έχουμε:
\[S_{l}^{-1}[k]-S_{l+1}[l+1]-S_{l}[l]-j_{l}=K[l]+K[l+1]\]
Τέτοια correlations ανάμεσα στα πρώτα \(l\) bytes ένος κλειδιού RC4, στο παραγόμενο keystream και στα επόμενα \(i\) bytes του κλειδιού, θα τις ονομάζουμε “Multibyte Correlations” και θα συμβολίζουμε ως \(\sigma _{i}\) το sum:
\[\sum_{k=0}^{i}Rk[k]\]
Οι φίλοι μας Pyshkin, Tews και Weinmann, τροποποίησαν την \(F_{Klein}\) ώστε να ψηφίζει για το sum των επόμενων m keybytes για κάθε m \(\in \) {1,…,13}. Έτσι, οδηγούμαστε στο:

 

\(F_{ptw_{m}}\left ( K[0], … ,K[l-1],X[l+m-2]\right )\)
\[=S_{l}^{-1}[l+m-1-X[l+m-2]]- \left (\sum_{a=l}^{l+m-1} S_{l}[a] \right)\]
που εξαρτάται μόνο από τα πρώτα 3 bytes του IV και ψηφίζει για το \(\sigma _{i}\) αντί για το \(Rk[i]\).
Τώρα, η επίθεση PTW δουλεύει ως εξής: πρώτα, ο επιτιθέμενος καταγράφει πακέτα και ανακτά τα keystreams όπως στις επιθέσεις FMS και KoreK. Γνωρίζει τα πρώτα \(l=3\) bytes όλων των κλειδιών ανά πακέτο. Τώρα εξετάζει την \(F_{ptw_{m}}\) για κάθε πακέτο και για κάθε m \(\in \left \{ 1,…,13 \right \}\) και παίρνει ψήφους για \(\sigma _{0},…,\sigma _{12}\). Μόλις επεξεργαστεί όλα τα πακέτα, το root key που απορρέει υπολογίζεται χρησιμοποιώντας \(Rk[0]=\sigma_{0}\) και \(Rk[i]=\sigma _{i}-\sigma _{i-1}\). Αν το κλειδί είναι σωστό, λαμβάνεται μια εναλλακτική απόφαση για μια από τις τιμές του \(\sigma_{i}\) και αναβαθμίζεται το κλειδί χρησιμοποιώντας 12 αφαιρέσεις χωρίς να υπάρχει ανάγκη για επανεξέταση όλων των πακέτων.

Η επίθεση χρειάζεται περίπου 35.000 με 40.000 πακέτα για ποσοστό επιτυχίας 50%, τα οποία μπορούν να συλλεχθούν σε λιγότερο από 1 λεπτό αν το δίκτυο είναι γρήγορο. Η CPU χρειάζεται μόλις μερικά δευτερόλεπτα για να εκτελέσει την επίθεση.

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

 

Leave a Reply

Your email address will not be published. Required fields are marked *