HIGHT

HIGHT(HIGh security and light weigHT) 암호 알고리즘은 RFID, USN 등과 같이 저전력ㆍ경량화를 요구하는 컴퓨팅 환경에서 기밀성을 제공하기 위해 2005년 KISA, ETRI 부설연구소 및 고려대가 공동으로 개발한 GFS구조의 64비트 경량 블록 암호 알고리즘이다. 스마트폰, 스마트카드 및 RFID등과 같이 저전력, 경량화를 요구하는 모바일 환경에서 기밀성 있는 보안을 확보하기 위해 개발되었다.

특징

• 휴대형 기기 및 모바일 환경에 적합하도록 특수 설계되었고, 전력 소비가 적도록 개발된 블록 암호화 알고리즘이다.
• 8비트 단위의 기본적인 산술연산, XOR, 순환이동만으로 사용가능 하도록 간단구조로 설계되었다.
• 128비트 국산암호화 알고리즘 SEED에 비해 제한된 호나경에 적용하기위해 매우 간단한 구조의 안전성, 효율성을 동시에 고려하였다.
• 메모리와 같은 하드웨어 자원이 부족한 환경에 적합하도록 일반적인 블록 암호화 알고리즘과는 다르게 S-Box(Substitution-box)를 제거하였다.
• 2006년 12월 정보통신단체 표준으로 제정되었다.
• 2010년 12월 ISO/IEC 국제 표준으로 제정되었다.

알고리즘

HIGHT 알고리즘은 전체적으로 일반화된 Feistel 변형 구조로 이루어져 있으며, 64비트의 평문과 128비트의 키로부터 생성된 8개의 8비트 화이트닝키와 128개의 8비트 서브키를 입력으로 사용함으로써 총 32라운드를 거쳐서 64비트 암호문을 출력한다.

기호와 표기

64비트 평문과 암호문은 각각 8개의 바이트로 다음과 같다.

* 평문 : $P_{7}\ ||\ P_{6}\ ||\cdots ||\ P_{0}$
* 암호문 : $C_{7}\ ||\ C_{6}\ ||\cdots ||\ C_{0}$

64비트 라운드 함수 입·출력은 8개의 바이트로 다음과 같다.

* $X_{i}=X_{i,7}\ ||\ X_{i,6}\ ||\cdots ||\ X_{i,0},i=0,\cdots ,32$

128비트 키(마스터키)는 16개의 바이트로 다음과 같다.

* $MK=MK_{15}\ ||\ MK_{14}\ ||\cdots ||\ MK_{0}$

라운드 함수에 적용되는 라운드키는 서브키($SK_{i}$)와 화이트닝키($WK_{i}$)로 다음과 같다.

* $SK_{i},i=0,\cdots ,127$
* $WK_{i},i=0,\cdots ,7$

산술 연산 기호

* ⊞ : 법 $2^{8}$ 덧셈
* ⊟ : 법 $2^{8}$ 뺄셈
* ⊕ : XOR (배타적 논리합)
* $A^{<<8}$ : 8비트 값 A에 대한 8비트 좌측 순환 이동

키 스케줄

HIGHT의 라운드키는 화이트닝키와 LFSR을 사용하여 생성한 서브키들로 이루어진다.

• 화이트닝키 생성

화이트닝키는 마스터키를 사용하여 다음과 같은 방법으로 생성한다.

$WK_{i}={\begin{cases}MK_{i+12}&,&0\leq i\leq 3\\MK_{i-4}&,&4\leq i\leq 7\end{cases}}$

LFSR(Left Feedback Shift Register) $h$

LFSR $h$의 연결 다항식은 $x^{7}+x^{3}+1$이다. 이 다항식은 $F_{2}[x]$에서 원시다항식이기 때문에 $h$는 $2^{7}-1=127$의 주기를 갖는다. $h$의 초기 내부 상태 값은 $\delta _{0}=(s_{6},s_{5},s_{4},s_{3},s_{2},s_{1},s_{0})=(1,0,1,1,0,1,0)_{2}$으로 정해진다. 그러면 $i=1,\cdots ,127$에 대하여 $\delta _{i}$는 다음과 같이 생성된다.

$s_{i+6}=s_{i+2}\oplus s_{i-1},$

