John the Ripper 와 레인보우 테이블 (개념적)

소개

사이버 보안 분야에서 비밀번호가 어떻게 보호되는지, 그리고 반대로 어떻게 손상될 수 있는지를 이해하는 것은 매우 중요합니다. 이 랩에서는 두 가지 기본 개념을 소개합니다. 바로 강력한 비밀번호 크래킹 도구인 John the Ripper 와 암호화 해시 함수를 역으로 변환하는 데 사용되는 사전 계산된 테이블인 레인보우 테이블 (Rainbow Tables) 입니다. John the Ripper 는 다양한 공격 방법을 사용할 수 있지만, 이 랩에서는 레인보우 테이블과 함께 사용하는 것에 대해 개념적으로 초점을 맞출 것입니다.

레인보우 테이블의 기본 원리를 탐구하고, 무차별 대입 공격 (brute-force attacks) 과의 효율성을 비교하며, 가장 효과적인 시나리오를 파악하고, 내재된 한계를 이해하게 될 것입니다. 마지막으로, 레인보우 테이블이 어떻게 생성되는지에 대해 개념적으로 논의할 것입니다. 이 랩은 실제 레인보우 테이블 작업의 복잡성과 리소스 집약도 때문에 실제적인 적용보다는 이러한 도구와 기술에 대한 이론적인 이해를 제공하도록 설계되었습니다.

레인보우 테이블 원리 이해

이 단계에서는 레인보우 테이블의 핵심 원리를 자세히 살펴보겠습니다. 레인보우 테이블은 암호화 해시 함수를 역으로 변환하는 데 사용되는 사전 계산된 테이블로, 주로 비밀번호 해시를 크래킹하는 데 사용됩니다. 가능한 모든 비밀번호 (무차별 대입) 나 사전의 모든 단어를 시도하는 대신, 레인보우 테이블은 사전 계산된 해시 값과 해당 평문 값의 체인 (chain) 을 저장합니다.

기본적인 아이디어는 계산 시간과 저장 공간을 맞바꾸는 것입니다. 시스템이 비밀번호를 저장할 때, 일반적으로 평문 비밀번호 자체가 아니라 해당 해시 값을 저장합니다. 예를 들어, 비밀번호가 password123이라면 시스템은 MD5 해시인 4d7d7e7e7e7e7e7e7e7e7e7e7e7e7e7e를 저장할 수 있습니다. 로그인 시도를 하면 입력한 비밀번호가 해시되고, 이 해시 값이 저장된 해시와 비교됩니다.

레인보우 테이블은 해시와 평문 값의 긴 "체인"을 생성하여 작동합니다. 평문으로 시작하여 해시하고, 해시에 "감소 함수 (reduction function)"를 적용하여 다른 평문을 얻은 다음, 그것을 해시하는 과정을 반복합니다. 이러한 체인의 시작점과 끝점만 테이블에 저장됩니다.

간단한 예시를 살펴보겠습니다.

1. 평문 P1로 시작합니다.
2. P1을 해시하여 H1을 얻습니다.
3. H1에 감소 함수 R을 적용하여 P2를 얻습니다.
4. P2를 해시하여 H2를 얻습니다.
5. H2에 R을 적용하여 P3을 얻습니다.
   ...이하 사전 정의된 체인 길이만큼 반복합니다.

크래킹하려는 대상 해시 HT가 있을 때, 감소 함수 R을 HT에 적용하여 잠재적인 평문 P_temp를 얻습니다. 그런 다음 P_temp를 해시하고 다시 R을 적용하는 과정을 반복하여 레인보우 테이블에 저장된 끝점 중 하나와 일치하는 해시를 생성합니다. 일치하는 항목이 발견되면 테이블에서 해당 시작점을 검색하고 해당 시작점부터 체인을 다시 생성하여 대상 해시 HT를 생성한 평문을 찾습니다.

