스펀지 함수

Sponge function
Illustration of the sponge construction
해시함수를 위한 스펀지 구조. P는i 입력 문자열의 블록이며, Z는i 해시 출력 블록이다.

암호학에서 스펀지 함수 또는 스펀지 구조는 어떤 길이의 입력 비트 스트림을 취하고 원하는 길이의 출력 비트 스트림을 생성하는 유한한 내부 상태를 가진 알고리즘의 한 종류다. 스펀지 기능은 이론적 및 실제적 용도를 모두 가지고 있다. 이들은 암호 해시, 메시지 인증 코드, 마스크 생성 기능, 스트림 암호, 의사 난수 생성기, 인증된 암호화를 포함한 많은 암호화 원시 요소를 모델링하거나 구현하는 데 사용할 수 있다.[1]

건설

스폰지 기능은 다음 세 가지 구성 요소로 제작된다.[2]

  • b비트를 포함한 상태 메모리 S
  • 함수 :{ 0 →{ 0 b f 상태 메모리를 변환하는 함수 f : 상태 값의 유사 순열)
  • 패딩 함수 P

상태 메모리는 크기 r(비트레이트)의 하나와 크기 c의 나머지 부분(용량)의 두 부분으로 나뉜다. 이 구간은 각각 R과 C로 표시된다.

패딩 기능은 패딩된 입력의 길이가 비트 전송률 r의 전체 배수가 되도록 입력 문자열에 충분한 비트를 추가한다. 따라서 패딩된 입력은 r비트 블록으로 분할될 수 있다.

작전

스펀지 기능은 다음과 같이 작동한다.

  • 상태 S가 0으로 초기화됨
  • 입력 문자열이 패딩되어 있다. 이는 입력이 패딩 함수 P를 사용하여 r비트의 블록으로 변환된다는 것을 의미한다.
  • 패딩된 입력의 각 r비트 블록 B에 대해:
    • R은 R XOR B로 대체된다(비트 XOR 사용)
    • S가 f(S)로 대체됨

이 과정은 패딩 처리된 입력 문자열의 모든 블록을 "흡수"한다.

이제 다음과 같이 스펀지 기능 출력이 준비되었다("수분 처리").

  • 상태 메모리의 R 부분이 출력됨
  • 충분한 비트가 출력될 때까지 반복:
    • S가 f(S)로 대체됨
    • 상태 메모리의 R 부분이 출력됨

출력할 r비트 미만이 남아 있으면 R이 잘린다(R의 일부만 출력된다).

또 다른 은유로는 상태 메모리를 "엔트로피 풀"로 설명하며, 입력은 "풀에 꽂혀" 있고, 변환 기능은 "엔트로피 풀에 고정"이라고 한다.[3]

입력 비트는 상태 메모리의 C 부분에 XOR로 처리되지 않으며, C 비트가 직접 출력되지도 않는다는 점에 유의하십시오. 입력에 의해 C가 변경되는 정도는 전적으로 변환 함수 f에 달려 있다. 해시 애플리케이션에서 충돌이나 프리이미지 공격에 대한 저항은 C에 따라 달라지며, 그 크기("용량" c)는 일반적으로 원하는 저항 수준의 두 배가 된다.

복층 시공

교대로 흡수하고 짜는 것도 가능하다.[4] 이 작업을 양면구축 또는 양면구축이라고 한다. 단일 패스 인증 암호화 시스템의 기본이 될 수 있다.

  • 상태 S가 0으로 초기화됨
  • R은 입력의 첫 번째 r비트 블록으로 XOR 처리됨
  • S가 f(S)로 대체됨
  • R은 이제 출력의 첫 번째 r비트가 된다.
  • R은 입력의 다음 r비트 블록으로 XOR 처리됨
  • S가 f(S)로 대체됨
  • R은 이제 출력의 다음 r비트가 된다.
  • …

덮어쓰기 모드

선택한 보안 수준을 유지하면서 흡수 중 XOR 작동을 생략할 수 있다.[4] 이 모드에서는 흡수 단계에서 입력의 다음 블록이 주의 R 부분을 덮어쓴다. 이렇게 하면 단계 사이에 더 작은 상태를 유지할 수 있다. 어차피 R 부분은 덮어쓰게 되므로 미리 폐기할 수 있으므로 C 부분만 보관하면 된다.

적용들

스펀지 기능은 이론적 및 실제적 용도를 모두 가지고 있다. 이론적 암호해석에서 랜덤 스펀지 함수는 적절한 경우 f가 랜덤 순열 또는 변환인 스폰지 구조다. 랜덤 스펀지 함수는 널리 사용되는 랜덤 오라클 모델, 특히 유한한 내부 상태보다 암호 원시성의 실제적인 한계를 더 많이 포착한다.[5]

스펀지 구조는 실용적 암호 원소 구축에도 활용할 수 있다. 예를 들어, 1600비트 상태의 케카크 암호 스펀지는 NIST가 SHA-3 대회에서 우승자로 선정했다. 케카크의 강점은 그 작가들이 개발한 복잡하고 다원형 순열에서 비롯된다.[6] Spritz라고 불리는 RC4-redesign은 알고리즘을 정의하기 위해 스펀지 구조를 말한다.

다른 예로, 스폰지 기능을 사용하여 암호 해싱 방식뿐만 아니라 관련 데이터(AED)[3]로 인증된 암호화를 구축할 수 있다.[7]

참조

  1. ^ The Keccak Team. "Duplexing The Sponge" (PDF).
  2. ^ Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. "Sponge Functions". Ecrypt Hash Workshop 2007.{{cite web}}: CS1 maint : 복수이름 : 작성자 목록(링크)
  3. ^ a b Rivest, Ron; Schuldt, Jacob (2014-10-27). "Spritz – a spongy RC4-like stream cipher and hash function" (PDF). Retrieved 2014-12-29.
  4. ^ a b Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. "Duplexing the sponge: single-pass authenticated encryption and other applications" (PDF).{{cite web}}: CS1 maint : 복수이름 : 작성자 목록(링크)
  5. ^ Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. "On the Indifferentiability of the Sponge Construction". EuroCrypt 2008.{{cite web}}: CS1 maint : 복수이름 : 작성자 목록(링크)
  6. ^ Boutin, Chad (2 October 2012). "NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition". NIST. Retrieved 4 October 2012.
  7. ^ van Beirendonck, M.; Trudeau, L.; Giard, P.; Balatsoukas-Stimming, A. (2019-05-29). A Lyra2 FPGA Core for Lyra2REv2-Based Cryptocurrencies. IEEE International Symposium on Circuits and Systems (ISCAS). Sapporo, Japan: IEEE. pp. 1–5. arXiv:1807.05764. doi:10.1109/ISCAS.2019.8702498.