미국 표준 'SHA-3' 해시 함수와 완벽 호환… 100비트 넣으면 난수 100비트 생성 가능

(지디넷코리아=박희범 기자)국내 연구진이 예측 불가능한 난수를 새로운 방법으로 구현하는데 성공했다. 병렬 구조 채택으로 초고속·안전성 '두 마리 토끼'를 모두 잡았다.

KAIST는 전산학부 이주영 교수 연구팀이 치환 기반 결정론적 난수 발생기(DRBG)의 안전성을 분석하는 새로운 이론적 기틀을 마련하고, 최적의 효율을 내는 결정론적 난수 발생기를 설계했다고 20일 밝혔다.

차세대 난수발생기를 개발한 KAIST 연구팀. 왼쪽부터 황성하, 정우혁 박사과정, 이주영 교수.(사진=KAIST)

이주영 교수는 이를 설명하며, 기존과 다른 4가지 강조했다. 특징은 ▲예측 불가능성 확보 ▲병렬 구조로 초고속 난수 생성 ▲POSDRBG 새로 설계 ▲안전성 기존대비 50% 개선 등이다.

이주영 교수는 "다만, 사업화보다는 국제 표준화하는데 난수 생성기 개발 목적이 있다"며 "현재 미국 국제 표준을 추진 중"이라고 설명했다.

난수에서 치환은 여러 비트나 바이트 순서를 바꿔 뒤섞는 과정으로 양방향 변환이 가능하다. 뒤섞은 걸 원래대로 돌릴 수 있음을 의미한다.

컴퓨터 보안에서 난수(Random number)는 비밀키나 초기값(IV)에 쓰이기에 예측 불가능한 무작위 수를 만들어야 하지만, 많은 수를 생성하다보면 일정한 패턴이 만들어질 수 있다.

이주영 교수 연구팀은 이 문제를 '구조 병렬화' 및 '스펀지 구조'로 해결했다. 난수 생성 속도도 초고속이어서 IoT 기기부터 대규모 서버까지 적용 가능하다는 것이 연구진의 설명이다.

난수 발생기는 블록 암호나 해시 함수, 치환 등 기본 암호학적 연산을 활용해 엔트로피 소스(환경에서 얻는 무작위 데이터)로부터 예측 불가능한 난수를 만들어 낸다.

이렇게 생성된 난수들은 비밀키 및 초기화 벡터 생성 등 대부분의 암호 알고리즘에서 활용된다.

연구팀은 치환 함수에 관심을 가졌다. 미국 표준 'SHA-3' 해시 함수에 사용되면서 우수한 안전성과 효율성이 확보되기 때문이다.

난수 생성 구조. 위 그림은 기존 스펀지 구조의 직렬형 DRBG. 아래는1의 출력효율(100%)을 갖는 병렬형 난수 생성 구조.

그러나, 'SHA-3'에 채택된 스펀지 구조가 문제였다. 이 구조는 치환 크기에 비해 출력 효율이 작다는 한계가 있다.

스펀지 구조는 스펀지가 물을 빨아 들이고 짜내듯 데이터 입력을 차례로 흡수하고, 원하는 길이만큼 출력할 수 있는 구조다. 출력 길이가 고정되지 않아, 필요에 따라 아주 긴 난수나 해시도 생성이 가능하다.

또 기존 치환 기반 결정론적 난수 발생기는 안전성을 증명할 때 ‘게임 호핑’이라는 기법을 사용해 왔다. 그러나 이 방식은 이론적으로 가능한 보안 수준보다 낮게 평가되는 문제가 있었다.

예를 들어, 치환 용량이 256비트일 경우 이론적으로는 min{c/2, λ/2}, 즉 128비트의 안전성을 기대할 수 있다. 하지만 기존 증명 방식에서는 min{c/3, λ/2}, 약 85비트 수준으로만 보장되는 것으로 나타났다.  여기서 입실론(λ)은 엔트로피 임계값, min은 둘 중 작은 값을 취하는 계산식이다.

게임 호핑 기법도 난수 발생기와 공격자가 맞붙는 상황을 ‘게임’으로 정의하고, 이를 여러 개의 작은 단계(미니게임)로 나눈 뒤 각 단계에서 공격자가 성공할 확률을 계산해 합산하다보니, 지나친 세분화로 실제보다 낮은 안전성 수치가 산출되는 문제가 있었다.

연구팀은 이를 극복하기 위해 기존 게임 호핑 기법을 세분화하지 않고, 2단계로 단순화하되, 병렬 구조화했다. 그 결과 난수 생성 안전성이 50%정도 개선됐다는 것. 여기서 50%는 2의 128승 안전성이 2의 192승으로 증가했다는 의미다.

병렬 구조로 개선하기 위해 연구팀은 'POSDRBG(Parallel Output Sponge-based DRBG)'를 새로 설계했다. 이 구조는 데이터를 병렬로 출력하는 것이 특징이다. 다른 말로 설명하면, 출력 효율이 처음으로 1을 달성했다. 100비트를 넣으면 난수가 100비트 나온다는 뜻이다. 기존 방법엣는 대부분 난수 생성이 절반에 그친다.

이주영 교수는 “POSDRBG는 소형 IoT 기기부터 대규모 서버까지, 난수 생성 속도와 안전성을 모두 개선한 새로운 결정론적 난수 발생기”라며, “국제 표준 'SP800-90A' 개정 과정에서 ‘치환 함수 기반 DRBG’가 정식 표준에 포함되는 데 긍정적인 영향을 줄 것”으로 기대했다.

'SP800-90A'는 미국 NIST(국가표준기술연구소)가 제정한 국제 표준 문서다. DRBG의 설계·운영 기준을 정의한다.

또 이 'POSDRBG'는 미국 표준 'SHA-3'와 완벽 호환된다.

KAIST 정보보호대학원 정우혁 박사과정생이 연구논문 제1 저자로, 이주영 교수가 교신저자로 참여했다.

연구결과는 8월 암호학 분야 최우수 국제학회(CRYPTO)에서 발표할 예정이다.

한편, 이 연구는 정보통신기획평가원(IITP)의 지원을 받아 수행됐다.

박희범 기자(hbpark@zdnet.co.kr)

Copyright © 지디넷코리아. 무단전재 및 재배포 금지.