역상 공격

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 프리이미지 공격의 종류
- 2.1. 제1 프리이미지 공격
- 2.2. 제2 프리이미지 공격
3. 프리이미지 공격의 계산 복잡도
- 3.1. 무차별 대입 공격
- 3.2. 제한된 프리이미지 공간 공격
4. 실제 프리이미지 공격 사례
5. 프리이미지 공격 방어
- 5.1. 솔트(Salt) 사용
- 5.2. 키 유도 함수 사용
6. 한국 사회와 프리이미지 공격
참조

1. 개요

역상 공격은 주어진 해시 값을 생성하는 입력을 찾는 공격(제1 역상 공격)과, 주어진 입력과 동일한 해시 값을 생성하는 다른 입력을 찾는 공격(제2 역상 공격)을 통칭한다. 이상적인 해시 함수에서 역상 공격은 무차별 대입 공격을 통해 이루어지며, 양자 컴퓨터는 구조화된 역상 공격을 더 빠르게 수행할 수 있다. 현재 실용적인 역상 공격은 MD5 및 SHA-1에 대한 충돌 공격이 알려져 있으며, 이는 인터넷 프로토콜에 영향을 미칠 수 있다. 비밀번호 보안을 위해 솔트와 키 유도 함수를 사용하며, 한국 사회에서는 짧은 비밀번호 사용으로 인한 취약점이 존재하여 개인정보 유출 사고에 대한 우려가 있다.

더 읽어볼만한 페이지

암호 공격 - 재전송 공격
재전송 공격은 유효한 데이터 전송을 가로채 재사용하여 권한 없는 접근을 시도하는 사이버 공격으로, 세션 ID, 일회용 비밀번호, 타임스탬핑 등을 통해 방지할 수 있으며, IoT 장치와 같은 시스템에서 보안 위험을 초래할 수 있다.
암호 공격 - 랜섬웨어
랜섬웨어는 컴퓨터 시스템 접근을 제한하고 금전을 요구하는 악성 소프트웨어이며, 암호화 기술을 활용하여 파일 접근을 막고, 비트코인 등장 이후 피해가 급증했으며, 이중 갈취 및 서비스형 랜섬웨어 형태로 진화하여 기업과 기관을 대상으로 공격하고, 파일 암호화, 시스템 잠금, 데이터 유출 등의 피해를 발생시킨다.

