CodeGate Qualifiers CTF 2012 : Misc #2 - 200 Points

CodeGate Qualifiers CTF 2012 : Misc #2 - 200 Points

Given Hints:

Alice wants to send a message to Bob in secure way.

Alice encrypted a plaintext PA = ¡°IMISSYOU¡± = 0x494D495353594F55 by using DES
and obtained ciphertext CA = 0xFA26ED1833264435.

Alice sent the ciphertext CA and the secret key to Bob. The secret key was encrypted
by converting each of its letters to a pair of digits giving its position in the
typewriter keyboard. More precisely, the following table is used.

1 2 3 4 5 6 7 8 9 0
---------------------------------------------------
1 | Q W E R T Y U I O P
2 | A S D F G H J K L
3 | Z X C V B N M

In this manner, 'A' is converted to 21, 'B' to 35, etc. In transmission, all of the
first digits were lost and the received secret key resulted in the pairs:

?8 ?9 ?9 ?4 ?3 ?5 ?9 ?5

After a few minutes, Bob recovered the secret key and smiled. Bob decided to reply in the same way.

Bob encrypts a plaintext PB = 0xB6B2B6ACACA6B0AA by using DES and obtained ciphertext CB = 0x05D912E7CCD9BBCA.

What is the secret key which Bob used? (0x????????????????) (Bob's secret key is different from Alice's secret key)

Identifying File:
We first begin by recovering the secret key. We know these are the possible letters by referencing to the table above:

?8 ?9 ?9 ?4 ?3 ?5 ?9 ?5
------------------------------
I O O R E T O T
K L L F D G L G
V C B B

From the list of possible letters, we can deduce the secret key to be

I L O V E B O B

We confirm this secret key to be correct by testing it out using DES.
Where do we proceed from here? We know the plaintexts PA and PB, the ciphertexts CA and CB and also the secret key SA. How are we going to determine the secret key SB with the information gathered? With some research and thinking, we know:
This CTF session lasts for only 36 hours and several teams manage to solve this challenge within hours.
With the available information, we know we have to conduct a "known plaintext attack", which needs days to brute-force. In view of practicality, this is clearly not the correct direction to head towards solving the challenge.

Let's take another look at the available information:

Plaintext Ciphertext Secret Key
------------------------------------------------------------------------
Alice | 494D495353594F55 FA26ED1833264435 494C4F5645424F42 (ILOVEBOB)
Bob | B6B2B6ACACA6B0AA 05D912E7CCD9BBCA

If we look close enough at the information above, we can make out some noticeable patterns from them => 0x5 in PA becomes 0xA in PB, 0x3 in PA becomes 0xC in PB, 0x2 in CA becomes 0xD in CB, etc. As the list grows, we can actually deduce a trait:

4 -> B 9 -> 6 D -> 2 5 -> A 3 -> C F -> 0
(0100) (1011) (1001) (0110) (1101) (0010) (0101) (1010) (0011) (1100) (1111) (0000)

A -> 5 2 -> D 6 -> 9 E -> 1 1 -> E 8 -> 7
(1010) (0101) (0010) (1101) (0110) (1001) (1110) (0001) (0001) (1110) (1000) (0111)

The common trait among the hex characters is the toggling of bits, which are shown in brackets. For bit manipulation, we can use the exclusive-OR operator (^) to achieve this toggling of bits action.

Let's toggle the bits in the secret key CA to obtain secret key CB and use DES to verify it:

494C4F5645424F42
^FFFFFFFFFFFFFFFF
----------------
B6B3B0A9BABDB0BD

Final Solution:
Flag: **B6B3B0A9BABDB0BD**

cheers
Mr.D