Multi-factor authentication, a mechanism where the user provides two or more loosely coupled evidences of their identity, has become ubiquitous in access management of computer systems. Compared to a single factor authentication, no single piece of information about the user is sufficient for authentication, and account take-over requires obtaining multiple kinds of information about the user.

However, known multi-factor authentication schemes rely on a single user’s knowledge, possession, and inherence. Consequently, while breaking multi-factor authentication is harder than breaking single-factor, password or key based, authentication, it still requires access to a single entity only.

For example, if an additional authentication requires entering a code sent via an SMS to the user’s phone, stealing or observing the user’s phone allows unauthorized access. Similarly, the answer to a ’secret question’, such as mother’s maiden name, can be obtained by getting access to the user’s personal file. With traditional multi-factor authentication, gaining unauthorized access to a computer system still depends on attacking and obtaining information about a single user.

A much harder to break would be an authentication scheme in which multiple people were involved in authentication, and in such a way that identity of people involved in authentication of a user’s access or action is not known in advance. In addition, human beings are notoriously good at identifying their acquaintances — in person or by phone, so that it is deemed beneficial to use person-to-person authentication in addition to person-to-computer authentication in a multi-factor authentication scheme with higher security.

Here, we propose to use a network of social connections of the user to establish a stronger multi-factor authentication scheme by requiring another person chosen among the user’s social connections, or pals to confirm the identity of the user and/or the genuineness of the user’s intent to perform the transaction.

In the following sections, we first describe the pal-based authentication scheme. Then, we analyse and discuss the added security it provides, as well as implementation issues.

Algorithm Outline

Let us consider a user undergoing access authorization to perform a certain transaction, such as payment, adding or updating financial details, money transfer, or access to sensitive information such as the user’s medical record.

When the user logs into the system, in addition to entering the password the user is presented with a random choice of a small subset (for example, 2 or 3 people) out of the list of their friends/relatives (whom they registered with the system) so that one of them also authorizes the transaction. Then, the following happens:

• The user chooses one person (the authentication pal) from the presented random subset.
• The user contacts the other person asking to authorize the transaction or log-in, by phone, email, or in person.
• The system sends the person the authentication link.

From this point on, authentication passes if the other person decides to confirm that the user and the user’s intent to perform transaction are genuine and confirms the original user’s identity. The original user does not have to disclose details of the transaction to their authentication pal, just to convince the pal that they are who they pretend to be.

This is a powerful second factor because it involves ’social authentication’ — the other person must become convinced that the user asking to authenticate is indeed their friend/relative and not an impostor. This can be used selectively when a stronger authentication is required, for example when essential information is changed or disclosed, or when a high-volume transaction is performed.

Example

Consider the following example:

• A logs into the system by sending their user id and password.
• The system maintains a list of A’s pals (registered by A and confirmed by each member of the list, just like friendship in Facebook or connections in LinkedIn): K, L, M, N, O, P.
• Out of the above list, the system chooses randomly two users: L and N and presents them to A.
• A chooses N for pal-based authentication.
• The system sends the authentication link to N by email (or by other electronic communication means), along with an explanation that N should only authorize the authentication attempt if they are sure that A is genuine and not an impostor.
• N and A contact each other. Either side may initiate the interaction.
• After talking to A, N becomes convinced that A’s identity is genuine, and follows the authentication link.
• N authenticates themself to the system (using any authentication scheme, such as single-factor, traditional multi-factor, or pal-based multi-factor authentication depending on risk level and environment) authorizes A’s identity.
• A gains access to the system.

Special cases

A problem arises with repeated failing attempts to authenticate using pal-based authentication.

• If the system presents a different random choice each time, the attacker must only gain access to the email and credentials of a single member of the pals’ list.

• On the other hand, if the system re-uses the same choice every time, then the attacker will know which other identity to steal in order to overcome pal-based authentication.

Because of this, if pal-based authentication fails because the other party actively refuses to authenticate the use, the user’s access should be restricted until the user’s identity is verified using different means. This is not a major issue however if pal-based identification is used selectively, in cases of high risk or high potential loss.

Related to this are different types of rejection during pal-based authentication. The following scenarios are possible:

• The user refuses to use pal-based authentication.

• The user agrees to use pal-based authentication, however the other party chosen by the user is unreachable or does not take an action (neither confirms nor rejects the user’s identity) — which is indistinguishable from the point of view of the system.

• As discussed above, the other party rejects the authentication attempt.

In each of the cases, a fallback authentication and re-validation mechanism must be provided.

The three a priori intuitions are related — infinite and undirected space, infinite and directed time, finite and undirected probability. Physics knows of uncertainty principle, we are uncertain about relation of time and space: both time and space cannot be intuited with certainty. Probability is as basic and fundamental as time and space for our cognition.

Just like geometry deals with a priori intuition of space, and mathematical analysis — with intuition of time, theory of probability deals with intuition of probability. There is philosophical justification for studying uncertainty, probability, and bayesian inference.

We introduce an approximate search algorithm for fast maximum a posteriori probability estimation in probabilistic programs, which we call Bayesian ascent Monte Carlo (BaMC). Probabilistic programs represent probabilistic models with varying number of mutually dependent finite, countable, and continuous random variables. BaMC is an anytime MAP search algorithm applicable to any combination of random variables and dependencies. We compare BaMC to other MAP estimation algorithms and show that BaMC is faster and more robust on a range of probabilistic models.

Abstract

We introduce a new approach to solving path-finding problems under uncertainty by representing them as probabilistic models and applying domain-independent inference algorithms to the models. This approach separates problem representation from the inference algorithm and provides a framework for efficient learning of path-finding policies. We evaluate the new approach on the Canadian Traveller Problem, which we formulate as a probabilistic model, and show how probabilistic inference allows efficient stochastic policies to be obtained for this problem.

Read more…

Abstract

We introduce an adaptive output-sensitive Metropolis-Hastings algorithm for probabilistic models expressed as programs, Adaptive Lightweight Metropolis-Hastings (AdLMH). The algorithm extends Lightweight Metropolis-Hastings (LMH) by adjusting the probabilities of proposing random variables for modification to improve convergence of the program output. We show that AdLMH converges to the correct equilibrium distribution and compare convergence of AdLMH to that of LMH on several test problems to highlight different aspects of the adaptation scheme. We observe consistent improvement in convergence on the test problems.

Full paper.

We suggest a justification for the use of a fixed threshold on the number of conflicts based on the analysis of a model problem. Following the suggested justification, we introduce a new algorithm, which differs in the ways when and how meta-agents are created and handled during search. The new algorithm exhibits considerably better performance compared to the original algorithm. The new algorithm is evaluated on several sets of problems, chosen to highlight different aspects of the algorithm.

Full PDF

This is a short version of Justifying and Improving MA-CBS.