이 방법은 대부분의 무거운 작업 (해싱 및 감소) 이 테이블 생성 단계에서 미리 수행되기 때문에 크래킹 시점에 필요한 계산량을 크게 줄여줍니다.

이해를 확인하기 위해 레인보우 테이블 사용과 관련된 절충점을 고려해 보십시오.

레인보우 테이블과 무차별 대입 공격 비교

이 단계에서는 레인보우 테이블과 전통적인 무차별 대입 공격 방법을 비교합니다. 각 방법의 차이점을 이해하면 장단점을 명확히 파악할 수 있습니다.

무차별 대입 공격 (Brute-Force Attack):
무차별 대입 공격은 올바른 비밀번호를 찾을 때까지 가능한 모든 문자 조합 (문자, 숫자, 기호) 을 시도합니다. 예를 들어, 4 자리 소문자 알파벳 비밀번호를 크래킹하려면 aaaa, aaab, aaac, ..., zzzz를 시도합니다.

• 장점: 충분한 시간과 리소스가 있다면 비밀번호를 찾을 것이 보장됩니다. 사전 계산이 필요하지 않습니다.
• 단점: 특히 더 길고 복잡한 비밀번호의 경우, 극도로 시간이 많이 소요되고 계산 집약적입니다. 각 추측마다 새로운 해시 계산이 필요합니다.

레인보우 테이블 공격 (Rainbow Table Attack):
이전 단계에서 논의했듯이, 레인보우 테이블 공격은 사전 계산된 해시 체인을 사용하여 해시를 역으로 변환합니다.

• 장점: 테이블이 생성되면 대량의 해시를 크래킹하는 데 무차별 대입 공격보다 훨씬 빠릅니다. 일반적인 비밀번호에 대한 반복적인 해시 계산을 피합니다.
• 단점: 사전 계산된 테이블을 위해 상당한 저장 공간이 필요합니다. 테이블은 특정 해시 알고리즘 (예: MD5, SHA1) 및 종종 특정 문자 집합 및 비밀번호 길이 범위에 따라 달라집니다. "솔트 (salted)" 해시 (해시하기 전에 비밀번호에 무작위 문자열이 추가되는 경우) 에는 효과가 떨어집니다. 각 솔트마다 새롭고 고유한 레인보우 테이블이 필요하기 때문입니다.

라이브러리에서 특정 책을 찾아야 하는 비유를 통해 차이점을 설명해 보겠습니다.

• 무차별 대입: 첫 번째 선반부터 시작하여 각 책을 집어 제목을 읽고 찾고 있는 책인지 확인합니다. 찾을 때까지 모든 책에 대해 이 작업을 수행합니다. 이는 철저하지만 느립니다.
• 레인보우 테이블: 누군가 이미 도서관을 훑어보고 특정 책 제목과 해당 책이 있는 선반 위치를 매핑하는 인덱스 (레인보우 테이블) 를 만들었습니다. 책이 필요할 때 인덱스를 참조하면 올바른 영역을 빠르게 알려주므로 모든 책을 확인하는 노력을 절약할 수 있습니다. 그러나 해당 인덱스를 처음 만드는 데는 많은 노력과 공간이 필요했습니다.

비밀번호 해싱에 "솔트"가 존재하면 레인보우 테이블 공격의 효과에 어떤 영향을 미칠지 고려해 보십시오.

레인보우 테이블 사용 시나리오 식별

이 단계에서는 레인보우 테이블이 가장 효과적이고 일반적으로 사용되는 특정 시나리오를 식별합니다. 최신 해싱 관행으로 인해 효과가 감소했지만, 개념적 및 역사적 사용 사례를 이해하는 것이 중요합니다.

레인보우 테이블은 다음과 같은 상황에서 특히 유용합니다.

