[보안] 🌟 Random Number Generator

• 보안에서 난수는 완죤완죤 랜덤해야해서 중요함

🔐 보안에서 난수를 사용하는 법

• 기밀성 측면 : Random key 생성
• 재사용 공격 방지 측면
  • Nonce 생성 : 재사용 공격 방지를 위해 한 번만 사용하는 의미 없는 덧붙이는 값
  • random padding : 블록 암호와 같이 평문 길이가 요구하는 암호문 길이보다 짧으 경우 남는 공간에 random한 수를 채워 넣음
• 부채널 공격 방지 측면 : Random mask 생성
  • 부채널이란 암호 패턴으로 유추하는 것이 아닌 전송량, 전류 변화 등 외부 요소로 알아내는 공격
    ex) RSA에서는 제곱더하기제곱더하기 연산을 반복함
    -> 비트값에 따라 연산 종류가달라짐 → 전류 바뀜
    → 전자기파 바뀜 = 파형 분석해서 알 수 있음
    → 이러한 부수적인 정보를 부채널
    매우매우 강력한 공격

🪔 난수 생성기(RNG, Random Number Generator)의 종류

• TRNG (True RNG)
  • 물리적 현상(잡음,방사선 붕괴, clock drift 등), 사용자 입력 등에 기반
  • ㄹㅇ 무작위, 패턴 찾기 어려움 -> 좋은 통계적 특성을 가짐
  • ex : nonce, PRNG의 seed 등
• PRNG (Pseudo RNG)
  • seed 값으로부터 수학적/알고리즘에의해 계산된 난수열을 생성
  • TRNG만큼 랜덤아님 패턴, 주기성을 가짐
  • 보통 seed를 TRNG 사용하도록 권장 (주기를 가지지 않도록)
  • 재귀적인 방법으로 계산가능
    • s(i+1) <- f(si,s(i-1),...,s(i-t))
    • but 일반적으로 좋은 통계적 특성을 가짐
    • 다음 비트 예측 불가
  • 스트림 암호 같은 경우는 키 스트림 생성기로 사용되며, seed가 키가 됨.
    • 이때 seed만 알면 재생성 가능 -> 예측도 가능
  • TRNG에 비해 매우 큼
  • 피드백 경로를 갖는 시프트 레지스터
  • 구성: 다항식 𝑃 (𝑥 )= 𝑥^𝑚 + 𝑝(𝑚−1)𝑥^(𝑚−1) + ⋯ + 𝑝1𝑥 + 𝑝0으로 표현
  • 다항식 P(x)가 기약다항식일 때 최대주기 : 2^m-1
  • ex) Linear Feedback Shift Register (LFSR), ANSI C의 rand() 함수

🌅 Linear Feedback Shift Registers

• 설계하기 쉬움
• 의사 난수 생성기(PRNG)중 하나
• 피드백 경로를 갖는 시프트 레지스터
  • degree(𝑚): 저장요소(Flip-flop)의 수
  • 피드백: 𝑝𝑖 (0 < 𝑖 < 𝑚) = 1인 부분의 스위치만 연결
• LFSR의 과정
  • 𝑠(𝑖+3) = 𝑠(𝑖+1)⨁𝑠𝑖
  • 시간이 경과할 때마다 하나씩 오른쪽으로 shift
  • ㄴ= 비트가 가장 왼쪽의 상태 비트는 피드백 경로에서 계산되며 이것은 이전 시간에서의 플립플롭 값의 XOR 합
    • XOR은 선형연산 -> 선형성을 만족
    • 선형성 : 𝐹(𝑎 + 𝑏) = 𝐹(𝑎) + 𝐹(𝑏), 𝐹(𝑘𝐴) = 𝑘𝐹(𝐴)
  • 가장 오른쪽의 상태 비트(FF0)가 현재 LFSR의 결과
• 구성
  • 다항식 𝑃 (𝑥 )= 𝑥^𝑚 + 𝑝(𝑚−1)𝑥^(𝑚−1) + ⋯ + 𝑝1𝑥 + 𝑝0으로 표현
  • P(x) = 피드백 함수 : LFSR의 구조와 동작을 정의하고 주기와 생성되는 시퀀스의 특성을 결정.
  • 다항식의 계수는 0 or 1 = 항이 없다 or 있다
• 최대 주기 : 2^m-1
  • P(x)가 기약다항식일 때 최대주기를 가짐
• 2m개의 결과 비트를 알면 P(x) 분석 가능
  • 해결안 : LFSR 여러개 조합 (ex 아래에서 볼 Trivium)
• degree(𝑚)=3일때인 아래 LFSR 그림에서, si는 내부 상태 비트를 나타냄
  • 초기 상태를 （s2=1，s1=0，s0=0）이라고 할 때 시간에 따른 LFSR의 상태 결과는 표 2.2와 같다.
  • 초기 상태가 0,0,0이면 값이 변화하지 않고 쭉 0000.. 이므로 이를 제외하고 아래와 같이 설정
  • 따라서 주기 : 2^3-1=7 개
    
    

Trivium

• LFSR 기반의 현대 stream 암호
• 구조 : 세 개의 nonlinear feedback shift register (NFSR) 사용
  • 대충 피드백구조, NFSR이 3개로되어있다 ~ 정도만,..
• 동작
  • 초기화 단계
    • A: 초기에 80비트 IV가 레지스터 A의 가장 왼쪽 위치에 입력
      • 이니셜 벡터(IV) : 동일 결과를 막기위해 사용(비밀스럽지는 않음)
      • 키가 들어가면 매번 동일한 입력은 동일한 결과가 나기 때문에 사용
    • B: 80비트 키가 레지스터 B의 가장 왼쪽 위치에 입력
      • 키스트림 생성기에 k 값드어감 ,k = 80비트 키,
    • C: 109-111 bit만 1, 그 외 bit은 0으로 설정
  • 준비 단계 : 1152 clock(번) 동작
    • 나온값을 졸라 돌림 -> A,B,C의 상관관계를 줄일고, 예측 불가하게 하도록 준비 동작
  • 암호화: 이후에 나오는 stream(1153 번째 값)부터 사용