레인보우 테이블
Rainbow table무지개 테이블은 암호 해시 함수의 출력을 캐시하기 위해 미리 계산된 테이블로, 일반적으로 암호 해시를 크래킹하기 위해 사용됩니다.표는 보통 제한된 문자 집합으로 구성된 특정 길이까지 키 파생 기능(또는 신용카드 번호 등)을 복구하는 데 사용됩니다.이는 모든 시도에서 해시를 계산하는 브루트포스 공격보다 컴퓨터 처리 시간과 저장 공간을 적게 사용하고 해시당 하나의 엔트리를 사용하는 단순한 키 파생 함수보다 처리 시간과 저장 공간을 적게 사용하는 시공간의 트레이드오프의 실제 예입니다.소금을 사용하는 키 파생물을 사용하면 이 공격을 실행할 수 없게 됩니다.
레인보우 테이블은 필립 외클린에[1] 의해 마틴 [2]헬먼에 의해 더 빠르고 단순한 알고리즘의 적용으로 발명되었다.
배경
사용자 인증의 경우 비밀번호는 일반 텍스트 또는 해시 중 하나로 저장됩니다.데이터베이스 액세스가 손상된 경우 일반 텍스트로 저장된 비밀번호가 쉽게 도난당하므로, 데이터베이스는 일반적으로 해시를 저장합니다.따라서 인증 시스템을 포함한 누구도 데이터베이스에 저장된 값만 보고 비밀번호를 배울 수 없습니다.
사용자가 인증용 비밀번호를 입력하면 해시가 계산되어 해당 사용자의 저장된 해시와 비교됩니다.2개의 해시가 일치하지 않으면 인증이 실패합니다.게다가 해시 값을 패스워드로 입력하면 인증 시스템이 해시 값을 두 번째로 해시하기 때문에 인증은 동일하게 실패합니다.
해시로부터 패스워드를 학습하는 것은 해시함수에 입력할 때 동일한 해시를 생성하는 문자열을 찾는 것입니다.이것은 해시 함수를 반전시키는 것과 같습니다.
brute-force 공격(사전 공격 등)을 사용하여 해시 함수를 반전시킬 수 있지만 가능한 비밀번호 세트가 충분히 클 경우 실행 불가능할 수 있습니다.brute-force 대신 미리 계산된 해시 체인 테이블을 사용하는 방법이 있습니다.레인보우 테이블은 특정한 기술적 어려움을 극복하는 특별한 종류의 테이블이다.
어원학
레인보우 테이블이라는 용어는 Oechslin의 첫 번째 논문에서 처음 사용되었다.이 용어는 공격의 성공률을 높이기 위해 다양한 감소 함수를 사용하는 방법을 나타냅니다.Hellman의 원래 방법은 각각 다른 축소 함수를 가진 많은 작은 테이블을 사용합니다.무지개 테이블은 훨씬 더 크고 각 열에 다른 축소 함수를 사용합니다.축소 함수를 나타내기 위해 색상을 사용하면 무지개가 무지개 테이블에 나타납니다.Oechslin의 논문 그림 2에는 이러한 섹션이 어떻게 관련되어 있는지를 나타내는 흑백 그래픽이 포함되어 있습니다.Crypto 2003 컨퍼런스에서 Oechslin은 무지개 관련성을 보다 명확하게 하기 위해 그래픽에 색상을 추가했습니다.회의에서 발표된 확장 그래픽은 오른쪽에 표시됩니다.
미리 계산된 해시 체인
패스워드 해시함수 H와 패스워드 P의 유한세트가 주어졌을 때 해시함수의 출력h가 주어졌을 때 H(p)=h가 되도록 P에 요소 p를 배치하거나 P에 그러한 p가 없다고 판단할 수 있는 데이터 구조를 미리 계산하는 것이 목표입니다.가장 간단한 방법은 P의 모든 P에 대해 H(p)를 계산하는 것이지만, 그 후 테이블을 저장하려면 δ(P n) 비트의 공간이 필요합니다.여기서 P는 세트 P의 크기, n은 H의 출력 크기입니다.이것은 큰 P에서는 금지되는 것입니다.해시 체인은 이 공간 요건을 줄이기 위한 기술입니다.이 개념은 해시 값을 P의 값에 다시 매핑하는 축소 함수 R을 정의하는 것입니다.단, 리덕션 함수는 실제로는 해시 함수의 역함수가 아니라 해시 함수의 도메인과 코도메인이 스왑된 다른 함수입니다.해시함수와 축소함수를 교대로 함으로써 패스워드와 해시값을 교대로 하는 체인을 형성한다.예를 들어, P가 알파벳6 문자의 소문자 패스워드 세트이고 해시 값이 32비트인 경우 체인은 다음과 같습니다.
![{\displaystyle {\color {Red}{\mathtt {aaaaaa}}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {281DAF40}}\,{\xrightarrow[{\;R\;}]{}}\,{\mathtt {sgfnyd}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {920ECF10}}\,{\xrightarrow[{\;R\;}]{}}\,{\color {Violet}{\mathtt {kiebgt}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/609e4ea6eac3f25b5982f3c9c6ccdaead642540d)
축소 함수의 유일한 요건은 특정 크기의 "일반 텍스트" 값을 반환할 수 있어야 한다는 것입니다.
테이블을 생성하기 위해 P에서 임의의 초기 비밀번호 세트를 선택하고 각 비밀번호에 대해 일정 길이의 k 체인을 계산하여 각 체인에 첫 번째 비밀번호와 마지막 비밀번호만 저장합니다.첫 번째 비밀번호는 시작점이고 마지막 비밀번호는 끝점입니다.위의 체인 예에서는 "aaaaaa"가 시작점이고 "kiebgt"가 끝점이며 다른 비밀번호(또는 해시 값)는 저장되지 않습니다.
다음으로 반전할 해시값h 를 지정하면(대응하는 패스워드를 검색), R, H, R 등을 적용하여h부터 시작하는 체인을 계산합니다.값이 테이블의 엔드포인트 중 하나와 일치하는 경우 해당 시작점에서 전체 체인을 다시 만들 수 있습니다.이 체인에는 h 값이 포함되어 있을 가능성이 높으며, 포함되어 있는 경우 체인 내의 직전 값은 우리가 찾는 패스워드 p입니다.
예를 들어, 해시가 지정된 경우920ECF10, 체인은 R을 먼저 적용하여 계산할 수 있다.
![{\displaystyle {\mathtt {920ECF10}}\,{\xrightarrow[{\;R\;}]{}}\,{\color {Violet}{\mathtt {kiebgt}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c5d0f08a2a5598244e082b88810425f16b660270)
"kiebgt"는 테이블 내의 엔드포인트 중 하나이므로 대응하는 시작 비밀번호 "aaaaaa"는 920ECF10에 도달할 때까지 체인을 따를 수 있습니다.
![{\displaystyle {\color {Red}{\mathtt {aaaaaa}}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {281DAF40}}\,{\xrightarrow[{\;R\;}]{}}\,{\mathtt {sgfnyd}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {920ECF10}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/96219a92ee1b95f41144e0498463f884939d996a)
따라서 비밀번호는 "sgfnyd"(또는 동일한 해시 값을 가진 다른 비밀번호)입니다.
단, 이 체인에 항상 해시값 h가 포함되어 있는 것은 아닙니다.h에서 시작하는 체인이 다른 시작점을 가진 체인과 결합하는 경우가 있습니다.예를 들어 해시 값 FB107E70의 체인은 kiebgt로 이어집니다.
![{\displaystyle {\mathtt {FB107E70}}\,{\xrightarrow[{\;R\;}]{}}\,{\mathtt {bvtdll}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {0EE80890}}\,{\xrightarrow[{\;R\;}]{}}\,{\color {Violet}{\mathtt {kiebgt}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/91cb90a3ee395b1ffaea3e25ae60d03cf331ba5c)
그러나 FB107E70은 "aaaaaa"부터 시작하는 체인에 없습니다.이를 거짓 경보라고 합니다.이 경우 일치는 무시되고 다른 일치를 찾기 위해h의 체인이 확장됩니다.h 체인이 적절한 일치가 없는 길이k까지 확장되면 패스워드는 어느 체인에서도 생성되지 않습니다.
테이블 내용은 반전되는 해시 값에 의존하지 않습니다.한 번 작성된 후 수정되지 않은 룩업에 반복적으로 사용됩니다.체인의 길이를 늘리면 테이블의 크기가 줄어듭니다.단, 룩업에 필요한 시간도 증가하며, 이것이 레인보우 테이블의 타임 메모리 트레이드오프입니다.단순한 원 아이템 체인의 경우 검색은 매우 빠르지만 테이블은 매우 큽니다.체인이 길어지면 검색 속도는 느려지지만 테이블 크기는 줄어듭니다.
단순 해시 체인에는 몇 가지 결함이 있습니다.가장 심각한 것은 두 개의 체인이 어느 시점에서 충돌할 경우(같은 값을 생성), 두 체인이 병합되고 결과적으로 생성에 동일한 계산 비용을 지불했음에도 불구하고 테이블에는 그만큼의 패스워드가 포함되지 않는다는 것입니다.이전 체인은 완전히 저장되지 않기 때문에 효율적으로 검출할 수 없습니다.예를 들어 체인 3의 세 번째 값이 체인 7의 두 번째 값과 일치하는 경우 두 체인은 거의 동일한 일련의 값을 포함하지만 최종 값은 같지 않습니다.해시함수 H는 충돌을 일으키지 않는 것이 보통 중요한 보안 기능으로 간주되기 때문에 충돌을 일으키지 않을 가능성이 높지만 축소함수 R은 가능한 평문을 올바르게 커버해야 하기 때문에 충돌에 견딜 수 없습니다.
다른 어려움은 R에 대한 올바른 함수를 선택하는 것의 중요성 때문에 발생합니다.R을 아이덴티티로 선택하는 것은 무차별적인 접근과 거의 다를 바 없습니다.공격자가 가능한 일반 텍스트가 무엇인지 잘 알고 있는 경우에만 가능한 암호 공간 전체가 아닌 가능한 일반 텍스트에만 시간과 공간을 사용하는 함수 R을 선택할 수 있습니다.실제로 R은 이전 해시 계산 결과를 가능한 일반 텍스트로 되돌리지만, 이 이점은 R이 선택한 클래스에서 패스워드가 나오지 않았음을 공격자에게 확실하게 거부하려는 클래스에서 가능한 모든 일반 텍스트를 생성하지는 않을 수 있다는 단점이 있습니다.또한 함수 R을 평문의 [2]예상 분포와 일치하도록 설계하는 것도 어려울 수 있다.
레인보우 테이블
레인보우 테이블은 단일 환원 함수 R을 관련된 일련의 환원 함수1 R~R로k 대체함으로써 일반 해시 체인과의 충돌 문제를 효과적으로 해결한다.이와 같이 2개의 체인이 충돌 및 Marge하기 위해서는 같은 반복으로 같은 값을 얻을 필요가 있습니다.따라서 이들 체인의 최종값은 동일합니다.최종 후처리 패스는 테이블 내의 체인을 정렬하여 다른 체인과 동일한 최종값을 가진 "복제" 체인을 제거할 수 있습니다.그런 다음 테이블을 채우기 위해 새로운 체인이 생성됩니다.이들 체인은 충돌이 없는 것은 아니지만(잠시 중복될 수 있음), 결합하지 않기 때문에 전체 [citation needed]충돌 수가 대폭 감소합니다.
축소함수의 시퀀스를 사용하면 검색 방법이 바뀝니다.대상 해시 값은 체인의 어느 위치에서나 찾을 수 있기 때문에 k개의 다른 체인을 생성해야 합니다.첫 번째 체인은 해시 값이 마지막 해시 위치에 있다고 가정하고 R만 적용합니다k.다음 체인은 해시 값이 두 번째에서 마지막 해시 위치에 있다고 가정하고 모든 축소k 함수를 적용하는 마지막 체인까지 계속k−1 적용됩니다.이로 인해 잘못된 알람을 생성하는 새로운 방법이 생성됩니다.해시 값의 위치를 잘못 추측하면 체인이 불필요하게 평가될 수 있습니다.
레인보우 테이블은 더 많은 체인을 따라야 하지만 테이블 수가 적기 때문에 단순 해시 체인 테이블은 머지 체인으로 인해 빠르게 비효율화되지 않고는 특정 크기를 초과할 수 없습니다. 이 문제를 해결하기 위해 여러 테이블을 유지하고 각 테이블을 검색해야 합니다.레인보우 테이블은 k배 더 큰 테이블에서도 유사한 성능을 얻을 수 있기 때문에 룩업을 k배 줄일 수 있습니다.
예
- 아래 그림의 해시('re3xes')에서 테이블에서 사용된 마지막 축소를 계산하여 테이블의 마지막 열에 암호가 표시되는지 확인합니다(스텝 1).
- 테스트가 실패하면(람보가 표에 표시되지 않음), 마지막 두 번의 감소로 체인을 계산합니다(이 두 개의 감소는 2단계에서 나타냅니다).
- 메모: 이 새로운 테스트가 다시 실패하면 패스워드가 검출될 때까지 3회, 4회 등으로 계속 진행합니다.비밀번호가 포함되어 있는 체인이 없는 경우 공격은 실패한 것입니다.
- 이 테스트가 양성이면(스텝 3, linux23이 체인의 끝과 테이블에 표시됨) 비밀번호는 linux23을 생성하는 체인의 시작 부분에서 취득됩니다.여기에서는 테이블에 저장되어 있는 대응하는 체인의 선두에 패스워드가 있습니다.
- 이 시점에서(스텝 4), 체인을 생성하고 반복할 때마다 해시와 타깃 해시를 비교한다.테스트는 유효하며 체인에서 해시 re3x가 검출되었습니다.현재의 패스워드(문화)는 체인 전체를 생성한 패스워드입니다.공격은 성공했습니다.
레인보우 테이블은 체인의 각 "링크"에 대해 다른 축소 함수를 가진 정교한 알고리즘을 사용합니다.따라서 두 개 이상의 체인으로 해시 충돌이 발생했을 때 각 체인의 동일한 위치에서 충돌이 발생하지 않는 한 체인은 병합되지 않습니다.이렇게 하면 검색 루틴이 [1]체인에 사용된 첫 번째 감소 함수의 인덱스를 통해 반복되어야 하므로 검색당 필요한 단계 수를 제곱하는 비용으로 주어진 테이블 크기에 대해 올바른 균열이 발생할 가능성이 높아집니다.
무지개 테이블은 작성된 해시 함수에 고유합니다.예를 들어 MD5 테이블은 MD5 해시만 크래킹할 수 있습니다.이 기법의 이론은 Philippe Oechslin이[3] Windows 패스워드 크래커 Ofcrack에서 구현한 시간/[1]메모리 교환의 빠른 형태로 발명했습니다.더 강력한 RainbowCrack 프로그램은 LM 해시, MD5, SHA-1을 포함한 다양한 문자 집합과 해시 알고리즘에 대해 무지개 테이블을 생성하고 사용할 수 있는 프로그램이 나중에 개발되었습니다.
reduction 함수와 hash 함수가 충돌하지 않는 단순한 경우 완전한 무지개 테이블(해시가 주어진 경우 대응하는 패스워드를 반드시 찾는 것)이 주어진 경우, 패스 세트 P의 크기, 테이블 계산에 필요했던 시간 T, 테이블 L의 길이 및 패스 발견에 필요한 평균 시간 T특정 해시에 일치하는 단어는 직접 [citation needed]관련이 있습니다.
따라서, 8 문자의 소문자 영숫자 패스워드 케이스(P 3 3 × 1012)는 퍼스널컴퓨터로 간단하게 처리할 수 있는 반면, 16 문자의 소문자 영숫자 패스워드 케이스(P25 ) 10)는 전혀 다루기 어렵습니다.
레인보우 테이블 방어
무지개 테이블은 큰 소금을 포함하는 단방향 해시에 대해 효과가 없습니다.예를 들어, 다음 함수를 사용하여 생성되는 암호 해시를 고려합니다(여기서 "+"는 연결 연산자임).
saltedhash(password) = hash(password + salt)
또는
saltedhash(password) = hash(hash(password) + salt)
salt 값은 기밀이 아니며 임의로 생성되어 비밀번호 해시와 함께 저장될 수 있습니다.salt 값이 크면 각 사용자의 암호가 고유하게 해시되므로 무지개 테이블을 비롯한 사전 계산 공격을 방지할 수 있습니다.즉, 같은 패스워드를 가지는 2명의 유저의 패스워드 해시가 다릅니다(다른 솔트가 사용되고 있는 경우).이를 성공시키려면 공격자는 가능한 각 salt 값에 대해 테이블을 미리 계산해야 합니다.솔트는 충분히 커야 합니다.그렇지 않으면 공격자는 각 솔트 값에 대한 테이블을 작성할 수 있습니다.12비트 salt를 사용한 오래된 Unix 패스워드의 경우 4096개의 테이블이 필요합니다.이는 공격자에 대한 비용이 크게 증가하지만 테라바이트 하드 드라이브에서는 비현실적이지 않습니다.SHA2 암호화 및 bcrypt 방식(Linux, BSD Unix 및 Solaris에서 사용됨)은 [4]128비트입니다.이러한 salt 값이 크면 패스워드의 거의 모든 길이에 대해 이러한 시스템에 대한 사전 계산 공격이 불가능합니다.공격자가 초당 100만 개의 테이블을 생성할 수 있다고 해도 가능한 모든 소금의 테이블을 생성하려면 수십억 년이 필요합니다.
사전 컴퓨팅 공격을 방지하는 또 다른 기술은 키 스트레칭입니다.스트레칭을 사용하면 기본 해시 함수를 통해 salt, password 및 일부 중간 해시 값이 여러 번 실행되어 각 [5]암호를 해시하는 데 필요한 계산 시간이 늘어납니다.예를 들어 MD5-Crypt에서는 salt, password 및 현재 중간 해시 값을 기본 MD5 해시 [4]함수에 반복적으로 공급하는 1000 반복 루프가 사용됩니다.사용자의 패스워드 해시는 salt값(비밀)과 최종 해시의 결합입니다.로그인 할 때마다 불과 1초만 기다리면 되기 때문에 사용자는 여분의 시간을 알아차릴 수 없습니다.한편, 스트레칭은 반복 횟수에 비례하여 공격자가 일정 기간 동안 수행할 수 있는 시도 횟수를 줄이기 때문에 브루트 포스 공격의 효과를 감소시킵니다.이 원리는 MD5-Crypt [6]및 bcrypt에 적용됩니다.이것은 또한 미리 계산된 표를 만드는 데 필요한 시간을 크게 증가시키지만, 소금이 없을 때는 한 번만 수행하면 됩니다.
키 강화라고 불리는 대체 접근법은 임의의 소금으로 키를 연장하지만 (키 신장과는 달리) 안전하게 소금을 삭제합니다.이로 인해 공격자와 정규 사용자 모두 salt [7]값에 대해 brute-force 검색을 수행합니다.키[8] 스트레칭을 소개한 논문은 이 이전 기술을 언급하고 의도적으로 다른 이름을 선택했지만, "키 강화"라는 용어는 종종 키 스트레칭을 지칭하는 데 사용되고 있습니다(논쟁적으로 잘못되었을 수 있습니다.
레인보우 테이블 및 기타 사전 계산 공격은 사전 설정된 범위를 벗어난 기호를 포함하거나 공격자가 미리 계산한 것보다 긴 암호에 대해서는 작동하지 않습니다.단, 사용자가 숫자나 특수문자를 추가하는 등 보다 안전한 비밀번호를 선택하는 일반적인 방법을 고려한 테이블을 생성할 수 있습니다.컴퓨팅 처리에 대한 상당한 투자 때문에 길이가 14개소를 넘는 무지개 테이블은 아직 흔하지 않습니다.따라서 14자보다 긴 비밀번호를 선택하면 공격자가 무차별적인 방법을 [citation needed]사용해야 할 수 있습니다.
Microsoft가 사용하는 오래된 해시 알고리즘인 LM 해시에 초점을 맞춘 구체적인 집중적인 노력이 공개되어 있습니다.LM 해시는 특히 취약합니다.이는 7자를 넘는 패스워드가 2개의 섹션으로 분할되어 각 섹션이 개별적으로 해시되기 때문입니다.15자 이상의 비밀번호를 선택하면 LM 해시가 [9]생성되지 않습니다.
일반적인 용도
Unix, Linux 및 BSD의 거의 모든 배포 및 변형은 솔트를 사용한 해시를 사용합니다.단, 많은 응용 프로그램은 솔트를 사용하지 않고 해시(일반적으로 MD5)만 사용합니다.Microsoft Windows NT/2000 패밀리는 LAN Manager 및 NT LAN Manager 해시 방식(MD4 기반)을 사용하고 있으며 무염이므로 가장 많이 생성되는 테이블 중 하나입니다.레인보우 테이블은 염분이 더 일반화되고 GPU 기반의 무차별 공격도 더 실용화됨에 따라 2020년 현재 사용량이 감소했습니다.단, 레인보우 테이블은 8글자 및9글자의 NTLM [10]패스워드에 사용할 수 있습니다.
「 」를 참조해 주세요.
메모들
- ^ a b c Oechslin, P. (2003). "Making a Faster Cryptanalytic Time-Memory Trade-Off" (PDF). Advances in Cryptology - CRYPTO 2003. LNCS. Vol. 2729. pp. 617–630. doi:10.1007/978-3-540-45146-4_36. ISBN 978-3-540-40674-7.
- ^ a b Hellman, M. (1980). "A cryptanalytic time-memory trade-off" (PDF). IEEE Transactions on Information Theory. 26 (4): 401–406. CiteSeerX 10.1.1.120.2463. doi:10.1109/TIT.1980.1056220. ISSN 0018-9448.
- ^ "LASEC - Security and Cryptography Laboratory: Dr Philippe Oechslin - Research". Faculté I&C - School of Computer and Communication Sciences. March 2004.
- ^ a b Alexander, Steven (June 2004). "Password Protection for Modern Operating Systems" (PDF). Login. USENIX Association. 29 (3).
- ^ Ferguson, Neils; Bruce Schneier (2003). Practical Cryptography. Indianapolis: John Wiley & Sons. ISBN 978-0-471-22357-3.
- ^ Provos, Niels; Mazières, David (June 6, 1999). "A Future-Adaptable Password Scheme" (PDF). Proceedings of the FREENIX Track: 1999 USENIX Annual Technical Conference. Monterey, CA, USA: USENIX Association.
- ^ Manber, U. (1996). "A simple scheme to make passwords based on one-way functions much harder to crack" (PDF). Computers & Security. 15 (2): 171–176. CiteSeerX 10.1.1.102.2597. doi:10.1016/0167-4048(96)00003-X.
- ^ Kelsey, J.; Schneier, B.; Hall, C.; Wagner, D. (1998). "Secure applications of low-entropy keys" (PDF). Information Security. LNCS. Vol. 1396. p. 121. doi:10.1007/BFb0030415. ISBN 978-3-540-64382-1.
- ^ "How to prevent Windows from storing a LAN manager hash of your password in Active Directory and local SAM databases". Microsoft. 24 September 2021.
- ^ "A Case for Modern Rainbow Table Usage". rainbowcrackalack.com. Positron Security. 26 February 2021.
레퍼런스
- Oechslin, Philippe (2003-08-17). "Making a Faster Cryptanalytic Time-Memory Trade-Off". Making a Faster Cryptanalytical Time-Memory Trade-Off (PDF). Advances in Cryptology: Proceedings of CRYPTO 2003, 23rd Annual International Cryptology Conference. Lecture Notes in Computer Science. Vol. 2729. Santa Barbara, California, USA: Springer. pp. 617–630. doi:10.1007/978-3-540-45146-4_36. ISBN 978-3-540-40674-7.
외부 링크
- 필립 오크랙 페이지 오리지널 레인보우 테이블 리서치
- Curlie에서의 암호화
| |||||||||||||||||||||||||||||
