Is it OK to embed mac key in cipher I am in a case where I can not share a mac key, only the encryption key. I need to provide authentication and integrity with the cipher so I would like to send a mac with the cipher. I cannot use AES-GCM for example, I am limited to AES-CBC.

Is it ok to embed mac key in the cipher in this case in term of security?

For example, like this: 

encrypt(text, key)
  mac_key = generateRandom256bitsKey()
  cipher = aes_encrypt(mac_key + text, key)
  return hmac(cipher, mac_key) + cipher

decrypt(cipher, hmac_sig, key)
  decrypted = aes_decrypt(cipher, key)
  mac_key = decrypted[0, 255]
  if (hmac(cipher, mac_key) != hmac_sig)
    return null;
  return decrypted[256, decrypted.length - 1]


Thanks,
To answer the question, no, you can't hope to get 256-bit IND-CCA2, by encrypting a 256 bit mac key.

Suppose you are playing the IND-CCA2 game and have got to the point where you have submitted two plain text messages $M_1, M_2$ and have got a challenge cipher text $C$. Your job is to decide which plain text $C$ corresponds to, with less than $2^{256}$ calls to the decryption oracle. Since you may choose both the mac and randomize the mac key (by modifying the first blocks of cipher text), the birthday paradox applies, and you are limited only by the collision resistance of the underlying hash function.

Depending on potential vulnerabilities in the underlying hash function, being able to modify the second half of the mac key, while leaving the first 128 bits of the mac key unmodified, might entail vulnerability to chose key attacks.

A more conventional IND-CCA2 secure construct would be:

encrypt(text, enc_key, mac_key)
  iv = generaterandom()
  cipher = iv + aes_cbc_encrypt(enc_key, iv, text)
  return cipher + hmac(mac_key, cipher)

decrypt(cipher, mac, enc_key, mac_key)
  if (hmac(mac_key, cipher) != mac)
    return null;
  iv = cipher[0..127]
  return aes_cbc_decrypt(enc_key,iv,cipher[128..cipher.length-1])


Please note that the usual caveats regarding all block chaining modes for 128 bit block sizes, and CBC mode in particular, apply regarding maximum amount of cipher text and maximum number of messages, before you start loosing security.

If you may choose the enc key and the mac key independently at random, that would be ideal. If not, but you are limited by a fixed size key material (the key in your question), you may extend it and split it, using a standard KDF, such as HKDF.

Please also note that if timing attacks apply, you might want to go ahead and decrypt the cipher text, even if the hmac verification fails (but still discard it in case of mac verification failure). However, if timing attacks against the application layer apply, you would anyway have to put in counter measures at that level.