September 2011 Archives

Having trace.pkl file and title with keyword "power" we know thats it's an Power Analysis task. In task said it's an signature generation function, by task name keyword "tokens" we can assume it's RSA.

If we plot some of our data list, we get something like:
Can you see impulses?

Main idea of Power analysis is that different instructions have different power consumption patterns.
RSA signature generation:

S = M^d mod N

or

S=1
for i =L-1 downto 0:
    S = S^2 mod N
    if di == 1:
        S = S * M mod N

For every bit of d we've square and if bit = 1 we've multiplication also. So we just check our data for duration patterns:
short+long=1, short=0. Simple, hah?

Sources included.
Thanks to @hellman1908 for error corection!

Fluxfingers posted their second pre-ctf challenge. It looks like "nc 0xbadcab1e.lu 9999"
Sending "test" as input we get the following response:

Using secp192r1, SHA-1.
connected at Tue Sep 13 23:03:25 2011.
Your message is test.
(r, s) = (0xe529012d41b1b2667c60764d75ab3318eda4043240bc003b, 0x79a546c30d1097473f675d3b9ee3fb55f9f6e6fd2127f8b)

As we can see SHA-1 is a signature hash function, and secp192r1 is an elliptic curve identificator. So, we have Elliptic curve, hash function and signature = ECDSA.
Sending same message to the server couple of times - we receive different signatures. But if we send same message two times fast enough:

$ echo "test" > /tmp/121
$ echo "test" > /tmp/122
$ perl -e 'foreach (1,2) {`nc -vvv 0xbadcab1e.lu 9999 < /tmp/12$_ >> /tmp/res`}' && cat /tmp/res

This is the signature generation machine.
Using secp192r1, SHA-1.
connected at Tue Sep 13 23:32:03 2011.
Your message is test.
(r, s) = (0x807baa0fd768f05ea851a8a48b0b3f509d02c0f1fc148e36, 0x5551c48119129b3e6bfc1a705d08455cde0fc10f527c1925)

This is the signature generation machine.
Using secp192r1, SHA-1.
connected at Tue Sep 13 23:32:03 2011.
Your message is test.
(r, s) = (0x807baa0fd768f05ea851a8a48b0b3f509d02c0f1fc148e36, 0x5551c48119129b3e6bfc1a705d08455cde0fc10f527c1925)

Boom! k value to be reused, and likely k is a timestamp. Let's check:

$ echo "test1" > /tmp/122
$ cat /dev/null > /tmp/res
$ perl -e 'foreach (1,2) {`nc -vvv 0xbadcab1e.lu 9999 < /tmp/12$_ >> /tmp/res`}' && cat /tmp/res

This is the signature generation machine.
connected at Tue Sep 13 23:36:53 2011.
Your message is test.
(r, s) = (0xf5e361f5e7e9936b1313ea2a8ad49a42f91fca30f232739d, 0xce8e2c43f6245d1f446a100baed038887c70e8e8fe5b2365)

This is the signature generation machine.
Using secp192r1, SHA-1.
connected at Tue Sep 13 23:36:53 2011.
Your message is test1.
(r, s) = (0xf5e361f5e7e9936b1313ea2a8ad49a42f91fca30f232739d, 0xe9a22b9c1feb92d719dc660ab8b3f25207105edb09d3e2ba)

e1 = sha1("test")
e2 = sha1("test1")
s1 = 0xce8e2c43f6245d1f446a100baed038887c70e8e8fe5b2365
s2 = 0xe9a22b9c1feb92d719dc660ab8b3f25207105edb09d3e2ba

compute k

k = 1315957013

Is it a timestamp?

>>> datetime.datetime.fromtimestamp(k)
datetime.datetime(2011, 9, 14, 3, 36, 53)

Having k we can easily compute d:

d = 373503280115841781950920337998842730338017239909
ascii(AlwaysUseAFreshNonce)

To check if d is correct - sign message "test" using curve secp192r1 and found d.