"The second life of a 40-bit encryption key"

Some time ago I had to deal with the design and implementation of the authentication protocol. A side effect of this work was the protocol, let's call it for brevity MAuth, which uses symmetric encryption with a key length of only 40 bits, the secret key of which cannot be obtained. Today it will be about him ...

What for?

MAuth is a development of the EKE family of protocols proposed in 1992 by Stephen Bellow and Michael Merritt. Warning the criticism of such a “secret” protocol, I’ll make a reservation right away that the scope of MAuth is limited to the transfer of information that is relevant only at the time of the transfer. To put it mathematically - during the time T since it was sent by one of the parties.

An example of a task that is successfully solved by this protocol is the protection of the connection when remotely controlling an object. It is required to ensure that it is impossible to manage without knowing the secret key and reliable client authentication systems. Object management commands are not something secret and are described in its technical documentation.
')

How?

Let's use the following notation of the description of the protected protocols. The MAuth handshake mode involves just three steps:
I. C -> S: C
Ii. S -> C: {Ns} Kcs
Iii. C -> S: {K'cs} Kcs
, where C and S are identifiers of the client and authentication server, respectively;
Ns is a pseudo-random number generated by the server;
Kcs is a secret key known to the client and server;
K'cs is the session key, K'cs = H (Kcs + Ns). Here H is a cryptographic hash function.

In the transfer mode, all messages are encrypted with a session key, which has the same length as the secret - 40 bits. This is the narrowest place of MAuth.

Suppose that the attacker knows the first command that the client sends to the server. In this case, using brute force, he can pick up a session key in time T. When using modern symmetric encryption algorithms whose vulnerability has not yet been found (for example, Blowfish ), we have enough time left before T expires to perform all the operations we need and break the connection.

This protocol is resistant to all types of both passive and active attacks. Listening to the attacker will give nothing except receiving the client ID. Using a strong pseudo-random number generator does not allow to guess Ns. Hacking a session key will also not give an opportunity to get Kcs, since it is not possible to pick up a hash of a random number (Kcs + Ns).

Replaying messages will stumble upon server failure. For this reason, a pseudo-random number must be unique in the context of a server communicating with a given client.

Substitution of messages will also lead to a disconnection. Moreover, the mutual authentication of the server by the client is deliberately omitted here to increase the speed and simplicity of the protocol. If an attacker tries to impersonate a server, the client, having received the answer encrypted with the wrong session key at the 4th step, will simply break the connection.

Bonuses

In accordance with Government Decree No. 957 “On Approving Regulations on Licensing Certain Types of Activities Related to Encryption (Cryptographic) Means” in accordance with clause 1 of the provisions on developing encryption tools, MAuth can be freely used in commercial applications.

In addition, the use of symmetric encryption gives us the opportunity to get rid of a third party (certification center). A secure transmission of 5 bytes of information when registering a client is a fairly simple task (you can transfer at a meeting, or by phone).

Thank you very much for reviewing the article to Ivan Ruchkin and Dmitry Tilik.

UPD from 12/07/2010

A day after the publication of the MAuth protocol description, it was hacked by the NeverWalkAloner habraiser . He noticed that after hacking the K'cs session key during T (assuming that the attacker knows the contents of one of the messages), having {K'cs} Kcs on hand, one can get the secret key Kcs by brute force. As a result, after 2T of the session, the attacker takes control of the control object at his disposal.

UPD from 12/10/2010

How to treat? Change the handshake mode as follows:
I. C -> S: C
Ii. S -> C: {Ns} H (Kcs)
Iii. C -> S: {H (Kcs - Ns)} H (Kcs)
where H is a cryptographic hash function (hash size is 40 bits).
All subsequent messages are encrypted with the session key K'cs = H (Kcs + Ns).

One more bonus is added to the bonuses: the variable length of the Kcs secret key.

Coauthor of the revised version of MAuth: NeverWalkAloner .