Sql-server – Service Broker Connection handshake failed. There is no compatible encryption algorithm

I wanted to add that the database is a restore from a SQL Server 2005

When you restore a database the Service Broker in it gets disabled and must be explicitly enabled (there are reasons why this is necessary, but I won't go into them). If you restored the DB and then set up the AG w/o enabling broker first, you have set up the AG w/o the Service Broker enabled and now you cannot run the ALTER DATABASE SET ENABLE_BROKER. Unfortunately to set it up correctly you must enable broker before adding it to the AG, which means you must tear apart the AG, enable broker, then set set up the AG again.

It appears you're using Dialog Level Security. This means you have deployed remote service bindings, users and certificates, successfully exchanged certificates and and granted SEND permission on the target service. For example, if you have a DB1 and a DB2, and a service S1 in DB1 and a service S2 in DB2, then, to begin a secure dialog from S1 to S2, you must have also:

• create a certificate C1 in DB1 owned by user that owns S1, lets say U1 (usually dbo)
• create a certificate C2 in DB2 owned by the user that owns S2, say U2 (again usually dbo, but this time dbo of DB2)
• export public key of C1 and C2
• create in DB1 an user, say U2' that will represent the S2 identity in DB1
• import C2 public key as a certificate C2' in DB1, owned by U2'
• create, in DB1, a remote service binding object that binds S2 to U2'. This way BEGIN DIALOG will know to use C2 public key to encrypt messages for S2
• create in DB2 an user U1' that represents U1's identity in DB2
• import C1 public key in DB2 as a certificate C1', owned by U1'. Because messages from S1 are signed with C1 private key (owned by U1), they will be identified in DB2 as being sent by U1' (the owner of C1', the corresponding public key).
• grant SEND on service S2 to U1'

Again, if you say that messages between S1 and S2 are flowing fine, then all the above steps are already correctly done (not a small feat!).

If I understand correctly now you want to add a new service, say S3, also located in DB2, if I understand correctly, that needs to also accept messages from S1. I will make a simplifying assumption that S3 is owned by the same user as S2 (since usually the owner is dbo, this assumption is usually true). If so then you already have the necessary users/certificates exchanged, all you need to do tell SSB to use them:

• in DB1 create a new remote service binding, RSB3, for service S3, using the same user U2'. BEGIN DIALOG will use the same certificate C2' to encrypt messages for S3 as for S2, but this is OK since both S3 and S2 are owned by the same user
• in DB2 grant SEND permission on service S3 to user U1'.

This should be it, now S1 can talk with S2 and also with S3.

This certificate exchange and user ownership logic is used to 'map' a user from DB1 to DB2, without relying on Windows domains. This mapping is done via exchanging public key certificates and then following the certificate ownership: In DB1, U1 (ie. the owner of S1) owns a certificate with a private key, C1. The same certificate's public key exists in DB2 and is owned by U1' (a user in DB2). Therefore U1 'maps' to U1'. Whenever ssbdiagnose complains that a user cannot be 'mapped using certificates' it means that this chain is broken somewhere.