[Data Structure][Kotlin] 해시(Hash)

해시(Hash)

• 단방향 암호화 기법
  • 평문을 암호문으로 바꾸는 암호화는 가능하지만, 암호문을 평문으로 바꾸는 복호화는 불가능하다.
• 입력된 값을 산술 연산을 통해 출력 데이터가 있는 위치를 식별할 수 있는 값으로 변환하는 것
• *해시 함수를 통해 입력 값이 데이터가 있는 곳을 알 수 있는 출력 값으로 연결될 수 있으므로, 해시 함수는 입력 값을 출력 값으로 mapping(매핑)해주는 함수라고도 한다.
  • 해시 함수 : 임의의 길이를 가진 데이터를 입력받아 고정된 길이의 값, 즉 해시값을 출력하는 함수

 

해시 맵(HashMap), 해시 테이블(Hash Table)

• 해시 기법을 사용하여 데이터를 보관하는 자료구조
• 데이터에 접근하거나 검색할 때 데이터들을 순회하면서 일일이 비교하는 일반적인 자료구조와 다르게 key 값을 통해 한 번의 산술연산으로 데이터에 접근할 수 있기 때문에 아주 빠른 접근 속도와 검색 속도가 특징이다.
• 해시 테이블은 특정 데이터를 저장할 때 해시 함수를 사용해 계산한 결과를 배열의 인덱스로 활용하여 데이터를 저장하는 방식이다. 즉, 입력값을 해시 함수 계산을 거쳐 나온 해시값을 기준으로 배열하여 입력값의 길이에 상관없이 데이터 공간을 효과적으로 활용할 수 있다.

 

해시 함수의 특징

단방향성

• 입력 데이터에서 해시값으로의 변환은 쉽지만, 해시값에서 원래 데이터로의 역변환은 거의 불가능하다.
  • 이는 해시 함수가 데이터의 무결성을 보장하고, 보안 용도로 활용되는 데에 중요한 특징이다.
• 이러한 단방향성을 평가하는 척도 중 하나가 역상 저항성(preimage resistance)이다.
  • 역상 저항성이 우수하다는 것은 어떤 해시 함수가 특정한 값을 출력하는 입력값을 찾기 어려움을 의미한다.
  • 현재 보안에 사용되는 많은 암호화 해시 함수는 서로 다른 입력값에 대해 완전히 다른 출력값을 반환하여 입력값을 유추하기 매우 어렵다.

 

해시 충돌

• 해시 함수는 서로 다른 입력에 대해 동일한 해시 값을 출력할 수 있다. 이를 해시 충돌이라고 부른다.
• 좋은 해시 함수는 충돌을 최소화해야 하며, 보안 측면에서 안전한 해시 함수는 매우 낮은 충돌 확률을 보장해야 한다.
• 이를 평가하는 척도를 충돌 저항성(collision resistance)으로 표현할 수 있다. 충돌 저항성이 우수하다는 건 어떤 해시 함수가 충돌하는 서로 다른 두 입력값을 찾기 어려움을 의미한다.

 

고정된 결괏값의 길이

• 해시 함수는 항상 일정한 길이의 결괏값을 출력한다.
• 입력 데이터의 크기가 다르더라도 항상 동일한 길이의 해시값을 반환하기 때문에 블록체인과 같은 분산 시스템에서 데이터의 일관성과 효율적인 처리를 보장하는 데에 유용하다.
  • 대용량 데이터에 변조가 일어났는지 확인할 때, 일일이 모든 데이터를 대조하는 것보다 데이터의 해시값을 비교하면, 변조가 일어났는지 쉽게 확인할 수 있다. 이러한 검사 방법을 데이터 무결성 검사라고 한다.

 

해시 함수 종류

• SHA(Secure Hash Algorithm)는 미국 표준 기술 연구소(NIST)에서 개발한 해시 함수 알고리즘들의 모음으로 SHA-1, SHA-2, SHA-3와 같은 다양한 버전이 있으며, 각각의 버전은 서로 다른 특징과 보안 수준을 가지고 있다.

 

SHA-1

• 1995년 미국 NSA 에서 발표한 해시함수로서 최대 264 비트의 메시지로부터 160 비트의(20 바이트) 해시값을 생성한다.
• SHA-1은 SSL/TLS, SSH, IPSec 등을 비롯해 기존의 많은 프로그램에서 사용된다.
• 입력 데이터의 길이를 512 비트 블록으로 맞추기 위해 *패딩 과정을 거친다
  • 패딩(padding) : 100개의 공간에 문자 1개가 들어오면 나머지 99개의 공간을 숫자 0 등으로 메우는 작업
