How do I verify a message came from me?

Question

I have many clients and a single server, and on each of these clients I want to be able to verify a message did indeed come from my server. My idea was to send some sort of key with cryptographic significance.

For example, say I wanted to send a boolean from the server to the client, I could send a message like this:

{
    "boolean": true,
    "key": 30
}

In this trivial example, the significance of the key is that it is divisible by 3. So the client would perform a check like this:

if payload["key"] % 3 == 0:
    valid = True
else:
    valid = False

Is this a good idea provided I use a more secure algorithm? If so, what would you suggest?

If not, how should I go about verifying the authenticity of the message?

Thanks.

EDIT:

My understanding of the HMAC approach is as follows:

Firstly you generate a key which will be stored on the server and all of the clients. For example,

import random
key = bytes(hex(random.getrandbits(128)).encode("utf-8"))

Then, on the server when you want to send a message to a client, you generate a HMAC as follows and send it along with the message:

import hmac
import hashlib
h = hmac.new(key, str(payload["key"]).encode("utf-8"), hashlib.sha3_256).hexdigest()

Then on the client, you run this again with your key and if they match then it is a valid message.

I have two problems with this approach. Firstly, there are only two possible HMACs - one for true and one for false. Additionally, hardcoding the secret key into the client doesn't sound like the best of ideas.

Answer 1

What you need is a digital signature algorithm. Public key cryptography means that you have a public and private key. The server can sign a message by performing some maths on it using his private key. All the clients, who know the servers public key, can then do some maths to verify the signature using the servers public key, proving the authenticity.

Server:

• create message

• sign the message with server private key

• append the signature to the message

• encrypt this all with client public key

• send to client

Client:

• recieve ciphertext

• decrypt ciphertext with client private key

• split the signature from the message

• verify the signature with server public key

• do something with the message

Public key cryptography algorithms include RSA and ECC. PyCryptoDome has both of these if you are continuing to use Python.

Side note: its advised not to use a psuedo-random number generator for crypto purposes, os.urandom,the secrets module or Crypto.Random (PyCryptoDome) are Crypto safe.

EDIT: The maths behind how a message is signed is different per algorithm. The signature is like a tag of authenticity that is sent with the message, and this tag cannot be re-created by anyone else. Anyone can verify the tag, given they know the server's public key.

Answer 2

Yes, this is a way to establish authenticity through the use of a so-called "shared secret".

In practice you could do it using the HMAC algorithm and a shared key between the server and clients.

Notice that here, there is a problem with shared keys: that is that the whole system is not secure as soon as one client is breached. There are also other ways to establish authenticity of messages without this problem by the mean of public key cryptography. In this case your server would be the only one knowing the secret key, and would sign its messages with it, so that the clients, knowing the public key of the server could verify the authenticity of the messages. Typical algorithms to do so are ECDSA or Ed25519.

Edit

As requested, here are more details regarding how these would work in practice:

HMAC

This is almost exactly as you described in your own edit.

1. You create a secret HMAC key, which you store on both the server and the clients.
2. You have a message which you want to authenticate, so you just "HMAC" it on the server using the secret HMAC key, and you send both the message and the HMAC digest to your client(s).
3. The client receives the message and the HMAC digest and computes the HMAC digest of the message, and then verifies it matches the one it received.

There is just one slight caveat I have with your way: you pass the value str(payload["key"]).encode("utf-8") as the msg in your HMAC call, but what is contained in your payload["key"] value? You would rather have your payload itself being passed to the HMAC and then append the hexdigest to the message, thus you'd have a structure a bit like this for your messages:

{
"payload": {
    "boolean": true,
    },
"mac": {
    "hmac-digest": "6eb6a866856dc7ea74c0d6bd41993106f696cc5091f88f188efbb23def6d248b"
    }
}

Now, as you said in your edit, HMAC values being deterministic, if you authenticate twice the same message, you'd get twice the same digest. But HMAC is about protecting authenticity of the messages, not confidentiality. (Notice that with HMAC, you get both authenticity and integrity of the message.)

Also, it is true that HMACed messages are trivially vulnerable to replay attacks, but so are public-key signed message. Adding a replay protection to your protocol is not that easy, and usually requires being stateful.

To have replay attack protection, you'd typically need to have a message index value, and keep track (thus being stateful) of the said index on each clients. (And reject any message that does not increase the index value.)

{
"payload": {
    "boolean": true,
    "index": 12 
    },
"mac": {
    "hmac-digest": "a1b0271d1eea012c81f06488645ce026914e095d9d770d7d213efbd968be3fe2"
    }
}

But notice that this is still vulnerable to replay attacks between clients, if all clients are not getting the same message at the same time...

Thus, you might want to include sender and receiver data in your payload, so that these are authenticated as well... as you can see the complexity of your protocol is increasing relatively fast!

Public key crypto

So, if you are to use public key crypto to authenticate your messages, the process would only differ slightly from the previous workflow:

1. You create a private key and its corresponding public key on the server and store them there.
2. You store the public key of the server on each of your clients.
3. You have a message which you want to authenticate, so you sign it on the server side using the private key, and you send both the message and the signature to your client(s).
4. The client receives the message and the signature and uses the public key of the server to verify that the signature was indeed produced by someone knowing the server's private key.

There a multiple algorithm to do so: - ECDSA - Ed25519 - RSA-PSS

Notice that the same caveats as with HMAC applies here: you might need to authenticate more than just the message to avoid replay attacks and any other abuse of your protocol.

Answer 3

The answers of @Lery and @SamG101 are good. In cases when receiver wants to be sure that the message comes really from you and not from smb. else who pretends to be you, such signature is sufficient.

But in some cases it is important to show who was the first one who sent the message, for instance, who was the first to solve some important problem. In such cases a simple signature is not sufficient because smb. else can sign message text with his key and sent to the others. Depending on time settings in your system and in systems of the others, depending on message routing etc. it may happen that many (or even the most of) recipients receive the 2nd message before yours.

If you actual goal is to show that you were the first one who sent this message, then you should also use some trusted timestamping service. There are many kinds of such services. I just wanted that you check if timestamp is important in your use case.

Update: To your question What actually is the signature?

Simplified, it looks as follows: For the message you want to send a hash is generated. There are different standardized algorithms for that. The hash is quick and resistant to collisions, so that it is very unlikely that 2 different messages produce the same hash. Then this hash is encrypted using your private key and added to the message. This encrypted hash is actually the signature.

Everyone who reads the message repeats the same hashing process and obtains the same hash. Then they use your public key to decrypt your signature. If decryption is successful and the hash is the same as they calculated, it means that only you could create this encrypted hash and thus the message comes from you.

Some important features of the digital signature:

• Everyone can decrypt your signature and thus check if you have created it
• If the signature can be decrypted with your public key, it means that the message comes really from you, because nobody can create anything decryptable with your public key
• It means also that you cannot deny that you have not signed it. Only you could do that (it is your responsibility to keep your private key safe)
• If calculated hash is not equal to the decrypted hash, it means that this signature does not sign this message. In such case there is no way to find out how much different the message is from what was signed, only one bit changed or the message is completely different.
• Hash algorithms are constructed in such way that they are quick and at the same time have good collisions resistance. I.e. the probability that 2 different messages produce the same hash is very low. If smb. takes your signature from some other message (you cannot deny that this is your signature) and tries to create another message that gives the same hash that you signed, it will be impossible. So you can be sure that your signature can be associated only with messages that you have really signed.