Introducing Secure Comparator

A word to pass

Passwords are the ultimate keepers of security, extensively used in the 21^st century's Internet. As more and more aspects of our lives become accessible online, the importance of keeping your passwords secure becomes crucial, because anybody knowing the password may access your accounts. However, when you input password to access your account, it uses thousands of intermediate links to deliver the data, meaning that your secret password can be compromised at any moment. Thus said, being aware of (and actively using) new authentication methods means keeping your valuable assets secure.

NOTE: This article contains simplified explanation of crypto material outlined in this paper. If you'd like to read more formal cryptographic description of Secure Comparator - go there instead for theoretic part of this post.

Note: Secure Comparator has undergone revision to include more checks against dishonest provers, thanks to community feedback. Please read the corresponding post or the revised paper. These checks only extend the original method presented in this post, so, just reading "Fixing Secure Comparator" after this post should give sufficient information in proper sequence.

Existing Authentication Methods

Existing methods provide some level of protection, - better or worse, - yet each of them has some significant drawbacks. So far, most current systems and secure protocols have used only three types of cryptographic primitives: encryption, key agreement and digital signatures. More high level tasks, like authentication, are achieved by combining those primitives in some way in a protocol.

As we described in details in our previous post, several authentication methods are utilized extensively across the Internet nowadays, yet each of these systems has to fight with significant drawbacks. This situation results in a sad fact – none of the existing authentication methods is absolutely secure.

We will list all of these methods and mention their main flaws below:

• Custom hash exchange protocols (they tend to fall after first minor vulnerability in hash algorithm or infrastructure)

• HTTP authentication (despite multiple patches there are still holes in their architecture)

• Kerberos (uses bulky and unreliable architecture, server is compromised sooner or later)

• SSL/TLS (while considered a golden security standard, has a variety of weaknesses and can be hacked)

• OAuth (was compromised several times and has a significant quantity of unfixable flaws)

Zero Knowledge Authentication

Based on the above, do we have other options? Apart from aforementioned three cryptographic primitives, specifically for authentication, there is one more useful cryptographic technique: Zero knowledge proof. Simply put, it is a way to verify your password without actually disclosing it.

What is ZKP?

From Wikipedia: a zero-knowledge proof or zero-knowledge protocol (ZKP) is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true, without conveying any information apart from the fact that the statement is indeed true. Moreover, a ZKP must satisfy three properties:

1. Completeness: if the statement is true, the honest verifier (that is, one following the protocol properly) will be convinced of this fact by an honest prover.

2. Soundness: if the statement is false, no cheating prover can convince the honest verifier that it is true, except with some small probability.

3. Zero-knowledge: if the statement is true, no cheating verifier learns anything other than this fact. This is formalized by showing that every cheating verifier has some simulator that, given only the statement to be proved (and no access to the prover), can produce a transcript that "looks like" an interaction between the honest prover and the cheating verifier

   .

How Does It Differ From Traditional Authentication Methods?

First two properties form the basis of authentication and can be achieved by proper combination of other cryptographic primitives. However, the last property ensures that the protocol flow and outcome is meaningful only to protocol participants and nobody else. In other words, protocol design does not leak any auxiliary information to the third-party observers and does not provide sufficient data for dishonest verifier to succeed as a prover.

What is SMP?


Socialist millionaire is a particular example of the above ZKPs. It describes the problem when two millionaires want to compare their wealth without disclosing the values to each other (and observers on their communicating channel). Basically, you can know whether you share (know) the same password with some other party, and if your passwords do not match, you do not get any, even indirect, information about the other party’s password. The specifics of the protocol are that it assumes two parties communicating, and each party is a prover and a verifier simultaneously.


There are many potential use cases, most of them may reinforce current security systems and eliminate outlined drawbacks. They may include the following:

• a new mechanism for HTTP password authentication (ensures that password or hashes of the password never gets sent over the network)

• a way to confirm established secret key after key agreement

• a mutual authentication mechanism

• remote attestation

• an OTP reinforcement

Is it new? Has it been verified?

Zero Knowledge Proofs have been scientifically studied and verified for years. From huge scope of possible algorithms implementing it, we've picked Socialist Millionaire's Protocol for its simplicity: it allows you to do the thing and it still is simple enough for everybody to understand.

SMP is being used in Off-the-Record Messaging protocol for some time, has been audited and still showed no serious issues so far.

Secure Comparator in Themis

Cryptography

In Themis we strive to use the best state-of-the art cryptography for our library. While examining OTR implementation, we were surprised they used only prime-field modular arithmetic. As we would like the highest security level for our users, we decided to implement it from scratch using Elliptic curve cryptography.

While the fitting choice for that seemed to be ed25519, providing even better protection from side-channel analysis, as compared to conventional (NIST-driven) ECC, as well as being free from any possible copyright and/or patent claims – it was not perfect yet.

Despite being a good candidate, it was still designed as a simple digital signature algorithm, while SMP has completely different requirements. The difference between what we had in ed25519 and what we wanted to receive for our needs lies in the field of the algorithm itself, which has other order and structure of ECC primitive operations. As a result, we needed a different handling of algorithm parameters.

To add even more, basic ed25519 takes it pride in constant time operations, offering protection to users' data from side-channel attacks, which are mostly timing ones. The fact that ed25519 code has lots of room for intense optimization leads to the algorithm having a short subset of operations to begin with:

• Q = d * G - basic ECC base point multiplication
• R = s * G + r * Q - sum of two points, where one is a multiple of base point

Quite contrary, SMP requires such feature:

• T = u * P - simple point multiplication, yet P is some random (not known in advance) point

