Advanced
Redesign of Stream Cipher Salsa20/8
Redesign of Stream Cipher Salsa20/8
Journal of the Korea Institute of Information and Communication Engineering. 2014. Aug, 18(8): 1904-1913
Copyright © 2014, The Korea Institute of Information and Commucation Engineering
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License(http://creativecommons.org/li-censes/ by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : April 17, 2014
  • Accepted : June 11, 2014
  • Published : August 31, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
길호 김
Department of IT Convergence and Application Engineering, PuKyong National University, Pusan 608-737, Korea
성기 김
Department of IT Convergence and Application Engineering, PuKyong National University, Pusan 608-737, Korea
경연 조
Department of IT Convergence and Application Engineering, PuKyong National University, Pusan 608-737, Korea

Abstract
스트림 암호의 동일한 키 재사용 금지와 무결성 보장이 안 되는 단점을 개선한 256비트 출력의 스트림 암호를 개발 했다. 개발한 스트림 암호는 Salsa20의 라운드 함수를 사용하여 8라운드 적용하고 5단계 파이프라인 구조의 하드웨어로 구현 했으며, WSN, DMB 등과 같은 응용에 적용하기 위해 실시간 처리와 빠른 성능을 보이며, 안전성도 만족하고 있다.
Keywords
Ⅰ. 서 론
유무선 네트워크와 다양한 정보처리 기기로 언제 어디서나 원하는 정보를 실시간으로 사용자 요구에 맞춘 형태로 제공할 수 있는 유비쿼터스(Ubiquitous) 시대가 오고 있으며, 이는 군수/국방 분야, 전자금융서비스, 근거리 무선 통신, 물류/유통, 환경감시, 가정 자동화(Home Automation) 등 다양한 분야에 적용되고 있으며, 유비쿼터스 핵심기술 중 하나인 무선 센서 네트워크(WSN: wireless sensor network)에 대한 관심이 높아지고 있다. 무선 센서 네트워크는 각 센서 노드의 제한적인 상황 때문에 데이터의 저장, 계산 능력, 배터리, 대역폭 등에 분명한 한계를 보이고 있으며, 더불어 센서노드는 여러 형태의 공격, 도청, 해킹, 가입자 비밀정보 유출, 서비스 교착상태(마비) 등에 취약한 것으로 알려져 있어 추가적인 보안에 대한 연구가 필요하다. 그리고 디지털 멀티미디어 방송(DMB: Digital Multimedia Broadcasting)에서 방송 콘텐츠에 대한 암호 기술의 적용은 실시간 처리가 요구되기 때문에 블록 암호는 적용할 수 없고 스트림 암호나 워터마크(Watermark)를 사용한다. 이와 같이 WSN, DMB 등에 안전하면서 신뢰할 수 있는 시스템 구현에는 실시간 처리가 가능한 스트림 암호의 사용이 더욱 늘어날 것으로 예상된다.
스트림 암호는 블록 암호보다 가볍기 때문에 수행 속도가 빠르며 암호의 구현 또한 쉬운 것으로 알려져 있지만 평문과 XOR연산으로 암호문을 만드는 단순함 때문에 동일한 키를 2번 이상 사용할 수 없고, 평문과 암호문은 정확히 일대일 대응관계이므로 공격자는 암호문 전체를 공격하지 않고 특정부분의 1비트 또는 1바이트 이상을 임의의 값으로 변경하므로 공격이 쉽게 이루어지며 스트림 암호는 이와 같은 공격을 감지할 수 있는 능력이 없다. 가볍고 빠른 수행은 실시간 처리가 필요한 WSN, DMB 구현에 중요한 요소이지만 동일한 키 재사용이 불가능한 것과 무결성(Integrity) 보장이 안 되는 단점으로 스트림 암호가 현재까지는 많이 사용되고 있지 않고 있다.
현재 WSN 상에서 구현된 암호는 공개 키 암호와 블록 암호인 AES [1 , 2] 가 있다. 이 암호들은 계산량과 계산에 필요한 메모리도 많이 필요한 무거운 암호이기 때문에 이를 극복할 대안으로 최근에 3단계로 진행된 eSTREAM [3 , 4] 프로젝트에서 소프트웨어와 하드웨어 부문에서 몇 개의 스트림 암호가 선택되었다. 그러나 eSTREAM에서 채택된 스트림 암호들 역시 동일 키 재사용을 할 수 없는 점과 무결성 보장이 안 되기 때문에 본 논문에서 WSN, DMB 등과 같은 실시간처리가 필요한 분야에 동일 키 재사용이 가능하며, 무결성이 우수한 하드웨어로 구현된 256비트 출력 스트림 암호를 제안한다. 개발한 스트림 암호는 eSTREAM의 소프트웨어 부분에서 가장 주목받은 Salsa20 [5] 의 라운드 함수를 기반으로 실시간 처리를 위한 빠른 수행을 위해 5단계 파이프라인 구조의 하드웨어로 구현 했으며, 스트림 암호의 단점인 동일 키 재사용 금지와 무결성 보장을 위해 평문의존형 가변적인 라운드 값의 적용과 개발한 스트림 암호 초기 상태값의 갱신을 의사 랜덤 수열 생성기(PRNG: Pseudo-Random Number Generator) 역할을 수행하는 산술 쉬프트 레지스터(ASR: Arithmetic Shift Register) [6] 를 적용했다.
일반적으로 암호 알고리즘을 하드웨어로 구현하는 것이 소프트웨어로 구현하는 것보다 보안적으로 안전하다고 알려져 있으며 수행속도도 하드웨어 구현이 훨씬 빠르다. 그리고 하드웨어 구현 시 메모리 사용을 최소화 할 수 있고(내부 상태 메모리), 비선형 변환 연산을 위한 S박스나 계산 복잡도가 높은 곱셈, 나눗셈, 지수, 유한체 연산을 사용하지 않으며 제한적인 하드웨어인 WSN에 쉽게 적용할 수 있는 암호 알고리즘으로 Salsa20을 선택했다.
개발한 스트림 암호는 Salsa20을 축소한 8라운드로 구현하여 Salsa20/8과 유사한 소프트웨어 수행 속도를 보이고 있으며 하드웨어 수행 속도는 약 1.53Gbps의 결과를 보인다.
본 논문의 구성은 2장에서 Salsa20의 라운드 함수 알고리즘을 간략히 설명하고, 3장에서 개발한 스트림 암호의 구조와 상세한 설계를 설명하고, 4장에서 개발한 스트림 암호의 소프트웨어, 하드웨어 구현 결과 및 안전성에 대해 분석하고, 마지막으로 결론으로 끝맺는다.
Ⅱ. Salsa20의 소개
Salsa20은 Daniel J. Bernstein이 개발한 512비트 출력의 스트림 암호로 유럽에서 시작된 eSTREAM 프로젝트에서 주목받은 암호 알고리즘이다. eSTREAM에서는 3차에 걸쳐 소프트웨어와 하드웨어 구현 부문으로 나누어 진행된 분석 및 평가의 결과로, HC-128 [7] , Rabbit [8] , Salsa20, SOSEMANUK [9] , Grain [10] , MICKEY [11] , Trivium [12] 스트림 암호를 선택했다.
이 중 Salsa20은 128비트 및 256비트의 비밀 키를 지원하고 64비트 IV(Initial Vector)를 사용해 512비트 키 스트림을 생성한다. 키 생성을 위한 내부 상태공간은 32비트로 된 4x4 테이블로 총 64바이트이다( 표 1 ). 내부상태의 갱신은 XOR 연산, 산술 덧셈 연산, 순환 연산으로만 구성되어 있고 S박스를 사용하지 않지만 블록 암호와 유사한 라운드 진행 방식으로 20라운드를 수행하며 대부분의 CPU에서 AES보다 좋은 성능을 보인다 [13] .
내부 상태 메모리 비교Table. 1Compare the internal status of the memory
PPT Slide
Lager Image
내부 상태 메모리 비교 Table. 1 Compare the internal status of the memory
지금부터는 간략한 Salsa20 알고리즘을 설명한다. Salsa20의 32비트 단위 4x4 2차원 내부 상태는 다음과 같다.
PPT Slide
Lager Image
내부 상태 X에서 c 0 ~ c 3 은 128비트 상수이며, 128비트 비밀 키는 k 0 ~ k 3 이고 256비트 비밀 키는 k 0 ~ k 3 = k 4 ~ k 7 이고 v 0 ~ v 1 은 64비트 IV이며 t 0 ~ t 1 은 64비트 카운트이다.
64바이트(512비트) 키 스트림 Z = X + X 20 으로 Salsa20의 라운드 함수를 20번 수행한 값과 정수 덧셈을 한 결과가 512비트 출력 키 스트림이 된다. Salsa20 라운드 함수의 핵심은 비선형 변환을 하는 quarterround로 4개의 32비트 입력을 받아 4개의 32비트 출력을 생성하며 알고리즘은 다음과 같다.
PPT Slide
Lager Image
수식 2에서 ⋘는 32비트 단위 왼쪽 순환 연산이다.
Salsa20 라운드 함수의 첫 번째는 columnround로 열 단위로 4번 quarterround를 수행하며 입력은 각각 (x 0 , x 4 , x 8 , x 12 ), (x 5 , x 9 , x 13 , x 1 ), (x 10 , x 14 , x 2 , x 6 ), (x 15 , x 3 , x 7 , x 11 )이다. 다음은 rowround로 행 단위로 4번의 quarterround를 수행하며 입력은 각각 (x 0 , x 1 , x 2 , x 3 ), (x 5 , x 6 , x 7 , x 4 ), (x 10 , x 11 , x 8 , x 9 ), (x 15 , x 12 , x 13 , x 14 )이다. Salsa20은 columnround와 rowround를 합쳐 Doubleround라 하며 Doubleround를 수행하면 1라운드가 된다. 이를 20번 반복한 후 초기 512비트 값과 덧셈한 결과가 최종 키 스트림이 된다. 본 논문에서는 20라운드가 아닌 8라운드 결과를 사용한다.
Ⅲ. Salsa20의 재설계
개발한 스트림 암호 설명에 사용된 그림이나 수식 등의 논리 및 산술 연산자들은 일반적인 표기법과 사용법을 그대로 적용하고, 변수 명의 위첨자는 상태 값을 나타내며, 아래첨자는 워드 또는 바이트 단위 순서 번호이다.
Salsa20 알고리즘을 8라운드로 축소한 하드웨어 구현을 위한 256비트 출력의 스트림 암호 개발을 위한 설계 중점 사항은 수행속도와 하드웨어 면적이다.
ㆍ 대표적인 수행속도를 높이기 위한 기술은 파이프라인으로 시스템을 구현하는 것이다. 그래서 개발한 스트림 암호를 5단계 파이프라인으로 설계 했다. 각각의 파이프라인 단계는 ASR 처리, Salsa20의 2라운드씩 처리하여 20라운드인 Salsa20을 8라운드로 축소해서 수행속도를 높였으며, 안전성에 문제가 없다면 수행속도 향상의 최선의 방법은 라운드 수를 축소하는 것이다.
ㆍ 하드웨어 면적을 최소로 만들기 위한 최선의 방법 역시 안전성에 문제가 없을 경우 수행 라운드 수를 줄이는 방법이다. 그리고 하드웨어 구현 시 메모리가 가장 많은 면적을 차지한다. 그래서 개발한 스트림 암호에서 사용되는 2048비트 라운드 키는 SHACAL-2의 키 스케줄링 알고리즘을 사용하여 2048비트 라운드 키 생성 후 이를 메모리에 저장한 후 사용하는 방식이 아니라 제어신호와 파이프라인 단계에 따라 그때그때 생성하는 방식으로 구현했다. SHACAL-2 키 스케줄링 알고리즘을 사용한 이유는 메모리를 사용 하지 않기 위해, S박스가 없고 산술 논리연산으로만 구성된 키 스케줄링 알고리즘을 선택했다.
그림 1 은 개발한 스트림 암호의 암호화 과정을 표현한 것으로 사용자가 입력한 각각 128비트 비밀 키와 IV를 사용하여 3.2절의 512비트 4개의 라운드 키를 생성한 다음, ASR1은 128비트 비밀 키, ASR2는 128비트 IV를 이용하여 초기화 한다. ASR1, 2를 수행하여 생성된 512비트와 첫 번째 512비트 라운드 키(K 0 )를 XOR 연산을 수행한다. 다음으로 결과 값 512비트는 Salsa20 2라운드를 수행하고 두 번째 512비트 라운드 키(K 1 )와 XOR 연산을 수행한다. 그 결과 값을 다시 Salsa20 2라운드 수행 후 세 번째 라운드 키(K 2 )와 XOR 연산을 수행한 다음 Salsa20 2라운드를 수행한다. 생성된 512비트 중 하위 256비트는 그림 1 과 같이 표백(Whitening)을 위해 임시로 저장하고 상위 256비트는 256비트 mk와 XOR 연산을 수행한 다음 마지막 라운드 키(K 3 )와 XOR 연산을 수행 후 Salsa20 2라운드를 수행한다. 512비트 수행 결과를 256비트로 나누어 XOR 연산 후 256비트 평문과 XOR 연산을 수행한 결과는 다음 번 256비트 mk로 사용되며 최종적인 256비트 암호문은 256비트 표백과 XOR 연산한 결과 값이다. 제일 처음 사용된 256비트 mk값은 사용자가 입력한 비밀 키와 IV이며 다음 번 mk는 그림 1 과 같이 평문에 의존적인 계속해서 가변적인 256비트 값이 된다. 표백 또한 가변적인 256비트 값이다. 그림 1 은 암호화 과정만을 표현한 것으로 개발한 스트림 암호는 암호와 복호가 서로 다른 알고리즘을 보인다. 자세한 내용 3.5절에서 설명한다.
PPT Slide
Lager Image
개발한 스트림 암호 흐름도 Fig. 1 stream cipher developed a flow chart
- 3.1. 초기화 과정
초기화 과정은 ASR1 277비트와 ASR2 278비트의 초기상태를 만드는 과정으로 스트림 암호에서는 최종적인 키 생성 과정에서 초기상태는 매우 중요하며 [14] , 초기상태 값의 노출은 스트림 암호의 안전성과 밀접한 관계가 있다. 그림 1 의 ASR1과 ASR2의 초기상태 값을 만들기 위해 각각 128비트 사용자 비밀 키와 IV를 사용하여 555비트(277+278)를 초기화 한다. 초기화 과정은 다음과 같다.
그림 1 에 대한 세부적인 알고리즘은 그림 1 의 순서대로 다음 절부터 자세히 설명한다.
- 3.2. 라운드 키 생성
개발한 스트림 암호에서는 4개의 512비트, 총 2048비트 라운드 키가 필요하다. 그래서 블록 암호 SHACAL-2의 라운드 키 생성 알고리즘을 사용하여 2048비트 라운드 키를 생성한다. 생성된 라운드 키는 메모리에 저장 후 사용하는 것이 아니라 제어입력 신호와 파이프라인 단계에 따라 라운드 키를 생성하는 방법을 사용했다. 32비트 단위 라운드 키 생성 알고리즘은 수식 3이다.
PPT Slide
Lager Image
수식 3에서 σ 0 와 σ 1 는 수식 4와 같고 수식 3은 SHACAL-2의 키 스케줄링 알고리즘이다.
PPT Slide
Lager Image
수식 4에서 ROTR i (X)와 SR i (X)는 각각 32비트 X 값을 i비트 만큼 오른 쪽 순환(Rotation)과 시프트(Shift) 연산이다.
- 3.3. 산술시프트레지스터(ASR)
PRNG로 사용한 산술 시프트 레지스터(ASR)를 개발 한 스트림 암호에서는 2개를 사용했고 각각 ASR1 [15] , ASR2 [16] 이다. ASR1은 GF(2 277 )상에서 특성다항식 (Characteristic Polynomial)은 16진수로 0x00200000 0x00000001 0x00000001 0x00000001 0x00000001 0x00000001 0x00000001 0x00000002 0x00000015, D = 2 21 을 적용한다. 그리고 ASR2는 GF(2 278 )상에서 특성다항식은 16진수로 0x00400000 0x00000001 0x00000001 0x00000001 0x00000001 0x00000001 0x00000001 0x00000002 0x00000001, D = 2 22 를 적용한다. ASR1, 2의 동작 알고리즘은 수식 5, 6이며, 수식 5, 6에서 w1, w2는 각각 32비트 임시 저장 변수이고, ASR1, 2의 위 첨자 i(i = 1)는 현재 상태를 나타내고 i+1 은 다음 상태이고 아래 첨자는 각각 ASR의 워드 단위 순서 번호이다.
PPT Slide
Lager Image
PPT Slide
Lager Image
ASR1, 2는 매 시스템 클록(System clock)에 따라 다음 상태로 변환되고 각각의 ASR은 하위 256비트 만 사용된다.
- 3.4. Salsa20의 암호
Salsa20 내부 상태 공간은 32비트 워드로 이루어진 4x4 테이블로 총 512비트 크기를 갖는다. 내부 상태 공간의 갱신은 512비트의 입력과 512비트의 출력을 갖는 해시 함수를 통해 이루어진다. 해시 함수는 Salsa20의 핵심으로 실제 Salsa20은 해시 함수의 counter 모드를 스트림 암호로 이용한 것으로, 512비트의 평문에 키와 IV, 라운드 수를 해시한 결과를 XOR 연산으로 암호화한다. 이러한 해시 함수는 여러 개의 quarterround로 구성되어 있고 각 quarterround는 XOR, 산술 덧셈, 고정 길이 왼쪽 순환 연산으로 구성되어 있다.
개발한 스트림 암호는 Salsa20의 2중 함수(Doubleround function)을 그대로 사용하여 2라운드 씩 4번, 총 8라운드를 적용하여 256비트 출력을 갖는 스트림 암호이다.
PPT Slide
Lager Image
수식 7의 매크로 함수 SALSA는 Salsa20의 128비트 처리 quarterround 함수이고 s[]는 워드 단위 4x4를 1차원 배열(Array)로 정의했다. 그리고 2중 함수의 구현은 수식 7과 같이 8번의 SALSA 매크로 함수의 호출로 이루어진다.
- 3.5. 가변적인 표백과 mk
표백은 ASR1, 2가 의사랜덤수열을 생성함에 따라 계속해서 가변적인 256비트 값이 생성된다. 이는 암호와 복호가 같은 값을 가지며 그림 1 에서와 같이 256비트 암호문 생성 마지막 단계에 적용하여 암호문에 포함된 의미 있는 정보를 숨기기 위해 표백을 사용한다.
256비트 mk 역시 가변적이며, 256비트 평문에 의존적인 값으로 생성되며 이는 마지막 Salsa20의 2라운드에 적용되는 순환 구조를 갖는다. 그리고 표백과는 다르게 암호와 복호가 서로 다른 값을 가지며 이로 인해 개발한 스트림 암호 역시 암호와 복호가 다른 특성을 보인다. 수식 8은 256비트 암호문 생성 알고리즘이다.
PPT Slide
Lager Image
수식 8에서 사용된 변수들은 256비트이며, mk_t는 mk를 만들기 위한 256비트 임시변수이다. 그리고 salsaH, salsaL, whiten은 각각 Salsa20을 적용한 후 상위 256비트, 하위 256비트, 표백이며 P와 C는 각각 평문과 그에 대응되는 암호문이다.
수식 9는 수식 8에 대응되는 복호 알고리즘이다.
PPT Slide
Lager Image
가변적인 표백과 mk의 적용은 개발한 스트림 암호의 안전성에 많은 영향을 미치며 자세한 안전성 분석은 4장에서 설명한다.
Ⅳ. 구현 및 안전성 분석
개발한 256비트 출력 스트림 암호의 소프트웨어 구현은 Visual Studio 2010 C 컴파일러를 사용하였고 실행환경은 Windows 7, Intel Core2 i5-2415M CPU 2.30GHz, 2.30GHz, 2GB RAM의 환경에서 알고리즘의 수행 시간을 테스트했다. 결과는 표 2와 같다. 표 2 에서 각 알고리즘은 초기화 과정은 제외하고, 약 6.4Gb의 암호문 생성 시간을 2번째 열에 표시했으며, 마지막 열은 각 알고리즘들의 소프트웨어 수행 중 내부 상태 변환을 위한 전역 변수 메모리양을 비교한 값이다.
6.4Gb 스트림 암호문 생성시간과 사용된 메모리 비교Table. 26.4Gb Ciphertext generation time of stream cipher and memory used compare
PPT Slide
Lager Image
6.4Gb 스트림 암호문 생성시간과 사용된 메모리 비교 Table. 2 6.4Gb Ciphertext generation time of stream cipher and memory used compare
- 4.1. 소프트웨어 분석
표 1 의 분석에서 AES 소프트웨어 구현은 256바이트 S박스와 32비트 단위 연산인 MixColumns을 미리 계산하여 메모리에 저장 후 사용하는 방법으로 현재까지 AES 구현 방법들 중 가장 빠른 방식이다. 그러나 이를 하드웨어로 구현할 때는 표 1 에서와 같이 최소 1024바이트의 고정된 메모리가 필요한 방법이다. 1024바이트도 암호화에 필요한 최소 메모리이며 암호와 복호가 다 필요한 경우는 최소 2048바이트가 요구 된다.
Salsa20/8은 Salsa20을 8라운드로 축소한 것으로 Salsa20 개발자가 제공한 소프트웨어로 구현된 C소스를 그대로 사용하였다. 결과는 표 1 과 같이 개발한 스트림 암호와 Salsa20/8이 거의 차이가 없는 것으로 보인다.
- 4.2. 하드웨어 구현
하드웨어 구현은 Verilog HDL을 사용하여 Modelsim 6.5d로 개발한 스트림 암호 알고리즘의 기능을 검증하였고, 스트림 암호성능 검증은 Quartus II 13.1을 활용하여 분석한 결과, Altera Cyclone Ⅳ E FPGA에서 Compile한 결과는 Total Logic Elements : 34952 Cell, Total Registers : 0, Total Pins: 520 이다. 제어입력 신호인 d1, d2, d3, d4, d5는 각각 1GHz에서 동작하고 있으며 Worse Case에서 5.98MHz(1.53Gbps)의 성능을 보여주었다. 그림 2 는 전체 하드웨어 흐름도이다.
하드웨어 구현 요약Table. 3Hardware implementation summary
PPT Slide
Lager Image
하드웨어 구현 요약 Table. 3 Hardware implementation summary
그림 2 에서 clk, start, d1, d2, d3, d4, d5는 각각 1비트 제어입력신호이고, IV0 ~ IV3, K0 ~ K3은 각각 사용자가 입력한 128비트 IV와 비밀 키이며, P는 256비트 평문이고, 이에 대응되는 256비트 암호문은 C이다.
그림 2 에서와 같이 4개의 파이프라인을 통한 5단계 과정을 통해 256비트 암호문이 생성된다. 그러나 매번 암호문 생성이 5단계를 거치는 것이 아니라 파이프라인 구현이므로 첫 번째 암호문만 5단계를 수행하고 두 번째 이후는 1단계씩 수행할 때마다 256비트 암호문이 생성되기 때문에 대기시간(Latency)은 5단계이다.
PPT Slide
Lager Image
하드웨어 흐름도 Fig. 2 Hardware flow chart
- 4.3. 안전성 분석
개발한 스트림 암호의 안전성 분석은 가장 최신의 Salsa20의 분석방법에 근거하여 안전성을 설명한다. 그림 1 에서 ASR1, 2는 상태변화에 따라 의사랜덤수열을 계속해서 생성하며 생성된 수열을 개발한 스트림 암호의 내부 상태값으로 연속해서 갱신하고 있다. 따라서 ASR1, 2의 전체적인 선형 복잡도 분석 확률을 먼저 구하면, ASR1의 최소 선형 복잡도는 277비트이고 ASR2는 278비트로 서로 독립적으로 수행하고 있다. 이는 각각의 ASR의 554개와 556개 출력 값을 알면 ASR1, 2의 모든 상태를 분석할 수 있다. 그래서 1/554와 1/556의 확률은 약 (2 -9 ) 2 = 2 -18 이다. 그러므로 ASR1, 2의 안전성이 약 2 -18 이라고 추정할 수 있다. 그리고 각각 ASR은 0을 제외한 최대 주기 수열을 생성한다. 이는 각 ASR의 특정 비트 또는 비트열(연속적이거나 연속적이지 않는 모든 경우)은 0을 제외한 모든 값들이 동일한 출현 빈도수를 보여줌으로 특정한 값을 추정한 어떤 공격 [17] 에도 내성이 있다.
Salsa20은 다른 스트림 암호와는 구조적으로 다르며 블록 암호의 라운드 함수를 반복 적용하여 CTR모드처럼 생성된 수열을 스트림 키로 사용한다. 이를 바탕으로 최신의 Salsa20 분석방법은 2007년 Y. Tsunoo 등의 축소된 8라운드 차분분석 [18] 이 있다. 이 분석방법은 Salsa20 라운드 함수의 핵심인 32비트 정수덧셈의 차분 확률(Differential Probabilities)을 이용하여 8라운드까지 256비트 비밀 키를 전수조사보다 계산복잡도 (Computational complexity)가 낮은 약 2255인 결과를 보인다. 본 논문에서는 참고문헌 [18] 의 방법을 보수적인 관점에서 그대로 적용하며 추가적으로 그림 1 과 같이 Salsa20의 내부 상태값을 2개의 ASR이 연속적으로 갱신하고 있으며, 수식 8과 같이 평문의존적인 가변적인 mk를 적용하고 있다. 여기서 평문은 분석 대상이 아니며 salsaH와 salsaL은 각각 차분분석에 포함되어 있기 때문에 이를 바탕으로 개발한 스트림 암호의 8라운드 차분분석 계산복잡도는 약 2 18 * 2 255 = 2 273 이 된다.
2012년 Z. Shi 등의 향상된 키 복구 공격(Improved Key Recovery Attacks) [19] 은 256비트 키에 대해 8라운드 계산복잡도가 약 2 250 으로 현재까지 알려진 공격 중 가장 효율적인 Salsa20의 공격방법이다. 이 방법은 차분분석 방법을 기본으로 Salsa20의 라운드 함수에서 열 (CCD)과 행(RCD)의 Chaining Distinguishers를 통해 Distinguishers에 의존적인 키를 찾는 방법이다. 참고문헌 [19] 의 분석방법을 개발한 스트림 암호에 그대로 적용한 계산복잡도는 약 2 18 * 2 250 = 2 268 이 된다.
해시함수로 20라운드 전체에 대한 Salsa20 충돌 (Collisions) [20] 을 찾는 방법으로 Salsa20의 라운드 함수 중 수식 2의 계산인 quarterround의 열과 행 변환 함수를 적용할 때 특정한 입력(quarterround(A, -A, A, -A))은 항상 상수값(0)을 가지는 특성을 이용해 어떤 특정한 입력 쌍에 대해서 512비트 출력이 같아지는 충돌이 발생한다. 참고문헌 [20] 의 부록에 충돌이 발생하는 입력 쌍이 2가지 예시되어 있다. 본 논문의 스트림 암호는 이와 같은 충돌을 피하기 위한 2가지 기술적 방법을 추가했다.
첫 번째는 특정한 값의 입력을 피하기 위해 의사랜덤수열 발생기 ASR1, 2의 사용이다. ASR의 출력은 미리 예측할 수 없으며, 이는 Salsa20의 충돌을 위한 미리 계산된 입력을 사용할 수 없게 된다. 두 번째는 가변적인 mk의 적용이다. 그림 1 에서와 같이 평문의존적인 256비트 값이 다음번 Salsa20 6라운드에 사용되면서 Salsa20 라운드 함수에서 발생하는 혼돈(Confusion)과 확산(Diffusion)으로 충돌을 피할 수 있다.
개발한 스트림 암호의 내부 상태는 512비트이며 비밀 키와 IV가 각각 128비트로 총 256비트에 대한 전수조사 방법보다 더 낮은 확률이다. 따라서 개발한 스트림 암호(2 -273 , 2 -268 )의 안전성은 현대 암호에서 요구하는 안전성을 충분히 만족하고 있다. 계산적인 안전성으로 위와 같이 안전성이 입증되었지만 상관관계 분석 (Correlation Analysis) [21] 과 대수적 분석(Algebraic Analysis) [22] 에 대한 안전성은 입증하지 못하였다. 개발한 암호 알고리즘은 Salsa20의 라운드 함수를 그대로 사용하므로 Salsa20의 안전성이 개발한 암호의 안전성에 직접적인 영향을 미치고 있다. Salsa20은 축소된 라운드에서 차분분석 방법을 기본으로 유사한 분석방법들이 효과적이지만, 아직까지 안전성에 심각한 문제가 밝혀지진 안았다. 그래서 개발한 스트림 암호도 Salsa20의 안전성만큼 안전할 것으로 판단된다.
마지막으로 개발한 스트림 암호는 무결성이 우수하다. 수식 9에서 암호문 C가 공격자에 의해 임의로 변경될 경우 복호할 때 대응되는 위치의 평문도 변경되고, 다음번 이후의 평문은 연속해서 mk가 변경되므로 평문 전체가 복호가 되지 않는다. 이와 같은 특성 때문에 우수한 무결성을 보인다. 그리고 최종적인 암호문 출력전에 표백으로 XOR 연산은 Salsa20의 마지막 라운드 512비트의 상태 정보를 숨기기 위한 것이다.
Ⅴ. 결 론
스트림 암호의 동일한 키 재사용 금지와 무결성 보장이 안 되는 단점을 개선한 256비트 출력의 스트림 암호를 개발 했다. 개발한 스트림 암호는 Salsa20의 라운드 함수를 사용하여 8라운드 적용하고 5단계 파이프라인 구조의 하드웨어로 구현 했으며, WSN, DMB 등과 같은 응용에 적용하기 위해 실시간 처리와 빠른 성능을 보인다. 안전성도 현재까지 알려진 가장 성능 좋은 Salsa20의 분석 방법으로 분석한 결과 전수조사보다 더 낮은 분석확률을 보이며 이는 개발한 스트림 암호가 안전할 것으로 판단된다. 추후 연구 과제로 개발한 알고리즘을 좀 더 확장 개선하여 더욱 고속인 Gbps급 스트림 암호 알고리즘을 개발함으로써 실시간으로 고속 이동 무선 통신 환경의 암호화에 적용하고자 한다.
BIO
김길호(Gil-ho Kim)
2000년 한국방송통신대학교 전자계산학과 (이학사)
2002년 부경대학교 컴퓨터공학과 (공학석사)
2010년 부경대학교 컴퓨터공학과 (공학박사)
※관심분야 : 반도체회로설계, 암호 알고리즘, 컴퓨터 구조
김성기(Sung-gi Kim)
1977년 2월 울산대학교 응용 물리학과 졸업
1994년 2월 부경대학교 전자계산학과 석사
2004년 3월~현재 부경대학교 IT융합응용공학과 박사과정
※관심분야 : 반도체회로설계, 암호 알고리즘, 컴퓨터 구조
조경연(Gyeong-yeon Cho)
1990 인하대학교 공과대학전자공학과 정보공학전공 (공학박사)
1983-1991 삼보컴퓨터 기술연구소 책임연구원
1991-현재 부경대학교 IT융합응용공학과 교수
1991-2001 삼보컴퓨터 기술연구소 비상임기술 고문
1998-현재 에이디칩스 사외이사 겸 비상임기술고문
※관심분야 : 전산기구조, 반도체회로설계, 암호 알고리즘
References
2001 FIPS PUB 197, “Advanced Encryption Standard(AES),” NIST
Bernstein D. J. , Schwabe P. 2008 “New AES Software Speed Records,” INDOCRYPT 2008, LNCS 5365 322 - 336
http://www.ecrypt.eu.org/stream/
http://www.ecrypt.eu.org/stream/phase3list.html
Bernstein D. J. “Salsa20 - Design, Specification, Security and Speed,” http://www.ecrypt.eu.org/stream/e2-salsa20.html
Park C. S. , Cho G. Y. 2006 “Generalization of Galois Linear Feedback Register,” Institute of Electronics Engineers of Korea 43, C1 (1)
Wu H. “Stream Cipher HC-128,” http://www.ecrypt.eu.org/stream/e2-hc128.html
Boesgaard M. , Vesterager M. , Christensen T. , Zenner E. “The Stream Cipher Rabbit,” http://www.ecrypt.eu.org/stream/e2-rabbit.html
Berbain C. , Billet O. , Canteaut A. , Courtois N. , Gilbert H. , Goubin L. , Gouget A. , Granboulan L. , Lauradoux C. , Minier M. , Pornin T. , Sibert H. “Sosemanuk, a fast softwareoriented stream cipher,” http://www.ecrypt.eu.org/stream/e2-sosemanuk.html
Hell M. , Johansson T. , Meier W. “A Stream Cipher Proposal: Grain-128,” http://www.ecrypt.eu.org/stream/e2-grain.html
Babbage S. , Dodd M. “The stream cipher MICKEY 2.0,” http://www.ecrypt.eu.org/stream/e2-mickey.html
De Canniere C. , Preneel B. “Trivium-Specifications,”
De Canniere C. 2008 “eSTREAM Software Performance,” LNCS 4986 119 - 139
Souradyuti P. , Preneel B. 2003 “Analysis of Non-fortuitous RC4 key stream generator,” Progress in Crytology-INDOCRYPT
Zenner E. 2007 “Why IV Setup for Stream Cipher is Difficult,” Proceedings of Dagstuhl Seminar on Symmetric Cryptography
Kim G.H. , Cho G.Y. 2013 “Design and Implementation of Stream Cipher based on SHACAL-2 Superior in the Confidentiality and Integrity,” JKMMS 16 (12) 1427 - 1438    DOI : 10.9717/kmms.2013.16.12.1427
Kim G.H. , Cho G.Y. , Lee K.H. , Shin S.U 2012 “Implementation of fast stream cipher AA128 suitable for real time processing applications,” J. Korea Inst. Inf. Commun. Eng. 16 (10) 2207 - 2216    DOI : 10.6109/jkiice.2012.16.10.2207
Hawkes P. , Rose G. 2002 “Guess-and-determine attacks on SNOW,” In Selected Areas in Cryptography - SAC 2002, LNCS 2595 37 - 46
Tsunoo Y. , Saito T. , Kubo H. , Suzaki T. , Nakashima H. 2007 “Differential cryptanalysis of Salsa20/8,” eSTREAM report 2007/010 In SASC 2007
Shi Z. , Zhang B. , Feng D. , Wu W. 2012 “Improved Key Recovery Attacks on Reduced Round Salsa20 and ChaCha,” ICISC 2012, LNCS 7839 337 - 351
Castro J. C. H. , Estvez-Tapiador J. M. , Quisquater J. J. 2008 “On the salsa20 core function,” LNCS 5086 462 - 469
Hawkes P. , Rose G. 2000 “Correlation cryptanalysis of SSC2,” Presented at the Rump Session of CRYPTO
Courtois N. 2003 “Fast Algebraic Attack on Stream Ciphers with Linear Feedback,” Advances in Cryptology-CRYPTO 2003, LNCS 2729 176 - 194