Fastest algorithm for message authentication?

Question

I'm searching for the fastest way to verify that a message was sent by the correct user.

1. The first solution I know of is to use HMAC. But in order to verify, I'll have to produce another signature and compare it with the original. In my case, this does not seem to be the best choice, because the time needed to verify is practically equal to the time needed to produce the signature.
2. To use a classic cryptographic signature (RSA or AES) over a MD hash. I didn't find benchmarks/times for verifying a signature (but just for producing the signature). Surely, to produce a signature is slow, but to verify?
3. Finally, is there any algorithm that use a statistical method for granting authentication (most of the messages are valid)?

After comparing benchmarks, it seems there is a third way which is a lot faster (10 times more): to use the GMAC/VMAC algorithms.

I'm developing in Java, but a C/C++ library would also be OK.

Specifically, my questions are:

1. Can you confirm that the best solution is GMAC/VMAC for this scope?
2. If yes, does anyone have an example for how to write the code for generating/verifying a byte array in Java (perhaps with the Bouncy Castle library).

Answer 1

eventually is there any algorythm that use a statistical method for granting authentication (the most of the messages are granted valid) ?

This would be a non-cryptographic way of doing it and would likely allow malicious users / attackers to fake authentication.

to use a classic cryptographic signature (RSA or AES) over a MD hash. i dint find benchmarks/times for veryfying a signature (but just for producing the signature) . Surelly to produce a signature is slow, but to verify?

RSA and Rabin-Williams signatures are highly asymmetric in speed. Signature generation is slow, but verification is comparatively fast. However, RSA, ECDSA, RW and thelike are still very slow compared to symmetric methods.

Note that AES is not an asymmetric algorithm and thus does not fall into this category.

first solution I knows it to use HMAC. For veryfing the data i have to produce the signature and comparing it with the original. It seams not the best in my case because the time for verifying is equal pratically to the time for producing the signature.

HMAC is a way construct a Message Authentication Code from a hash function. There are other MACs as well, which usually are faster (because hash functions are slow), which include GMAC, VMAC and CMAC (/OMAC).

The standard recommendation would be to use HMAC with a decently fast hash function. If that doesn't cut it, and you need more speed, you probably want CMAC with AES (assuming you have hardware acceleration for AES). If even that doesn't cut it, you are probably in a hardware deployment scenario and won't use Java anyways.

Note that HMAC and CMAC don't require a nonce for proper security, which makes them a nice choice most of the time. Other algorithms like GMAC and VMAC do require a nonce and there usually will be severe security implications (like a leak of the key), if the nonce is ever re-used.

if yes in question 1, it would be usefull to see a example how do write the code for generating/verifying a byte array in java(probably the most idoneus is bouncy castle library). I thank you if you can show a short example for using it.

You will have to ask this question on a more programming focused site such as StackOverflow. Maybe also have a look at this previous Q&A there.

Answer 2

If one can live with symmetric cryptography (as considered in the question with HMAC), then from the standpoint of speed and for a single large message to authenticate per key, nothing will beat Universal hashing of Mark N. Wegman, J. Lawrence Carter; New hash functions and their use in authentication and set equality, in Journal of Computer and System Sciences, 1981. And that's simple in principle, too.

Universal hashing can be extended to multiples messages authenticated with the same key, using a block cipher or other symmetric keyed construction, and thus become a full-blown Message Authentication Code (MAC). A common implementation of that idea is Poly1305-AES. VMAC and GMAC are in this category too. The later can provide message encryption, and that makes it appreciably slower (when encryption is used, for implementations where it is optional).

If one wants the convenience of asymmetric cryptography (no secret on the receiver side) and can exchange messages in a bidirectional protocol, it is possible to use the above (Universal hashing or any MAC); the asymmetric cryptography negotiates a symmetric session key, and we are back to the previous problem.

If one wants asymmetric cryptography and have only one-way or non-iterative communication, then I know no substitute for hashing (such as SHA-256 or SHA-512 of FIPS 180-4) as part of a digital signature scheme (such as RSASSA-PSS or ECDSA of FIPS 186-4). For large messages, hashing is much slower than a Wegman-Carter MAC, typically by a decimal order of magnitude (or more) for software implementation.