it-swarm-korea.com

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

어디서 찾을 수 있습니까? 마지막에 금 냄비가 있습니까?
그들로부터 어떻게 보호합니까?


Area51 proposal 에서

이 질문은 금주의 IT 보안 질문입니다.
자세한 내용은 2011 년 9 월 9 일 블로그 항목 또는 자신의 제출 금주의 질문.

149
AviD

Rainbow Tables는 일반적으로 암호 복구에서 해시 테이블이라는 계산 시간 저장 균형을 활용하는 다른 간단한 기술과 혼동됩니다.

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

레인보우 테이블이 더 복잡합니다. Rainbow 테이블을 만들려면 해싱 함수와 축소 함수라는 두 가지가 필요합니다. 주어진 레인보우 테이블 세트의 해싱 함수는 복구하려는 해시 비밀번호와 일치해야합니다. 축소 기능은 해시를 암호로 사용 가능한 것으로 변환해야합니다. 간단한 축소 기능은 해시를 Base64로 인코딩 한 다음 특정 문자 수로 자릅니다.

레인보우 테이블은 특정 길이의 "체인"으로 구성됩니다 (예 : 100,000). 체인을 구성하려면 임의의 시드 값을 선택하십시오. 그런 다음 해시 및 축소 함수를이 시드 및 해당 출력에 적용하고 100,000 번 반복합니다. 시드 및 최종 값만 저장됩니다. 이 과정을 반복하여 원하는만큼 체인을 만듭니다.

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

해시 테이블의 장점은 암호 복구가 매우 빠르며 (이진 검색) 해시 테이블을 작성하는 사람이 상위 10,000 개의 암호와 같이 암호를 입력 할 대상을 선택할 수 있다는 것입니다. Rainbow Tables와 비교할 때의 약점은 해시 테이블이 모든 단일 해시 암호 쌍을 저장해야한다는 것입니다.

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

해시 테이블은 일반 비밀번호에 적합하고 Rainbow Tables는 강력한 비밀번호에 적합합니다. 가장 좋은 방법은 해시 테이블을 사용하여 가능한 한 많은 암호를 복구하거나 상위 N 개의 암호 사전을 사용하여 기존의 크래킹을하는 것입니다. 남아있는 사람들은 Rainbow Tables를 사용하십시오.

180
Crunge

Rainbow 테이블이 무엇인지에 대한 많은 좋은 설명이 있습니다. 이것은 Rainbow 테이블 작동 방식 이 특히 좋습니다. 또한 Wikipedia article 도 매우 잘 설명되어 있습니다. 주제에 대한 최종 논문을 좀 더 깊이 읽으려면 더 빠른 암호화 시간-메모리 트레이드 오프 만들기 입니다.

Rainbow Tables에 대한 간단한 설명은 시간 메모리 트레이드 오프 기술을 사용한다는 것입니다. 대상 해시 값과 단어 사전을 취한 다음 각 단어를 해시하고 즉시 비교를 수행하는 대신 ( John 과 같은 방법을 사용하는 무력 접근법) 대신 사전의 모든 값을 해시합니다 사전 (사전 크기에 따라 시간이 오래 걸릴 수 있음). 그러나 일단 완료되면 Rainbow 테이블의 사전 해시 값에 대해 원하는만큼의 해시를 비교할 수 있으며 이는 해시를 다시 계산하는 것보다 훨씬 빠릅니다.

레인보우 테이블이 사용하는 축소의 사용을 설명하지 않았기 때문에 이전에 짧게하기 위해 여기에 쓴 설명은 잘못되었습니다. 이 비트를 다시 쓸 때까지 더 나은 설명을 보려면 @ Crunge answer 를 참조하십시오.

RainbowCrack 와 같은 응용 프로그램을 사용하여 Rainbow 테이블을 직접 생성하거나 The Shmoo Group , Free Rainbow Tables 프로젝트와 같은 소스에서 다운로드 할 수 있습니다. 웹 사이트, Ophcrack 프로젝트 및 필요한 해시 유형에 따라 다른 많은 장소.

레인보우 테이블 기반 공격으로부터 시스템을 보호하는 가장 효과적인 방법은 시스템 내 모든 해시가 salted 인지 확인하는 것입니다. 이는 미리 생성 된 Rainbow 테이블을 쓸모 없게 만들고 공격자가 대상 해시에 대해 사용할 사용자 지정 테이블 집합을 생성해야한다는 것을 의미합니다. 이는 소금을 알고있는 경우에만 가능합니다.

