Score:2

1st round attack on rc4

bj flag

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])
        key.append(ki)

    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)
        else:
            self.cipher = ARC4.new(self.IV + self.main_key)

    def call(self):
        return self.cipher.encrypt(b"\x00")[0]
```
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.