Introduced an attack on Single-byte XOR cipher based on english frequency analysis
Introduced an attack on Repeated-key XOR cipher based on hamming distances and Single-byte XOR attacks.
Signed-off-by: Philippe Pepos Petitclerc <ppeposp@gmail.com>
module crapto
import english_utils
+import xor
--- /dev/null
+HUIfTQsPAh9PE048GmllH0kcDk4TAQsHThsBFkU2AB4BSWQgVB0dQzNTTmVS
+BgBHVBwNRU0HBAxTEjwMHghJGgkRTxRMIRpHKwAFHUdZEQQJAGQmB1MANxYG
+DBoXQR0BUlQwXwAgEwoFR08SSAhFTmU+Fgk4RQYFCBpGB08fWXh+amI2DB0P
+QQ1IBlUaGwAdQnQEHgFJGgkRAlJ6f0kASDoAGhNJGk9FSA8dDVMEOgFSGQEL
+QRMGAEwxX1NiFQYHCQdUCxdBFBZJeTM1CxsBBQ9GB08dTnhOSCdSBAcMRVhI
+CEEATyBUCHQLHRlJAgAOFlwAUjBpZR9JAgJUAAELB04CEFMBJhAVTQIHAh9P
+G054MGk2UgoBCVQGBwlTTgIQUwg7EAYFSQ8PEE87ADpfRyscSWQzT1QCEFMa
+TwUWEXQMBk0PAg4DQ1JMPU4ALwtJDQhOFw0VVB1PDhxFXigLTRkBEgcKVVN4
+Tk9iBgELR1MdDAAAFwoFHww6Ql5NLgFBIg4cSTRWQWI1Bk9HKn47CE8BGwFT
+QjcEBx4MThUcDgYHKxpUKhdJGQZZVCFFVwcDBVMHMUV4LAcKQR0JUlk3TwAm
+HQdJEwATARNFTg5JFwQ5C15NHQYEGk94dzBDADsdHE4UVBUaDE5JTwgHRTkA
+Umc6AUETCgYAN1xGYlUKDxJTEUgsAA0ABwcXOwlSGQELQQcbE0c9GioWGgwc
+AgcHSAtPTgsAABY9C1VNCAINGxgXRHgwaWUfSQcJABkRRU8ZAUkDDTUWF01j
+OgkRTxVJKlZJJwFJHQYADUgRSAsWSR8KIgBSAAxOABoLUlQwW1RiGxpOCEtU
+YiROCk8gUwY1C1IJCAACEU8QRSxORTBSHQYGTlQJC1lOBAAXRTpCUh0FDxhU
+ZXhzLFtHJ1JbTkoNVDEAQU4bARZFOwsXTRAPRlQYE042WwAuGxoaAk5UHAoA
+ZCYdVBZ0ChQLSQMYVAcXQTwaUy1SBQsTAAAAAAAMCggHRSQJExRJGgkGAAdH
+MBoqER1JJ0dDFQZFRhsBAlMMIEUHHUkPDxBPH0EzXwArBkkdCFUaDEVHAQAN
+U29lSEBAWk44G09fDXhxTi0RAk4ITlQbCk0LTx4cCjBFeCsGHEETAB1EeFZV
+IRlFTi4AGAEORU4CEFMXPBwfCBpOAAAdHUMxVVUxUmM9ElARGgZBAg4PAQQz
+DB4EGhoIFwoKUDFbTCsWBg0OTwEbRSonSARTBDpFFwsPCwIATxNOPBpUKhMd
+Th5PAUgGQQBPCxYRdG87TQoPD1QbE0s9GkFiFAUXR0cdGgkADwENUwg1DhdN
+AQsTVBgXVHYaKkg7TgNHTB0DAAA9DgQACjpFX0BJPQAZHB1OeE5PYjYMAg5M
+FQBFKjoHDAEAcxZSAwZOBREBC0k2HQxiKwYbR0MVBkVUHBZJBwp0DRMDDk5r
+NhoGACFVVWUeBU4MRREYRVQcFgAdQnQRHU0OCxVUAgsAK05ZLhdJZChWERpF
+QQALSRwTMRdeTRkcABcbG0M9Gk0jGQwdR1ARGgNFDRtJeSchEVIDBhpBHQlS
+WTdPBzAXSQ9HTBsJA0UcQUl5bw0KB0oFAkETCgYANlVXKhcbC0sAGgdFUAIO
+ChZJdAsdTR0HDBFDUk43GkcrAAUdRyonBwpOTkJEUyo8RR8USSkOEENSSDdX
+RSAdDRdLAA0HEAAeHQYRBDYJC00MDxVUZSFQOV1IJwYdB0dXHRwNAA9PGgMK
+OwtTTSoBDBFPHU54W04mUhoPHgAdHEQAZGU/OjV6RSQMBwcNGA5SaTtfADsX
+GUJHWREYSQAnSARTBjsIGwNOTgkVHRYANFNLJ1IIThVIHQYKAGQmBwcKLAwR
+DB0HDxNPAU94Q083UhoaBkcTDRcAAgYCFkU1RQUEBwFBfjwdAChPTikBSR0T
+TwRIEVIXBgcURTULFk0OBxMYTwFUN0oAIQAQBwkHVGIzQQAGBR8EdCwRCEkH
+ElQcF0w0U05lUggAAwANBxAAHgoGAwkxRRMfDE4DARYbTn8aKmUxCBsURVQf
+DVlOGwEWRTIXFwwCHUEVHRcAMlVDKRsHSUdMHQMAAC0dCAkcdCIeGAxOazkA
+BEk2HQAjHA1OAFIbBxNJAEhJBxctDBwKSRoOVBwbTj8aQS4dBwlHKjUECQAa
+BxscEDMNUhkBC0ETBxdULFUAJQAGARFJGk9FVAYGGlMNMRcXTRoBDxNPeG43
+TQA7HRxJFUVUCQhBFAoNUwctRQYFDE43PT9SUDdJUydcSWRtcwANFVAHAU5T
+FjtFGgwbCkEYBhlFeFsABRcbAwZOVCYEWgdPYyARNRcGAQwKQRYWUlQwXwAg
+ExoLFAAcARFUBwFOUwImCgcDDU5rIAcXUj0dU2IcBk4TUh0YFUkASEkcC3QI
+GwMMQkE9SB8AMk9TNlIOCxNUHQZCAAoAHh1FXjYCDBsFABkOBkk7FgALVQRO
+D0EaDwxOSU8dGgI8EVIBAAUEVA5SRjlUQTYbCk5teRsdRVQcDhkDADBFHwhJ
+AQ8XClJBNl4AC1IdBghVEwARABoHCAdFXjwdGEkDCBMHBgAwW1YnUgAaRyon
+B0VTGgoZUwE7EhxNCAAFVAMXTjwaTSdSEAESUlQNBFJOZU5LXHQMHE0EF0EA
+Bh9FeRp5LQdFTkAZREgMU04CEFMcMQQAQ0lkay0ABwcqXwA1FwgFAk4dBkIA
+CA4aB0l0PD1MSQ8PEE87ADtbTmIGDAILAB0cRSo3ABwBRTYKFhROHUETCgZU
+MVQHYhoGGksABwdJAB0ASTpFNwQcTRoDBBgDUkksGioRHUkKCE5THEVCC08E
+EgF0BBwJSQoOGkgGADpfADETDU5tBzcJEFMLTx0bAHQJCx8ADRJUDRdMN1RH
+YgYGTi5jMURFeQEaSRAEOkURDAUCQRkKUmQ5XgBIKwYbQFIRSBVJGgwBGgtz
+RRNNDwcVWE8BT3hJVCcCSQwGQx9IBE4KTwwdASEXF01jIgQATwZIPRpXKwYK
+BkdEGwsRTxxDSToGMUlSCQZOFRwKUkQ5VEMnUh0BR0MBGgAAZDwGUwY7CBdN
+HB5BFwMdUz0aQSwWSQoITlMcRUILTxoCEDUXF01jNw4BTwVBNlRBYhAIGhNM
+EUgIRU5CRFMkOhwGBAQLTVQOHFkvUkUwF0lkbXkbHUVUBgAcFA0gRQYFCBpB
+PU8FQSsaVycTAkJHYhsRSQAXABxUFzFFFggICkEDHR1OPxoqER1JDQhNEUgK
+TkJPDAUAJhwQAg0XQRUBFgArU04lUh0GDlNUGwpOCU9jeTY1HFJARE4xGA4L
+ACxSQTZSDxsJSw1ICFUdBgpTNjUcXk0OAUEDBxtUPRpCLQtFTgBPVB8NSRoK
+SREKLUUVAklkERgOCwAsUkE2Ug8bCUsNSAhVHQYKUyI7RQUFABoEVA0dWXQa
+Ry1SHgYOVBFIB08XQ0kUCnRvPgwQTgUbGBwAOVREYhAGAQBJEUgETgpPGR8E
+LUUGBQgaQRIaHEshGk03AQANR1QdBAkAFwAcUwE9AFxNY2QxGA4LACxSQTZS
+DxsJSw1ICFUdBgpTJjsIF00GAE1ULB1NPRpPLF5JAgJUVAUAAAYKCAFFXjUe
+DBBOFRwOBgA+T04pC0kDElMdC0VXBgYdFkU2CgtNEAEUVBwTWXhTVG5SGg8e
+AB0cRSo+AwgKRSANExlJCBQaBAsANU9TKxFJL0dMHRwRTAtPBRwQMAAATQcB
+FlRlIkw5QwA2GggaR0YBBg5ZTgIcAAw3SVIaAQcVEU8QTyEaYy0fDE4ITlhI
+Jk8DCkkcC3hFMQIEC0EbAVIqCFZBO1IdBgZUVA4QTgUWSR4QJwwRTWM=
--- /dev/null
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+import base64
+import crapto
+
+# Check usage
+if args.length != 1 then
+ print "Usage: repeating_key_xor_solve <cipher_file>"
+ exit 1
+end
+
+# Read the cipher from the file
+var cipher_bytes = args[0].to_path.read_all_bytes.decode_base64
+
+# Create a RepeatingKeyXorCipher object to manipulate your ciphertext
+var xorcipher = new RepeatingKeyXorCipher
+xorcipher.ciphertext = cipher_bytes
+
+# Try to find the best candidate key
+xorcipher.find_key
+
+# Decrypt the cipher according to the found key
+xorcipher.decrypt
+
+# Check the resulting plaintext out...
+print xorcipher.plaintext
--- /dev/null
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+# Cryptographic attacks and utilities for XOR-based algorithms.
+module xor
+
+import combinations
+import crypto
+import english_utils
+
+redef class SingleByteXorCipher
+ # Tries to find key using frequency analysis on all possible plaintexts.
+ # Populates `self.key`
+ fun find_key do
+
+ # Accumulate best result
+ var max = 0.0
+ var best = 0.to_b
+
+ # Iterate on possible values for a byte
+ var xor_b = new Bytes.with_capacity(1)
+ for b in [0 .. 255] do
+ # Need `Bytes` to pass to xor
+ xor_b[0] = b.to_b
+
+ # Xor and evaluate result
+ var xored = ciphertext.xorcipher(xor_b)
+ var result = xored.to_s.english_scoring
+ if result > max then
+ max = result
+ best = b.to_b
+ end
+ end
+
+ self.key = best
+
+ end
+end
+
+redef class RepeatingKeyXorCipher
+ # Attempts to find the key by using frequency analysis on the resulting plaintexts.
+ # Best key lengths are estimated using the hamming distance of blocks of keylength bytes.
+ # Ciphertext is then transposed in such a way that it can be solved by sequences of
+ # SingleByteXor (one for each offset in the key).
+ #
+ # `min_keylength` and `max_keylength` are limits as to what key lengths are tested.
+ # `considered_keylength_count` is the number of best key lengths that are kept to be
+ # analysed by the SingleByteXor frequency analysis.
+ fun find_key(min_keylength, max_keylength, considered_keylength_count: nullable Int) do
+
+ # Set default values
+ if min_keylength == null then min_keylength = 2
+ if max_keylength == null then max_keylength = 40
+ if considered_keylength_count == null then considered_keylength_count = 3
+
+ # Find the best candidate key lengths based on the normalized hamming distances
+ var best_sizes = get_normalized_hamming_distances(min_keylength, max_keylength, considered_keylength_count)
+
+ var best = 0.0
+ var best_key: nullable Bytes = null
+ for ks in best_sizes do
+
+ # Rearrange ciphertext to be in SingleByteXORable blocks
+ var transposed = transpose_ciphertext(ks)
+
+ var key = new Bytes.empty
+ for slot in transposed do
+ var sbx = new SingleByteXorCipher
+ sbx.ciphertext = slot
+ sbx.find_key
+ key.add sbx.key
+ end
+
+ # Evaluate the resulting plaintext based on english frequency analysis
+ var eng_score = ciphertext.xorcipher(key).to_s.english_scoring
+ if eng_score > best then
+ best_key = key
+ best = eng_score
+ end
+
+ assert best_key != null
+ self.key = best_key
+
+ end
+ end
+
+ # Computes the normalized hamming distances between blocks of ciphertext of length between `min_length` and `max_length`.
+ # The `considered_keylength_count` smallest results are returned
+ private fun get_normalized_hamming_distances(min_keylength, max_keylength, considered_keylength_count: Int): Array[Int] do
+
+ var normalized_distances = new HashMap[Float, Int]
+
+ # Iterate over all given key lengths
+ for ks in [min_keylength .. max_keylength[ do
+
+ # Initialize the blocks of size `ks`
+ var blocks = new Array[Bytes]
+ while (blocks.length + 1) * ks < ciphertext.length do
+ blocks.add(ciphertext.slice(blocks.length * ks, ks))
+ end
+
+ # Compute the normalized hamming distance with all block combinations
+ var pairs = new CombinationCollection[Bytes](blocks, 2)
+ var hamming_dists = new Array[Float]
+ for p in pairs do
+ hamming_dists.add(p[0].hamming_distance(p[1]).to_f / ks.to_f)
+ end
+
+ # Normalize the results based on the number of blocks
+ var normalized = 0.0
+ for dist in hamming_dists do normalized += dist
+ normalized /= hamming_dists.length.to_f
+ normalized_distances[normalized] = ks
+
+ end
+
+ # Collect the best candidates
+ var distances = normalized_distances.keys.to_a
+ default_comparator.sort(distances)
+ var best_distances = distances.subarray(0, considered_keylength_count)
+ var best_sizes = [for d in best_distances do normalized_distances[d]]
+
+ return best_sizes
+ end
+
+ # Returns a rearranged format of the ciphertext where every byte of a slot will be XORed with the same offset of a key of length `keylength`.
+ private fun transpose_ciphertext(keylength: Int): Array[Bytes] do
+ var transposed = new Array[Bytes]
+ for i in [0 .. keylength[ do
+ transposed.add(new Bytes.empty)
+ end
+
+ for byte_idx in [0 .. ciphertext.length[ do
+ transposed[byte_idx % keylength].add(ciphertext[byte_idx])
+ end
+
+ return transposed
+ end
+end
test_rubix_cube
test_rubix_visual
test_csv
+repeating_key_xor_solve
test_rubix_visual
test_rubix_cube
test_csv
+repeating_key_xor_solve
--- /dev/null
+../lib/crapto/examples/repeating_key_xor_cipher.txt
--- /dev/null
+Usage: repeating_key_xor_solve <cipher_file>
--- /dev/null
+I'm back and I'm ringin' the bell
+A rockin' on the mike while the fly girls yell
+In ecstasy in the back of me
+Well that's my DJ Deshay cuttin' all them Z's
+Hittin' hard and the girlies goin' crazy
+Vanilla's on the mike, man I'm not lazy.
+
+I'm lettin' my drug kick in
+It controls my mouth and I begin
+To just let it flow, let my concepts go
+My posse's to the side yellin', Go Vanilla Go!
+
+Smooth 'cause that's the way I will be
+And if you don't give a damn, then
+Why you starin' at me
+So get off 'cause I control the stage
+There's no dissin' allowed
+I'm in my own phase
+The girlies sa y they love me and that is ok
+And I can dance better than any kid n' play
+
+Stage 2 -- Yea the one ya' wanna listen to
+It's off my head so let the beat play through
+So I can funk it up and make it sound good
+1-2-3 Yo -- Knock on some wood
+For good luck, I like my rhymes atrocious
+Supercalafragilisticexpialidocious
+I'm an effect and that you can bet
+I can take a fly girl and make her wet.
+
+I'm like Samson -- Samson to Delilah
+There's no denyin', You can try to hang
+But you'll keep tryin' to get my style
+Over and over, practice makes perfect
+But not if you're a loafer.
+
+You'll get nowhere, no place, no time, no girls
+Soon -- Oh my God, homebody, you probably eat
+Spaghetti with a spoon! Come on and say it!
+
+VIP. Vanilla Ice yep, yep, I'm comin' hard like a rhino
+Intoxicating so you stagger like a wino
+So punks stop trying and girl stop cryin'
+Vanilla Ice is sellin' and you people are buyin'
+'Cause why the freaks are jockin' like Crazy Glue
+Movin' and groovin' trying to sing along
+All through the ghetto groovin' this here song
+Now you're amazed by the VIP posse.
+
+Steppin' so hard like a German Nazi
+Startled by the bases hittin' ground
+There's no trippin' on mine, I'm just gettin' down
+Sparkamatic, I'm hangin' tight like a fanatic
+You trapped me once and I thought that
+You might have it
+So step down and lend me your ear
+'89 in my time! You, '90 is my year.
+
+You're weakenin' fast, YO! and I can tell it
+Your body's gettin' hot, so, so I can smell it
+So don't be mad and don't be sad
+'Cause the lyrics belong to ICE, You can call me Dad
+You're pitchin' a fit, so step back and endure
+Let the witch doctor, Ice, do the dance to cure
+So come up close and don't be square
+You wanna battle me -- Anytime, anywhere
+
+You thought that I was weak, Boy, you're dead wrong
+So come on, everybody and sing this song
+
+Say -- Play that funky music Say, go white boy, go white boy go
+play that funky music Go white boy, go white boy, go
+Lay down and boogie and play that funky music till you die.
+
+Play that funky music Come on, Come on, let me hear
+Play that funky music white boy you say it, say it
+Play that funky music A little louder now
+Play that funky music, white boy Come on, Come on, Come on
+Play that funky music
+
nitlanguage / nit.git / commitdiff