Anyone working on the Matasano crypto challenges?

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Anyone working on the Matasano crypto challenges?

itsameta4: Sep 29, 2013

I have an on-again/off-again desire to maybe get into Security/pen-testing/yadayada, and spend too much time on Hacker News, so I was pretty psyched when Matasano Security released their crypto challenge: 6 sets of 8 problems, designed to walk you through learning the basics of crypto. Previously, they were essentially invite-only, with a long backlog for them to even get back to you. (I was waiting over a year!) But, now they're up and running publically. They said they'd be getting the answers out a few days a week, but I guess they're still backlogged.

Anyway, has anyone been working through them? I've been using them to teach myself Python. Things have been going pretty well so far, but I can't even loving parse Set 2, question 2.

tptacek posted:

CBC mode is a block cipher mode that allows us to encrypt irregularly-sized messages, despite the fact that a block cipher natively only transforms individual blocks.

In CBC mode, each ciphertext block is added to the next plaintext block before the next call to the cipher core.

The first plaintext block, which has no associated previous ciphertext block, is added to a "fake 0th ciphertext block" called the initialization vector, or IV.

Implement CBC mode by hand by taking the ECB function you wrote earlier, making it encrypt instead of decrypt (verify this by decrypting whatever you encrypt to test), and using your XOR function from the previous exercise to combine them.

The file here is intelligible (somewhat) when CBC decrypted against "YELLOW SUBMARINE" with an IV of all ASCII 0 (\x00\x00\x00 &c)

Don't cheat.

Do not use OpenSSL's CBC code to do CBC mode, even to verify your results. What's the point of even doing this stuff if you aren't going to learn from it?

So, I didn't write an ECB function earlier, because he said to just import whatever library your language uses for crypto, and feed it AES/ECB. Or am I dense, and was actually supposed to implement AES myself with no guidance? :gonk:

The last problem was just padding a message and had nothing to do with writing a XOR function, though it has somewhat to do with this one, maybe. Also wtf would I even XOR, that's not how AES, combine who, what

Anybody else get stuck here?

e: It's a bitwise add :v:

itsameta4 fucked around with this message at 20:19 on Aug 26, 2014

# ? Aug 26, 2014 09:56

Adbot: ADBOT LOVES YOU

# ? May 4, 2024 22:45

robostac: Sep 23, 2009

I'm pretty sure they are expecting you to just continue to use the library function for AES/ECB - implementing that would be crazy and not that useful as none of the challenges will involve exploiting that algorithm. ECB mode is the simplest mode you can get from the library (where it just encrypts a block), so if you have a way to do that you can then build on that to implement the more complicated modes yourself (which is useful as you can then solve challenges against those modes).

CBC works by taking the block of plaintext, xor'ing it with the previously encrypted block, and then encrypting that data. The IV is needed for the first block, as there isn't a previously encrypted block.

To decrypt you run the AES/ECB algorithm on a block, then xor the result with the previous block of encrypted data. The first block is xor'ed against the IV as there wasn't a previous block of encrypted data to use.

# ? Aug 27, 2014 11:05

Argue: Sep 29, 2005; I represent the Philippines

I had the same question when I saw that. Yeah, just use the built in AES, but you have to implement the ECB/CBC part. Later on you'll also need to find a pure Python/Ruby/whatever implementation of SHA1 (rather than using the built in one or rolling out your own).

This has been very satisfying so far; I'm at challenge 29 now and I feel like I'm learning quite a bit. I've been doing it in Python; I wanted to do it in Haskell but my Haskell skill is not quite there yet; it took me forever to just solve the first two problems :v :

# ? Aug 27, 2014 14:26

floWenoL: Oct 23, 2002

I've been going through these problems, too -- I'm up to challenge 52 now. Some of the problems are poorly explained, but the folks #cryptopals channel on freenode are helpful.

Did them all in Python (3). Didn't feel like struggling with learning a new language at the same time, although once I finish them all going back and doing everything in a new language would be a good way to learn it.

# ? Sep 16, 2014 20:23

ImDifferent: Sep 20, 2001

I did the first set of 6 a while back, in Ruby. Haven't had the time to look at the next set yet. And yeah, I was totally frustrated at the ambiguous wording of some of them.

# ? Sep 17, 2014 03:19

mattx0r: Feb 11, 2005; ./configure --omg-optimized

