Set 1 - Challenge 8

Original Challenge Description from matasano

Detect AES in ECB mode

In this file are a bunch of hex-encoded ciphertexts.

One of them has been encrypted with ECB.

Detect it.

Remember that the problem with ECB is that it is stateless and deterministic; the same 16 byte plaintext block will always produce the same 16 byte ciphertext.

My Solution

• Since one byte represents two nibbles, in our give file we need to find duplicate patterns in the the block of 32. "fold" command  is our friend

• Now what we need to do is get these blocks for every line of the input and see if there are any duplicates. "sort" and "wc" can be used in a loop.

that marks the end of Set 1!

Set 1 - Challenge 5

Original Challenge Description from matasano

Implement repeating-key XOR

Here is the opening stanza of an important work of the English language:

Burning 'em, if you ain't quick and nimble
I go crazy when I hear a cymbal

Encrypt it, under the key "ICE", using repeating-key XOR.

In repeating-key XOR, you'll sequentially apply each byte of the key; the first byte of plaintext will be XOR'd against I, the next C, the next E, then I again for the 4th byte, and so on.

It should come out to:

0b3637272a2b2e63622c2e69692a23693a2a3c6324202d623d63343c2a26226324272765272
a282b2f20430a652e2c652a3124333a653e2b2027630c692b20283165286326302e27282f

Encrypt a bunch of stuff using your repeating-key XOR function. Encrypt your mail. Encrypt your password file. Your .sig file. Get a feel for it. I promise, we aren't wasting your time with this.

My Solution

• Here is the Xor program I came up with

• Now lets create the file with given stuff 

• Now encrypt it with our program

• Based on the first and last few bytes it looks good but lets make sure it really matches  with given output. We will copy & paste the given output in a file and then compare with what was generated by "my-encrypt"

No news from "diff" is good news!

Set 1 - Challenge 4

Original Challenge Description from matasano

Detect single-character XOR

One of the 60-character strings in this file has been encrypted by single-character XOR.

Find it.

My Solution

As the hint suggested previous code would help.  I realized that my English score engine could be modified to print the score first so that it would be easier to sort numerically based on the score.

So I changed the changed program to print "nnn is score"  instead of "score is nnn"  ( where nnn is the numeric score) and with some bash scripting, its party time!

I know, later I may have to change this a bit to handle everything within C program :)

Set 1 - Challenge 3

Original Challenge Description from matasano

Single-byte XOR cipher

The hex encoded string:

1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736

... has been XOR'd against a single character. Find the key, decrypt the message.

You can do this by hand. But don't: write code to do it for you.

How? Devise some method for "scoring" a piece of English plaintext. Character frequency is a good metric. Evaluate each output and choose the one with the best score.

• Need a program to brute-force xor with one  byte to produce the output.

• Then we can visually go through the output to see whats makes sense and/or also write anther program to check if the output is English based on the letter frequency

My Solution

• Here is the brute-force program

OK,  MAXLINE is not really for the lines but this will crash if given bigger input.

Now lets run this program against the given input and see what the output looks like

Most of the output is not printable but below chunk seems interesting.

Although bacon is not my thing but you can see the most probable message here 

Now lets  write a program to do the scoring for English and see if it picks up the one seen above.

Weight is given to most common English letters and then other alphabets and the program prints the max score and some other stuff. This may have to be modified later.

Now run the earlier program through our scoring engine and see if it gets the food.

I modified the brute-force  program a bit to output the xor byte

Now, can not wait to tweet!

Set 1 - Challenge 1

Original Challenge Description from matasano

Convert hex to base64

The string:

49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d

Should produce:

SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t

So go ahead and make that happen. You'll need to use this code for the rest of the exercises.

Cryptopals Rule

Always operate on raw bytes, never on encoded strings. Only use hex and base64 for pretty-printing.

My Solution

• Create a program to   convert hex bytes to raw bytes and compile

• Now convert the given hex string into raw

• Lets check if openssl base64 encoding matches with whats given

  It does!

Set 1 - Challenge 6

Original Challenge Description from matasano

Break repeating-key XOR

There's a file here. It's been base64'd after being encrypted with repeating-key XOR.

Decrypt it.

Here's how:

