Correlation A_s13

Ας υποθέσουμε πως ισχύουν οι ακόλουθες συνθήκες:
\[S_{l}[1]=l\]
\(X[0]=l\)

 

Αν το \(S_{l}[1]\) δεν συμμετάσχει σε καμία αντιμετάθεση (swap) για το υπόλοιπο του RC4-KSA, θα συμβεί στο RC4-PRGA το εξής:

  • Το \(i\) θα πάρει την τιμή \(1\)
  • Το \(j\) θα πάρει την τιμή \(l\)
  • Τα \(S_{n}[1]\) και \(S_{n}[l]\) θα αντιμετατεθούν οπότε έχουμε \(S_{n+1}[l]=l\) ενώ το \(S_{n+1}[1]\) παραμένει άγνωστο.


Αν το output τώρα είναι \(X[0]=l\), θα σημαίνει ότι το \(S_{n+1}[l]+S_{n+1}[1]\) θα πρέπει να μας έχει δείξει την τιμή του \(S_{n+1}[l]\) και έτσι, τα \(S_{n+1}[1]\) και \(S_{n}[l]\) θα πρέπει να ήταν 0.

Αν το \(S_{l}[l]\) δεν συμμετείχε σε καμία αντιμετάθεση μετά το βήμα \(l+1\) στο RC4-KSA, τότε το \(j_{l+1}\) θα πρέπει να μας είχε δείξει στο 0 στο \(S_{l}\), το οποίο ύστερα αντιμετατέθηκε στο \(S_{l+1}[l]\). Έτσι, παίρνουμε την φόρμουλα:

\[S_{l}^{-1}[0]=j_{l+1}=j_{l}+S_{l}[l]+K[l]\]
Λύνοντάς της για \(K[l]\), παίρνουμε της εξής συνάρτηση:
\[F_{korekAs13}\left ( K[0],…,K[l-1] \right )=S_{l}^{-1}[0]-j_{l}-S_{l}[l]\]
Η συνάρτηση \(F_{korekAs13}\) αυτή καθ’ αυτή δεν εξαρτάται από το \(X[0]\), αλλά το \(X[0]\) είναι απαραίτητο για να τσεκάρουμε αν η συνθήκη \(X[0]=0\) ισχύει.

Αν ούτε το \(S_{l}[1]\) ούτε το \(S_{l+1}[l]\) δεν συμμετάσχει σε κανένα από τα υπόλοιπα βήματα του RC4-KSA, η \(F_{korekAs13}\) θα πάρει τη τιμή \(K[l]\). Η πιθανότητα για να συμβεί αυτό είναι:

σε ένα βήμα του RC4-KSA: \(\frac{n-2}{n}\)
σε όλα τα υπόλοιπα βήματα: \(\left (\frac{n-2}{n} \right )^{n-l}\)

Πρόκειται για μεγαλύτερη πιθανότητα επιτυχίας απ’ την επίθεση FMS που χρειαζόταν 3 αντί για 2 τιμές να μην μεταβληθούν για το υπόλοιπο του RC4-KSA. Αυτό μεταφράζεται σε περίπου \(13,75\)% πιθανότητες για \(n=256\) και \(l=3\), καθώς και περίπου \(15,75\)% για \(n=256\) και \(l=15\) που είναι οι περιπτώσεις του πρώτου και του τελευταίου byte του κλειδιού αντίστοιχα, για ένα κλείδωμα WEP με 104 bits.
 

Παράδειγμα:

Ας υποθέσουμε ότι έχουμε δώσει το κλειδί \(K=7,251,14,243,201,222,52,166\) στο RC4 και ο επιτιθέμενος γνωρίζει τα πρώτα \(l=3\) bytes του κλειδιού. Πρέπει τώρα να προσπαθήσει να βρει το επόμενο byte, δηλαδή το \(K=[3]\).

Στο επόμενο βήμα, έχουμε \(j_{4}=j_{3}+S_{3}[3]+K[3]=19+1+243=7\) πόντους στο \(S_{3}[7]=0\) και το \(S_{3}[7]=0\) αντιμετατίθεται με το \(S_{3}[3]=1\). Τα \(S_{3}[1]=3\) και \(S_{4}[3]=0\) παραμένουν ανέπαφα κατά την διάρκεια του υπόλοιπου του RC4-KSA. Στην αρχή του RC4-PRGA, το \(S_{n}[1]=3\) αντιμετατίθεται με το \(S_{n}[3]=3\), παίρνουμε \(S_{n+1}[1]+S_{n+1}[3]=3\) πόντους στο \(S_{n+1}[3]=3\) και παράγεται το πρώτο byte του output \(Χ[0]=3\). Οι παρακάτω εικόνες αναπαριστούν αυτά τα βήματα:

Correlation A_s13 figure 1
Τα πρώτα 4 βήματα του RC4-KSA για \(K=7,251,14,243,201,222,52,166\)
 
Correlation A_s13 figure 2
Το πρώτο byte του output για \(K=7,251,14,243,201,222,52,166\)

 

Ο επιτιθέμενος που θα υπολόγιζε το:
\begin{align}
F_{korekAs13}\left ( 7,251,14,3 \right )&=S_{3}^{-1}[0]-j_{3}-S_{3}[3] \\
&=7-19-1 \\
&=243
\end{align}
θα μπορούσε να πάρει την σωστή τιμή για το \(K[3]\).

 

Leave a Reply

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