Understanding hybrid cryptography's concepts: signing and CA

Question

After learning about symmetric encryption, public-key encryption, one-way hash, digital signature and digital certificate, I was tasked to think of an imaginary hybrid cryptosystem. I was thinking along the lines of this:

• Alice and Bob agrees on a shared private key that is to be used to encrypt (using encryption algorithm like AES) messages
• To reach private key agreement, Alice and Bob will use DH
• Alice now wants to send the message p to Bob
• To ensure that Bob can verify the message p comes from Alice, Alice will sign the message p.
• Because signing requires a lot more resources and can only typically only sign a message with a limited amount of length, Alice will first hash (say using SHA-1) then message p to a message digest called md1. The message digest md1 is then signed by Alice (using some signing algorithm like RSA). This message digest md1 now contains a digital signature and will be called s
• Then, Alice will send both the original message p and the signed message digest s after encrypting them using an encryption algorithm (say AES) using the private key that was agreed upon during DH. Alice also sends the required information in regard to verifying the signature.

Now the message sending process is done. It's Bob's turn to receive the sent packages:

• Bob will receive and encrypted original message p and signed message digest s
• With RSA, Bob can convert the signed message digest s back to message digest md2
• To verify that the message has not been tampered with midway, Bob will now hash using the same hashing algorithm (in this case, SHA-1) from the sent original message p to create another md3
• Bob then checks if md3 and md2 are the same or not. If they are, they are from Alice. If they're not, Bob will ignore this message
• Bob has now received the original message

I was thinking along the lines of the above, but some points went over my head.

---

Questions:

1. Bob magically knows that the algorithms used are SHA-1, RSA and AES. How do Alice and Bob agree on the algorithms used in the whole process?
2. When I'm hashing and signing, I'm providing integrity and authentication at the same time. Are these two processes inseparable if I want to provide both aspects? I'm assuming that you always sign the message digest because of efficiency problems (as mentioned above), is this correct?
3. The very first step of DH is to exchange a public key generated by Alice and Bob. To do that, they will need to agree on an initial large prime number pn and its prime generator g. Then, I will send the public key generated by both sides. However, as I will be exchanging messages, how do I know that the agreed pn and g are not tampered by others and that the public key sent from both sides are indeed from themselves and not an attacker? Do I need to sign these message exchanges?
4. As you can see in my example, I have failed to involve a CA in my imaginary hybrid cryptosystem. In my understanding, a CA will verify that messages are indeed from a company/person. To verify the messages are from one side, CA will see the digital certificate that is sent alongside the message. However, why do I need to involve a CA when I can sign a message myself and ask the receiver to verify the signed message? Why involve a third-party?

Answer 1

You're confusing a lot of things:

Alice and Bob agrees on a shared private key that is to be used to encrypt

You cannot have a "shared private" key; sharing and keeping things private are opposite terms. That would be called a secret key, as it is kept secret between Alice and Bob (some books confuse these terms as well, but yeah).

To reach private key agreement, Alice and Bob will use DH

OK, the first statement should come after this second one. And yeah, secret key agreement or establishment.

To ensure that Bob can verify the message $p$ comes from Alice, Alice will sign the message $p$.

With what key? You've used key agreement using DH and you've specified that you'd use a secret key for encryption.

Because signing requires a lot more resources and can only typically only sign a message with a limited amount of length, Alice will first hash (say using SHA-1) then message $p$ to a message digest called $\mathit{md1}$.

Hashing is typically part of the signature generation and verification operation.

encrypting them using an encryption algorithm (say AES)

AES is a block cipher, it is not a generic cipher that handles messages of any size, and it isn't CPA secure by itself. This matters because if e.g. you'd use AES CBC, it may fail to padding oracle attacks before you decide to check the signature. This was one of the mistakes of e.g. the early TLS protocols (well, up to 1.2, so this is not the distant past or anything).

With RSA, Bob can convert the signed message digest $s$ back to message digest $\mathit{md2}$.

There is no rule that retrieval and comparing hashes is part of the verification procedure for signature schemes. Recalculation of the hash is of course necessary, but the verification procedure may have a different way of making sure that the hashes are identical.

---

1. Bob magically knows that the algorithms used are SHA-1, RSA and AES. How do Alice and Bob agree on the algorithms used in the whole process?

They agree on it beforehand. The algorithms may be static, depend on a single version number, or be established during a handshake (a la TLS).

2a. When I'm hashing and signing, I'm providing integrity and authentication at the same time. Are these two processes inseparable if I want to provide both aspects?

The processes are not inseparable but they are commonly linked to each other. Unless you explicitly think of a way to untangle them you're probably OK for both.

2b. I'm assuming that you always sign the message digest because of efficiency problems (as mentioned above), is this correct?

That depends, as you'd normally use an authenticated cipher or MAC to provide message integrity / authenticity. Those may not use a hash at all.

3. The very first step of DH is to exchange a public key generated by Alice and Bob. To do that, they will need to agree on an initial large prime number $\mathit{pn}$ and its prime generator $g$. Then, I will send the public key generated by both sides. However, as I will be exchanging messages, how do I know that the agreed $\mathit{pn}$ and $g$ are not tampered by others and that the public key sent from both sides are indeed from themselves and not an attacker? Do I need to sign these message exchanges?

That's not strictly necessary as using different values will lead to an invalid secret. It does make sense to:

1. Validate that DH was successful before validating messages. Although not strictly required, it will better allow you distinguish between broken key establishment and broken messages.

2. Include the parameters or parameter names in the above validation.

3. For particular protocols (ECDH with a P-xxx or Brainpool prime curve) to check the validity of the public key.

But note that if you'd use pre-established parameters that the attacker may not have an attack vector in the first place. It depends on your protocol.

4a. As you can see in my example, I have failed to involve a CA in my imaginary hybrid cryptosystem.

You've also failed to define a key pair for signing / verification, so that should come at no surprise.

4b. In my understanding, a CA will verify that messages are indeed from a company/person. To verify the messages are from one side, CA will see the digital certificate that is sent alongside the message.

Incorrect. A CA is used to establish trust in the certificates used, which contain the public key used for signature verification (or, in other protocols, encryption). A CA is not involved in the transport protocol at all, except maybe to validate that the certificates are still valid (CRL / OCSP) at the time that the connection is being established.

4c. However, why do I need to involve a CA when I can sign a message myself and ask the receiver to verify the signed message? Why involve a third-party?

The CA is only involved to let the receiver trust the public key of your certificate. If you can use an out-of-band procedure to trust the public key / certificate then you don't need a CA (you could e.g. use self-signed certificates in that case).

---

You're still a terrible long way off of defining your own secure transport protocol. Either you should follow a crypto course and practice a lot, or you should use an existing protocol such as TLS.