We had to extend ed25519 implementation with this functionality, at the same time armoring it even more with blinding approach to preserve its resistance to timing attacks. To read in-depth about this, please read our “Armoring ed25519 implementation for SMP” blog post.

The SMP Protocol

Our SMP protocol is very similar to one described here, except the fact that we use ECC for all computations. Let’s suppose we have two parties (Alice and Bob as always :)) with secrets x and y and they wish to know whether x == y. They use ed25519 curve with G as a basepoint. Alice starts the protocol:

• Alice:
  • picks two random numbers: a2 and a3
  • computes G2a = a2 * G and G3a = a3 * G
  • sends G2a and G3a to Bob
• Bob:
  • picks two random numbers: b2 and b3
  • computes G2b = b2 * G and G3b = b3 * G
  • computes G2 = b2 * G2a and G3 = b3 * G3a
  • picks random number r
  • computes Pb = r * G3 and Qb = r * G + y * G2
  • sends G2b, G3b, Pb and Qb to Alice
• Alice:
  • computes G2 = a2 * G2b and G3 = a3 * G3b
  • picks random number s
  • computes Pa = s * G3 and Qa = s * G + x * G2
  • computes Ra = a3 * (Qa - Qb)
  • sends Pa, Qa, Ra to Bob
• Bob:
  • computes Rb = b3 * (Qa - Qb)
  • computes Rab = b3 * Ra
  • checks whether Rab == Pa - Pb
  • sends Rb to Alice
• Alice:
  • computes Rab = a3 * Rb
  • checks whether Rab == Pa - Pb

NOTE: If the Rab == Pa - Pb check succeeds then each party is convinced that x == y. Since Rab = (Pa - Pb) + (a3 * b3 * (x - y)) * G2, iff x == y, Rab = (Pa - Pb) + 0 * G2 = Pa - Pb. If x != y, then a3 * b3 * (x - y) * G2 is a random ECC point not known to any party, so no information is revealed.

ECC-Specific Corrections

All numbers used in ECC calculations for best security must be less than ECC base point order. For ed25519 a suitable number is any 32-byte array, but with three last bits cleared in the first byte, first bit cleared and second bit set in the last byte. This applies to any random numbers used as well as for secrets themselves.

NOTE: We do not directly use secret information in SMP calculations. To allow arbitrary length string to be compared, we hash all the information and compare hashes instead. Currently, we use SHA-256 for that.

Ease of Use

Essentially, Themis is all about ease of use and ability to use complicated cryptosystems in stable and self-sufficient forms, so that they don't get problematic human errors invade their code.

themis_status_t err;
secure_comparator_t *ctx = secure_comparator_create();
...
/* Specify data to compare */
err = secure_comparator_append_secret(ctx, secret_data, secret_data_len);
/* You can call this function more than once to append data, before you start comparing */
/* err = secure_comparator_append_secret(ctx, secret_data, secret_data_len); */
...
/* if you are an initiator, start the protocol (responders skip this call) */
err = secure_comparator_begin_compare(ctx, data_to_send, data_to_send_len);
/* and send data_to_send to your peer */
...

/* receive data from your peer */
err = secure_comparator_proceed_compare(ctx, received_data, received_data_len, data_to_send, data_to_send_len);

while ((THEMIS_SCOMPARE_SEND_OUTPUT_TO_PEER == err) && (THEMIS_SCOMPARE_NOT_READY == secure_comparator_get_result(ctx))
{
    /* send data_to_send to you peer */
    /* receive back peer's response */
    err = secure_comparator_proceed_compare(ctx, received_data, received_data_len, data_to_send, data_to_send_len);
}

switch (secure_comparator_get_result(ctx)):
{
    case THEMIS_SCOMPARE_MATCH:
        /* your secret data matches your peer's secret data */
        if (THEMIS_SCOMPARE_SEND_OUTPUT_TO_PEER == err)
        {
                /* you are responder, send the final data_to_send to initiator for him to be able to complete compare */
        }
        break;

    case THEMIS_SCOMPARE_NO_MATCH:
        /* your secret data does not match your peer's secret data */
        break;

     default:
        /* some error happened? Please, submit a bug... */
}

Secure Comparator in Themis: notes on introducing advanced technology into Themis

Although we're confident that ZKP/SMP and our modifications to ed25519 are safe and secure ways to implement authentication, these algorithms in exact combination we use have not been extensively verified by cryptographic community and don't have lengthy track records (as our other objects have).

To make sure no advanced experimental code intervenes the functioning of well-established cryptosystems, we've separated them on file level, on cryptosystem definition level and in build system.

By default, SMP will not be available (even compiled), when you build Themis. If you really like the idea, have a good use-case for it or just want to give it a try, you may rebuild Themis with SMP support. On Linux just define following environment variable before issuing any build command:

export SECURE_COMPARATOR=enable
make 

That's it! You should now have Themis with SMP support. Please, feel free to provide feedback and get in touch when you apply this technology to your project.

Should we replace everything we use with it, if it is so good?

ZKP is not a single solution to all problems. Surely, you still need other primitives and protocols. It is not a replacement, but rather a supplement. It helps to reduce the potential attack scope by eliminating some of the issues outlined above. And it is a good-to-have tool to keep in mind when designing new security systems.

Possible use cases

We've designed SC to enable some specific corner-cases of authentication:

• authenticating database requests between entities, which do not have shared trust infrastructure, within request process

• authenticating username/password and enhancing key agreements in similar circumstances

• reverse proof scheme for One Time Password solutions (specifically in areas, where verifier can be partially flawed and can act against interest of prover, for instance online banking)

Thank you and stay tuned for more

Because we have some more interesting findings in applying SC in the works we plan to publish soon. Meanwhile, you can study the whitepaper and Themis source code to understand Secure Comparator more, if you're interested.