White-box cryptography in pictures
Good day!
You always wanted to know about the principles of public key encryption, but were afraid to ask? Not? Anyway, the article is interesting (and even understandable), and in the end lies a toy based on the material studied.
So, the theme is public key encryption, or rather, White-Box Encrypting. The difference is that the “box” instead of the usual encryption function has a certain program in which this function is hidden. But I will tell about it later, but first ...
What is encryption, I believe, many understand at least intuitively, but what is the public key and why is it needed? Where is it used? How good is its crypt endurance?
Alyona needs to send a secret message with a technical task Lesha through this channel.
Lyosha cannot work without a clear technical task, so he writes a public-key encryption algorithm consisting of two elements — the encryption algorithm itself (open) and the decryption algorithm (private). He sends the first algorithm to Alena, and the second leaves to himself - that’s why he’s closed.
Alena happily receives the algorithm, applies the message, receives encrypted data, which she sends to our hero. The latter, in turn, applies its decryption algorithm to this data, receiving the original secret message. Everyone is happy - the project will be completed on time.
Let everything not be so rosy - the attacker intercepted the transfer. This is a problem - having an encryption algorithm and encrypted data, the villain will be able to recover the secret message, especially if the encryption function is specified explicitly.
The solution was white-box encryption - instead of the public key, Lyosha sends Aliona a program in which this algorithm is hidden (obfuscated, complicated), so the attacker is unlikely to find this function. It is much faster to find the original message in full brute force, and this is an NP class problem, so the larger the message and the more complex the algorithm, the more time it spends on it.
')
If Alena also can do magic, they can fully communicate with each other, while maintaining secrecy.
Consider the slot machines. It is known that the probability of winning on these devices is extremely small, while nothing depends on a person at all. Obviously, this is not fair. So why not fix it?
No sooner said than done. Meet the representative of the class of fair gambling - “honest one-armed gangster”, the probability of winning in which equals 100%. This probability was due to the fact that all the information that affects the successful outcome is in the game before the eyes.
Why, you ask, a machine that does not bring benefits? Everything is so simple - the approach is based on the theory of computational complexity (“complexity theory” - the name was taken from there), so a person, as already mentioned, simply needs to solve the NP problem (hello, brute force). And so life does not seem like honey, the game goes on time.
The game contains two methods of encryption of different complexity - hashing (many in one) and bijection (one in one). The main goal of our game was to explain the principle of such encryption "on the fingers."
The point is to recover (decrypt) the original data over the Z 3 ring (modulo-3 residue ring), having before your eyes only an encrypted message and an encryption algorithm.
This algorithm is a set of nodes with transition tables - it has 2 inputs, whose values ​​are converted, generating an output value. The algorithm was divided into nodes for a reason - this is obfuscation (complication), because it is much easier to choose an inverse function for the transformation function, which makes the whole NP problem losing its meaning. The superposition of these nodes is the same encryption algorithm.
The algorithm for constructing a bijection is essentially simple: the composition of bijections is a bijection, so you only need to find a way to construct an elementary bijection. Analytical geometry has come to our aid — we are not ciphering the colors, but the coordinates of the vector. Multiplying the transition matrix by a given vector, we get a new vector - encrypted, and in order to go from the received to the original vector, the transition matrix must be reversible - we build the inverse of the original, multiply by the encrypted message and get the original data. Thus, it all comes down to building such a matrix.
The hashing algorithm is even simpler: we build a bijection, and on each layer of nodes we remove a few pieces, continuing so until we get the number of nodes we need at the end. The fact that this algorithm was once a bijection, guarantees us a uniform distribution, which reduces the number of collisions to a minimum.
In this way:
The toy was made on Canvas, so you can play it from any device. They wrote, of course, in JavaScript, PHP (to generate a graph), C ++ (to post it), and also used the KineticJS framework to make everything work faster (but they have some kind of dislike for Firefox, so it’s a bit slow) .
As promised, I share a link to the toy , which was made while working in the laboratory at the university.
I hope it will quite clearly show that even the simplest mappings (such as hash 4-2) are quite complex to decrypt after obfuscation.
All good. : 3
You always wanted to know about the principles of public key encryption, but were afraid to ask? Not? Anyway, the article is interesting (and even understandable), and in the end lies a toy based on the material studied.
So, the theme is public key encryption, or rather, White-Box Encrypting. The difference is that the “box” instead of the usual encryption function has a certain program in which this function is hidden. But I will tell about it later, but first ...
Description
What is encryption, I believe, many understand at least intuitively, but what is the public key and why is it needed? Where is it used? How good is its crypt endurance?
Crypt resistance
the ability of the algorithm to resist hacking without a hot soldering iron.
Consider this task:
Given:
- Secret message;
- Man # 1, let's call him Alena;
- Person # 2 - Lesha;
- Unprotected communication channel.
Task:
Alyona needs to send a secret message with a technical task Lesha through this channel.
Decision:
Lyosha cannot work without a clear technical task, so he writes a public-key encryption algorithm consisting of two elements — the encryption algorithm itself (open) and the decryption algorithm (private). He sends the first algorithm to Alena, and the second leaves to himself - that’s why he’s closed.
Alena happily receives the algorithm, applies the message, receives encrypted data, which she sends to our hero. The latter, in turn, applies its decryption algorithm to this data, receiving the original secret message. Everyone is happy - the project will be completed on time.
Let everything not be so rosy - the attacker intercepted the transfer. This is a problem - having an encryption algorithm and encrypted data, the villain will be able to recover the secret message, especially if the encryption function is specified explicitly.
The solution was white-box encryption - instead of the public key, Lyosha sends Aliona a program in which this algorithm is hidden (obfuscated, complicated), so the attacker is unlikely to find this function. It is much faster to find the original message in full brute force, and this is an NP class problem, so the larger the message and the more complex the algorithm, the more time it spends on it.
Proof
The table shows the estimated time for a complete brute force of passwords, depending on their length. It is assumed that the password can use 36 different characters (Latin letters of one register + numbers), and the search speed is 100,000 passwords per second (attack class B, typical for recovering the password from the Windows Cache (.PWL files) to the Pentium 100). Wikipedia
| Number of characters | Number of options | Persistence | Iteration time |
|---|---|---|---|
| one | 36 | 5 bits | less than a second |
| 2 | 1296 | 10 bits | less than a second |
| 3 | 46,656 | 15 bits | less than a second |
| four | 1,679,616 | 21 bits | 17 seconds |
| five | 60 466 176 | 26 bits | 10 minutes |
| 6 | 2 176 782 336 | 31 bits | 6 o'clock |
| 7 | 78 364 164 096 | 36 bits | 9 days |
| eight | 2,821 109 9x10 12 | 41 bits | 11 months |
| 9 | 1,015 599 5x10 14 | 46 bits | 32 years |
| ten | 3,656 158 4x10 15 | 52 bits | 1 162 years |
| eleven | 1,316 217 0x10 17 | 58 bits | 41,823 years |
| 12 | 4,738 381 3x10 18 | 62 bits | 1,505,615 years old |
')
If Alena also can do magic, they can fully communicate with each other, while maintaining secrecy.
Pro toy
Consider the slot machines. It is known that the probability of winning on these devices is extremely small, while nothing depends on a person at all. Obviously, this is not fair. So why not fix it?
No sooner said than done. Meet the representative of the class of fair gambling - “honest one-armed gangster”, the probability of winning in which equals 100%. This probability was due to the fact that all the information that affects the successful outcome is in the game before the eyes.
Why, you ask, a machine that does not bring benefits? Everything is so simple - the approach is based on the theory of computational complexity (“complexity theory” - the name was taken from there), so a person, as already mentioned, simply needs to solve the NP problem (hello, brute force). And so life does not seem like honey, the game goes on time.
The game contains two methods of encryption of different complexity - hashing (many in one) and bijection (one in one). The main goal of our game was to explain the principle of such encryption "on the fingers."
The point is to recover (decrypt) the original data over the Z 3 ring (modulo-3 residue ring), having before your eyes only an encrypted message and an encryption algorithm.
This algorithm is a set of nodes with transition tables - it has 2 inputs, whose values ​​are converted, generating an output value. The algorithm was divided into nodes for a reason - this is obfuscation (complication), because it is much easier to choose an inverse function for the transformation function, which makes the whole NP problem losing its meaning. The superposition of these nodes is the same encryption algorithm.
Maths
The algorithm for constructing a bijection is essentially simple: the composition of bijections is a bijection, so you only need to find a way to construct an elementary bijection. Analytical geometry has come to our aid — we are not ciphering the colors, but the coordinates of the vector. Multiplying the transition matrix by a given vector, we get a new vector - encrypted, and in order to go from the received to the original vector, the transition matrix must be reversible - we build the inverse of the original, multiply by the encrypted message and get the original data. Thus, it all comes down to building such a matrix.
The hashing algorithm is even simpler: we build a bijection, and on each layer of nodes we remove a few pieces, continuing so until we get the number of nodes we need at the end. The fact that this algorithm was once a bijection, guarantees us a uniform distribution, which reduces the number of collisions to a minimum.
In this way:
- The original message is the vector of values ​​above the ring Z 3 (3 values ​​represented by different colors);
- The encryption algorithm is a matrix;
- Algorithm obfuscation - matrix sets with two inputs and one output;
- An encrypted message is a vector obtained by multiplying the original message by the matrix.
Programming
The toy was made on Canvas, so you can play it from any device. They wrote, of course, in JavaScript, PHP (to generate a graph), C ++ (to post it), and also used the KineticJS framework to make everything work faster (but they have some kind of dislike for Firefox, so it’s a bit slow) .
Conclusion
As promised, I share a link to the toy , which was made while working in the laboratory at the university.
I hope it will quite clearly show that even the simplest mappings (such as hash 4-2) are quite complex to decrypt after obfuscation.
All good. : 3
Source: https://habr.com/ru/post/171169/
All Articles