야로 알고리즘

Yarrow algorithm

Yarrow 알고리즘은 John Kelsey, Bruce Schneier 및 Niels Ferguson에 의해 고안되어 1999년에 발표된 암호화 의사 난수 생성기(CPRNG) 패밀리입니다.Yarrow 알고리즘은 명시적으로 특허가 없고 로열티가 없으며 오픈 소스이므로 이를 사용하기 위해 라이선스가 필요하지 않습니다.Fortuna의 Ferguson과 Schneier의 개선된 디자인은 그들의 책인 Practical Cryptography에 설명되어 있습니다.

Yarrow는 FreeBSD에서 사용되었지만 현재는 Fortuna로 [1]대체되었습니다.Yarrow는 iOS와[2] macOS에서도 /dev/random 디바이스로 통합되었지만, Apple은 2020년 [3]1분기부터 Fortuna로 전환했습니다.

이름.

Yarrow라는 이름은 I Ching 점괘의 무작위 생성 과정에서 Yarrow 식물의 사용을 암시합니다.샤 왕조(기원전 2070년경~기원전 1600년경) 이후, 중국인들은 점괘를 위해 실로 된 줄기를 사용해 왔다.점쟁이는 50개의 야로 줄기를 여러 개로 나누고 모듈식 산수를 재귀적으로 사용하여 불균일한 분포를 가진 2비트의 랜덤 정보를[4] 생성합니다.

원칙

Yarrow의 주요 설계 원칙은 공격에 대한 저항성, 암호화 배경 없이 프로그래머가 쉽게 사용할 수 있으며 기존 구성 요소를 재사용할 수 있다는 것입니다.ANSI X9.17이나 RSAREF 2.0 PRNG 등 지금까지 널리 사용되고 있던 설계에는 상황에 따라서는 공격의 기회를 제공하는 허점이 있습니다.이들 중 일부는 실제 공격을 염두에 두고 설계되지 않았습니다.또한 Yarrow는 PRNG 기능에 대한 지식이 부족한 시스템 설계자가 쉽게 통합할 수 있도록 하는 것을 목표로 하고 있습니다.

설계.

구성 요소들

Yarrow의 설계는 엔트로피 축적기, 재삽입 메커니즘, 생성 메커니즘 및 재삽입 제어의 4가지 주요 요소로 구성됩니다.

Yarrow는 2개의 풀로 엔트로피를 축적합니다.즉, 키가 손상되는 시간을 가능한 한 짧게 유지하기 위해 키를 자주 재시드하는 고속 풀과 드물지만 보수적인 키를 재시드하는 저속 풀입니다.이것에 의해, 엔트로피 추정치가 매우 낙관적인 경우에도, 다시 삽입된 데이터가 확실히 확보됩니다.

재설치된 메커니즘은 엔트로피 축전지를 생성 메커니즘에 연결합니다.패스트 풀에서 재시딩하면 시작 후 패스트풀에 대한 현재 키와 모든 입력의 해시가 새 키를 생성하기 위해 사용됩니다.저속 풀에서 재시딩하면 저속 풀로의 모든 입력의 해시가 새 키를 생성하기 위해 사용된다는 점을 제외하고는 동일하게 동작합니다.두 리시딩 모두 패스트풀의 엔트로피 추정치를 0으로 리셋하지만 마지막 리시딩에서는 저속풀의 추정치를 0으로 설정합니다.재시딩 메커니즘은 키를 항상 갱신하기 때문에 풀 정보의 키가 재설치 전에 공격자에게 인식되어도 재설치 후에는 공격자에게 인식되지 않습니다.

재설치된 제어 컴포넌트는 빈번한 재시딩(필요하지만 반복적인 추측 공격이 발생할 수 있음)과 빈번하지 않은 재시딩(재시딩) 사이에서 이용되고 있습니다.이 경우 키를 가진 공격자가 더 많은 정보를 얻을 수 없게 됩니다.Yarrow는 소스가 일부 임계값을 초과할 때마다 고속 풀을 사용하여 재설치하고 최소 2개의 소스가 다른 임계값을 초과할 때마다 저속 풀을 사용하여 재설치합니다.특정 임계값은 Yarrow-160 섹션에 기재되어 있습니다.

