hash dos 공격 with Tomcat

 

<시작하며..>

(2011-2012) 작년 연말/올해 연초 부터 hash dos 공격에 대한 보안 취약성에 대한 얘기가 있었다. 관련 내용을 정리해서 올려본다.

 

<시작>

12월 29일 한 통의 메일을 톰캣 리더 개발자인 Mark Thomas로부터 메일을 받았다. dos 공격을 당할 수 있는 내용에 대해서 oracle은 패치를 하지 않을 것이고, tomcat은 maxParameterCount의 값을 디폴트로 10000개로 지정하는 패치를 내어놓겠다고 했다.  톰캣 5 는 더이상 패치하겠다고 발표한 생태였지만, 패치를 하겠다고 얘기가 있었다.

 

[SECURITY] Apache Tomcat and the hashtable collision DoS vulnerability 11-12-29 (목) 07:28 보낸사람 : "Mark Thomas"<markt@apache.org> 주소록에 추가 받는사람 : "Tomcat Users List"<users@tomcat.apache.org> 참조     : <announce@tomcat.apache.org>, <announce@apache.org>, "Tomcat Developers List"<dev@tomcat.apache.org> You may have read about a recently announced vulnerability rooted in the Java hashtable implementation [1]. Since Apache Tomcat uses a hashtable for storing HTTP request parameters, it is affected by this issue. As per [1], it appears that Oracle will not be providing a fix for this vulnerability with in the JRE. Tomcat has implemented a work-around for this issue by providing a new option (maxParameterCount) to limit the number of parameters processed for a single request. This default limit is 10000: high enough to be unlikely to affect any application; low enough to mitigate the effects of the DoS. The work-around is available in: trunk 7.0.23 onwards 6.0.35 onwards The work-around will also be available in 5.5.35 once released. If using an earlier version of Apache Tomcat that does not have the maxParameterCount attribute available, limiting the maxPostSize to a few 10's of kB should also mitigate the issue although it may cause issues for some applications. While this is not viewed as a vulnerability in Apache Tomcat, the Apache Tomcat security team is making this announcement due to the high likelihood that applications will be affected by this issue and to make users aware of the available work-arounds. The Apache Tomcat security team [1] http://www.nruns.com/_downloads/advisory28122011.pdf

자세한 정보는 메일의 아래 문서에서 확인할 수 있다. http://www.nruns.com/_downloads/advisory28122011.pdf

<간략하게 소개하는 취약점과 테스트 자료>

대부분의 언어에서는 Hash table을 많이 사용하고 있다. 특히 웹 서비스의 경우는 hash table로 데이터를 매핑해서 쓴다. 특히 post 방식일 때는 hash table을 파라미터 값으로 자동으로 매핑한다. get 방식일 때는 파라미터의 길이에 대해서 이미 브라우져단/서버단에서 기본적으로 제한을 가져서 문제가 없다. 그러나 post 방식일 때는 파라미터 개수 제한이 없다. (물론 서버 설정에서 이를 설정상으로 막을 수 있다.)

이를 악용하여 공격자가 조작된 값(colliding keys)을 파라미터로 전달하여 cpu 를 소진시킬 수 있다. hash contension이 일어나도록 동일한 string key값을 보내서 서버에 부담을 준다. (multi-collisions)
또는 randomized hash function이 없는 경우에도 활용될 수 있다.
hash table의 약점을 노린 것으로 hash table에 파라미터 입력시 O(n**2)으로 complexity가 높아지면서 cpu를 소진시켜 서버가 서비스를 못하게 한다. 하나의 요청만으로 웹 서버의 서비스를 못하게 할 수 있다.

hashtable에 존재하는 값과 입력된 값이 다를 경우 충돌이 일어나고, 그 충돌되는 값이 많아지면서 해당 값들을 계속 비교하는 경우를 multi-collision이라고 한다.

You tube에는 이런 취약점을 이용해서 간단하게 테스트한 자료가 있다.

<

 

<자바 패치 >

2003년부터 이 부분이 알려져 있다. Rice 대학의 Crosby, Wallach 가 발표한 논문에 비슷한 논문이 있다.
http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003.pdf

Perl와 CRuby는 고쳐졌지만 php 4/5, V8, 자바, asp.net, Python, Ruby에 보안 취약이 있었다.

자바의 경우는 String.hasCode()  메서드를 이용한 HashMap, HashTable 클래스를 사용하고 있다. DJBX33A 알고리즘을 사용하는데. 이슈가 있다. 2011년 11월 1일 레드햇 버그질라에 이 문제에 대한 이슈가 올라왔었지만, 오라클은 이 부분에 대해서 자바 hashmap 구현을 바꾸지 않겠다고 했다. 즉 자바 언어의 hash 구현의 이슈가 아니라고 답변하였고 웹 서버(tomcat, jbossweb, flassfish)에서 처리되는 것으로 되었다. (개인적인 의견으로는 참 애매한 이슈인 것 같다. 원래 그렇게 최악의 상황을 감안하고 구현되었을 수도 있고, 이거 고쳐서 backward compatibility를 잃어버리는 것보다는 나을 수 있다는 생각도 든다. 굳이 고쳐서 탈나는 것보다는 이게 나을 수도 ^^;;;)

https://bugzilla.redhat.com/show_bug.cgi?id=750533

그래서 12월 29일 close가 되었고, tomcat 리더 개발자인 mark tomas는 메일을 보낸 것이었다.

 

<톰캣 패치>

6.0.35, 7.0.23이 바로 패치되었고, 5.5.35는 늦게 패치가 되었다.

위에서 얘기한 Connector의 필드값으로 maxParameterCount 개수를 지정하면 문제를 해결하면 된다.

http://tomcat.apache.org/tomcat-6.0-doc/config/ajp.html

 

패치 할 수 없는 상황에서는 maxPostSize 를 이용할 수도 있다.

 

핵심 코드가 바뀌었는지 간단히 살펴본다.

http://www.mail-archive.com/dev@tomcat.apache.org/msg57020.html

Connector.java

maxParameterCount 파라미터를 읽는다.

tomcat/trunk/java/org/apache/catalina/connector/Connector.java      /** +     * The maximum number of parameters (GET plus POST) which will be +     * automatically parsed by the container. 10000 by default. A value of less +     * than 0 means no limit. +     */ +    protected int maxParameterCount = 10000; +    /** +     * Return the maximum number of parameters (GET plus POST) that will be +     * automatically parsed by the container. A value of less than 0 means no +     * limit. +     */ +    public int getMaxParameterCount() { +        return maxParameterCount; +    } + + +    /** +     * Set the maximum number of parameters (GET plus POST) that will be +     * automatically parsed by the container. A value of less than 0 means no +     * limit. +     * +     * @param maxParameterCount The new setting +     */ +    public void setMaxParameterCount(int maxParameterCount) { +        this.maxParameterCount = maxParameterCount; +    }

 

tomcat/trunk/java/org/apache/tomcat/util/http/Parameters.java

기존에는 간단하게 Hashtable<String,String[]>의 값을 저장했지만, 새로 바뀐 버전에는 Hashtable<String,ArrayList<String>> 타입으로 바꾸었다.

-    private final Hashtable<String,String[]> paramHashStringArray = -        new Hashtable<String,String[]>(); ==> +    private final Hashtable<String,ArrayList<String>> paramHashValues = +        new Hashtable<String,ArrayList<String>>();

 

구버전까지는 key값에 대한 value값을 array list로 해서 계속 추가되는 형태이다. 반면 신버전에서는 Capacity의 크기를 체크한 후 값을 저장하는 코드로 바뀌었다. 이 값은

-        String values[]; -        if (paramHashStringArray.containsKey(key)) { -            String oldValues[] = paramHashStringArray.get(key); -            values = new String[oldValues.length + newValues.length]; -            for (int i = 0; i < oldValues.length; i++) { -                values[i] = oldValues[i]; -            } -            for (int i = 0; i < newValues.length; i++) { -                values[i+ oldValues.length] = newValues[i]; -            } -         } else { -            values = newValues;           } -        paramHashStringArray.put(key, values);      } ==> +        ArrayList<String> values; +        if (paramHashValues.containsKey(key)) { +             values = paramHashValues.get(key);          } else { +            values = new ArrayList<String>(1); +            paramHashValues.put(key, values); +        } +        values.ensureCapacity(values.size() + newValues.length); +        for (String newValue : newValues) { +            values.add(newValue);          }

<아파치 해결>

LimitRequestBody 값으로 개수를 지정한다. 디폴트값은 1000000(백만)이라서 조절이 필요할 수 있다.
http://httpd.apache.org/docs/2.0/mod/core.html

<Directory "/home/www/web">
    LimitRequestBody 102400
</Directory>

 

