샤발

Shabal

Shabal은 프랑스 연구 프로젝트인 Saphir가 NIST의 해시함수 국제경쟁에 제출한 암호화 해시함수입니다.

Saphir 파트너

Saphir의 연구 파트너(LIENS 제외)는 Shabal의 개념을 시작하였고, 이후 연구 프로젝트 Saphir2의 파트너와 함께 Shabal의 최종 설계에 적극적으로 참여하였습니다.Saphir(Security and Analysis of Hash Primitives)는 해시 함수에 대한 ANR 자금 지원 프로젝트입니다.Saphir는 2006년 3월에 창업하여 3년간 Cryptolog International, DCSSI, France Telecom(리더), Gemalto 및 LIENS의 5개 파트너를 통합했습니다.Saphir2의 파트너는 Saphir의 파트너 외에 Sagemria의 EADS SN, Sagemia의 4개 새로운 파트너이기도 합니다.o [1]프로젝트

역사

Shabal은 NIST 해시함수 대회에 참가하여 2라운드에 진출하였으나 최종 라운드에 진출하지 못했습니다.샤발은 주로 보안 문제 때문에 최종 후보로 선정되지 않았다.전체 해시 알고리즘의 보안은 손상되지 않았지만, 시간 복잡성이 낮은 비랜덤성 속성이 발견됨에 따라 NIST의 암호화 기술자들 사이에서 향후 [2]더 강력한 공격이 발생할 가능성에 대한 우려가 제기되었습니다.

알고리즘의 이름은 세바스티앙 샤발에게 [1]바치기 위해 선택되었다.

묘사

Shabal은 와이드 파이프 Merkle-Damgörd 해시 구조의 변형으로 간주할 수 있는 동작 모드를 사용합니다.샤발의 내부 상태는 A, B, C로 표시된 세 부분으로 구성되어 있습니다.Shabal의 키 배열은 서로 상호작용하는 비선형 피드백 시프트 레지스터를 사용하여 A와 B를 업데이트합니다.치환의 메인루프에서는 모듈러 곱셈과 모듈러 덧셈, XOR, 보완 및 AND 연산이 사용됩니다.

Shabal function mode of operation

샤발의 체인 모드는 (A, B) ← PM,C와 같이 동작합니다.

(A, B, C) ← (A, C – M, B),

(A w W, B + M),

여기서 M은 메시지블록, W는 카운터입니다.모든 메시지 블록을 처리한 후 메시지 블록과 카운터 값이 고정되는 3개의 최종 라운드가 적용됩니다.Shabal에는 2개의 조정 가능한 파라미터(p, r)가 정의되어 있습니다.여기서 p는 키 순열 내에서 실행되는 루프의 수, r은 A의 크기입니다.(p, r)의 기본값은 (3, 12)입니다.또한 p와 r은 16p ≤ 0 mod r을 충족해야 합니다.Shabal의 [2]모든 출력 크기에 동일한 내부 기능이 사용됩니다.

Shabal 출력 크기

다이제스트 길이에 근거한 샤발의 출력 사이즈는 다음과 같습니다.

  • 샤발-192
  • 샤발-224
  • 샤발-256
  • 샤발-384
  • 샤발-512[1]

샤발 출력

샤발 해시 예시:

  • 샤발-192: CB6E700F CE4DCF97 D2BBBF00 0C5364FB B40C8732 0D733948
  • 샤발-224: 14A6DD99 E8D207F9 F7187681 326F6930 8BCAAE00 25F4855F 3120BA43
  • 샤발-256: C0088FDA 9ABA672A 79D0BD56 07AE488E 095E2114 06855B3B 1877A349 A2543F99
  • 샤발-384: 3312DE9D DA850D91 03785C3A C611B112 5D1BCAFC 033755D2 3B8EE05E 15251E4E 636A724F F0A8E584 4AABEAF 122FC0C4
  • 샤발-512: C6168015 0A3F1FC8 688DD952 8E9E2FED 23EF9578 BCE2A7CB A5D80961 E6C932 9701A5A6 F037B89F 20C6C44E DC7931E7 2BB5B5AB82 B3ADCD32 9CE25056 22305E98[1]

보안.

  • 샤발의 순열을 위해 다양한 구별법이 제안되었다.큐브 테스터를 사용하여 샤발의 키 순열의 통계적 비랜덤성 속성을 시간 복잡도300 [3]2로 설명하였다.
  • 2개의 콜을 사용한171 샤발의 키 배열에 대한 회전 식별자가 제시되었습니다.식별자는 P에 있는 대부분의 연산이 입력 간의 회전 관계를 유지한다는 관측치를 기반으로 합니다.단, 비대칭 IV, 블록카운터의 추가 및 최종 [4][5]라운드의 존재로 인해 공격은 해시 알고리즘으로 확장할 수 없습니다.
  • 3을 곱하면 확률이 1인 최상위 비트의 차이가 유지된다는 관찰에 기초하여 또 다른 구별자가 제시되었다.이 관찰을 이용하여 저자들은 키 배열에 대한 반등가 키를 찾는 방법을 제시했다.관련 키 모델에서, 저자들은 또한 단일 쿼리를 사용하여 P와 무작위 치환을 구별하는 방법을 제시했다.이 메서드는 임의의 보안 파라미터로 일반화할 수 있습니다.저자들은 또한 최종화의 반복 횟수가 36이 아닌 24N(N ÷ 2)인 샤발의 변형에 대한 의사 충돌 및 의사 초 사전 이미지를 찾는 방법을 제시했다.그러나 반복 횟수가 36회일 [6]경우 차이를 상쇄할 수 없기 때문에 원래 샤발에서는 이 공격이 작동하지 않습니다.
  • 검증이 용이한 키 치환 P에 대해 몇 가지 비랜덤성 특성이 표시되었다.저자들은 P에서 고정점을 찾는 간단한 방법을 제안했다.치환에 대한 입력은 치환 루프의 영향을 받지 않도록 선택되었다.이 메서드는 A의 단어 수 및 라운드 수와는 무관하므로 조정 가능한 보안 파라미터의 선택에 관계없이 사용할 수 있습니다.저자들은 또한 키 [2]입력에서 유일한 차이점이 있는 다수의 대형 다중 충돌을 구성하는 방법을 보여주었다.
  • 데이터 복잡도가 [7]2개인 미분23 분석을 사용하여 일부 편향된 출력 비트에 식별자가 제시되었습니다.
  • 시간 복잡도84 2의 샤발 압축 함수에 대한 저중량(45비트) 의사 충돌 공격이 제시되었다.보안 파라미터(2, 12)[8]를 사용한 Shabal 512의 2회 및 2회400 메모리 복잡도의497 프리이미지 공격.
  • 어떤 식별자도 해시 알고리즘의 보안을 직접 위협하지 않습니다.또한 설계자는 이상적인 [2]암호보다 약한 가정을 요구하도록 체인 모드의 무관성 보안 증명을 수정했습니다.

실장

레퍼런스

  1. ^ a b c d Bresson, Emmanuel; Clavier, Christophe; Fuhr, Thomas; Icart, Thomas; Misarsky, Jean-Francois; Naya-Plasencia, Maria; Reinhard, Jean-Rene; Thuillet, Celine; Videau, Marion (2008-10-28). "Shabal, a Submission to NIST's Cryptographic Hash Algorithm Competition" (PDF): 2–3, 20, 22, 32–35. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  2. ^ a b c d NIST Interagency Report 7764 (February 2011). "Status Report on the Second Round of the SHA-3 Cryptographic Hash Algorithm Competition" (PDF): 20–21. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  3. ^ Aumasson, Jean-Philippe. "On the pseudorandomness of Shabal's keyed permutation" (PDF). Retrieved 14 November 2018. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  4. ^ Van Assche, Gilles (24 March 2010). "A rotational distinguisher on Shabal's keyed permutation and its impact on the security proofs" (PDF). {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  5. ^ Aerts, Nieke (August 2011). "Cryptanalysis of Hash Functions In particular the SHA-3 contenders Shabal and Blake" (PDF): 56–57. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  6. ^ Aumasson, Jean-Philippe; Mashatan, Atefeh; Meier, Willi. "More on Shabal's permutation" (PDF). Retrieved 14 November 2018. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  7. ^ Novotney, Peter (20 July 2010). "Distinguisher for Shabal's Permutation Function" (PDF). {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  8. ^ Isobe, Takanori; Shirai, Taizo. "Low-weight Pseudo Collision Attack on Shabal and Preimage Attack on Reduced Shabal-512" (PDF). Retrieved 14 November 2018. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)