E-MACs: Towards More Secure and More Efficient Constructions of Secure Channels - Information Security and Cryptology-ICISC 2010 - page 304

had never encrypted, while INT-CTXT implies that it is computationally infea-
sible for an adversary to produce a ciphertext not previously produced by the
sender, regardless of whether or not the corresponding plaintext is new .
Although the work of [5] shows that the E & A composition is generally inse-
cure, the results do not apply to all variants of E & A constructions. For instance,
the E & A composition does not provide indistinguishability under chosen plain-
text attacks (IND-CPA) because there exist secure MACs that reveal information
about the plaintext ([5] provides a detailed example). Obviously, if such a MAC
is used in the construction of an E & A system, the resulting composition will not
provide IND-CPA. Unlike standard MACs, however, it is a basic requirement of
E -MACs to be as secret as the used encryption algorithm. Indeed, Theorem 1

guarantees that the proposed -MAC does not reveal any information about the

plaintext that is not revealed by the ciphertext.
Another result of [5] is that the generic E & A does not provide INT-CTXT.
(Although the notion of INT-PTXT is the more natural security requirement
[5] while the interest of the stronger INT-CTXT notion is more in the security
implications shown in [5].) The reason why E & A compositions generally do not
provide INT-CTXT is that one can come up with a secure encryption algorithm
with the property that a ciphertext can be modified without changing its de-
cryption [5]. Obviously, when such an encryption algorithm is combined with
the proposed

E

-MAC to construct an E & A system, since the tag is computed
as a function of the plaintext, only INT-PTXT is reached.
In practice, however, it is possible to construct an E & A system that does
provide INT-CTXT. For instance, a sucient condition for the proposed

E

-MAC
to provide INT-CTXT for the composed system is to be used with a secure one-
to-one encryption algorithm. To see this observe that any modification of the
ciphertext will correspond to modifying the plaintext (since the encryption is
one-to-one). Therefore, by Theorem 2, modified ciphertexts can only be accepted
with negligible probabilities. Indeed, secure E & A systems have been constructed
in practice. A popular example of such constructions is SSH [51], which uses a
variant of E & A the has been proven to be secure in [4].
So far, we have shown that E -MACs can be used to replace standard MACs in
the construction of E & A systems with two additional properties: they can have
provable confidentiality and they can be more ecient (observe that the tag of the
proposed

E

-MAC is the output of the universal hash function; no post-processing
was performed). What we will show next is that

E

E -MACs can have another security

advantage. More specifically, we will show that -MACs can utilize the structure

of the E & A system to achieve better resilience to a new attack on universal hash
functions based MACs; namely, the key-recovery attack [27].

E

6 E -MACs and Key Recovery

Recently, Handschuh and Preneel [27] showed that, compared to block cipher
based, MACs based on universal hash functions have a key-recovery vulnerability.
In principle, a small probability of successful forgery on authentication codes is