Correlation A_s3

Αυτή η επίθεση μοιάζει πολύ με την επίθεση FMS αλλά αντί για το \(X[0]\), χρησιμοποιούμε το \(X[1]\) για να πάρουμε πληροφορίες για το \(K[l]\).

Θεωρούμε ότι ισχύουν οι ακόλουθες συνθήκες:

  1. \(S_{l}[1] \neq 2\)
  2. \(S_{l}[2] \neq 0\)
  3. \(S_{l}[1] < l\)
  4. \(S_{l}[2] < l\)
  5. \(S_{l}[1]+S_{l}[2] < l\)
  6. \(S_{l}[2]+S_{l}\left [ S_{l}[1]+S_{l}[2] \right ]=l\)
  7. \(S_{l}^{-1}[X[1]]\neq 1\)
  8. \(S_{l}^{-1}[X[1]]\neq 2\)
  9. \(S_{l}^{-1}[X[1]]\neq S_{l}[1]+S_{l}[2]\)

 
Όπως και στην επίθεση FMS, το \(S_{l}\left [ j_{l}+S_{l}[l]+K[l] \right ]\) μετατίθεται στο \(S_{l+1}[l]\). Αν κανένα από τα \(S_{l}[1], S_{l}[2]\) και \(S_{l+1}[l]\) δεν συμμετάσχει σε καμία αντιμετάθεση (swap) στο υπόλοιπο του RC4-KSA, στα επόμενα δύο βήματα του RC4-PRGA θα συμβεί το εξής:
 

  1. Το \(i\) παίρνει τιμή 1.
  2. Το \(j_{n+1}\) παίρνει την τιμή του \(S_{n}[1]\).
  3. Τα \(S_{n}[1]\) και \(S_{n} \left [ S_{n}[1] \right ]\) αντιμετατίθενται. Επειδή \(S_{n}[1] \neq 2\) και \(S_{n}[1] < l\), δεν θα επηρεαστεί ούτε το \(S_{n+1}[2]\) ούτε το \(S_{n+1}[l]\). Επειδή \(S_{n}[2] \neq 0\), δεν θα επηρεαστεί το \(S_{n+1}\left [ S_{n}[1]+S_{n}[2] \right ]\).
  4. Παράγεται το πρώτο output \(X[0]=S_{n+1}\left [ S_{n+1}[1]+S_{n+1}[S_{n}[1]] \right ]\) αλλά δεν το χρησιμοποιούμε για την επίθεση.
  5. Το \(i\) παίρνει τιμή 2.
  6. To \(j_{n+2}\) παίρνει τιμή \(j_{n+1}+S_{n+1}[2]=S_{n}[1]+S_{n}[2]\). Επειδή \(S_{n}[1]+S_{n}[2] < l\), τότε \(j_{n+2} < l\).
  7. Τα \(S_{n+1}[2]\) και \(S_{n+1} \left [ S_{n}[1]+S_{n}[2] \right ]\) αντιμετατίθενται. Επειδή \(S_{n}[1]+S{n}[2] < l\), δεν θα επηρεαστεί το \(S_{n+2}[l]\) ούτε το sum \(S_{n+2}[2]+S_{n+2} \left [S_{n+2}[1]+S_{n+2}[2] \right ]\), το οποίο παραμένει \(l\).
  8. Τώρα παράγεται το δεύτερο output που είναι \(S_{n+2}\left [ S_{n+2}[2]+S_{n+2}\left [ S_{n+2}[1]+S_{n+2}[2] \right ] \right ]=S_{n+2}[l]=S_{l}\left [ j_{l}+S_{l}[l]+K[l] \right ]\). Αν ισχύει ότι \(S_{l}^{-1}[X[1]]=1\) ή \(S_{l}^{-1}[X[1]]=2\) ή \(S_{l}^{-1}[X[1]]=S_{l}[1]+S_{l}[2]\), τότε ξέρουμε ότι το \(S[1]\) ή το \(S[2]\) ή το \(S \left [ S[1]+S[2] \right ]\) έχει τροποποιηθεί κατά την διάρκεια του υπολοίπου του RC4-KSA.

 
Λύνοντας την εξίσωση ως προς \(K[l]\), παίρνουμε το εξής αποτέλεσμα:
\[F_{korekAs3}\left ( K[0],…,K[l-1],X[1] \right )=S_{l}^{-1}\left [ X[1] \right ]-j_{l}-S_{l}[l]\]

Οι πιθανότητες επιτυχίας είναι τόσο καλές όσο και της επίθεσης FMS.

Η συγκεκριμένη επίθεση ανακαλύφθηκε από τον Δαβίδ Χαλτονίδη, κατά κόσμον David Hulton και έχει ιδιαίτερο ενδιαφέρον γιατί δείχνει ότι προσπερνώντας το πρώτο output (την πρώτη λεξη) του RC4-PRGA, δεν αποτρέπει επιθέσεις σε διεργασίες που μοιάζουν με αυτές του WEP.

Ακόμα κι αν ο KoreK χρησιμοποιούσε μόνο τις πρώτες δύο λέξεις του output από το RC4-PRGA, η ιδέα πίσω απ’ αυτή την επίθεση (καθώς και μερικών άλλων επιθέσεων του KoreK) θα μπορούσε να επεκταθεί σε μια επίθεση που να χρησιμοποιεί μόνο την τρίτη λέξη του output του RC4-PRGA. Αυτή η επίθεση όμως θα απαιτούσε περισσότερες τιμές να μην αλλάξουν στο υπόλοιπο του RC4-KSA με αποτέλεσμα χαμηλότερη πιθανότητα επιτυχίας. Για παράδειγμα, η πιθανότητα τέσσερις διαφορετικές τιμές να μείνουν απαράλλακτες ως προς \(j\) για 252 βήματα στο RC4-KSA, είναι περίπου 2%.
 

Παράδειγμα:

Ας υποθέσουμε ότι δίνεται στο RC4 το κλειδί \(K=220,255,36,86,169,80,173,194\). Ο επιτιθέμενος γνωρίζει τα πρώτα \(l=4\) bytes του \(K\) και προσπαθεί τώρα να βρει το \(K[4]\). Μπορεί να προσομοιώσει τα πρώτα 4 βήματα του RC4-KSA κι επειδή μπορεί, θα το κάνει!

Στο 5ο βήμα του RC4-PRGA, το \(j_{n+1}\) παίρνει τιμή \(0\) και το \(S_{n}[1]\) αντιμετατίθεται με το \(S_{n}[0]\). Η αντιμετάθεση αυτή δεν επηρεάζει ούτε το \(S[2]\) ούτε το \(S[4]\). Τώρα το \(S_{n+1}[2]\) προστίθεται στο \(j\) κι έτσι \(j_{n+2}=2\). Το δεύτερο byte του output είναι τώρα \(S_{n+2}\left [ S_{n+2}[2]+S_{n+2}[2] \right ]=S_{n+2}[4]=8\) και αποκαλύπτει το byte του κλειδιού \(K[4]=169\) χρησιμοποιώντας:

\begin{align}
F_{korekAs3}(220,255,36,86,8)&=S_{4}^{-1}\left [ X[1] \right ]-j_{4}-S_{4}[4] \\
&=S_{4}^{-1}[8]-91-4 \\
&=169
\end{align}

Correlation A_s3 figure 1
Τα πρώτα 5 βήματα του RC4-KSA για \(K=220,255,36,86,169,80,173,194\)
 
Correlation A_s3 figure 2
Τα πρώτα δύο bytes του output για \(K=220,255,36,86,169,80,173,194\)

 

Leave a Reply

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