어떻게 MD5 해쉬값은 되돌릴 수 없?

https://stackoverflow.com/questions/330207

11-07-2019
|

문제

하나의 개념이 나는 항상에 대해 궁금은 사용하여 암호화 해시 기능과 값입니다.나는 이러한 기능을 생성할 수 있는 해시된 값은 독특하고 거의 반대하는 것은 불가능하지만,여기에 무엇이 나는 항상 궁금:

는 경우에는 서버에서 PHP 나는 생산:

md5("stackoverflow.com") = "d0cc85b26f2ceb8714b978e07def4f6e"

을 실행할 때에는 동일한 문자열을 통해 기능 MD5,당신은 같은 결과를 얻을 당신의 PHP 설치합니다.프로세스가 사용 중 일부를 생산하는 값에서부터 시작 값입니다.

지 않는 이가 있다는 것을 의미하는 몇 가지 방법이 해체 무슨 일이 일어나고 있는 역 hash value?

그것이 무엇입에 관한 이러한 기능을하는 결과 문자열을 불가능하게 되?

해결책

입력 재료는 출력의 길이가 항상 128 비트 인 무한 길이 일 수 있습니다. 이는 무한한 수의 입력 문자열이 동일한 출력을 생성한다는 것을 의미합니다.

임의의 숫자를 선택하고 2로 나누면 나머지를 기록하면 각각 0 또는 1 (0) 또는 1 홀수를 얻을 수 있습니다. 0 또는 1을 가져 와서 원래 번호를 얻을 수 있습니까?

다른 팁

MD5와 같은 HASH 기능이 가역적이라면 데이터 압축 알고리즘의 역사에서 유역 이벤트 였을 것입니다! MD5가 가역적이라면 임의의 크기의 임의의 데이터 덩어리가 정보 손실없이 128 비트로 표현 될 수 있음을 쉽게 알 수 있습니다. 따라서 원본 메시지의 크기에 관계없이 원본 메시지를 128 비트 숫자에서 재구성 할 수 있었을 것입니다.

여기서 가장 귀중한 답변이 강조하는 것과는 달리 비 혐의 (즉, 동일한 값에 대한 몇 가지 문자열 해싱이 있음) 큰 (잠재적으로 무한) 입력 크기와 고정 출력 크기 사이의 차이로 인해 암호화 해시 함수가 있습니다. 중요한 점이 아닙니다 - 실제로, 우리는 이러한 충돌이 가능한 한 거의 발생하지 않는 해시 기능을 선호합니다.

이 기능을 고려하십시오 (PHP 표기법에서 질문으로) :

function simple_hash($input) {
     return bin2hex(substr(str_pad($input, 16), 0, 16));
}

문자열이 너무 짧은 경우 일부 공백이 추가 된 다음 문자열의 첫 16 바이트를 가져간 다음 16 진수로 인코딩합니다. MD5 해시와 동일한 출력 크기 (32 16 진 문자 또는 BIN2HEX 부품을 생략하면 16 바이트)가 있습니다.

print simple_hash("stackoverflow.com");

이것은 출력됩니다 :

737461636b6f766572666c6f772e636f6d

이 기능은 또한 MD5에 대한 Cody의 답변에 의해 강조된 것과 동일한 비 주입 속성을 가지고 있습니다. 우리는 컴퓨터에 맞는 한 크기의 문자열을 전달할 수 있으며 32 개의 16 진로 만 출력합니다. 물론 그것은 주입 할 수 없습니다.

그러나이 경우 동일한 해시에 맵핑하는 문자열을 찾는 것은 사소한 일입니다 (그냥 적용하십시오. hex2bin 당신의 해시에서, 당신은 그것을 가지고 있습니다). 원래 문자열에 길이 16 (예제)이 있으면이 원래 문자열도 얻을 수 있습니다. 입력의 길이가 상당히 짧았다는 것을 알고 있더라도 MD5에는 이런 종류의 일이 불가능합니다 (예 : 무차별 적 공격이 일치 할 때까지 가능한 모든 입력을 시도하는 것 외에는).

암호화 해시 함수의 중요한 가정은 다음과 같습니다.

