카스미

KASUMI
카스미
일반
디자이너미쓰비시 전기
유래미스티1
암호 상세
키 사이즈128비트
블록 크기64비트
구조.파이스텔 네트워크
라운드8

KASUMIUMTS, GSMGPRS 모바일 통신 시스템에서 사용되는 블록 암호입니다.UMTS에서 KASUMI는 기밀성(f8)과 무결성 알고리즘(f9)에 각각 [1]UEA1과 UIA1이라는 이름으로 사용된다.GSM에서 KASUMI는 A5/3 키 스트림 제너레이터 및 GEA3 키 스트림 제너레이터의 GPRS에서 사용됩니다.

KASUMI는 유럽표준기구 ETSI[2]일부인 SAGE(Security Algorithms Group of Experts)에 의해 UMTS 보안시스템에서 사용되는 3GPP를 위해 설계되었습니다.SAGE는 3GPP 표준화에 따른 일정상의 압박 때문에 새로운 암호를 개발하는 대신 3GPP 기술 사양 그룹(TSG)과 3G 보안(SA3)의 시스템 측면에 대해 이미 [2]일부 평가를 거친 기존 알고리즘을 기반으로 개발하기로 합의했다.이들은 미쓰비시전기가 개발해 특허를 낸 암호[4] 알고리즘[3] 선택했다.원래 알고리즘은 하드웨어 구현이 용이하고 3G 이동통신 보안에 설정된 기타 요건을 충족하도록 약간 수정되었습니다.

KASUMI는 원래 알고리즘인 MISTY1에서 따온 이름입니다.- 「히라가나」(로마지 카스미)는 「미스트」의 일본어입니다.

2010년 1월, Orr Dunkelman, Nathan Keller 및 Adi Shamir는 관련 키 공격과 매우 적은 계산 리소스로 Kasumi를 공격할 수 있다는 논문을 발표했습니다.이 공격은 MISTY1에 대해서는 효과가 없습니다.[5]

묘사

KASUMI 알고리즘은 3GPP [6]기술사양에 규정되어 있습니다.KASUMI는 128비트키와 64비트 입출력 블록암호입니다카스미의 핵심은 8라운드 페이스텔 네트워크다.메인 Feistel 네트워크의 라운드 함수는 되돌릴 수 없는 Feistel과 같은 네트워크 변환입니다.라운드 함수는 각 라운드마다 고정 키 스케줄을 사용하여 원래 128비트 키에서 파생된 8개의 16비트 서브 키로 구성된 라운드 키를 사용합니다.

주요 일정

128비트 키 K는 8개의 16비트 서브키i K로 나뉩니다.

또한 마찬가지로 16비트 서브키 K'i로 분할된 수정키 K'를 사용한다.변경된 키는 0x123456789를 사용한 XORing에 의해 원래 키에서 파생됩니다.ABCDEFFEDCBA9876543210 ('nothing secret' 번호로서 선택).

라운드 키는 지정된 양만큼 왼쪽으로 비트 회전하여 하위 키와 수정된 하위 키(변경되지 않음)에서 파생됩니다.

라운드 키는 다음과 같습니다.

서브키 인덱스의 추가는 순환이기 때문에 i+j가 8보다 크면 실제 서브키 인덱스를 얻기 위해 결과에서 8을 빼야 합니다.

알고리즘

