Using rainbow tables to find encryption keys of block ciphers?
Define a function that takes the 4-bit plaintext identifier and the 36-bit key as input. For the purpose of the rainbow table you can treat it as an opaque 40-bit value.

The output of this function is the ciphertext you get when you encrypt the plaintext corresponding to the identifier with the specified key.

One you have this function, you can proceed with the rainbow table creation like you'd do for any other function.