1. 대규모 비밀번호 크래킹 (솔트되지 않은 해시): 주요 이점은 대량의 솔트되지 않은 비밀번호 해시를 크래킹하는 데 있습니다. 공격자가 솔트되지 않은 MD5 또는 SHA1 해시 데이터베이스를 획득한 경우, 사전 계산된 레인보우 테이블을 사용하여 많은 해시에 대한 평문 비밀번호를 신속하게 찾을 수 있습니다. 이는 동일한 해시 값이 항상 동일한 평문에 해당하므로 테이블을 여러 대상에 재사용할 수 있기 때문입니다.

2. 오프라인 공격: 레인보우 테이블은 오프라인 공격에 사용됩니다. 즉, 공격자는 이미 해시 값을 획득했으며 (예: 손상된 데이터베이스 또는 네트워크 스니핑을 통해) 대상 시스템과 상호 작용하지 않고 이를 크래킹하려고 시도합니다. 이는 일반적으로 속도 제한이 있는 로그인 양식에 직접 비밀번호를 시도하는 온라인 공격과 대조됩니다.

3. 알려진 해시 알고리즘: 레인보우 테이블은 특정 해시 알고리즘 (예: MD5, SHA-1, NTLM) 에 대해 생성되어야 합니다. 대상 시스템이 알 수 없거나 사용자 정의 해싱 알고리즘을 사용하는 경우 사전 계산된 레인보우 테이블은 쓸모가 없습니다.

4. 크래킹을 위한 제한된 계산 리소스 (하지만 생성에는 충분): 레인보우 테이블을 생성하는 것은 계산 집약적이지만, 이를 사용하여 해시를 크래킹하는 것은 상대적으로 빠릅니다. 따라서 초기 테이블 생성을 위해 강력한 리소스에 액세스할 수 있지만, 덜 강력한 기계나 시간 제약이 있는 환경에서 빠른 크래킹을 수행해야 하는 공격자에게 적합합니다.

5. 일반/취약한 비밀번호 크래킹: 레인보우 테이블은 사전 계산된 체인에 포함될 가능성이 높은 일반적이고 짧거나 간단한 비밀번호에 가장 효과적입니다. 복잡하거나 길거나 진정한 무작위 비밀번호는 일반적인 레인보우 테이블에서 찾기 어렵거나 비현실적으로 큰 테이블이 필요할 수 있습니다.

bcrypt, scrypt, Argon2 와 같은 강력하고 느린 해싱 알고리즘을 사용하고, 가장 중요하게는 각 비밀번호에 고유한 무작위 값을 **솔트 (salting)**하는 현대적인 비밀번호 저장 관행이 레인보우 테이블의 효과를 크게 완화했다는 점에 유의하는 것이 중요합니다. 솔팅은 두 사용자가 동일한 비밀번호를 가지고 있더라도 저장된 해시가 다르도록 보장하여 일반적인 레인보우 테이블을 쓸모없게 만듭니다.

공격자가 솔트되지 않은 MD5 비밀번호 해시 목록을 획득한 시나리오를 생각해 보십시오. 레인보우 테이블이 그들에게 효율적인 도구가 될까요?

레인보우 테이블의 한계 이해

이 단계에서는 레인보우 테이블의 상당한 한계를 살펴보고, 이로 인해 최신 사이버 보안 관행에서 효과가 감소한 이유를 알아봅니다.

1. 솔팅 (Salting): 이것이 가장 중요한 한계입니다. "솔트"는 해시되기 전에 비밀번호에 추가되는 무작위 데이터 문자열입니다. 예를 들어 비밀번호가 password123이고 솔트가 xyz라면, 시스템은 password123xyz를 해시합니다. 각 사용자는 일반적으로 고유한 솔트를 받기 때문에, 두 사용자가 동일한 비밀번호를 가지고 있더라도 저장된 해시는 다릅니다. 이는 MD5(password)에 대해 생성된 레인보우 테이블이 MD5(password + salt)에는 작동하지 않음을 의미합니다. 솔트된 해시를 레인보우 테이블로 크래킹하려면, 공격자는 각 고유 솔트마다 별도의 레인보우 테이블을 생성해야 하는데, 이는 많은 사용자에게는 사실상 불가능합니다.

