Channels ▼


The Mithra Authentication Protocol

Source Code Accompanies This Article. Download It Now.

May03: The Mithra Authentication Protocol

Daniel is a developer and security engineer for Cinnober Financial Technology. He can be contacted at [email protected]

In networked environments, proper authentication between communicating parties is crucial, especially for encrypted protocols. For instance, the Diffie-Hellman (DH) key-agreement protocol is great for establishing a shared secret key, but it doesn't authenticate the parties who are agreeing upon the common secret key. Thus, malicious parties may secretly establish an encryption key between two parties and no one is the wiser. This is generally called a "Man-in-the-Middle" attack (MITM).

MITM attacks work like this: In Figure 1, Bob wants to establish a secret key with Alice. Malicious user Mallory, purporting to be Alice, establishes a key with Bob. Next, Mallory establishes a secret key with Alice, purporting to be Bob. Mallory now acts as a secret go-between and neither Alice nor Bob is the wiser. Mallory can read everything that's encrypted by Alice and Bob.

RSA offers the ability to associate users with a cryptographic keypair. Assuming key sizes have been appropriately chosen, this authentication mechanism is powerful and generally hard to defeat. However, RSA is not a panacea. There are issues associated with it, such as how to protect the private key, how to prevent a man-in-the-middle from substituting your public key from a public key directory, how to securely administrate all the keys, and so on. Given the scenario where you have users logging in from different hosts, storing the user's private key securely might also be a problem.

When public key cryptography is used as a means to authenticate an entity, certificates are often used. A certificate is simply a description of the owner of the certificate implemented as a data structure containing fields such as the:

  • Name of the certificate's owner.

  • Name of the certificate owner's organization.

  • Expiration date.

  • Issuing date.

  • Owner's public key.

  • Name of the certificate's signer.

  • Certificate's signature.

A trusted certificate is usually cryptographically signed by someone you trust, thereby testifying to the accuracy of the certificate. Usually, a certifying authority (CA) performs this task. By following the signature chain, you eventually encounter a CA certificate you trust, usually called the "root CA." If not, then the certificate you're trying to verify should be refused. This signature chain (or hierarchy) forms a certificate infrastructure; this is what's normally referred to as a "public key infrastructure" (PKI); see Figure 2.

To authenticate themselves, users with valid certificates may sign a piece of data given by the entity requesting the user to authenticate. The signed data and certificate are sent back to the requester, which can verify both the signature and the validity of the certificate. As long as the associated private key hasn't been compromised, the scheme works.

In SSL, the name of the host running the web server is used as the owner of its certificate. This enables clients to verify that they have a secure connection with the server they believe is on the other end.

Although SSL is a robust and secure protocol, the trust relationship is sometimes reversed in an intranet. In this case, clients are deemed not secure and servers need to be sure that clients aren't being spoofed. SSL can, of course, provide client authentication, but the financial cost of 1000-plus client certificates can be burdensome since SSL certificates aren't free. Moreover, certificates are usually issued on a yearly basis, so certificate costs are ongoing, and having lots of certificates adds to your system's total cost of ownership. Furthermore, public key cryptography imposes a substantial performance hit. As a Java developer, I like to cut as many performance corners as possible. That's why I developed the Mithra authentication protocol. (The source code for Mithra is available electronically; see "Resource Center," page 5.)


I designed Mithra to thwart Man-in-the-Middle attacks. Its design goals are to:

  • Detect an MITM attack.

  • Avoid sending the password (or any other authenticator) in the clear over the network.

  • Prevent replay attacks.

Mithra uses a challenge-response pattern. The way it works is that clients wishing to authenticate to servers initiate a transaction claiming to be user X. In the reply, clients receive an N-byte nonce. (A nonce is just a random piece of data, generated once and only once; after use, the nonce should never be reused.)

In Figures 3 through 6, which describe the protocol, malicious user Mallory is assumed to be sitting in the middle—intercepting, relaying, and reading traffic between server and client.

1. The client starts by sending an authentication request containing the name of the user that's to be authenticated. The server replies with an N-byte nonce (Figure 4).

2. The client computes the cryptographic hash value of the concatenated parameters: the password (pwd), IPClient, IPServer, and nonce. The computed hash value (authenticator) is sent to the server (Figure 5).

3. The server, having knowledge of the same parameters as the client, tries to reproduce the authenticator on its own (AuthServer). If the authenticator supplied by the client matches the one computed by the server, the user is authenticated. If not, then the protocol is aborted and discarded (Figure 6).

Why Does This Work?

Assuming that Mallory sits in the middle, the server's version of IPClient is IPMallory, thus producing a different hash value than the authenticator's. By the same token, the client's version of IPServer is IPMallory. Since the hash algorithm is dependent on the exact order of how the parameters are concatenated, two very different hash values are produced.

The client's authenticator would be: Hash(pwd+IPClient+IPMallory+nonce) and the server would compute: Hash(pwd+IPMallory+IPServer+nonce). These hash values would obviously not match.

Moreover, since Mallory doesn't know the password, she is not able to generate the authenticator by herself. This implies that the password should be hard to guess—preferably automatically generated—especially considering that people generally choose passwords that are easy to remember, hence, easy to guess.