$\delta _{i}=(s_{i+6},s_{i+5},s_{i+4},s_{i+3},s_{i+2},s_{i+1},s_{i}),$     $1\leq i\leq 127$

$h$의 주기가 127이기 때문에 $\delta _{0}=\delta _{1}27$이다.

• 서브키 생성

서브키를 생성하는 알고리즘은 다음과 같이 구성된다.

:$For\ i=0\ to\ 7$
::$For\ j=0\ to\ 7$
:::$SK_{16\cdot i+j}\leftarrow MK_{j-imod8}\boxplus \delta _{16\cdot i+j}$;
::$For\ j=0\ to\ 7$
:::$SK_{16\cdot i+j+8}\leftarrow MK_{(j-imod8)+8}\boxplus \delta _{16\cdot i+j+8}$;
$\delta _{i}\ (0\leq i\leq 127)$는 LFSR $h$의 내부 상태의 값들이다.

• 암호화키 생성

HIGHT의 암호화 알고리즘이 수행되기 위하여 라운드키 생성과정은 바이트 단위의 8개의 화이트닝키($WK_{0},\cdots ,WK_{7}$)와 128개의 서브키($SK_{0},\cdots ,SK_{127}$)를 생성한다.

복호화키 생성

HIGHT의 복호화 알고리즘은 암호화 알고리즘과 같은 화이트닝키와 서브키 바이트들을 이용하지만 순서가 다르다. 복호화 알고리즘에서는 $WK_{4},WK_{5},WK_{6},WK_{7}$이 초기 변환에, $WK_{0},WK_{1},WK_{2},WK_{3}$이 최종 변환에 사용된다. 복호화 알고리즘에서 사용되는 서브키 바이트들은 $SK'_{i}$로 표시되며, 다음과 같이 정의된다.

$SK'_{i}=SK_{127-i},$     $i=0,\cdots ,127$

암호화

• 암호화 초기 변환

HIGHT 암호화의 초기 변환은 네 개의 화이트닝키 바이트($WK_{0},WK_{1},WK_{2},WK_{3}$)를 이용하여 평문 $P$를 첫 번째 라운드 함수의 입력인 $X_{0}=X_{0,7}\ ||\ X_{0,6}\ ||\cdots ||\ X_{0,0}$

로 변환한다.

$X_{0,i}=P_{i},\quad i=1,3,5,7$
$X_{0,0}=P_{0}\boxplus WK_{0}$
$X_{0,2}=P_{2}\oplus WK_{1}$
$X_{0,4}=P_{4}\boxplus WK_{2}$
$X_{0,6}=P_{6}\oplus WK_{3}$

• 암호화 라운드 함수

HIGHT의 라운드 함수는 다음과 같은 두개의 보조 함수를 갖는다.

$F_{0}(X)=X^{<<1}\oplus X^{<<2}\oplus X^{<<7}$
$F_{1}(X)=X^{<<3}\oplus X^{<<4}\oplus X^{<<6}$

라운드 함수는 $Round_{1}$ 부터 $Round_{32}$까지 32회 반복한다. 각 $i$번째 라운드 함수 $Round_{i},\ i=1,\cdots ,\ 31$는 $X_{i-1}=X_{i-1,7}\ ||\cdots ||\ X_{i-1,0}$를 $X_{i}=X_{i,7}\ ||\cdots ||\ X_{i,0}$와 같이 변화한다.

$X_{i,j}=X{i-1,j-1},j=1,3,5,7$
$X_{i,0}=X{i-1,7}\oplus (F_{0}(X_{i-1,6})\boxplus SK_{4i-1})$
$X_{i,2}=X{i-1,1}\oplus (F_{0}(X_{i-1,0})\boxplus SK_{4i-4})$
$X_{i,4}=X{i-1,3}\oplus (F_{0}(X_{i-1,2})\boxplus SK_{4i-3})$
$X_{i,6}=X{i-1,5}\oplus (F_{0}(X_{i-1,4})\boxplus SK_{4i-2})$

마지막 라운드 함수($Round_{32}$)에서는 바이트들을 섞지 않는다. 따라서 입력값 $X_{31}=X_{31,7}\ ||\cdots ||\ X_{31,0}$으로부터 출력값 $X_{32}=X_{32,7}||\cdots ||X_{32,0}$은 다음과 같이 계산된다.

