Proxy Authentication Technology
3 years ago, I came up with the idea of an account password recovery algorithm. Its main advantage is that it allows you to restore an account in cases where it is impossible to do it in another way, for example, when you forgot your password, answers to secret questions, and lost access to a trusted mailbox, and you can recover it after lost, and after his shift by the attacker.
It is to this topic that I dedicated my dissertation, parts of which I have already published before. Now, I will describe the algorithm itself, its model, and provide estimates of the probabilities of successful authentication of a legal user and intruders.
While working on my thesis, I found in the foreign literature only a couple of prototype systems, which can also be classified as social authentication systems. A few months after the publication of my algorithm, Facebook announced a similar system of "trusted friends."
So, the social authentication algorithm itself can be divided into 4 main stages:
1. Preparatory stage.
2. Launch of the social authentication system (SSA).
3. Receiving guarantors' ratings.
4. Analysis of the assessments of guarantors by the Authorization Center.
')
Three basic object classes are involved in authentication:
• S - a kind of information system, having in its composition an access control subsystem that implements an authentication technology with the help of trusted persons, which we will call the Authorization Center (CA) CA;
• User - a user who has an account in the IS S;
• Voucher - the guarantor , the person capable of confirming the user's identity.
During the authentication process, the guarantors must confirm the identity of the user in the CA.
At the preparatory stage in the Authorization Center (CA), using a special interface, a list of expert guarantors is compiled, which will be able to confirm the identity of the legal user, which includes:
• trusted channels of communication with guarantors, for example, email addresses, phone numbers, accounts in Internet pagers or social networks, etc .;
• the competence of guarantors, in the form of weights, calculated on the basis of answers to several questions, or on the basis of information available to the user;
• Optionally, a user comment can be added, which will be sent to the guarantor when asked for confirmation.
A request is sent to the trusted channel, after confirmation, which is added to the list of guarantors.
This is how the algorithm itself works:
The probability of successful authentication in this case depends on:
p1 - the probability of successfully passing the CAPTCHA;
p2 - the probability to get a list of guarantors;
p3 - the probability to determine the guarantor and contact him;
p4 is the probability to get a rating from the guarantor;
p5 - the probability of obtaining a satisfactory assessment.
Since the probabilities p1, p2, p3, p4 and p5 are independent from each other by their nature, according to the binomial law, the probability for a user to get v - unsatisfactory estimates from w - the total number of estimates is equal to:
,
Where
- number of combinations.
The probability of getting a list of guarantors depends directly on such a parameter as the pre-moderation time and the method of its calculation.
There are two most likely reasons why a user could apply for a new password. Either his account was hacked, or he forgot the old password. What exactly happened, depends on how long ago the password was last changed.
The less time elapsed between changing the password and contacting the Authorization Center (CA), the higher the likelihood of account hacking. The period of time, when hit in which the account will be considered presumably hacked, is called the pre-moderation time . In this case, the list of guarantors is transferred to the appealing user.
If the password during this time has not changed, the user could simply forget it. To make sure of this CA sends a message to the legal user asking to allow or prohibit the password recovery procedure. The more time there is no answer, the higher the probability of losing the password. Therefore, if, after the time of pre-moderation, the answer was never received, then the password recovery procedure begins.
Thus, the pre-moderation time is a period of time during which the legal user will almost certainly take advantage of his account, i.e. period of time for which the user will have time to notice that he forgot his password, his account was hacked, or he received a message from the authorization center (CA). This parameter is used to protect against abuse by intruders and allows a high probability to restore access to the account in case of its hacking.
The most obvious is the calculation of the pre-moderation time using the quantile method. For this purpose, a variational series of time intervals is built between user sessions with the system t1, .., tn. And equal to the pre-moderation time can be considered a given quantile of the required level, for example, 0.95,
. In this case, the probability of obtaining a list of guarantors for a legal user who actively uses his account is 95%, and the probability for an attacker is only 5%. Due to the universality of the quantile method and applicability for any family of distributions, it is not necessary to refine the type of distribution, however, if user appeals follow any distribution, then the pre-moderation time can be calculated more accurately.
The probability of determining the guarantor and contacting him strongly depends on the nature of the initiator of the verification. The obtained list of guarantors contains only definitions written by the user, for example, “brother”, “uncle Yura”, “Boar”, “par0vi4ok” or even “Vasya Pupkin”. For a legal user, identifying each of them and contacting them does not pose any problems, unlike an intruder. Such a task will become an insurmountable obstacle to automated and non-personalized attacks.
The probability of getting an estimate from the guarantor depends on the wishes and time of the user. In general, it may take from several hours to 2 weeks to obtain the required number of assessments.
The probability of obtaining a satisfactory assessment from one guarantor is not as small as we would like and depends on the attacker's model and type of attack.
Finally, we come to the question of how the user’s identity is assessed by the guarantor, what grades are considered satisfactory and how many grades can be considered sufficient?
Guarantors evaluate the user's identity on a 7-point ordinal scale, which is then converted into numbers using the Harrington number-verbal scale.
A score of 5, 6, and 7 points is considered satisfactory.
For grading, the guarantor must indicate the number of the SVP, which the user has informed him and the method for verifying the user's identity.
Since for greater security, the guarantors should consist of different groups, i.e. they do not need to be intimately familiar with each other, they, by definition, have different competencies that must be considered when making a decision.
To do this, each of the guarantors corresponds to the weighting factor of his competence, which depends on their main characteristics, such as: attitude and amount of communication with the user, as well as the method of checking his personality, which are determined based on the answers
many questions 
. Since the answers are given in the ordinal scale, each of them corresponds to a positive normalized coefficient 
, and 
:
- the normalized response rate of the kth guarantor to the nth question.
Raising the assessment received from the expert to the degree of his competence will be its erosion. In order to increase the robustness of the mechanism, the estimates of guarantors calculated in this way will exclude the smallest, and the smallest of the remaining, will be considered a general estimate.
According to one of the studies, the assessment of three guarantors is sufficiently reliable, so the minimum general competence should exceed 2 (
)
We list the main mechanisms of protection and their impact:
- Passing CAPTCHA before creating an SVP protects against automated attacks;
- checking for pre-moderation time allows a legal user to probably recover a password if it is lost and with a very high probability when an account is hacked, and for an attacker to be a serious obstacle to continuing a further attack;
- the list of guarantors that are transmitted to the user who applied has made it significantly more difficult for an attacker to obtain ratings;
- The rating scale allows you to set not only positive, but also negative, thereby giving guarantors the opportunity to resist attacks;
- identification of the appealing user is carried out using the SVP, and the estimates are set by the guarantors directly to Central Asia, and not transmitted through the user, which makes it safe to listen to the channel between the user and the guarantors;
- the mechanism takes into account the competence of the guarantors in its assessments.
Since, in order to increase robustness, it was decided to consider authentication successful even in the case of one unsatisfactory rating, the probability of successful authentication is:
We list the main types of attacks of malefactors applicable for this system, and their features, in ascending order of parameters:
• Automated Attack (AA) - an attack for which you only need to enter the input parameters, in this case, the victim's login. Such attacks are effective in selecting passwords. Having a database of logins of any server and a dictionary with the most common passwords can be brute-force to crack a large number of accounts. It differs in that although using special systems you can learn how to pass CAPTCHA with some probability, but the task of automatically determining a person’s contacts based on partial data is not solved yet, and therefore p2 = 0, which makes the system practically invulnerable to this type of attack.
• Non-personalized semi-automated attack (NPA) - an attack in which the attacker's goal is not a specific, but a lot of victims, and only part of the attacker's actions are automated, for example, sending messages to the guarantors asking for help.
• Non-personalized manual attack (NNA) - an attack in which the attacker's goal is not a specific, but a lot of victims, while the actions of the attacker are practically non-automated.
• Personalized Attack (PA) - an attack in which the target of an attacker is a specific person, and the attacker is highly skilled and more able to collect information about the victim.
• Attack from a close acquaintance (KSA) - an attack in which an intruder is a person closely acquainted with the victim.
• Attack by the guarantor (TSA) - an attack in which the attacker is one of the guarantors. Such an attack is dangerous because he knows the victim well and has the opportunity to rate himself.
• Attack from the guarantors group (ASGP) - an attack in which several guarantors are immediately attackers. And if you consider that the group consists of at least two people, and the minimum number of assessments for which authentication is possible is three, then the main problem for attackers is to get a list of guarantors. Here, by the way, a small paradox is revealed, which is that the most reasonable behavior on the side of a bona fide sponsor in such a situation is not to give a negative evaluation, but to ignore the intruders, because It is quite possible that they lack only the competence of an expert to gain access.
But first, let's estimate the probability of authenticating a legitimate user. Since the probability of obtaining a list of guarantors and the likelihood of receiving a positive assessment will vary slightly depending on the reason for launching the recovery system, we will consider both the situation with the loss of the password and the situation with changing the password by the attacker:
Thus, depending on the competence of the guarantors, and therefore the minimum required number of assessments, the probability of successful authentication in the event of a password loss ranges from 82.8% to 96.7% , and in the case of a password change by an attacker from 71.7% to 90.2% .
Similarly, we estimate the probability of success of various types of attacks:
It is worth noting that these probabilities are valid if the victim is an active user. Then the probability of obtaining a list of guarantors is quite small. However, if the user has left this resource for a long time, then the probability of p2 eventually approaches 100%. In this case, the success of the attacks will be somewhat different:
I will note that the probabilities calculated above are applicable only for evaluating the first attack on a specific user, since with the increase in the number of attacks, the guarantors' professionalism grows. Thus, due to a decrease in the likelihood of obtaining a positive assessment, as well as any general assessment, the probability of an attack’s success decreases.
Considering that it takes at least several hours to identify guarantors and communicate with them, then one successful ABO attack on an active user requires 150 man-years and a server with at least 450 thousand users, or only 5 man-years and 45 thousand inactive account files. records. A successful NNA attack on an active user requires 8 person-years and a server with at least 11 thousand users, or only 10 person-months and a thousand inactive accounts. Moreover, with increasing computing power, the effectiveness of attacks does not increase . As can be seen from these calculations, non-personalized attacks pose virtually no danger.
PA attacks still have a low probability of success, but if desired, their effectiveness can be increased, although the cost of such an attack will still be inadequate.
Although the likelihood of attacks from acquaintances and guarantors are quite high, you should not forget that the number of opportunities to conduct such an attack is strongly limited by the number of acquaintances, and even more so by the number of those who chose the attacker as a guarantor. Thus, even though such attacks have the highest chance of success compared to other types, the risk of such attacks is also very low.
Finally, I note that escalation methods are well integrated into this system. One of the methods for obtaining a list of guarantors is to create multiple password recovery sessions in the hope that one of them will fall into the required interval. To escalate such massive attacks, escalation methods are ideally suited, the essence of which is that each repeated action requires more and more costs. For example, to create a new SVP, if a sufficiently long period of time has not passed after the previous one, you need to take some action that is easy for a legitimate user and costly for an attacker, such as filling a complicated CAPTCHA or providing a new e-mail for communication. But the most ideal in this case would be the requirement to transfer a small amount (about 100 rubles) to a temporary account, a kind of pledge that could be accessed by successfully authenticating. Such a requirement would become an insurmountable obstacle to any massive attack.
The economic efficiency of this system is to reduce the cost of user support, by automating social authentication, which is now carried out in manual mode by those technical staff. support
Application area:
This system is most effective in large information systems such as social networks, online games and in general any information systems having access to trusted communication channels, for example, to the Internet.
Moreover, when integrated into a social network or an online server, pre-tuning can be carried out on the basis of data available in the system. So Vkontakte already present division into family, classmates, friends. In online games as guarantors, you can use members of the clan or guild, which includes or included a user.
I apologize for some confusion, just in one article it is very difficult to describe the contents of more than a hundred pages of the thesis.
Unfortunately, it was not possible to contact those who could implement this system in a social network, such as Vkontakte or game projects like WoT. I hope that on this site there are those who are interested in this idea :)
It is to this topic that I dedicated my dissertation, parts of which I have already published before. Now, I will describe the algorithm itself, its model, and provide estimates of the probabilities of successful authentication of a legal user and intruders.
While working on my thesis, I found in the foreign literature only a couple of prototype systems, which can also be classified as social authentication systems. A few months after the publication of my algorithm, Facebook announced a similar system of "trusted friends."
So, the social authentication algorithm itself can be divided into 4 main stages:
1. Preparatory stage.
2. Launch of the social authentication system (SSA).
3. Receiving guarantors' ratings.
4. Analysis of the assessments of guarantors by the Authorization Center.
')
Three basic object classes are involved in authentication:
• S - a kind of information system, having in its composition an access control subsystem that implements an authentication technology with the help of trusted persons, which we will call the Authorization Center (CA) CA;
• User - a user who has an account in the IS S;
• Voucher - the guarantor , the person capable of confirming the user's identity.
During the authentication process, the guarantors must confirm the identity of the user in the CA.
At the preparatory stage in the Authorization Center (CA), using a special interface, a list of expert guarantors is compiled, which will be able to confirm the identity of the legal user, which includes:
• trusted channels of communication with guarantors, for example, email addresses, phone numbers, accounts in Internet pagers or social networks, etc .;
• the competence of guarantors, in the form of weights, calculated on the basis of answers to several questions, or on the basis of information available to the user;
• Optionally, a user comment can be added, which will be sent to the guarantor when asked for confirmation.
A request is sent to the trusted channel, after confirmation, which is added to the list of guarantors.
This is how the algorithm itself works:
The probability of successful authentication in this case depends on:
p1 - the probability of successfully passing the CAPTCHA;
p2 - the probability to get a list of guarantors;
p3 - the probability to determine the guarantor and contact him;
p4 is the probability to get a rating from the guarantor;
p5 - the probability of obtaining a satisfactory assessment.
Since the probabilities p1, p2, p3, p4 and p5 are independent from each other by their nature, according to the binomial law, the probability for a user to get v - unsatisfactory estimates from w - the total number of estimates is equal to:
,
Where
- number of combinations.
The probability of getting a list of guarantors depends directly on such a parameter as the pre-moderation time and the method of its calculation.
There are two most likely reasons why a user could apply for a new password. Either his account was hacked, or he forgot the old password. What exactly happened, depends on how long ago the password was last changed.
The less time elapsed between changing the password and contacting the Authorization Center (CA), the higher the likelihood of account hacking. The period of time, when hit in which the account will be considered presumably hacked, is called the pre-moderation time . In this case, the list of guarantors is transferred to the appealing user.
If the password during this time has not changed, the user could simply forget it. To make sure of this CA sends a message to the legal user asking to allow or prohibit the password recovery procedure. The more time there is no answer, the higher the probability of losing the password. Therefore, if, after the time of pre-moderation, the answer was never received, then the password recovery procedure begins.
Thus, the pre-moderation time is a period of time during which the legal user will almost certainly take advantage of his account, i.e. period of time for which the user will have time to notice that he forgot his password, his account was hacked, or he received a message from the authorization center (CA). This parameter is used to protect against abuse by intruders and allows a high probability to restore access to the account in case of its hacking.
The most obvious is the calculation of the pre-moderation time using the quantile method. For this purpose, a variational series of time intervals is built between user sessions with the system t1, .., tn. And equal to the pre-moderation time can be considered a given quantile of the required level, for example, 0.95,
. In this case, the probability of obtaining a list of guarantors for a legal user who actively uses his account is 95%, and the probability for an attacker is only 5%. Due to the universality of the quantile method and applicability for any family of distributions, it is not necessary to refine the type of distribution, however, if user appeals follow any distribution, then the pre-moderation time can be calculated more accurately.
The probability of determining the guarantor and contacting him strongly depends on the nature of the initiator of the verification. The obtained list of guarantors contains only definitions written by the user, for example, “brother”, “uncle Yura”, “Boar”, “par0vi4ok” or even “Vasya Pupkin”. For a legal user, identifying each of them and contacting them does not pose any problems, unlike an intruder. Such a task will become an insurmountable obstacle to automated and non-personalized attacks.
The probability of getting an estimate from the guarantor depends on the wishes and time of the user. In general, it may take from several hours to 2 weeks to obtain the required number of assessments.
The probability of obtaining a satisfactory assessment from one guarantor is not as small as we would like and depends on the attacker's model and type of attack.
Finally, we come to the question of how the user’s identity is assessed by the guarantor, what grades are considered satisfactory and how many grades can be considered sufficient?
Guarantors evaluate the user's identity on a 7-point ordinal scale, which is then converted into numbers using the Harrington number-verbal scale.
A score of 5, 6, and 7 points is considered satisfactory.
For grading, the guarantor must indicate the number of the SVP, which the user has informed him and the method for verifying the user's identity.
Since for greater security, the guarantors should consist of different groups, i.e. they do not need to be intimately familiar with each other, they, by definition, have different competencies that must be considered when making a decision.
To do this, each of the guarantors corresponds to the weighting factor of his competence, which depends on their main characteristics, such as: attitude and amount of communication with the user, as well as the method of checking his personality, which are determined based on the answers
many questions . Since the answers are given in the ordinal scale, each of them corresponds to a positive normalized coefficient , and :
- the normalized response rate of the kth guarantor to the nth question.
Raising the assessment received from the expert to the degree of his competence will be its erosion. In order to increase the robustness of the mechanism, the estimates of guarantors calculated in this way will exclude the smallest, and the smallest of the remaining, will be considered a general estimate.
According to one of the studies, the assessment of three guarantors is sufficiently reliable, so the minimum general competence should exceed 2 (
)
We list the main mechanisms of protection and their impact:
- Passing CAPTCHA before creating an SVP protects against automated attacks;
- checking for pre-moderation time allows a legal user to probably recover a password if it is lost and with a very high probability when an account is hacked, and for an attacker to be a serious obstacle to continuing a further attack;
- the list of guarantors that are transmitted to the user who applied has made it significantly more difficult for an attacker to obtain ratings;
- The rating scale allows you to set not only positive, but also negative, thereby giving guarantors the opportunity to resist attacks;
- identification of the appealing user is carried out using the SVP, and the estimates are set by the guarantors directly to Central Asia, and not transmitted through the user, which makes it safe to listen to the channel between the user and the guarantors;
- the mechanism takes into account the competence of the guarantors in its assessments.
Since, in order to increase robustness, it was decided to consider authentication successful even in the case of one unsatisfactory rating, the probability of successful authentication is:
We list the main types of attacks of malefactors applicable for this system, and their features, in ascending order of parameters:
• Automated Attack (AA) - an attack for which you only need to enter the input parameters, in this case, the victim's login. Such attacks are effective in selecting passwords. Having a database of logins of any server and a dictionary with the most common passwords can be brute-force to crack a large number of accounts. It differs in that although using special systems you can learn how to pass CAPTCHA with some probability, but the task of automatically determining a person’s contacts based on partial data is not solved yet, and therefore p2 = 0, which makes the system practically invulnerable to this type of attack.
• Non-personalized semi-automated attack (NPA) - an attack in which the attacker's goal is not a specific, but a lot of victims, and only part of the attacker's actions are automated, for example, sending messages to the guarantors asking for help.
• Non-personalized manual attack (NNA) - an attack in which the attacker's goal is not a specific, but a lot of victims, while the actions of the attacker are practically non-automated.
• Personalized Attack (PA) - an attack in which the target of an attacker is a specific person, and the attacker is highly skilled and more able to collect information about the victim.
• Attack from a close acquaintance (KSA) - an attack in which an intruder is a person closely acquainted with the victim.
• Attack by the guarantor (TSA) - an attack in which the attacker is one of the guarantors. Such an attack is dangerous because he knows the victim well and has the opportunity to rate himself.
• Attack from the guarantors group (ASGP) - an attack in which several guarantors are immediately attackers. And if you consider that the group consists of at least two people, and the minimum number of assessments for which authentication is possible is three, then the main problem for attackers is to get a list of guarantors. Here, by the way, a small paradox is revealed, which is that the most reasonable behavior on the side of a bona fide sponsor in such a situation is not to give a negative evaluation, but to ignore the intruders, because It is quite possible that they lack only the competence of an expert to gain access.
But first, let's estimate the probability of authenticating a legitimate user. Since the probability of obtaining a list of guarantors and the likelihood of receiving a positive assessment will vary slightly depending on the reason for launching the recovery system, we will consider both the situation with the loss of the password and the situation with changing the password by the attacker:
Thus, depending on the competence of the guarantors, and therefore the minimum required number of assessments, the probability of successful authentication in the event of a password loss ranges from 82.8% to 96.7% , and in the case of a password change by an attacker from 71.7% to 90.2% .
Similarly, we estimate the probability of success of various types of attacks:
It is worth noting that these probabilities are valid if the victim is an active user. Then the probability of obtaining a list of guarantors is quite small. However, if the user has left this resource for a long time, then the probability of p2 eventually approaches 100%. In this case, the success of the attacks will be somewhat different:
I will note that the probabilities calculated above are applicable only for evaluating the first attack on a specific user, since with the increase in the number of attacks, the guarantors' professionalism grows. Thus, due to a decrease in the likelihood of obtaining a positive assessment, as well as any general assessment, the probability of an attack’s success decreases.
Considering that it takes at least several hours to identify guarantors and communicate with them, then one successful ABO attack on an active user requires 150 man-years and a server with at least 450 thousand users, or only 5 man-years and 45 thousand inactive account files. records. A successful NNA attack on an active user requires 8 person-years and a server with at least 11 thousand users, or only 10 person-months and a thousand inactive accounts. Moreover, with increasing computing power, the effectiveness of attacks does not increase . As can be seen from these calculations, non-personalized attacks pose virtually no danger.
PA attacks still have a low probability of success, but if desired, their effectiveness can be increased, although the cost of such an attack will still be inadequate.
Although the likelihood of attacks from acquaintances and guarantors are quite high, you should not forget that the number of opportunities to conduct such an attack is strongly limited by the number of acquaintances, and even more so by the number of those who chose the attacker as a guarantor. Thus, even though such attacks have the highest chance of success compared to other types, the risk of such attacks is also very low.
Finally, I note that escalation methods are well integrated into this system. One of the methods for obtaining a list of guarantors is to create multiple password recovery sessions in the hope that one of them will fall into the required interval. To escalate such massive attacks, escalation methods are ideally suited, the essence of which is that each repeated action requires more and more costs. For example, to create a new SVP, if a sufficiently long period of time has not passed after the previous one, you need to take some action that is easy for a legitimate user and costly for an attacker, such as filling a complicated CAPTCHA or providing a new e-mail for communication. But the most ideal in this case would be the requirement to transfer a small amount (about 100 rubles) to a temporary account, a kind of pledge that could be accessed by successfully authenticating. Such a requirement would become an insurmountable obstacle to any massive attack.
The economic efficiency of this system is to reduce the cost of user support, by automating social authentication, which is now carried out in manual mode by those technical staff. support
Application area:
This system is most effective in large information systems such as social networks, online games and in general any information systems having access to trusted communication channels, for example, to the Internet.
Moreover, when integrated into a social network or an online server, pre-tuning can be carried out on the basis of data available in the system. So Vkontakte already present division into family, classmates, friends. In online games as guarantors, you can use members of the clan or guild, which includes or included a user.
I apologize for some confusion, just in one article it is very difficult to describe the contents of more than a hundred pages of the thesis.
Unfortunately, it was not possible to contact those who could implement this system in a social network, such as Vkontakte or game projects like WoT. I hope that on this site there are those who are interested in this idea :)
Source: https://habr.com/ru/post/183292/
All Articles