I'm trying to implement the 1st round attack on RC4 stream cipher according to Attacks on the RC4 stream cipher. For now I am interested in section 4.2 Attack on other key bytes. It works really fine for all the bytes of the random key of length 8, except the 2nd byte. The needed value t is always the second frequent one, whereas the most frequent is 2, which corresponds to the second byte of stream equals 0.
I can't come up with the right answer. I've followed the paper properly, and all the probability calculations seem very strong to me.

Here I attach my own implementation:

def get_appr_sessions(n: int):
    return 3 * ceil(17 * n * log(n))

def recover_kth(key: list[int], n: int, k: int, t: int):
    j = 0
    s = [_ for _ in range(n)]
    for i in range(k):
        j = (j + s[i] + key[i]) % n
        s[j], s[i] = s[i], s[j]

    jk = s.index(t)
    return (jk - j - s[k]) % 256

def attack_iv_follows_key(n: int, keylen: int, guess: int):
    key = [guess]

    tfreqs = [dict() for _ in range(keylen)]
    ts = [(0, 0) for _ in range(keylen)]

    for _ in range(get_appr_sessions(n)):
        o = Oracle(True)                 # True means that IV follows the main key
        for i in range(1, keylen):
            ti = (i - o.call()) % n
            tfreqs[i].setdefault(ti, 0)
            tfreqs[i][ti] += 1

            if tfreqs[i][ti] > ts[i][1] and ti != 2:  # ti == 2 is the case from my question
                ts[i] = (ti, tfreqs[i][ti])
#    for fr in tfreqs:
#        print(sorted(list(fr.items()), key=lambda x: x[1], reverse=True)[:10])
#    print(ts[:10])
    for i in range(1, keylen):
        ki = recover_kth(key, n, i, ts[i][0])

    print(key, ts, bytes(key))

class Oracle:
    #main_key: bytes = b"zemarin"
    main_key: bytes = b'O\x89\xbd\xb1\x9de\xe6'

    def __init__(self, pre: bool):
        self.IV = urandom(64 - len(self.main_key))
        if pre:
            self.cipher = ARC4.new(self.main_key + self.IV)
            self.cipher = ARC4.new(self.IV + self.main_key)

    def call(self):
        return self.cipher.encrypt(b"\x00")[0]


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.