The danger of using "training" crypto protocols
This post was inspired not by the post by EugeneSukhov himself , but by the first comment from @AstralMan.
Indeed, often seeing a description or even a ready-made implementation (corresponding to the description) of a high-level cryptographic protocol, some people try to incorporate it right into their own project and announce this to the general public (please do not take this as a stone in the AstralMan garden). But such a decision is not the best! The description of the crypto protocol, as a rule, does not contain the various necessary checks on the side of the participants and clarifications that are of critical importance in actual use. History knows many examples of a protocol based on strong and time-tested encryption, hashing, etc. It turned out to be hacked precisely because of the very logic of construction, and because of such “trifles” as checks and clarifications. The description of the crypto protocol, demonstrating its very idea, will be called educational.
Immediately, I note that the authentication protocol from the article EugeneSukhov is educational. This means that under certain conditions it is quite possible to attack him, as will be demonstrated in the future. However, this does not mean that the protocol is bad, and its author is not a professional. This means only that the author wanted to convey to the readers a high-level concept of the protocol, and lowered the exact, meticulous specification of the protocol, which was transferred to the developers for further "combat" implementation, for reasons of irrelevance.
Take, for example, at least RSA and suppose that we decided to transmit only one byte using this cryptosystem. Using RSA training will naturally end in failure! Having intercepted the ciphertext, the attacker instantly recovers the plaintext (the same byte) using a full enumeration of numbers from zero to 255. The “combat” RSA of such arbitrariness must not allow that to happen with a competent implementation.
')
In the future, we will assume that the attacker (or offender) has access to the full arsenal of assorted nasty actions, such as “listening” to the communication channel, saving all intercepted messages, changing messages, sending previously intercepted messages, etc. We will also assume that the intruder can steal the database from the server. I’ll clarify that all these assumptions do not disagree with the assumptions of the author of the analyzed educational crypto protocol.
We now turn to the kind of protocol that the author presented.
Pay attention to the latest transfer from the client to the server M = hash (RND). It would seem, why hashing? You can simply send the RND and finish it. But not everything is so simple. To begin with, let's consider a weakened version of the authentication protocol, without using hashing on the last transfer, and point out its shortcomings. The protocol scheme will look like this:
The first drawback is that in the weakened version of the protocol the client plays the role of the so-called “Oracle Decryption”. Indeed, the server sends a message to the client (in our case, RND) encrypted in the client's public key. The client decrypts the message with its private key and sends the message in clear text back to the server. Such protocol building strategies are “non-standard”, carry potential vulnerabilities and, in a sense, speak of the author of the protocol amateurishness.
The second drawback is more serious and lies in the fact that the protocol is cracked with some reservations almost instantly. We describe the attack. Suppose the intruder has recognized the number N - the RSA cryptosystem module. Whether he did this by intercepting the data at the registration stage, or has it stolen the database from the server is not important. The main thing is that he knows N. Also suppose that in order to encrypt the message {d || N} on the symmetric key K, the counter mode is chosen (quite real situation). This means that the intruder will be able to easily form the message {d || p} _K by modifying the message {d || N} _K, where p is a prime number chosen by him, and send a message to the client. I would like to lay the truth of this statement on the shoulders of the reader. Further. The attacker chooses the number p in such a way that p-1 has a “good” (in a cryptographic sense) factoring out and also exceeds d (the client's private key). Then, instead of {RND} _e, the intruder sends g - forming groups Z_p ^ *. The unsuspecting client in full compliance with the protocol on the last transfer sends the attacker g ^ d (mod p). Using the Polig-Hellman algorithm, the intruder calculates the client's private key d in polynomial time. After that, the offender will always be able to impersonate a client.
And now we will return to the consideration of the protocol “in the original”, as it was presented by the author (with hashing at the last transfer). I argue that if k is the client's private key length d in bits, then it is realistic to calculate the private key in less than k client attempts to authenticate with the server. I will not give the mathematical calculations proving the statement presented in the article itself, since they are quite voluminous and not intended for a wide circle of readers. However, in order not to be unfounded, I will describe how you can calculate a few lower bits of the d key for a single attempt to authenticate a client on the server. It is obvious that the possibility of such a calculation indicates the vulnerability of the training protocol. Once again, I’ll draw the reader’s attention to the fact that the vulnerability of the training protocol is a “regular” situation that can absolutely say nothing about the persistence of the “combat” protocol. Earlier assumptions that the attacker knows the number N and that the counter mode is used for symmetric encryption are still valid.
Take for our humble example the prime number p = 65537 = 2 ^ 16 + 1. In Z_p ^ *, choose the element g that generates Z_p ^ *. We calculate the values ​​of hash (g), hash (g ^ 2), hash (g ^ 3), ..., hash (g ^ {p-1}) and store them on your computer as a table. Time and memory for this operation will take very little. Intercepting data from the server to the client and, as previously described, replace N with p, RND with g. As a result, we get a hash from the client from an unknown element - hash (g ^ i), find it on our computer in the table and restore i. So we come to the equation
g ^ d = g ^ i mod p
It follows from it that d = i + a (p-1), where a is some unknown number. We obtain that d = i + 2 ^ 16 * a. If we represent the number i as a bit string of length 16, then it will be the last 16 bits of the client's private key.
Note. If this fact is not immediately obvious to someone, then consider the decimal number system. For example, let A = B + 10 ^ 3 * C. Then B is the remainder of dividing the number A by 10 ^ 3 = 1000. And since 1000 is a power of 10 (we work in the decimal number system), then B is the last three digits of A. If A = 12345, then A = 345 + 12 * 1000 and such a decomposition is unique for a non-negative B <= 1000.
Naturally, during the attack, we could calculate a greater number of low bits of the private key. Note that this number directly depends on the available memory on our computer, in which we can store a table of hashes, and on the performance of the PC.
Afterword : In this article I would like to emphasize that those “ready-made” solutions, algorithms and protocols in the field of cryptography, which can be found in the public domain in the literature or the Internet are not at all “ready-made”, they are educational. If you want your project to have really reliable protective mechanisms, take care of the presence in your team of a person with specialized education and experience in the field of information security. This area is extremely extensive, complex and diverse, to understand it with a swoop, I assure you. All success and thank you for your attention!
Indeed, often seeing a description or even a ready-made implementation (corresponding to the description) of a high-level cryptographic protocol, some people try to incorporate it right into their own project and announce this to the general public (please do not take this as a stone in the AstralMan garden). But such a decision is not the best! The description of the crypto protocol, as a rule, does not contain the various necessary checks on the side of the participants and clarifications that are of critical importance in actual use. History knows many examples of a protocol based on strong and time-tested encryption, hashing, etc. It turned out to be hacked precisely because of the very logic of construction, and because of such “trifles” as checks and clarifications. The description of the crypto protocol, demonstrating its very idea, will be called educational.
Immediately, I note that the authentication protocol from the article EugeneSukhov is educational. This means that under certain conditions it is quite possible to attack him, as will be demonstrated in the future. However, this does not mean that the protocol is bad, and its author is not a professional. This means only that the author wanted to convey to the readers a high-level concept of the protocol, and lowered the exact, meticulous specification of the protocol, which was transferred to the developers for further "combat" implementation, for reasons of irrelevance.
Take, for example, at least RSA and suppose that we decided to transmit only one byte using this cryptosystem. Using RSA training will naturally end in failure! Having intercepted the ciphertext, the attacker instantly recovers the plaintext (the same byte) using a full enumeration of numbers from zero to 255. The “combat” RSA of such arbitrariness must not allow that to happen with a competent implementation.
')
In the future, we will assume that the attacker (or offender) has access to the full arsenal of assorted nasty actions, such as “listening” to the communication channel, saving all intercepted messages, changing messages, sending previously intercepted messages, etc. We will also assume that the intruder can steal the database from the server. I’ll clarify that all these assumptions do not disagree with the assumptions of the author of the analyzed educational crypto protocol.
We now turn to the kind of protocol that the author presented.
Pay attention to the latest transfer from the client to the server M = hash (RND). It would seem, why hashing? You can simply send the RND and finish it. But not everything is so simple. To begin with, let's consider a weakened version of the authentication protocol, without using hashing on the last transfer, and point out its shortcomings. The protocol scheme will look like this:
The first drawback is that in the weakened version of the protocol the client plays the role of the so-called “Oracle Decryption”. Indeed, the server sends a message to the client (in our case, RND) encrypted in the client's public key. The client decrypts the message with its private key and sends the message in clear text back to the server. Such protocol building strategies are “non-standard”, carry potential vulnerabilities and, in a sense, speak of the author of the protocol amateurishness.
The second drawback is more serious and lies in the fact that the protocol is cracked with some reservations almost instantly. We describe the attack. Suppose the intruder has recognized the number N - the RSA cryptosystem module. Whether he did this by intercepting the data at the registration stage, or has it stolen the database from the server is not important. The main thing is that he knows N. Also suppose that in order to encrypt the message {d || N} on the symmetric key K, the counter mode is chosen (quite real situation). This means that the intruder will be able to easily form the message {d || p} _K by modifying the message {d || N} _K, where p is a prime number chosen by him, and send a message to the client. I would like to lay the truth of this statement on the shoulders of the reader. Further. The attacker chooses the number p in such a way that p-1 has a “good” (in a cryptographic sense) factoring out and also exceeds d (the client's private key). Then, instead of {RND} _e, the intruder sends g - forming groups Z_p ^ *. The unsuspecting client in full compliance with the protocol on the last transfer sends the attacker g ^ d (mod p). Using the Polig-Hellman algorithm, the intruder calculates the client's private key d in polynomial time. After that, the offender will always be able to impersonate a client.
And now we will return to the consideration of the protocol “in the original”, as it was presented by the author (with hashing at the last transfer). I argue that if k is the client's private key length d in bits, then it is realistic to calculate the private key in less than k client attempts to authenticate with the server. I will not give the mathematical calculations proving the statement presented in the article itself, since they are quite voluminous and not intended for a wide circle of readers. However, in order not to be unfounded, I will describe how you can calculate a few lower bits of the d key for a single attempt to authenticate a client on the server. It is obvious that the possibility of such a calculation indicates the vulnerability of the training protocol. Once again, I’ll draw the reader’s attention to the fact that the vulnerability of the training protocol is a “regular” situation that can absolutely say nothing about the persistence of the “combat” protocol. Earlier assumptions that the attacker knows the number N and that the counter mode is used for symmetric encryption are still valid.
Take for our humble example the prime number p = 65537 = 2 ^ 16 + 1. In Z_p ^ *, choose the element g that generates Z_p ^ *. We calculate the values ​​of hash (g), hash (g ^ 2), hash (g ^ 3), ..., hash (g ^ {p-1}) and store them on your computer as a table. Time and memory for this operation will take very little. Intercepting data from the server to the client and, as previously described, replace N with p, RND with g. As a result, we get a hash from the client from an unknown element - hash (g ^ i), find it on our computer in the table and restore i. So we come to the equation
g ^ d = g ^ i mod p
It follows from it that d = i + a (p-1), where a is some unknown number. We obtain that d = i + 2 ^ 16 * a. If we represent the number i as a bit string of length 16, then it will be the last 16 bits of the client's private key.
Note. If this fact is not immediately obvious to someone, then consider the decimal number system. For example, let A = B + 10 ^ 3 * C. Then B is the remainder of dividing the number A by 10 ^ 3 = 1000. And since 1000 is a power of 10 (we work in the decimal number system), then B is the last three digits of A. If A = 12345, then A = 345 + 12 * 1000 and such a decomposition is unique for a non-negative B <= 1000.
Naturally, during the attack, we could calculate a greater number of low bits of the private key. Note that this number directly depends on the available memory on our computer, in which we can store a table of hashes, and on the performance of the PC.
Afterword : In this article I would like to emphasize that those “ready-made” solutions, algorithms and protocols in the field of cryptography, which can be found in the public domain in the literature or the Internet are not at all “ready-made”, they are educational. If you want your project to have really reliable protective mechanisms, take care of the presence in your team of a person with specialized education and experience in the field of information security. This area is extremely extensive, complex and diverse, to understand it with a swoop, I assure you. All success and thank you for your attention!
Source: https://habr.com/ru/post/124090/
All Articles