Problem F
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 2: Compute the key schedule

Now that we have the RNG, create code to compute the key schedule so we can have a key stream for each user. There are two steps to creating a key for a user. Below we have provided pseudo-code for init_key and key_schedule. The first random number after warm-up is used in init_key, then the next random number is used for a step of the key generation algorithm.

init_key
Args -
RND          (16 bit random number)
ID_NUM       (8 bit user ID)
--
NUM = RND(left shift 16) OR ID_NUM    // a 16 bit number
BYTES = bytes(NUM)         // 4 bytes little-endian
return SHA256_HASH(BYTES)  // see your language's hash library

key_schedule
Args -
RND          (16 bit random number)
OLD_KEY      (256 bit old key)
--
CAT_RND = 0     // concatenate the binary of RND back to back so its 256 bits long
for i in {1,2,...,16} do
        CAT_RND = CAT_RND OR RND(leftshift 16*i bits)
return SHA256_HASH(CAT_RND XOR OLD_KEY) // this is your new key

Note: the initial key is not used as a key for encrypting / decrypting. It is only used to initialize the key schedule.

Input

Each line of input has a seed followed by an ID number, separated by a space.

Output

For each line of input, output the first 5 keys as hex strings

1 1
42 193
25 60

f3ec20cceb58d8581c696045a63229562f66bfeb820971b7d750576e2bcb4bcb 271897912debe1e9560dbf72ba8327618ab5429d4b304d159b9b4f6f2e3f9e99 e603323228c7698c0ec3dc961eb91967f35d398b0dcc7c2b5006b0385cd8635e 472d4692637ddcc1fad84be5a093e39f1ca436a3d3af2a565ebc8e7277890980 b9fac15ccbb4bec0984e0615997d2f6caa184cfc32165117cc7b7e881e309177
08dc6229ba991481e19da68042b7358bb82a0fd1c67a9ac36e292a195f1ca1d0 cd90195911043756a2bc11e6e3393e0c9f5f676088ee7cf7f236ff51344d4e4e 2921db5e09f3d24122641b23c818298e3a4a8a766a8710493101adb5a93fc6e4 e993cd55591387c711f1ff38d243c812075558b17095e3c343d78a1a6c0018a3 08f489040fcea004c0b4d4f6597212bfb0f84a39965d5bb41f70b07d65279131
6ab675bdec7496efcff9c3f7fe9f69ca4a5a51a51a4c390387077e710e1cc1bf 10907a16ad92501d046b5edc3b862a3425b885a555693110aefe2560cf56269a 32bbbdbf2f85ca8831f8f4c763c6ef387feecee2accc71fb559d4440cfa98d26 662ff8cd5077cf682c8e22396f9e7e98fa4eb6da450db3a5270ed501f913208f a6a550954fe0c01c931a2cd081c6625ddbdcb6bddd7d3d56548bbad61db3fcbf