• 충돌쌍 문제 : 두 개의 서로 다른 데이터에 대해 해시를 계산했을 때, 동일한 해시값이 생성되는 것
  • 충돌쌍 문제를 악용하면 시스템 내부의 파일을 임의로 교체하고, 마치 기존에 존재하던 파일인 것처럼 속일 수 있다.

 

SHA-2

• 2001년 미국 NSA 에서 발표한 해시함수로서 SHA-224, SHA-256, SHA-384, SHA-512 등의 4가지 변형이 있는데, 이 중 SHA-256와 SHA-512가 주로 사용된다.
• 해시값의 크기는 SHA-* 뒤에 명시되어 있는데, 예를 들어 SHA-256는 256bit(32 바이트), SHA-512는 512 bit(64 바이트)의 해시값을 생성한다.
  • SHA-256
    
    • SHA-2 계열에 속하는 해시 함수로 256 비트(32 바이트)의 해시값을 생성한다.
    • 블록체인 기술을 기반한 최초의 암호화폐인 비트코인(Bitcoin)은 SHA-256을 트랜잭션 처리와 보안을 위해 사용한다.
    • 비트코인 이외에도 여러 가상 화폐 및 블록체인 프로젝트에서 SHA-256을 사용한다.

 

SHA-3

• 2015년 미국 NIST 에서 발표한 해시함수로서 SHA-2와 동일하게 4개의 224, 256, 384, 512 비트의 해시값을 생성하는데, SHA-3는 SHA-2와 다른 해시 알고리즘(Keccak)을 사용한다.

---

충돌(Collision)

• 충돌은 서로 다른 두 입력 값이 해시 함수를 거쳐 동일한 해시 주소를 가리키는 경우를 의미한다.
• 만약 해시 함수가 여러 입력 값에 대해 같은 결과를 많이 만든다면 충돌이 많아질 수 있고, 이렇게 되면 데이터를 찾는데 더 오랜 시간이 걸릴 수 있다. 따라서 해시 함수를 잘 설계하는 것도 HashMap 의 효율성에 연관된다.

 

충돌 해결법

1. Chaining 기법

• 개방 해싱(Open Hashing) 기법 중 하나
• 해시 테이블 저장공간 외의 공간을 활용하는 기법
• 충돌이 일어나면, 링크드 리스트라는 자료 구조를 사용해서, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 기법
• 이 경우 N 개의 데이터가 같은 *Bucket 에 저장된다면 최악의 경우 O(N)의 시간복잡도를 갖는다.
  • Bucket : 해시 테이블의 구조 내에서 데이터를 저장하는 단위
• Bucket 안의 데이터들을 관리하는 자료구조의 구현을 제외하면 구현이 간단하고, 쉽게 추가하고 삭제할 수 있다는 장점이 있다.
• 데이터의 수가 많아지면 동일한 버킷에 chaining 되는 데이터가 많아져 효율성이 감소한다는 단점이 있다.

class MyHashMap(private val size: Int = 8) {
    
    val hashTable = Array(size) { mutableListOf<Pair<Int, Int>>() }
    
    fun getKey(data: String): Int {
        return data.hashCode()
    }
    
    fun hashFunction(key: Int): Int {
        return key % size
    }
    
    fun saveData(data: String, value: Int) {
        val indexKey = getKey(data)
        val hashAddress = hashFunction(indexKey)
        
        val bucket = hashTable[hashAddress]
        for (index in bucket.indices) {
            if (bucket[index].first == indexKey) {
                bucket[index] = indexKey to value
                return
            }
        }
        
        bucket.add(indexKey to value)
    }
    
    fun readData(data: String): Int? {
        val indexKey = getKey(data)
        val hashAddress = hashFunction(indexKey)

        // 방법 1
//        val bucket = hashTable[hashAddress]
//        if (bucket.isNotEmpty()) {
//            for (index in bucket.indices) {
//                if (bucket[index].first == indexKey) {
//                    return bucket[index].second
//                }
//            }
//        }
//
//        return null            

         // 방법 2
         return hashTable[hashAddress].firstOrNull { it.first == indexKey }?.second
    }
}

fun main() {
    val myHashMap = MyHashMap()
    myHashMap.saveData("one", 1)
    myHashMap.saveData("two", 2)

    println(myHashMap.readData("one"))  // 1
    println(myHashMap.readData("two"))  // 2
    println(myHashMap.readData("three"))  // null
}

 

 

2. Linear Probing 기법

