Key Recovery from State Information - RC4: Stream Cipher and Its Variants - page 106

Input: S N , j N , P, S and B.
Output: The recovered key bytes K[0],K[1],...,K[l−1] or FAIL.

Guess the Left Half-Key:
for u = 1 to t do
Iteratively guess {K[i u−1 + 1],...,K[i u ]}\P;
T i u

{K[0],...,K[i u ]} : the tuple pass the filter i u

← ;

end

Guess the Right Half-Key:
for v =1 to t ′ do
Iteratively guess {K[i ′ v + 1],...,K[i ′ v−1 ]}\P;
T i v

{K[i ′ v + 1],...,K[l−1]} : the tuple pass the filter i v

← ;

end

Merge to Get the Full Key:
L←{K[i t + 1],...,K[i t+1 ]}\P and
R ←{K[i t ′ +1 + 1],...,K[i t ′ ]}\P;
if |L| <|R| then
Guess L;
T i t+1

← {K[0],...,K[i t+1 ]} : the tuple pass the filter i t+1 ;

Guess R\T i t+1 using the filter i t ′ +1 ;
end
else
Guess R;
T i t ′ +1 {K[i t ′ + 1],...,K[l−1]} : the tuple pass the filter i v ← ;

L\T i t ′ +1 using the filter i t+1 ;
end

Cross-Filtration:
if K[0...m−1] is guessed from the left filters and K[m...l−1] is
guessed from the right filters then
then validate K[m...l−1] using the left filters up to l−1 and
validate K[0...m−1] using the right filters up to N −1−l;
end

Algorithm 4.7.1: BidirKeySearch