Correlation A_neg

Το correlation A_neg είναι κάπως… ανορθόδοξο και γι’ αυτό ίσως έχει κερδίσει τις εντυπώσεις. Ας υποθέσουμε ότι ισχύουν οι ακόλουθες συνθήκες:

  1. \(S_{l}[1]=2\)
  2. \(S_{l}[2]=0\)
  3. \(X[0]=2\)

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

  1. \(K[l] \neq 1-S_{l}[l]-j_{l}\)
  2. \(K[l] \neq 2-S_{l}[l]-j_{l}\)

Ακόμα κι αν μια απ’ αυτές τις τιμές αλλάξει κατά την διάρκεια του υπολοίπου RC4-KSA, είναι πολύ πιθανό το output να είναι κάτι διαφορετικό από 2.

Για να πάρουμε μια εκτίμηση για το πόσο καλές είναι αυτές οι υποθέσεις, θα χρησιμοποιήσουμε το ακόλουθο μοντέλο:

  • Με πιθανότητα \(\left ( \frac{n-2}{n} \right )^{n-l}\), αυτές οι 2 τιμές θα παραμείνουν ανέπαφες για το υπόλοιπο του RC4-KSA και το output θα είναι \(X[0]=2\).
  • Με πιθανότητα \(1-\left ( \frac{n-2}{n} \right )^{n-l}\), τουλάχιστον μία απ’ αυτές τις τιμές θα μεταβληθεί στο υπόλοιπο του RC4-KSA. Στην εντελώς τυχαία εκδοχή του RC4-PRGA, η πρώτη λέξη του output θα είναι 2 με πιθανότητα \( \frac{1}{n}\) και αυτό είναι ανεξάρτητο από το τι συμβαίνει στο προηγούμενο RC4-KSA.

Άρα, η πιθανότητα το RC4-PRGA να έχει το 2 σαν πρώτη λέξη του output είναι:

\[\left ( \frac{n-2}{n} \right )^{n-l}+\left ( 1-\left ( \frac{n-2}{n} \right )^{n-l} \right )\cdot \frac{1}{n}\]

Αυτό μας οδηγεί στο ακόλουθο κλάσμα που μας λέει ποιες είναι οι πιθανότητες το \(S[1]\) και το \(S[2]\) να παραμείνουν ανέπαφα αν η πρώτη λέξη του output του PRC4-PRGA είναι 2:

\[\frac{\left ( \frac{n-2}{n} \right )^{n-l}}{\left ( \frac{n-2}{n} \right )^{n-l}+\left ( 1-\left ( \frac{n-2}{n} \right )^{n-l} \right )\cdot \frac{1}{n}}\]

Για \(l=3\) και \(n=256\), το κλάσμα μας δίνει 97,61% πιθανότητα και για \(l=15\) και \(n=256\) μας δίνει 97,85% που είναι ουσιαστικά οι πιθανότητες για το πρώτο και το τελευταίο byte του κλειδιού για ένα 104-bit WEP. Ο KoreK βρήκε επίσης κάποια ακόμα κριτήρια τα οποία μπορούν να εξαιρέσουν συγκεκριμένες τιμές από το να είναι το επόμενο byte του κλειδιού αλλά θα βγει σεντόνι πάλι το άρθρο και θα με βρίζεις. Άμα μου έρθει η όρεξη, θα το επεκτείνω στο μέλλον. Πάμε λοιπόν στο κλασσικό μας…
 

Παράδειγμα:

Ας υποθέσουμε ότι χρησιμοποιούμε το RC4 με κλειδί \(K=104,153,101,133,126,174,180,135)\) και ο επιτιθέμενος γνωρίζει τα πρώτα \(l=3\) bytes του \(K\). Τώρα θα προσπαθήσει να εξαιρέσει συγκεκριμένες τιμές από πιθανές τιμές του \(K[3]\). Γνωρίζει ότι ισχύουν τα \(S_{3}[1]=2\) και \(S_{3}[2]=0\) και παρατηρεί το \(X[0]\).

 

Correlation A_neg figure 1
Τα πρώτα 4 βήματα του KSA για \(K=104,153,101,133,126,174,180,135\)
 

Μετά το 3ο βήμα του RC4-KSA, έχουμε \(j_{3}=104\) και το \(i\) δείχνει στο \(S_{3}[3]=3\). Μόνο αν \(K[3]=150\) ή \(K[3]=151\) θα μπορούσε να οδηγήσει σε αλλαγή του \(S[1]\) ή του \(S[2]\) στο 4ο βήμα αλλά όπως φαίνεται στο σχήμα, \(K=133\). Για το υπόλοιπο του RC4-KSA, παραμένουν απαράλλακτα τα \(S_{3}[1]=2\) και \(S_{3}[2]=0\) και το πρώτο byte του output είναι \(Χ[0]=2\). Έτσι, μπορεί ο επιτιθέμενος να αποκλείσει το 150 και το 151 ως πιθανές τιμές για το \(K[3]\) με αρκετά μεγάλη πιθανότητα επιτυχίας. Στις εικόνες βλέπουμε τα βήματα που περιγράψαμε μέσα στο RC4-KSA και στο RC4-PRGA.

 

Correlation A_neg figure 1
Το πρώτο byte του output για \(K=104,153,101,133,126,174,180,135\)

 
 

Leave a Reply

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