>
내 목표는 수정 된 해시 함수의 해시 충돌을 찾는 것입니다. 수정 된 해시가 SHA-1의 첫 36 비트 만 출력한다고 가정합니다. 아시다시피 SHA-1은 160 비트 해시 값이므로 비교를 위해 40 자 중 9자를 출력하면됩니다.

프로그램을 시작하는 방법은 문자열을 해싱하는 것입니다 (SHA-1 알고리즘이 실행 중이고 이름을 sha1로 지정합니다. 또한 SHA-1 알고리즘의 출력이 올바른지 확인했습니다).

먼저, 첫 번째 36 비트 SHA-1 만 필요하기 때문에 2 개의 문자열을 하드 코딩하고 40 자 중 9자를 추출합니다. 아래 함수는 기본적으로 충돌이 발견되면 true를, 충돌이 발견되지 않으면 false를 반환합니다.

public static boolean findCollision(int x1, int x2) {
    String message1 = "I tried " + x1 + " iteration to find a collision";
    String message2 = "I tried " + x2 + " iteration to find a collision";       

    //hashing my string and extracting 9 characters
    String message_hash1 = sha1(message1);
    String message_hash2 = sha1(message2);
    String modified_hash1 = message_hash1.substring(0, 9);
    String modified_hash2 = message_hash2.substring(0, 9);
    if (modified_hash1.equals(modified_hash2))  
        return true; 
    else 
        return false;
}

마지막으로, 무한 루프에서 최대 MAX_VALUE까지 정수를 랜덤 화하고 해시가 발견되는 경우에만 나갈 주요 함수가 있습니다.

public static void main(String[] args) {
    Random random = new Random();
    int x1 = 0;
    int x2 = 0;
    int counter = 0;
    while (true) {
        while(true){
            x1 = random.nextInt(Integer.MAX_VALUE);
            x2 = random.nextInt(Integer.MAX_VALUE);
            if (x1 != x2) 
                break;  
        } 
        if (findCollision(x1, x2) == true) {
            break;
        }
        counter++;
    }
    System.out.println("\nNumber of trials: " + counter);
}

SHA-1의 첫 24 비트 만 가져 오려고하면 충돌을 쉽게 찾을 수 있습니다. 그러나 몇 시간 동안 실행하더라도 36 비트에 대한 충돌을 찾을 수 없습니다. 따라서 36 비트 SHA-1만으로 충돌을 발견 할 수있는 다른 방법이 무엇인지 궁금합니다.


  • 답변 # 1

    이 내용을 입력하는 동안 생일 공격 을 봐야한다는 것을 깨달았습니다. , 아마도 내 대답보다 훨씬 더 정교해질 것입니다.

    36 비트의 데이터가 있다는 것은\ $2 ^ {36} = 68719476736 \ $의 총 가능성을 의미합니다. Pigeonhole 원리 를 기반으로 68719476736의 다른 문자열의 해시를 비교하면 충돌.

    그래서 쉬워요! 다음을 실행하기 만하면됩니다 (의사 코드) :

    hashset = (new hashset that uses your hashing algorithm)
    for(i = 0; i < 68719476736 + 1; i++) {
        if hashset.contains(string(i)) break; 
        hashset.add(string(i));
    }
    print("This took " + i + " tried!")
    
    

    이로 인해 충돌이 발생하면보증됩니다.하지만문제가 있습니다. 모든 반복에 100 밀리 초가 걸린다면 솔루션을 얻는 데 약 217 년이 필요합니다. 당신의 위대한 증손이 해결책을 가지고 당신에게 돌아올 것이라고 선생님에게 말하십시오. ~ 40 일 안에 이것을 실행하기 위해 2000 대의 컴퓨터를 구입할 수도 있습니다.

    내 알고리즘은 컴퓨터가 충돌하지 않는다고 가정 할 때 거의 보장됩니다. 이것은 "사물을 테스트하는 방법"에 대한 교훈으로, 개발자에게 유용합니다. 무언가를 테스트하고 싶을 때는 무작위로하지 마십시오. 알고리즘의 문제는 충돌이 발생하지 않을 것입니다. 언젠가이 작업을 마치려면 임의성이 필요하다는 것을 알고 있습니다.

    질문은, 우리가 이것을 개선하기 위해 무엇을 할 수 있을까요?

    충돌이 발생할 가능성을 충분히 얻기 위해 몇 개의 다른 문자열이 필요한지 확인할 수 있습니다. 생일 문제 의 일종으로, n이 다른 확률을 쉽게 계산할 수 있습니다. 사람들은 m 명의 그룹에서 같은 생일을 보낸다.

    근 사자 수아래의 공식을 사용하여 68719476736 + 1 개의 문자열을 보유한 경우 (예 : 1과 68719476736 사이의 모든 숫자) + 1) 충돌을 일으킬 확률이 약 50 %가되도록 308652를 선택해야합니다.

    당신이 시도 할 수있는 것은 무작위로 1과 68719476736 + 1 사이의 308652 숫자를 가져 와서 해시하여 충돌을 찾습니다. 충돌이없는 한 이것을 반복하십시오.

    의사 코드는 다음과 같습니다 :

    generator = RandomBigIntGenerator()
    numbers = []
    for(i = 0; i < 308652; i++) {
        numbers.add(generator.random(1,68719476736+1))
    }
    hashset = {} (With your hashing function)
    for n in numbers {
        if hashset.contains(n) {
            print("yay done");
            break;
        }
        hashset.add(m);
    }
    
    

    총체적으로 충돌이 있기를 희망하지만 컴퓨팅 능력이 필요합니다.

    코드 검토 관점에서 :

    이미 시도한 문자열을 추적해야하며 실제로 충돌을 찾는 데 도움이되는 유용한 정보를 제공합니다.

    문자열을 만들 때너무하지 마십시오.

    68719476736은 biiggg 숫자이지만 여전히 SHA1의1461501637330902918203684832716283019655932542976값보다 훨씬 작습니다. :

  • 답변 # 2

    24 비트에는 약 1,680 만 개의 해시가있을 수 있으므로 충돌을 찾을 때까지 평균 810 만 쌍을 시도해야합니다. 36 비트를 사용하면 숫자에 4096을 곱해야 680이 각각 340 억 개가됩니다. 반복 할 때마다 두 개의 해시를 계산하지 않고 루프 전에 하나를 계산하고 일정하게 유지하여이를 반으로 줄일 수 있습니다.

    그러나 그것은 아마도 당신이 보내고 싶은 시간보다 더 많은 시간 일 것입니다. 이 시간을 줄이는 한 가지 방법은 생일 역설을 활용하는 것입니다 ( https : //en.m.wikipedia .org/wiki/Birthday_problem ). 해시 목록을 계산하고 서로를 비교하면 충돌 가능성이 훨씬 높아집니다. 이 전화 화면에서 완전한 알고리즘을 입력하려고 시도하지는 않지만 :-)

  • 이전 ecmascript 6 - momentjs를 사용하지 않고 자바 스크립트로 날짜 형식을 지정하는 방법
  • 다음 javascript - 피아노, 모든 키를 출력하고 스케일을 제공