역상 공격
암호학적 해시 함수 공격 모델
유형	암호 공격
목표	해시 함수의 원상을 찾는 것
속성	해시 함수의 원상 저항성을 깨뜨림 주어진 해시값에 대해 해당 해시값을 생성하는 입력값(원상)을 찾아내는 것이 목표
공격 종류
역상 공격	주어진 해시값에 대해, 그 해시값을 생성하는 입력값을 찾는 공격
제2역상 공격	주어진 입력값에 대해, 동일한 해시값을 생성하는 다른 입력값을 찾는 공격
충돌 공격	동일한 해시값을 생성하는 서로 다른 두 개의 입력값을 찾는 공격
기술적 세부 사항
목표 1	주어진 해시값 y에 대해 h(x) = y를 만족하는 x를 찾는 것
목표 2	주어진 입력값 x에 대해 x' ≠ x 이면서 h(x) = h(x')를 만족하는 x'를 찾는 것
목표 3	h(x) = h(x')를 만족하는 서로 다른 입력값 x와 x'를 찾는 것
추가 정보
관련 용어	암호학 해시 함수 암호 공격

2. 프리이미지 공격의 종류

역상 공격은 목표하는 해시 값 또는 메시지에 따라 크게 두 가지 유형으로 나눌 수 있다.

제1 프리이미지 공격: 주어진 해시 값 `h`에 대해, $H(m) = h$ 를 만족하는 임의의 메시지 `m`을 찾는 공격이다.
제2 프리이미지 공격: 주어진 메시지 `m`₁에 대해, $H(m_1) = H(m_2)$ 를 만족하면서 $m_1 \neq m_2$ 인 다른 메시지 `m`₂를 찾는 공격이다.

2. 1. 제1 프리이미지 공격

제1 프리이미지 공격은 주어진 해시 값에 대해, 해당 해시 값을 생성하는 임의의 입력을 찾는 공격을 의미한다.

이상적인 해시 함수에서 첫 번째 또는 두 번째 프리이미지를 계산하는 가장 빠른 방법은 무차별 대입 공격을 이용하는 것이다. `n`-비트 해시의 경우, 이 공격은 시간 복잡도 2ⁿ을 가지며, 이는 일반적인 출력 크기인 128비트 해시에서는 현실적으로 수행하기 어렵다고 간주된다. 만약 이러한 복잡도가 공격자가 달성할 수 있는 최선의 성능이라면, 해당 해시 함수는 프리이미지 저항성(preimage resistance)을 갖는다고 본다. 그러나 양자 컴퓨터는 구조화된 프리이미지 공격을

\sqrt{2^{n}} = 2^{\frac{n}{2}}

의 시간 복잡도로 수행할 수 있다는 일반적인 결과가 있으며, 이는 두 번째 프리이미지 공격^[2]과 충돌 공격에도 영향을 미친다.

특정 해시 함수에 대해서는 암호 분석을 통해 더 빠른 프리이미지 공격 방법이 발견될 수 있다. 이러한 공격은 해당 함수에 특화되어 있다. 이미 몇 가지 중요한 프리이미지 공격이 발견되었지만, 아직 실용적인 수준은 아니다. 만약 실용적인 프리이미지 공격이 발견된다면 많은 인터넷 프로토콜에 큰 영향을 미칠 수 있다. 여기서 "실용적"이라는 것은 공격자가 합리적인 양의 자원(비용, 시간 등)을 투입하여 공격을 성공시킬 수 있음을 의미한다. 예를 들어, 특정 해시 값이나 메시지에 대한 프리이미지를 찾는 데 수조 달러가 들고 수십 년이 걸리는 공격은 실용적이지 않지만, 수천 달러가 들고 몇 주가 걸리는 공격은 매우 실용적이라고 할 수 있다.

현재까지 알려진 실용적이거나 거의 실용적인 공격^[3]^[4]은 대부분 MD5 및 SHA-1에 대한 충돌 공격이다.^[5] 일반적으로 충돌 공격은 프리이미지 공격보다 실행하기 쉬운데, 이는 특정 값(주어진 해시 값)을 목표로 하는 프리이미지 공격과 달리, 어떤 두 입력 값이든 같은 해시 값을 내기만 하면 되기 때문이다. 무차별 대입을 통한 충돌 공격의 시간 복잡도는

2^{\frac{n}{2}}

으로, 프리이미지 공격의 2ⁿ보다 훨씬 낮다.

2. 2. 제2 프리이미지 공격

이상적인 해시 함수에서, 주어진 입력 값 ''x''₁에 대해 해시값 H(''x''₁)과 동일한 해시값을 갖는 다른 입력 값 ''x''₂ (즉, 제2 프리이미지)를 찾는 가장 빠른 방법은 무차별 대입 공격이다. ''n''-비트 해시의 경우, 이 공격은 시간 복잡도 2^''n''을 가지며, 이는 ''n'' = 128비트와 같은 일반적인 출력 크기에서는 매우 비현실적인 수준으로 간주된다. 만약 이 복잡도가 공격자가 달성할 수 있는 최선이라면, 해당 해시 함수는 제2 프리이미지 저항성을 갖는다고 본다.

그러나 양자 컴퓨터는 구조화된 프리이미지 공격(제2 프리이미지 포함)과 충돌 공격을 2^''n''/2의 복잡도로 수행할 수 있다는 일반적인 결과가 있다.^[2]

특정 해시 함수에 대한 암호 분석을 통해 더 빠른 프리이미지 공격 방법이 발견될 수도 있다. 이러한 공격은 해당 함수에 특화된다. 이미 몇 가지 중요한 프리이미지 공격이 발견되었지만, 아직 실용적인 수준은 아니다. 만약 실용적인 프리이미지 공격이 발견된다면 많은 인터넷 프로토콜에 큰 영향을 미칠 것이다. 여기서 "실용적"이란 공격자가 합리적인 비용과 시간 내에 공격을 성공시킬 수 있음을 의미한다. 예를 들어, 수조 달러의 비용과 수십 년의 시간이 필요한 공격은 비실용적이지만, 수천 달러의 비용과 몇 주가 걸리는 공격은 매우 실용적일 수 있다.

현재까지 알려진 실용적이거나 거의 실용적인 공격은 대부분 MD5 및 SHA-1에 대한 충돌 공격이다.^[3]^[4]^[5] 일반적으로 충돌 공격은 특정 해시값에 구애받지 않고 어떤 두 입력 값이든 같은 해시값을 내면 되기 때문에 프리이미지 공격보다 실행하기 쉽다. 제2 프리이미지 공격과 달리, 무차별 대입을 통한 충돌 공격의 시간 복잡도는 2^''n''/2에 불과하다.

3. 프리이미지 공격의 계산 복잡도

이상적인 해시 함수에 대한 프리이미지 공격의 시간 복잡도는 기본적으로 무차별 대입 공격에 의존하며, n-비트 해시의 경우 2ⁿ이다. 이 복잡도는 일반적인 해시 길이(예: 128비트)에서는 매우 높아, 이러한 함수는 프리이미지 저항성을 갖는다고 간주된다. 그러나 양자 컴퓨터는 이 복잡도를 2^n/2로 낮출 가능성이 있다.^[2]

특정 해시 함수에 대한 암호 분석을 통해 더 낮은 복잡도를 갖는 공격 방법이 발견될 수도 있지만, 이는 해당 함수에만 적용된다. 현재까지 실용적인 수준의 프리이미지 공격은 보고된 바 없으나, 만약 발견된다면 많은 인터넷 프로토콜에 심각한 영향을 미칠 수 있다.

참고로, 충돌 공격은 프리이미지 공격보다 일반적으로 더 낮은 복잡도를 가진다. 무차별 대입 충돌 공격의 시간 복잡도는 2^n/2이며, 현재까지 알려진 실용적이거나 거의 실용적인 공격^[3]^[4]은 대부분 MD5나 SHA-1과 같은 오래된 해시 함수에 대한 충돌 공격이다.^[5]

3. 1. 무차별 대입 공격

이상적인 해시 함수에서 첫 번째 또는 두 번째 프리이미지를 계산하는 가장 기본적인 방법은 무차별 대입 공격이다. n-비트 해시의 경우, 이 공격은 2ⁿ의 시간 복잡도를 가진다. 예를 들어, 일반적으로 사용되는 128비트 해시의 경우 2¹²⁸번의 연산이 필요하며, 이는 현재 기술로는 사실상 불가능한 수준으로 여겨진다. 만약 이 정도의 계산량이 공격자가 동원할 수 있는 최선의 방법이라면, 해당 해시 함수는 프리이미지 저항성을 갖는다고 평가받는다.

그러나 양자 컴퓨터의 발전은 이러한 상황을 바꿀 수 있다. 양자 컴퓨터는 특정 구조를 가진 프리이미지 공격을 2^n/2의 시간 복잡도로 수행할 수 있는 것으로 알려져 있다. 이는 두 번째 프리이미지 공격^[2]이나 충돌 공격에도 적용될 수 있다.

무차별 대입 공격보다 더 빠른 프리이미지 공격 방법은 특정 해시 함수를 암호 분석하여 찾아낼 수 있지만, 이는 해당 함수에만 적용되는 방법이다. 이미 몇 가지 중요한 프리이미지 공격 기법이 발견되었지만, 아직 현실적으로 사용될 수 있는 수준은 아니다. 만약 공격자가 합리적인 비용과 시간 내에 실행할 수 있는 실용적인 프리이미지 공격이 발견된다면, 많은 인터넷 프로토콜에 큰 영향을 미칠 수 있다. 예를 들어, 수조 달러와 수십 년이 걸리는 공격은 비현실적이지만, 수천 달러와 몇 주가 걸리는 공격은 매우 실용적이라고 할 수 있다.

현재까지 알려진 실용적이거나 거의 실용적인 공격^[3]^[4]은 대부분 MD5나 SHA-1과 같은 오래된 해시 함수에 대한 충돌 공격이다.^[5] 일반적으로 충돌 공격은 특정 값에 얽매이지 않고 어떤 두 값이든 충돌시키면 되기 때문에 프리이미지 공격보다 실행하기 쉽다. 무차별 대입 방식을 사용하더라도 충돌 공격의 시간 복잡도는 2^n/2로, 프리이미지 공격(2ⁿ)보다 훨씬 낮다.

3. 2. 제한된 프리이미지 공간 공격

이상적인 해시 함수에 대한 제1 역상 공격이 계산적으로 어렵다는 것은 가능한 해시 입력 값의 집합이 무차별 대입 공격을 하기에는 너무 크다는 가정을 전제로 한다. 하지만 주어진 해시 값이 비교적 작거나 특정 규칙을 따르는 입력 값 집합에서 생성된 것으로 알려진 경우, 무차별 대입 공격이 효과적일 수 있다. 공격의 실현 가능성은 입력 집합의 크기와 해시 함수 계산 속도 또는 비용에 따라 달라진다.

대표적인 예시는 비밀번호 인증을 위해 해시를 사용하는 경우이다. 시스템은 사용자 비밀번호의 원문 대신 해시 값을 저장하여 인증 데이터를 관리한다. 사용자가 로그인을 시도하면 입력한 비밀번호를 해시하여 저장된 값과 비교한다. 만약 저장된 해시 값이 유출되더라도 공격자는 비밀번호 원문이 아닌 해시 값만 얻게 된다. 그러나 많은 사용자들이 예측 가능한 방식으로 비밀번호를 선택하고, 길이가 짧은 비밀번호를 사용하는 경우가 많다. 이 경우, 사용된 해시 함수가 이론적으로 역상 공격에 안전하더라도, 빠른 해시 함수라면 가능한 모든 조합을 시도하여 원래 비밀번호를 찾아낼 수 있다.^[6] 이러한 공격의 속도를 늦추기 위해 키 유도 함수와 같은 특수한 해시 함수가 개발되었다. 또한 짧은 비밀번호에 대한 무차별 대입 공격을 막기 위한 방법으로는 솔트(salt) 기법이 있다. (관련 정보: 비밀번호 크래킹)

4. 실제 프리이미지 공격 사례

특정 해시 함수를 암호 분석하여 이론적으로 더 빠른 프리이미지 공격 방법을 찾을 수 있다. 이는 해당 함수에만 적용된다. 하지만 중요한 프리이미지 공격 방법들이 발견되었음에도 불구하고, 아직 실용적인 수준의 공격 성공 사례는 보고되지 않았다. 여기서 "실용적"이란 공격자가 합리적인 비용과 시간 내에 공격을 성공시킬 수 있음을 의미한다. 예를 들어, 수천 달러의 비용으로 몇 주 안에 특정 메시지의 프리이미지를 찾아낼 수 있다면 이는 실용적인 공격으로 간주될 수 있다.^[2]

현재까지 알려진 실용적이거나 거의 실용적인 공격 사례들은 대부분 MD5나 SHA-1과 같은 오래된 해시 함수에 대한 충돌 공격이다.^[3]^[4]^[5] 일반적으로 충돌 공격은 프리이미지 공격보다 실행하기 쉬운데, 이는 공격 목표값이 특정 해시값으로 고정되지 않고 임의의 두 입력값에 대한 해시 충돌만 찾으면 되기 때문이다. 무차별 대입 공격을 기준으로 비교했을 때, n비트 해시 함수에 대한 프리이미지 공격의 시간 복잡도는 2ⁿ이지만, 충돌 공격은 2^n/2으로 현저히 낮다.

5. 프리이미지 공격 방어

해시 함수에 대한 역상 공격(프리이미지 공격)은 주어진 해시 값에 해당하는 원래 입력값을 찾아내려는 시도를 말한다. 만약 공격자가 이 공격에 성공하면, 예를 들어 시스템에 저장된 비밀번호의 해시 값을 가지고 원래 비밀번호를 알아내는 등의 보안 문제가 발생할 수 있다.

이러한 프리이미지 공격의 위험성을 낮추고 해시 함수의 안전성을 강화하기 위한 여러 가지 방어 기법들이 사용된다. 대표적인 방법으로는 비밀번호와 같은 원본 데이터에 사용자별로 고유한 임의의 값을 추가하여 해시하는 솔트(salt) 기법이 있다. 또한, 의도적으로 해시 계산 과정을 복잡하게 만들어 무차별 대입 공격의 효율성을 떨어뜨리는 키 유도 함수를 사용하는 방법도 중요한 방어 전략 중 하나이다. 이러한 기법들은 해시 값만으로는 원본 데이터를 쉽게 유추하기 어렵게 만들어 정보 시스템의 보안 수준을 높이는 데 기여한다.

5. 1. 솔트(Salt) 사용

비밀번호 인증 시스템에서는 일반적으로 사용자의 비밀번호 원문 대신 그 해시 값을 저장한다. 사용자가 로그인을 시도하면 입력한 비밀번호를 해시하여 저장된 값과 비교하는 방식이다. 만약 저장된 해시 값이 유출되더라도 공격자는 원래 비밀번호를 직접 알 수는 없다. 그러나 많은 사용자들이 예측하기 쉽거나 짧은 비밀번호를 사용하는 경우가 많아, 해시 함수 자체는 안전하다고 평가되더라도 무차별 대입 공격을 통해 가능한 모든 조합을 시도하여 원래 비밀번호를 알아낼 위험이 존재한다.^[6] 특히 미리 계산된 해시 값 목록인 레인보우 테이블을 이용한 공격에 취약할 수 있다.

이러한 문제를 해결하고 보안성을 높이기 위해 솔트(salt)를 사용하는 방법이 있다. 솔트는 비밀번호를 해싱하기 전에 각 사용자마다 고유하게 생성된 임의의 문자열을 비밀번호에 덧붙이는 것을 의미한다. 이렇게 하면 설령 여러 사용자가 동일한 비밀번호를 사용하더라도, 각기 다른 솔트 값 때문에 최종적으로 저장되는 해시 값은 모두 달라지게 된다. 이는 공격자가 레인보우 테이블과 같은 기존의 해킹 기법을 사용하여 저장된 해시 값으로부터 원래 비밀번호를 유추하는 것을 훨씬 어렵게 만든다. 빈번한 개인정보 유출 사고를 겪는 한국의 인터넷 환경에서 사용자 비밀번호를 안전하게 보호하기 위한 중요한 보안 기법으로 강조된다. 또한, 짧은 비밀번호에 대한 무차별 대입 공격의 효율성을 낮추는 데에도 기여한다.^[6]

5. 2. 키 유도 함수 사용

일반적으로 비밀번호 인증 시스템은 사용자의 비밀번호 원문 대신 그 해시 값을 저장하여 보안을 유지한다. 사용자가 로그인을 시도하면 입력한 비밀번호를 해시하여 저장된 값과 비교한다. 만약 저장된 해시 값이 유출되더라도 공격자는 원래 비밀번호를 바로 알 수는 없다.

하지만 많은 사용자가 예측하기 쉽거나 짧은 비밀번호를 사용하는 경향이 있다. 해시 함수 자체는 역상 저항성을 갖도록 설계되었더라도, 계산 속도가 매우 빠른 해시 함수를 사용하면 공격자가 가능한 모든 비밀번호 조합을 빠르게 시도해보는 무차별 대입 공격에 취약해질 수 있다.^[6] 즉, 해시 값 자체를 알아내는 것은 어렵지만, 흔히 사용되는 비밀번호들을 빠르게 해시하여 유출된 해시 값과 비교하는 방식으로 원래 비밀번호를 찾아낼 가능성이 높아진다.

이러한 문제점을 해결하기 위해 키 유도 함수가 사용된다. 키 유도 함수는 의도적으로 해시 계산 속도를 느리게 만들어, 공격자가 짧은 시간 안에 많은 비밀번호를 테스트하는 것을 어렵게 만든다. 이는 무차별 대입 공격의 효율성을 크게 떨어뜨려 시스템의 보안성을 높이는 역할을 한다. ''참조'': 비밀번호 크래킹. 짧은 비밀번호 테스트를 방지하는 또 다른 중요한 방법으로는 솔트(salt)를 사용하는 기법이 있다.

6. 한국 사회와 프리이미지 공격

이상적인 해시 함수에 대한 제1 역상 공격은 가능한 모든 입력값을 하나씩 대입해보는 무차별 대입 검색 방식으로는 현실적으로 찾아내기 어렵다고 여겨진다. 이는 해시 함수에 입력될 수 있는 값의 경우의 수가 너무 많기 때문이다. 하지만 주어진 해시값이 비교적 작은 입력값 집합에서 생성되었거나, 특정 규칙성을 가진 입력값에서 생성되었다는 정보가 있다면 무차별 대입 검색이 효과적일 수 있다. 이러한 공격의 실용성은 입력값 집합의 크기와 해시 함수 계산 속도 및 비용에 따라 달라진다.

비밀번호 인증 시스템은 역상 공격의 대표적인 대상이 될 수 있다. 많은 시스템은 사용자의 비밀번호 원문 대신 비밀번호를 해시 함수로 처리한 해시값을 저장하여 보안을 유지한다. 사용자가 로그인을 시도하면 입력한 비밀번호를 해시하여 저장된 해시값과 비교한다. 만약 해커가 시스템에 침입하여 저장된 해시값을 훔치더라도, 해시값만으로는 원래 비밀번호를 바로 알 수 없다. 그러나 대부분의 사용자는 기억하기 쉬운 단어나 짧은 조합 등 예측 가능한 방식으로 비밀번호를 만드는 경향이 있다. 이렇게 만들어진 비밀번호는 종류가 많지 않으므로, 해시 함수 자체는 역상 공격에 안전하게 설계되었더라도 빠른 계산 속도를 이용해 가능한 모든 조합을 시도하여 원래 비밀번호를 찾아낼 수 있다.^[6] 이러한 무차별 대입 검색의 속도를 늦추기 위해 키 유도 함수와 같이 특별히 계산 시간을 늘린 해시 함수가 개발되었다. 또한, 짧은 비밀번호에 대한 무차별 대입 공격을 방지하는 방법 중 하나로 솔트(salt) 기법이 사용된다. (''관련 항목: 비밀번호 크래킹'')

참조

_[1] 서적 Fast Software Encryption Springer-Verlag 2012-11-17
_[2] 웹사이트 Quantum attacks against Blue Midnight Wish, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Shabal, SHAvite-3, SIMD, and Skein https://cr.yp.to/has[...] 2020-03-29
_[3] 웹사이트 Why We Need to Move to SHA-2 https://casecurity.o[...] Certificate Authority Security Council 2014-01-30
_[4] 웹사이트 Google Online Security Blog: Announcing the first SHA1 collision https://security.goo[...] 2017-02-23
_[5] 웹사이트 MD5 and Perspectives https://www.cs.cmu.e[...] 2009-01-01
_[6] 웹사이트 25-GPU cluster cracks every standard Windows password in <6 hours https://arstechnica.[...] Ars Technica 2020-11-23
_[7] 웹사이트 인터넷プロトコルにおける暗号技術的ハッシュ関数についての攻撃 (Attacks on Cryptographic Hashes in Internet Protocols) https://www.nic.ad.j[...] 2012-03-14
_[8] 웹사이트 PKI相互運用技術からみたSHA-1問題 http://www.jnsa.org/[...] 日本ネットワークセキュリティ協会 2012-03-14
_[9] 문서 RFC 4270

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com