설계 철학

Yarrow는 충분한 엔트로피가 축적되어 PRNG가 예측 불가능한 상태가 될 수 있다고 가정한다.설계자는 키가 손상된 경우에도 PRNG를 복구할 수 있는 능력을 유지하기 위해 엔트로피를 축적합니다.RSAREF, DSA 및 ANSI X9.17 PRNG에서도 유사한 설계 철학이 채택되었다.

야로우-160

Yarrow는 단방향 해시 함수와 블록 암호라는 두 가지 중요한 알고리즘을 사용합니다.자세한 설명과 속성은 아래 표에 나와 있습니다.

알고리즘 특성. Yarrow-160의 용도
해시함수 h(x)
  • 일방통행
  • m비트 출력 크기
  • 난치성의 충돌

정해진M입력 값, M개의 출력 값 선택이 m비트 값에 걸쳐 균일하게 분포됩니다.

SHA-1 해시 함수
블록 암호 E()
  • 기존 플레인텍스트 공격 및 선택 플레인텍스트 공격에 대한 내성

고도의 패턴의 입력이 주어지면 출력의 통계 퍼포먼스가 높아집니다.

3키 트리플 DES

시대

생성 메커니즘 기능

Yarrow-160은 카운터 모드에서 3키 트리플 DES를 사용하여 출력을 생성합니다.C는 n비트의 카운터 값, K는 키입니다.다음 출력 블록을 생성하기 위해 Yarrow는 여기에 표시된 함수를 따릅니다.

Yarrow는 키가 손상되면 손상된 출력 전에 이전 출력의 누수를 즉시 중지할 수 있기 때문에 출력 블록의 카운트를 유지합니다.시스템 보안 파라미터g P에 도달하면 알고리즘은 k비트의 PRNG 출력을 생성하여 새 키로 사용합니다.Yarrow-160에서는 시스템보안 파라미터가 10으로 설정되어 있습니다.즉g, P = 10입니다.역추적할 수 있는 출력 수를 최소화하기 위해 파라미터를 의도적으로 낮게 설정합니다.

다시 설치했다

Yarrow-160의 재설치 메커니즘은 해시함수 및 블록암호로서 SHA-1과 Triple DES를 사용한다.상세한 순서는, 오리지날 페이퍼에 기재되어 있습니다.

Yarrow-160의 실장

Yarrow-160은 Java 및 FreeBSD용으로 구현되었습니다.그 예는 Mark R. V. Murray의 [5]"FreeBSD를 위한 Yarrow PRNG 구현"에서 찾을 수 있다.

야로우의 장단점

