The article starts from zero and will gradually increase its level until a full description of these functions.
What is a Hash?
The definition of Wikipedia, says "In science, a hash function or hash algorithm is a function to summarize or probabilistically identify a large set of information, resulting in a generally lower finite image ..."
A hash function is a mathematical algorithm that gives us a result B by applying it to an initial value A. It's like any mathematical function, eg the square root function would result in us if it is applied 2 to 4. E like any mathematical function has to act in such manner and must meet certain criteria. We can not return anything, so we need to take back certain properties so that we can use.
Properties that have to comply with the hash function?
1 - Whatever the length of the text based on the length of the hash result B will always be the same. For example, if the length of the output B is set to 128 bits, if we apply a hash function for a 5-bit A to B will give us a 128-bit, and if it is applied to an A of 380 million bits, we B gives a 128-bit as well.
2 - For each entry, the function will generate an output B only. Or what is the same, it is impossible for two texts bases A and A 'have the same hash B.
According to these first two properties, then we realize the usefulness of the hash functions.
The most immediate use is to generate a summary of something. In fact, these functions are also known as abstract functions. An actual example may be typical of the document repository. If someone wants to store say "La_Divina_ Comedia.doc"
whose content is Dante Alighieri, the system the first thing to do is check that it is not already stored previously with the same or another name, such as "Dante Alighieri.doc. The system can compare the document letter by letter with input from all the docs to check that your database is not the abstract or you can compare the input with summaries of the documents in the database, an option far more manageable and quick.
Moreover, as the output B is unique for each A, can also be used to verify the integrity of A. We can see that many programs include a hash along with your download, this way, we can verify that the program has not been changed or have introduced a virus or been troyanizado. If the bytes of an application will calculate the hash and B hereto, when someone changed the application A, to recalculate its hash value will be changed and different from B.
Can try to calculate the md5 of a document, then modify a single comma of the document and calculate the MD5 again. Summer and has completely changed, although we have only changed a single comma.
3 - As a basic text, is easy and fast (for a computer) to calculate their number summary.
4 - It is impossible to reconstruct the text based on the number summary.
This is known as One-Way Hash functions. From the hash it is impossible to reconstruct the text base.
Attention here!, This is a point that many are not clear. You need only read well, from hash B is impossible to draw the text, it means there is or is computationally impossible, using mathematical or not to reverse the hash algorithm, B is reached from the text base.
If they realize this is very different than using brute force. It has nothing to do. With brute force you apply the hash function to different texts until we get a hash similar to the hash of the text we want, which will result in the search text.
Our hash function.
Let's invent an example to see it clearly. This could not be taken as a hash function reliably because it is too weak to attack, but it serves as graphic example if it was not entirely clear.
This hash function in our example it does is translate the text to each character input into its equivalent ASCII code, the groups of 3 on 3 and applied the mathematical function (1 - 2) * 3.
As we see, the value of our hash function applied to the basic text to "a place of Cu Mancha" is -19,631.
Satisfies property 1, (almost), with a little more development may cause the size of the hash returned is always the same.
Meets the 2, the value of the hash is unique for each text. If we change one iota the sentence, the value changes.
Meets the 3 because it is the result and immediately get to 4, as from -19631 can not get to the text.
5. - You can not Collisions.
Are collisions?
The first feature we've seen of the hash function, which tells us that the size of the resulting hash B of A is always the same, can not deduce that met the second features that B said that the hash has to be unique for each A.
For example, the function returns an MD5 hash of 128 bits. For each hash corresponds to a single base, there should be only one text for each combination of the hash returned, or should have only 2 ^ 128 different texts, which is not true. As there are infinite different texts, we can say that there are infinite possibilities that two texts have the same hash.
This is known as a collision.
Surely we have seen many times without realizing that happening. There are many systems that require use of passwords, such as systems and other forums where it is stored is not the password, but the hash of that password. This is not done with the purpose of summarizing the password, will be shorter than the hash generated is done so that if someone has access to store passwords, or if someone disassembles the application proteguida, etc, can not see password in the plane and continue with no access (unless the cracking by brute force if you know the algorithm of the function).
Must have ever encountered with any program that requests a password to access something, you get the cracker, and gives you access without password? I remember that in Excel95 or 97, the program leaves or desprotejía cells functioned well, but not unprotected leaf was the key.
That is because the hash function algorithm used for passwords is as simple as that we have an example, have multiple collisions and very easy to find. So instead of looking for the password that is seeking to hash collisions, passwords alternatives having the same hash that the real password.
The strength of a hash function requires that these collisions are the minimum possible and found to be as difficult as possible.
Well, here comes the base hash function. Explains their overall functioning, their properties and uses.
They no longer have an excuse to ask how to decrypt a hash, I think it has become clear that the hashes are not an encryption method and the result can not get the text-based rather than by brute force.
Properties of a function with respect to hash collisions.
The properties that should have hash primitives are:
1. Resistance to preimagen: One Way Hash Function. As we said before, means that any given image, it is computationally impossible to find a message x such that h (x) = y. Otherwise known as this property is that h is one-way.
2. Resistance 2 preimagen: OWHF: Weak One Way Hash Function. Means that given x it is computationally impossible to find an x 'such that h (x) = h (x'). Another way to know this property is that h is a collision-resistant soft.
3. Collision resistance: CRHF: Strong One Way Hash Function. Means that it is computationally impossible to find two different messages x, x 'such that h (x) = h (x'). This property is also known as a strong collision resistance.
Let's make some examples to see the need for these properties:
We will establish a digital signature scenario.
X is attached a document with his signature, which consists of clacular the hash of X, h (X), and in numbers, C (h (X)) with the private key of the sender or owner.
To verify the completeness of X, the recipient or the person concerned with the public key decrypts the owner C (h (X)) to obtain h (X) initial estimates of the new h (X) of the document and compares them . If h (X) is equal to the initial h (X) is that this new document has not been altered and that belongs to the signer.
If the hash function does not have an resintencia to 2nd preimagen, an attacker C that might find a message X 'such that h (X') = h (X), and claim that the document is not signed but X X '.
Or imagine that C must file a third party to sign a document X, yet another document drafted Y. If the hash function is not resistant to collisions, C garbage can add information to X and Y (X 'and Y') so that h (X + X ') = h (Y + Y'). Then the sign X is also signing Y.
Finally, if (e, n) is the RSA public key of A, C can choose randomly calculate a yy z = e mod n, and claim that is the signature of z, if one can find C preimagen such that x = z h (x), where x is important to A. This is avoidable if h is resistant to preimagen.
MD5 Algorithm
The MD5 algorithm performs the following operations:
1. Adding a bit of filler:
The message is filled in or extended so that its length in bits is congruent to 448 module 512. This must be the case because we must reserve 64 bits for adding the message length in the next step. So if they do not reach the previous matching the filling is added, consisting of a bit'1 'followed by as many bits'0' as required.
The reason why a one followed by zeros that should be used only when filled with a value (eg all zeros) the process would be reversed to remove the stuffing.
Anyway, he always does this filler, but the length of the message is consistent and 448 in module 512. Therefore, add at least 1 bit of padding, and a maximum of 512 bits. Note the following figure:
2. Adding binary representation length of the message:
Subsequently added to the message (with stuffing made) a representation of the message length before being filled. This representation will have a length of 64 bits (16 words of 32 bits, ie two integers of 4 bytes each). In the event that the message is more than bits, will only be considered less representative than the 64 bits, which means that this representation of the message length is made in module.
The message now has a number multiple of 512 bits, so there will be a whole number of words of 32 bits (4 bytes of integers), namely 512 / 32 = 16, so it can be concluded that if there are b blocks 512 bits each, which form the message, then the message will have 32-bit words of n: n = 16 * b
3. Initialize MD buffer:
To calculate the hash value or abstract need a buffer of 4 words of 32 bits (A, B, C, D), but before starting the process has been initialized with a predicted value, which provides Rivest:
A = Word 01 23 45 67 67 45 23 01
Word B = 89 ab ab cd cd ef ef 89
Word Faith C = dc ba 98 98 ba dc faith
Word D = 76 54 32 10 10 32 54 76
In the first column hexadecimal values are ordered so that the values are less significant in the first place (by Rivest notation used in the implementation of this algorithm), and the second most important values are to the left (positions higher memory in Intel 80xxx)
Why do these forms represent the same values should be trying to avoid confusion, because depending on the type and architecture of the machine on which the algorithm has to work, this will undergo changes in these values when performing the implementation. This is due to the different ways in which data is stored in memory in different architectures (Intel, Sun, Sparc, ...)
MD4 and MD5 algorithms are designed to facilitate its implementation in so-called little-endian architectures. This format assumes that the least significant byte of a word is stored in the lowest position, and the most significant byte at the highest. Is the format used by Intel processors that integrate PC 80xxx home.
4. Process the message in blocks of 512 bits:
This is the core of the algorithm. Here we define the four functions that are used in the four rounds to be applied on each block. See the following figure:
These four functions as input parameters are three words of 32 bits each (three integers of 4 bytes long) and returned as an output. They are:
F (X, Y, Z) = (X and Y) or ((not X) and Z)
G (X, Y, Z) = (X and Z) or (Y and (not Z))
H (X, Y, Z) = X Y Z
I (X, Y, Z) = Y (or X (not Z))
Where F acts as a conditional if in programming: If x = 1 then Y will be 1 otherwise Z is 1.
G also operates as a conditional F: If Z = 1 then X is 1 and is 1 otherwise.
H simply performing the operation Exclusive-OR (XOR) of X, Y and Z.
I performed the operation XOR is 1 if X or Z is 0.
On the other hand does not use the constant MD5 ( 'magic' constants) that were used in MD4. In its place is used a table of 64 elements constructed from the trigonometric function within. T is the ith element of that table, which is equal to the integer part of 4294967296 times abs (sin (i)), where i is expressed in radians. Since there are 16 steps to perform in each of the four rounds, ie, 64 operations, the idea is to use one of the above table for each round.
5. Collect the output hash value:
The output hash value is obtained from records A, B, C and D, where D is more representative byte and the least A.
Attacks
Birthday attack.
The best known attack (brute force) to a hash function is known as the "birthday attack" and is based on the following paradox.
What is the quantity of people who put in a room so that the probability that the birthday of one of them is the same day as mine?
We calculate an n such that (1 / 365)> 0.5, then n> 182.
However, it would be the number of people necessary to meet any two of these years the same day?
Each pair has a probability of 1 / 365, and a group of n people there are n (n-1) / 2 different pairs, then
(n (n-1) / 2) (1 / 365)> 0.5
This is true if n> 23, a surprising number smaller than 182.
The consequence of this paradox is that although it is very difficult to calculate an x an x 'such that h (x) = h (x'), it is much easier to find two random xyx 'such that h (x) = h ( x ').
This in practice means that an n-bit hash of a collision would 2nd preimagen or weak once every 2 ^ n, but will produce a strong collision once every 2 ^ (n / 2).
In the case of a hash of 64 bits would require 2 ^ 64 messages a given x to obtain x ', but enough to generate 2 ^ 32 random messages to appear with the same two hash. The first attack it would take 600,000 years to a computer to generate a million messages per second, while the latter required only a few hours.
Wang Yin-attack or attack Chinese-Yu
I suppose that many would have read that currently MD5 and SHA1 hash functions have been broken by a group of Chinese mathematicians who are useless and so on.
We will try to explain this so that everyone can evaluate the degree of disruption of these functions, but does not assess the extent to which we are affected.
As seen in the Birthday Attack, to find two messages X and X 'trials have the same SHA-1 (160 bits), for example, by brute force would be needed to generate 2 ^ (160 / 2) messages.
Well, this group of mathematicians has discovered a system that allows to do this with less effort than by brute force.
Specifically for SHA1 can find a "collision Birthday" with an effort equivalent to 2 ^ 69 hash operations, instead of 2 ^ 80 required by brute force.
As we can see, this is a strong attack on collisions, but not against the collision of 2 preimagen, which does not affect. If someone wants to generate a message x 'having the same x SHA1 an existing message, you must continue to generate 2 ^ 160 to get messages.
And although the "birthday attack" against SHA1 became 2000 times faster, is still the order of 10,000 times more difficult for an attack on a DES, which is not accessible to the entire world.
However, there are cases where the implications are important.
Imagine you compose a contract of sale of real estate in word, to which I attach jpgs with several photographs of the property.
At the same time a genre Alternative A 'with the same pictures but by changing the price in my favor.
It is practically impossible for the h (A) = h (A ').
However I can create multiple versions of A and A ', changing random bits of photos (could be done by modifying the text by adding spaces, no significant change things, etc. but would be a very dirty and the notaries "cheating" . But changing bits of the pictures as much as to lose something), until two versions of the same hash.
I present to the buyer's version of A, agree to the terms and signs it electronically. A variant of the change by that of A 'and I already have a signed legal contract of sale with conditions other than the establishment.
If the hash function to be used for the signature is an SHA1 for example, through the tri-Chinese attack will have to generate 2 ^ 69 variants of A and 2 ^ 69 variants of A ', which as we have seen before, though not affordable to anyone, it is feasible.
But if the hash function is an MD5 for example, you only need to generate 2 ^ 32 variants of A and 2 ^ 32 variants of A ', which is accessible to any PC.
Multicolision attack of Joux-Wang.
If we look at the functioning of the MD5 algorithm, we see the message is divided into blocks of 512 bits. The first block is "hashed" using as parameter the initialization vector and resulting in another 128-bit vector, which serves as initialization for the next block of 512 bits, and so on.
Then it becomes obvious that if I No two blocks A and B, where A! = B, which satisfy that MD5 (A) = MD5 (B), if you add a "payload" Q, then MD5 (A + Q) MD5 = (B + Q).
http://www.codeproject.com/dotnet/HackingMd5.asp.
The development shown here as an example, is based on an application that runs files in a proprietary format for distribution. We have an executable goodexe.exe before it becomes a distribution format. Bin, and an "extractor" that runs this. Bin.
Devilexe.exe also has an executable that is supposed to be malware.
What your application is taking a vector A and B such that MD5 (A) = MD5 (B), generates good.bin doing goodexe.exe A + + evilexe.exe, and generates evil.bin by B goodeexe.exe + + evilexe.exe. In this way, MD5 (good.bin) = MD5 (evil.bin).
Then the extractor, if looking. Bin is A or B, or evilexe runs goodexe.
This way you can hang good.bin on the network, and later replaced by evil.bin (previously renamed of course).
Since MD5 is the same, nobody will doubt, and run a separate program.
Personally I see no utility in this instance, is how to distribute a trojan that only the activation date you decide to graduate.
"The story of Alice and her boss"
Another example that is more interesting.
Here you can see two cards in PostScript different within the same context where MD5 is the same for both:
http://www.cits.rub.de/MD5Collisions/
In a sign that a letter of recommendation is ordinary, you are signing the other, which is a card that gives you access to secrets.
The creators of these letters do not give technical details about how this is done, but say they are preparing a document that explains it.
But we do not like to wait, so we detail the procedure exclusively.
If we publish both. Ps, we see that the code is something like this:
Code: [Select]
%! PS-Adobe-1.0
%% BoundingBox: 0 0 612 792
(characters rare) (rare characters) eq (/ Times-Roman findfont 20 scalefont setfont
300 700 moveto (Julius. Caesar) show
.
.
) (/ Times-Roman findfont 20 scalefont setfont
300 700 moveto (Julius. Caesar) show
.
.
ifelse)
showpage
Perhaps some layoffs because the code is in reverse Polish notation, but if we look at the line of rare characters, what he is doing is comparing what is inside the first parenthesis to what lies within the second.
Returns True if they are equal, and you run the first block of code (), which is corresponding to the letter of recommendation, and if you are not the same code is executed by the next block (), which is the letter that empowers .
Now open them. Ps with a hex editor and as we look at the structure diviéndola in blocks of 64 bytes.
Why 64 bytes? Because as we said before, the algorithm is MD5 hash of 512 to 512 bits (64 bytes).
So we see that the first block of 64 bytes is common in both. Ps, as is the header that has been touched up conveniently to fill exactly that.
Well, and we also see that the following two blocks of 64 bytes correspond to the characters of the first parenthesis.
These two blocks differ from one another ps.
A block of 4, everything is common to both. Ps.
Now everything is clearer.
Cab mounted header have to fill 64 bytes. Then have created two versions A and B by adding 128 bytes randomly looking for a collision that MD5 (Cab + A) = MD5 (Cab + B).
At this point, like the rest of the code is the same for both documents, both documents share hash, so we are looking whether the document has A or B to show a letter or the other.
Current state of the hash function.
MD4 hash function is totally broken and out of print, in fact there are algorithms that find collisions in a few seconds.
To use MD5 must take certain precautions, but anyone who has read this paper is able to take them. It is best not to use it, but if we have no choice, using it is perfectly safe with care. For example not using MD5 if firmeis anything which writes the document to sign is an interested party, or change anything before you sign the document or save a copy, etc..
For SHA1, I would not say as they say in many places that the building is on fire and we lost. The only thing is that the alarm sounds, even though we do not see the smoke, and it is prudent to go to the emergency exit, but no need to run or panic. But nor should we stay on the site, because the cryptanalytic attacks each day get better, and each will be easier and faster.
The solution being given to this problem is to increase the size of the hashes. PGP uses and SHA256, etc. But it is only a patch. These algorithms are all mono, and giving more bits only increases the effort to find collisions. But according to advance the methods of cryptanalysis, and computing power, Iran is cutting time, and we in them.
The most critical point is legal. All that is firm with a legal certificate or the electronic ID future, has the same value as a handwritten signature.
The legal consideration is based inter alia on the hash algorithm of the signature works like it should be and that the resulting hash is unique to the signed text.
If a system can not guarantee that the document is such that you signed, and there is no possibility that you have the cambiazo to another document that has the same hash, all the documents signed by that application will not be legal.
If you have pictures of traffic Australia without going further:
http://www.hispasec.com/unaaldia/2489
Solution? Very simple. Using double hashes.
People are not given the importance of the problem of collisions, and if it is, for example PHP, do not settle well.
If you sign for something rather than encrypt the MD5 or SHA1 or SHA256 the document is encrypted by a concatenation of MD5 + SHA1 example, a collision would have to look twice to get an alternative document, which is currently impossible.
If you have to use electronic signatures to documents, and will be signed using MD5 for example, adding a fingerprint-style camp with SHA1 hash of the document.
...............................................................................
Seguramente todos hemos oído hablar de ellos, pero pocos tienen realmente claro lo que son y cómo funcionan.
El artículo comienza desde cero y va a ir aumentando su nivel hasta una descripción completa de estas funciones.
¿Qué es un hash?
La definición de Wikipedia, dice: "En ciencia, una función de hash o algoritmo hash es una función para resumir o identificar probabilísticamente un gran conjunto de información, lo que resulta en una imagen finito generalmente menor ..."
Una función hash es un algoritmo matemático que nos da un resultado B por su aplicación a un valor inicial A. 's, como cualquier función matemática, por ejemplo, la raíz cuadrada resultado en función de si se aplica 2 a 4. E igual que cualquier función matemática tiene que actuar en la forma y debe cumplir con ciertos criterios. No podemos devolver nada, así que necesitamos que vuelva a hacerse determinadas propiedades de manera que podemos utilizar.
Propiedades que tienen que cumplir con la función de hash?
1 - Sea cual sea la longitud del texto sobre la base de la longitud de la B resultado será siempre el mismo. Por ejemplo, si la longitud de la salida B se fija a 128 bits, si se aplica una función de hash para un poco 5-A a B, nos dará un 128-bits, y si se aplica a una A de 380 millones de bits , nos da una B de 128 bits también.
2 - Por cada entrada, la función de generar una salida B solamente. O lo que es lo mismo, es imposible que dos textos bases A y A 'tienen el mismo hash B.
Según estas dos primeras propiedades, entonces nos damos cuenta de la utilidad de las funciones de hash.
El uso más inmediato es generar un resumen de algo. De hecho, estas funciones también se conocen como funciones de resumen. Un ejemplo real puede ser típico de la repositorio de documentos. Si alguien quiere almacenar decir "La_Divina_ Comedia.doc"
cuyo contenido es Dante Alighieri, el sistema lo primero que hay que hacer es comprobar que no está ya almacenada previamente con el mismo u otro nombre, como "Dante Alighieri.doc. El sistema se puede comparar el documento letra por letra con el aporte de todos la documentación para comprobar que su base de datos no es el resumen o se puede comparar la entrada con los resúmenes de los documentos en la base de datos, una opción mucho más manejable y rápido.
Además, como la salida B es única para cada una, también se puede utilizar para verificar la integridad de A. Se puede ver que muchos programas incluyen un hash junto con su descarga, de esta manera, podemos comprobar que el programa no ha cambiado o han introducido un virus o han sido troyanizado. Si los bytes de una solicitud de calcular el hash y B, cuando alguien ha cambiado la aplicación A, de volver a calcular su valor se cambiará y diferentes de B.
Puede tratar de calcular el md5 de un documento y, a continuación, modificar una sola coma del documento y calcular el MD5 de nuevo. Verano y ha cambiado completamente, aunque sólo hemos cambiado una sola coma.
3 - Como un texto de base, es fácil y rápido (de un ordenador) para calcular su número resumen.
4 - Es imposible reconstruir el texto en función del número resumen.
Esto se conoce como Camino de un Hash functions. Desde el hash es imposible reconstruir el texto base.
Atención aquí, este es un punto que muchos no están claros. Solo hay que leer bien, desde hash B es imposible sacar el texto, significa que hay o es computacionalmente imposible, utilizando matemática o no para invertir la algoritmo, B se alcanza la base del texto.
Si se dan cuenta de esto es muy diferente de utilizar la fuerza bruta. No tiene nada que ver. Con la fuerza bruta de aplicar la función a los diferentes textos hasta obtener un hash similar a la hash del texto que queremos, lo que resultará en la búsqueda de texto.
Nuestra función.
Vamos a inventar un ejemplo para verlo claramente. Esto no podría tomarse como una función de hash fiable porque es demasiado débil para atacar, pero sirve como ejemplo gráfico, si no era del todo clara.
Esta función en nuestro ejemplo lo que hace es traducir el texto a cada entrada de caracteres en su equivalente en código ASCII, los grupos de 3 en 3 y aplica la función matemática (1 - 2) * 3.
Como vemos, el valor de nuestra función de hash aplicada a la base el texto a "un lugar de Cu Mancha" es -19.631.
Satisface la propiedad 1, (casi), con un poco más de desarrollo puede hacer que el tamaño de la tabla que se muestra es siempre la misma.
Cumple con el 2, el valor del hash es único para cada texto. Si cambiamos un ápice la sentencia, el valor cambia.
Cumple las 3 porque es el resultado de inmediato y llegar a 4, a partir de -19631 no se puede obtener en el texto.
5. - Usted no puede colisiones.
Son las colisiones?
La primera característica que hemos visto de la función de hash, que nos dice que el tamaño de la resultante de un hash de B es siempre la misma, no puede deducir que se reunió la segunda B, características que dice que el hash ha de ser único para cada A.
Por ejemplo, la función devuelve un valor hash MD5 de 128 bits. Para cada hash corresponde a una sola base, sólo puede haber un texto para cada combinación de la tabla hash devuelto, o debería haber sólo 2 ^ 128 textos diferentes, que no es cierto. Como hay infinidad de textos diferentes, podemos decir que hay infinitas posibilidades de que ambos textos tienen el mismo hash.
Esto se conoce como una colisión.
Seguramente hemos visto muchas veces sin darse cuenta de que eso suceda. Existen muchos sistemas que requieren el uso de contraseñas, tales como los sistemas y en otros foros donde se almacena la contraseña no es, pero el hash de la contraseña. Esto no se hace con el propósito de resumir la contraseña, será más corto que el hash generado se realiza de manera que si alguien tiene acceso al almacén de contraseñas, o si alguien desmonta la aplicación proteguida, etc, no puede ver la contraseña en el avión y continuar que no tienen acceso (a menos que el agrietamiento por la fuerza bruta, si conoce el algoritmo de la función).
Debe haber tropezado nunca con cualquier programa que solicita una contraseña para acceder a algo, se obtiene el cracker, y le da el acceso sin contraseña? Recuerdo que en Excel95 o 97, el programa deja desprotejía o células funcionado bien, pero no sin protección es la clave de la hoja.
Esto se debe a que la función de hash algoritmo usado para las contraseñas es tan simple como que tenemos un ejemplo, las colisiones múltiples y muy fácil de encontrar. Así que en vez de buscar la contraseña que está tratando de colisiones de hash, contraseñas alternativas que tengan el mismo hash que el verdadero contraseña.
La fuerza de una función de hash requiere que estas colisiones son el mínimo posible y se encontró que era lo más difícil posible.
Bueno, aquí viene la función de base. Explica su funcionamiento general, sus propiedades y usos.
Ya no tienen excusa para preguntar cómo descifrar un hash, creo que ha quedado claro que los hashes no son un método de cifrado, y el resultado no puede obtener el texto de base y no por la fuerza bruta.
Propiedades de una función con respecto a las colisiones de hash.
Las propiedades que deben tener las primitivas hash son:
1. Resistencia a preimagen: Ida función. Como hemos dicho antes, significa que cualquier imagen, es computacionalmente imposible encontrar un mensaje x tal que h (x) = y. Conocido también como esta propiedad es que h es de sentido único.
2. Resistencia 2 preimagen: OWHF: Débil Ida función. Significa que dado x, es computacionalmente imposible encontrar una x 'tal que h (x) = h (x'). Otra forma de conocer esta propiedad es que h es resistente a una colisión suave.
3. Resistencia a la colisión: CRHF: Fuerte Ida función. Significa que es computacionalmente imposible encontrar dos diferentes mensajes x, x ', de modo que h (x) = h (x'). Esta propiedad también se conoce como resistencia fuerte colisión.
Vamos a hacer algunos ejemplos para ver la necesidad de estas propiedades:
Vamos a establecer un escenario de firma digital.
X se adjunta un documento con su firma, que consta de clacular el hash de X, h (X), y, en números, C (h (X)) con la clave privada del remitente o el titular.
Para verificar la integridad de X, el destinatario o la persona en cuestión con la clave pública descifra el propietario C (h (X)) para obtener h (X), las estimaciones iniciales de la nueva h (X), del documento y las compara. Si h (X) es igual a la inicial h (X), es que este nuevo documento no ha sido alterado y que pertenece al firmante.
Si la función no tiene una resintencia al 2 preimagen, C que un atacante podría encontrar un mensaje de X ', de modo que h (X) = h (X), y afirman que el documento no está firmado, pero XX ».
C o imaginar que debe presentar a un tercero para que firmar un documento X, otro documento elaborado Y. Si la función no es resistente a colisiones, C basura pueden agregar información a X e Y (X e Y '), de modo que h (X + X ') = h (Y + Y'). Entonces el signo X es también la firma de Y.
Por último, si (e, n) es la clave pública RSA de A, C puede elegir aleatoriamente un yy calcular z = e mod n, y afirman que es la firma de z, si uno puede encontrar C preimagen tal que x = zh ( x), donde x es importante para A. Esto es evitable si h es resistente a preimagen.
Algoritmo MD5
El algoritmo MD5 realiza las siguientes operaciones:
1. Añadir un poco de relleno:
El mensaje es rellenado o se amplíe de modo que su longitud en bits es congruente a 448 módulo 512. Este debe ser el caso, porque tenemos que reserva 64 bits para añadir la longitud del mensaje en el próximo paso. Por lo tanto, si no llegan a la correspondencia anterior se añade el relleno, que consiste en una bit'1 'seguido por el mayor número bits'0 "según sea necesario.
La razón por la cual un uno seguido de ceros que debe utilizarse sólo cuando esté llena de un valor (por ejemplo, todos los ceros) el proceso se invirtió para eliminar el relleno.
En cualquier caso, siempre que este relleno, pero la longitud del mensaje es coherente y 448 en el módulo 512. Por lo tanto, añadir al menos 1 poco de relleno, y un máximo de 512 bits. Tenga en cuenta la siguiente figura:
2. Adición de representación binaria de longitud del mensaje:
Posteriormente añadió que el mensaje (con relleno hecho) una representación de la longitud del mensaje, antes de ser llenados. Esta representación tendrá una longitud de 64 bits (16 palabras de 32 bits, es decir, dos enteros de 4 bytes cada uno). En el caso de que el mensaje es más que bits, sólo se consideran menos representativo que el de 64 bits, lo que significa que esta representación de la longitud del mensaje se hace en el módulo.
El mensaje tiene ahora un número múltiplo de 512 bits, por lo que será un número entero de palabras de 32 bits (4 bytes de enteros), es decir, 512 / 32 = 16, por lo que se puede concluir que si hay bloques de 512 bits b cada una, que forman el mensaje, el mensaje tendrá palabras de 32 bits de n: n = 16 * b
3. Iniciar MD búfer:
Para calcular el valor de hash o resumen necesita un buffer de 4 palabras de 32 bits (A, B, C, D), pero antes de comenzar el proceso ha sido inicializado con un valor determinado, que establece Rivest:
A = Word 01 23 45 67 67 45 23 01
La palabra B = 89 ab ab cd cd ef 89 ef
Word Fe C = 98 98 dc ba ba dc fe
Palabra D = 76 54 32 10 10 32 54 76
En la primera columna de valores hexadecimales están ordenados de manera que los valores son menos importantes en el primer lugar (por Rivest notación utilizada en la aplicación de este algoritmo), y la segunda más importante son los valores a la izquierda (posición superior en la memoria Intel 80xxx)
¿Por qué estas formas representan los mismos valores deben estar tratando de evitar la confusión, porque según el tipo y la arquitectura de la máquina en la que el algoritmo tiene que trabajar, este será objeto de cambios en estos valores cuando se realiza la aplicación. Esto se debe a las diferentes formas en que los datos se almacenan en la memoria en diferentes arquitecturas (Intel, Sun, Sparc, ...)
MD4 y MD5 son algoritmos diseñados para facilitar su aplicación en las denominadas arquitecturas little-endian. Este formato asume que el byte menos significativo de una palabra se almacena en la posición más baja, y el byte más significativo en el más alto. Es el formato utilizado por los procesadores Intel que integran PC 80xxx casa.
4. Procesar el mensaje en bloques de 512 bits:
Este es el núcleo del algoritmo. Aquí se definen las cuatro funciones que se utilizan en las cuatro rondas que se aplicarán en cada bloque. Véase la siguiente figura:
Estas cuatro funciones como parámetros de entrada son tres palabras de 32 bits cada uno (tres enteros de 4 bytes de longitud) y regresó como una salida. Ellos son:
F (X, Y, Z) = (X e Y) o ((no X) y Z)
G (X, Y, Z) = (X y Z) o (Y y (no Z))
H (X, Y, Z) = X Y Z
I (X, Y, Z) = Y (o X (no Z))
Donde F actúa como un condicional si en la programación: Si x = 1 entonces Y será el 1 de lo contrario Z es 1.
G también funciona como un condicional F: Si Z = 1, entonces X es 1 y es el 1 de otra cosa.
H simplemente realiza la operación o-exclusivo (XOR) de X, Y y Z.
Realizar la operación XOR es 1 si X o Z es 0.
Por otra parte no utiliza la constante MD5 ( 'magia' constantes) que se utilizaron en MD4. En su lugar se utiliza una tabla de 64 elementos construidos a partir de la función dentro trigonométricas. T es el i-ésimo elemento de la tabla, que es igual a la parte entera de 4294967296 veces abs (sin (i)), donde se expresa en radianes. Puesto que hay 16 pasos a realizar en cada una de las cuatro rondas, es decir, 64 operaciones, la idea es utilizar una de la tabla de arriba para cada ronda.
5. Recoger el valor de hash de salida:
El valor de hash de la producción se obtiene a partir de los registros A, B, C y D, donde D es más representativo y el byte menos A.
Ataques
Cumpleaños ataque.
El más conocido ataque (fuerza bruta) a una función de hash es conocido como el "ataque de cumpleaños" y se basa en la siguiente paradoja.
¿Cuál es la cantidad de personas que ponen en una habitación de manera que la probabilidad de que el cumpleaños de uno de ellos es el mismo día que la mía?
Calculamos un n tal que (1 / 365)> 0,5, entonces n> 182.
Sin embargo, sería el número de personas necesarias para cumplir con cualquier de estos dos años el mismo día?
Cada par tiene una probabilidad de 1 / 365, y un grupo de n personas hay n (n-1) / 2 pares diferentes y, a continuación,
(n (n-1) / 2) (1 / 365)> 0,5
Esto es cierto si n> 23, un número sorprendente de menos de 182.
La consecuencia de esta paradoja es que, aunque es muy difícil calcular un x una x 'tal que h (x) = h (x'), es mucho más fácil encontrar dos xyx azar ', de modo que h (x) = h (x ').
Esto en la práctica significa que un hash de n bits de colisión o de 2 ª preimagen débiles una vez cada 2 ^ n, pero producirá una fuerte colisión una vez cada 2 ^ (n / 2).
En el caso de un hash de 64 bits que requieren 2 ^ 64 mensajes de un determinado x para obtener x ', pero suficiente para generar 2 ^ 32 mensajes al azar a aparecer con el mismo hash dos. El primer ataque se llevaría 600.000 años a un equipo para generar un millón de mensajes por segundo, mientras que el segundo requiere sólo unas pocas horas.
Wang Yin-ataque o el ataque chino Yu -
Supongo que muchos habrán leído que en la actualidad hash MD5 y SHA1 funciones se han roto por un grupo de matemáticos chinos que son inútiles y así sucesivamente.
Vamos a tratar de explicar esto para que todos puedan evaluar el grado de perturbación de estas funciones, pero no evaluar la medida en que se ven afectados.
Como hemos visto en el cumpleaños de ataque, para encontrar dos mensajes X y X 'ensayos tienen el mismo SHA-1 (160 bits), por ejemplo, por la fuerza bruta se necesita para generar 2 ^ (160 / 2) los mensajes.
Bueno, este grupo de matemáticos ha descubierto un sistema que permite hacer esto con menos esfuerzo que por la fuerza bruta.
Específicamente para SHA1 puede encontrar una "colisión de cumpleaños" con un esfuerzo equivalente a 2 ^ 69 operaciones hash, en lugar de 2 ^ 80 requeridos por la fuerza bruta.
Como podemos ver, este es un fuerte ataque a las colisiones, pero no contra la colisión de 2 preimagen, que no afecta. Si alguien quiere generar un mensaje x 'que tengan el mismo x SHA1 un mensaje, usted debe seguir para generar 2 ^ 160 para recibir mensajes.
Y aunque el "ataque de cumpleaños" contra SHA1 veces más rápido se convirtió en 2000, sigue siendo del orden de 10.000 veces más difícil para un ataque a una DES, que no es accesible a todo el mundo.
Sin embargo, hay casos en que las consecuencias son importantes.
Imagínese que usted componer un contrato de venta de bienes raíces en la palabra, a la que le adjunto jpg con varias fotografías de la propiedad.
Al mismo tiempo, un género Variante A con las mismas imágenes, pero al cambiar el precio a mi favor.
Es prácticamente imposible que la h (A) = h (A ').
Sin embargo puedo crear múltiples versiones de A y A ', el cambio de bits aleatorios de fotos (que se podría hacer mediante la modificación del texto mediante la adición de espacios, no cambiar las cosas importantes, etc, pero sería muy sucia y los notarios "trampa". Pero cambiar los bits de las imágenes tanto como para perder algo), hasta dos versiones de un mismo hash.
Les presento al comprador de la versión A, de acuerdo con los términos y la firma electrónica. Una variante del cambio por la de A 'y que ya han firmado un contrato de venta con condiciones distintas de la creación.
Si la función que debe utilizarse para la firma es un SHA1 por ejemplo, a través de la triple ataque chino tendrá que generar 2 ^ 69 variantes de A y 2 ^ 69 variantes de A ', que como hemos visto antes, aunque no asequible a cualquier persona, es factible.
Pero si la función de hash MD5 es un por ejemplo, sólo tendrá que generar 2 ^ 32 variantes de A y 2 ^ 32 variantes de A ', que es accesible a cualquier PC.
Multicolision ataque de Joux-Wang.
Si nos fijamos en el funcionamiento del algoritmo MD5, vemos que el mensaje se divide en bloques de 512 bits. El primer bloque es "hash", utilizando como parámetro el vector de inicialización y derivados en otro vector de 128 bits, que sirve como inicio para el siguiente bloque de 512 bits, y así sucesivamente.
Entonces se hace obvio que si no dos bloques A y B, donde A! = B, que cumplan que MD5 (A) = MD5 (B), si añade una "carga" Q y, a continuación, MD5 (A + Q) = MD5 (B + Q).
http://www.codeproject.com/dotnet/HackingMd5.asp.
El desarrollo se muestra aquí como un ejemplo, se basa en una aplicación que se ejecuta en archivos de un formato propietario para su distribución. Tenemos un ejecutable goodexe.exe antes de que sea un formato de distribución. Bin, y un "extractor" que se ejecuta este. Bin.
Devilexe.exe también tiene un ejecutable que se supone que es malware.
Lo que su aplicación se está llevando a un vector A y B tal que MD5 (A) = MD5 (B), genera good.bin haciendo goodexe.exe A + + evilexe.exe, y genera evil.bin por B goodeexe.exe + + evilexe . exe. De esta manera, MD5 (good.bin) = MD5 (evil.bin).
A continuación, el extractor, si busca. Bin es A o B, o evilexe corre goodexe.
De esta manera usted puede colgar en la red good.bin, y más tarde sustituido por evil.bin (previamente renombrado por supuesto).
Desde MD5 es el mismo, nadie duda, y ejecutar un programa separado.
Personalmente no veo ninguna utilidad en este caso, es cómo distribuir un troyano que sólo la fecha de activación de decidir graduarse.
"La historia de Alicia y su jefe"
Otro ejemplo que es más interesante.
Aquí puedes ver dos tarjetas en PostScript diferentes en el mismo contexto en el que MD5 es el mismo para ambos:
http://www.cits.rub.de/MD5Collisions/
En una señal de que una carta de recomendación es ordinario, que están firmando los demás, que es una tarjeta que le da acceso a secretos.
Los creadores de estas letras no dan detalles técnicos acerca de cómo se hace esto, pero dicen que están preparando un documento que lo explica.
Pero no nos gusta esperar, por lo que detalle el procedimiento exclusivamente.
Si publicar ambos. Ps, vemos que el código es algo como esto:
Código: [Seleccionar]
%! PS-Adobe-1.0
%% BoundingBox: 0 0 612 792
(caracteres raros) (caracteres raros) eq (/ Times-Roman findfont 20 scalefont setfont
300 700 moveto (Julius. César) muestran
.
.
) (/ Times-Roman findfont 20 scalefont setfont
300 700 moveto (Julius. César) muestran
.
.
siotro)
showpage
Tal vez algunos despidos, porque el código es en notación polaca inversa, pero si nos fijamos en la línea de caracteres raros, lo que está haciendo es comparar lo que hay dentro de los primeros paréntesis a lo que hay dentro de la segunda.
Devuelve True si son iguales, y se ejecuta el primer bloque de código (), que es correspondiente a la carta de recomendación, y si usted no es el mismo código se ejecuta por el siguiente bloque (), que es la carta que autoriza a .
Ahora abra. Ps con un editor hexadecimal y nos fijamos en la estructura diviéndola en bloques de 64 bytes.
¿Por qué 64 bytes? Porque como hemos dicho antes, el algoritmo de hash MD5 es de 512 a 512 bits (64 bytes).
Así vemos que el primer bloque de 64 bytes es común en ambos. Ps, como es la cabecera que ha sido retocada convenientemente para llenar exactamente eso.
Bueno, y también vemos que los dos bloques de 64 bytes corresponden a los caracteres de la primera paréntesis.
Estos dos bloques se diferencian unos de otros ps.
Un bloque de 4, todo es común a ambos. Ps.
Ahora todo está claro.
Cab cabecera han montado para llenar 64 bytes. Entonces han creado dos versiones A y B, mediante la adición de 128 bytes al azar en busca de una colisión que MD5 (Cab + A) = MD5 (Cab + B).
En este punto, al igual que el resto del código es el mismo para ambos documentos, de ambos documentos compartir hash, por lo que están buscando si el documento tiene A o B para mostrar una carta o la otra.
Estado actual de la función de hash.
MD4 función está totalmente rota y fuera de impresión, de hecho existen algoritmos que se encuentran las colisiones en pocos segundos.
Para usar MD5 deben tomar ciertas precauciones, pero cualquiera que haya leído este documento es capaz de tomar. Es mejor no usarlo, pero si no tenemos otra opción, pero al mismo tiempo el uso seguro con cuidado. Por ejemplo no usar MD5 si todo lo que escribe firmeis el documento a firmar es una de las partes interesadas, o cambiar cualquier cosa antes de firmar el documento o guardar una copia, etc.
Para SHA1, yo no diría como se dice en muchos lugares que el edificio está en llamas y perdimos. La única cosa es que suene la alarma, a pesar de que no se ve el humo, y es prudente para ir a la salida de emergencia, pero no hay necesidad de ejecutar o pánico. Pero tampoco hay que quedarse en el sitio, porque la criptoanalíticas ataques cada día mejoran, y cada uno será más fácil y más rápido.
La solución que se está dando a este problema es aumentar el tamaño de los hashes. PGP utiliza y SHA256, etc, pero es sólo un parche. Estos algoritmos son mono, y dando más bits sólo aumenta el esfuerzo para encontrar colisiones. Sin embargo, de acuerdo para avanzar en los métodos de criptoanálisis, y la potencia de cálculo, Irán es el tiempo de corte, y nosotros en ellos.
El punto más crítico es legal. Todo lo que se firma con un certificado del DNI electrónico o el futuro, tiene el mismo valor que una firma manuscrita.
La consideración jurídica se basa entre otras cosas, en el algoritmo de la firma funciona como debe ser y que el resultado del hash es único en el texto firmado.
Si un sistema no puede garantizar que el documento es tal que usted firmó, y no hay posibilidad de que usted tiene el cambiazo a otro documento que tenga el mismo hash, todos los documentos firmados por que la aplicación no será legal. Si usted tiene fotos de tráfico de Australia sin ir más lejos:
http://www.hispasec.com/unaaldia/2489
Solución? Muy simple. Uso de doble hash.
La gente no es dada la importancia del problema de las colisiones, y si lo es, por ejemplo, PHP, así no se conforman.
Si usted firma para algo más que codificar el MD5 o SHA1 o SHA256 el documento está codificada por una concatenación de MD5 + SHA1 ejemplo, un choque que tiene que mirar dos veces para obtener un documento alternativo, que actualmente es imposible.
Si tiene que utilizar la firma electrónica a los documentos, y será firmado utilizando MD5, por ejemplo, la adición de una huella dactilar de estilo campamento con SHA1 hash del documento.
No hay comentarios:
Publicar un comentario