정보보호 05 암호개론 (3)
Hashing (1) dictionary symbol table in computer science application spelling checker thesarus data dictionary in database application symbol tables generated by loader, assembler, and compiler operations on symbol table determine if a particular name is in the table retrieve the attributes of that name modify the attributes of that name insert a new name and its attribute delete a name and its attributes use hashing very good expected performance: O(1)
Hashing (2) identifiers x hash table f(x) = a a hash function
Hashing (3) Hash Table Def) identifier density of a hash table: n/t where n: number of identifiers in table T: total number of possible identifiers loading density or loading factor of a hash table: a = n/(s b) where s: number of slots in each bucket b: number of bucket two identifiers i 1 and i 2 are synonyms with respect to f, if f(i 1 ) = f(i 2 ) where i 1 i 2 an overflow occurs when we hash a new identifier, i, into a full bucket a collision occurs when we hash two nonidentical identifiers into the same bucket collisions and overflows occur simultaneously iff bucket size is 1
Hashing (4) Example) hash table ht with b=26, s=2, n=10 hash function f 1st character of identifier slot 0 slot 1 0 acos atan 1 2 char ceil 3 define 4 exp 5 float floor 6 25 Identifiers acos define float exp char atan ceil floor clock ctime hash table with 26 bucket and two slots per bucket
Hash Function Hashing (5) requirements for a hash function easy to compute minimizes the number of collision (but, we can not avoid collisions) uniform hash function for randomly chosen x from the identifier space, P[f(x)=i] = 1/b, for all buckets i a random x has an equal chance of hashing into any of the b buckets
Hashing (6) Hash Function (cont.) mid-square middle of square hash function frequently used in symbol table applications hash function f m squaring the identifier obtain the bucket address by using an appropriate number of bits from the middle of the square if we use r bits, 2 r buckets are necessary
Hashing (7) Hash Function (cont.) division(modular) use the modulus(%) operator f D (x) = x % M where M: table size range of bucket address: 0 ~ M-1 the choice of M is critical choose M as a prime number such that M does not divide r k a for small k and a choose M such that it has no prime divisors less than 20
Hashing (8) Hash Function (cont.) folding shift folding ex) identifier x = 12320324111220 x 1 x 2 x 3 x 4 x 5 123 203 241 112 20 folding at the boundaries 123 203 241 112 x 2 203 302 x 4 112 211 123 + 302 + 241 + 211 + 20 = 897 20 699
Hashing (9) Hash Function (cont.) digit analysis used in case all the identifiers are known in advance examine the digits of each identifier delete those digits that have skewed distributions select the digit positions to be used to calculate the hash address
Hashing (10) Overflow Handling linear open addressing linear probing when overflow occurs, linear search for the empty slot in the hash table using circular rotation bucket x # of comparisons 0 acos 1 1 atoi 2 2 char 1 3 define 1 4 exp 1 5 ceil 4 6 cos 5 7 float 3 8 atol 9 9 floor 5 10 ctime 9 25
Hashing (11) Overflow Handling (cont.) linear open addressing (cont.) quadratic probing examine the hash table buckets ht[f(x)], ht[(f(x) + i 2 ) % b], ht[(f(x) - i 2 ) % b], for 0 i (b-1)/2, where b: number of buckets in the table reduce the average number of probes rehashing use a series of hashing functions f 1, f 2,, f b bucket f i (x) is examined for i = 1, 2,, b
Hashing (12) Overflow Handling (cont.) chaning defect of linear probing comparison of identifiers with different hash values maintain list of identifiers one list per one bucket each list has all the synonyms requires a head node for each chain link data(key) link bucket(head node) list(linked list)
Hashing (13) Overflow Handling (cont.) chaning (cont.) [0] acos atoi atol [1] [2] [3] [4] char ceil cos define exp ctime [5] [6] [25] float floor
정보보호에서의해쉬함수이용 데이터무결성을제공하는알고리즘중하나 메시지인증알고리즘 단방향해쉬함수 임의의길이의메시지를받아들여특정길이의출력값생성 출력값비교를통해무결성확인
해쉬함수의조건 H 는임의의크기의입력 M 을적용할수있어야한다. H 는일정크기의출력 h = H(M) 을만들어야한다. H 와 M 이주어졌을때 h = H(M) 계산이쉬워야한다 H 와 h 가주어졌을때 M 을구하는계산이거의불가능해야한다.(one way property) H 가주어졌을때같은출력을갖는두입력을착지어려워야한다. ( 충돌회피성 )(weak collision resistance)
전자서명의조건 위조불가 서명자만이서명생성가능 서명자인증 서명자의신분확인가능 재사용불가 다른문서의서명으로사용불가능 변경불가 서명된문서내용변경불가 부인불가 서명한사실부인불가
디지털서명알고리즘 공개키암호방식을이용한서명방식 서명자가비밀키로서명을생성하고, 검증자가공개키로확인하는시스템 직접서명방식 송신자와수신자간에직접서명및검증 중계서명방식 중재자를통해확인 통신전에정보공유가필요없고, 외부로부터공격에강하며, 시간확인까지가능
RSA 서명방식 가장먼저실용화 서명알고리즘의안전도는 RSA 암호방식안전도와동일 가장보편적으로사용 알고리즘 키생성단계 RSA 암호알고리즘과동일 서명단계 메시지 M 의해쉬값 H 를구하여서명값계산 S = H da mod n A 원본메시지 M 과같이전송 검증단계 원본메시지에대한 H 계산 공개키로 S 의 H 계산후비교
그외서명방식 ElGamal 서명알고리즘 키생성 서명 서명검증 DSS(Digital Signature Standard) 서명알고리즘 ElGamal 서명기술응용 NIST에의해 1994년 12월표준채택 ElGamal(512비트 ) 보다짧은서명값 (160비트) 서명 서명검증단계 타원곡선디지털서명알고리즘 EC-DSA 1985년 N.Koblitz와 V.S Miller가 RSA 방식의대안으로제시 동일한안전성을실현하는데 RSA 1024 비트, ECC 160 비트 EC-KCDSA
해쉬함수의응용 (1)
해쉬함수의응용 (2)
해쉬함수의응용 (3)
해쉬함수의응용 (4)
해쉬함수의응용 (5)
해쉬함수의응용 (6)
해쉬함수 (1) MD5 (Message Digest Version 5) 512 비트입력 128 비트출력 충돌회피성에대한문제로인해기존응용과호환으로만사용제한 MD4 (Message Digest Version 4) 1990 년 Rivest 가개발 메시지를 128 비트로압축 MD5 보다약간빠르고, 안전성측면에서는다소떨어짐 MD2 (Message Digest Version 2) PEM 프로토콜에응용 보안성은바이트의 random permutation 에달려있음 다른함수보다다소느리지만취약부분은아직발견되지않음
해쉬함수 (2) RIPE-MD 유럽의 RIPE 프로젝트에서개발된해쉬함수 SHA-1 못지않은안전성을가진것으로평가되며, 128, 160, 256, 320 비트해쉬출력값을제공 HAVAL 1992 년 Zheng 에의해개발 출력값길이가가변 MD5 를변형하여 1024 비트블록으로수행 다양한라운드수와 7 개의가변함수, 128, 160, 192, 224, 256 비트길이해쉬값출력가능
해쉬함수 (3) SHA (Secure Hash Algorithm) NIST 에의해 1993 년 FIPS PUB 180 으로표준화 MD4 와유사하게설계 512 비트단위로메시지를입력하여 160 비트해쉬값출력 ( 입력전메시지길이를 512 비트정수배로조정 ) SHA-1( 전자서명용 ) 과 MD5 비교 각각의키길이의차이가있음 (160 : 128) 공격대응면에서 SHA-1 이더강하다 ( 길이차이 ) 안전성 : SHA-1 이비교적더안전 속도 : 연산이많아 SHA-1 이다소늦다 단순성과간결성 : 두알고리즘모두비교적간단하며적용용이 바이트순서 : (big-endian : little-endian)
해쉬함수 (4)
해쉬함수 (5) 일반적으로 MD5 가많이사용되고있음 취약성이발견되어제한적사용권고 SHA-1 은디지털서명에사용하도록제안됨 AES 의 128, 192, 256 비트에적용하도록 SHA256, SHA382, SHA512 로확장 RIPE-MD-128, RIPE-MD-160, RIPE-MD-256, RIPE-MD-320 은 MD5 를대신할수있도록제안 RIPE-MD-128 은충돌저항성문제가있음 RIPE-MD-160 은효율성은낮지만높은안전성으로널리사용중 Tiger 는 64 비트환경에최적화됨
키관리 ( Key Management) 생성 분배 (distribution) 보관 폐기
KDC (Key Distribution Center) 키의생성과분배및관리를담당하는장비또는시설 사용자의수가많아질수록키관리가어려워짐 중앙집중식 수평적다중식 (flat multiple KDC) 계층적다중식 (hierarchical multiple KDC)
SKA(Symmetric Key Agreement) KDC 를사용하지않고두통신자의세션키로운영 D-H(Diffe-Hellman) KA(Key Agreement) 두사용자가안전하게키를교환하는방식 이산대수알고리즘에근거 사용자 A 는임의의수 x 를고르고 R 1 = g x mod p 계산 사용자 B 는임의의수 y 를고르고 R 2 = g y mod p 계산 R 1, R 2 교환 사용자 A 는 (R 2 ) x mod p 계산 사용자 B 는 (R 1 ) y mod p 계산 K = (R 2 ) x mod p = (g y mod p) x mod p = g yx mod p = g xy mod p = (g x mod p) y mod p = (R 1 ) y mod p