레인보우 테이블이란 무엇이며 어떻게 사용됩니까?

레인보우 테이블은 일반적으로 컴퓨팅 시간을 활용하는 또 다른 간단한 기술 암호 복구의 절충점 : 해시 테이블.

해시 테이블은 암호 사전에서 각 단어를 해싱하여 구성됩니다. 암호-해시 쌍은 해시 값별로 정렬 된 테이블에 저장됩니다. 해시 테이블을 사용하려면 해시를 가져 와서 원래 암호가있는 경우 테이블에서 이진 검색을 수행하여 원래 암호를 찾습니다.

레인보우 테이블은 더 복잡합니다. 레인보우 테이블을 구성하려면 두 가지가 필요합니다. : 해싱 기능과 축소 기능 주어진 Rainbow Tables에 대한 해싱 기능은 복구하려는 해시 된 암호와 일치해야합니다. 축소 기능은 해시를 암호로 사용할 수있는 것으로 변환해야합니다. 간단한 축소 기능은 Base64입니다. 해시를 인코딩 한 다음 특정 문자 수로 자릅니다.

레인보우 테이블은 특정 길이 (예 : 100,000)의 “체인”으로 구성됩니다. 체인을 구성하려면 임의의 시드 값을 선택합니다. 이 시드와 그 출력에 해싱 및 축소 기능을 적용하고 100,000 회 반복을 계속합니다. 시드 및 최종 값만 저장됩니다.이 프로세스를 반복하여 원하는만큼 체인을 만듭니다.

복구하려면 Rainbow Tables를 사용하는 암호, 암호 해시는 동일한 길이에 대한 위의 프로세스 :이 경우 100,000이지만 체인의 각 링크는 유지됩니다. 체인의 각 링크는 각 체인의 최종 값과 비교됩니다. 일치하는 항목이 있으면 각 해싱 함수의 출력과 각 축소 함수의 출력을 모두 유지하면서 체인을 재구성 할 수 있습니다. 재구성 된 체인에는 해당 암호의 해시와이를 생성 한 암호가 포함됩니다.

해시 테이블의 강점은 암호 복구가 매우 빠르고 (이진 검색) 사람을 구축한다는 것입니다. 해시 테이블은 상위 10,000 개의 암호와 같이 그 안에 들어가는 것을 선택할 수 있습니다. Rainbow Tables에 비해 약점은 해시 테이블이 모든 단일 해시-암호 쌍을 저장해야한다는 것입니다.

Rainbow Tables는 해당 테이블을 구성하는 사람이 링크 수를 선택하여 필요한 저장 공간을 선택할 수 있다는 이점이 있습니다. 각 체인. 시드와 최종 값 사이의 링크가 많을수록 더 많은 암호가 캡처됩니다. 한 가지 약점은 체인을 구축하는 사람이 “캡처 한 암호를 선택하지 않아 Rainbow Tables가 일반 암호에 최적화 될 수”없다는 것입니다. 또한 암호 복구에는 긴 해시 체인을 계산하는 작업이 포함되므로 복구 비용이 많이 듭니다. 체인이 길수록 더 많은 암호가 캡처되지만 내부에서 암호를 찾는 데 더 많은 시간이 필요합니다.

해시 테이블은 일반적인 암호에 적합하고 레인보우 테이블은 까다로운 암호에 적합합니다. 가장 좋은 방법은 해시 테이블 및 / 또는 상위 N 개 암호 사전을 사용하는 기존 크래킹을 사용하여 가능한 한 많은 암호를 복구하는 것입니다. 나머지는 레인보우 테이블을 사용하십시오.

댓글

