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 at the end lies a toy based on the material studied.
So, the topic is public key encryption, or rather, White-Box Encrypting. The difference is that the “box” has a certain program instead of the usual encryption function, in which this function is hidden. But I’ll talk about this later, but first ...
What is encryption, I believe, many understand at least intuitively, but what is a public key and why is it needed? Where is it used? How good is its cryptographic strength?
Alena needs to send a secret message with the technical task of Lesha on this channel.
Lesha can’t work without a clear technical specification, so he writes a public key encryption algorithm, consisting of two elements - the encryption algorithm (public) and the decryption algorithm (private). He sends the first algorithm to Alena, and leaves the second to himself - for that he is closed.
Alena joyfully receives the algorithm, applies it to the message, receives encrypted data, which she sends to our hero. That, 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 disaster - having an encryption algorithm and encrypted data, the villain will be able to recover the secret message, especially if the encryption function is set explicitly.
The solution was white-box encryption - instead of the public key, Lesha sends Alena a program in which this algorithm is hidden (obfuscated, complicated), so it’s unlikely that the attacker can pick up this function. It is much faster to find the original message by brute force, and this is an NP class task, so the larger the message and the more complex the algorithm, the more time it will spend on it.
If Alena also knows how to do magic, they can quite fully communicate with each other, while maintaining secrecy.
Consider 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 fair gambling class - the “honest one-armed bandit”, whose probability of winning is 100%. This probability is due to the fact that all the information that affects the successful outcome is in front of the player’s 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, exhaustive search). And so that life does not seem to be honey, the game goes on time.
The game contains two encryption methods of varying complexity - hashing (many to one) and bijection (one to one). The main goal of our game was to explain the principle of such encryption "on the fingers."
The bottom line is to restore (decrypt) the original data over the ring Z 3 (ring of residues modulo 3), 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 select the inverse function of the conversion function in explicit form, which is why this whole NP problem loses its meaning. The superposition of these nodes is the very encryption algorithm.
The algorithm for constructing a bijection is essentially simple: the composition of a bijection is a bijection, so you only need to find a way to build an elementary bijection. Analytical geometry came to our aid - we do not encrypt 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 be able to move from the one received to the original vector, the transition matrix must be reversible - build the inverse to the original, multiply by the encrypted message and get the original data. Thus, it all comes down to constructing such a matrix.
The hashing algorithm is even simpler: we build a bijection, and on each layer of nodes we remove several pieces, continuing this way until we get the required number of nodes at the end. The fact that this algorithm was once a bijection guarantees a uniform distribution, which minimizes collisions.
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 place it), and also used the KineticJS framework to make everything work faster (but they have some dislike with Firefox, so it slows down a bit) .
As promised, I am sharing a link to a toy that was made while working in the laboratory at the university.
I hope that it will show quite clearly that even the simplest mappings (such as a 4-2 hash) are complex enough to decrypt after obfuscation.
Good to all. : 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 at the end lies a toy based on the material studied.
So, the topic is public key encryption, or rather, White-Box Encrypting. The difference is that the “box” has a certain program instead of the usual encryption function, in which this function is hidden. But I’ll talk about this later, but first ...
Description
What is encryption, I believe, many understand at least intuitively, but what is a public key and why is it needed? Where is it used? How good is its cryptographic strength?
Cryptographic strength
ability of the algorithm to resist hacking without a hot soldering iron.
Consider the following task:
Given:
- Secret message;
- Man # 1, let's call him Alena;
- Man # 2 - Lesha;
- Unprotected communication channel.
Task:
Alena needs to send a secret message with the technical task of Lesha on this channel.
Decision:
Lesha can’t work without a clear technical specification, so he writes a public key encryption algorithm, consisting of two elements - the encryption algorithm (public) and the decryption algorithm (private). He sends the first algorithm to Alena, and leaves the second to himself - for that he is closed.
Alena joyfully receives the algorithm, applies it to the message, receives encrypted data, which she sends to our hero. That, 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 disaster - having an encryption algorithm and encrypted data, the villain will be able to recover the secret message, especially if the encryption function is set explicitly.
The solution was white-box encryption - instead of the public key, Lesha sends Alena a program in which this algorithm is hidden (obfuscated, complicated), so it’s unlikely that the attacker can pick up this function. It is much faster to find the original message by brute force, and this is an NP class task, so the larger the message and the more complex the algorithm, the more time it will spend on it.
Proof
The table shows the estimated time for a complete enumeration of passwords depending on their length. It is assumed that 36 different characters can be used in the password (Latin letters of the same register + numbers), and the search speed is 100,000 passwords per second (attack class B, typical for recovering a password from the Windows Cache (.PWL files) on a Pentium 100). Wikipedia
| Number of characters | Number of options | Durability | Sorting Time |
|---|---|---|---|
| one | 36 | 5 bit | less than a second |
| 2 | 1296 | 10 bit | less than a second |
| 3 | 46,656 | 15 bit | less than a second |
| four | 1 679 616 | 21 bit | 17 seconds |
| five | 60 466 176 | 26 bit | 10 minutes |
| 6 | 2 176 782 336 | 31 бит | 6 часов |
| 7 | 78 364 164 096 | 36 бит | 9 дней |
| 8 | 2,821 109 9x1012 | 41 бит | 11 месяцев |
| 9 | 1,015 599 5x1014 | 46 бит | 32 года |
| 10 | 3,656 158 4x1015 | 52 бита | 1 162 года |
| 11 | 1,316 217 0x1017 | 58 бит | 41 823 года |
| 12 | 4,738 381 3x1018 | 62 бита | 1 505 615 лет |
If Alena also knows how to do magic, they can quite fully communicate with each other, while maintaining secrecy.
About the toy
Consider 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 fair gambling class - the “honest one-armed bandit”, whose probability of winning is 100%. This probability is due to the fact that all the information that affects the successful outcome is in front of the player’s 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, exhaustive search). And so that life does not seem to be honey, the game goes on time.
The game contains two encryption methods of varying complexity - hashing (many to one) and bijection (one to one). The main goal of our game was to explain the principle of such encryption "on the fingers."
The bottom line is to restore (decrypt) the original data over the ring Z 3 (ring of residues modulo 3), 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 select the inverse function of the conversion function in explicit form, which is why this whole NP problem loses its meaning. The superposition of these nodes is the very encryption algorithm.
Maths
The algorithm for constructing a bijection is essentially simple: the composition of a bijection is a bijection, so you only need to find a way to build an elementary bijection. Analytical geometry came to our aid - we do not encrypt 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 be able to move from the one received to the original vector, the transition matrix must be reversible - build the inverse to the original, multiply by the encrypted message and get the original data. Thus, it all comes down to constructing such a matrix.
The hashing algorithm is even simpler: we build a bijection, and on each layer of nodes we remove several pieces, continuing this way until we get the required number of nodes at the end. The fact that this algorithm was once a bijection guarantees a uniform distribution, which minimizes collisions.
In this way:
- The initial message is a vector of values above the ring Z 3 (3 values represented by different colors);
- Encryption Algorithm - Matrix;
- Algorithm obfuscation - sets of matrices with two inputs and one output;
- An encrypted message is a vector obtained by multiplying the original message by a 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 place it), and also used the KineticJS framework to make everything work faster (but they have some dislike with Firefox, so it slows down a bit) .
Conclusion
As promised, I am sharing a link to a toy that was made while working in the laboratory at the university.
I hope that it will show quite clearly that even the simplest mappings (such as a 4-2 hash) are complex enough to decrypt after obfuscation.
Good to all. : 3