I've been working through these since I discovered this thread last week. I made the grave mistake of trying to learn Clojure at the same time as solving the problems, but despite the pains of learning a new language, this is probably the most fun I've had programming in the last year.

Right now I'm stuck on challenge 14, but I'm not sure if it's because I can't see the solution or because I'm misinterpreting the question.

In the challenge, plaintext is being encrypted with the following scheme:

code:

AES-128-ECB(random-prefix || attacker-controlled || target-bytes, random-key)

In challenge 12, we could decode the ECB message by controlling the position of the target-bytes in the ciphertext by varying the length of the attacker-controlled bytes, but in challenge 14, there's now a random amount of padding prepended to the plaintext each time a message is encrypted. The problem seems really straight-forward if the length of the padding remains fixed between successive calls to the encryption function, but I can't for the life of me figure out how to deal with an unknown prefix of varying length.

Is there something I'm missing here or am I on the right track and suffering from tunnel vision?

# ? Nov 17, 2014 01:05

Jabor: Jul 16, 2010; #1 Loser at SpaceChem

Here's a clue that should help get you on the right track. If you're still stuck after thinking about it for a while, post again and I'll try come up with a more specific hint that still doesn't just give the game away.

Can you get any information about the length of the random prefix?

# ? Nov 17, 2014 13:21

mattx0r: Feb 11, 2005; ./configure --omg-optimized

Jabor posted:

Here's a clue that should help get you on the right track. If you're still stuck after thinking about it for a while, post again and I'll try come up with a more specific hint that still doesn't just give the game away.

Can you get any information about the length of the random prefix?

Thanks for the hint, I think I got it.

Here's the conclusion I reached: If the prefix length doesn't change, you can pass increasingly larger plaintext blocks containing a single repeating character until ECB produces two identical adjacent ciphertext blocks. Knowing the position of the start of the first repeating block and the length of the attacker-controlled bytes required to produce the repeating blocks, you can determine the length of the prefix. Right?

# ? Nov 17, 2014 17:19

Jabor: Jul 16, 2010; #1 Loser at SpaceChem

mattx0r posted:

Thanks for the hint, I think I got it. Here's the conclusion I reached: If the prefix length doesn't change, you can pass increasingly larger plaintext blocks containing a single repeating character until ECB produces two identical adjacent ciphertext blocks. Knowing the position of the start of the first repeating block and the length of the attacker-controlled bytes required to produce the repeating blocks, you can determine the length of the prefix. Right?

It's a start, but that's not quite what I was getting at.

The prefix length is going to be randomised on every encryption.

Can you figure out what a block of repeating characters encrypts to even without knowing the prefix length?

# ? Nov 18, 2014 01:00

mattx0r: Feb 11, 2005; ./configure --omg-optimized

Jabor posted:

It's a start, but that's not quite what I was getting at.

The prefix length is going to be randomised on every encryption.

Can you figure out what a block of repeating characters encrypts to even without knowing the prefix length?

Hmm, okay. If we provide the encryption function with (3 * block-size - 1) bytes of repeating characters, we can determine what a block of repeating characters looks like by finding the first two adjacent repeating blocks in the ciphertext.

I'm not sure what this buys me though, the attack in ch 12 required us to always know how many bytes needed to be added to the plaintext to move a given secret byte to the end of a block. It seems like with a random prefix, we'll never be able to perform the same operation...

# ? Nov 18, 2014 06:12

Adbot: ADBOT LOVES YOU

# ? May 4, 2024 22:45

Bognar: Aug 4, 2011; I am the queen of France; Hot Rope Guy

mattx0r posted:

Hmm, okay. If we provide the encryption function with (3 * block-size - 1) bytes of repeating characters, we can determine what a block of repeating characters looks like by finding the first two adjacent repeating blocks in the ciphertext.

I'm not sure what this buys me though, the attack in ch 12 required us to always know how many bytes needed to be added to the plaintext to move a given secret byte to the end of a block. It seems like with a random prefix, we'll never be able to perform the same operation...

I wouldn't say that you would never be able to perform the same operation.

If you prefix with a block of repeating characters, how can you tell if the randomized prefix is divisible by the block size? What are the chances of that happening? How fast is your computer?

# ? Nov 18, 2014 16:25

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Anyone working on the Matasano crypto challenges?