• 오, 세상에, 충격을 받았음을 인정합니다. 모든 레인보우 테이블에 대해 논의하고 설명합니다. 시간, 그리고 이번에는 ” 일반적으로 혼란스러워하는 ” 중 하나였습니다! 나는 완전히 +1000 번이나 여기서 새로운 것을 배웠습니다. (그리고 답을 알았다 생각했습니다). 질문을해서 다행 이네요 … 감사합니다!
• 구체적이기는하지만 (이제 눈을 뜨고 좀 더 조사했습니다 :)) Rainbow Tables는 다음을 사용하여 Hellman Hash Chains와 차별화됩니다. 몇 가지 다른 감소 기능. 실제로 더 복잡하지만 정말 아름다운 아이디어입니다 (Ah!는 ‘ ” Rainbow ” 테이블?)
• 이것은 매우 좋은 설명이라는 데 동의합니다. 내 대답에서 나는 그것을 간단하게 설명했고 또한 단순하게 됨으로써 잘못 설명했습니다.Rainbow 테이블의 장점은 모든 해시 값을 저장하지 않는다는 점입니다. ‘ 나는 내 편집을 할 것이고, 더 나은 설명이기 때문에 이것을 투표 할 것입니다.
• 흠 … 내가 그것에 대해 더 많이 생각할수록, 실제 시스템에서 Rainbow Tables는 그다지 유용하지 않습니다. 해시 테이블. 언급했듯이 일반적인 암호의 경우 해시 테이블이 훨씬 낫습니다 (크기가 훨씬 빠르기 때문에 암호 사전에 대한 크기 요구 사항은 물론 가능한 전체 암호 범위보다 훨씬 작기 때문입니다). 그리고 ‘ 농담입니까? 대부분의 암호는 해당 범주에 속하며 RT에서 호출해야하는 경우는 매우 드뭅니다 (당분간 그렇게 될 것입니다).
• 안타깝게도 여기에서 저를 잃어 버렸습니다. ” Rainbow Tables를 사용하여 비밀번호를 복구하기 위해 비밀번호는 동일한 길이로 위의 프로세스를 거칩니다. ” 비밀번호를 사용할 때 어떻게 프로세스를 수행 할 수 있습니까 ‘도 알려지지 않았나요? 암호 해시를 의미 했습니까? 또한 ‘이 있습니다. ” 체인의 각 링크는 각 체인의 최종 값과 비교됩니다. ” 링크 값이 지속적으로 해시되고 축소되므로 체인의 링크가 체인의 최종 값과 일치하는 상황을 볼 수 없습니다.

무지개 테이블이 무엇인지에 대한 좋은 설명이 많이 있습니다.이 설명은 무지개 테이블 작동 방식

목적 및 관련성

레인보우 테이블은 어려운 암호, 즉 큰 사전에서도 찾을 수없는 암호를 해독하는 데 도움이됩니다. 암호는 역사적으로 데이터베이스에 일반 해시로 저장되었으며, 이것이 바로 Rainbow 테이블이 효과적인 이유입니다. 하나의 Rainbow 테이블을 만들고 (느린) 해시로 가득 찬 데이터베이스를 여러 개 실행 (빠름)합니다.

요즘에는 점점 더 많은 시스템에서 Bcrypt, Scrypt 또는 Argon2와 같은 적절한 비밀번호 저장 알고리즘을 사용합니다. 참조 : 비밀번호를 안전하게 [저장]하는 방법 이러한 알고리즘은 다음과 같습니다. 더 이상 레인보우 테이블에 “취약하지”않습니다. 각 해시가 고유하기 때문에 암호가 동일하더라도 레인보우 테이블이 더 이상 작동하지 않습니다.

이것이 오늘날 레인보우 테이블이 인기가없는 이유입니다.Argon2와 같은 현대적인 것을 사용하지 않더라도 오늘날 개발자는 일반적으로 적어도 소금을 사용해야한다는 것을 알고 있습니다. 무지개 테이블을 쓸모 없게 만들기에는 이미 충분합니다.

작동 방식

테이블 만들기

각 길이가 5 인 두 개의 체인 만있는 무지개 테이블을 만든다고 가정 해보십시오. 무지개 테이블은 48 비트 (12 개의 16 진수 문자 만)를 출력하는 가상의 해시 함수 MD48을위한 것입니다. 체인을 구축 할 때 다음과 같이 표시됩니다.