15
Mark Davidson

목적과 관련성

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

요즘 점점 더 많은 시스템에서 Bcrypt, Scrypt 또는 Argon2와 같은 적절한 암호 저장 알고리즘을 사용합니다. 암호를 안전하게 저장하는 방법? 이러한 알고리즘은 더 이상 Rainbow 테이블에 대해 "취약성"이 아닙니다. 각 해시는 고유하므로 암호가 동일하더라도 Rainbow 테이블이 더 이상 작동하지 않습니다.

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

작동 방식

테이블 생성

레인보우 테이블은 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로 바뀝니다. 이제이 해시를 기본적으로 암호로 다시 포맷하는 "감소"기능을 적용하고 "z"로 끝납니다. 다시 해시하면 fbade9e36a3f를 얻은 다음 다시 줄이고 renjaj820를 얻습니다. 더 많은 사이클이 있으며 최종 결과는 WLgOSj입니다.

두 번째 체인도 마찬가지입니다. 우리는 다른 가치로 시작해서 같은 일을합니다. 이것은 0uUoAD로 끝납니다.

전체 Rainbow 테이블은 다음과 같습니다.

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 밀리 초 (또는 원하는 경우 1 밀리 초) 인 마이크로 초의 10,000 회입니다.

저장소 요구 사항

MD5를 포함한 해시 함수에 대한 완전하고 빠른 조회 테이블을 만들려면 여전히 1000 억 테라 바이트의 스토리지가 필요합니다. 그다지 도움이되지 않습니다. 그러나 10 자까지 소문자 비밀번호 만 포함하려면 어떻게해야합니까?

해시를 찾는 데 최대 30 초를 소비하고 해시 + 감소주기 당 1 마이크로 초 (백만 분의 1 초)가 필요하다고 가정하면 체인 길이는 다음과 같습니다. 1 million × 30 = 3 천만 . 26이 있습니다10 (또는 1014) 10 개의 소문자 비밀번호가 가능하며 체인 당 3 천만 개의 값을 포함합니다. 그것은 우리에게 4 백만 체인을 남깁니다. 각 체인에는 시작 및 끝 값만 저장되며 값은 각각 10 자임을 알고 있습니다. 따라서 2 × 10 × 4 million = 76 MiB 데이터입니다.

10 자 암호를 모두 반복하여 테이블을 생성하는 데 시간이 오래 걸립니다. 체인 당 30 초, 4 백만 체인의 시간은 약 91 년입니다. 그러나 많은 사람들이 그러한 테이블에 관심을 가질 것이므로 1092 개의 CPU (= 91 × 12)를 풀링하면 1 개월 밖에 걸리지 않습니다. 이 표는 암호 공간과 비교할 수있는 크기를 보여줍니다. 조회에는 30 초 밖에 걸리지 않으며 76MiB 데이터 만 저장해야합니다.

결론

Rainbow 테이블은 time-memory trade-off 로 간주 될 수 있습니다. 하나는 테이블의 작은 부분 만 저장하고 조회 시간에 대한 추가 계산을 통해이를 복구합니다. 이것이 암호를 안전하게 유지하기 위해 소금 또는 Scrypt 또는 Argon2와 같은 우수한 암호 저장 알고리즘이 중요한 이유의 일부입니다. Rainbow 테이블은 소금과 암호를 모두 포함 할 수있을 정도로 큰 항목이 테이블에 포함 된 경우 소금에 절인 암호 만 복구 할 수 있습니다. 이는 extremely 비효율적이며 전체 목적을 무효화합니다.

암호화에도 비슷한 사항이 적용됩니다. 사람들이 암호로 파일을 암호화 할 때 파일을 크랙하기 위해 Rainbow 테이블을 만들 수 있습니다. 소프트웨어가 AES를 사용하고 파일의 첫 번째 블록이 사용자가 제공 한 암호를 사용하여 "암호 수정"으로 해독해야한다면 Rainbow 테이블은 해시 함수 대신 AES를 사용한다고 가정 해 봅시다.

암호 (알 수없는 강도, 특히 사용자가 재사용 할 수있는 암호)를 처리 할 때마다 항상 적절한 (느린) 암호 저장 알고리즘을 통해 암호를 느리고 독특하게 만드십시오.

7
Luc