길이연장공격

Length extension attack

암호화와 컴퓨터 보안에서 길이 확장 공격은 공격자가 메시지의 내용을1 알 필요 없이 공격자가 통제하는 메시지에2 대해 해시(메시지1)와 메시지1 길이를 사용하여 해시(메시지1 ‖)를2 계산할 수 있는 공격 유형이다. MD5, SHA-1과 같은 알고리즘과 Merkle-Damgård 구조에 기초한 대부분의 SHA-2는 이러한 공격에 취약하다.[1][2][3] SHA-384와 SHA-512/256을 포함한 SHA-2의 잘린 버전은 취약하지 않으며,[4] SHA-3 알고리즘도 취약하지 않다.[5]

Merkle-Damghrd 기반 해시가 빌드 H(비밀 ‖ 메시지)와 함께 메시지 인증 코드로 오용되고,[1] 메시지 및 비밀의 길이가 알려지면, 길이 연장 공격은 누구나 메시지의 끝에 추가 정보를 포함시켜 비밀을 알지 못한 채 유효한 해시를 만들 수 있다. HMAC는 이 구조를 사용하지 않기 때문에 HMAC 해시는 길이 확장 공격의 경향이 없다.[6]

설명

취약한 해싱 기능은 입력 메시지를 받아 내부 상태를 변환하는 데 사용하는 방식으로 작동한다. 입력이 모두 처리된 후 함수의 내부 상태를 출력하여 해시 다이제스트가 생성된다. 해시 다이제스트에서 내부 상태를 재구성할 수 있으며, 그 후 새로운 데이터를 처리하는 데 사용할 수 있다. 이런 식으로 메시지를 확장하고 새 메시지의 유효한 서명인 해시를 계산할 수 있다.

예

특정 유형의 와플을 특정 위치에서 특정 사용자에게 전달하기 위한 서버를 구현하여 지정된 형식의 요청을 처리할 수 있다. 

원본 데이터: count=10&lat=37.351&user_id=1&long=-119.827&waplle=eggo 원본 서명: 6d5f807e23db210bc254a28be2d6759a0f5f5d99

서명이 사용자에게 유효한 경우에만 서버는 주어진 요청(사용자 "1"을 위해 주어진 위치에 에고 타입의 와플 10개를 배달해 달라)을 수행할 것이다. 여기서 사용하는 서명은 공격자에게 알려지지 않은 키로 서명된 MAC이다. (이 예 역시 같은 요청과 서명을 두 번 보내 재생 공격에 취약하다.)

공격자는 이 예에서 요청된 와플을 "에고"에서 "거짓말"로 바꾸는 등 요청을 수정할 수 있다. 이는 쿼리 문자열의 중복된 내용이 후자의 값을 우선하는 경우 메시지 형식의 유연성을 이용하여 수행할 수 있다. 이러한 유연성은 메시지 형식의 착취를 나타내지 않는데, 이는 메시지 형식이 애초에 암호화된 보안성을 갖도록 설계되지 않았기 때문이며, 이를 돕기 위한 서명 알고리즘이 없었기 때문이다. 

원하는 새 데이터: count=10&lat=37.351&user_id=1&long=-119.827&wafle=eggo&wafle=liege.

이 새로운 메시지에 서명하기 위해서는 일반적으로 공격자가 메시지가 서명된 키를 알고 새 MAC를 생성하여 새 서명을 생성해야 한다. 단, 길이연장 공격으로는 해시함수의 상태로 해시(위에서 부여한 서명)를 공급할 수 있으며, 원래 요청이 중단된 곳에서 원래 요청의 길이를 아는 한 계속 진행할 수 있다. 이 요청에서, 원본 키의 길이는 14바이트로, 이는 다양한 가정한 길이의 위조 요청을 시도하고, 서버가 유효하다고 받아들이는 요청을 확인하는 것으로 결정될 수 있었다.[further explanation needed]

해싱 함수에 공급되는 메시지는 종종 패딩되는데, 많은 알고리즘은 길이가 특정 크기의 배수인 입력 메시지에서만 작동할 수 있기 때문이다. 이 패딩의 내용은 항상 사용되는 해시함수에 의해 지정된다. 공격자는 메시지의 내부 상태가 정렬되기 전에 위조한 메시지에 이러한 패딩 비트를 모두 포함해야 한다. 따라서 공격자는 다음과 같은 패딩 규칙을 사용하여 약간 다른 메시지를 생성한다. 

New Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo\x80\x00\x00 \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00 \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00 \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00 \x00\x00\x00\x02\x28&waffle=liege

이 메시지에는 페이로드 전 해시함수 내부의 원래 메시지에 추가된 패딩이 모두 포함된다(이 경우 0x80에 이어 0x00s의 숫자와 0x228 = 552 = (14+55)*8은 키의 길이와 끝에 추가된 원본 메시지를 더한 것이다). 공격자는 원래 메시지에 대해 해시된 키/메시지 쌍 뒤에 있는 상태가 최종 "&"까지의 새 메시지의 상태와 동일하다는 것을 알고 있다. 공격자는 이 시점에서 해시 다이제스트도 알고 있는데, 이는 그 시점에서 해시함수의 내부 상태를 알고 있다는 것을 의미한다. 그런 다음 해싱 알고리즘을 그 시점에서 초기화하고, 마지막 몇 글자를 입력하며, 원본 키 없이 그의 새 메시지에 서명할 수 있는 새로운 다이제스트를 생성하는 것은 사소한 일이다. 

새 서명: 0e41270260895979317f3898ab85668953aa2

서버는 새 서명과 새 데이터를 새 요청에 결합해 비밀번호만 알았을 경우 생성됐을 서명과 동일해 위조 요청을 유효한 요청으로 본다.

참조

  1. ^ a b Vũ, Hoàng (2012-03-30). "MD5 Length Extension Attack Revisited - Vũ's Inner Peace". Archived from the original on 2014-10-29. Retrieved 2017-10-27.
  2. ^ Duong, Thai; Rizzo, Juliano (2009-09-28). "Flickr's API Signature Forgery Vulnerability" (PDF). Retrieved 2017-10-27.
  3. ^ Meyer, Christopher (2012-07-30). "Hash Length Extension Attacks". Retrieved 2017-10-27.
  4. ^ Bostrom, Michael (2015-10-29). "size_t Does Matter: Hash Length Extension Attacks Explained" (PDF). Retrieved 2020-11-23.
  5. ^ Keccak Team. "Strengths of Keccak - Design and security". Retrieved 2017-10-27. Unlike SHA-1 and SHA-2, Keccak does not have the length-extension weakness, hence does not need the HMAC nested construction. Instead, MAC computation can be performed by simply prepending the message with the key.
  6. ^ Lawson, Nate (2009-10-29). "Stop using unsafe keyed hashes, use HMAC". Retrieved 2017-10-27.