Chain 0: 0=cfcd208495d5 => z=fbade9e36a3f => renjaj820=7668b2810262 => aL=8289e8a805d7 => ieioB=2958b80e4a3a => WLgOSj Chain 1: 1=c4ca4238a0b9 => ykI4oLkj=140eda4296ac => Dtp=1b59a00b7dbe => W=61e9c06ea9a8 => 6cBuqaha=d4d2e5280034 => 0uUoAD 

첫 번째 체인이기 때문에 0로 시작합니다. (시작할 값이 필요합니다.) MD48로 이것을 해시하면 cfcd208495d5로 바뀝니다. 이제 기본적으로이 해시를 다시 포맷하는 “reduce”함수를 적용합니다. “z”로 끝납니다. 다시 해시하면 fbade9e36a3f를 얻은 다음 다시 줄인 다음 renjaj820를 얻습니다. . 더 많은주기가 있으며 최종 결과는 WLgOSj입니다.

두 번째 체인에 대해서도 동일합니다. 다른 값으로 시작하여 동일한 작업을 수행합니다. 이것은 0uUoAD로 끝납니다.

우리의 완전한 무지개 테이블은 다음과 같습니다 :

WLgOSj => 0 0uUoAD => 1 

이것이 저장해야하는 전부입니다.

해시 찾기

온라인에서 해시를 찾았다 고 가정 해 보겠습니다. 7668b2810262. 테이블을 사용하여 해시를 분해 해 보겠습니다!

Looking for hash "7668b2810262", reduced to "aL". hashed=>reduced "aL" to ieioB hashed=>reduced "ieioB" to WLgOSj Found a match, "WLgOSj" is in our rainbow table: WLgOSj => 0 The chain starts with "0". Let"s walk that chain and look for the hash. hashed "0" to cfcd208495d5 hashed "z" to fbade9e36a3f hashed "renjaj820" to 7668b2810262 That hash matches! Found the password: renjaj820 

직접 해보기 위해 위의 예제는 다음 Python 스크립트를 사용하여 생성되었습니다. https://gist.github.com/lgommans/83cbb74a077742be3b31d33658f65adb

속성 확장

요약 :

• 빠른 조회는 커버리지가 동일하다고 가정하고 더 큰 테이블을 의미합니다.
• 더 나은 범위는 조회 속도가 느리거나 테이블이 더 크다는 것을 의미합니다.
• 테이블이 작을수록 조회 속도가 느리거나 범위가 나빠집니다.

다음 섹션에서는 해시 + 감소 당 시간이 1µs라고 가정하고 충돌을 설명하지 않습니다. 이들은 모두 정확한 값이 아니라 예시를 의미하는 야구장 번호입니다.

조회 시간

해시 + 감소 작업에 마이크로 초가 걸리면 체인이 백만 개이고 체인 당 10,000 개 감소가있는 테이블을 생성하는 데 약 3 시간이 걸립니다.
chain_length × chain_count / reductions_per_second / seconds_per_hour
= 10 000 × 1 000 000 / 1 000 000 / 3600 = 2.8 시간.

해당 테이블에서 조회하는 데 평균 10 밀리 초가 걸립니다. 이는 해시가 포함 된 체인을 찾기 전에 일반적으로 chain_length/2 축소를 거쳐야하기 때문입니다. 예를 들어, 테이블에있는 값을 찾기 전에 해시에서 3000 개를 줄여야 할 수 있습니다. 다음으로, 일치하는 값을 찾을 때까지 처음부터 해당 체인을 다시 수행해야합니다. 테이블에서 찾기 위해 3000을 수행해야했다면 체인의 올바른 지점에 도달하기 위해 처음부터 7000 개를 줄여야합니다. 기본적으로 조회 할 때 단일 체인을 생성 할 때만 큼 많은 작업을 수행합니다. 따라서 조회 시간은 마이크로 초당 10,000 번이며 이는 10 밀리 초 (또는 원하는 경우 1 센티 초)입니다.

저장소 요구 사항

