Encrypt-and-mac IND-CCA security I have been stuck all day trying to understand how to show that an Encrypt-and-Mac ($SE_{EaM}$) scheme is not IND-CCA secure. I have seen this similar post, however it is slightly different and the notation in the selected answer confuses me.

The line of thought I want to follow is this: While the $MAC$ is perfectly UF-CMA secure it could still reveal information on the message since its computed directly from it and not the ciphertext (like in encrypt-then-mac). Consequently this would mean that $SE_{EaM}$ is not even IND-CPA secure, and therefore not IND-CCA secure. I want to know first if this line of reasoning is sound. 

In terms of actually showing this, is it feasible to simply suppose that the $MAC$ scheme could afford no privacy to the message whatsoever. The post I referenced seems to have done that by adding the message in the clear to the actual tag ($t = m|t$), if I misunderstood I would appreciate clarification. If this is valid how could I use this in a IND-CPA game of $SE_{EaM}$?

I hope it will then become clearer how to show in a reduction that since IND-CCA implies IND-CPA, my $SE_{EaM}$ scheme is not IND-CCA. Or maybe I am looking at it completely wrong, in which case do let me know.

Thanks and happy new year!
There is an excellent paper from Bellare and Namprempre that addresses the security properties of composite schemes in a rigorous and formal manner. Regarding IND-CPA security of Encrypt-And-MAC the paper has this to say:


  E&amp;M does not provide IND-CPA. E&amp;M does not preserve privacy because the MAC could reveal information about the plaintext. This is true regardless of whether the MAC is weakly or strongly unforgeable. We provide details assuming that the MAC is strongly unforgeable below.
  
  Let $\mathcal{MA = (K_m, T , V)}$ be a given MA scheme. We define an MA scheme $\mathcal{MA'}$ which is the same as the given one except that it prepends the first bit of the message to the tag. Formally $\mathcal{MA' = (K_m, T', V')}$ has the same key generation algorithm as the given MA scheme and the following tagging and verification algorithms:
  
  Algorithm $\mathcal{T'(K, M)}$
  Parse $M$ as $x||M'$ where $x$ is a bit
  Return $x||\mathcal{T}(K, M)$
  
  Algorithm $\mathcal{V'(K, M, \tau)}$
  Parse $M$ as $x||M'$ where $x$ is a bit
  Parse $\tau$ as $s||\tau'$ where $s$ is a bit
  If $x = s$ and $\mathcal{V}(K, M, \tau') = 1$ then return $1$
  Else return $0$  
  
  It is easy to see that if $\mathcal{MA}$ is SUF-CMA secure then $\mathcal{MA'}$ is SUF-CMA secure. However, if $\mathcal{MA'}$ is used as the base message authentication scheme in the E&amp;M composition method, the resulting symmetric encryption scheme will not achieve IND-CPA because the first bit of the message is provided to the adversary via the MAC. The adversary can use this to break the scheme in the IND-CPA sense as follows. It queries its $\mathrm{LR}$ oracle with two messages $M_0$, $M_1$ such that the first bit of $M_0$ is $0$ and the first bit of $M_1$ is $1$. It gets back ciphertext $C = C'||\tau$ . It lets $s$ be the first bit of $\tau$ . As per our construction above, $s$ is the first bit of $M_b$ and hence $s = b$, so the adversary returns $s$. The advantage of this adversary is one.
  
  In fact, we can make a stronger statement. Not only do there exist schemes for which the E&amp;M method fails to provide IND-CPA, but it will fail to be so for most of the commonly defined MA schemes, including CBC-MAC and HMAC, because the latter are MACs. Indeed, an adversary can use the MAC present in the ciphertext of the composite scheme to see whether the same message has been encrypted twice, something which should not be possible if the scheme is to meet a strong notion of privacy like IND-CPA. This attack is successful regardless of whether the underlying MAC is weakly or strongly unforgeable.
  
  E&amp;M does not provide IND-CCA and NM-CPA. Since both IND-CCA and NM-CPA imply IND-CPA, the above means that E&amp;M provides neither IND-CCA nor NM-CPA secure.


So your line of reasoning that you provided in your question is correct. We can use the fact that a MAC can leak information about the plaintext to break such a schemes IND-CPA security. Then, it follows that, since IND-CCA implies IND-CPA, a scheme that is not IND-CPA is not IND-CCA.