레인보우 테이블의 계산 과정
간단히 말하면 특정 알고리즘, 특히 비대칭 알고리즘(예: md5 알고리즘)을 효과적으로 크랙하는 방법입니다. 그의 프로세스는 원본 데이터와 암호화된 데이터에 해당하는 해시 테이블을 구축하는 것입니다. 이러한 방식으로 암호화된 데이터를 얻은 후 비교, 쿼리 또는 특정 작업을 통해 원본 데이터를 빠르게 찾을 수 있습니다. 이론적으로 쿼리에 소요되는 시간을 고려하지 않으면 해시 테이블이 클수록 크래킹이 더 효과적이고 빨라집니다. 물론 이 방법은 다른 크래킹 방법(예: 충돌)에는 서툴고, 가변 길이 키와 같은 최신 고급 알고리즘에서는 그 효과가 크게 줄어듭니다. 그러나 무슨 일이 있어도 레인보우 테이블(해시)은 데이터 암호화 및 암호 해독에 항상 무력하지만 매우 효과적인 방법입니다.
비밀번호 해시 함수 H와 비밀번호 P가 있다고 가정합니다. 전통적인 접근 방식은 H(X)의 모든 출력을 철저하게 열거하고 H(P)=H(x[y])를 설정하는 것입니다. 우리는 P==를 얻습니다. H와 R 함수를 번갈아 사용하여 해시 함수를 얻고 교대로 비밀번호와 해시 값을 형성하여 값을 얻습니다.
예: P가 6자리 비밀번호 세트라고 가정합니다. 해시 값, 32비트 긴 체인 다음과 같이 보일 수 있습니다:
aaaaaa -H()->281DAF40 -R()-> sgfnyd -H()-> 9203CF10 --R() -->kiebgt.
테이블을 생성하기 위해 P에서 무작위 초기 비밀번호 세트를 선택하고, 각 체인에 대해 고정 길이 K 테이블을 계산하고, 각 체인의 첫 번째 비밀번호와 마지막 비밀번호를 저장합니다. 첫 번째 비밀번호를 시작점이라고 하고 마지막 비밀번호를 끝점이라고 합니다. 위의 예제 체인에서 "AAAAAA"는 시작점이 되고 "kiebgt"는 끝점이 되며 다른 비밀번호(또는 해시)는 저장되지 않습니다.
암호문 h가 주어지면 연산을 반대로 하고(해당 비밀번호 찾기) R 다음에 H, R 다음에 h 등을 넣어 체인을 계산해야 합니다. 이 작업 중 어느 시점에서든 해당 지점의 값이 이전 해시 체인의 끝점 중 하나와 일치하는 것을 발견하면 우리가 찾고 있는 비밀번호 p에 해당하는 시작점이 있는 것입니다.
예를 들어 해시 920ECF10이 주어지면 첫 번째 요청인 체인: 발견 위치:
90E1CF10---R()-->kiebgt
를 계산합니다. p> p>kiebgt는 엔드포인트 중 하나이므로 다른 지점을 새 엔드포인트로 사용하여 aaaaaa를 찾습니다.
aaaaa--H-->281DAF40---R --> sgfnyd--H-->920EC10
따라서 비밀번호는 "sgfnyd"입니다.
그러나 FB107E70이 체인에 없지만 동일한 엔드포인트 AAAAAA를 갖고 있는 경우 다른 해시 링크와 해독 경쟁을 계속해야 합니다.
단순에는 몇 가지 함정이 있습니다. 해시 체인. 언제든지 두 개의 체인이 서로 충돌하면(동일한 값 생성) 병합되므로 가장 심각한 암호를 생성하기 위해 동일한 계산 비용을 지불하더라도 테이블은 많은 암호를 다루지 않습니다. 이전 체인으로 인해 모두 저장하지 않으면 효율적으로 탐지하는 것이 불가능합니다. 예를 들어 체인 3의 세 번째 값이 체인 7의 두 번째 값과 일치하는 경우 두 체인은 거의 동일한 값 시퀀스를 포함하지만 최종 값은 동일하지 않습니다. 해시 함수 H는 일반적으로 중요한 보안 기능으로 간주되어 충돌을 일으키지 않으므로 충돌을 일으킬 가능성이 적습니다. 그러나 축소 함수 R은 가능한 일반 텍스트를 올바르게 처리해야 하기 때문에 충돌 방지 기능이 없습니다.
또 다른 어려움은 R에 적합한 기능을 선택하는 것의 중요성입니다. R의 정체성을 선택하는 것은 무차별적인 접근 방식과 같지 않습니다. 공격자가 가능한 평문을 가지고 있는 경우에만 함수 R을 선택할 수 있으므로 가능한 암호의 전체 공간이 아닌 시간과 공간만 가능한 평문에 할당되도록 하는 것이 좋습니다.
R Shepherd에 영향을 미치기 전에 해시 계산 결과는 일반 텍스트일 수 있지만 R이 클래스에서 가능한 모든 일반 텍스트를 생성하지 못할 수 있다는 장점과 단점이 있습니다. 공격자는 공격자가 제공하는 비밀번호 없이 부정적인 결과를 확실히 확인하려고 합니다. 수업을 선택하세요. 더욱이, 원하는 분포와 일치하도록 함수 R 일반 텍스트를 설계하는 것이 어려울 수 있습니다.
레인보우 테이블의 충돌 문제는 단일 빼기 함수 R의 시퀀스를 연관된 빼기 함수 R 1 ~ R K 테이블로 대체함으로써 일반 해시 체인으로 효과적으로 해결됩니다. 이런 식으로 두 체인이 충돌하고 병합하려면 동일한 반복에서 동일한 값에 도달해야 합니다. 따라서 각 체인의 최종 값은 동일합니다. 최종 후처리 단계에서는 테이블의 체인을 정렬하여 동일한 최종 값을 가진 다른 체인에서 "중복" 체인을 제거할 수 있습니다. 새로운 체인을 생성하고 테이블을 채웁니다. 이러한 체인은 충돌이 없는 것은 아니지만(일시적으로 겹칠 수 있음) 병합되지 않으므로 총 충돌 횟수가 크게 줄어듭니다.
찾는 방법은 시퀀스의 복원 기능을 사용하여 다양합니다. 관심 있는 해시 값은 체인의 어느 곳에서나 발견될 수 있으므로 서로 다른 체인에 대해 K개의 테이블을 생성해야 합니다. 첫 번째 체인은 해시 값이 마지막 해시 위치에 있다고 가정하고 R K 테이블에만 적용됩니다. 체인은 해시 값이 두 번째에서 마지막 해시 위치에 있다고 가정하고 R ? -1,H에 적용됩니다. 모든 복원 기능을 적용하는 마지막 체인까지 계속해서 H와 교환합니다. 잘못된 경보를 생성하여 새로운 경로를 생성합니다. 잘못된 위치의 해시 값을 "추측"하면 불필요하게 체인을 평가할 수 있습니다.
레인보우 테이블에는 따라야 할 체인이 더 많지만 더 적은 수의 테이블로 그렇게 합니다. 간단한 해시 연결 목록은 특정 크기를 초과하는 병합 체인으로 인해 증가할 수 없고 빠르게 비효율적이 됩니다. 이를 처리하기 위해 여러 개를 유지합니다. 각 조회는 각 테이블을 검색해야 합니다. Rainbow 테이블은 동일한 성능을 얻을 수 있으므로 ?배의 조회 테이블을 사용하여 수행할 수 있습니다.