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

pair ( ( M ) , MAC( M )) is transmitted to the intended receiver. In the EtA com-

position, the plaintext is passed to the encryption algorithm to get a ciphertext,
the resulting ciphertext is passed to the MAC algorithm to get a tag, and the
resulting (

E

( M ))) is transmitted to the intended receiver. In the
AtE composition, the plaintext is passed to the MAC algorithm to get a tag,
the resulting tag is appended to the plaintext message and the result is passed
to the encryption algorithm, and the resulting (

E

( M ) , MAC(

E

( M, MAC( M ))) is transmitted
to the intended receiver. The transport layer of SSH uses a variant of E & A [51],
IPsec uses a variant of EtA [14], while SSL uses a variant of AtE [21].
Over dedicated primitives, generic compositions possess several design and
analysis advantages due to their modularity and the fact that encryption and
authentication schemes can be designed, analyzed, and replaced independently
from each other [38]. Further, and most important, generic compositions can
allow for faster implementations of authenticated encryption when fast encryp-
tion algorithms, such as stream ciphers, are combined with fast MACs, such as
universal hash functions based MACs [38].
The E & A composition has a parallelizable advantage over the EtA and the
AtE constructions. The fact that the encryption and authentication operations
can be performed simultaneously can further increase the eciency of the generic
composition. On the other hand, the E & A composition imposes an extra require-
ment on the MAC algorithm. As opposed to the EtA and AtE compositions,
the tag in the E & A composition is a function of the plaintext message (not
the ciphertext as in EtA ) and is sent in the clear (not encrypted as in AtE ).
Therefore, the tag must be at least as confidential as the ciphertext since, other-
wise, the secrecy of the plaintext can be compromised by an adversary observing
its corresponding tag. This implies that generic compositions are more involved
than just combining an encryption algorithm and a MAC algorithm. Indeed,
in [38] and [5], the security of different generic compositions of authenticated
encryption systems is analyzed. Using a secure encryption algorithm (secure in
the sense that it provides privacy against chosen-plaintext attacks) and a secure
MAC (secure in the sense that it provides unforgeability against chosen-message
attacks), it was shown that only the EtA will guarantee the construction of se-
cure channels. Therefore, special attention must be paid to the design of secure
channels if the E & A or the AtE compositions are used.
Although significant efforts have been devoted to the design of dedicated au-
thenticated encryption primitives, and the analysis of the generic compositions,
no effort has been made to design new primitives that utilize the special char-
acteristics of the generic compositions. In this paper, we provide the first such
work. Specifically, we introduce the design of special purpose MACs to be used
in the construction of E & A compositions. The driving motive behind this work
was the intuition that MACs used in the generic composition of authenticated
encryption systems, unlike standard MACs, can utilize the fact that messages
to be authenticated must also be encrypted. That is, since both the encryption
and authentication algorithms are applied to the same message, there might be a
redundancy in the computations performed by the two primitives. If this turned

E