• 폐쇄 해싱(Close Hashing) 기법 중 하나
• 해시 테이블 저장 공간 안에서 충돌 문제를 해결하는 기법
• 충돌이 일어나면, 해당 Hash Address 의 다음 address 부터 맨 처음 나오는 빈 공간에 저장하는 기법
  • 저장 공간 활용도를 높이기 위한 기법

class MyHashMap(private val size: Int = 8) {
    
    private val hashTable = Array<Pair<Int, Int>?>(size) { null }

    private fun getKey(data: String): Int {
        return data.hashCode()
    }
    
    private fun hashFunction(key: Int): Int {
        return key % size
    }
    
    fun saveData(data: String, value: Int) {
        val indexKey = getKey(data)
        var hashAddress = hashFunction(indexKey)

        while (hashTable[hashAddress] != null) {
            if (hashTable[hashAddress]?.first == indexKey) {
                hashTable[hashAddress] = indexKey to value
                return
            }
            hashAddress = (hashAddress + 1) % size
        }

        hashTable[hashAddress] = indexKey to value
    }
    
    fun readData(data: String): Int? {
        val indexKey = getKey(data)
        var hashAddress = hashFunction(indexKey)

        while (hashTable[hashAddress] != null) {
            if (hashTable[hashAddress]?.first == indexKey) {
                return hashTable[hashAddress]?.second
            }
            hashAddress = (hashAddress + 1) % size
        }
        
        return null
    }
}

fun main() {
    val myHashMap = MyHashMap()
    myHashMap.saveData("one", 1)
    myHashMap.saveData("two", 2)

    println(myHashMap.readData("one"))   // 1
    println(myHashMap.readData("two"))   // 2
    println(myHashMap.readData("three")) // null
}

 

해시 함수 공격

레인보우 공격(rainbow attack)

• 해시 함수는 '입력값이 같으면 언제나 같은 결과를 나타낸다'라는 특정이 있다. 그래서 사용자의 암호 유형을 정의한 레인보우 테이블(다이제스트 목록)을 만들어 하나씩 대입해 보면 암호를 발견할 수 있다.
• 일한 메시지가 언제나 동일한 *다이제스트를 갖는다면 해커가 전처리(pre-computing) 된 다이제스트를 다량 확보한 다음 탈취한 다이제스트와 비교해 원본 메시지를 찾아내거나 동일한 메시지를 찾을 수 있다. 
  • 다이제스트 : 임의 길이의 데이터 블록을 고정 길이로 변환하는 해시 알고리즘에서의 해시값

 

무차별 대입 공격

• 암호의 해시를 되돌리긴 어렵다. 대신 공격자는 동일한 해시값을 찾을 때까지 단순히 입력을 계속 시도할 수 있다. 무차별적인 데이터를 넣다 보면 암호화가 무너질 수 있다.
• 해시 함수는 원래 짧은 시간에 데이터를 검색하기 위해 설계했다. 해커는 매우 빠른 속도로 임의 길이의 문자 다이제스트와 해킹할 대상의 다이제스트를 비교하는 데 심혈을 기울인다.

 

해시 함수 보완법

키 스트레칭(Key Stretching)

• 말 그대로 키 스트레칭 쭉 늘린다는 것이다.
• 키 확장 기술은 가능한 각 키를 테스트하는데 걸리는 리소스(시간 및 공간)를 늘려 무차별대입공격에 더 안전한 키(암호 또는 암호 문구)를 만드는 데 사용한다.
• 단방향 암호화를 시도하는 기본 단계를 복잡하게 만들어 공격 자체를 어렵게 만든다.

 

솔팅(Salting)

• 말 그대로 솔팅, 소금을 친다는 것이다.
• 실제 암호의 앞 혹은 뒤 혹은 앞뒤 어느 곳에다가 솔트 된 데이터와 원본 패스워드를 넣어 해시값을 만든다.
• 레인보우 공격을 방지하는 효과가 있다.
• 무차별 대입 공격의 난이도는 반복 횟수에 따라 증가한다.
• 공격자가 파생 키 사전을 미리 계산하지 못한다는 장점이 있다.

---

잔재미코딩 온라인 강의 사이트입니다

[Kotlin] HashMap

블록체인 해시함수 | 정의, 특징, 블록체인 활용 예시 - 코드스테이츠 공식 블로그

암호학) CHF: Cryptographic hash function 암호화 해시 함수 메커니즘과 공격법

암호학) CHF: Cryptographic hash function 암호화 해시 함수 메커니즘과 공격법

암호학) 암호키 동작 원리와 SHA의 진화