Obviously, a VPN's claim that it doesn't log should be met with extreme skepticism. There are real cases where use of a VPN that claimed to be logless directly led to arrests and lifetime sentences:
One of the most important things Yardbird stated were that everyone in the group who used Tor and remailers remained free, while those who relied on services such as Privacy.LI were arrested and convicted.
Let's put that aside and blindly assume that the VPN is being honest. Is it still possible to trace?
Traffic analysis attacks
It is absolutely possible, and there are even companies who buy traffic analysis information from ISPs in bulk and resell them, with Team Cymru explicitly advertising the ability to trace VPN connections*.
Even if a VPN is honest about their claim that they do not log, their upstream ISP certainly logs. It would be unheard of for them not to. For a VPN (as opposed to Tor), the ingress and egress go through the same ISP, allowing trivial traffic analysis attacks. I explained a bit of this in this answer. Take the following series of events, with the ISP being the upstream ISP of the VPN (or a proxy):
- ISP sees
203.0.113.42 send 253 bytes of data at t+0.
- ISP sees the proxy server send a 253 byte request to
example.com/foo.html at t+1.
- ISP sees
example.com send a 90146 byte reply at t+2.
- ISP sees
203.0.113.42 receive a 90146 byte reply at t+3.
From this, it becomes trivial to realize that
188.8.131.52 connected to
example.com/foo.html. This is a type of traffic analysis attack, specifically a traffic correlation attack. Virtually all ISPs keep this sort of information via NetFlow and similar ubiquitous systems.†
Network stack issues
There is another problem with a VPN. You have to realize that the term Virtual Private Network is now more a marketing term. VPNs were never designed with anonymity in mind. All it is designed for is to connect two systems and expose them to each other as virtual network interfaces with private IP addresses to simulate a genuine private (i.e. out-of-band) network. This has several issues:
- Your networking stack is "exposed", so a vulnerability in your kernel could be exploitable.
- For this same reason, TCP/IP fingerprinting can uniquely identify you, even behind a VPN.
- You are forced onto the same NAT as a large number of untrusted users, allowing them to attack you indirectly, sometimes even allowing them to discover things like your hostname.
Visualizing the issue
It's useful to see how this all works, visually, in the form of a diagram. The single line represents traffic under your home IP, and the double line represents traffic with a different IP. A traffic correlation attack involves correlating the activity (timing and sizes) of both types of traffic.
How a plain connection works:
Client ----[Client ISP]----+
Server <---[Server ISP]----+
How a VPN works:
Client ----[Client ISP]---[ ]----> VPN
[VPN ISP] |
Server <===[Server ISP]===[ ]=======+
How Tor works:
Client ----[Client ISP]---[ ]--> Node1
[Node1 ISP] |
+======[ ]==> Node2
[Node2 ISP] |
+======[ ]==> Node3
[Node3 ISP] |
Server <===[Server ISP]===[ ]======+
You can see in this diagram how the VPN's ISP is in the position to trivially correlate the two connections, compared to a mixnet like Tor where the first and last node's ISP must collaborate to have a chance at deanonymizing someone. This is not impossible, and an adversary who can see a significant portion of the internet at any given time may be able to pull this off a certain percentage of the time. It is very difficult to do, however, and the Tor protocol includes a number of features (both deployed and in active development) to make this even harder than it already is.
Another important thing to remember is that Tor will periodically switch the nodes it uses. Although the first node stays the same in order to avoid so-called Sybil attacks, the other two will change around every 10 minutes, or whenever a different domain is visited. This reduces the chance that the final node sees too much traffic over time. VPNs, on the other hand, will naturally be static targets.
What this all means
- Using a VPN (or proxy) does not protect you from the VPN's ISP revealing its logs, even if the VPN service is completely honest about their no-logging policy.
- Your networking stack is exposed and visible to any 3rd party server you connect to, allowing potential exploitation and TCP/IP fingerprinting.
- Anonymity networks like Tor provide some level of traffic correlation protection and hides your networking stack, though like all systems, it's not perfect.
If you need anonymity, you should use Tor without a VPN, unless a VPN is necessary to bypass a firewall that Tor cannot bypass, otherwise it would be superfluous.
* Disturbingly, CEO and founder of Team Cymru, Rabbi Rob Thomas, used to be on the Tor Project board of directors.
† Unlike VPNs, Tor is able to resist NetFlow monitoring by collapsing flow records with keepalives.