Jenkins’ correlation

Το 1996, ο Robert J. Jenkins δημοσίευσε μια παρατήρηση για το RC4 και τις ιδιότητές του ως random number generator. Ο Jenkins σημείωσε ότι ισχύει:

\[Prob\left ( S\left [ S\left [ i \right ] +S\left [ j \right ] \right ] +S\left [ j \right ] =i \right )=\frac{2}{256}\]

για μια τυχαία εσωτερική κατάσταση του RC4-PRGA. Αυτή η πιθανότητα είναι διπλάσια απ’ αυτή που κάποιος ενστικτωδώς θα περίμενε.

Αυτή η ιδιότητα γενικεύτηκε και αποδείχθηκε αργότερα από διάφορους ερευνητές. Την πιο ακριβή απόδειξη την έδωσε ο Klein ο οποίος έδειξε τις ακόλουθες πιθανότητες:

Έστω \(n\geq 2\) και \(i\in \left \{ 0,…,n-1 \right \}\) αυθαίρετες αλλά σταθερές τιμές. Για κάθε τιμή \(x \in \left \{ 0,…,n-1 \right \}\) και μια τυχαία επιλεγμένη μετάθεση \(S\) των αριθμών \(0,…,n-1\), έχουμε:

\[Prob\left ( S\left [ j \right ] +S\left [ S\left [ j \right ] \right ]=i \hspace{2 mm}| \hspace{2 mm} j=x \right )=\frac{2}{n}\]

και για κάθε τιμή του \(c\in \left \{ 0,…,n-1 \right \}\) με \(c\neq i\) έχουμε:

\[Prob\left ( S\left [ j \right ]+S\left [ S\left [ i \right ]+S\left [ j \right ] \right ]=c \hspace{2 mm} | \hspace{2 mm} j=x \right )=\frac{n-2}{n\left ( n-1 \right )}\]

Απ’ αυτό συμπεραίνουμε ότι ανεξάρτητα από την τιμή \(j\), για κάθε τιμή του \(n\geq 2\) και \(i\in \left \{ 0,…,n-1 \right \}\) και μιας τυχαία επιλεγμένης μετάθεσης των αριθμών \(0,…,n-1\), παίρνουμε την πιθανότητα:

\[Prob\left ( S\left [ j \right ]+S\left [ S\left [ i \right ]+S\left [ j \right ] \right ]=i \right )=\frac{2}{n}\]

Και για κάθε τιμή του \(c\in \left \{ 0,…,n-1 \right \}\) με \(c\neq i\) έχουμε:

\[Prob\left ( S\left [ j \right ]+S\left [ S\left [ i \right ]+S\left [ j \right ] \right ]=c \right )=\frac{n-2}{n\left ( n-1 \right )}\]

Έτσι μπορούμε να συλλέξουμε πληροφορίες σχετικά με την εσωτερική κατάσταση του stream cipher του RC4. Ας υποθέσουμε ότι παρατηρούμε ένα output

\[X\left [ l \right ]=S_{n+l+1}\left [ S_{n+l+1}\left [ l+1 \right ]+S_{n+l+1}\left [ j_{n+l+1} \right ] \right ]\]

Ξέρουμε πλέον ότι:

\begin{align}
Prob\left ( S_{n+l+1}\left [ j_{n+l+1} \right ]+X\left [ l \right ] =l+1 \right )&=\frac{2}{n} \\
Prob\left ( S_{n+l+1}\left [ j_{n+l+1} \right ] =l+1-X\left [ l \right ] \right )&=\frac{2}{n}
\end{align}

και για κάθε \(c\neq S_{n+l+1}\left [ j_{n+l+1} \right ]\):

\[Prob\left ( c=l+1-X\left [ l \right ] \right )=\frac{n-2}{n\left ( n-1 \right )}\]

και ξέρουμε ότι το \(S_{n+l+1}\left [ j_{n+l+1} \right ]\) μόλις αντιμετέθηκε με το \(S_{n+l}[l+1]\) οπότε μπορούμε να ξαναγράψουμε τις εξισώσεις ως:

\begin{align}
Prob\left ( S_{n+l}[l+1]=l+1-X\left [ l \right ] \right )&=\frac{2}{n} \\
Prob\left ( c=l+1-X\left [ l \right ] \right )&=\frac{n-2}{n\left ( n-1 \right )}
\end{align}

 

Leave a Reply

Your email address will not be published.