2. 생성 시 계산 비용: 레인보우 테이블을 사용하는 것은 빠르지만, 하나를 생성하는 것은 극도로 계산 집약적이고 시간이 많이 소요됩니다. 광범위한 문자 및 길이를 포괄하는 포괄적인 테이블의 경우, 강력한 하드웨어에서도 몇 주, 몇 달 또는 몇 년이 걸릴 수 있습니다.

3. 저장 공간 요구 사항: 레인보우 테이블은 방대한 저장 공간을 필요로 합니다. 특정 해시 알고리즘에 대한 일반적인 비밀번호를 크래킹하도록 설계된 테이블은 쉽게 테라바이트의 디스크 공간을 차지할 수 있습니다. 이는 많은 공격자에게 비현실적입니다.

4. 해시 알고리즘에 대한 특정성: 레인보우 테이블은 특정 해싱 알고리즘 (예: MD5, SHA-1, NTLM) 에 대해 생성됩니다. 다른 알고리즘으로 생성된 해시를 크래킹하는 데 사용할 수 없습니다. 시스템이 MD5 에서 SHA-256 으로 전환하면 이전 MD5 레인보우 테이블은 쓸모없게 됩니다.

5. 강력한 해시에 대한 효과: bcrypt, scrypt, Argon2 와 같은 최신 "느린" 해싱 알고리즘은 계산 비용이 많이 들도록 설계되어 무차별 대입 및 레인보우 테이블 공격을 훨씬 느리게 만듭니다. 이러한 알고리즘은 의도적으로 계산 지연을 추가하여 초당 수백만 개의 해시 계산을 더 어렵게 만듭니다.

6. 제한된 범위: 레인보우 테이블은 유한한 수의 사전 계산된 체인만 포함할 수 있습니다. 사전 계산된 세트에 포함되지 않은 비밀번호 (예: 매우 길거나 복잡하거나 진정한 무작위 비밀번호) 는 크래킹할 수 없습니다.

이러한 한계, 특히 솔팅 및 강력한 해싱 알고리즘의 광범위한 채택으로 인해, 레인보우 테이블은 최신 비밀번호 저장 시스템에 대해 훨씬 효과가 떨어집니다. 그러나 역사적인 공격 방법과 적절한 비밀번호 보안 관행의 중요성을 이해하는 데 관련 개념으로 남아 있습니다.

솔팅이 레인보우 테이블에 대한 가장 효과적인 대응책으로 간주되는 이유를 고려해 보십시오.

레인보우 테이블 생성 논의 (개념적)

이 마지막 단계에서는 레인보우 테이블 생성 과정을 개념적으로 논의합니다. 복잡성과 리소스 요구 사항 때문에 실제 생성을 수행하지는 않겠지만, 기본 프로세스를 이해하는 것이 중요합니다.

레인보우 테이블 생성은 해시 체인을 만들기 위한 일련의 반복적인 단계를 포함합니다.

1. 매개변수 정의:

   • 해시 함수: 테이블이 생성될 특정 암호화 해시 함수 (예: MD5, SHA-1, NTLM) 를 선택합니다.
   • 문자 집합: 가능한 비밀번호가 포함할 수 있는 문자 집합 (예: 소문자, 대문자, 숫자, 기호) 을 정의합니다.
   • 비밀번호 길이 범위: 포함할 비밀번호의 최소 및 최대 길이를 지정합니다.
   • 체인 길이 (k): 각 체인에 몇 개의 해시 - 축소 단계가 포함될지 결정합니다. 체인이 길수록 저장해야 할 시작/끝 지점이 줄어들지만, 크래킹 시 계산량이 늘어납니다.
   • 체인 수 (m): 생성할 고유 체인의 수를 결정합니다. 체인이 많을수록 커버리지가 증가하지만 테이블 크기도 커집니다.

