Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I'm doing Matasano's challenges and struggling with second part of 49th problem where I'm asked to do the length extension attack with CBC-MAC without IV manipulation. There is a hint that I can simulate iv somehow to do this but I don't understand. Can someone drop me some hint atleast? I did the part with forging the first block of the message with changing the IV.

In particular there is a message format like this

  from=#{from_id}&tx_list=#{transactions}

With the transaction list formatted like:

  to:amount(;to:amount)*

The task is: capture a valid message from target user. Use length extension to add a transaction paying the attacker's account 1M spacebucks.

EDIT Alright, as I failed to explain it properly with my own words, here is the original problem

49. CBC-MAC Message Forgery

Let's talk about CBC-MAC.

CBC-MAC is like this:

  1. Take the plaintext P.
  2. Encrypt P under CBC with key K, yielding ciphertext C.
  3. Chuck all of C but the last block C[n].
  4. C[n] is the MAC.

Suppose there's an online banking application, and it carries out user
requests by talking to an API server over the network. Each request
looks like this:

  message || IV || MAC

The message looks like this:

  from=#{from_id}&to=#{to_id}&amount=#{amount}

Now, write an API server and a web frontend for it. (NOTE: No need to
get ambitious and write actual servers and web apps. Totally fine to
go lo-fi on this one.) The client and server should share a secret key
K to sign and verify messages.

The API server should accept messages, verify signatures, and carry
out each transaction if the MAC is valid. It's also publicly exposed -
the attacker can submit messages freely assuming he can forge the
right MAC.

The web client should allow the attacker to generate valid messages
for accounts he controls. (Feel free to sanitize params if you're
feeling anal-retentive.) Assume the attacker is in a position to
capture and inspect messages from the client to the API server.

One thing we haven't discussed is the IV. Assume the client generates
a per-message IV and sends it along with the MAC. That's how CBC
works, right?

Wrong.

For messages signed under CBC-MAC, an attacker-controlled IV is a
liability. Why? Because it yields full control over the first block of
the message.

Use this fact to generate a message transferring 1M spacebucks from a
target victim's account into your account.

I'll wait. Just let me know when you're done.

~ waiting ~

~ waiting ~

~ waiting ~

All done? Great - I knew you could do it!

Now let's tune up that protocol a little bit.

As we now know, you're supposed to use a fixed IV with CBC-MAC, so
let's do that. We'll set ours at 0 for simplicity. This means the IV
comes out of the protocol:

  message || MAC

Pretty simple, but we'll also adjust the message. For the purposes of
efficiency, the bank wants to be able to process multiple transactions
in a single request. So the message now looks like this:

  from=#{from_id}&tx_list=#{transactions}

With the transaction list formatted like:

  to:amount(;to:amount)*

There's still a weakness here: the MAC is vulnerable to length
extension attacks. How?

Well, the output of CBC-MAC is a valid IV for a new message.

"But we don't control the IV anymore!"

With sufficient mastery of CBC, we can fake it.

Your mission: capture a valid message from your target user. Use
length extension to add a transaction paying the attacker's account 1M
spacebucks.

HINT:

  This would be a lot easier if you had full control over the first
  block of your message, huh? Maybe you can simulate that.

Food for thought:

  How would you modify the protocol to prevent this?
share|improve this question
1  
I'm not sure about the exact attack required, but does this do what you need: CBC-MAC forging textbook question –  otus Jul 7 at 20:21
    
@otus It isn't what I need. The problem states that I can intercept only one message. And also this attack wouldn't be very helpful with required message format. I can't share the full problems unfortunately because they against it. –  swish Jul 8 at 4:02
    
Please edit the question to make clearer what the problem is. We don't have the second part of 49th problem in Matasano's problem set memorized in our head. Right now, the question does not seem answerable to me. Also, I suggest you edit the question to tell us what research you've done, what attacks on CBC-MAC you are familiar with, and what you've tried. –  D.W. Jul 10 at 6:55
    
@D.W. I've added some particulars, maybe it clarifies the problem a bit. –  swish Jul 14 at 9:18
1  
Can you add more info on the cipher? Specifically, what is the block size? –  mikeazo Jul 14 at 13:52

1 Answer 1

It seems that all this discussion about the IV is just to confuse the reader. Ignore IV. You just have to do a simple length-extension attack on the CBC-MAC. Yes, one message is enough.

share|improve this answer
    
I still unable to succeed. All I can do is to generate valid messages of the form M||(XOR(M[1],MAC)||M[2])*. But I still can't control any part of the message, it just generates copies of original with junk in the middle. Even to produce this it requires wrong padding implementation, without additional block to the already padded messages. –  swish Jul 19 at 10:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.