In this paper, we tackle the issue of security of multi-agent systems of embedded agents. These systems provide scalable and flexible ways to control complex, distributed and interconnected systems of embedded components, which can connect to and disconnect from the system during runtime. The lack of central authority makes such systems more dynamic and adaptive. However, securing these systems is challenging and raises many issues. In this work, we aim at providing a public key infrastructure to enable agents to securely connect to the system while it runs and without the need to load certificates beforehand. To do so, we establish an infrastructure where agents generate their own keys and ask for certificate from certificate authorities. Those authorities act without the need to coordinate themselves and distribute certificates to requesters, following the rules of a trust management system. The infrastructure provides the ability for the agents to obtain certificates and establish secure communications between themselves without the need of an external, centralized system.
Multi-agent system (MAS) is a paradigm for decentralized computing, which can be France (P. Elbaz-Vincent) 4.0 International (CC BY 4.0).
CEUR can be seen as communities of agents autonomously cooperating to achieve their own goals and eventually achieve the global goal of the entire system. However, most of those MEAS rely on wireless ad hoc networks, which increases the likelihood of a wide range of attacks.
The traditional way of securing communications in an open system, including the Internet, requires the use of a Public Key Infrastructure (PKI). But, traditional PKIs are based on a central hierarchy of trusted third parties, which conflicts with the design of a decentralized MAS. This is why we propose Multi-Agent Key Infrastructure (MAKI), a minimalist PKI where trust is established without the need of third-parties, and which relies on the two most important features of MAS, the cooperation between agents and their autonomy.
The rest of the paper is organized as follows: the background and related works are presented in the next section; while Section 3 describes the infrastructure itself. We discuss security considerations and limitations in Section 4. An initial implementation in a MEAS simulator and obtained results are given in Section 5. Finally, we conclude the paper in Section 6.
MEAS are particularly vulnerable as they are afected by physical threats on their
hardware and by software and network threats on their code and communication, but
also threats targeting their collaboration algorithms and cognitive behavior. Meta-studies
showed that many works focus on securing such systems using various tools such as trust
management systems, intrusion detection systems, security norms enforcing or plain
cryptography [
However, cryptographic constraints are not always considered in works deploying trust
management systems (TMS) [
Therefore, our work focuses on designing an infrastructure allowing cryptographic computation without the need for the agents to fetch and carry certificates or any cryptographic data before connecting to the MEAS.
To this end, Blockchain Technology (BCT) is a widely used solution [
BCT are not the first attempt at trying to decentralize PKI. The authors of [
Another approach to solve this problem could be to remove the need for certificates.
This can be done using identity- or attribute-based encryption [
Thus, we develop a specific infrastructure, designed for MEAS and leveraging the autonomy and cooperative behavior of the agents that do not require neither pre-loaded certificates nor of-band verification and no high volume of memory or computational power.
The objective of our work is to develop an infrastructure allowing all the agents to send messages and interact with the assurance of the authenticity and the integrity of their exchanges, including the messages exchanged when applying a trust management system.
To do so, we consider the following hypotheses: (H1) Authentication of an agent is not required when connecting to the system. This means that the names of the agents are only a way to diferentiate them. The cooperation between agents will be based on the capabilities announced by each agent. (H2) Agents are capable to sign the messages they send using asymmetric keys. (H3) Private keys can not be compromised, agents never emit their key and their hardware is either hardened enough or inaccessible enough to prevent physical attacks.
In this work, we focus on communication-related attacks with mote-class attackers, i.e., attackers with similar resources as the agents of the system. As MEAS often rely on ad hoc, wireless networks, we assume that attackers are able to eavesdrop on the communication media and manipulate it by tampering with messages.
The core concept of MAKI is to autonomously distribute the role of CA to the agents. CAs are responsible for generating, signing, and revoking certificates used by the other members of the PKI. By doing so, MAKI does not require external third-parties and does not rely on a single agent. Its most fundamental rule is that every agent should hold a valid certificate to be authorized to take part in the system. The role of CA is thus fundamental and it must be considered with care when defining algorithms for assigning this role to agents. To allow as most flexibility and resilience as possible, we intend to allow every agent to decide for itself whether or not it should endorse the role of CA leveraging an existing TMS, or a new TMS if there is none, to guide its decision to trust or not a CA, or to become one if none are available. We consider the autonomy of the agents and decentralized feature of MAS which prevents the risk of single point of failure and increases the scalability of the system.
MAKI is threefold. The use of cryptographic primitives allows agents to sign their messages. That alone is enough to satisfy the need of integrity and authenticity when agents are exchanging messages, especially when using the TMS. Moreover, MAKI also provides a way to enforce the decision taken by the TMS by adding the requirement of holding a valid certificate and thus most likely globally excluding an agent by revoking its certificate. However, the use of certificates requires an authority to deliver them, authority that should not impede the autonomy of the MEAS. Lastly, MAKI provides a way to decide which agents should be authority and a way to filter out malicious authorities by leveraging and extending the TMS in use.
Only knowing the name, an identifier such as a number or a string, of an agent, is not
enough to establish a communication with it as it can very easily be spoofed. To prevent
identity spoofing or stealing, we use a name and a public key, or only a public key, to
define the identity of an agent. This prevents any attempt of identity spoofing but not
Sybil attacks [
CA is a role, a behavior, one agent can decide to endorse if it considers it necessary. Once an agent becomes CA, it is allowed to self-sign its certificate and will inherit responsibilities. Those responsibilities are (i) delivering, and updating, certificates to other agents, (ii) maintaining the list of certificates it delivered and (iii) maintaining the list of certificates it revoked.
Since CAs are self-signed, it is impossible to revoke their certificates. However, they can still be ignored if they do not behave properly. For example, a CA that, after a given amount of time, has not delivered certificates when new agents are joining the system will be judged suspicious since it does not behave as a CA as it should. Then, its legitimacy may decrease. And, even though its certificate can only be revoked by itself, if it is not legitimate, it will be considered as revoked and thus agents will not interact Algorithm 1 How an agent chooses its role
T ∈ [0, 1) 1: CAs ← SendToInRange(CAPresenceRequest) 2: TrustedCAs ← FilterByTrust(CAs, TrustLevel.Moderate) 3: if can become CA and (TrustedCAs is empty or Random(0, 1) > T) then listed above. By doing so, we decrease the risk of malicious agents simply taking on the role of CA to prevent any exclusion attempt and ensure that the privilege of being a CA always come with the responsibility to serve other agents.
Moreover, we consider adding cross-certification for CAs that would want to share their trust and distrust with another CA. By simply doing so, they earn more legitimacy since they now are liable to be revoked by another CA.
The number of CAs needed for a system to be eficient dependents on run-time parameters such as the number, the position of the benevolent agents and malicious ones but also on the capabilities of the agents. For example, to maintain low latency when delivering certificates, it can be suitable to have each agent in range of a CA. This means that the proportion of CAs to the total number can be expressed as a variation of: =
× + with the proportion of benevolent CAs the average range of agents the density of benevolent agents the total number of CAs a positive ofset, proportional to N to prevent single-point-of-failure situations
However, if and varies at run-time, will too. This is why we let the agents choose for themselves if they deem necessary to become a CA. A simple algorithm describing a way to make this choice is given in Algorithm 1. The is implemented as a probability of one agent becoming CA even though there already is one in its range.
Even if this is for an example with an objective of having at least one CA in range of all agents, we could simply tailor the algorithm by changing the definition of “in range” (SentToInRange) by the maximum of agents necessary to route a message from its source to a CA.
The certificate and Certificate Revocation List (CRL) formats were adapted to fit the
MAKI needs. The certificate format is much simpler than an X.509 one [
Certificates propagation relies on a combination of gratuitous broadcast and adding them to the exchanged messages, depending on the network throughput and the acceptable overhead on the messages.
Certificates are revoked through two mechanisms. The first one is the CRL; when necessary, a CA will update its CRL and broadcast it. This will allow an immediate revocation but, as the communications are ad hoc, it does not assure that the revocation will reach immediately each agent. To complete the usage of CRL, we also consider using short-lived certificates. By doing so, revocation orders only need to reach the CAs to ensure that the targeted agent will eventually be revoked since its certificate will expire and the CAs will not renew it.
MAKI is originally intended to be deployed in coordination with a TMS. We provide in
this section the rules and criteria used to extend the TMS to include MAKI prerogatives.
If there is no TMS, we also provide some essential explanation on TMS as well as
guidelines to deploy a minimalistic TMS satifying the requirements of MAKI. As stated
in [
Trust and reputation are very common mechanisms to increase resilience in MAS [
TMS are commonly split in three parts: trust management, trust modelling and decision making. The first part describes how the information is gathered, the second describes how the trust is represented and information aggregated and the last one describes how the decisions are made depending on the trust values.
In our case, trust gathering includes direct information, i.e., the information from experiencing the interaction with the agent and indirect information, i.e., the information collected by asking other agents. Since the communications are wireless and not encrypted, for the exchanges to establish MAKI at least, we consider using eavesdropping on communications to corroborate the declarations of an agent. For example, if a CA refutes Requesting an agent certificate or sharing its certificate having delivered a certificate to a malicious agent, an accuser could provide the signed exchange between the CA and the malicious agent in which the delivery is done. However, eavesdropping requires the agents to stay in promiscuous mode which is very energy consuming. Depending on the role taken by an agent, we can establish criteria for the TMS. These are indicators of the implication of the agent in MAKI, to prevent selfish behaviors or indicators of the concordance of the behavior with the other agents. For the CA role, the criteria are as follows: • A high number of delivered certificates means that it is implicated in MAKI at the cost of its own computation and its energy and that a large number of agents trust it to deliver their certificates.
• A cross-certified CA share the trust with its cross-certifier and it shows that it is ready to take the risk of being cross-certified with a malicious CA to be more trustworthy and useful. • Refusing to deliver any certificate, hence only being a CA to be able to self-sign its certificate is a red flag. It means that, at best, the agent is selfish but most-likely, it wants to make it harder to be excluded. • Revoking a certificate with no good reason or proof is also a red flag. CAs should not be allowed to act unilaterally.
Overall, any agent caught lying, or undertaking an attack such as a Sybil attack should lose the trust of the system and have its certificate revoked. For all other intents, the certificates delivered by an agent , a CA, will have a value for an agent ℬ that is related to the mutual trust between and ℬ. The trust ℬ will have in is related to the trust ℬ has in the agents holding a certificate delivered by .
We established guidelines for the decision making part. They are presented in Table 1. They are based on the trade-of between the risk and the benefit of undertaking an interaction with other agents depending on their needs and their roles. We defined three level of trust, Low, Moderate and High that the target agent should satisfy in order to allow an interaction. Although, a CA has no information about newcomers when they ifrst ask for a certificate so we choose not to hold them responsible if an agent using a certificate it delivered is excluded. This also removes the incentive of refusing to revoke the certificate since that would correspond to admitting a fault. This can be moderate in the case of a CA blindly delivering certificate to agents that were revoked when it seems obvious that the CA could have known about the revocation.
Lastly, we do not assume to be able to choose one model to fit all requirements for
all kinds of MEAS as there are many trust models in the literature ranging from linear
sums [
One dificulty about TMS is to decide whether or not to trust newcomers, especially in systems where an agent could easily change its identity when it is identified as malevolent or even plain excluded. One way to mitigate this behavior named “whitewashing” is to trust newcomers very little. This way, a whitewasher would have to behave properly in order to earn the trust of the other agents before trying to exploit them.
Starting the systems with unknown and possibly malicious agents, could lead to malicious agents obtaining disproportionate weight in the system, which would be disastrous. With the hypothesis that the first benevolent agents of MAKI are deployed by the same entity, for example, operators deploy the first agents and open the system to external agents later on, we propose two ways of bootstrapping MAKI. The first way would be to hard-code some initial trust values for certain agents. It could be acceptable since the operators are in control of the initial conditions so that they know that all agents are benevolent. The second way would be to run MAKI in a controlled environment long enough so that some agents obtain suficiently high trust to steer the whole system in the right direction. Both ways can also be complementary, we could hard-code some values and let the system organize around them. The main point to consider is the time taken by the system to stabilize which also depends on the population and the density of agents and should be studied on a case-by-case basis.
Adding a new agent is quite simple from an insider point of view, one CA should deliver to it a certificate and it would only be trusted with lower importance tasks until it earns trust from the agents it interacts with.
From the new agents point of view, connecting to MAKI is straightforward. It has to ifnd out the identity of one CA and request a certificate. To do so, it can either eavesdrop on the communications or broadcast a request. Once it has a certificate, it can probe the state of the system and decide whether or not it made the right choice or if it should change its CA or become a CA. Figure 1 illustrate such an example.
By signing every interaction, we ensure that the source of each interaction can be identified and held accountable to fuel the TMS, leading to the detection and possible exclusion of untrustworthy agents. Signing also allows the detection of any attempt in tampering with a message during its transmission. However, detection and exclusion do not apply to an agent but to an identity, i.e., a pair of name and public key. Nevertheless, we can reduce the impacts of agents continually generating new identities using detection at network level as described in Section 3.3 and by not trusting newcomers right away.
In terms of the intrusion detection, MAKI relies on a TMS and, thus, is at least as eficient as the TMS. Moreover, MAKI does not create new ways for malicious agents to circumvent the TMS as, even though they can not be revoked, CAs can still be excluded by being ignored and given a very bad trust review when asked. The simple model we proposed is vulnerable to some attacks such as on-of attacks, selective-lying attacks and such, but it is only given a simple placeholder until a more rigorous model is implemented.
The number of CAs also impacts the security MAKI provides, too few CAs implies a high risk of having to rely on a malicious CA; too many makes the choice harder as, most likely, none of the CAs will be able to meet the minimal number of distributed certificates.
The ratio of malicious to benevolent agents is only interesting to look at the scale the agents can collaborate. At this scale, the ratio can not exceed fifty percent since it would mean that the malicious agents can collude to exclude any agent arbitrarily. Under this limit, as it is the responsibility of the TMS to detect the malicious agents, the ratio can be as high as the TMS allows it.
MAKI adds a necessary overhead in terms of the number and the size of exchanged messages, storage, computation and time. First, messages need to be exchanged to request and deliver certificates and to find trustworthy CAs. At least one request and one reply are necessary to get a signed certificate. The size of messages also increases since they now include a signature and possibly a certificate. Second, it is necessary for CAs to store the certificates they have delivered as well as a CRL. NotCA agents only have to store their current certificate and are advised to store the certificates of the agents they interact with the most. Third, the computation requirements are increased due to the use of cryptographic primitives (see Section 5 for the details on an example of such primitives). Last, due to the above mentioned overhead, the time before an agent can start collaborate after joining the system is increased since it first has to get a certificate.
The code of the proof-of-concept and the totality of the execution traces and results are
freely available at [
As stated, MAKI is agnostic of cryptographic choices and most of the trust models. Cryptographic choices and TMS should be tailored to the real application of the MEAS and capabilities of the agents.
For our experiment, we followed the NIST recommendations [
For trust modelling, we defined the trust as a value starting at 0 and increasing infinitely. We set the increments to small values such as 1 or 2 and defined the function of the trust growth rate to: ∶ ↦ + with , the Low trust level.
We fixed the trust level according to trust growth rate, Low is 1 so that 0 trust means being untrustworthy, Moderate is set to 30 and High to 90. This prevents free whitewashing attacks without being too harsh and preventing agents to earn their place in the system. We used without-compromise approach for the trust loss, as of now, every malicious behavior is punished by a total loss of trust, efectively setting the trust in the misbehaving agent to 0 independently from its previous trust. This particular model was designed for demonstration purpose and may no fit all the modelling needs of real-world MEAS. More advanced and tailored models are available depending on the deployed MEAS. As of now, the trust model is only fed with four kinds of information: • “Agent collaborated successfully.” This is used for bootstrapping and is discuss in the next section. • “CA delivered a new certificate.” This increases the trust in which is used to weight the trust of the certificate holder. Thus, a CA has a real incentive to deliver certificate since it earns more trust each time. • “The certificate of agent is revoked.” The trust in is nullified. • “The agent is malicious.” The trust in is nullified and a certificate revocation request will be sent to the CA that delivered the certificate is using.
This proof-of-concept was implemented using an in-house multi-embedded-agents
simulator built on top of the Mesa agent modeling framework [
We designed five scenarios that are derivations of the six following steps: 1. agents detect malicious behavior from an agent ℰ. 2. The trust in ℰ of these agents drops to 0. 3. If ℰ certificate is not self-signed, the agents request to the issuer a revocation of ℰ certificate. 4. If the certifier agrees to it, it revokes the certificate and advertises it. 5. All the agents learning about the revocation will lose their trust in ℰ if not already done. 6. ℰ will not receive any new certificate.
In the first scenario, is the totality of the agents (except ℰ). In this case, everything happens as described above with the step 5 skipped since all the agents already lost their trust in ℰ. The result is presented in Figure 3a.
In the second scenario, is 60% of the agents, including or not the certifier. In this case, if more than half of the agents the certifier trust are in the 60%, which is the case in the configuration we chose, everything happens exactly as described above. The result is presented in Figure 3b.
In the third scenario, is only 40% of the agents, including or not the certifier. In this case, it is less likely that the 40% of the agents are more than half of the agents trusted by the certifier. It is not the case in the configuration we chose, and steps 4 to 6 do not happen. The rest of the agents continue to trust ℰ. The result is presented in Figure 3c.
For the last two scenarios, ℰ is a CA and its certificate is self-signed and thus can not be revoked. In the first scenario, is all the agents making their trust in ℰ drops to 0, and agents certified by ℰ will change their CA. However, some agents may not have time to change CA and will be revoked and excluded. Future implementations will account for this particular timing problem by waiting a little before requesting the revocation of certificates delivered by a malicious CA. As in the first two scenarios, every agent will ignore ℰ and new agents may reach the same conclusion after checking the number of certificates signed by ℰ in use. It is less direct than being able to revoke ℰ but using the number of delivered certificates rule and indirect information will eventually lead to the same result. The result is presented in Figures 3d. 80 60 t s rTu40 20 0 t 60 rs u T 40 20 0
Agent0 (NotCA) loses the trust of all the agents and is revoked
Trust of 1 in 0 Trust of 2 in 0 Trust of 3 in 0 Trust of 4 in 0 Trust of 5 in 0 Trust of 6 in 0 Trust of 7 in 0 Trust of 8 in 0 Trust of 9 in 0 Agent0 (NotCA) loses the trust of 60 % of the agents and is revoked
Trust of 1 in 0 Trust of 2 in 0 Trust of 3 in 0 Trust of 4 in 0 Trust of 5 in 0 Trust of 6 in 0 Trust of 7 in 0 Trust of 8 in 0
Trust of 9 in 0 80 60 t s rTu40 20 0 t s rTu40 20 0
In the last scenario, is only 40% of the agents, including agents certified by ℰ and others that are not. Only the agents that detected the malicious behavior will lose their trust in ℰ but, since the trust in an agent is weighted by the trust in its certifier they will also lose their trust in the agents certified by ℰ. Some of those agents will change certificates since they are part of the 40% and some will not since they have no reason to do so. The result is presented in Figures 4a and 4b. We can see in Figure 4b that the agent 8 is temporarily distrusted by the rest of the system. At first, it lose the trust of the agents not trusting agent 1 since since the its certificate was signed by agent 1, this 100 80 ts 60 u r T 40 20 0 includes the agent 4. Then, it loses the trust of the whole system as it certificate expires. Its certificate expires because it choose the agent 4 as a CA which was not replying. Eventually, agent 8 asks another CA while holding its expired certificate and regains the trust of the whole system.
Lastly, there is one pattern appearing in Figures 3 and 4 that surprised us. We can see the trust occasionally dropping, but not to 0, or increasing a lot at once while we did not implement any rules in our TMS leading to this behavior. This is due to a change of CA, the agent may choose a new CA based on its view of the system but chooses a CA that is less trusted by the other agents. On the other hand, an agent can choose a more trusted CA and increases its trustability quite quickly.
This paper presented a new public key infrastructure, coined MAKI, aiming at enabling public key encryption in open multi-agent systems of embedded agents with no third-party nor central server. We discussed several security concerns depending on the threat model and hypotheses on the use case of the multi-agent system. As with any cryptographic system, MAKI comes with additional cost in computing, energy, and storage but we tried to limit its cost while not impinging on the autonomy of the agents. A proof-of-concept was developed using the Mesa framework and used five scenarios to demonstrate how MAKI handles malicious behavior and certificate distribution. We are currently working on finalizing the proof-of-concept by adding indirect information to the TMS, describing more malicious behavior, coalition of malicious agents for example, and computing the energy cost of MAKI. Furthermore, we intend to provide formal security proof using a security protocol verification tool.
This work is supported by the French National Research Agency in the framework of the “Investissements d’avenir” program (ANR-15-IDEX-02).