Iptables – Instance in private subnet can connect internet but can’t ping/traceroute

I have an AWS VPC with some public subnets and a private subnet, like the image below.

• Both instances can connect to the internet (INSTANCE A connects through NAT GATEWAY instance)
• NAT GATEWAY can ping and traceroute hosts on internet and instances on other subnets
• INSTANCE A can ping NAT GATEWAY and other instances in its subnet and other subnets

The NAT GATEWAY is a Ubuntu 16.04 (t2.micro) instance, configured by me. It's not a managed AWS NAT gateway. It's working perfectly as a gateway for all other hosts inside the VPC, as well for D-NAT (for some private Apache servers) and also acting as a SSH Bastion.

The problem is that INSTANCE A can't ping or traceroute hosts on internet. I've already tried/checked:

• Route tables
• Security groups
• IPTABLES rules
• kernel parameters

Security Groups

 NAT GATEWAY
 Outbound: 
  * all traffic allowed
 Inbound:
  * SSH from 192.168.0.0/16 (VPN network)
  * HTTP/S from 172.20.0.0/16 (allowing instances to connect to the internet)
  * HTTP/S from 0.0.0.0/0 (allowing clients to access internal Apache servers through D-NAT)
  * ALL ICMP V4 from 0.0.0.0/0 


 INSTANCE A
 Outbound: 
  * all traffic allowed
 Inbound:
  * SSH from NAT GATEWAY SG
  * HTTP/S from 172.20.0.0/16 (public internet throught D-NAT)
  * ALL ICMP V4 from 0.0.0.0/0

Route tables

PUBLIC SUBNET
172.20.0.0/16: local
0.0.0.0/0: igw-xxxxx (AWS internet gateway attached to VPC)

PRIVATE SUBNET
0.0.0.0/0: eni-xxxxx (network interface of the NAT gateway)
172.20.0.0/16: local

Iptables rules

# iptables -S
-P INPUT ACCEPT
-P FORWARD ACCEPT
-P OUTPUT ACCEPT

# iptables -tnat -S
-P PREROUTING ACCEPT
-P INPUT ACCEPT
-P OUTPUT ACCEPT
-P POSTROUTING ACCEPT
-A POSTROUTING -o eth0 -j MASQUERADE

Kernel parameters

net.ipv4.conf.all.accept_redirects = 0  # tried 1 too
net.ipv4.conf.all.secure_redirects = 1
net.ipv4.conf.all.send_redirects = 0  # tried 1 too
net.ipv4.conf.eth0.accept_redirects = 0  # tried 1 too
net.ipv4.conf.eth0.secure_redirects = 1
net.ipv4.conf.eth0.send_redirects = 0  # tried 1 too
net.ipv4.ip_forward = 1

Sample traceroute from INSTANCE A

Thanks to @hargut for pointing out a detail about traceroute using UDP (and my SGs not allowing it). So, using it with -I option for ICMP:

# traceroute -I 8.8.8.8
traceroute to 8.8.8.8 (8.8.8.8), 30 hops max, 60 byte packets
 1  ip-172-20-16-10.ec2.internal (172.20.16.10)  0.670 ms  0.677 ms  0.700 ms
 2  * * *
 3  * * *
 ...