해시 함수 (MD5)에 대한 완전하고 빠른 조회 테이블을 만들려면 “아직 1000 억 테라 바이트의 스토리지가 필요합니다.” 별로 도움이되지 않습니다. 하지만 10 자까지 소문자 암호 만 포함하려면 어떻게해야합니까?

해시를 찾는 데 최대 30 초를 소비하고 해시 당 1 마이크로 초 (백만 분의 1 초)가 필요하다고 가정하면 어떻게됩니까? +주기를 줄이면 체인 길이는 1 million × 30 = 3 천만입니다. 26 ¹⁰ (또는 10 ¹⁴ ) 가능한 10 개의 소문자 암호가 있으며 체인 당 3 천만 개의 값을 처리합니다. 그것은 우리에게 4 백만 개의 체인을 남깁니다. 각 체인에는 시작 및 끝 값만 저장되어 있으며 값은 각각 10 자라는 것을 알고 있습니다. 따라서 2 × 10 × 4 million = 76MiB 데이터입니다.

10 자 암호를 모두 반복하여 테이블을 생성하는 데는 오랜 시간이 걸립니다. 체인 당 30 초에 4 백만 개의 체인을 곱하면 약 91 년. 많은 사람들이 이러한 테이블에 관심을 가질 것이므로 1092 개의 CPU (= 91×12)를 풀링하면 1 개월 밖에 걸리지 않습니다. 이는 이러한 테이블이 포함 된 암호 공간에 비해 얼마나 작은지를 보여줍니다. 조회는 30 초 밖에 걸리지 않으며 76MiB 데이터 만 저장하면됩니다.

결론

Rainbow 테이블은 시간-메모리 절충 으로 간주됩니다. 하나는 테이블의 작은 부분 만 저장하고 조회 시간에 대한 추가 계산을 통해이를 복구합니다. 이것이 솔트 또는 Scrypt 또는 Argon2와 같은 좋은 암호 저장 알고리즘이 암호를 안전하게 유지하는 데 중요한 이유의 일부입니다.레인보우 테이블은 솔트와 비밀번호를 모두 포함 할 수있을만큼 큰 항목이 테이블에 포함 된 경우에만 솔트 된 비밀번호를 복구 할 수 있습니다. 이는 매우 비효율적이며 전체 목적에 위배됩니다.

비슷한 것이 암호화에도 적용됩니다. 사람들이 암호로 파일을 암호화하면 파일을 해독하기 위해 레인보우 테이블을 만들 수 있습니다. 소프트웨어가 AES를 사용하고 파일의 첫 번째 블록이 사용자가 제공 한 암호를 사용하여 “암호 수정”으로 해독해야한다고 가정 해 보겠습니다. 그러면 레인보우 테이블이 해시 함수 대신 AES를 사용합니다.

암호 (강도를 알 수없는 비밀, 특히 사용자가 다시 사용할 수있는 경우)를 처리 할 때마다 항상 적절한 (느린) 암호 저장 알고리즘을 통해 실행하여 느리고 고유하게 크랙하십시오.

댓글

• 좋은 설명입니다. 올바르게 이해했다면 무지개 테이블의 힘은 좋은 축소 기능을 갖는 데 있습니다. 좋은 것을 어떻게 생각합니까? 그리고 체인 전체의 모든 후보에 대한 충돌을 피하려면 어떻게해야합니까?
• @ Kyu96 좋은 질문입니다! 저는 ‘ 답을 모르지만 찾으시면 관심이 있습니다. 이 페이지는 무지개 테이블이 무엇인지에 대한 일반적인 질문에 관한 것이며 알고리즘을 설계하는 방법과 같은 세부 사항이 아닙니다. 새 질문을 열어야 하지만이 웹 사이트는 ” 디지털 위협으로부터 자산을 보호 ” (iirc ). “에 대한 자매 사이트 인 crypto.stackexchange.com 의 주제와 관련이있을 것 같습니다. 암호화 시스템의 수학과 속성, 분석 (” 암호 분석 “) 및 일반적으로 암호화를 구성하는 보조 주제 (예 : 난수) 세대. ”