Tags: data-structure hash-collision
Rating:
**Description**
> We advise you to replace uses of `unordered_hash` with our new `SecureHashtable` class, since we added advanced crypto to make it 14.3 times more secure.
>
> Update: the binary was compiled with g++ and libstdc++, 64bit
>
> We're running a demo version, try it now:
>
> `nc secure-hash.ctf.hackover.de 1337`
**Files provided**
- [`secure_hash.cpp`](https://github.com/EmpireCTF/empirectf/blob/master/writeups/2018-10-05-Hackover-CTF/files/secure_hash.cpp)
**Solution**
The service provided lets us register and login using a supposedly secure [hash table](https://en.wikipedia.org/wiki/Hash_table) implementation, built atop a [`std::unordered_set`](http://www.cplusplus.com/reference/unordered_set/unordered_set/).
```cpp
if (choice == 1) {
if (name == "root") {
printf("You are not root!\n");
continue;
}
table.insert_keyvalue(name, password);
} else if (choice == 2) {
if (table.lookup_keyvalue(name, password)) {
printf("Success! Logged in as %s\n", name.c_str());
if (name == "root") {
printf("You win, the flag is %s\n", flag.c_str());
return 0;
}
} else {
printf("Invalid credentials!\n");
}
} else {
printf("Invalid choice!\n");
}
```
Registration is achieved by inserting values with `table.insert_keyvalue`, and logging in by checking with `table.lookup_keyvalue`. We are not allowed to register a(nother) user with `name == "root"`, so if the program had no other vulnerabilities, we would only be able to log in as `root` if we already knew the flag, which is the password to the `root` account.
An important thing to note is that `lookup_keyvalue` does not return a boolean!
```cpp
enum auth_result {
AUTH_FAILURE,
AUTH_SUCCESS,
AUTH_TIMEOUT,
};
auth_result lookup_keyvalue(const std::string& name, const std::string& password);
```
And since by default, `0` is assigned to the first value of an enum, `1` to the second, and so on, `AUTH_SUCCESS` and `AUTH_TIMEOUT` are both truthy results, and both will sucessfully let us log in. The timeout is not difficult to trigger either:
```cpp
size_t iterations = 0;
size_t MAX_ITERATIONS = 1000;
while (it != end) {
if (*it++ == digest)
return AUTH_SUCCESS;
// Avoid DoS attacks by fixing upper time limit.
if (iterations++ >= MAX_ITERATIONS)
return AUTH_TIMEOUT;
}
```
Whenever the program has to look through more than `1000` values that all fall into the same bucket of the `std::unordered_set`, it will give up and let us log in. The bucket used is determined based on some SHA-512 digest:
```cpp
std::string digest = sha512sum(name, password);
size_t bucket = values.bucket(digest);
```
The `sha512sum` function itself uses OpenSSL to do the hashing, and [documentation for the `EVP_` functions can easily be found](https://linux.die.net/man/3/evp_digestupdate):
```cpp
std::string sha512sum(const std::string& name, const std::string& password) {
EVP_MD_CTX *mdctx;
const EVP_MD *md;
unsigned char md_value[EVP_MAX_MD_SIZE];
unsigned int md_len;
mdctx = EVP_CREATE_FN();
md = EVP_get_digestbyname("sha512");
EVP_MD_CTX_init(mdctx);
EVP_DigestInit_ex(mdctx, md, NULL);
EVP_DigestUpdate(mdctx, name.c_str(), name.size());
EVP_DigestUpdate(mdctx, password.c_str(), password.size());
EVP_DigestFinal_ex(mdctx, md_value, &md_len);
EVP_DESTROY_FN(mdctx);
return std::string(reinterpret_cast<char*>(md_value), md_len);
}
```
In particular, notice that `name` and `password` are added to the digest one after another, and that the number of bytes added is determined using [`std::string::size`](http://www.cplusplus.com/reference/string/string/size/), which returns the number of actual bytes of the string, not including the null byte (assuming it is even used internally).
This means that with `name == "foo"` and `password == "bar"`, the digest gets updated with the three bytes `foo`, then the three bytes `bar`. Do you see the problem?
The same result can be achieved with e.g `name == "fo"` and `password = "obar"`, and so these two sets of credentials will result in the same digest and therefore the same bucket in the `std::unordered_set`.
Now we have everything needed to exploit the program. We start by adding 1000 users with `name == "ro"` and `password == "ot1"`, then simply attempt a login with `name == "root"` and `password == "1"` (the `1` was used because neither field could be empty). All of these credentials (duplicates are not checked, but simply inserted again and again) have the same digest and so they end up in the same bucket.
([Full exploit script here](https://github.com/EmpireCTF/empirectf/blob/master/writeups/2018-10-05-Hackover-CTF/scripts/secure_hash.sh))
`hackover18{00ps_y0u_mu5t_h4ve_h1t_a_v3ry_unlikely_5peci4l_c4s3}`
