The first sudo I enter on my Ubuntu 14.04 server is always slow. The password prompt displays immediately, but after I press enter it takes about 10-15 seconds until the output is printed. All sudo commands after this execute instantly.
Running something like sudo strace -S time -c sudo echo hi does not show anything useful in this case, since the sudo from sudo echo hi is already the second sudo and executes fast. If some time passes and I have to re-enter the password in a running session, it is slow again.
All the solutions I found were about adding your hostname as resolution for 127.0.0.1 in the /etc/hosts file, which I did to no avail. su root executes instantly. The only thing I remember changing in the last days is the netmask of a subnet the server is routing, installing samba, dnsutils and bind9. But none of those processes are running and the problem remains, in physical access, ssh sessions as well as tmux sessions.
EDIT: New Approach
I tried running sudo tcpdump -vvvi any > tcpdump.log while having all NIC's disconnected. The log shows a lot of the following:
18:35:09.453399 IP (tos 0x0, ttl 64, id 49112, offset 0, flags [DF], proto UDP (17), length 76)
localhost.38498 > localhost.domain: [bad udp cksum 0xfe4b -> 0x1050!] 58546+ SRV? _kerberos._udp.KF.OURLOCALDOMAIN.DE. (48)
18:35:09.457412 IP (tos 0x0, ttl 64, id 49113, offset 0, flags [none], proto UDP (17), length 76)
localhost.domain > localhost.38498: [bad udp cksum 0xfe4b -> 0x8fcd!] 58546 ServFail q: SRV? _kerberos._udp.KF.OURLOCALDOMAIN.DE. 0/0/0 (48)
Same entries show up with tcp instad of udp. I replaced the domain name of our university with OURLOCALDOMAIN.
Now I think kerberos might have something to do with it, but I deleted the /etc/krb5.conf and rebooted, still no change. It seems to me, that the server tries to validate itself on a central kerberos server from our university network. I know that some years prior, this IP was registered to a server that ran samba for our departement. Could there be a connection? I changed my hostname to the one that was used back then, no change in sudo behavior. Lmwangi suggests something about PAM, which i have little knowledge about, so I don't know how to approach this.
I also remembered I switched from Heimdal Kerberos to MIT Kerberos when installing samba, because i had troubles during the samba installation.
I am also going to try the ideas from the comments in the next days, but I will be traveling for a couple days so it might take some time.
EDIT 2: Solved
There was a legacy dns-search entry in the /etc/network/interfacesthat messed everything up. I feel very stupid. Everything works now.
Best Answer
I'd suspect that your box is attempting to contact an external authentication service (think of NIS/LDAP) using PAM...
If I understand PAM right, you wouldn't be able to see the PAM lookup in your strace calls. I'd suggest that you run tshark/tcpdump and see if you can correlate specific network traffic to your sudo attempts. Suspects here would be DNS lookups &| LDAP calls.
If you do find out what's causing the lookups, find out the relevant PAM module to edit and fix the issue. Alternatively, if it's a DNS lookup, just add an /etc/hosts entry to fake the name and redirect to localhost. This will make your sudo fast since the lookup will be fast and will redirect to the localhost and the network transaction will fail fast since there's nothing listening on localhost...