Divide and Conquer Attacks

26th January 2009

These are lecture notes from my Computer Science course, not a general reference for "Divide and Conquer Attacks"

Divide and Conquer attacks exploit approximate linear relationships between function inputs and its outputs. Linearity is bad.

Geffe Generator

• 3 feedback registers
• 1 feedback register selects between the other 2
• Z = (a & b) + (not(a) & c)

Flaw in this. You can do a divide and conquer attack by attacking each register individually; when you attack one at a time, you get an ‘agreement’ amount because of the way one feedback register ‘chooses’ between the other two. So you enumerate, measuring the agreement factor.

For the final register (the ‘choosing’ one) you just have to brute force it, as the agreement factor will always be 50% (not sure why now…).

Stuff about functions

A function f(x1, x2) is approximated by g(x1, x2) if the percentage of pairs (x1,x2) that match are greater than 50%.

The two functions are ‘uncorrelated’ if they match exactly 50% of the time.

If they match less than 50% of the time you can just find another function that is the opposite (essentially).

Comments