Update 2: as of 2011-01-19 (yes, the same day), the problem is fixed in the repository (revision 9f1405).
Update 3: AdaCore changed it's name from ACT several years ago. Changed all references to that name accordingly. Sorry about that. :)
Update 4: as Pascal Obry informed in his comment on this post, the updated version is available to all AdaCore customers and the GPL version has been updated at Open-DO forge.
A few weeks ago, the following video has been released:
Well, those guys did a great job not only studying this vulnerability but also spreading the news. Then the question arose: is Ada Web Server vulnerable to this sort of attack?
The short answer is: sadly yes. This post tries to explain how we have tested this issue.
Keep in mind that only if a few hours I managed to get this code working and managed to keep my server at 100% for over 3 minutes with only 46656 variables in my post request.
The compiler used was GNAT GPL 2011. The AWS version is 2.10.0. And the operating system is Sabayon Linux.
Introduction
It all started at the #ada IRC channel at freenode. As I am used to run AWS servers all around I was curious if my servers were vulnerable or not.
After some research on the web I realized there wasn't any official report on the issue and I couldn't find anything useful. So, I went to the chat room and started talking to jesselang.
He discovered the AWS uses the Ada.Strings.Hash function internally. As it isn't really complex I realized we where not safe.
This is the actual implementation of this function (which is actually inside the file s-strhas.adb in your GNAT distribution):
------------------------------------------------------------------------------
-- --
-- GNAT COMPILER COMPONENTS --
-- --
-- S Y S T E M . S T R I N G _ H A S H --
-- --
-- S p e c --
-- --
-- Copyright (C) 2009, Free Software Foundation, Inc. --
-- --
-- GNAT is free software; you can redistribute it and/or modify it under --
-- terms of the GNU General Public License as published by the Free Soft- --
-- ware Foundation; either version 3, or (at your option) any later ver- --
-- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
-- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
-- or FITNESS FOR A PARTICULAR PURPOSE. --
-- --
-- --
-- --
-- --
-- --
-- You should have received a copy of the GNU General Public License and --
-- a copy of the GCC Runtime Library Exception along with this program; --
-- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see --
-- --
-- GNAT was originally developed by the GNAT team at New York University. --
-- Extensive contributions were provided by Ada Core Technologies Inc. --
-- --
------------------------------------------------------------------------------
pragma Compiler_Unit;
package body System.String_Hash is
-- Compute a hash value for a key. The approach here is follows the
-- algorithm used in GNU Awk and the ndbm substitute SDBM by Ozan Yigit.
----------
-- Hash --
----------
function Hash (Key : Key_Type) return Hash_Type is
pragma Compile_Time_Error
(Hash_Type'Modulus /= 2 ** 32
or else Hash_Type'First /= 0
or else Hash_Type'Last /= 2 ** 32 - 1,
"Hash_Type must be 32-bit modular with range 0 .. 2**32-1");
function Shift_Left
(Value : Hash_Type;
Amount : Natural) return Hash_Type;
pragma Import (Intrinsic, Shift_Left);
H : Hash_Type;
begin
H := 0;
for J in Key'Range loop
H := Char_Type'Pos (Key (J))
+ Shift_Left (H, 6) + Shift_Left (H, 16) - H;
end loop;
return H;
end Hash;
end System.String_Hash;
Turns out this is a linear hash function. It should easy to come up with a reverse algorithm, but ...
Generating Strings with Colliding Hash
Generating a code for this should be hard. I haven't got lazy right from the start; I spent like 20 minutes trying to crack this up but as I have no previous experience in doing such thing and binary arithmetic isn't really my thing I decide to go for the brutal force approach. :)
So I generated a short string. Something arbitrary, such as "ccc" (that's actually what I used). And I implemented a dirty loop to generate substrings with 6 characters each with the same has. Bingo! I found out 12 strings but I decided to use only 8 of them for they only had alphanumeric characters.
And here is the pretty thing: as this hash function is linear all I had to do is to combine all those strings. I came up with 46656 combinations in total - only because I didn't want big variable names in my post requests.
Another thing I found out is that it seems to be quite more likely to have collisions in bigger strings. First I tested against "tt" I and came up with only 4 usable collisions. Adding another character gave me twice as much. I haven't really tested this though.
The attack
I decided to use AWS.Client to implement my attack on AWS.Server. Ironic, isn't it?The code is really simple. Using unbounded string as a buffer I generated a string containing all the post data I needed. And then I invoked the AWS.Client.Post function. The client code is quite fast (really, less than 1 second).
Now the server code. I just implemented a hello world. Simply as that. It's actually a slightly changed version of the code listed in Gem #29 AdaCore have published. The changes where just to check if I was calling AWS.Client right, before I did the not-so-tricky part of generating the post data. Of course.
The results
I ran both client and server in a computer with AMD Athlon(tm) II X4 640 Processor and 4gB ram. The client being small I see no problem. :)
As expected, the client kept my server using 100% of one core. It stayed that way until the process completion, which took well over 3 minutes.
Firing up 5 client instances managed to get a DoS.
Both brutal force, client and server codes have been forwarded to jesselang's email address who kindly will report back to Ada Core Technologies. With any luck we will be seeing a patch for this in the near future.
Conclusion
It was a really bad surprise finding any information about this issue online. I don't know if Ada Core has been working on it already of they have ignored it completely. Until there is a fix for this available, let's hope no one uses this to damage running systems.
Even more astonishing is that the development community (with the exception of perl community) assumed plain Hash tables are great for everything. I've avoided it in the past for security reasons myself. After seeing anyone using hash table I decided to use it a lot.... and now I've been using Hash table myself to represent json data and key/value pairs from configuration files. Time to review all my code. :)