KASUMI 알고리즘은 64비트 워드를 2개의 32비트 반쪽(왼쪽(과 오른쪽(으로 처리합니다.입력 단어는 첫 번째 라운드의 왼쪽과 오른쪽 절반을 연결한 것입니다.

각 라운드에서 오른쪽 절반은 라운드 함수의 출력과 함께 XOR 처리되며, 이후 절반은 교환됩니다.

여기i KL, KOi, KIi i라운드th 라운드 키입니다.

짝수와 홀수의 라운드 함수는 약간 다릅니다.각 경우에 라운드 함수는 2개의 함수i FL과 FOi 구성됩니다.홀수 라운드의 경우

공평한 라운드를 위해

출력은 마지막 라운드의 출력을 연결한 것입니다.

t 8 8( \ { output } \ ,

FL FO 기능은 모두 32비트 입력 데이터를 2개의 16비트 반으로 나눕니다.FL 함수는 되돌릴 수 없는 비트 조작이며, FO 함수는 되돌릴 수 없는 3라운드 Feistel 유사 네트워크입니다.

함수 FL

의 32비트 입력 x( L , FL(KL_))는 2개의 16비트 ({ x로 나뉩니다. 먼저 의 왼쪽 절반은 1 l 함께 비트 단위로 나뉩니다.그 결과 r의 오른쪽 가 적용되어 r의 오른쪽 절반에 합니다

으로 출력 r의오른쪽 절반({ r 라운드 KL_}})로 OR하여 왼쪽으로 1비트 회전합니다. 결과 l의 왼쪽 절반을 얻기 위해 입력 왼쪽 절반으로 XOR이 됩니다

함수의 출력은 좌우 x r { x'=의 연결입니다.

함수 FO

32비트 ( K , i ,) ( FO ( _ { , _ { , ) )는 2개의 16비트 0 ( \ x =_ \ 으로 분할되어 Feistel 네트워크를 3회 통과합니다.

3라운드(값 1, 2, 3을 취하는 j로 색인화)에서 왼쪽 절반이 새로운 오른쪽 반을 얻도록 수정되고 오른쪽 반이 다음 라운드의 왼쪽 반이 됩니다.

함수의 은 x 33 { { x ' =_ { \ r {3 입니다.

기능 FI

함수 FI는 불규칙한 Feistel과 같은 네트워크입니다.

16비트 x({ x {x}, { FI 2개의 x 0 ({ x0})로 분할되며, ({ 9비트, wide 입니다.

왼쪽 비트는 먼저 9비트 대체 상자(S박스) S9에 의해 섞이고 그 결과 XOR에 0확장 r 0r_})을 붙여 새로운 9비트 오른쪽 r 을 얻습니다.

오른쪽 r0의 비트({ 7비트 S박스 S7에 의해 섞이고 그 결과 새로운 오른쪽 r의 최하위 비트(LS7)가 XOR되어 새로운 7비트 왼쪽 됩니다.

중간 1 1 r r 1 { \ style { } = { 1 } \ _ { { key ki키 KI로 XOR 처리하여 x =2} \ {2 and and and and and 2 \ _ {) ) and wide wide ) and2

오른쪽 ({2})는 9비트 S박스 S9에 의해 섞이고 그 결과 의 새로운9비트 오른쪽 절반인 왼쪽 XOR됩니다.

마지막으로 왼쪽 비트({ 7비트 S박스 S7로 섞은 후 의 오른쪽 절반의 최하위 비트(LS7)를 XOR하여 출력의 왼쪽 비트({ 얻는다.

출력은 x 33 { x'=}\ 의 최종 합입니다.

대체 상자

대체 박스(S박스) S7 및 S9는 사양의 비트 단위 AND-XOR 식과 룩업 테이블 양쪽에 의해 정의된다.비트 단위의 표현은 하드웨어 실장을 목적으로 하고 있습니다만, 현재는 하드웨어 설계에서도 룩업테이블을 사용하는 것이 일반적입니다.

S7은 다음 어레이로 정의됩니다.

인트 S7[128] = {    54, 50, 62, 56, 22, 34, 94, 96, 38,  6, 63, 93,  2, 18,123, 33,    55,113, 39,114, 21, 67, 65, 12, 47, 73, 46, 27, 25,111,124, 81,    53,  9,121, 79, 52, 60, 58, 48,101,127, 40,120,104, 70, 71, 43,    20,122, 72, 61, 23,109, 13,100, 77,  1, 16,  7, 82, 10,105, 98,   117,116, 76, 11, 89,106,  0,125,118, 99, 86, 69, 30, 57,126, 87,   112, 51, 17,  5, 95, 14, 90, 84, 91,  8, 35,103, 32, 97, 28, 66,   102, 31, 26, 45, 75,  4, 85, 92, 37, 74, 80, 49, 68, 29,115, 44,    64,107,108, 24,110, 83, 36, 78, 42, 19, 15, 41, 88,119, 59,  3 }; 

S9은 다음 어레이로 정의됩니다.

인트 S9[512] = {   167,239,161,379,391,334,  9,338, 38,226, 48,358,452,385, 90,397,   183,253,147,331,415,340, 51,362,306,500,262, 82,216,159,356,177,   175,241,489, 37,206, 17,  0,333, 44,254,378, 58,143,220, 81,400,    95,  3,315,245, 54,235,218,405,472,264,172,494,371,290,399, 76,   165,197,395,121,257,480,423,212,240, 28,462,176,406,507,288,223,   501,407,249,265, 89,186,221,428,164, 74,440,196,458,421,350,163,   232,158,134,354, 13,250,491,142,191, 69,193,425,152,227,366,135,   344,300,276,242,437,320,113,278, 11,243, 87,317, 36, 93,496, 27,      487,446,482, 41, 68,156,457,131,326,403,339, 20, 39,115,442,124,   475,384,508, 53,112,170,479,151,126,169, 73,268,279,321,168,364,   363,292, 46,499,393,327,324, 24,456,267,157,460,488,426,309,229,   439,506,208,271,349,401,434,236, 16,209,359, 52, 56,120,199,277,   465,416,252,287,246,  6, 83,305,420,345,153,502, 65, 61,244,282,   173,222,418, 67,386,368,261,101,476,291,195,430, 49, 79,166,330,   280,383,373,128,382,408,155,495,367,388,274,107,459,417, 62,454,   132,225,203,316,234, 14,301, 91,503,286,424,211,347,307,140,374,       35,103,125,427, 19,214,453,146,498,314,444,230,256,329,198,285,    50,116, 78,410, 10,205,510,171,231, 45,139,467, 29, 86,505, 32,    72, 26,342,150,313,490,431,238,411,325,149,473, 40,119,174,355,   185,233,389, 71,448,273,372, 55,110,178,322, 12,469,392,369,190,     1,109,375,137,181, 88, 75,308,260,484, 98,272,370,275,412,111,   336,318,  4,504,492,259,304, 77,337,435, 21,357,303,332,483, 18,    47, 85, 25,497,474,289,100,269,296,478,270,106, 31,104,433, 84,   414,486,394, 96, 99,154,511,148,413,361,409,255,162,215,302,201,      266,351,343,144,441,365,108,298,251, 34,182,509,138,210,335,133,   311,352,328,141,396,346,123,319,450,281,429,228,443,481, 92,404,   485,422,248,297, 23,213,130,466, 22,217,283, 70,294,360,419,127,   312,377,  7,468,194,  2,117,295,463,258,224,447,247,187, 80,398,   284,353,105,390,299,471,470,184, 57,200,348, 63,204,188, 33,451,    97, 30,310,219, 94,160,129,493, 64,179,263,102,189,207,114,402,   438,477,387,122,192, 42,381,  5,145,118,180,449,293,323,136,380,    43, 66, 60,455,341,445,202,432,  8,237, 15,376,436,464, 59,461 }; 

암호 분석

2001년에는 Kün(2001)[7]에 의해 6라운드 KASUMI에 대한 불가능한 차분 공격이 제시되었다.

2003년, Elad Barkan, Eli Biham 및 Nathan Keller는 A5/3 암호를 피한 GSM 프로토콜에 대한 중간자 공격을 시연하여 프로토콜을 어겼습니다.다만,[8] 이 어프로치에서는, A5/3 암호는 공격되지 않습니다.이 논문의 정식 [9]버전은 2006년 후반에 출판되었다.

2005년 이스라엘 연구자 엘리 비함, 오르 던켈만, 네이선 켈러는 카스미에 대해 철저한 검색보다 [10]8라운드를 더 빨리 파괴할 수 있는 관련 직사각형(부메랑) 공격을 발표했다.공격에는 2개의 선택된 플레인텍스트가 필요합니다54.6.각각은 관련된4개의 키 중 하나로 암호화되어 있으며, 2개의 KASUMI 암호화와 같은76.1 시간 복잡성이 있습니다.이것은 분명히 실질적인 공격은 아니지만, KASUMI의 추정 강도에 의존했던 3GPP 프로토콜의 보안에 대한 몇 가지 증거를 무효화한다.

2010년 던켈만, 켈러, 샤미르는 A5/3 키를 관련 키 공격에 의해 [5]완전히 회복할 수 있는 새로운 공격을 발표했습니다.공격의 시간과 공간의 복잡성은 저자가 최적화되지 않은 레퍼런스 KASUMI를 사용하여 인텔 Core 2 Duo 데스크톱 컴퓨터에서 2시간 만에 공격을 수행할 정도로 충분히 낮습니다.저자들은 이 공격이 3G 시스템에서 A5/3를 사용하는 방법에는 적용되지 않을 수 있다고 지적한다.그들의 주된 목적은 MISTY에 대한 변경이 알고리즘의 보안에 큰 영향을 미치지 않는다는 3GPP의 보증을 의심하는 것이었다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ "Draft Report of SA3 #38" (PDF). 3GPP. 2005.
  2. ^ a b "General Report on the Design, Speification and Evaluation of 3GPP Standard Confidentiality and Integrity Algorithms" (PDF). 3GPP. 2009.
  3. ^ Matsui, Mitsuru; Tokita, Toshio (Dec 2000). "MISTY, KASUMI and Camellia Cipher Algorithm Development" (PDF). Mitsubishi Electric Advance. Mitsubishi Electric corp. 100: 2–8. ISSN 1345-3041. Archived from the original (PDF) on 2008-07-24. Retrieved 2010-01-06.
  4. ^ US 7096369, 마쓰이, 미츠루, 도키타, 토시오, 2002년 9월 19일 발행, 2006년 8월 22일 발행
  5. ^ a b Orr Dunkelman; Nathan Keller; Adi Shamir (2010-01-10). "A Practical-Time Attack on the A5/3 Cryptosystem Used in Third Generation GSM Telephony". {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  6. ^ "3GPP TS 35.202: Specification of the 3GPP confidentiality and integrity algorithms; Document 2: Kasumi specification". 3GPP. 2009.
  7. ^ Kühn, Ulrich. Cryptanalysis of Reduced Round MISTY. EUROCRYPT 2001. CiteSeerX 10.1.1.59.7609.
  8. ^ Elad Barkan, Eli Biham, Nathan Keller. Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication (PDF). CRYPTO 2003. pp. 600–616.{{cite conference}}: CS1 maint: 여러 이름: 작성자 목록(링크)
  9. ^ Elad Barkan, Eli Biham, Nathan Keller. "Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication by Barkan and Biham of Technion (Full Version)" (PDF).{{cite web}}: CS1 maint: 여러 이름: 작성자 목록(링크)
  10. ^ Eli Biham, Orr Dunkelman, Nathan Keller. A Related-Key Rectangle Attack on the Full KASUMI. ASIACRYPT 2005. pp. 443–461. Archived from the original (ps) on 2013-10-11.{{cite conference}}: CS1 maint: 여러 이름: 작성자 목록(링크)

외부 링크