Need help finding keysize for Vigenere cipher

Question

I am doing a crypto challenge for breaking a Vigenere style repeating XOR encryption (https://cryptopals.com/sets/1/challenges/6).

I have looked at similar questions asked here, mainly this one: Finding a keylength in a repeating key XOR cipher But I am still unabe to determine whats the best way to find the length of encryption key.

I have a Base64 text (which I converted into hexadecimal value) that has been encrypted using repeating XOR encryption (a key of unknown size was repeated and sequentially XOR-ed across bytes of the plaintext).

The challenge suggests taking first and second keysize worth of bytes (for each keysize in some range) and counting Hamming or edit distance between them (and normalizing them by dividing by keysize). And that keysize with lowest distance should be the length of the key (no explanation is given why this should work, and I dont quite understand it). I have tried this method, but unfortunately I am not getting the correct keysize. Here's my pseudocode

for keysize in 2..100:
    a = bytes[0:keysize]
    b = bytes[keysize:(2*keysize)]
    score = hamming_distance(a,b) / (8*keysize) // mult by 8 since each byte is 8 bit and edit distance is counted by bits

(I tested this on my own encrypted message which I encrypted with keysize: 3 and it did not give me the correct result)

I have also tried calculating edit distance across several adjacent keysize worth of bytes and then averaging them (like the answer on linked post suggested), but that too didn't work.

I also tried doing Friedman's test, but later realized that this couldn't really work in my case as encrypted message consists of random binary characters, not 26 English alphabet letters.

What is the best approach for finding the correct keysize?

Answer 1

For the explanation to why this approach works I found an excellent answer here: repeating-key xor and hamming distance

And I managed to finally find the correct keysize using the following pseudocode:

dictionary = () // dict or hashmap which stores <Keysize, Score> as <K,V> pair
for keysize in 2..max_keysize:
    n = 0, score = 0
    while True:
         if 2*keysize >= bytes.len():
             break
         a = bytes[:keysize]
         b = bytes[keysize:2*keysize]
         score += (hamming_distance(a,b) / (8*keysize))
         n += 1
    averaged_score = score / n
    dictionary.add(keysize, averaged_score)

And finally you select keyisze with lowest averaged_score