Problem G
Encrypted Chat App

Background

Persons of interested have been observed using a chat protocol they designed. We must figure out if there are any mistakes they made when implementing so we can decrypt their messages. The general algorithm is as follows:

1. User A creates a random number, user B creates a random number

2. The random numbers are traded using a public-key encryption and authentication scheme.

3. With the random numbers, each user creates a key stream for A and B

4. A/B encrypt/decrypt messages using an asymmetric encryption algorithm (in this case, AES256).

The following is the format of the resulting message:

[ID][to code][from code][start byte][encrypted message][end byte]

ID

- bytes of usrLETTER_#PACKETNUM

to code

- receiver username in base64

from code

- sender username in base64

start byte

- start of message byte code, 1f1f

encrypted message

- the actual encrypted message

end byte

- end of message byte code, 0f0f

This part of the algorithm appears secure, but we believe there is a mistake they made which we can use to decrypt the traffic.

Part 3: Decrypt the messages

Given some traffic from the chat application, decrypt the messages using a weakness in the RNG and return the crypto-variables (seed and user ID).

Each user on each device has a running key list which is used to encrypt (and decrypt) messages. The random numbers, register states, and IDs used to initiate this process are shared via key public key encryption. Then users can message back and forth using a stream of new keys to avoid re-using keys. Below is some rough pseudo-code for how we believe the users are encrypting their messages.

The actual encryption used on the messages seems to be some sort of Feistel cipher. Each 64 byte block of data is operated on via a split and recombination step. Many of these steps are performed, along with mixing in key material, to perform a sort of permutation of the input data.

Below we have provided the encryption pseudo-code. Your job is to implement the decryption step, and brute force the required cryptovariables.

encrypt_step
ARGS - bytes (64 bytes)
       key (32 bytes)
L = bytes[FIRST 32 BYTES]
R = bytes[LAST 32 BYTES]
L_new = R
R_new = L XOR R XOR key
return L_new + R_new (64 bytes)

encrypt_message
ARGS - message (bytes)
       key (32 bytes)
message_blocks = message[BREAK INTO 64 BYTE CHUNKS]
FOR i IN number of message_blocks:
    block = message_blocks[i]
    FOR j IN STEPS:
        H = HASH(special_bytes(i,j))
        K_ij = key OR H
        cipher = encrypt_step(block, K_ij)
return CIPHER (the encryped bytes)

HASH is an unkown hash function, but we are almost certain it is one of the popular hashes, and its digest is 256 bits.

special_bytes
ARGS - i (int)
       j (int)
BYTE1 = 11(base 16) XOR i[LEFT SHIFT 2]
BYTE2 = 22(base 16) XOR j[LEFT SHIFT 3]

Note: A new key is used for each message sent, this is computed using the key schedule. You will also need to think about how to detect the decrypted messages once your brute force approach finds them.

Input

Each line of input is a sequence of bytes of the packet. Note that there are all taken to be first / new messages, that is, there is no key relation between them.

Output

For every line of input, output the seed and ID, separated by a space.

117 115 114 95 35 49 49 100 71 86 122 100 70 57 49 99 50 86 121 31 31 141 6 134 44 94 31 133 31 155 110 2 47 55 201 242 146 115 157 155 208 157 251 152 48 20 154 135 241 155 159 159 124 67 168 121 106 36 97 91 180 195 16 250 121 241 118 40 212 133 101 5 123 112 12 38 204 162 108 97 79 103 33 41 165 15 15
117 115 114 95 35 49 50 100 71 86 122 100 70 57 49 99 50 86 121 31 31 219 129 186 88 135 145 139 158 205 27 10 106 9 208 131 216 151 140 143 71 186 208 138 87 156 211 159 235 138 223 141 194 69 43 96 108 117 111 55 56 23 37 240 52 247 110 109 6 98 118 57 100 118 111 116 175 98 165 125 70 126 117 115 63 15 15
117 115 114 95 35 49 51 100 71 86 122 100 70 57 49 99 50 86 121 31 31 246 15 190 45 6 92 20 148 140 170 6 186 58 131 212 194 191 223 126 31 246 187 253 190 119 175 255 174 239 178 159 127 216 225 96 121 121 32 216 121 210 22 236 100 228 125 42 188 77 1 0 1 9 5 3 64 227 75 21 1 17 1 41 129 15 15

3 240
12 3
49 103