A fast authentication mode based on Multi-Block Chaining (MBC) is put forward; and its security is proved. The MBC mode is for new generation block cipher algorithms. Its speed is about 13% faster than that of the authentication modes in common use (for example, cipher block chaining-message authentication code mode). The dependence test results meet the requirement. The MBC mode is complete; its degree of avalanche effect is about 0.9993; its degree of strict avalanche criterion is 0.992 or so. The frequency test results indicate that the output generated by the MBC mode has uniformity. The binary matrix rank test results imply that it is linear independent among disjoint sub-matrices of the output. Maurers universal statistical test results show that the output could be significantly compressed without loss of information. Run test, spectral test,non-overlapping template matching test, overlapping template matching test, Lempel-Ziv compression test,linear complexity test, serial test, approximate entropy test, cumulative sums test, random excursions test and random excursions variant test results fulfill the requirements of all. Therefore the MBC mode has good pseudo-randomness. Thus the security of MBC mode is verified by the way of statistical evaluation.