[Boneh-crypto-course] Are we keeping up?

Jeremy Holland jeremy at jeremypholland.com
Wed Apr 11 02:00:26 CDT 2012

For what it's worthy, this is the way I solved Q8 & Q9:


We need to find a collision for f1(x,y) = AES(y,x) XOR y. So, writing it out, we have:

AES(y1,x1) XOR y1 = AES(y2,x2) XOR y2

Well, we proved in the lecture that h(m,H) is insecure because we can pass D(m',E(m,H)) as H', resulting in E(m',D(m',E(m,H))), which simplifies directly to E(m,H) or h(m,H), causing a collision, so that's where I started. This gives us the following (note I am using E for the AES encryption function and D for the AES decryption function, since otherwise it would get hairy-looking since email doesn't support TeX):

E(y1,x1) XOR y1 = E(y2,D(y2,E(y1,x1))) XOR y2

But that ended up with:

E(y1,x1) XOR y1 = E(y1,x1) XOR y2

..then that meant that y1 and y2 had to be identical, in which case the while thing turns into the identity function and nothing is achieved. So then I subbed in the *whole* of f1(x,y), like so:

E(y1,x1) XOR y1 = E(y2,D(y2,E(y1,x1) XOR y1)) XOR y2

Leaving me with

E(y1,x1) XOR y1 = E(y1,x1) XOR y1 XOR y2

Which works out perfectly with any x1, y1 you wish, and y2 = 0^n, since any string of bits XOR 0 is itself. Then it was just a matter of plugging in numbers and boom - you're done.

Q9 was simpler than Q8, IMHO:

For this one, we had f2(x,y) = AES(x,x) XOR y, and so our collision equation looks like this:

E(x1,x1) XOR y1 = E(x2,x2) XOR y2

The handy fact here is that any number XOR itself is equal to 0. So I just set y1 = E(x1,x1) and y2 = E(x2,x2), giving us:

E(x1,x1) XOR E(x1,x1) = E(x2,x2) XOR E(x2,x2)

Simplifying to:

0 = 0

And that's pretty much that. Hope this helps!

- Jeremy Holland

On Apr 11, 2012, at 1:17, Jim Blandy <jimb at red-bean.com> wrote:

> The quizzes are a bit harrowing for me emotionally, even though I do fine on them. I think this is because, although I am able to *solve* the problems, I don't have an *algorithm* for solving them; it's a blind leap each time.
> For example, in the "make these functions collide" one, I couldn't possibly explain how I solved it. I just stared at it, and then tried some stuff, then thought "hey, this should do it." My first attempt was just to try to write down equations and then solve them, but that got nowhere. The blind leap was the only way.
> Now that I've got the answers, though, it would be fun to work it through equationally.
> _______________________________________________
> Boneh-crypto-course mailing list
> Boneh-crypto-course at red-bean.com
> http://www.red-bean.com/mailman/listinfo/boneh-crypto-course
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.red-bean.com/pipermail/boneh-crypto-course/attachments/20120411/05b43698/attachment.html>

More information about the Boneh-crypto-course mailing list