동일한 SHA1 해시를 얻을 수 있습니까?

동일한 SHA1 해시를 얻을 수 있습니까?

---

이 질문에 이미 답변이 있습니다.

• SHA1 충돌 확률 3 답변

두 개의 다른 문자열 S1과 S2 (S1! = S2)가 주어지면 다음과 같은 것이 가능합니다.

SHA1(S1) == SHA1(S2)

사실이다?

1. 그렇다면-어떤 확률로?
2. 그렇지 않다면-왜 안됩니까?
3. 중복을 얻을 확률이 0 인 입력 문자열의 길이에 상한이 있습니까? 또는 SHA1 (따라서 중복 가능성)의 계산은 문자열 길이와 무관합니까?

내가 달성하려는 목표는 민감한 ID 문자열 (부모 ID와 같은 다른 필드와 함께 결합 될 수 있음)을 해시하여 해시 값을 ID로 대신 사용할 수 있도록하는 것입니다 (예 : 데이터베이스).

예:

Resource ID: X123
Parent ID: P123

클라이언트가 "X123-P123"을 볼 수 있도록 내 리소스 식별의 특성을 노출하고 싶지 않습니다.

대신 새 열 해시 ( "X123-P123")를 만들고 싶습니다. AAAZZZ라고 가정 해 보겠습니다. 그런 다음 클라이언트는 ID AAAZZZ로 리소스를 요청할 수 있으며 내부 ID 등에 대해 알 수 없습니다.

---

설명하는 것을 충돌 이라고합니다 . SHA-1은 서로 다른 출력을 생성 할 수있는 더 많은 개별 메시지를 입력으로 받아들이 기 때문에 충돌이 반드시 존재합니다 (SHA-1은 최대 2 ^ 64 비트의 비트 문자열을 먹을 수 있지만 160 비트 만 출력합니다. 따라서 적어도 하나의 출력 값이 여러 번 표시되어야 함). 이 관찰은 함수가 "좋은"해시 함수인지 여부에 관계없이 입력보다 작은 출력을 가진 모든 함수에 유효합니다.

