Random
Randomness(진짜 랜덤인가), Unpredictability(예측 불가능) 2가지 특징을 만족하는지 확인해야 됨.
Randomness를 판단하는 기준
Uniform distribution: bit단위로 다 뽑고 bit의 0혹은1 빈도수가 비슷하면 Uniform distribution을 따른다 라고 할 수 있다.
Independence: 부분 시퀀스만으로 다른 부분 시퀀스를 추론하기 어려운 것을 말한다.
위 2가지를 만족하면 Randomness를 만족한다고 말한다.Unpredictability
지금까지의 데이터만혹은 많은 양의 데이터를 가지고 다음에 나올 데이터를 예측할 수 없으면 Unpredictability하다고 한다.
PseudoRandom Number Generator
랜덤처럼 보이는 것
TRNG = TRBG
N = number, B = bit
TRNG의 경우 자연적으로 발생하는 랜덤값,
PRNG는 자연적으로 만들어진 것이아닌 인위적으로 만든 값. 그것이 마치 랜덤처럼 보이게 만든 것.
DRNG = DRBG = PRNG = PRBG
D = Deterministic(입력이 같으면 출력이 같다)True Random Number Generator (TRNG)
Keystroke timing patterns, disk electrical activity, mouse movement, system clock 등과 같은 랜덤 소스들을 가지고 Binary화할 수 있는 알고리즘이 있으면 TRNG로 만들 수 있다.
TRNG도 정말 랜덤이기에 8bit 중에 1이 1개, 0이 7개일 수도 있기에 이후에 처리를 해줄 수도 있다.
-> 비효율적이다.
원하는 시간에 원하는 크기의 랜덤값을 만들기에는 비용이 많이 든다.PseudoRandom Number Generator (PRNG)
원할 때 특정 길이의 데이터를 뽑아낼 수 있다.
Deterministic algorithm(동일한 입력 동일한 출력)사용.
PRNG의 넣는 입력값 즉, seed를 TRNG를 통해 뽑은 값들을 사용하여 TRNG와 PRNG를 같이 사용하자.
PRNG: 랜덤한 비트를 계속 만들어내는 것.
Pseudorandom Function (PRF): 고정된 길이의 랜덤한 값을 만들어 내는 것.✅ PRNG의 요구사항
Randomness, Unpredictability, Seed
NIST SP800-22
SP800으로 시작하는것은 보안 관련된 제품이나 알고리즘을 개발하거나 할 때 참조해야하는 표준 문서이다.
랜덤리스란걸 판별을 할 때, 사용해야 할 테스트 종류
Frequency test: Uniform distribution을 따르는지 체크 하는 방법으로 0와 1이 거의 동일하게 나오는지 테스트
Runs test: 통계학에서 사용되는 용어.
Maurer's universal statisticcal test: 압축이 잘 된다는것은 0이나 1이 뭉쳐있는 경우다. 압축이 잘 안되면 랜덤한 특성이다.Unpredictability
Forward unpredictability: seed가 알려지지 않는 이상 다음에 나오는 출력에 대해 절대로 예측하지 못하여야 한다.
-> seed만 잘 가지고 있으면 앞으로의 결과에 예측을 하지 못하여야 한다.
Backward unpredictability: 내가 아무리 많은 데이터를 가지고 있더라도 그 데이터들로부터 seed값을 유추할 수 없어야 한다.Seed Requirements
seed값은 TRNG를 통해 생성하고, 이것을 사용해 원하는 만큼 원하는 길이의 PRNG를 사용.
PRNG Design
Entropy Input: TRNG에서 나온 랜덤값을 Seed로 쓰겠다.
Reseed Function: 하나의 Seed를 하나가지고 random number을 몇번 만들면 Seed값을 refresh해라
Test: 회로가 구동할때마다 그 전에 Physical하게 하드가 정상적으로 잘 돌아가는지 test. Deterministic하기에 중간에 어떤값이 나오고 마지막에 어떤 값이 나와야되는지 안다. 그렇기에 해당 과정을 실행하기 전에 해당 값으로 테스트를 진행하고 동일한 값이 나오면 정상이다.
Symmetric block ciphers의 경우 plaintext를 알아도 key값을 모르면 랜덤한 값인지 모른다.
-> Symmetric block ciphers도 PRNG를 만들때 사용이 가능하다.Linear Congruential Generator (일차합동)
합동식이 일차식이다.
최고참이 1차항이다 = Linear하다 이 의미임.
Ri+1 합동 (a x Ri + b) mod n 이런형식을 반복함으로써 마치 랜덤값처럼 보이도록 함.
첨에 8,9 나오고 마지막에 8,9 처럼 주기가 생기게 된다.
주기를 파악하게 된다면 이전의 출력값으로 앞으로의 출력값을 알 수 있다.
mod n값이 충분히 크지 않을 경우 주기를 파악하기 쉽다.
-> 주기를 파악하게 되면 해당 Random Number System이 뚫린다.One-Way Hash Function
입력을 계속 달라지게 하면 출력값에 대해 유사성을 파악하기 힘듦.
seed로 들어갔던 입력값이 +1 되어서 다시 seed가 되어 입력으로 들어간다.
출력값이 만약에 seed값으로 바로 들어가게 되면 seed값 자체가 노출되는 상황이 발생할 수 있다.
만약에 출력값이 seed값으로 들어가게 된다면 그러면 seed값을 유추해 볼 수 있다.
-> 출력값을 seed를 넣는것이 아니라 처음에 들어온 seed값을 count mode 처럼 +1 하면서 One-way has function의 seed값으로 넣음.
One-way: 한쪽으로 가는것은 쉬운데 반대쪽으로 가는것은 어려워야 한다.
Collision free: 충돌이 발생하면 안됨.Block Cipher Mode of Operation
Block Chiper 하나만 가지고는 입력값이 계속 고정되어있다.
Random Number에 임의의 키 스트림을 만들어내서 그거랑 XOR해서 데이터를 암호화한다.
CTR mode, OFB mode : 사전에 미리 준비해 놓을 수 있는 모드
OFB mode: Key값을 노출시키지 않는다면 어느정도 Random Number Generator로 사용 가능하다.
Counter mode
Fraction of One Bits: 0과 1의 비율 테스트. 0.5이상이 1이 더 많은거
Fraction of Bits that Match with Preceding Block:앞에서의 bit와 현재 bit와 비교해서 같은게 몇개가 있느냐 1786~이랑 5e17b~랑 해서 1이랑 5랑 같은 비트이다. 0001이랑 0101이랑 이런거
같은 것과 같지 않은것의 비율이 50:50이면 좋다.
=> Block Cipher을 가지고 Random Number Generator를 활용했을 때 우리가 Randomness측면에서 봤었던 내용들이 잘 만족이 되는지 확인 가능.Conditiong
TRNG 처음에 자연에서 발생한 리소스를 가져와서 그대로 쓰는것이 아닌 비트로 바꿔서 사용하는데 비트로 바꿀 때 자연에서 온 데이터이다보니까 bias가 있을 수 있다.
ex) 8비트 뽑았는데 0000 0001 일 수도 있음.
정말 랜덤이긴 한데 랜덤이면 가질 거라고 생각한 Uniform distribution과 같은 특성이 작을 때는 안될 때도 있다.
이럴 때 어느 정도 수치를 조절해서 우리가 생각하는 Randomness라는 특성을 만족하도록 자연에서 발생한 TRNG도 바꿔줄 때가 있다. 그때 사용되는 개념이 Conditioning이다.Conditioning Algorithms
Block Cipher에 나온 입력값을 그대로 넣어서 출력값을 그대로 seed값으로 사용할 수도 있다. (Block Cipher은 Plain text와 Cipher text는 전혀 다르기에)
hash function or block cipher이 사용된다.
Conditioning: 리소스로부터 만들어진 Bias를 해결하기 위해 사용되는 알고리즘
Health testing: 그래서 나온 결과가 진짜 Random Number로 쓸 만하냐에 대한 테스트,
하드웨어가 Random Number로서의 특징을 만족하고 있는지, Random Number를 만들어 낼 수 있는 상황인 건지 테스트
=> PseudoRandom Number Generator 혹은 Deterministic Random Number Generator를 보안해서 그것을 사용해 우리가 원할 때 원하는 만큼의 Random Number를 만들어냄
