1

I want to make guillou quisquater authentication for a website with Laravel (PHP). The authentication is between server and client(user). In the references i've read (here and here) the registration scheme is:

  1. The server selects 2 primes p and q large enough that factoring their product n = pq is infeasible.
  2. Then the server select another large prime b (0 < b < n). The values b and n are published. p and q are kept secret from all provers and verifiers.
  3. When generating new certificates, the server rolls new random private key u (0 < u < n) and public key its inverse u-1 obscured by the group key v = u-1 b. These values replace the private and public keys normally generated by the RSA scheme.

For the authentication scheme:

  1. Alice rolls random r (0 < r < n) and sends to Bob.
  2. Bob rolls random k (1 < k < n) and computes y = k ur mod n and x = kb mod n, then sends (y, hash(x)) to Alice.
  3. Alice computes z = vr yb mod n and verifies hash(z) equals hash(x).

My questions are:

  1. When user register to my website, the user has to choose username and password. But the scheme not mentioning what the username and password for. Please explain to me what is the purpose of username and password in registering and the authentication scheme.
  2. When the user register, the scheme said that the server select 2 primes p and q. Should I generate the 2 primes on each user registration? or should I generate the 2 prime numbers once and use those primes for every user?
  3. Is there any PHP library that can compute z = vr yb mod n fast? because it takes up to 3 minutes when computing this equation (I tested with p=337 and q=357)
  4. In the registration scheme (the bold sentence), should I save the p and q value in the server database?
  • You point num 1 is wrong. It is not server who selects these two numbers, it is TA. GQ requires certificates and a Trusted Authority for issuing these. I imagine username and password might be used on TA to release private key but the server should not take usernames and passwords. I'm curious. Why would you need to design such a scheme in a website? – Marko Vodopija May 3 '17 at 8:11
  • is it possible for the server to take the TA roles? because i'm a bit confused for the scheme if the server and TA are seperated. – kevin May 3 '17 at 8:34
  • It is possible, yes. The server should not have the private keys for the clients, these should be kept on the client side and the server should just sign the clients public key. Why would you need this scheme in the first place? Can't really comment on any aspect of it without some scope. – Marko Vodopija May 3 '17 at 8:38
  • I design this scheme for my thesis :) In my thesis i plan to make a zero knowledge authentication system for a website using PHP. The goal is to create a secure authentication without sending any password to the server. Now im confused how could i achieve that. Then, i am also confused about the purpose of the username and password that the client choose when they register. Because as far as i know the username and password has no function in the register and login scheme. I have read many paper and journals on this topic, but it leads to nothing Thank you in advance – kevin May 3 '17 at 8:49
0

Username and password is an authentication system where you would transmit the pair trough (encrypted) channel and use it to prove to the server that client is who it claims to be (knowledge of the password is the proof). In contrast, Zero Knowledge authentication protocols never transmit a password over the channel. They work on challenge-response scheme.

Since you are designing a zero knowledge solution based on Guillou Quisquater authentication protocol, having username and password will defeat the purpose. This would in turn answer your first question: no, you will not have username and password on the registration. The purpose of registration is to introduce the client to the server as a registered client. During registration, a user will provide some means for the server to verify the client in the future (authentication). In username and password authentication scheme, this would be the password. It would be later used to prove to the server that the client is the one who registered and the knowledge of the password is the proof of this. Registration in a zero knowledge authentication protocol would be a bit different.

On purely theoretical level, without going into details on any specific point, here are the steps needed to design such a scheme:

Registration

  1. Client will generate public and private key pair
  2. Client will present it's public key to the server (who also assumes trusted authority role)
  3. Server will make the public key into a certificate and send it to client
  4. Client is responsible for storing the certificate and private key corresponding to this certificate securely. Certificate is in turn the username and the private key would be the password even though it would never be transmitted over the wire.

Authentication

  1. Client will present it's certificate to the server
  2. Server will check the certificate and reject it if it is not valid (not issued by the server). Taken directly from article you linked:
  1. Prover chooses random k ∈ Zn
  2. Prover sends verifier Cert(prover), γ = kb mod n
  3. Verifier checks certificate, rejecting if verTA(ID(prover) || v, s)≠true.
  1. If check is successful, server will continue with the authentication scheme as you described in your question.

Answers to your questions

When the user register, the scheme said that the server select 2 primes p and q. Should I generate the 2 primes on each user registration? or should I generate the 2 prime numbers once and use those primes for every user?

These two numbers are not generated on user registration but on initial set up. You would generate them once and use them on every user registration.

Is there any PHP library that can compute z = vr yb mod n fast? because it takes up to 3 minutes when computing this equation (I tested with p=337 and q=357)

You will need to ask this specific question on another SE, probably on stackoverflow.SE. You will also need to do mathematical (RSA) calculations on the client side and will need similar toolkit there. Even though all this is purely theoretical, please bear in mind doing cryptography in the browser is tricky at best. Also, you will need to solve the storage of the client credentials (certificate and private key) on the client side too. This is not trivial!

In the registration scheme (the bold sentence), should I save the p and q value in the server database?

Since all of this is for your thesis, you need to decide the scope. If safe storage of these two numbers is out of scope, you can declare a database as a safe enough storage and save them there. The other extreme is to use HSM.

  • Thanks for the explanation, really cleared up some things for me. Can I use md5 hash and AES (symmetric key) for the certificate? – kevin May 5 '17 at 15:58
  • @kevin how would you use AES in certificate? MD5 is deprecated, you would want to use SHA-2 for this purpose. – Marko Vodopija May 5 '17 at 16:05
  • As far as I know, the server is the only one who encrypt and decrypt the certificate. Is it correct? or how it should be? The server will: 1. encrypt before sending it back to client in registration phase 2. decrypt when client send the certificate (in authentication phase), to get the ID, v, and signature. I don't want the client can read the ID, v, and signature that includes in the certificate. So, I need to encrypt them before sending it back to client. – kevin May 7 '17 at 7:50
  • @kevin v is a public key, prover should know his key. All server needs to do is sign it. You may use a HMAC for such purpose. – Marko Vodopija May 7 '17 at 8:50
  • sorry, I was wrong at the previous comment. Actually prover know his public key (v), because I generate the the private and public key in client side (with javascript), then the public key is sent to the server to make a certificate encrypted with AES, so anyone that have the certificate can't get the username inside it (especially hacker). If I replace the AES with HMAC, anyone can read the username, because HMAC only satisfy data integrity. So, can I encrypt the certificate if the prover knows his private and public key? or is there any other suggestion? – kevin May 9 '17 at 7:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.