해시 함수와 비밀번호 저장의 기본
많은 서비스는 사용자의 비밀번호를 그대로 저장하지 않고 SHA-256이나 MD5 같은 해시 함수를 이용해 변환한 값을 저장합니다. 해시 함수는 입력값을 넣으면 항상 같은 길이의 고정된 문자열을 출력하고, 결과값만 보고는 원래 입력을 역으로 계산해낼 수 없다는 특징이 있습니다. 그래서 데이터베이스가 유출되더라도 해시값만 있으면 공격자가 원본 비밀번호를 바로 알아내기 어렵다고 여겨져 왔습니다.
Rainbow Table 공격의 동작 원리
하지만 해시 함수는 같은 입력에 대해 항상 같은 출력을 내놓는다는 성질이 있습니다. 즉 ‘1234’를 해시하면 언제, 어디서 계산하든 동일한 결과가 나옵니다. 공격자는 이 점을 이용해 미리 수많은 비밀번호 후보와 그에 대응하는 해시값을 계산해 거대한 표로 만들어 둡니다. 이것이 바로 Rainbow Table입니다. 비유하자면 자물쇠 번호를 하나하나 맞춰보는 대신, 미리 만들어둔 ‘번호-열쇠 대응표’를 펼쳐놓고 훔친 열쇠 모양과 일치하는 번호를 찾는 것과 같습니다. 실제 계산을 매번 새로 하지 않고 표에서 값을 찾기만 하면 되기 때문에, 유출된 해시값을 이 표와 대조하는 것만으로 순식간에 원래 비밀번호를 알아낼 수 있습니다.
왜 해시만으론 안전하지 않은가, 그리고 Salt
문제는 전 세계 수많은 사용자가 ‘123456’, ‘qwerty’처럼 자주 쓰는 비밀번호를 반복해서 사용한다는 점입니다. 공격자는 이런 흔한 비밀번호들에 대해 미리 대규모 Rainbow Table을 구축해두고, 어떤 서비스의 DB가 유출되든 동일한 표로 대조 공격을 할 수 있습니다. 해시 자체는 안전해 보여도, ‘같은 입력은 같은 출력’이라는 성질 때문에 대량의 사전 계산 공격에는 취약한 것입니다.
이를 막기 위한 표준적인 방법이 Salt입니다. 각 사용자의 비밀번호에 무작위 문자열(salt)을 덧붙인 뒤 해시를 계산하면, 같은 비밀번호를 쓰는 사용자라도 저장되는 해시값이 모두 달라집니다. 그러면 공격자는 사용자마다 다른 salt에 맞춰 매번 새로 표를 만들어야 하므로, 미리 계산해둔 Rainbow Table이 무용지물이 됩니다. 여기에 더해 bcrypt, scrypt, Argon2처럼 계산 비용을 의도적으로 높인 해시 알고리즘을 사용하면, 대량 계산 자체를 어렵게 만들어 실무에서 훨씬 안전한 비밀번호 저장이 가능해집니다.