Message Authentication - Codes: The Guide to Secrecy from Ancient to Modern Times - page 265

In the above, it is clear that there is no confidentiality since anyone can get
Alice's public key to decipher the cryptogram. To provide both authenticity
and confidentiality, Alice can first “sign” her message with her private key, then
use Bob's public key to ensure confidentiality.

Diagram 7.9 PKC Encryption: Authentication, Confidentiality,
and Signature

d B D
E d B ( E e B ( E d A ))( m )= E d A ( m )

e B

d A
E

Alice
m

−−−−−−→
E d A ( m )

−−−−−−−−−−−→
E e B ( E d A )( m )

Bob →

→ E

D e A ( E d A ( m )) = m
←−−−−−−−−−−−−−−−

D
e A

The main disadvantage to the last scheme is that an already slow PKC
process must be executed four rather than two times, so should be used only
when the highest possible security is needed.

Comparisons and Summary
MAC and enciphering functions are very closely related as we noted above
in one instance, when we discussed use of an MDC with encryption on page 265.
However, a MAC function need not have an inverse, since a MAC is typically
a many-to-one function. Also, PKC encryption can provide a virtual digital
signature, but a MAC cannot because, with a keyed MAC, both Alice and Bob
share the same secret key.
As for cryptanalysis, a hash function is only as secure as the bitlength of the
message digest. For instance, SHA-1 outputs 160-bit message digests, and SHA-
256 outputs 256-bit message digests, the latter being a very secure modern-day
option. Cryptanalyzing a MAC with a brute-force attack is more problematic
than that for a hash function since Mallory must know message-MAC pairs to
do so, as we have seen in Section 7.2. Effectively, if the (keyed) MAC outputs
n -bit message digests and the key has bitlength , then the effort required to
launch a brute-force attack on the MAC is M = min(2 , 2 n ). A similar comment
may be voiced for SKC enciphering algorithms. Hence, for an optimally secure
MAC today, we would want to see M 256 bits.

One issue we have not yet addressed is the order of encryption and au-
thentication in general. Should we encipher first, then encrypt, or should we
authenticate first, then encipher?
If we encipher first, this has the advantage that if Bob receives a message
that is invalid, he discovers this when he attempts to authenticate it. Thus,

≥