주어진 해시를 생성하는 스트링을 찾기가 어렵습니다 (Preimage Resistance)
주어진 문자열과 동일한 해시를 생성하는 다른 스트링을 찾기가 어렵습니다 (두 번째 프리 이미지 저항).
동일한 해시가있는 한 쌍의 문자열을 찾기가 어렵습니다 (충돌 저항)

분명히 내 simple_hash 기능은 이러한 조건 중 어느 것도 충족하지 않습니다. (실제로, 입력 공간을 "16 바이트 문자열"으로 제한하면 내 기능은 주사가되므로 2 차 미지 저항성 및 충돌 저항성입니다.)

이제 MD5에 대한 충돌 공격이 존재합니다 (예 : 동일한 해시가있는 동일한 접두사가있는 동일한 접두사가있는 경우에도 한 쌍의 문자열을 생성 할 수 있습니다. 중요한 것은 MD5입니다. 아직 사전이 이미지 공격은 없지만 공격이 더 좋아질 것입니다.

실제 질문에 답하기 위해 :

결과 문자열을 되돌릴 수없는 이러한 기능은 무엇입니까?

MD5 (및 기타 해시 기능이 Merkle-Damgard Construction에서 제작하는 것은 효과적으로 수행하는 일은 메시지를 키로 사용하여 암호화 알고리즘을 적용하고 결과 암호문을 해시로 사용하여 "일반 텍스트"로 고정 된 값을 적용하는 것입니다. (그 전에 입력은 패딩 및 블록으로 분할되며,이 블록 각각은 이전 블록의 출력을 암호화하는 데 사용되며, 입력과 함께 리버스 계산을 방지합니다.)

현대의 암호화 알고리즘 (해시 함수에 사용 된 것 포함)은 일반 텍스트와 암호 텍스트 (또는 적대가 그중 하나를 선택할 때조차도)가 주어지면 키를 복구하기가 어렵게 만들기 위해 만들어집니다. 각 출력 비트가 각 키 비트 (여러 번)와 각 입력 비트에 의해 결정되는 방식으로 많은 비트 셔플 작업을 수행함으로써 일반적으로이를 수행합니다. 이렇게하면 전체 키와 입력 또는 출력을 알고 있다면 내부에서 발생하는 일만 쉽게 되돌릴 수 있습니다.

MD5와 유사한 해시 함수 및 프리이 이미지 공격 (단일 블록 해시 스트링, 물건을 더 쉽게 만들 수 있음)의 경우 암호화 기능의 입력 및 출력 만 있지만 키는 아닙니다 (이것은 찾고있는 것입니다).

Cody Brocious의 대답은 옳은 일입니다. 엄격히 말하면, 많은 문자열이 동일한 해시에 매핑되기 때문에 해시 함수를 "반전"할 수 없습니다. 그러나 그 어느 쪽이든 발견하십시오 하나 주어진 해시에 매핑되는 문자열 또는 찾기 둘 같은 해시에 매핑되는 줄 (즉 충돌), cryptanalyst의 주요 돌파구가 될 것입니다. 이 두 가지 문제의 큰 어려움은 좋은 해시 기능이 암호화에 유용한 이유입니다.

MD5는 고유 한 해시 값을 생성하지 않습니다. MD5의 목표는 소스에 대한 사소한 변경에 따라 크게 변화하는 값을 신속하게 생성하는 것입니다.

예,

"hello" -> "1ab53"
"Hello" -> "993LB"
"ZR#!RELSIEKF" -> "1ab53"

(분명히 그것은 실제 MD5 암호화가 아닙니다)

대부분의 해시 (전부가 아닌 경우)도 비 유니크입니다. 오히려, 그들은 독특합니다 충분한, 충돌은 매우 불가능하지만 여전히 가능합니다.

좋은 생각하는 방법은 해시 알고리즘을 생각하는 것입의 크기를 조정의 이미지를 포토샵에서...말이 있는 이미지 5000x5000 픽셀이고 당신은 그런 다음 크기를 조정하 32x32.당신은 여전히 대표는 원본 이미지의 그러나 그것은 훨씬 작고 효과적으로"throw away"특정 부분의 이미지 데이터에 맞게 작은 크기입니다.그래서 만약 당신의 크기를 조정하는 32x32 이미지 백업하 5000x5000 모든 당신을 얻을 것이 흐릿한 엉망입니다.그러나기 때문에 32x32 이미지지 않는 큰 것 이론적으로 생각할 수 있는 또 다른 이미지가 될 수 있는 소형화하여 정확한 생산한 동일한다.

는 비유이지만 그것을 이해하는 데 도움이 무엇을 해시입니다.

해시 충돌은 당신이 생각하는 것보다 훨씬 더 가능성이 높습니다. 살펴보십시오 생일 역설 그것이 왜 그 이유를 더 잘 이해하기 위해.

가능한 입력 파일의 수가 128 비트 출력 수보다 크기 때문에 MD5 해시를 가능한 각각에 고유하게 할당하는 것은 불가능합니다.

암호화 해시 기능은 데이터 무결성 또는 디지털 서명을 확인하는 데 사용됩니다 (해시는 효율성을 위해 서명). 따라서 원본 문서를 변경하면 원래 해시가 변경된 문서와 일치하지 않음을 의미합니다.

이러한 기준은 때때로 사용됩니다.

프리 이미지 저항 : 주어진 해시 함수 및 주어진 해시의 경우 해시에 주어진 해시가있는 입력을 찾기가 어려워야합니다.
두 번째 사전 이미지 저항 : 주어진 해시 함수 및 입력의 경우 동일한 해시로 두 번째, 다른 입력을 찾기가 어려워 야합니다.
충돌 저항 : 주어진 기능이있는 경우 동일한 해시로 두 가지 다른 입력을 찾기가 어려워 야합니다.

이러한 기준은 주어진 해시와 일치하는 문서를 찾기가 어렵도록 선택되며, 그렇지 않으면 해시와 일치하는 원본으로 원본을 교체하여 문서를 위조 할 수 있습니다. (교체가 횡설수설이더라도 원본의 단순한 교체로 인해 혼란이 발생할 수 있습니다.)

숫자 3은 숫자 2를 의미합니다.

특히 MD5는 결함이있는 것으로 나타났습니다.MD5 및 기타 해시 기능을 중단하는 방법.

그러나 이것은 무지개 테이블이 시작되는 곳입니다. 기본적으로 그것은 별도로 해시 된 많은 양의 값 일 뿐이며 결과는 디스크에 저장됩니다. 그런 다음 역전 비트는 매우 큰 테이블에서 조회하는 "그냥"입니다.

분명히 이것은 가능한 모든 입력 값의 하위 집합에 대해서만 가능하지만 입력 값의 경계를 알고 있다면 계산할 수 있습니다.

중국 과학자는 두 개의 다른 문자열 사이에 충돌하기 위해 "선택된 prefix 충돌"이라는 방법을 발견했습니다.

예는 다음과 같습니다. http://www.win.tue.nl/hashclash/fastcoll_v1.0.5.exe.zip
소스 코드 : http://www.win.tue.nl/hashclash/fastcoll_v1.0.5_source.zip

대부분의 말과 같이 MD5는 가변 길이 데이터 스트림이 고정 길이의 데이터 덩어리로 해시되도록 설계되었으므로 많은 입력 데이터 스트림에서 단일 해시가 공유됩니다.

그러나 체크섬에서 원래 데이터를 찾아야한다면, 예를 들어 비밀번호 해시가 있고 원래 비밀번호를 찾아야하는 경우, 종종 구글 (또는 선호하는 검색 자) 만 해시보다 더 빠릅니다. 무차별 한 힘보다 대답. 이 방법을 사용하여 몇 가지 암호를 성공적으로 발견했습니다.

가장 투표 된 모든 답변이 무엇을 의미하는지 이해하는 가장 좋은 방법은 실제로 MD5 알고리즘을 되돌리려 고하는 것입니다. 나는 그것을 되돌리려 고했던 것을 기억한다 md5crypt 몇 년 전 알고리즘은 원래 메시지를 복구하지 않고 분명히 불가능하기 때문에 원래 메시지를 복구하지 않고 원래 해시와 동일한 해시를 생성하는 메시지를 생성하는 것입니다. 이것은 적어도 이론적으로 사용자를 저장 한 Linux 장치에 로그인하는 방법을 제공합니다. 두 메시지 모두 동일한 결과 해시가 있으므로 시스템은 내 비밀번호 (원래 해시에서 생성)를 유효한 것으로 인식합니다. 전혀 작동하지 않았습니다. 몇 주 후, 내가 정확하게 기억한다면 소금 초기 메시지에서 나를 죽였다. 나는 유효한 초기 메시지뿐만 아니라 절대 할 수 없었던 소금에 절인 유효한 초기 메시지를 제작해야했습니다. 그러나이 실험에서 얻은 지식은 좋았습니다.

정의에 따르면 해시 (cryptographic hash) 기능 : 반전 할 수 없어야하며 충돌이 없어야합니다 (최소한 불가능).

질문 : 그것은 한 가지 방법 해시입니다. 입력 (길이에 관계없이)은 고정 크기 출력을 생성합니다 (Algo (MD5의 512 비트 경계)를 기준으로 패딩). 정보는 압축 (손실)이며 실제로 역 변환에서 생성 할 수 없습니다.

MD5에 대한 추가 정보 : 충돌에 취약합니다. 최근 에이 기사를 살펴 보았습니다.http://www.win.tue.nl/hashclash/nostradamus/

Crypto Hash 구현 (MD5 및 SHA)의 소스 코드를 Opens Mozilla Code에서 찾을 수 있습니다. (FreeBl Library).

이제 MD5 해시 또는 해당 물질에 대한 다른 해시는 가능한 모든 문자열에 대해 미리 계산되고 쉽게 접근 할 수 있도록 저장됩니다. 이론적으로 MD5는 가역적이지 않지만 이러한 데이터베이스를 사용하면 특정 해시 값을 초래 한 텍스트를 찾을 수 있습니다.

예를 들어 다음 해시 코드를 사용해보십시오 http://gdataonline.com/seekhash.php 해시를 계산하는 데 사용한 텍스트를 찾으려면

aea23489ce3aa9b6406ebb28e0cda430

f (x) = 1은 돌이킬 수 없습니다. 해시 기능은 돌이킬 수 없습니다.

이것은 실제로입니다 필수의 그들이 누군가가 해시 데이터의 부패하지 않은 사본을 가지고 있는지 여부를 결정하는 기능을 충족시키기 위해. 이것은 무차별의 힘 공격에 대한 감수성을 가져다줍니다. 요즘에는 특히 MD5에 대해 매우 강력합니다.

또한 수학적 지식을 가지고 있지만 암호화하는 지식이 거의없는 사람들 사이에는 여기와 다른 곳에서 혼란이 있습니다. 여러 암호는 단순히 키 스트림으로 데이터를 xor하므로 암호 텍스트가 키 스트림을 사용할 수 있었기 때문에 해당 길이의 모든 일반 텍스트에 해당한다고 말할 수 있습니다.

그러나 이것은 씨앗에서 생성 된 합리적인 일반 텍스트를 무시합니다. password 씨앗에 의해 생성 된 다른 것보다 훨씬 더 가능성이 높습니다. Wsg5Nm^bkI4EgxUOhpAjTmTjO0F!VkWvysS6EEMsIJiTZcvsh@WI$IH$TYqiWvK!%&Ue&nk55ak%BX%9!NnG%32ftud%YkBO$U6o 두 번째가 가능성이 있다고 주장하는 사람은 누구나 웃을 것입니다.

같은 방식으로 두 가지 잠재적 비밀번호를 결정하려는 경우 password 그리고 Wsg5Nm^bkI4EgxUO, 일부 수학자들이 당신이 믿는 것만 큼 어렵지 않습니다.

나는 모든 다양한 주장을 좋아합니다. 해시 값의 실제 값은 단순히 암호와 같은 문자열에 대한 인간이 읽을 수없는 자리 표시자를 제공하는 것이 분명합니다. 구체적인 보안 이점이 없습니다. 공격자가 해시 암호로 테이블에 액세스했다고 가정하면 다음과 같습니다.

자신의 선택의 비밀번호를 해시하고 테이블에 대한 쓰기/편집이있는 경우 암호 테이블 내부에 결과를 배치하십시오.
공통 비밀번호의 해시 값을 생성하고 비밀번호 테이블에서 유사한 해시 값의 존재를 테스트하십시오.

이 경우 약한 비밀번호는 해시된다는 사실에 의해 보호 될 수 없습니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow