I have read a blog post, where you can build your own privacy proxy server built on Raspberry PI. The post got me thinking about how I can use this to protect my privacy on my Android phone, and also get rid of those annoying ads. 

Since I own a Samsung Galaxy S3 LTE with Android 4.3 (with a HW based Knox counter), rooting the phone now means you break Knox, and loose warranty. Past the point of no return ...

This means I have to solve this without root. Luckily newer Androids support VPN without rooting, but setting a mandatory system-wide proxy is still not possible without root. 

But thanks to some iptables magic and Privoxy, this is not a problem anymore :) 

The ingredients to build your own privacy protection proxy:

To get the cheap VPS server, I recommend using Amazon EC2, but choose whatever you like. The micro instance is very cheap (or even free), and has totally enough resources for this task. I'm using the Ubuntu free tier now and it works like a charm. And last but not least Amazon has two-factor authentication! You can set up an Ubuntu server under 10 minutes. Use the AWS region nearest to you, e.g. I choose EU - Ireland.

VPN

For the VPN program, I recommend the free version of the OpenVPN AS (EDIT: be sure to use OpenVPN AS 2.0.6 or later, both on the server and the client). Easy to set-up quick start guide is here, GUI based configuration, and one-click client installer for Android, iOS, Windows, Linux, OSX. The Ubuntu installer packages are here.

The most important settings:

• I prefer to use the TCP 443 and UDP 53 ports for my OpenVPN setup, and let the user guess why. 
• For good performance, UDP is preferred over TCP. 
• VPN mode is Layer 3 (routing/NAT).
• Don't forget to allow the configured VPN ports in the AWS firewall (security groups). 

Other VPN settings:

• listen-address your.ip.add.ress:8118
• accept-intercepted-requests 1

Beware not to allow everyone accessing your Privoxy server in the AWS EC2 security groups, be sure it is reachable only to VPN users!

After everything is set, start privoxy with "service privoxy start", and add it to the autostart "update-rc.d privoxy defaults".

Iptables

And the final step is to configure your iptables chain to forward every web traffic from the VPN clients to the Privoxy server:

iptables -t nat -A PREROUTING -s 5.5.0.0/16 -p tcp -m multiport --dports 80,8080,81 -j DNAT --to-destination your.ip.add.ress:8118

Optionally you can block access to all other ports as well, and what does not go through your Privoxy won't be reachable.

Based on your Linux distribution and preference, you might make this rule persistent.

Final test

Now you can connect to the VPN server from your Android device.
After connecting, the final results can be seen in the following screenshots. And yes, there is a reason I chose Angry Birds as an example.

Spoiler alert

If you are afraid of NSA tracking you, this post is not for you. If you want to achieve IP layer anonymity, this post is not for you. As long as you are the only one using that service, it should be trivial to see what could possibly go wrong with that.

Known issues

Whenever the Internet connection (Wifi, 3G) drops, the VPN connection drops as well, and your privacy is gone ...

Sites breaking your privacy through SSL can still do that as long as the domain is not in the Privoxy blacklist.

Additional recommendation

If you are using OSX or Windows, I can recommend Aviator to be used as your default browser. It is just great, give it a try!

PS: There are also some adblock apps removed from the official store which can block some ads, but you have to configure a proxy for every WiFi connection you use, and it is not working over 3G.