davehull/XOR Brutr Output

## XOR Brutr Output
I've been playing around with Matasano Crypto Challenges for my own edification.
It's been fun and insightful. I've learned a number of new things and enjoyed
doing so. If you're a mediocre programmer like me and have an interest in crypto,
I highly recommend checking out the challenges -- http://cryptopals.com/.

A few of the exercises in set 1 have you playing around with XOR for encryption.
You create a script that can brute force single key decryption and if you're
ambitious you'll write a function that will examine letter frequencies of the
output and score the results, returning the one that is most likely to be
English. I wrote multiple scoring functions for this, one that counts English
letter frequencies, one that counts English bigram frequencies, one for trigram
frequencies and lastly one that calculates Shannon Entropy. The output of these
functions all make up the composite score.

Later you have to write a XOR brute force decryption program that first applies
Hamming Distances at the bit level, which equates to calculating the Index of
Coincidence over the ciphertext, all in an effort to determine the size of the
XOR key used to encrypt the data. Here I stumbled a bit. First I didn't pay
careful enough attention and missed that the given ciphertext was base64 encoded.
I also didn't get the math quite right for building my byte arrays on which the
Hamming Distance would be calculated. But I eventually resolved those isses
after a day of banging my head on the desk trying to figure out what the issue
was.

Now I have a XOR brute force tool that can reliably calculate key size... well,
to an extent. These calculations are about probabilities not certainties, but
one thing I noticed right away was that longer keys are easier to calculate
with greater certainty, while shorter keys are more difficult. Here's some output
from my script that will show what I mean. I found it fascinating, but I've also
not been getting sufficient sleep of late -- thank you Matasano.

First, let's set a variable for our plaintext:
$data = "Dennis Fisher talks with Dan Kaminsky about the VENOM bug, the value of
virtual machine escapes, why everyone wants to make every bug the worst one of
all time or just a bunch of hype and what the Avengers have to do with
vulnerability disclosure."

Next, let's set our key:
$key = "eatoin shrdlu"

$key.length
13

Let's XOR encrypt our plaintext with the key and get $cipherText:
$cipherText = .\XOR-Encrypt.ps1 -String $data -key $key
$cipherText (line breaks added)
21041a01001d003501010c090745151503021d000401060c4c31040f54240803491d1b191d4c14
070e011b491a4816482421223a2841161a0e4200070017441a140914114f060800050100101914
0941190e0a06491d0d52011f160411111c454e571b1152011a1017181b010c4e57120606174c01
0a41190e020b00161e171615550714134f1d0645531f1d161f01450e1a0a49014653091e084c01
0c0c114f061c00191d01104c14450301010a06001c0e520c1505004115010d4e571b090644181d
004135190c0047161a014404141304541b064e441c48050d181d45170103070b52120a1b080501
1c4110061a0d4c1c1b0716095b

Let's run this through the XOR brute forcer to see what it says about the key
size:
XOR-Brutr.ps1 -MaxKeySize 40 -String $cipherText -Encoding base16 | Sort-Object AvgDist | ft * -AutoSize
KeySize          AvgDist
-------          -------
     13 2.74660633484163
     39 2.78461538461538
     26 2.81730769230769
     33  2.8989898989899
     40            2.905
     25             2.93
     38 2.94210526315789
     34 2.94607843137255
     35 2.95714285714286
     29 2.98522167487685
     37 2.99459459459459
     27                3
     28                3
     30 3.00952380952381
     31 3.01075268817204
     23 3.01449275362319
      8 3.01724137931034
     18 3.02314814814815
     22 3.03181818181818
     36 3.03888888888889
     20 3.04090909090909
     10 3.04347826086957
     24  3.0462962962963
     21 3.05238095238095
     14 3.05357142857143
     32 3.07291666666667
     12 3.10087719298246
     19 3.10526315789474
     15 3.10666666666667
     17 3.15837104072398
     16          3.21875
     11 3.23376623376623
      9 3.23931623931624
      5 3.25416666666667
      4 3.42916666666667
      7 3.44957983193277
      6            3.525
      3 3.82716049382716
      2 4.24590163934426

     Beautiful! The result correctly calculates that the key size is 13 bytes, but
     watch what happens with smaller keys.

