그레인(암호)

Grain (cipher)

Gran은 2004년 Martin Hell, Thomas Johanson 및 Willi Meier에 의해 eSTREAM에 제출된 스트림 암호입니다.eSTREAM 프로젝트에 의해 프로파일2의 최종 eSTREAM 포트폴리오에 선정되었습니다.곡립은 주로 제한된 하드웨어 환경용으로 설계되었습니다.80비트 키와 64비트 IV를 사용할 수 있습니다.이 사양에서는 (키, iv)쌍당 최대 출력길이는 권장하지 않습니다.Gran128a에서는 128비트의 보안과 인증을 모두 제공하는 하드웨어 환경에서 사용하는 것이 권장되는 암호인 Gran128a에서 이 암호의 잠재적인 약점이 발견되어 수정되었습니다.

묘사

Gran의 160비트 내부 상태는 80비트 LFSR(Linear Feedback Shift Register)와 80비트 NLFSR(Non-Linear Feedback Shift Register)로 구성됩니다.그레인에서는 비선형 필터 함수에 의해 해방되는 암호문 비트마다 1비트의 LFSR 및 1비트의 NLFSR 상태가 갱신됩니다.80비트 NLFSR은 비선형 5대 1 부울 함수와 LFSR에서 선택한 1비트 선형 입력으로 업데이트됩니다.비선형 5 대 1 함수는 NLFSR 상태의 5비트를 입력으로 받아들입니다.80비트 LFSR은 6대 1의 선형 함수로 갱신됩니다.키 입력 조작 중 암호 출력은 NLFSR 및 LFSR 업데이트 기능 모두에 선형 입력으로 추가로 피드백됩니다.

원래의 그레인 버전 0.0 송신에서는 80비트 NLFSR의 1비트와 80비트 LFSR의 4비트가 비선형 5대1 부울함수(밸런스하도록 선택되고 1차 상관에 면역되며 대수도 3)에 의해 출력은 80SRLF의 1비트와 선형적으로 결합된다.출력.

업데이트된 그레인 버전 1.0 송신에서는 80비트 NLFSR의 1비트와 80비트 LFSR의 4비트가 (약간 수정된) 비선형 5대 1 부울 함수에 공급되고 출력이 80비트 NLFSR의 7비트와 선형적으로 결합되어 출력으로 해방된다.

암호를 초기화하려면 80비트 키가 80비트 NLFSR에 직접 로드되고 64비트 IV가 LFSR의 하위64비트에 로드되며 LFSR의 나머지 16비트 상위비트가 1로 채워집니다.이 암호는 160라운드로 씰링되며 생성된 키 스트림의 160비트는 LFSR 및 NLFSR 업데이트 기능 양쪽에 선형적으로 피드백됩니다.암호는 초기화 프로세스 중에 키스트림 출력을 해제하지 않습니다.

Gran의 저자들은 Gran 버전 1.0 사양에서 Gran 초기화 프로세스의 완전한 확산 속도에 대해 설명합니다.「2개의 다른 IV를 사용한 초기화의 경우, 시프트 레지스터 비트가 양쪽 초기화에서 같을 확률은 0.5에 가까워야 합니다.시뮬레이션 결과, 160 크로킹 후에 실현되는 것으로 나타났습니다."

성능

이 암호는 최대 16라운드를 병렬로 실행할 수 있도록 설계되어 있어 하드웨어 사용을 늘리는 대신 보다 신속하게 구현할 수 있습니다.

보안.

키 크기는 80비트이고 IV 크기는 64비트로 지정됩니다.작성자들은 완전한 키 검색보다 빠른 공격은 불가능하도록 암호 설계되어 있으므로 최선의 공격은 2보다 훨씬80 낮은 계산 복잡도를 필요로 한다고 주장한다.

원래의 Gran 버전 0.0 [1]사양에서는 다음과 같이 주장하고 있습니다.Gran은 하드웨어 어플리케이션에서 사용하는 것으로 알려진 여러 암호보다 높은 보안을 제공합니다.이러한 암호의 잘 알려진 예로는 블루투스에서 사용되는 E0과 GSM에서 사용되는 A5/1이 있습니다.이러한 암호는 하드웨어 구현이 매우 적지만 매우 안전하지 않은 것으로 입증되었습니다.E0 및 A5/1에 비해 Gran은 하드웨어의 복잡성을 줄이면서도 높은 보안을 제공합니다."

저자들은 E0에[2] 대한 공격을 인용하고 있습니다.2 프레임과35 2 프레임의 복잡도(프레임의 길이는 2745비트40)가 필요합니다.원래의 Gran Version 0.0 암호는 80비트 키를 판별하기 위해 2개의 연산과38 2개의 키 스트림비트가 필요한43 키 회복[3] 공격에 의해 파괴되었습니다.

개정된 Gran Version 1.0 [4]사양에서는 암호는 약간 수정된 출력 함수를 가지고 있으며 NLFSR 피드백 함수는 약간의 변경을 받았습니다.사양은 다음과 같습니다. "필터 함수는 매우 작고 변수 5개뿐이며 비선형성 12입니다.단, 이것은 입력 중 하나가 NLFSR에서 가져온다는 사실에 의해 부분적으로 보상됩니다.NLFSR로부터의 입력 비트는, LFSR 와 NLFSR 의 양쪽 모두의 스테이트내의 다른 비트에 비선형적으로 의존합니다.작은 필터 기능도 적절한 위치에서 NLFSR로부터 선형으로 [sic] 7비트를 추가하여 보정하여 출력 함수를 형성합니다."

2006년 10월 현재 Gran Version 1.0에 대해 brute force 공격보다 뛰어난 키 회복 공격은 없습니다.

그러나 2006년 9월 오즈굴 쿠쿠크에 의해 곡물 1.0 [5]초기화에 대한 슬라이드 재동기 공격이라는 논문에 관련 키 공격이 실렸다.이 문서에서는 다음과 같이 주장하고 있습니다.「스트림 암호 Gran 1.0 의 관련 키와 초기치를 찾을 수 있습니다.모든 (K,IV) 쌍에 관련된 (K'),IV') 1비트 시프트 키 스트림을 생성하는 확률 1/22의 쌍.이는 아직 효율적인 키 복구 공격이 되지는 않지만 초기화의 취약점을 나타내며, 조금만 노력해도 극복할 수 있습니다.

레퍼런스

  1. ^ Martin Hell, Thomas Johansson, Willi Meier (2005-04-29). "Grain - A Stream Cipher for Constrained Environments" (PDF). eSTREAM.{{cite web}}: CS1 maint: 여러 이름: 작성자 목록(링크)
  2. ^ Yi Lu, http://lasecwww.epfl.ch/~vaudenay/ (2004). "Cryptanalysis of Bluetooth Keystream Generator Two-Level E0" (PDF). Advances in Cryptology - Asiacrypt 2004, LNCS vol. 3329, pp.483-499, Springer, 2004.
  3. ^ Côme Berbain, Henri Gilbert, Alexander Maximov (2006-01-02). "Cryptanalysis of Grain" (PDF). eSTREAM.{{cite web}}: CS1 maint: 여러 이름: 작성자 목록(링크)
  4. ^ Martin Hell, Thomas Johansson, Willi Meier (2006). "Grain - A Stream Cipher for Constrained Environments" (PDF). eSTREAM.{{cite web}}: CS1 maint: 여러 이름: 작성자 목록(링크)
  5. ^ Ozgul Kucuk (2006-07-16). "Slide Resynchronization Attack on the Initialization of Grain 1.0" (PS). eSTREAM.

외부 링크