가정하면 (기본적으로 출력 반환되면 그 유일한 제한, 임의의 값을 반환하는 개념 개체 「랜덤 신탁 "과 같은 SHA-1 동작합니다 절 입력에 m , 항상 그 후에 반환해야합니다 V 입력에 m을 ), 다음 두 개의 고유 한 문자열 S1 및 S2에 대한 충돌 확률은 2 ^ (-160)이어야합니다. 여전히 임의의 오라클처럼 동작하는 SHA-1 가정하에 많은 입력 문자열을 수집하면 약 2 ^ 80 개의 문자열을 수집 한 후 충돌을 관찰하기 시작합니다.

(2 ^ 80이 아니라 2 ^ 160이 아닙니다. 왜냐하면 2 ^ 80 문자열을 사용하면 약 2 ^ 159 쌍의 문자열을 만들 수 있기 때문입니다. 이것은 충돌에 적용될 때 대부분의 사람들에게 놀라움을주기 때문에 종종 "생일 역설"이라고 불립니다. 생일에. 주제에 대한 Wikipedia 페이지 를 참조하십시오 .)

이제 우리는 SHA-1이 실제로 무작위 오라클처럼 행동 하지 않는다고 강력하게 의심합니다 . 왜냐하면 생일 패러독스 접근법이 무작위 오라클에 대한 최적의 충돌 검색 알고리즘이기 때문입니다. 그러나 약 2 ^ 63 단계에서 충돌을 찾아야하는 공개 된 공격이 있으므로 생일 패러독스 알고리즘보다 2 ^ 17 = 131072 배 더 빠릅니다. 이러한 공격은 진정한 임의의 오라클에서 수행 할 수 없습니다. 이 공격은 실제로 완료되지 않았으며 이론적으로 남아 있습니다 (일부 사람들 은 시도했지만 충분한 CPU 성능을 찾을 수 없음 ) ( 업데이트 : 2017 년 초부터 누군가 가 SHA-1 충돌을 계산했습니다.위에서 언급 한 방법으로 예측 한대로 정확히 작동했습니다.) 그러나 이론은 타당 해 보이며 실제로 SHA-1은 임의의 오라클이 아닌 것 같습니다. 따라서 충돌 확률에 관해서는 모든 베팅이 꺼져 있습니다.

세 번째 질문에 관해서는 n 비트 출력 을 가진 함수의 경우 2 ^ n 개 이상의 개별 메시지를 입력 할 수있는 경우, 즉 최대 입력 메시지 길이가 n 보다 큰 경우 반드시 충돌이 발생합니다 . 경계 m 이 n 보다 작 으면 대답이 쉽지 않습니다. 함수가 임의의 오라클로 작동하면 충돌의 존재 확률은 m = n / 2 주위의 가파른 컷오프가 아니라 선형이 아닌 m으로 낮아집니다 . 이것은 생일 역설과 같은 분석입니다. SHA-1을 사용하면 m <80 이면 충돌이 없을 가능성이있는 반면 m> 80최소한 한 번의 충돌이있을 가능성이 높습니다 ( m> 160 이면 확실성이 됨).

"충돌이 있습니다"와 "충돌을 찾았습니다"사이에는 차이가 있습니다. 충돌 이 존재 해야하는 경우에도 시도 할 때마다 2 ^ (-160) 확률이 있습니다. 이전 단락이 의미하는 바는 (개념적으로) 2 ^ 160 쌍의 문자열을 시도 할 수 없다면, 예를 들어 80 비트 미만의 문자열로 제한하기 때문에 그러한 확률은 의미가 없다는 것입니다.

---

네, 비둘기 구멍 원리 때문에 가능합니다 .

대부분의 해시 (또한 sha1)는 출력 길이가 고정 된 반면 입력은 임의의 크기입니다. 그래서 충분히 오래 시도하면 찾을 수 있습니다.

그러나 암호화 해시 함수 (예 : sha-family, md-family 등)는 이러한 충돌을 최소화하도록 설계되었습니다. 알려진 최선의 공격은 충돌을 찾기 위해 2 ^ 63 번의 시도가 필요하므로 실제로는 0 인 2 ^ (-63)입니다.

---

gitSHA1 해시를 ID로 사용 하며 2014 년 에도 알려진 SHA1 충돌은 없습니다. 분명히 SHA1 알고리즘은 마술입니다. 지금 쯤이면 발견되었을 것 같은 길이의 문자열에 대해서는 충돌이 존재하지 않는 것이 좋은 방법이라고 생각합니다. 그러나 마법을 신뢰하지 않고 베팅 맨이 아니라면 임의의 문자열을 생성하여 DB의 ID와 연결할 수 있습니다. 그러나 SHA1 해시를 사용하고 충돌을 가장 먼저 발견 한 경우, 해당 시점에 임의의 문자열을 사용하도록 시스템을 변경하여 기존 ID에 대한 "무작위"문자열로 SHA1 해시를 유지할 수 있습니다.

---

해싱 함수에서 충돌은 거의 항상 가능합니다. 현재까지 SHA1은 예측할 수없는 충돌을 생성하는 데있어 매우 안전했습니다. 위험은 충돌을 예측할 수있을 때 동일한 해시 출력을 생성하기 위해 원래 해시 입력을 알 필요가 없다는 것입니다.

예를 들어, MD5에 대한 공격은 Security Now 팟 캐스트 에피소드 179에서 예를 들어 작년에 SSL 서버 인증서 서명에 대해 이루어졌습니다 . 이로 인해 정교한 공격자가 악성 웹 사이트에 대한 가짜 SSL 서버 인증서를 생성 할 수 있었으며 이는 실제적인 것으로 보입니다. . 이러한 이유로 MD5 서명 인증서를 구입하지 않는 것이 좋습니다.

---

당신이 말하는 것을 충돌이라고합니다. 다음은 SHA1 충돌에 대한 기사입니다. http://www.rsa.com/rsalabs/node.asp?id=2927

편집 : 그래서 다른 응답자가 비둘기 구멍 원칙 LOL을 언급하는 것으로 저를 때렸지만 이것이 비둘기 구멍 원칙이라고 부르는 이유입니다. 왜냐하면 캐리어 비둘기가 둥지를 틀기 위해 일부 구멍이 있지만 구멍보다 비둘기가 더 많기 때문입니다. , 그러면 일부 비둘기 (입력 값)는 구멍 (출력 값)을 공유해야합니다.

참고 URL : https://stackoverflow.com/questions/2479348/is-it-possible-to-get-identical-sha1-hash