$key = "eatoin shrdl"
$key.length
12
$cipherText = .\XOR-Encrypt.ps1 -String $data -key $key
XOR-Brutr.ps1 -MaxKeySize 40 -String $cipherText -Encoding base16 | Sort-Object AvgDist | ft * -AutoSize
KeySize          AvgDist
-------          -------
     24 2.58333333333333
     36 2.66111111111111
     38 2.85789473684211
     40            2.915
     19 2.95215311004785
     29 2.97536945812808
     22 3.00909090909091
     16 3.02232142857143
     23 3.03381642512077
     18 3.03703703703704
     37 3.03783783783784
     14 3.05357142857143
     30 3.05714285714286
     32           3.0625
     27 3.06481481481481
     12 3.06578947368421
     28 3.06632653061224
     25             3.08
     33 3.08585858585859
     13  3.1131221719457
      9 3.11965811965812
     31 3.12365591397849
     11 3.13419913419913
     35 3.13809523809524
     34 3.15196078431373
     20 3.15909090909091
     26 3.16826923076923
     39 3.18974358974359
     17 3.19004524886878
     21  3.1952380952381
     10              3.2
     15 3.24444444444444
      8 3.26293103448276
      5 3.35416666666667
      6            3.425
      7 3.50840336134454
      4 3.56666666666667
      3  3.9917695473251
      2 4.61475409836066

Our top result is not 12, but notice the top two results are multiples
of 12 and 12 is significantly higher in the rankings than any key
lengths less than 12. Let's try a shorter key:
$key = "eatoin shrd"
$key.length
11
$cipherText = .\XOR-Encrypt.ps1 -String $data -key $key
XOR-Brutr.ps1 -MaxKeySize 40 -String $cipherText -Encoding base16 | Sort-Object AvgDist | ft * -AutoSize
KeySize          AvgDist
-------          -------
     33 2.69191919191919
     22 2.70909090909091
     11 2.81385281385281
     18 2.97222222222222
     38 2.98421052631579
     23  3.0048309178744
     28 3.06632653061224
     15 3.07111111111111
     39 3.07179487179487
     24  3.0787037037037
     16 3.09821428571429
     31 3.10215053763441
     37 3.11351351351351
     32 3.11458333333333
     36 3.11666666666667
     40             3.12
     17 3.12669683257919
     13 3.12669683257919
     26 3.12980769230769
     35 3.13809523809524
     21 3.13809523809524
     34 3.15686274509804
     20 3.15909090909091
     29 3.17733990147783
     25             3.18
     30 3.18571428571429
     12 3.18859649122807
     27 3.19444444444444
     14 3.20089285714286
     10 3.20434782608696
      8 3.27155172413793
     19 3.27272727272727
      9  3.2948717948718
      7 3.47058823529412
      6 3.59583333333333
      5 3.62083333333333
      4 3.65416666666667
      3 4.12757201646091
      2 4.20491803278689
Again our correct key size is not the top result, but the two top
results are multiples of the correct result and the correct result
follows immediately. What of a smaller key size?

$key = "eatoin sh"
$key.length
9
$cipherText = .\XOR-Encrypt.ps1 -String $data -key $key
XOR-Brutr.ps1 -MaxKeySize 40 -String $cipherText -Encoding base16 | Sort-Object AvgDist | ft * -AutoSize
KeySize          AvgDist
-------          -------
     36 2.66111111111111
     27 2.75925925925926
     31 2.88709677419355
      9  2.8974358974359
     32 2.91666666666667
     38 2.92105263157895
     23 2.93719806763285
     22 2.95909090909091
     29 2.97044334975369
     18 2.99074074074074
     40            3.025
     37 3.02702702702703
     14 3.05803571428571
     30 3.07619047619048
     28  3.0765306122449
     20 3.08181818181818
     35 3.09047619047619
     34 3.10294117647059
     17 3.10407239819005
     26 3.11538461538462
     16 3.11607142857143
     15             3.12
     13 3.13122171945701
     25             3.16
     10 3.17391304347826
     21              3.2
     39 3.20512820512821
     33 3.20707070707071
     19 3.21052631578947
     11 3.22077922077922
     24 3.25925925925926
      5 3.37083333333333
      7 3.39915966386555
     12 3.41228070175439
      8 3.42672413793103
      6 3.45416666666667
      4 3.57916666666667
      3 3.98765432098765
      2 4.45491803278689
Again, not the top result, but the top two are multiples and the
correct result follows closely. This pattern continues for small
keys.
$key = "eatoin s"
$key.length
8
$cipherText = .\XOR-Encrypt.ps1 -String $data -key $key
XOR-Brutr.ps1 -MaxKeySize 40 -String $cipherText -Encoding base16 | Sort-Object AvgDist | ft * -AutoSize
KeySize          AvgDist
-------          -------
     24 2.58333333333333
     40             2.68
     32 2.72916666666667
     16           2.9375
     36 2.98333333333333
     39 2.98974358974359
     20 3.00454545454545
     21 3.00952380952381
     30 3.01428571428571
     34 3.01960784313725
     33 3.02020202020202
     28 3.04081632653061
      8 3.04741379310345
     12 3.08333333333333
     38 3.11052631578947
     29 3.14285714285714
     31 3.16129032258065
     25             3.17
     27 3.17592592592593
     37 3.18918918918919
     18 3.19444444444444
     23 3.19806763285024
     22 3.22272727272727
     19 3.24401913875598
     14 3.25446428571429
     35 3.26190476190476
     17 3.28054298642534
     11 3.28571428571429
     15 3.29777777777778
     13 3.30769230769231
     26 3.31730769230769
      9 3.32905982905983
     10 3.35652173913044
      6 3.36666666666667
      7 3.59663865546219
      4 3.61666666666667
      5           3.6375
      3 3.98353909465021
      2 4.68852459016393

$key = "eato"
$cipherText = .\XOR-Encrypt.ps1 -String $data -key $key
XOR-Brutr.ps1 -MaxKeySize 40 -String $cipherText -Encoding base16 | Sort-Object AvgDist | ft * -AutoSize
KeySize          AvgDist
-------          -------
     24 2.58333333333333
     28 2.64285714285714
     36 2.66111111111111
     40             2.68
     32 2.72916666666667
     20 2.79545454545455
     30 2.85714285714286
     34 2.88725490196078
     16           2.9375
     29 2.94581280788177
     38 2.94736842105263
     39 2.94871794871795
     26 2.96153846153846
     22 3.00909090909091
     35 3.01428571428571
     33 3.02020202020202
     14 3.02232142857143
     27 3.02777777777778
      8 3.04741379310345
     12 3.06578947368421
     31  3.0752688172043
     13 3.09049773755656
     15 3.09333333333333
     21 3.09523809523809
     37 3.11891891891892
     25             3.12
     23  3.1207729468599
     18 3.14814814814815
     17 3.17647058823529
     11 3.17748917748918
     10              3.2
     19 3.21531100478469
      6             3.25
      9 3.28632478632479
      4 3.31666666666667
      7 3.31932773109244
      5 3.57083333333333
      3 3.77366255144033
      2 4.33196721311475

What's the point of posting this? I guess the take away is that if
you're trying to brute force XOR keys by first determining the key
size, you can't automatically take the top result to be the correct
key size. Even Matasano's instructions state that this is about
probability not certainty, but the interesting property that they
don't discuss, probably because they want people to notice on their
own, is that for short keys, the top results may be multiples of
the actual key size, so be mindful of that pattern.
	I've been playing around with Matasano Crypto Challenges for my own edification.
	It's been fun and insightful. I've learned a number of new things and enjoyed
	doing so. If you're a mediocre programmer like me and have an interest in crypto,
	I highly recommend checking out the challenges -- http://cryptopals.com/.

	A few of the exercises in set 1 have you playing around with XOR for encryption.
	You create a script that can brute force single key decryption and if you're
	ambitious you'll write a function that will examine letter frequencies of the
	output and score the results, returning the one that is most likely to be
	English. I wrote multiple scoring functions for this, one that counts English
	letter frequencies, one that counts English bigram frequencies, one for trigram
	frequencies and lastly one that calculates Shannon Entropy. The output of these
	functions all make up the composite score.

	Later you have to write a XOR brute force decryption program that first applies
	Hamming Distances at the bit level, which equates to calculating the Index of
	Coincidence over the ciphertext, all in an effort to determine the size of the
	XOR key used to encrypt the data. Here I stumbled a bit. First I didn't pay
	careful enough attention and missed that the given ciphertext was base64 encoded.
	I also didn't get the math quite right for building my byte arrays on which the
	Hamming Distance would be calculated. But I eventually resolved those isses
	after a day of banging my head on the desk trying to figure out what the issue
	was.

	Now I have a XOR brute force tool that can reliably calculate key size... well,
	to an extent. These calculations are about probabilities not certainties, but
	one thing I noticed right away was that longer keys are easier to calculate
	with greater certainty, while shorter keys are more difficult. Here's some output
	from my script that will show what I mean. I found it fascinating, but I've also
	not been getting sufficient sleep of late -- thank you Matasano.

	First, let's set a variable for our plaintext:
	$data = "Dennis Fisher talks with Dan Kaminsky about the VENOM bug, the value of
	virtual machine escapes, why everyone wants to make every bug the worst one of
	all time or just a bunch of hype and what the Avengers have to do with
	vulnerability disclosure."

	Next, let's set our key:
	$key = "eatoin shrdlu"

	$key.length
	13

	Let's XOR encrypt our plaintext with the key and get $cipherText:
	$cipherText = .\XOR-Encrypt.ps1 -String $data -key $key
	$cipherText (line breaks added)
	21041a01001d003501010c090745151503021d000401060c4c31040f54240803491d1b191d4c14
	070e011b491a4816482421223a2841161a0e4200070017441a140914114f060800050100101914
	0941190e0a06491d0d52011f160411111c454e571b1152011a1017181b010c4e57120606174c01
	0a41190e020b00161e171615550714134f1d0645531f1d161f01450e1a0a49014653091e084c01
	0c0c114f061c00191d01104c14450301010a06001c0e520c1505004115010d4e571b090644181d
	004135190c0047161a014404141304541b064e441c48050d181d45170103070b52120a1b080501
	1c4110061a0d4c1c1b0716095b

	Let's run this through the XOR brute forcer to see what it says about the key
	size:
	XOR-Brutr.ps1 -MaxKeySize 40 -String $cipherText -Encoding base16 \| Sort-Object AvgDist \| ft * -AutoSize
	KeySize AvgDist
	------- -------
	13 2.74660633484163
	39 2.78461538461538
	26 2.81730769230769
	33 2.8989898989899
	40 2.905
	25 2.93
	38 2.94210526315789
	34 2.94607843137255
	35 2.95714285714286
	29 2.98522167487685
	37 2.99459459459459
	27 3
	28 3
	30 3.00952380952381
	31 3.01075268817204
	23 3.01449275362319
	8 3.01724137931034
	18 3.02314814814815
	22 3.03181818181818
	36 3.03888888888889
	20 3.04090909090909
	10 3.04347826086957
	24 3.0462962962963
	21 3.05238095238095
	14 3.05357142857143
	32 3.07291666666667
	12 3.10087719298246
	19 3.10526315789474
	15 3.10666666666667
	17 3.15837104072398
	16 3.21875
	11 3.23376623376623
	9 3.23931623931624
	5 3.25416666666667
	4 3.42916666666667
	7 3.44957983193277
	6 3.525
	3 3.82716049382716
	2 4.24590163934426

	Beautiful! The result correctly calculates that the key size is 13 bytes, but
	watch what happens with smaller keys.

	$key = "eatoin shrdl"
	$key.length
	12
	$cipherText = .\XOR-Encrypt.ps1 -String $data -key $key
	XOR-Brutr.ps1 -MaxKeySize 40 -String $cipherText -Encoding base16 \| Sort-Object AvgDist \| ft * -AutoSize
	KeySize AvgDist
	------- -------
	24 2.58333333333333
	36 2.66111111111111
	38 2.85789473684211
	40 2.915
	19 2.95215311004785
	29 2.97536945812808
	22 3.00909090909091
	16 3.02232142857143
	23 3.03381642512077
	18 3.03703703703704
	37 3.03783783783784
	14 3.05357142857143
	30 3.05714285714286
	32 3.0625
	27 3.06481481481481
	12 3.06578947368421
	28 3.06632653061224
	25 3.08
	33 3.08585858585859
	13 3.1131221719457
	9 3.11965811965812
	31 3.12365591397849
	11 3.13419913419913
	35 3.13809523809524
	34 3.15196078431373
	20 3.15909090909091
	26 3.16826923076923
	39 3.18974358974359
	17 3.19004524886878
	21 3.1952380952381
	10 3.2
	15 3.24444444444444
	8 3.26293103448276
	5 3.35416666666667
	6 3.425
	7 3.50840336134454
	4 3.56666666666667
	3 3.9917695473251
	2 4.61475409836066

	Our top result is not 12, but notice the top two results are multiples
	of 12 and 12 is significantly higher in the rankings than any key
	lengths less than 12. Let's try a shorter key:
	$key = "eatoin shrd"
	$key.length
	11
	$cipherText = .\XOR-Encrypt.ps1 -String $data -key $key
	XOR-Brutr.ps1 -MaxKeySize 40 -String $cipherText -Encoding base16 \| Sort-Object AvgDist \| ft * -AutoSize
	KeySize AvgDist
	------- -------
	33 2.69191919191919
	22 2.70909090909091
	11 2.81385281385281
	18 2.97222222222222
	38 2.98421052631579
	23 3.0048309178744
	28 3.06632653061224
	15 3.07111111111111
	39 3.07179487179487
	24 3.0787037037037
	16 3.09821428571429
	31 3.10215053763441
	37 3.11351351351351
	32 3.11458333333333
	36 3.11666666666667
	40 3.12
	17 3.12669683257919
	13 3.12669683257919
	26 3.12980769230769
	35 3.13809523809524
	21 3.13809523809524
	34 3.15686274509804
	20 3.15909090909091
	29 3.17733990147783
	25 3.18
	30 3.18571428571429
	12 3.18859649122807
	27 3.19444444444444
	14 3.20089285714286
	10 3.20434782608696
	8 3.27155172413793
	19 3.27272727272727
	9 3.2948717948718
	7 3.47058823529412
	6 3.59583333333333
	5 3.62083333333333
	4 3.65416666666667
	3 4.12757201646091
	2 4.20491803278689
	Again our correct key size is not the top result, but the two top
	results are multiples of the correct result and the correct result
	follows immediately. What of a smaller key size?

	$key = "eatoin sh"
	$key.length
	9
	$cipherText = .\XOR-Encrypt.ps1 -String $data -key $key
	XOR-Brutr.ps1 -MaxKeySize 40 -String $cipherText -Encoding base16 \| Sort-Object AvgDist \| ft * -AutoSize
	KeySize AvgDist
	------- -------
	36 2.66111111111111
	27 2.75925925925926
	31 2.88709677419355
	9 2.8974358974359
	32 2.91666666666667
	38 2.92105263157895
	23 2.93719806763285
	22 2.95909090909091
	29 2.97044334975369
	18 2.99074074074074
	40 3.025
	37 3.02702702702703
	14 3.05803571428571
	30 3.07619047619048
	28 3.0765306122449
	20 3.08181818181818
	35 3.09047619047619
	34 3.10294117647059
	17 3.10407239819005
	26 3.11538461538462
	16 3.11607142857143
	15 3.12
	13 3.13122171945701
	25 3.16
	10 3.17391304347826
	21 3.2
	39 3.20512820512821
	33 3.20707070707071
	19 3.21052631578947
	11 3.22077922077922
	24 3.25925925925926
	5 3.37083333333333
	7 3.39915966386555
	12 3.41228070175439
	8 3.42672413793103
	6 3.45416666666667
	4 3.57916666666667
	3 3.98765432098765
	2 4.45491803278689
	Again, not the top result, but the top two are multiples and the
	correct result follows closely. This pattern continues for small
	keys.
	$key = "eatoin s"
	$key.length
	8
	$cipherText = .\XOR-Encrypt.ps1 -String $data -key $key
	XOR-Brutr.ps1 -MaxKeySize 40 -String $cipherText -Encoding base16 \| Sort-Object AvgDist \| ft * -AutoSize
	KeySize AvgDist
	------- -------
	24 2.58333333333333
	40 2.68
	32 2.72916666666667
	16 2.9375
	36 2.98333333333333
	39 2.98974358974359
	20 3.00454545454545
	21 3.00952380952381
	30 3.01428571428571
	34 3.01960784313725
	33 3.02020202020202
	28 3.04081632653061
	8 3.04741379310345
	12 3.08333333333333
	38 3.11052631578947
	29 3.14285714285714
	31 3.16129032258065
	25 3.17
	27 3.17592592592593
	37 3.18918918918919
	18 3.19444444444444
	23 3.19806763285024
	22 3.22272727272727
	19 3.24401913875598
	14 3.25446428571429
	35 3.26190476190476
	17 3.28054298642534
	11 3.28571428571429
	15 3.29777777777778
	13 3.30769230769231
	26 3.31730769230769
	9 3.32905982905983
	10 3.35652173913044
	6 3.36666666666667
	7 3.59663865546219
	4 3.61666666666667
	5 3.6375
	3 3.98353909465021
	2 4.68852459016393

	$key = "eato"
	$cipherText = .\XOR-Encrypt.ps1 -String $data -key $key
	XOR-Brutr.ps1 -MaxKeySize 40 -String $cipherText -Encoding base16 \| Sort-Object AvgDist \| ft * -AutoSize
	KeySize AvgDist
	------- -------
	24 2.58333333333333
	28 2.64285714285714
	36 2.66111111111111
	40 2.68
	32 2.72916666666667
	20 2.79545454545455
	30 2.85714285714286
	34 2.88725490196078
	16 2.9375
	29 2.94581280788177
	38 2.94736842105263
	39 2.94871794871795
	26 2.96153846153846
	22 3.00909090909091
	35 3.01428571428571
	33 3.02020202020202
	14 3.02232142857143
	27 3.02777777777778
	8 3.04741379310345
	12 3.06578947368421
	31 3.0752688172043
	13 3.09049773755656
	15 3.09333333333333
	21 3.09523809523809
	37 3.11891891891892
	25 3.12
	23 3.1207729468599
	18 3.14814814814815
	17 3.17647058823529
	11 3.17748917748918
	10 3.2
	19 3.21531100478469
	6 3.25
	9 3.28632478632479
	4 3.31666666666667
	7 3.31932773109244
	5 3.57083333333333
	3 3.77366255144033
	2 4.33196721311475

	What's the point of posting this? I guess the take away is that if
	you're trying to brute force XOR keys by first determining the key
	size, you can't automatically take the top result to be the correct
	key size. Even Matasano's instructions state that this is about
	probability not certainty, but the interesting property that they
	don't discuss, probably because they want people to notice on their
	own, is that for short keys, the top results may be multiples of
	the actual key size, so be mindful of that pattern.