임의 길이의 데이터로부터 정해진 길이의 값(해시값)을 계산하는 함수. 암호에서 사용하는 것(SHA-256 등)은 해시값으로부터 원래 데이터를 구하는 것도, 같은 해시값이 되는 두 데이터를 찾는 것도 현실적으로 불가능하도록 만들어지며, 변조 검출, 디지털 서명, 비밀번호 저장에 사용된다.
일본어 명칭: ハッシュ関数
해시 함수(Hash Function)은(는) 정보 보안 기초, 자료 구조와 알고리즘, 양자 컴퓨터의 하드웨어 등 3개 분야의 연습 문제 8개에 나와요.
분야: 정보 보안 기초
암호에서 사용하는 해시 함수에는 세 가지 성질이 요구됩니다. 역상 저항성(일방향성)은 해시값으로부터 그 해시값이 되는 입력을 찾기가 어렵다는 것입니다. 제2 역상 저항성은 어떤 입력이 주어졌을 때 같은 해시값이 되는 다른 입력을 찾기가 어렵다는 것입니다. 충돌 저항성은 같은 해시값이 되는 서로 다른 두 입력을 아무것이나 찾기가 어렵다는 것입니다. 또한 입력이 1비트만 달라도 출력의 약 절반의 비트가 바뀌는 성질(눈사태 효과)도 가집니다.
출력이 n비트인 이상적인 해시 함수에서는 역상을 무차별 대입로 찾으려면 대략 2^n회의 계산이 필요하지만, 충돌은 생일 역설에 의해 약 2^(n/2)회로 찾을 가능성이 높아집니다. 이 때문에 SHA-256의 충돌에 대한 강도는 약 128비트 상당으로 여겨집니다. MD5나 SHA-1은 무차별 대입보다 훨씬 적은 계산으로 충돌을 만드는 방법이 발견되었으므로, 디지털 서명 등 안전이 필요한 용도에는 사용하지 않게 되어 있습니다.
해시값은 데이터의 '지문'으로 사용할 수 있습니다. 내려받은 파일의 해시값을 공식적으로 제시된 값과 비교하면 손상되거나 바꿔치기되지 않았는지 알 수 있습니다(다만 공식 값 자체를 신뢰할 수 있는 경로로 얻었다는 것이 전제입니다). 디지털 서명에서는 긴 문서 대신 그 해시값에 서명합니다. 비밀번호 저장에서는 솔트를 더하고, bcrypt나 Argon2처럼 일부러 계산을 무겁게 한 방식을 사용합니다. 키와 조합한 HMAC은 메시지 인증 코드로서 변조 검출에 사용됩니다.
정답: C. 입력이 같으면 반드시 같은 해시값이 되고, 입력이 1비트만 달라도 해시값은 예측할 수 없을 만큼 크게 바뀐다
해시 함수는 임의 길이의 데이터로부터 정해진 길이의 값(해시값, 다이제스트)을 계산하는 함수입니다. 예를 들어 SHA-256은 입력 길이와 관계없이 256비트 값을 출력합니다. 같은 입력에서는 반드시 같은 값이 얻어지고, 입력이 조금이라도 다르면 출력은 예측할 수 없을 만큼 크게 바뀝니다. 암호에서 사용하는 해시 함수에는 나아가 해시값으로부터 원래 입력을 구하는 것이 현실적으로 불가능할 것(일방향성, 역상 저항성)과, 같은 해시값이 되는 서로 다른 두 입력을 찾기 어려울 것(충돌 저항성)이 요구됩니다. 해시 함수는 키를 사용하지 않는 계산이며 암호화가 아니므로, 복호화하여 원래대로 되돌릴 수도 없습니다. 변조 검출, 디지털 서명, 비밀번호 저장 등에 사용됩니다.
정답: A. 역상 공격은 약 2^256회, 충돌 공격은 약 2^128회
출력이 n비트인 이상적인 해시 함수에서는 해시값이 2^n가지 있으며, 입력을 하나 시도할 때마다 정해진 해시값과 일치할 확률은 1/2^n입니다. 그래서 역상 공격에는 대략 2^n회, n = 256이라면 약 2^256회의 계산이 필요합니다. 한편 충돌 공격에서는 어느 두 개가 일치해도 되므로, k개의 입력을 시도하면 비교할 수 있는 쌍이 약 k^2/2가지로 늘어납니다. k^2/2가 2^n에 가까워지는, k가 2^(n/2) 정도에서 충돌을 찾을 가능성이 높아지며, n = 256이라면 약 2^128회입니다. 이것은 '23명이 있으면 생일이 같은 두 사람이 있을 확률이 50%를 넘는다'는 생일 역설과 같은 생각으로, 생일 공격이라고 합니다. 이 때문에 해시 함수의 충돌에 대한 강도는 출력 비트 수의 절반으로 추정되며, 128비트 상당의 강도를 원한다면 256비트 출력이 필요합니다.
암호화는 키를 사용하여 원래대로 되돌릴 수 있는(복호화할 수 있는) 변환이지만, 해시 함수는 키를 사용하지 않고 원래대로 되돌릴 수 없는 일방향 계산입니다. 그래서 해시값은 비밀을 지키기 위해서가 아니라 데이터가 같은지 확인하기 위해 사용합니다.
입력 길이와 관계없이 256비트(16진수로 64자)입니다. 1글자의 데이터든 큰 파일이든 같은 길이의 값이 됩니다.
해시 함수는 임의 길이의 데이터로부터 정해진 길이의 값(해시값, 다이제스트)을 계산하는 함수입니다.
암호에서 사용되는 해시 함수(암호학적 해시 함수)의 성질로 올바른 것은?출력이 n비트인 이상적인 해시 함수에서는 해시값이 2^n가지 있으며, 입력을 하나 시도할 때마다 정해진 해시값과 일치할 확률은 1/2^n입니다.
출력이 256비트인 이상적인 해시 함수에 대해 무차별 대입로 공격할 때 필요한 계산 횟수의 기준으로, '주…SHA-256 같은 범용 해시 함수는 대량의 데이터를 빠르게 처리하도록 만들어졌으므로, GPU 등을 사용하면 초당 막대한 수의 후보를 시도할 수 있습니다.
비밀번호 저장에 SHA-256 같은 고속 해시 함수를 그대로 사용하지 않고, bcrypt나 Argon2처럼…양자 내성 암호는 쇼어 알고리즘으로 풀려 버리는 소인수분해나 이산 로그 문제 대신, 격자 문제나 해시 함수 등에 기반한 암호로, 현재의 컴퓨터나 네트워크 기기에서 그대로 동작합니다.
양자 내성 암호(포스트 양자 암호, PQC)의 설명으로 올바른 것은?비밀번호는 그대로 저장하지 않고 해시 함수로 계산한 해시값을 저장하는 것이 기본입니다.
웹 서비스에서 이용자의 비밀번호를 저장할 때, 비밀번호에 이용자마다 다른 무작위 값(솔트)을 더한 뒤 해시…디지털 서명(Digital Signature) 솔트(Salt) 해시 테이블(Hash Table) GPU 양자 내성 암호(Post-Quantum Cryptography) 쇼어 알고리즘(Shor's Algorithm) 메시지 인증 코드(Message Authentication Code) 공개 키 암호(Public-key Cryptography) 다요소 인증(Multi-factor Authentication) 대칭 키 암호(Symmetric-key Cryptography)