Egloos | Log-in
F/OSS study
F/OSS study
[Linux] random number generators
Linux : 2.6.30


커널에서 제공하는 난수 생성기는 /dev/random과 /dev/urandom 장치가 있다.
둘은 비슷한 기능을 제공하지만 /dev/random의 경우는 난수를 발생시키기 위해 필요한 entropy
(입력 장치, 디스크, 기타 random sample을 제공하는 인터럽트의 이벤트에 의해 생성됨)가
채워질 때까지 block되어 true (or high quality) random number 만을 생성하지만
/dev/urandom은 충분한 entropy가 없는 경우에도 현재 entropy pool 내의 데이터 만으로 난수를 생성한다.

struct entropy_store {
    /* read-only data: */
    struct poolinfo *poolinfo;
    __u32 *pool;
    const char *name;
    int limit;
    struct entropy_store *pull;

    /* read-write data: */
    spinlock_t lock;
    unsigned add_ptr;
    int entropy_count;
    int input_rotate;
};

entropy pool을 관리하는 자료 구조는 위의 entropy_store 구조체로서 중요한 필드 만 살펴보면
pool은 실제 entropy 데이터를 저장하는 버퍼이며
add_ptr은 pool에 entropy를 추가하거나 얻어오는데 사용하는 인덱스 값이고
entropy_count는 현재 pool 내의 entropy의 양을 나타내는 값이다. (bit 단위)

/proc/sys/kernel/random/poolsize 파일을 읽으면 (primary) entropy pool의 크기를 알 수 있고
/proc/sys/kernel/random/entropy_avail 파일을 읽으면 현재 entropy_count 값을 알 수 있다.

사실 entropy pool은 총 3개가 존재하는데
시스템의 entropy를 수집하는 4096 bits (= 512 bytes = 128 words) 크기의 primary pool과
/dev/random과 /dev/urandom에서 각각 사용하는 1024 bits 크기의 (출력용?) pool이 2개 있다.
(실제 이름은 각각 input_pool, blocking_pool, nonblocking_pool이다.)
/dev/[u]random 파일에 데이터를 write하여 해당 pool의 데이터를 refresh (overwrite가 아니다!) 할 수 있지만
이렇게 해도 entropy_count 값 자체에는 영향을 주지 않는다.

그림 출처: Analysis of the Linux Random Number Generator, Gutterman 외, 2006. (아래 참고)

primary pool의 entropy_count는 기본적으로 시스템의 이벤트를 통해서만 증가하며
(root 사용자가 /dev/[u]random 파일을 열어서 ioctl을 호출하면 강제로 바꿀 수는 있다.)
secondary pool들의  entropy_count는 primary pool에서 데이터를 가져오는 만큼 증가하고
pool에서 데이터를 읽어내면 그 만큼 entropy_count가 감소한다.

시스템 이벤트는 다음과 같은 함수들을 통해 primary pool에 입력된다.
  • void add_input_randomness(unsigned int type, unsigned int code, unsigned int value) : 입력 장치의 인터럽트 핸들러가 불리기 직전에 호출된다.
  • void add_interrupt_randomness(int irq) : IRQF_SAMPLE_RANDOM 플래그가 설정된 인터럽트 처리가 끝나고 호출된다.
  • void add_disk_randomness(struct gendisk *disk) : 블록 장치의 I/O request가 완료되었을 때 호출된다.
이 세 함수들은 내부적으로 모두 add_timer_randomness() 함수를 호출하는데
이 함수는 현재 jiffies 값, (가능한 경우) 현재 프로세서가 실행한 클럭 사이클 수 및
인자로 주어진 값을 이용하여 pool의 데이터를 갱신한다.
(입력 장치의 경우 type, code, value를 조합한 값 (< 256), 일반 인터럽트의 경우는 irq 번호 + 256, 디스크의 경우는 장치 번호 + 256)

entropy_count 값의 갱신은 (randomness를 높이기 위해) 매우 신중을 기해 증가시키는데
동일한 인터럽트가 이전에 발생한 시간과의 차이를 3중으로 기록하여 비교한 후 제일 작은 값을 택해 2로 나누고
그 중 하위 12(?) 비트 중에서 제일 먼저 1이 나오는 bit의 위치를 더한다. (2의 지수승으로 내림?)
해당하는 코드는 다음과 같다.

    if (!state->dont_count_entropy) {
        delta = sample.jiffies - state->last_time;
        state->last_time = sample.jiffies;

        delta2 = delta - state->last_delta;
        state->last_delta = delta;

        delta3 = delta2 - state->last_delta2;
        state->last_delta2 = delta2;

        if (delta < 0)
            delta = -delta;
        if (delta2 < 0)
            delta2 = -delta2;
        if (delta3 < 0)
            delta3 = -delta3;
        if (delta > delta2)
            delta = delta2;
        if (delta > delta3)
            delta = delta3;

        /*
         * delta is now minimum absolute delta.
         * Round down by 1 bit on general principles,
         * and limit entropy entimate to 12 bits.
         */
        credit_entropy_bits(&input_pool, min_t(int, fls(delta>>1), 11));
    }

수학적으로 복잡한 계산이 필요하기 때문에 여기서 자세히 살펴보지는 않겠지만
entropy pool에 데이터가 들어갈 때는 twisted GFSR (Mersenne twister)라는 방식으로 계산되며
entropy pool에서 데이터가 나올 때는 전체 pool 데이터에 SHA-1 해시값을 계산하여
다시 pool에 넣고 (역시 TGFSR 이용) 데이터를 갱신한 후에 읽고 여기에 다시 SHA-1 해시값을 계산한 후에
결과값을 XOR 연산을 통해 반으로 줄인 후 (fold) 리턴한다.
궁금한 사람은 아래의 참조 문서를 살펴보면 되겠다..

=== 참조 문서 ===

by namhyung | 2009/11/12 17:15 | Kernel | 트랙백 | 덧글(0)
트랙백 주소 : http://studyfoss.egloos.com/tb/5168232
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]

:         :

:

비공개 덧글

◀ 이전 페이지 다음 페이지 ▶

카테고리
General
Application
System
Kernel
Book
Tips
태그
kernel glibc git x86 documentation compiler gcc algorithm binutils awk synchronization script SMP block-layer memory computer-architecture bash CARM vcs C build patch scm blktrace perf CAaQA3 sed elf emacs linux
전체보기
이글루 파인더

최근 등록된 덧글
1번은 call-stack 금방 확인이 ..
by 혁 at 11/13
해당 문법에 대한 자세한 가이드 같..
by ㅇㄷㅎ at 11/07
perf에 대한 설명 감사드립니다! ..
by flavono123 at 10/24
최근 등록된 트랙백
Tod's Ferrari Homme
by Tods Pas Cher,Kodak did ..
Mocassin Femme
by Mocassins Homme, I got so..
natural garcinia cambogia
by
rss

skin by jiinny


X