From c876a2c009bcf3b06b8348d98f7ea85cd66fb600 Mon Sep 17 00:00:00 2001 From: Philippe Pepos Petitclerc Date: Fri, 13 May 2016 21:20:41 -0400 Subject: [PATCH] lib/crapto: Introduce 2 new attacks on XOR ciphers 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 --- lib/crapto/crapto.nit | 1 + lib/crapto/examples/repeating_key_xor_cipher.txt | 64 +++++++++ lib/crapto/examples/repeating_key_xor_solve.nit | 38 ++++++ lib/crapto/xor.nit | 150 ++++++++++++++++++++++ tests/niti.skip | 1 + tests/nitvm.skip | 1 + tests/repeating_key_xor_solve.args | 1 + tests/sav/repeating_key_xor_solve.res | 1 + tests/sav/repeating_key_xor_solve_args1.res | 80 ++++++++++++ 9 files changed, 337 insertions(+) create mode 100644 lib/crapto/examples/repeating_key_xor_cipher.txt create mode 100644 lib/crapto/examples/repeating_key_xor_solve.nit create mode 100644 lib/crapto/xor.nit create mode 100644 tests/repeating_key_xor_solve.args create mode 100644 tests/sav/repeating_key_xor_solve.res create mode 100644 tests/sav/repeating_key_xor_solve_args1.res diff --git a/lib/crapto/crapto.nit b/lib/crapto/crapto.nit index 6662877..5f3f017 100644 --- a/lib/crapto/crapto.nit +++ b/lib/crapto/crapto.nit @@ -16,3 +16,4 @@ module crapto import english_utils +import xor diff --git a/lib/crapto/examples/repeating_key_xor_cipher.txt b/lib/crapto/examples/repeating_key_xor_cipher.txt new file mode 100644 index 0000000..cecdb81 --- /dev/null +++ b/lib/crapto/examples/repeating_key_xor_cipher.txt @@ -0,0 +1,64 @@ +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= diff --git a/lib/crapto/examples/repeating_key_xor_solve.nit b/lib/crapto/examples/repeating_key_xor_solve.nit new file mode 100644 index 0000000..f88e2d9 --- /dev/null +++ b/lib/crapto/examples/repeating_key_xor_solve.nit @@ -0,0 +1,38 @@ +# 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 " + 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 diff --git a/lib/crapto/xor.nit b/lib/crapto/xor.nit new file mode 100644 index 0000000..8745c1a --- /dev/null +++ b/lib/crapto/xor.nit @@ -0,0 +1,150 @@ +# 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 diff --git a/tests/niti.skip b/tests/niti.skip index 571f594..4634f40 100644 --- a/tests/niti.skip +++ b/tests/niti.skip @@ -40,3 +40,4 @@ test_ffi_c_lots_of_refs test_rubix_cube test_rubix_visual test_csv +repeating_key_xor_solve diff --git a/tests/nitvm.skip b/tests/nitvm.skip index 47cb8a0..a68b4cc 100644 --- a/tests/nitvm.skip +++ b/tests/nitvm.skip @@ -40,3 +40,4 @@ test_ffi_c_lots_of_refs test_rubix_visual test_rubix_cube test_csv +repeating_key_xor_solve diff --git a/tests/repeating_key_xor_solve.args b/tests/repeating_key_xor_solve.args new file mode 100644 index 0000000..2f6c9ff --- /dev/null +++ b/tests/repeating_key_xor_solve.args @@ -0,0 +1 @@ +../lib/crapto/examples/repeating_key_xor_cipher.txt diff --git a/tests/sav/repeating_key_xor_solve.res b/tests/sav/repeating_key_xor_solve.res new file mode 100644 index 0000000..8a61309 --- /dev/null +++ b/tests/sav/repeating_key_xor_solve.res @@ -0,0 +1 @@ +Usage: repeating_key_xor_solve diff --git a/tests/sav/repeating_key_xor_solve_args1.res b/tests/sav/repeating_key_xor_solve_args1.res new file mode 100644 index 0000000..f81264e --- /dev/null +++ b/tests/sav/repeating_key_xor_solve_args1.res @@ -0,0 +1,80 @@ +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 + -- 1.7.9.5