$X_{32,i}=X{31,i},\ i=0,2,4,6$
$X_{32,1}=X{31,1},\boxplus (F_{1}(X_{31,0})\oplus SK_{124}$
$X_{32,3}=X{31,3},\oplus (F_{0}(X_{31,2})\boxplus SK_{125}$
$X_{32,5}=X{31,5},\boxplus (F_{1}(X_{31,4})\oplus SK_{126}$
$X_{32,7}=X{31,7},\oplus (F_{0}(X_{31,6})\boxplus SK_{127}$

암호화 최종 변환

HIGHT의 최종 변환은 $Round_{32}$의 출력인 $X_{32}=X_{32,7}\ ||\cdots ||\ X_{32,0}$을 4개의 화이트닝키($WK_{4},WK_{5},WK_{6},WK_{7}$)를 이용하여 변환한다.

$C_{i}=X_{32,i},\ i=1,3,5,7$
$C_{0}=X_{32,0}\boxplus WK_{4}$
$C_{2}=X_{32,2}\oplus WK_{5}$
$C_{4}=X_{32,4}\boxplus WK_{6}$
$C_{6}=X_{32,6}\oplus WK_{7}$

복호화

HIGHT의 복호화 알고리즘은 암호화 알고리즘과 마찬가지로 라운드키 생성과정, 초기 변환(암호화 최종 변환의 역변환), 라운드 함수 32회 반복, 최종 변환(암호화 초기 변환의 역변환)으로 구성되어 있다. 복호화 알고리즘에서의 중간값은 $X_{i}^{'}=X_{i,7}^{'}\ ||\cdots ||\ X_{i,0}^{'},\ i=0,\cdots ,32$로 표시된다.

• 복호화 초기변환

복호화 알고리즘의 초기 변환은 암호화 알고리즘의 최종 변환에 대한 역변환이다. 이 함수는 4개의 화이트닝키($WK_{4},WK_{5},WK_{6},WK_{7}$)를 이용하여 암호문 $C$를 복호화 알고리즘의 첫 번째 라운드 함수의 입력값($X_{0,i}^{'}=X_{0,7}^{'},\ ||\cdots ||\ X_{0,0}^{'}$)으로 다음과 같이 변환한다.

$X_{0,i}^{'}=C_{i},\ i=1,3,5,7$
$X_{0,0}^{'}=C_{0}\boxminus WK_{4}$
$X_{0,2}^{'}=C_{2}\oplus WK_{5}$
$X_{0,4}^{'}=C_{4}\boxminus WK_{6}$
$X_{0,6}^{'}=C_{6}\oplus WK_{7}$

• 복호화 라운드 함수

복호화 알고리즘의 $i$번째 라운드 함수를 $Round_{i}^{'},\ i=1,\cdots ,32$로 표시한다.
$i$번째 라운드 함수 $Round_{i}^{'}$는 $X_{i-1}^{'}=X_{i-1,7}^{'}\ ||\cdots ||\ X_{i-1,0}^{'}$를 $X_{i}^{'}=X_{i,7}^{'}\ ||\cdots ||\ X_{i,0}^{'}$로 다음과 같이 변환한다.

$X_{i,j}^{'}=X_{i-1,j+1\ mod8}^{'},\ j=1,3,5,7$
$X_{0,0}^{'}=X_{i-1,1}^{'}\boxminus (F_{1}(X_{i-1,0}^{'})\oplus SK_{4i-1}^{'})$
$X_{0,2}^{'}=X_{i-1,3}^{'}\oplus (F_{0}(X_{i-1,2}^{'})\boxplus SK_{4i-2}^{'})$
$X_{0,4}^{'}=X_{i-1,5}^{'}\boxminus (F_{1}(X_{i-1,4}^{'})\oplus SK_{4i-3}^{'})$
$X_{0,6}^{'}=X_{i-1,7}^{'}\oplus (F_{0}(X_{i-1,6}^{'})\boxplus SK_{4i-4}^{'})$

암호화 알고리즘에서와 마찬가지로, 마지막 라운드 함수($Round_{32}^{'}$)에서는 바이트들을 섞지 않는다. 따라서 다음과 같이 연산된다.

$X_{32,i}^{'}=X_{31,i}^{'},\ i=0,2,4,6$
$X_{32,1}^{'}=X_{31,1}^{'}\boxminus (F_{1}(X_{31,0}^{'})\oplus SK_{127}^{'})$
$X_{32,3}^{'}=X_{31,3}^{'}\oplus (F_{0}(X_{31,2}^{'})\boxplus SK_{126}^{'})$
$X_{32,5}^{'}=X_{31,5}^{'}\boxminus (F_{1}(X_{31,4}^{'})\oplus SK_{125}^{'})$
$X_{32,7}^{'}=X_{31,7}^{'}\oplus (F_{0}(X_{31,6}^{'})\boxplus SK_{124}^{'})$

• 복호화 최종 변환

복호화 알고리즘의 최종 변환은 암호화 알고리즘에서의 초기 변환에 대한 역변환이다. 이 함수는 네 개의 화이트닝키($:X_{32}^{'}=X_{32,7}^{'}\ ||\cdots ||\ X_{32,0}^{'}$을 평문 $P$로 변환한다.

$P_{i}=X_{32,i}^{'},\ i=1,3,5,7$
$P_{0}=X_{32,0}^{'}\boxminus WK_{0}$
$P_{2}=X_{32,2}^{'}\oplus WK_{1}$
$P_{4}=X_{32,4}^{'}\boxminus WK_{2}$
$P_{6}=X_{32,6}^{'}\oplus WK_{3}$

전망

국산 암호화 기술이 스마트폰, USN, U-City, U-Health등 유비쿼터스 환경에서 널리 활용될 수 있도록 중소기업을 포함한 산학연(산업계, 학계, 연구분야)을 대상으로 무료로 소스코드를 배포하는 등 암호이용 활성화를 위해 지속적으로 지원할 계획이라고 한다.

참고자료

• 경수, 〈HIGHT 암호 알고리즘에 대해〉, 《네이버 블로그》 , 2017-01-31
• 한국인터넷진흥원, "HIGHT 블록암호 알고리즘 사양 및 세부 명세서", 2009-07
• 오병민기자, "스마트폰용 국산 경량 암호화 기술 국제표준으로 채택" 《보안뉴스》, 2010-06-08

이 HIGHT 문서는 알고리즘에 관한 토막글입니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 이 문서의 내용을 채워주세요.

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘, 알고리즘 □■⊕, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 채굴 알고리즘 SHA-256 • X11 • X11고스트 • X13 • X14 • X15 • X16R • X17 • 그로스톨 • 네오스크립트 • 니스트5 • 리라2알이 • 미리아드-그로스톨 • 블레이크 • 블레이크2 • 블레이크B • 블레이크2B • 블레이크256R8 • 블레이크256R14 • 스컹크해시 • 스케인 • 스크립트 알고리즘 • 스크립트엔 • 엘비알와이(LBRY) • 이더해시 • 이퀴해시 • 제반 • 쿼크 알고리즘 • 큐빗 알고리즘 • 크립토나이트 • 크립토나이트 라이트 • 타임트래블10 • 텐서리티 • 파스칼 • 프로그작업증명(ProgPoW) 매칭 알고리즘 BM25 • FAISS • 경매 • 더치 경매 • 매칭 알고리즘 • 매칭튜터 • 벡터검색 • 비크리 경매 • 센디 • 집닥 • 튜다 • 틴더 추천 알고리즘 TF-IDF • 역문서빈도(IDF) • 용어빈도(TF) • 추천 알고리즘 • 콘텐츠 기반 필터링 • 협업 필터링 고급 검색 알고리즘 AND-OR 검색 트리 • 국소 검색 알고리즘 • 국소 다발 검색 • 모의정련 • 언덕 오르기 검색 • 유전 알고리즘 대항 검색 검색의 차단 • 알파베타 가지치기 • 전방 가지치기 • 최소최대 알고리즘 제약 만족 문제 국소검색 • 역추적검색 • 제약전파 게임이론 게임이론 • 공유지의 비극 • 내시균형 • 메커니즘 디자인 • 비협조게임 • 사회선택이론 • 역게임이론 • 제로섬게임 • 조정게임 • 죄수의 딜레마 • 치킨게임 • 팃포탯 • 협조게임 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반