패스워드 크래킹
패스워드 관리
보안 관리자의 첫번째 방어책
좋지 못한(크래킹되기 쉬운) 패스워드
1. 길이가 너무 짧거나 널(NULL)인 패스워드
2. 사전에 나오는 단어나 이들의 조합으로 이루어진 패스워드
3. 키보드에서 일렬로 키를 나열한 패스워드
4. 사용자 계정 정보에서 유추 가능한 단어들로 구성한 패스워드
좋은 패스 워드 : 기억하기는 쉽고 크래킹하기 어려운 패스워드
요즘 패스워드에 대한 제약이 많아짐. ex) 대문자, 특수문자를 섞거나 알파벳, 숫자를 순서로 사용하지 못하게 함
해시와 암호화
해시(Hash): 임의의 데이터로부터 일종의 짧은 '전자 지문'을 만들어 내는 방법
암호화(Encryption): 특별한 알고리즘을 이용해 데이터를 전달하는 것
해시 알고리즘을 이용하면, 패스워드를 해시된 문자열로 변경 가능하나, 해시된 문자열을 원래의 패스워드로 변경하는 것, 즉 역해시는 원천적으로 봉쇄되어있다. (역함수를 구하는 것이, 복구가 불가능!)
암호화는 해시와 달리 키 값을 이용하여 암호화된 문자열로 변경하기기 때문에, 암호화된 문자열을 키 값을 이용해 원래의 패스워드로 복호화 하는 것이 가능하다.
로마시대 암호화 방식: 기본적인 치환 방식
3자씩 알파벳을 밀어내 대응되는 글자로 치환
cafe => zxcb => cafe
123456789의 Hash값: 2677861
123486789의 Hash값: 4569155
Hash값 앞 6자리의 숫자를 버리기 때문에, 방법(로직)을 알더라도 앞의 1.81838과 1.81882를 알아낼 방법이 없다. 그렇기에 원래의 수를 알아내는 것은 불가능!
즉, Hash는 로직을 알고 있을 경우 해시의 결과 값을 구하기가 쉽다. 하지만 Hash의 결과 값을 통해 생성하기 전의 원래 값을 알기 어렵다. + 값이 아주 조금만 다르더라도 Hash 결과 값은 무척 상이하게 생성된다.
Salt
Hash나 암호화로 패스워드를 저장 -> 같은 패스워드에 대해 같은 Hash값, 같은 암호문으로 저장
=> 같은 Hash 결과나 암호문은 같은 결과만으로도 패스워드를 노출시키는 약점이 발생!
운영체제 별로 다양한 Hash 알고리즘이 존재 ex) 'eodlf@!11'을 MD5 알고리즘 Hash
Salt는 위와 같은 상황을 막기 위해 패스워드 Hash와 암호화에 사용되는 첨가물의 일종
패스워드 파일에 저장 시 MD5 Hash 값만 저장 불가능. 왜냐하면 시스템이 어떤 것(Salt)을 합해 Hash를 구한 것인지 알 수 없기 때문에 사용자가 비밀번호를 입력하더라도 Salt를 알수 없으니 로그인이 불가능하게 되는 경우가 발생한다.
그러한 상황을 방지하기 위해 패스워드 파일에 저장 시 간단한 인코딩을 통해 Hash 결과 값 앞이나 뒤에 어떤 것(Salt)을 합하였는지 를 붙여준다. 그렇게 하면 어떠한 Salt값을 이용하여 패스워드를 Hash했는지 알 수 있게 된다.
로그인이 되는 방식
서버 패스워드 파일에 ID와 비밀번호가 저장이 되어 있다고 가정해보자. 비밀번호는 MD5 알고리즘을 이용하였다.
사용자가 입력한 password에 대해 Salt값 4F(password)를 MD5 알고리즘을 통해 Hash값을 결과값을 도출해 낸 후 뒤에 password가 초록색 칸과 같은지 비교하는 방식이다.
사용자가 입력한 ID와 비밀번호를 패스워드 파일에 저장되어있는 ID, 비밀번호와 단순 비교한다면 얼마나 간단하고 좋을까? 하지만 이러한 방식을 이용한다면 같은 패스워드에 대해 같은 Hash값, 암호화 값을 가지게 되기 때문에 보안상 매우 취약해진다는 큰 단점이 존재한다.
Salt를 적용하는 것만으로 똑같은 패스워드를 다르게 숨길 뿐만 아니라 적용 수준에 따라 패스워드 크래킹을 매우 어렵게 만들어주기에 보안상으로도 철저해진다. Hash에 Salt만 넣었는데 너무 맛있네 ~
패스워드 크래킹의 이해
(ID와 Hash값을 안다고 가정)
1. 사전대입 공격
사용자가 설정하는 대부분의 패스워드에 특정 패턴이 있음에 착안
패스워드를 사용할 만한 것을 사전으로 만들어놓고 하나씩 대입해 패스워드(Hash값) 일치 여부 확인
ex) Hash값을 알고있으니 사전에 있는 단어를 MD5 혹은 어떠한 알고리즘을 통해 Hash값과 같은지 비교하는 방법
2. 무작위 대입 공격(Brute force Attack)
패스워드에 사용될 수 있는 문자열의 범위를 정하고, 그 범위 내에서 생성 가능한 모든 패스워드를 생성하여 입력
패스워드가 그다지 복잡하지 않거나, 요즘 컴퓨터가 좋아서 짧을 경우 단시간에 크래킹
안쓰는 이유? 시간이 너무 오래걸리고, 몇회이상 실패시 잠김기술 등이 생겨나서 사실 불가능에 가까운 방법
ex) Hash값을 알고있으니, 무작위로 값을 패스워드를 생성해 MD5 알고리즘을 통해 Hash값과 같은지 비교
#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
#define PWD_SIZE 16
int first_cnt = 0;
int second_cnt = 0;
int locat = 0;
char myPwd[PWD_SIZE] = "Tlqkf!1234";
char pwdHack[PWD_SIZE];
char bruteHack[PWD_SIZE];
void GetPwd(); // Pwd를 알고있던 경우, 즉 Hash값을 아는 경우에 가능한 방법!
bool GetBrutePwd(int, int); // Pwd를 모르는 경우, 모든방법을 이용!
bool checkPwd(char*, char*); // Pwd를 비교하는 함수
void main() {
//GetPwd();
//printf("==hash값을 아는 경우==\n");
//printf("대입횟수: %d\n", first_cnt);
//printf("비밀번호: %s\n", pwdHack);
printf("★★Brute Force Attack★★\n");
for (int i = 1; i < PWD_SIZE; i++)
if (GetBrutePwd(0, i) == true) break;
if (checkPwd(myPwd, bruteHack)) {
printf("login 성공!\n");
printf("대입횟수: %d\n", second_cnt);
printf("비밀번호: %s\n", bruteHack);
}
else {
printf("비밀번호 너무 어렵네 ^^;");
}
}
void GetPwd() {
for (char alpha = 33; alpha <= 126 && myPwd[locat] != NULL; alpha++) {
first_cnt++;
if (myPwd[locat] == alpha) {
pwdHack[locat++] = alpha;
alpha = 33;
}
}
pwdHack[locat] = NULL;
return;
}
bool GetBrutePwd(int cnt, int size) {
if (cnt == size) {
//printf("%s\n", bruteHack);
}
else {
for (char i = 33; i <= 126; i++) {
second_cnt++;
bruteHack[cnt] = i;
if (checkPwd(myPwd, bruteHack)) return true;
GetBrutePwd(cnt + 1, size);
if (checkPwd(myPwd, bruteHack)) return true;
}
}
return false;
}
bool checkPwd(char pwd[16], char hack[16]) {
bool isSame = true;
for (int i = 0; pwd[i] != NULL; i++)
if (pwd[i] != hack[i]) isSame = false;
return isSame;
}
3. 레인보우 테이블을 이용한 공격
1980년 마틴 헬만에 의해 소개, 모든 Hash값에 대해서 미리 다 계산한 다음 table로 옮긴후 table에서 검색해서 패스워드를 도출해내는 방식
Hash의 경우의 수가 말도안되게 많기 때문에 이를 table에 저장하는 것은 메모리도 많이 먹을 것이고 속도도 느리게 된다. 그래서 생각한 방법이 table을 압축하자. 압축을 통해 메모리의 크기를 엄청 줄이게 됨. ex) 일반 테이블: TB -> 압축파일: GB
레인보우 테이블의 또 다른 핵심 아이디어
대용량으로 생성될 수 있는 해시 테이블을 R(Reduction) 함수를 이용해 작은 크기로 줄이는 것
패스워드가 6자리 숫자로 이루어진 '234342'
MD5 Hash 값 'C1F2FE224298D6E39EBA607D46F3D9CC'
R 함수는 이 Hash값에서 또 다른 형태의 무작위 패스워드 추출
R 함수가 MD5 Hash 값 중 앞의 6개 숫자만 뽑아낸다고 가정
R(C1F2FE224298D6E39EBA607D46F3D9CC)은 '122242'
그렇게 하여 첫번째 패스워드값과 R을 2번실행하였을 때 나온 MD5 Hash 값을 저장
최종 table을 생성하면서 기존의 레인보우 table들은 삭제하는 것이 아니라, 최종 table을 통해 유추해낸 패스워드를 가지고 기존의 레인보우 테이블로 이동하는 것이다. 즉, 기존의 레인보우 테이블(위 그림은 3가지)과 최종 테이블이 같이 존재한다.
그래서 최종 table에서 최초의 패스워드 값과 마지막 Hash값만 가지고 어떻게 사용해?
문제를 통해 알아보자. 현재 패스워드의 해시 값 '570727EE4270E0C1A4D8FBB741926DB8'
1. 최종 table[표 4-7]에서 MD5 Hash 값이 있는지 확인하자.
2. Hash값이 없기 때문에 R함수로 추출하자. -> 570727
3. 추출해낸 패스워드(570727)를 기준으로 Hash값을 생성한다. -> '86AB6B3355F33F7CD6265----'
4. 생성한 Hash값이 최종 table에 있는지 확인
-> 4-2. 생성한 Hash값이 최종 table에 존재하지 않는다면 R함수 반복
5. 생성한 Hash값이 최종 table에 존재한다면 생성한 Hash값에 해당하는 table의 Line으로 이동한다.
6. 이동한 Line에 찾고자 하는 Hash값에 대한 패스워드가 있는지 확인한다. -> 346343
중간중간 R함수를 동작하면서 생기는 MD5 Hash값은 뭐하는 용도?
중간중간 MD5 Hash값을 동작하면서 나오는 값들은 결국 최초의 패스워드 값을 찾기위한 용도로서 어떠한 방식으로 추출되는지를 확인하기 위한 방법이다.
★즉, R함수를 동작하면서 발생하는 패스워드들과 MD5 해시 값들은 최초의 패스워드와 해시값들을 치환한 값이라고 생각하자!
최초의 패스워드 값의 Hash값과 마지막 Hash값이 무슨 연관인데?
첫번째 단계에 주어진 Hash값이 최종 table에 존재하는지 확인하는데, 없을 경우 2,3,4 번을 반복한다. 그렇게 해서 만약 Hash값이 최종 table에 존재한다면 그 테이블로 이동해 Hash값과 비교한다음 맞다면 그 Hash값에 대한 비밀번호는 바로 옆에 저장되어있는 최초의 패스워드일 것이다.
Q) 레인보우 테이블 체인 2,000개 이상, 최초 패스워드, 최종 해시값만 레인보우 테이블에 저장
체인을 2,000개 사용하는 레인보우 테이블에서 해시 값을 1만개 저장하고 있다면 레인보우 테이블에서 확인할 수 있는 패스워드의 종류의 수는?
A) 2,000 * 10,000 = 20,000,000(개), 2천만개