Break Repeating Key XOR

In [ ]:

    

function englishiness(ptarray::Array{UInt8, 1})
EnglishFrequencies = Dict( # from http://scottbryce.com/cryptograms/stats.htm
    'e'=>12.51, 
    't'=>9.25,
    'a'=>8.04,
    'o'=>7.6,
    'i'=>7.26,
    'n'=>7.09,
    's'=>6.54,
    'r'=>6.12,
    'h'=>5.49,
    'l'=>4.14,
    'd'=>3.99,
    'c'=>3.06,
    'u'=>2.71,
    'm'=>2.53,
    'f'=>2.3,
    'p'=>2.0,
    'g'=>1.96,
    'w'=>1.92,
    'y'=>1.73,
    'b'=>1.54,
    'v'=>0.99,
    'k'=>0.67,
    'x'=>0.19,
    'j'=>0.16,
    'q'=>0.11,
    'z'=>0.09,
    )
    s=0
    for ll in ptarray
        llchar = Char(ll)
        if isalpha(llchar)
            s+=get(EnglishFrequencies, lowercase(llchar), -5)
        else
            s+=-20
        end
    end
    return s
end
function genBestSingleByteXORDecrypt(ctbytes::Array{UInt8, 1})
    bestdecrypt = []
    bestscore = -Inf
    bestkey = 0x00
    for xx in 0x00:0xff
        if isascii(Char(xx))
            ptbytes = ctbytes $ xx
            ptscore = englishiness(ptbytes)
            if ptscore > bestscore
                bestscore = ptscore
                bestdecrypt = ptbytes
                bestkey = xx
            end
        end
    end
    return (bestscore, bestdecrypt, bestkey)
end;


    

In [ ]:

    

function stringToBytes(X::String)
    return [UInt8(X[ii]) for ii in 1:length(X)]
end;


    

In [ ]:

    

function hammingDistance(a::Array{UInt8,1}, b::Array{UInt8,1})
    differentbits = a $ b
    d = 0
    for ii in 1:length(differentbits)
        c = bits(differentbits[ii])
        for jj in 1:8
            if c[jj] == '1'
                d+=1
            end
        end
    end
    return d
end

function hammingDistance(a::String, b::String)
    return hammingDistance(stringToBytes(a), stringToBytes(b))
end;


    

In [ ]:

    

function repeatToLength(a::Array{UInt8,1}, len::Int64)
    if len < length(a)
        return a[1:len]
    else
        b = repeat(a, outer=convert(Int64, ceil(len / length(a))))
        return b[1:len]
    end
end
function repeatingKeyXOR(pt::Array{UInt8,1}, key::Array{UInt8,1})
    return pt $ repeatToLength(key, length(pt))
end;


    

In [ ]:

    

a = "this is a test"
b = "wokka wokka!!!";


    

In [ ]:

    

abytes = stringToBytes(a)
bbytes = stringToBytes(b);


    

In [ ]:

    

hammingDistance(abytes, bbytes)


    

In [ ]:

    

hammingDistance(a,b)


    

In [ ]:

    

cipher2 = read("6.txt");


    

In [ ]:

    

cipherbytes = base64decode(String(cipher2));


    

In [ ]:

    

dists = []
for kk in 1:40
    d = 0
    nblocks = 10
    for bb in 1:nblocks
        d += hammingDistance(cipherbytes[(1+(kk*(bb-1))):(kk*bb)], cipherbytes[(kk*bb+1):(kk*(bb+1))])
    end
    d = d / nblocks / kk
    push!(dists, (kk, d))
end;


    

In [ ]:

    

sort!(dists,lt=(x,y)->x[2]<y[2])


    

In [ ]:

    

keysize = dists[1][1]
nbytes = length(cipherbytes)
decryptkey = Array{UInt8,1}()
for ii in 1:keysize
    block = cipherbytes[ii:keysize:nbytes]
    (score, ptbytes, key) = genBestSingleByteXORDecrypt(block);
    push!(decryptkey, key)
end
fullptbytes = repeatingKeyXOR(cipherbytes, decryptkey);


    

In [ ]:

    

String(decryptkey)


    

In [ ]:

    

String(fullptbytes)