제가 항상 궁금해했던 한 가지 개념은 암호화 해시 함수와 값의 사용입니다. 이러한 함수가 고유하고 사실상 되돌릴 수없는 해시 값을 생성 할 수 있다는 것을 이해합니다.하지만 여기에 항상 궁금했던 것이 있습니다.
내 서버에서 PHP에서 다음을 생성합니다.
md5("stackoverflow.com") = "d0cc85b26f2ceb8714b978e07def4f6e"
MD5 함수를 통해 동일한 문자열을 실행하면 PHP 설치에서 동일한 결과를 얻을 수 있습니다. 일부 시작 값에서 일부 값을 생성하는 데 프로세스가 사용됩니다.
이것은 무슨 일이 일어나고 있는지를 분해하고 해시 값을 역전시킬 수있는 방법이 있다는 것을 의미하지 않습니까?
결과 문자열을 다시 추적 할 수 없게 만드는 이러한 함수는 무엇입니까?
답변
The input material can be an infinite length, where the output is always 128 bits long. This means that an infinite number of input strings will generate the same output.
If you pick a random number and divide it by 2 but only write down the remainder, you’ll get either a 0 or 1 — even or odd, respectively. Is it possible to take that 0 or 1 and get the original number?
답변
If hash functions such as MD5 were reversible then it would have been a watershed event in the history of data compression algorithms! Its easy to see that if MD5 were reversible then arbitrary chunks of data of arbitrary size could be represented by a mere 128 bits without any loss of information. Thus you would have been able to reconstruct the original message from a 128 bit number regardless of the size of the original message.
답변
Contrary to what the most upvoted answers here emphasize, the non-injectivity (i.e. that there are several strings hashing to the same value) of a cryptographic hash function caused by the difference between large (potentially infinite) input size and fixed output size is not the important point – actually, we prefer hash functions where those collisions happen as seldom as possible.
Consider this function (in PHP notation, as the question):
function simple_hash($input) {
return bin2hex(substr(str_pad($input, 16), 0, 16));
}
This appends some spaces, if the string is too short, and then takes the first 16 bytes of the string, then encodes it as hexadecimal. It has the same output size as an MD5 hash (32 hexadecimal characters, or 16 bytes if we omit the bin2hex part).
print simple_hash("stackoverflow.com");
This will output:
737461636b6f766572666c6f772e636f6d
This function also has the same non-injectivity property as highlighted by Cody’s answer for MD5: We can pass in strings of any size (as long as they fit into our computer), and it will output only 32 hex-digits. Of course it can’t be injective.
But in this case, it is trivial to find a string which maps to the same hash (just apply hex2bin on your hash, and you have it). If your original string had the length 16 (as our example), you even will get this original string. Nothing of this kind should be possible for MD5, even if you know the length of the input was quite short (other than by trying all possible inputs until we find one that matches, e.g. a brute-force attack).
The important assumptions for a cryptographic hash function are:
- it is hard to find any string producing a given hash (preimage resistance)
- it is hard to find any different string producing the same hash as a given string (second preimage resistance)
- 동일한 해시 (충돌 저항)를 가진 문자열 쌍을 찾기가 어렵습니다.
분명히 내 simple_hash기능은 이러한 조건을 충족하지 않습니다. (사실, 입력 공간을 “16 바이트 문자열”로 제한하면 내 함수가 주입 형이되어 2 차 이미지 및 충돌 방지가 입증 될 수 있습니다.)
이제 MD5에 대한 충돌 공격이 존재합니다 (예 : 동일한 접두사를 사용하여 동일한 해시를 사용하고 상당한 작업을 수행하지만 불가능하지는 않은 작업으로도 문자열 쌍을 생성 할 수 있음). 따라서 사용하지 않아야합니다. 중요한 모든 것을위한 MD5. 아직 사전 이미지 공격은 없지만 공격은 더 나아질 것입니다.
실제 질문에 답하려면 :
결과 문자열을 다시 추적 할 수 없게 만드는 함수는 무엇입니까?
MD5 (및 Merkle-Damgard 구조에 구축 된 기타 해시 함수)가 효과적으로 수행하는 작업은 결과 암호문을 해시로 사용하여 메시지를 키로, 고정 값을 “일반 텍스트”로 사용하여 암호화 알고리즘을 적용하는 것입니다. (그 전에는 입력이 패딩되고 블록으로 분할되며,이 각 블록은 이전 블록의 출력을 암호화하는 데 사용되며, 역 계산을 방지하기 위해 입력과 XOR 처리됩니다.)
최신 암호화 알고리즘 (해시 함수에 사용되는 알고리즘 포함)은 일반 텍스트와 암호문 (또는 공격자가 둘 중 하나를 선택하는 경우에도)이 주어 지더라도 키를 복구하기 어렵게 만드는 방식으로 만들어졌습니다. 일반적으로 각 출력 비트가 각 키 비트 (여러 번) 및 각 입력 비트에 의해 결정되는 방식으로 많은 비트 셔플 링 작업을 수행합니다. 이렇게하면 전체 키와 입력 또는 출력을 알고있는 경우에만 내부에서 일어나는 일을 쉽게 되돌아 갈 수 있습니다.
MD5와 같은 해시 함수 및 사전 이미지 공격 (일을 쉽게하기 위해 단일 블록 해시 문자열 사용)의 경우 암호화 함수의 입력 및 출력 만 있고 키는 없습니다 (찾고있는 것입니다).
답변
Cody Brocious’s answer is the right one. Strictly speaking, you cannot “invert” a hash function because many strings are mapped to the same hash. Notice, however, that either finding one string that gets mapped to a given hash, or finding two strings that get mapped to the same hash (i.e. a collision), would be major breakthroughs for a cryptanalyst. The great difficulty of both these problems is the reason why good hash functions are useful in cryptography.
답변
MD5 does not create a unique hash value; the goal of MD5 is to quickly produce a value that changes significantly based on a minor change to the source.
E.g.,
"hello" -> "1ab53"
"Hello" -> "993LB"
"ZR#!RELSIEKF" -> "1ab53"
(Obviously that’s not actual MD5 encryption)
Most hashes (if not all) are also non-unique; rather, they’re unique enough, so a collision is highly improbable, but still possible.
답변
해시 알고리즘을 생각하는 좋은 방법은 Photoshop에서 이미지 크기를 조정하는 것입니다. 현재 가지고있는 것은 여전히 원본 이미지의 표현이지만 훨씬 더 작고 이미지 데이터의 특정 부분을 효과적으로 “버려서”더 작은 크기에 맞 춥니 다. 따라서 32×32 이미지의 크기를 5000×5000으로 다시 조정하면 흐릿한 엉망이됩니다. 그러나 32×32 이미지는 그다지 크지 않기 때문에 이론적으로는 정확히 동일한 픽셀을 생성하기 위해 다른 이미지를 축소 할 수 있습니다.
이는 비유 일 뿐이지 만 해시가 수행하는 작업을 이해하는 데 도움이됩니다.
답변
A hash collision is much more likely than you would think. Take a look at the birthday paradox to get a greater understanding of why that is.