장점

  • Yarrow는 기존 구성 요소를 재사용합니다.
  • 이전의 PRNG에 비해 Yarrow는 상당히 효율적입니다.
  • Yarrow는 암호화 배경이 없는 프로그래머가 비교적 안전한 방법으로 사용할 수 있습니다.Yarrow는 휴대성이 뛰어나고 정확하게 정의되어 있습니다.인터페이스는 심플하고 명확합니다.이러한 기능에 의해, 실장 에러가 발생할 가능성이 어느 정도 감소합니다.
  • Yarrow는 공격 지향 설계 프로세스를 사용하여 만들어졌습니다.
  • Yarrow의 엔트로피 추정은 매우 보수적이어서 철저한 검색 공격을 방지합니다.실제 응용 프로그램에서는 엔트로피 과대평가와 예측 가능한 시작점으로 인해 PRNG가 실패하는 경우가 매우 흔합니다.
  • Yarrow의 재시딩 프로세스는 상대적으로 계산 비용이 많이 들기 때문에 PRNG의 키를 추측하는 데 드는 비용이 더 높습니다.
  • Yarrow는 시드 파일 관리를 단순화하는 기능을 사용하여 파일을 지속적으로 업데이트합니다.
  • 암호 해독 공격을 처리하기 위해 Yarrow는 보안 보호된 블록 암호에 기반하도록 설계되었습니다.생성 메커니즘의 보안 수준은 블록 암호에 따라 달라집니다.
  • Yarrow는 데이터에 의존하는 실행 경로를 피하려고 합니다.이는 타이밍 공격이나 전력 분석 등의 사이드 채널 공격을 방지하기 위해 이루어집니다.이는 RSAREF 2.0 PRNG와 같은 이전 PRNG에 비해 개선된 것입니다.이 PRNG는 내부 운용에 관한 추가 정보가 보호되지 않게 되면 완전히 무너집니다.
  • Yarrow는 암호 해시 함수를 사용하여 입력 샘플을 처리하고 보안 업데이트 함수를 사용하여 샘플을 기존 키와 결합합니다.따라서 공격자가 입력 샘플을 쉽게 조작할 수 없습니다.RSAREF 2.0 PRNG 등의 PRNG에는 이러한 종류의 선택 입력 공격에 저항하는 기능이 없습니다.
  • ANSI X9.17 PRNG와 달리 Yarrow는 중요한 타협에서 회복할 수 있습니다.즉, 키가 손상되어도 공격자는 미래의 출력을 영원히 예측할 수 없습니다.이것은 Yarrow의 파종 메커니즘 때문이다.
  • Yarrow는 키에서 분리된 엔트로피 샘플 풀을 가지고 있으며 엔트로피 풀의 내용을 완전히 예측할 수 없는 경우에만 키를 다시 삽입합니다.이 설계는 키를 가진 공격자가 다음 샘플을 추측하고 다음 출력을 관찰하여 결과를 확인하는 반복적인 추측 공격을 방지합니다.

단점

  • Yarrow의 출력은 암호로 도출되기 때문에 이러한 출력을 사용하는 시스템은 생성 메커니즘 자체만큼 안전할 수 있습니다.즉, 생성 메커니즘을 파괴할 수 있는 공격자는 야로우의 출력에 의존하는 시스템을 쉽게 파괴할 수 있습니다.이 문제는 엔트로피 축적을 증가시켜서는 해결할 수 없습니다.
  • Yarrow에는 엔트로피 추정이 필요하며,[6] 이는 구현에 있어 매우 큰 과제입니다.PRNG를 [7]다시 장착하기 전에 어느 정도의 엔트로피를 채취해야 할지 알 수 없는 문제인데, 이 문제는 Yarrow를 개량한 Fortuna(PRNG)에 의해 해결되었다.Fortuna에는 엔트로피를 수집할 수 있는 풀이 32개 있으며 엔트로피 추정기를 완전히 제거했습니다.
  • 야로의 힘은 열쇠의 크기에 의해 제한된다.예를 들어 Yarrow-160의 유효 키 사이즈는 160비트입니다.보안에 256비트가 필요한 경우 Yarrow-160은 작업을 수행할 수 없습니다.
  • Yarrow-160은 SHA-1을 사용하고 있는데, SHA-1은 첫 번째 [8]공개 충돌로 인해 널리 사용되지 않는 것으로 여겨져 왔다.

레퍼런스

  1. ^ "[base] Revision 284959". Svnweb.freebsd.org. Retrieved 18 October 2016.
  2. ^ "iOS Security" (PDF). Apple.com. October 2012. Retrieved 2016-10-21.
  3. ^ "Random number generation". Apple Support. Retrieved 2020-10-26.
  4. ^ Schneier, Bruce. "Questions & Answers about Yarrow". Schneier on Security. Retrieved 2016-02-15. The fortuneteller would divide a set of 50 stalks into piles, then repeatedly use modular arithmetic to generate two random bits.
  5. ^ "An implementation of the Yarrow PRNG for FreeBSD". Retrieved 18 October 2016.
  6. ^ "Fortuna Cryptographically Secure PRNG : AN0806 - Application Note" (PDF). Silabs.com. Retrieved 2016-10-21.
  7. ^ citadel (4 March 2004). "Fortuna – A Cryptographically Secure Pseudo Random Number Generator – CodeProject". Retrieved 18 October 2016.
  8. ^ Stevens, Marc; Bursztein, Elie; Karpman, Pierre; Albertini, Ange; Markov, Yarik (2017-02-23). "SHAttered". SHAttered. Retrieved 2017-04-27.

외부 링크