To find possible key sizes for an encrypted message, I break the message into blocks with length s,

blocks :: String -> Int -> [String]
blocks s n = (take n s) : blocks (drop n s) n  

for each such partition find the average Hamming distance (normalised by the block's length) between any 2 of the blocks and find the key for which this average is the smallest

Some helping functions that I use

--unpack :: ByteString -> [Word8] 

packStr :: String -> B.ByteString
packStr = encodeUtf8 . T.pack

toBin' 0 = []
toBin' n = let (q,r) = n `divMod` 2 in r : toBin' q

toBin 0 = [0]
toBin n = reverse (toBin' n)

toInt s = map (\n -> read n :: Int) (map show s)
-- to built all possible pairs
combs :: Int -> [a] -> [[a]]
combs _ []     = []
combs 0 _      = []
combs 1 x      = L.map (:[]) x
combs n (x:xs) = (L.map (x:) (combs (n-1) xs) ) ++ combs n xs   

Normalised Hamming distance(s): (count amount of '1' in binary code. the famous "this is a test" "wokka wokka!!!" distance is 37)

-- normalised (by keysize) hamming distance
nHamming :: String -> String -> Double
nHamming s t = (fromIntegral (length $ filter (\c -> c == 1) $ concat $ map toBin . toInt $ zipWith 
xor (B.unpack (packStr s)) (B.unpack (packStr t)))) / (minLength s t) where minLength s t = 
fromIntegral $ min (length s) (length t)

-- returns list of normalised (by keysize) hamming distances for all possible pairs of blocks for a 
given keysize (which is the length of blocks)
alham :: [String] -> [Double]
alham ss = map (\[x, y] -> nHamming x y) (combs 2 ss)

-- calculates the average = sum of hamming distances / amount
edham :: [String] -> Double
edham [] = 0.0
edham s  = (sum (alham s)) / (fromIntegral ((length s) * ((length s) -1)) )

and choose n for which this average is the smallest:

keyLengths s = let n = fromIntegral (length s) in take n [1..]

-- returns keys with their result in ascending order
posKeys :: String -> [(Double, Int)]
posKeys s = L.sortBy (on compare fst) $ zip (map edham (map (blocks s) (keyLengths s))) [1..]

Now, if I, for example, encode a message with a key "key", the logic says that if I apply posKey to the encrypted message the result should have 3 at least between 3 smallest. Yet it is not so - I keep getting some bug numbers as 66 or 54 (at least they are divisible by 3 :) ). I cannot understand what I have missed in my solution. Would appreciate your help!

The algorithm:

  1. Cut the message into blocks of length n, for all n from 1 to (length of the message)

  2. For each such partition, calculate the Hammering distance (divided by the length of block) for any 2 blocks from that partition

  3. Sum the values from the previous step and divide by m*(m-1), where m is the number of blocks in the partition.

  4. Choose the n with the smallest result for step 3.

The way I understand what is going on, this algorithm should work. Yet it doesn't, and the n corresponding to the actual key does not give the smallest result.

  • $\begingroup$ Could you describe the algorithm that you use to find the key size and where you are unsure of that algorithm? Note that this is not a programming Q/A site, so questions about the implementation of the algorithm are not on topic here. $\endgroup$ – Maarten Bodewes Dec 18 '19 at 20:27
  • $\begingroup$ @Maarten-reinstateMonica, I have added the description to the question $\endgroup$ – arryn Dec 18 '19 at 20:46
  • $\begingroup$ Right. OK, so final mod question: are you wondering why the algorithm doesn't work (meaning that you trust your implementation is correct) or are you wondering why the algorithm doesn't work? Do you understand that statistical properties may not manifest themselves if the sample size is (too) small? $\endgroup$ – Maarten Bodewes Dec 18 '19 at 20:54
  • $\begingroup$ @Maarten-reinstateMonica how long should the sample be? I've tried different lengths $\endgroup$ – arryn Dec 18 '19 at 22:04
  • 1
    $\begingroup$ Yes, I think that's the best way of going about it. Note that cracking a cipher is not necessarily exact science, so if you only have a candidate or two for the key size you can certainly try them all. $\endgroup$ – Maarten Bodewes Dec 19 '19 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.