* 참고 사항

이 메일의 배경은 12월 28일 독일에서 열린 Chaos Communication Congress의  Julian zeri Walde가 발표로 인해서 알려졌다. 자세한 내용은 아래와 같다. 원리에 대한 설명이 있다.

http://events.ccc.de/congress/2011/Fahrplan/attachments/2007_28C3_Effective_DoS_on_web_application_platforms.pdf

간단하게 이 자료를 소개하면서 자바의 소스를 분석해본다.

일반적으로 hash table은 O(n) 방식으로 내용을 검색하거나 추가할 수 있다.

 

그러나 하나의 키에 계속 값이 붙는 screwed 상황이 일어날 수 있다.  이 때는 O(n**2)가 되어서 속도가 저하되는 이슈가 있다.

 

 

만약 10bytes 짜리 20만개를 최악의 케이스로 넣는 다면, 40,000,000,000 번의 string 비교가 일어나고 40초가 걸릴 수 있다. (참고로 String intern, String compare는 비싼 자원이다..)

 

자바의 내부는 String hash값은 어떻게 되어 있을까?

public final class String     implements java.io.Serializable, Comparable<String>, CharSequence { /** Cache the hash code for the string */ private int hash; // Default to 0 /**      * Returns a hash code for this string. The hash code for a      * <code>String</code> object is computed as      * <blockquote><pre>      * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]      * </pre></blockquote>      * using <code>int</code> arithmetic, where <code>s[i]</code> is the      * <i>i</i>th character of the string, <code>n</code> is the length of      * the string, and <code>^</code> indicates exponentiation.      * (The hash value of the empty string is zero.)      *      * @return  a hash code value for this object.      */     public int hashCode() {     int h = hash;         int len = count;     if (h == 0 && len > 0) {         int off = offset;         char val[] = value;             for (int i = 0; i < len; i++) {                 h = 31*h + val[off++];             }             hash = h;         }         return h;     } }

 

결국 hash code 공식은 다음 공식을 따른다.

hash code = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

위키에 좀더 멋진 공식 표현이 있다. (http://en.wikipedia.org/wiki/Java_hashCode())

 

멋진 공식이라 하더라도. hash value는 int 라는 제한적인 값(min<int<max) 범위에 있기 때문에 중복될 수 있다. 또한 아래와 같이 동일한 hashcode를 생성할 수 있다. 이런 것을 악용한다면, 웹 서버들을 장애를 일으킬 수 있을 것이다.

public class a1 {     public static void main(String[] args) {         System.out.println(new String("FB").hashCode());         System.out.println(new String("Ea").hashCode());     } } #결과 2236 2236

 

생각해보면, hashcode는 unique한 값이 아닌 적당하게 써서 관리하기 위한 목표를 가지고 있다. 취약점을 어쩔 수 없으니. 적당하게 크기 제한하는 것이 좋은 사례인 것 같다..


PS
2012년 1월 17일 Mark Tomas는 정식으로 메일을 보냈다.
http://mail-archives.apache.org/mod_mbox/tomcat-announce/201201.mbox/%3C4F155CE2.3060301%40apache.org%3E

CVE-2012-0022 Apache Tomcat Denial of Service

Severity: Important

Vendor: The Apache Software Foundation

Versions Affected:
- Tomcat 7.0.0 to 7.0.22
- Tomcat 6.0.0 to 6.0.33
- Tomcat 5.5.0 to 5.5.34
- Earlier, unsupported versions may also be affected

Description:
Analysis of the recent hash collision vulnerability identified unrelated
inefficiencies with Apache Tomcat's handling of large numbers of
parameters and parameter values. These inefficiencies could allow an
attacker, via a specially crafted request, to cause large amounts of CPU
to be used which in turn could create a denial of service.
The issue was addressed by modifying the Tomcat parameter handling code
to efficiently process large numbers of parameters and parameter values.

Mitigation:
Users of affected versions should apply one of the following mitigations:
- Tomcat 7.0.x users should upgrade to 7.0.23 or later
- Tomcat 6.0.x users should upgrade to 6.0.35 or later
- Tomcat 5.5.x users should upgrade to 5.5.35 or later

Credit:
The inefficiencies in handling large numbers of parameters were
identified by the Apache Tomcat security team.

References:
http://tomcat.apache.org/security.html
http://tomcat.apache.org/security-7.html
http://tomcat.apache.org/security-6.html
http://tomcat.apache.org/security-5.html