If Mallory launches her MITM attack from the same host (IP address) as the client, the protocol breaks. Generally, if Mallory has the power to manipulate the client computer at will, launching an MITM attack is harder than attacking the system by some other means (installing keystroke loggers, for instance). Protecting against an attack at an endpoint is extremely difficult, if not impossible.

On the other hand, if Mallory sets up her fake server on the same host as the real server, the operating system will likely deny opening a listening port to whichever server comes up second. So, detecting that particular attack configuration is easy. Mithra is best suited for intranet systems because duplicate IP-addresses are easier to detect with an intranet (you usually have better knowledge regarding which network segments and subnets are used by your system).

Implementation Guidelines

A cryptographically strong one-way hash algorithm such as MD5 or SHA-1 should be used. MD5 and SHA-1 produce a 128-bit and a 160-bit hash value, respectively. Both algorithms are available in Java through the Java Cryptography Extension (JCE).

However, MD5 is beginning to show some cracks in its design, especially in its compression function. Furthermore, its hash value is considered to be more and more insecure against a brute-force attack as computational power increases according to Moore's Law.

On the other hand, SHA-1 produces a larger hash value, which greatly increases its resistance against a brute-force attack. Furthermore, there are newer versions of this algorithm—SHA-256, SHA-384, and SHA-512—that allow for even larger hash values. I recommend that SHA-1, or one of its newer versions, should be used in Mithra implementations.

The nonce value must never be repeated for a given password or the protocol will break. The nonce's only purpose is to guarantee the uniqueness of the resulting authenticator to thwart replay attacks. The easiest way to guarantee nonce uniqueness is to seed the pseudorandom number generator with the user's name and password and some other volatile value (a timestamp or counter, for instance).

The size of the nonce is also important. If it's too small, the nonce value space causes the nonce values to repeat, which has a negative impact on the protocol's security. Therefore, I recommend a minimum size of 16 bytes (128 bits). This yields a value space of 2128 unique values, assuming an even distribution. In reality, most pseudorandom number generators aren't able to evenly distribute all the values, but this recommendation takes that into account by allowing a fairly large error margin; 2128 is a very large number. Generally, the larger the number space, the less probability of generating the same number twice.

The host addresses should be represented as IP addresses instead of DNS host names. There are a number of security-related issues regarding DNS services, and a slew of different attacks that can be launched against DNS services. IP addresses are more static and not susceptible to DNS-style attacks, per definition. On the other hand, IP addresses are not as secure as you might think; a skilled attacker can easily forge or manipulate IP packets at will. Still, it's generally better to use IP addresses instead of DNS names.

Java offers two kinds of pseudorandom number generators (PRNGs): java.util.Random is of a type called a "linear congruential generator" and should never be used in security-critical applications (given enough mathematical skill, this number generator is trivial to break); is of better quality, hence, better suited for this type of application. More often than not, quality comes with a price, and this case is no exception. This PRNG is far slower than the other, especially in the first method invocation, when it initializes its internal state. Nevertheless, its advantages outweigh its disadvantages.

For security reasons, passwords should never be stored in the clear because they are an attractive target for attackers wishing to gain access to the system. The best way to store a password is to store only its hashed values. Identical passwords share the same hash value. Thus, a password can be verified without compromising the actual password. An attacker is then forced to generate hash values for many different passwords and see if they match the stored hash values in order to crack a given password. An attacker would typically compile a large table of commonly used passwords and their associated hash value, then start a hash value comparison routine. Whenever there's a match between the hash values, the attacker can look up the corresponding password. This is commonly referred to as a "dictionary attack." Having passwords stored in the clear constitutes a major risk to the overall security of a system. Mithra works regardless of whether the passwords are hashed.

To make a dictionary attack more difficult, a "salt" is commonly used. A salt value is simply a nonsecret value that is concatenated to the password before it's hashed. This means that for each password, the attacker must have as many hash values as there are possible salt values.

So, if an n-bit salt value is used, the attacker must generate 2n different hash values for each password. This raises the attacker's computational bar significantly. Thus, when using a salt value of 32 bits (4 bytes), the attacker has to generate 4.294.967.296 (232) different hash values for each password in order to mount a dictionary attack.

However, while salt generally makes dictionary attacks more demanding, they provide little resistance against a dedicated attack on a single password because the salt value is not a secret. An attacker usually knows which password they want cracked (for example, the administrator's). Having said that, implementing salted hashes rarely affects the security negatively and it does provide additional diffusion to the hash value, making a general dictionary attack very hard to launch.

Generally, people choose bad passwords that are easy to guess. There are mainly two ways of alleviating this problem—force users to include special characters and numbers in their passwords, or simply generate difficult passwords centrally and forbid users to set their own. Difficult passwords are hard to remember, however, so the latter approach will typically result in the user writing it down on a post-it note and sticking it somewhere close to the computer.


There are lots of password authentication protocols, but to the best of my knowledge, none I've seen can detect an MITM attack without using public key cryptography (except perhaps Kerberos). I invite you all to use, comment on, or analyze Mithra—and I'm sure someone out there will come up with a clever attack against it.


Thanks to Patrick Tennberg for providing useful comments.


Related Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.