2. 초기 평문 선택:

   • 정의된 문자 집합 및 길이 범위에서 시작 평문 P_start를 무작위로 선택합니다. 이 P_start는 체인의 "시작 지점"이 됩니다.

3. 체인 생성 루프:

   • 각 P_start에 대해 k번의 반복 (여기서 k는 체인 길이) 을 수행합니다.
   • 해시: 현재 평문 P_i를 해시하여 해시 H_i를 얻습니다.
   • 축소: 축소 함수 R_j를 H_i에 적용하여 유효한 평문 P_{i+1}으로 다시 변환합니다. 축소 함수는 매우 중요하며, 해시 값을 정의된 문자 집합 및 길이 내의 유효한 평문으로 다시 매핑하도록 설계되어야 합니다. 중요하게도, "충돌"(두 개의 다른 체인이 하나로 병합되는 현상) 을 방지하기 위해 체인 내의 각 단계 j에서 종종 다른 축소 함수 R_j가 사용됩니다.

4. 끝점 저장:

   • k번의 반복 후 최종 해시 H_k와 최종 평문 P_end를 얻게 됩니다. 레인보우 테이블에 (P_start, P_end) 쌍을 저장합니다. 체인의 중간 값은 저장되지 않고 이 두 지점만 저장됩니다.

5. 반복:

   • 원하는 수의 고유 체인을 생성하기 위해 m번 (여기서 m은 체인 수) 반복하여 단계 2-4 를 반복합니다.

레인보우 테이블 생성의 핵심 과제는 효과적인 축소 함수를 설계하고 방대한 양의 데이터를 관리하는 데 있습니다. ophcrack 및 hashcat(하지만 hashcat은 무차별 대입/사전 공격에 더 중점을 두지만 사전 계산된 테이블을 사용할 수 있음) 과 같은 도구는 레인보우 테이블을 생성하고 활용하는 데 사용할 수 있는 소프트웨어의 예입니다. John the Ripper 는 주로 비밀번호 크래커이지만, 사전 계산된 테이블과 함께 사용하거나 사전 및 무차별 대입 공격을 수행하는 데에도 사용할 수 있습니다.

레인보우 테이블 생성에 대한 이러한 개념적 이해는 강력하지만 제한적인 크래킹 도구를 만드는 데 필요한 상당한 사전 계산 및 저장 투자를 강조합니다.

요약

이 개념적 실습을 통해 John the Ripper 와 레인보우 테이블에 대한 기초적인 이해를 얻었습니다. 레인보우 테이블은 암호화 해시 함수를 역으로 변환하는 데 사용되는 사전 계산된 테이블로, 저장 공간을 희생하여 크래킹 속도를 높이는 방식임을 배웠습니다. 레인보우 테이블과 무차별 대입 공격을 비교하며, 솔트되지 않은 대규모 해시 집합에 대한 레인보우 테이블의 효율성을 강조했지만, 상당한 저장 및 생성 비용도 함께 언급했습니다.

레인보우 테이블이 역사적으로 효과적이었던 시나리오, 주로 손상된 데이터베이스에서 솔트되지 않은 해시를 오프라인으로 크래킹하는 경우를 파악했습니다. 결정적으로, 레인보우 테이블의 주요 한계를 탐구했으며, 솔팅이 현대 비밀번호 저장 관행에 대해 대부분 비효과적으로 만드는 가장 중요한 대응책임을 알게 되었습니다. 마지막으로, 매개변수 정의, 해시 체인 생성, 시작 및 끝점만 저장하는 과정을 포함하는 레인보우 테이블 생성의 복잡한 과정을 개념적으로 논의했습니다.

이 실습은 비밀번호 보안의 발전과 공격자와 방어자 간의 지속적인 군비 경쟁을 강조하며, 사이버 보안의 이러한 중요한 개념을 이해하는 데 이론적 기반을 제공합니다.