1. Let KEYSIZE be the guessed length of the key; try values from 2 to (say) 40.
2. Write a function to compute the edit distance/Hamming distance between two strings. The Hamming distance is just the number of differing bits. The distance between:

   this is a test

   and

   wokka wokka!!!

   is 37. Make sure your code agrees before you proceed.
3. For each KEYSIZE, take the first KEYSIZE worth of bytes, and the second KEYSIZE worth of bytes, and find the edit distance between them. Normalize this result by dividing by KEYSIZE.
4. The KEYSIZE with the smallest normalized edit distance is probably the key. You could proceed perhaps with the smallest 2-3 KEYSIZE values. Or take 4 KEYSIZE blocks instead of 2 and average the distances.
5. Now that you probably know the KEYSIZE: break the ciphertext into blocks of KEYSIZE length.
6. Now transpose the blocks: make a block that is the first byte of every block, and a block that is the second byte of every block, and so on.
7. Solve each block as if it was single-character XOR. You already have code to do this.
8. For each block, the single-byte XOR key that produces the best looking histogram is the repeating-key XOR key byte for that block. Put them together and you have the key.

This code is going to turn out to be surprisingly useful later on. Breaking repeating-key XOR ("Vigenere") statistically is obviously an academic exercise, a "Crypto 101" thing. But more people "know how" to break it than can actually break it, and a similar technique breaks something much more important.

My Solution

• I created a small program with the help of wiki  and it calculated the 37 correctly. Below are the program snippets.

• Looking at the problem, we need to create hamming distance between different size blocks, so the above functions would need to be modified to accept the length as a parameter. Also, we can not rely on null byte at the end.

• Here is the updated version

• After  getting the file 6.txt, I converted to rawbytes  with below  command

• Now we are ready to run our hamming program to guess the key size. I fed the raw bytes to hamming program and it looked like this

• Based on this I thought the key length is 3 or 5.  I ruled out 2 because 2 was the minimum even when a test file was encrypted with "ICE". Anyways assuming the key length is 3 we need to get   every fourth byte in a stream and try our "bruteforce" program used earlier. 
• We can write in C but this can be easily done in shell as well. Our friend "xxd"can used together with "cut" and "tr"

-p produces plain hex and -c indicates the bytes/octets

• To get the transpose , we need to get only first bytes from every line and then the subsequent one.
• We will start with just first one and check the "English Score"  So "xxd", "cut" and "tr"   combined like above give us what we wanted. We can change the "cut" parameter to 3-4, 5-6 etc  for the remainder streams.  Lets first  brute-force  this.

• This doesn't look much like real message so lets run again with key size of 5

• This is not a whole lot different.  lets try another key size. Upon closer look at out hamming program above key size 29 is next, so lets try that.

• All  of them are valid English.  I think we got it!  btw, I modified the brute-force program to indicate the actual ascii character which is used to brute-force. This will help us reveal the key directly without any look ups.
• Now lets try the second block

• Based on the above two key starts with "Te". Now its time to write another shell script to do this 29 times and extract the key

• The variable is the parameter to "cut"  which needs to be repeated 29 times. The above script does its job and now we just need to extract the key which is at the end following 2 or 3 numbers.

• This makes it easy to copy the key ( although its mixed with the shell prompt). Now that we have the key lets decrypt the file 

Set 1 - Challenge 7

Original Challenge Description from matasano

AES in ECB mode

The Base64-encoded content in this file has been encrypted via AES-128 in ECB mode under the key

"YELLOW SUBMARINE".

(case-sensitive, without the quotes; exactly 16 characters; I like "YELLOW SUBMARINE" because it's exactly 16 bytes long, and now you do too).

Decrypt it. You know the key, after all.

Easiest way: use OpenSSL::Cipher and give it AES-128-ECB as the cipher.

Do this with code.

You can obviously decrypt this using the OpenSSL command-line tool, but we're having you get ECB working in code for a reason. You'll need it a lot later on, and not just for attacking ECB.

My Solution

• OK, I'm going to incur some technical debt here is the way to decrypt using openssl.

Having said that I know in python or java  its probably going to take a few lines of code to do this once your using a crypto library.  I will try to spend sometime figuring out how to do this in C.

Please let me know if you can recommend any in C library.   or are we supposed to write our own AES program ?